“本文來自天池優秀選手yche，他針對落幕不久的第一屆POLARDB資料庫性能大賽兩道賽題：實作一個簡化、高效的kv存儲引擎，支援Write、Read以及Range接口，整理了一套詳細的比賽攻略，小天今天把這套冠軍整理的baseline分享出來，希望有更多的天池小寶貝們盤下這波分享，下屆POLARDB資料庫性能大賽穩得飛起喲~”
△第一屆POLARDB資料庫性能大賽排名
一、比賽攻略
注意：詳細代碼和答辯PPT下載下傳請檢視Github倉庫
http://t.cn/EMlV8Pk Rapids團隊成員: CheYulin, SunShixuan, WangLipeng。1. 賽題介紹
評測程式分為2個階段：
1）Recover正确性評測： 此階段評測程式會并發寫入特定資料（key 8B、value 4KB） 同時進行任意次kill -9來模拟程序意外退出（參賽引擎需要保證程序意外退出時資料持久化不丢失），接着重新打開DB，調用Read、Range接口來進行正确性校驗。
2）性能評測
随機寫入：64個線程并發随機寫入，每個線程使用Write各寫100萬次随機資料（key 8B、value 4KB）
随機讀取：64個線程并發随機讀取，每個線程各使用Read讀取100萬次随機資料
順序讀取：64個線程并發順序讀取，每個線程各使用Range有序（增序）周遊全量資料2次
注： 2.2階段會對所有讀取的kv校驗是否比對，如不通過則終止，評測失敗； 2.3階段除了對疊代出來每條的kv校驗是否比對外，還會額外校驗是否嚴格遞增，如不通過則終止，評測失敗。
2. 最終線上效果
程序耗時
順序讀取中，在記憶體并發讀取visit總時間大概在105-110秒，吞吐量: 284.1-296.2 GB/s 。
程序啟動間隔(波動不大，取其中一次作為樣本)
曆史最佳成績離理論曆史最佳成績累加差了0.69 seconds； 這應該是與機器讀寫性能波動有關，其中寫性能波動最大。
二、賽題背景分析及了解
1. 賽題注意點
Recover正确性評測要求: 每次Write調用都要将資料至少寫入到page-cache。
每個階段開始，DB Engine都會被重新打開； 每個階段進行中， 隻有讀取或者寫入中的一種情況發生； 每一階段結束，page cache會被清空(清空page cache的時間占用總時間)。
對于複賽的順序讀取，recovery階段使用單線程，并且隻周遊全量資料1次，選手需要做相應處理。
評測中， Key-Value大小都是固定的， Key可用64bit無符号整數表示，并且分布均勻。
評測中，允許使用的最大記憶體2GB (不計評測程式記憶體占用)；各子階段會有固定的64線程随機寫入或随機讀取或順序讀取。
2. 賽題分析
傲騰存儲特征
為達到磁盤的峰值吞吐量， 需要保證iostat中的兩個關鍵參數avgrq-sz(扇區個數，一般每個扇區512B)和avgqu-sz(IO隊列長度) 處于合适大小。 并且每個request有最大大小，不能設定太大，具體可以檢視blockdev --getmaxsect /dev/sda(/dev/sda為檢視的裝置)。
随機讀寫隻要有合适大小塊(avgrq-sz)，保證足夠IO隊列長度(avgqu-sz)就可以達到接近順序讀寫的效果。
順序讀取通過128KB大小請求,QD=8可以達到2595-2605 MB/s左右。
随機讀取4KB大小請求, QD=20+可以達到2290 MB/s左右，波動很小。
随機寫入16KB大小請求, QD=20+可以達到2180-2200 MB/s。
注意點
随機寫入：保證iostat中的合适大小的avgrq-sz(通過實驗測得 mmap buffer 16KB比較優)， 保證avgqu-sz(handle tail threads)，至少需要QD=8(實驗中測得8,16,32都差不多)，通過寫檔案時候系統的同步(鎖)。
随機讀取：保證iostat中的合适大小的avgqu-sz(handle tail threads)。
順序讀取：保證iostat中的合适avgrq-sz和avgqu-sz。做好充分的overlap-io和記憶體通路(100-110秒左右)。
三階段是獨立進行的(無混合的讀寫操作)，是以評測不要求索引支援O(logn)或更低複雜度的動态插入。
三、核心思路
每一階段結束，page cache會被清空。 是以，整體設計中除了記憶體映射檔案(meta-file, key/val buffer files), 其他檔案操作都通過DirectIO。
1.儲存和索引設計
檔案設計
Key和Value都使用write-ahead-log方式，順序append到相應位置，并通過一個meta檔案記錄相應記錄個數。
Value大小固定為4KB，是以在設計索引時候可以不存Value長度， 并且可以将偏移量直接除以4KB來減少空間占用。
Key大小固定為8B， 根據PolarString定義, Key可以被轉化為64bit-Big-Endian無符号整數表示， Key分布比較随機，是以可按Key分Bucket來設計存儲結構, 來支援并發恢複索引。
可以将Key-Value在寫入時候一一對應，這樣就不用寫偏移量，而通過順序周遊write-ahead-log恢複出來。
索引設計
評測中不要求索引支援O(logn)或更低複雜度的動态插入，是以采用 bucket + sorted array 的方案； 按照Key的Big-Endian無符号整數高位分bucket，每個Bucekt内采用根據Bucket内偏移比較的sorted array； 通過計算bucket id 和 branchless-lower-bound加跳過重複支援value in-bucket offset查詢。
并行索引建構(0.2秒，throughput = 488.28125MB/0.2s = 2441.4 MB/s)，每個線程配置設定一些buckets， 因為每個bucket的大小均勻是以workload balanced，多bucket使得sort時間可以忽略， 此外sort還和io overlap在一起。
寫入相關的檔案設計
寫入buffer必須使用檔案作為backend的(通過mmap)，來保證正确性。
考慮到range時候順序讀盤更快，寫入時候同一bucket寫在同一區域。
2.檔案設計
key/value write-ahead logs 各32個(一個檔案裡面分bucket, bucket id相鄰的在檔案中相鄰)。
meta-file, mmap key buffer file, mmap value buffer file各1個, slice成BUCKET_NUM的views (e.g. 1024)。
檔案整體設計分為三部分: (1) K-V-Log檔案, (2) Meta-Count檔案, (3) Key/Value Buffer檔案。
2.1 K-V Log檔案
key-value的對應: 邏輯上, key-value被寫到一個的相同bucket, 對應到相同的in-bucket offset, 通過write-ahead追加到對應的log檔案。 我們把8-byte-key通過big-endian轉化出uint64_t類型的整數key。
對應從key到bucket_id的計算如下代碼所示：
inline uint32_t get_par_bucket_id(uint64_t key) {
return static_cast<uint32_t >((key >> (64 - BUCKET_DIGITS)) & 0xffffffu);
} 邏輯上的bucket到實際中的檔案, 通過下面的函數算出, 在設計中, 我們讓相鄰的value buckets被group到同一個value log file, 來為range查詢順序讀服務。
inline pair<uint32_t, uint64_t> get_key_fid_foff(uint32_t bucket_id, uint32_t bucket_off) {
constexpr uint32_t BUCKET_NUM_PER_FILE = (BUCKET_NUM / KEY_FILE_NUM);
uint32_t fid = bucket_id / BUCKET_NUM_PER_FILE;
uint64_t foff = MAX_KEY_BUCKET_SIZE * (bucket_id % BUCKET_NUM_PER_FILE) + bucket_off;
return make_pair(fid, foff * sizeof(uint64_t));
}
inline pair<uint32_t, uint64_t> get_value_fid_foff(uint32_t bucket_id, uint32_t bucket_off) {
// Buckets 0,1,2,3... grouped together.
constexpr uint32_t BUCKET_NUM_PER_FILE = (BUCKET_NUM / VAL_FILE_NUM);
uint32_t fid = bucket_id / BUCKET_NUM_PER_FILE;
uint64_t foff = MAX_VAL_BUCKET_SIZE * (bucket_id % BUCKET_NUM_PER_FILE) + bucket_off;
return make_pair(fid, foff * VALUE_SIZE);
} 最終設計中, 我們采用了32個value檔案和32個key檔案。 這是因為多線程寫入同一檔案時候可以有一定的同步作用(有寫入鎖的存在), 來緩解最後剩下tail threads打不滿IO的情況。 此外，檔案過多容易觸發Linux作業系統的bug，從DirectIO進入BufferIO, 即使已經标志flag設定了O_DIRECT.
2.2 Meta-Count 檔案
meta-count檔案用來記錄每個bucket中現在write-ahead進行到第幾個in-bucket位置了, 該檔案通過記憶體映射的方式, 來通過操作對應數組mmap_meta_cnt_， 記錄每個bucket寫入write-ahead-entry個數。
// Meta.
meta_cnt_file_dp_ = open(meta_file_path.c_str(), O_RDWR | O_CREAT, FILE_PRIVILEGE);
ftruncate(meta_cnt_file_dp_, sizeof(uint32_t) * BUCKET_NUM);
mmap_meta_cnt_ = (uint32_t *) mmap(nullptr, sizeof(uint32_t) * (BUCKET_NUM),
PROT_READ | PROT_WRITE, MAP_SHARED, meta_cnt_file_dp_, 0);
memset(mmap_meta_cnt_, 0, sizeof(uint32_t) * (BUCKET_NUM)); 2.3. Key/Value Buffer 檔案
buffer files用來在寫入時候進行對每個bucket-entries的buffer (通過記憶體映射檔案得到aligned buffer, 來具備kill-9容錯功能). 一個bucket對應相應的key-buffer和value-buffer; 所有的key-buffers從一個key-buffer檔案記憶體映射出來; 同理所有的val-buffers從一個val-buffer檔案映射出來。
我們給出一個Value Buffer檔案的示例, Key Buffer檔案相關的設計與之類似。
// Value Buffers. (To be sliced into BUCKET_NUM slices)
value_buffer_file_dp_ = open(value_buffers_file_path.c_str(), O_RDWR | O_CREAT, FILE_PRIVILEGE);
if (value_buffer_file_dp_ < 0) {
log_info("valbuf err info: %s", strerror(errno));
exit(-1);
}
ftruncate(value_buffer_file_dp_, tmp_buffer_value_file_size);
mmap_value_aligned_buffer_ = (char *) mmap(nullptr, tmp_buffer_value_file_size, \
PROT_READ | PROT_WRITE, MAP_SHARED, value_buffer_file_dp_, 0);
for (int i = 0; i < BUCKET_NUM; i++) {
mmap_value_aligned_buffer_view_[i] =
mmap_value_aligned_buffer_ + VALUE_SIZE * TMP_VALUE_BUFFER_SIZE * i;
}
在設計中, 我們使用了16KB value buffer 和 4KB key buffer, 分别整除VALUE_SIZE和sizeof(uint64_t)。 我們選擇較小的buffer是為了讓IO盡可能快地均衡地被打出去(不要有很少的線程最後還在打IO以緻于打不滿), value buffer不選擇更小是為了防止sys-cpu過高影響性能，并且我們對磁盤的benchmark顯示16KB是一個比較優的值。
3.寫入階段思路
清空page cache占用總時間，傲騰存儲iops和throughput都高， 是以使用DirectIO繞過page cache手動管理緩沖和寫盤。
寫入時候先對bucket加鎖，将Key/Value一一對應，分别寫入這個bucket對應的key-mmap-buffer和value-mmap-buffer， 在buffer滿的時候寫入log檔案。
4.随機和順序讀取階段設計思路
随機讀取
做最小粒度的同步。奇數和偶數線程同步，來保證64線程間較小的讀取進度差别和穩定的queue-depth（24左右）。
嘗試了讀8KB，并進行緩存置換，命中率不高：2%；這說明通過讀更大block-size來優化随機讀取不可行。
順序讀取
流水線設計：io部分(io協調者， io線程)，通過set-affinity減少numa結點間的切換；記憶體讀取部分(64threads)同步讀一個bucket與下一塊bucket的io overlap在一起。
每塊buffer為一個讀取機關，io協調者通過送出任務給io線程打到合适avgrq-sz和avgqu-sz，進而打滿IO throughput，詳見io協調者。
流水線使用2塊buffer滾動。
在多次全量周遊中，偶數次次周遊重用奇數次的前幾塊buffer(塊數通過程式中的KEEP_REUSE_BUFFER_NUM指定，作為cache)。
5. 容錯(K/V Buffer Files Flush)的思路
大體思路: 我們通過ParallelFlushTmp并行flush key, value buffers; 該函數在寫入階段的析構函數調用(如果進行到對應代碼), 否則在讀取階段建構index前會調用。
優化: 我們通過ftruncate對應檔案長度為0表示所有buckets對應的需要flush的buffers已經Flush出去了, 避免重複的Flush. 相應邏輯在FlushTmpFiles函數中。
由于文章篇幅較長，代碼較多，是以小天将部分代碼和作者的比賽經驗放在下篇分享，後天見哦~