作者：王亞普
來源：http://wangyapu.com/2019/02/01/tianchi_polar_db/

這次天池 PolarDB 數據庫性能大賽競爭相當激烈，眼睛一閉一睜成績就會被血洗，最後榜單成績是第三名，答辯翻車了，最終取得了大賽季軍。雲計算領域接觸的是最前沿的技術，阿里雲的 PolarDB 作爲雲原生數據庫里程碑式的革新產品，也爲這次比賽提供了最先進的硬件環境。

整個比賽獲益良多，體會比較深的兩點：

  • 爲了充分使用新硬件, 榨乾硬件的紅利來達到極致的性能，一定要 Benchmark Everything，經驗並不一定是對的，實踐出真知。
  • 從大的解決方案，到小的細節優化，需要足夠的勇氣嘗試不同的思路，從而不斷完善，達到最優解。


比賽背景

  1. 以 Optane SSD 爲背景，實現高效的 KV 存儲引擎。
  2. 實現 Write、Read 和 Range 接口。
  3. 正確性檢測：保證進程意外退出不會造成數據丟失。
  4. 在規定時間內完成隨機寫、隨機讀、Range（順序讀）三個性能評測階段。

賽題剖析

  1. 正確性檢測 kill -9 模擬進程意外退出，需要保證數據不丟失。
  2. 只有 2G 物理內存可用。
  3. 64個線程併發順序讀取，每個線程各使用 Range 有序（增序）遍歷全量數據 2 次。設計出有利於 Range 並且兼顧讀寫性能的架構至關重要。
  4. 隨機寫、隨機讀、順序讀三個階段都會重新 Open DB，儘可能挖掘 Open 階段的細節優化點。
  5. Drop Cache 的時間也計入總成績，儘可能減少 PageCache 的使用。

核心設計思想

以 Range 爲核心，同時兼顧隨機寫和隨機讀的性能。

  1. 劃分多個 DB 分片減少鎖衝突，提高併發度。
  2. Key/Value 數據分離，可使用塊偏移地址表示數據位置。
  3. 充分利用 PageCache 避免進程退出不丟失數據，引入 Mmap 讀寫數據。
  4. 索引全量加載到內存，保證索引分區內和分區之間有序。
  5. Range 階段需要大塊緩存，保證順序讀。
  6. Open DB 並行加載 DB 分片，每個分片的加載過程是獨立的。

全局架構

隨機寫和隨機讀都會根據 key 定位到具體的數據分片，轉變爲具體某個 DB 分片的讀寫操作。Range 查詢需要定位到分片的上界和下界，然後依次順序將分片進行遍歷。

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

全局架構

DB 劃分爲多個分片的作用：

  1. 降低鎖衝突。
  2. 提高讀、寫、Open 併發度。
  3. 降低數據定位時間。
  4. 有利於 Range 大塊緩存數據。

DB分片需要支持範圍查詢：DB 分片內和分片之間數據有序。

存儲方案

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

存儲方案

  1. 根據 Key 的高 11 位定位 DB 分片以及分片所對應的文件。
  2. 單個 DB 分片視角：每個 DB 分片主要分爲索引文件、MergeFile、數據文件。其中索引文件存儲數據的 Key 以及 Offset，MergeFile 的作用用於聚合 IO，將 4k 聚合成 16K 後進行落盤。
  3. 數據文件視角：比賽初期數據文件與 DB 分片採用了 1 對 1 的架構設計，後期爲了降低隨機IO，提高寫入速度，數據文件與 DB 分片設計爲一對多的方式，每個文件管理多個分片。

關鍵參數

  1. 64 個數據文件，2048 個 DB 分片，數據文件與 DB 分片是一對多的關係。
  2. 4 個 Value 合併爲 16K 落盤，減少磁盤交互次數。
  3. 創建 8 個 DB 分片、1G 的緩存池。
  4. 2 個 Range 預讀線程，每個 DB 分片均分成 2 段併發預讀。

隨機寫設計思路

  1. 當需要寫入數據時，首先定位到數據分片以及數據文件，進行加鎖操作。
  2. 先將數據寫入 MergeBuffer，更新索引。
  3. 當下一個數據來時執行同樣的操作，當 MergeBuffer 填滿 16K，使用 DIO 將 16K 數據批量刷盤。
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

隨機寫過程

隨機寫關鍵點

  1. Key 轉化爲 uint64_t，根據 uint64_t 的高 11 位定位 DB 分片以及數據文件。
  2. 索引以及 Megre IO 無法避免 kill -9 檢測，採用 Mmap 映射文件讀寫。
  3. 對象複用：每個分片獨立一份 16k Buffer 複用，減少資源開銷。
  4. 先寫數據文件再更新索引，索引直接使用指針地址賦值，避免內存拷貝。
  5. Value 採用 DIO 16K 字節對齊寫入。
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

Open DB 階段

細節決定成敗，因爲三個階段都會重新打開 DB，所以 Open DB 階段也成爲優化的關鍵一環。

  1. posix_fallocate 預先分配文件空間。
  2. 64 個線程併發加載 2048 個 DB 分片，每個分片的加載都是獨立的。
  3. 順序、批量讀取索引文件將 KeyOffset 加載到內存 Vector。索引的結構非常簡單，只記錄key 和 邏輯偏移offset，offset * 4096 計算出數據的物理偏移地址。
  4. 採用快排對 Key 進行從小到大排序，相同 Key 的 Offset 也從小到大排列。方便實現點查詢和範圍查詢。考慮到性能評測階段基本沒有重複的key，所以 Open 階段去除了索引的去重工作，改爲上界查詢。

索引結構：

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

Drop Cache 優化

Drop Cache 一共包含清理 PageCache、dentries 和 inodes，可根據參數控制。

sysctl -w vm.drop_cache = 1 // 清理 pagecache 
sysctl -w vm.drop_cache = 2 // 清理 dentries（目錄緩存）和 inodes 
sysctl -w vm.drop_cache = 3 // 清理 pagecache、dentries 和 inodes

PageCache 是重災區，儘可能在使用 PageCache 的地方做一些細節優化。

  1. 將每個分片 16K 合併 I/O 的在 close 時強制寫入磁盤的數據文件。
  2. 索引加載完成後，調用 POSIX_FADV_DONTNEED 則將指定的磁盤文件中數據從 Page Cache 中換出，穩定提升 20 ~ 30ms。


隨機讀

隨機讀核心就是實現點查詢 O(logn)。

  1. 根據 Key 定位 DB 分片以及數據文件。
  2. 二分查找 DB 分片的索引數據，得到 Key 所對應 Value 數據的 offset 上界。
  3. 根據數據的分區號和偏移地址採用 DIO 讀取 Value數據。
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

Range

Range 核心設計思想

  • 預讀先行，保證預讀和 Range 線程可以齊頭並進。
  • 預讀將整個數據分片加載至緩存，保證 Range 線程完全讀取緩存。
  • 儘可能提高預讀線程的速度，打滿 IO。
  • 建立緩存池，循環複用多個緩存片。
  • 典型的生產者 / 消費者模型， 需要控制好緩存片的等待和通知。

Range 架構設計

Range 的架構採用 8 個 DB 分片作爲緩存池，從下圖可以看出緩存片分爲幾種狀態：

  • 正在被讀取
  • 可以被 Range 線程讀取
  • Range 線程讀完可以被重複利用的
  • 未被使用的
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

Range 順序讀架構

當緩存池 8 個分片全部被填滿，將重新從頭開始，重複利用已被釋放的緩存分片。針對 Range 範圍查詢採用 2 個預讀線程持續讀取數據分片到可用的緩存片中，Range 線程順序從緩存中獲取數據進行遍歷。整個過程保證預讀先行，通過等待/通知控制 Range 線程與預讀線程齊頭並進。

緩存片的使用注意點：

  1. 將每個 DB 分片分爲 2 段併發讀取，每段 64m，提高分片預讀的速度。
  2. Range 線程需要等待預讀線程完成分片的預讀之後纔可以進行讀取。
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

緩存片讀取方式

可以看出這是一個典型的生產者消費者模型，需要做好預讀線程和 Range 線程之間的協作：

  1. 每個緩存片持有一把鎖和一個條件變量，控制緩存片的等待和通知。
  2. 每個緩存片採用引用計數以及 DB 分片號判斷是否可用。
  3. 預讀線程將 DB 分片分成 2 個段進行併發讀取，每段讀完通知 Range 線程。Range 線程收到信號後判斷所有段是否都讀完，如果都讀完則根據索引有序遍歷整個緩存片。

緩存片數據結構

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

Range 制勝點

在 Range 階段如何保證預讀線程能夠充分利用 CPU 時間片以及打滿 IO？採取了以下優化方案：

Busy Waiting 架構

Range 線程和預讀線程的邏輯是非常相似的，Range 線程 Busy Waiting 地去獲取緩存片，然後等待所有段都預讀完成，遍歷緩存片，釋放緩存片。預讀線程也是 Busy Waiting 地去獲取緩存片，獲取預讀緩存片其中一段進行預讀，通知 Range 該線程，釋放緩存片。兩者在獲取緩存片唯一的區別就是 Range 線程每次獲取不成功會 usleep 讓出時間片，而預讀線程沒有這步操作，儘可能把 CPU 打滿。

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

因爲比賽環境的硬件配置很高，這裏使用忙等去壓榨 CPU 資源可以取得很好的效果，實測優於條件變量阻塞等待。然而在實際工程中這種做法是比較奢侈的，更好的做法應該使用無鎖的架構並且控制自旋等待的限度，如果自旋超過限定的閾值仍沒有成功獲得鎖，應當使用傳統的方式掛起線程。

預讀線程綁核

爲了讓預讀線程的性能達到極致，根據 CPU 親和性的特點將 2 個預讀線程進行綁核，減少線程切換開銷，保證預讀可以打滿 CPU 以及 IO。

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

以上兩個優化完成後，Range（順序讀）的成績相當穩定，不會出現較大幅度的波動。

整體工程優化

  1. Key 轉化爲 uint64_t 藉助 bswap 指令。
  2. 儘可能加上分支預測 unlikely。
  3. 對象複用，減少資源開銷。
  4. 位移、& 操作代替除法、取餘運算。
  5. 批量讀取索引數據，做好邊界處理。

memcpy 4k 加速

利用 SSE 指令集 對 memcpy 4k 進行加速：

  1. 直接操作彙編，使用 SSE 的 movdqu 指令。
  2. 數據結構需要 8 字節對齊。
  3. 針對 4k 的場景使用 16 個寄存器完成並行運算。
阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

String 黑科技

  1. 目標：隨機讀階段實現零拷貝。
  2. 原因：由於 String 分內的內存不是 4k 對齊，所以沒辦法直接用於 DIO 讀取，會額外造成一次內存拷貝。
  3. 實現：使用自定義的內存分配器，確保分配出的內存 $string[0] 位置是 4k 對齊的，然後強轉爲標準的 String 供後續使用。

自定義實現了 STL Allocator 步驟：

  • 申請內存空間
  • 構造函數
  • 析構函數
  • 釋放空間
  • 替換 basic_string allocator

爲了防止自定義 Allocator 分配的內存被外部接口回收，將分配的 string 保存在 threadlocal 裏，確保引用計數不會變0。

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

失敗的嘗試

  1. 隨機讀建立 4k 緩存池，一次緩存 16k 數據，限制緩存數量。但是實測命中率很低，性能下降。
  2. PageCache 大塊預讀，通過 posix_fadvise 預讀、釋放緩存片來提高預讀速度。最終結果優於直接使用 PageCache，仍無法超過 DIO。


最佳成績

整個比賽取得的最佳成績是 414.27s，每個階段不可能都達到極限成績，這裏我列出了每個階段的最佳性能。

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

歷史成績記錄

思考與展望

阿里第一屆天池 PolarDB 數據庫性能大賽小結（深度多圖）

第一版設計架構

這是比賽初期設計的架構，個人認爲還是最初實現的一個分片對應單獨一組數據文件的架構更好一些，每個分片還是分爲索引文件、MergeFile 以及一組數據文件，數據文件採用定長分配，採用鏈表連接。這樣方便擴容、多副本、遷移以及增量備份等等。當數據量太大沒辦法全量索引時，可以採用稀疏索引、多級索引等等。這個版本的性能評測穩定在 415~416s，也是非常優秀的。

相關文章