點選上方“芋道原始碼”，選擇“設為星標”

做積極的人，而不是積極廢人！

原始碼精品專欄

 

• 中文詳細註釋的開源專案
• 訊息中介軟體 RocketMQ 原始碼解析
• 資料庫中介軟體 Sharding-JDBC 和 MyCAT 原始碼解析
• 作業排程中介軟體 Elastic-Job 原始碼解析
• 分散式事務中介軟體 TCC-Transaction 原始碼解析
• Eureka 和 Hystrix 原始碼解析
• Java 併發原始碼

來源：http://t.cn/EfuZTfi

• 比賽背景
• 賽題剖析
• 核心設計思想
• 全域性架構
• 儲存方案
• 關鍵引數
• 隨機寫設計思路
• 隨機寫關鍵點
• Open DB 階段
• Drop Cache 最佳化
• 隨機讀
• Range
• 整體工程最佳化
• memcpy 4k 加速
• 失敗的嘗試
• 最佳成績
• 思考與展望

---

這次天池 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 查詢需要定位到分片的上界和下界，然後依次順序將分片進行遍歷。

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

1. 降低鎖衝突。
2. 提高讀、寫、Open 併發度。
3. 降低資料定位時間。
4. 有利於 Range 大塊快取資料。

DB分片需要支援範圍查詢：DB 分片內和分片之間資料有序。

儲存方案

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 資料批次刷盤。

隨機寫關鍵點

1. Key 轉化為 uint64_t，根據 uint64_t 的高 11 位定位 DB 分片以及資料檔案。
2. 索引以及 Megre IO 無法避免 kill -9 檢測，採用 Mmap 對映檔案讀寫。
3. 物件復用：每個分片獨立一份 16k Buffer 復用，減少資源開銷。
4. 先寫資料檔案再更新索引，索引直接使用指標地址賦值，避免記憶體複製。
5. Value 採用 DIO 16K 位元組對齊寫入。

KeyOnly keyOnly;
keyOnly.key = keyLong;
KeyOnly *ptr = reinterpret_cast(mIndexPtr);
pthread_mutex_lock(&mMutex;);
memcpy(static_cast<char *>(mSegmentBuffer) + mSegmentBufferIndex * 4096, value.data(), mSegmentBufferIndex++;

if (mSegmentBufferIndex == MergeLimit) {
    pwrite64(mDataDirectFd, mSegmentBuffer, MergeBufferSize, mWritePosition);
    mWritePosition += MergeBufferSize;
    mSegmentBufferIndex = 0;
}

ptr[mTotalKey] = keyOnly;
mTotalKey++;
pthread_mutex_unlock(&mMutex;);

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 階段去除了索引的去重工作，改為上界查詢。

索引結構：

struct KeyOffset {
    uint64_t key;
    uint32_t offset;

    KeyOffset()
            : key(0),
              offset(0) {
    }

    KeyOffset(uint64_t key, uint32_t offset)
            : key(key),
              offset(offset) {
    }
} __attribute__((packed));

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資料。

uint32_t offset = binarySearch(keyLong);

if (unlikely(offset == UINT32_MAX)) {
    return kNotFound;
}
static __thread void *readBuffer = NULL;
if (unlikely(readBuffer == NULL)) {
    posix_memalign(&readBuffer;, getpagesize(), 4096);
}
if (unlikely(value->size() != 4096)) {
    value->resize(4096);
}
RetCode ret = readValue(offset - 1, readBuffer);
memcpy(&((*value)[0]), readBuffer, 4096);
return ret;

Range

Range 核心設計思想

• 預讀先行，保證預讀和 Range 執行緒可以齊頭併進。
• 預讀將整個資料分片載入至快取，保證 Range 執行緒完全讀取快取。
• 盡可能提高預讀執行緒的速度，打滿 IO。
• 建立快取池，迴圈復用多個快取片。
• 典型的生產者 / 消費者模型， 需要控制好快取片的等待和通知。

Range 架構設計

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

• 正在被讀取
• 可以被 Range 執行緒讀取
• Range 執行緒讀完可以被重覆利用的
• 未被使用的

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

快取片的使用註意點：

1. 將每個 DB 分片分為 2 段併發讀取，每段 64m，提高分片預讀的速度。
2. Range 執行緒需要等待預讀執行緒完成分片的預讀之後才可以進行讀取。

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

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

快取片資料結構

class CacheItem {
public:
    CacheItem();

    ~CacheItem();

    void WaitAllDataSegmentReady(); // Range 執行緒等待當前快取片所有段被讀完 
    uint32_t GetUnReadDataSegment(); // 預讀執行緒獲取還未讀完的資料段 
    bool CheckAllSegmentReady(); // 檢測所有段是否都讀完 
    void SetDataSegmentReady(); // 設定當前資料段預讀完成，並向 Range 執行緒傳送通知 
    void ReleaseUsedRef(); // 釋放快取片取用計數     
    uint32_t mDBShardingIndex; // 資料庫分片下標     
    void *mCacheDataPtr; // 資料快取     
    uint32_t mUsedRef; // 快取片取用計數     
    uint32_t mDataSegmentCount; // 快取片劃分為若干段     
    uint32_t mFilledSegment; // 正在填充的資料段計數，用於預讀執行緒獲取分片時候的條件判斷     
    uint32_t mCompletedSegment; // 已經完成的資料段計數 
    pthread_mutex_t mMutex;
    pthread_cond_t mCondition;
};

Range 制勝點

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

Busy Waiting 架構

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

// 預讀執行緒 CacheItem *item = NULL;
while (true) {
    item = mCacheManager->GetCacheItem(mShardingItemIndex);
    if (item != NULL) {
        break;
    }
}

while (true) {
    uint32_t segmentNo = item->GetUnReadDataSegment();
    if (segmentNo == UINT32_MAX) {
        break;
    }
    uint64_t cacheOffset = segmentNo * EachSegmentSize;
    uint64_t dataOffset = cacheOffset + mStartPosition;
    pread64(mDataDirectFd, static_cast<char *>(item->mCacheDataPtr) + cacheOffset, EachSegmentSize, dataOffset);
    item->SetDataSegmentReady();
}
item->ReleaseUsedRef();

// Range 執行緒 CacheItem *item = NULL;
while (true) {
    item = mCacheManager->GetCacheItem(mShardingItemIndex);
    if (item != NULL) {
        break;
    }
    usleep(1);
}
item->WaitAllDataSegmentReady();

char key[8];
for (auto mKeyOffset = mKeyOffsets.begin(); mKeyOffset != mKeyOffsets.end(); mKeyOffset++) {
    if (unlikely(mKeyOffset->key == (mKeyOffset + 1)->key)) {
        continue;
    }
    uint32_t offset = mKeyOffset->offset - 1;
    char *ptr = static_cast<char *>(item->mCacheDataPtr) + offset * 4096;
    uint64ToString(mKeyOffset->key, key);
    PolarString str(key, 8);
    PolarString value(ptr, 4096);
    visitor.Visit(str, value);
}
item->ReleaseUsedRef();

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

預讀執行緒綁核

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

static bool BindCpuCore(uint32_t id) {
    cpu_set_t mask;
    CPU_ZERO(&mask;);
    CPU_SET(id, &mask;);
    int ret = pthread_setaffinity_np(pthread_self(), sizeof(mask), &mask;);
    return ret == 0;
}

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

整體工程最佳化

1. Key 轉化為 uint64_t 藉助 bswap 指令。
2. 盡可能加上分支預測 unlikely。
3. 物件復用，減少資源開銷。
4. 位移、& 操作代替除法、取餘運算。
5. 批次讀取索引資料，做好邊界處理。

memcpy 4k 加速

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

1. 直接操作彙編，使用 SSE 的 movdqu 指令。
2. 資料結構需要 8 位元組對齊。
3. 針對 4k 的場景使用 16 個暫存器完成並行運算。

inline void
mov256(uint8_t *dst, const uint8_t *src) {
    asm volatile ("movdqu (%[src]), %%xmm0\n\t"
                  "movdqu 16(%[src]), %%xmm1\n\t"
                  "movdqu 32(%[src]), %%xmm2\n\t"
                  "movdqu 48(%[src]), %%xmm3\n\t"
                  "movdqu 64(%[src]), %%xmm4\n\t"
                  "movdqu 80(%[src]), %%xmm5\n\t"
                  "movdqu 96(%[src]), %%xmm6\n\t"
                  "movdqu 112(%[src]), %%xmm7\n\t"
                  "movdqu 128(%[src]), %%xmm8\n\t"
                  "movdqu 144(%[src]), %%xmm9\n\t"
                  "movdqu 160(%[src]), %%xmm10\n\t"
                  "movdqu 176(%[src]), %%xmm11\n\t"
                  "movdqu 192(%[src]), %%xmm12\n\t"
                  "movdqu 208(%[src]), %%xmm13\n\t"
                  "movdqu 224(%[src]), %%xmm14\n\t"
                  "movdqu 240(%[src]), %%xmm15\n\t"
                  "movdqu %%xmm0, (%[dst])\n\t"
                  "movdqu %%xmm1, 16(%[dst])\n\t"
                  "movdqu %%xmm2, 32(%[dst])\n\t"
                  "movdqu %%xmm3, 48(%[dst])\n\t"
                  "movdqu %%xmm4, 64(%[dst])\n\t"
                  "movdqu %%xmm5, 80(%[dst])\n\t"
                  "movdqu %%xmm6, 96(%[dst])\n\t"
                  "movdqu %%xmm7, 112(%[dst])\n\t"
                  "movdqu %%xmm8, 128(%[dst])\n\t"
                  "movdqu %%xmm9, 144(%[dst])\n\t"
                  "movdqu %%xmm10, 160(%[dst])\n\t"
                  "movdqu %%xmm11, 176(%[dst])\n\t"
                  "movdqu %%xmm12, 192(%[dst])\n\t"
                  "movdqu %%xmm13, 208(%[dst])\n\t"
                  "movdqu %%xmm14, 224(%[dst])\n\t"
                  "movdqu %%xmm15, 240(%[dst])"
    :
    :[src] "r"(src),
    [dst] "r"(dst)
    : "xmm0", "xmm1", "xmm2", "xmm3",
            "xmm4", "xmm5", "xmm6", "xmm7",
            "xmm8", "xmm9", "xmm10", "xmm11",
            "xmm12", "xmm13", "xmm14", "xmm15", "memory");
}

#define mov512(dst, src) mov256(dst, src); \ mov256(dst + 256, src + 256); 
#define mov1024(dst, src) mov512(dst, src); \ mov512(dst + 512, src + 512); 
#define mov2048(dst, src) mov1024(dst, src); \ mov1024(dst + 1024, src + 1024); 
inline void memcpy_4k(void *dst, const void *src) {
    for (int i = 0; i 16; ++i) {
        mov256((uint8_t *) dst + (i <8), (uint8_t *) src + (i <8));
    }
}

String 黑科技

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

自定義實現了 STL Allocator 步驟：

• 申請記憶體空間
• 建構式
• 解構式
• 釋放空間
• 替換 basic_string allocator

為了防止自定義 Allocator 分配的記憶體被外部介面回收，將分配的 string 儲存在 threadlocal 裡，確保取用計數不會變0。

template<typename T>
class stl_allocator {
public:
    typedef size_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef T *pointer;
    typedef const T *const_pointer;
    typedef T &reference;
    typedef const T &const;_reference;
    typedef T value_type;

    stl_allocator() {}
    ~stl_allocator() {}

    template<class U>
    struct rebind {
        typedef stl_allocator other;
    };

    template<class U>
    stl_allocator(const stl_allocator &) {}

    pointer address(reference x) const { return &x; }

    const_pointer address(const_reference x) const { return &x; }

    size_type max_size() const throw() { return size_t(-1) / sizeof(value_type); }

    pointer allocate(size_type n, typename std::allocator<void>::const_pointer = 0) {
        void *buffer = NULL;
        size_t mallocSize = 4096 + 4096 + (n * sizeof(T) / 4096 * 4096);
        posix_memalign(&buffer;, 4096, mallocSize);
        return reinterpret_cast(static_cast<int8_t *>(buffer) + (4096 - 24));
    }

    void deallocate(pointer p, size_type n) {
        free(reinterpret_cast<int8_t *>(p) - (4096 - 24));
    }

    void construct(pointer p, const T &val;) {
        new(static_cast<void *>(p)) T(val);
    }

    void construct(pointer p) {
        new(static_cast<void *>(p)) T();
    }

    void destroy(pointer p) {
        p->~T();
    }

    inline bool operator==(stl_allocator const &a;) const { return this == &a; }

    inline bool operator!=(stl_allocator const &a;) const { return !operator==(a); }
};
typedef std::basic_string<char, std::char_traits<char>, stl_allocator<char>> String4K;}

失敗的嘗試

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

最佳成績

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

思考與展望

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