NvmStore：第二屆資料庫大賽比賽記錄

前段時間因興趣使然，參加了第二屆阿裡資料庫大賽，并成功沖入決賽。

本屆資料庫大賽的題目是在Intel提供的持久化記憶體（Persistent Memory）上實作一套KV Store。

持久化記憶體一直是資料庫研究的一個新興研究方向，十分高興這次有機會在真正的持久化記憶體上實作系統并測試。

這裡是我們參賽作品的一個介紹。

題目簡介

本次資料庫大賽的題目是在Intel Optane Persistent Memory上實作一套高性能的KV Store，

通路模式主要是随機通路。由于使用的是持久化記憶體，要求實作的系統能夠持久化資料，

在系統Crash等場景下可以正确恢複。Key的寫入要求是原子的，寫入失敗不能影響舊值。

測試使用16個線程寫入随機鍵值對，每個線程寫入大約20M條記錄，随後會進行十次混合讀寫。

混合讀寫階段的讀寫具有熱點，以寫入過程的時間和混合讀寫過程中最慢一次的時間作為成績。

總共提供的PMEM大小是64G，但寫入資料量會大于64G（因為有重複Key的寫入）。

複賽階段提供了8G DRAM以供使用。具體的題目描述請參見比賽

官方網站的介紹

。

我所在的隊伍在最後的決賽獲得了季軍（第四名）。

首先需要介紹一下Persistent Memory，這是一種插在記憶體插槽上的新興儲存設備，

在資料庫領域是一個前沿研究熱點。它具有類似DRAM的随機讀取能力，但是能在掉電之後保持資料不丢失。

與插在PCI-E/M.2插槽的所謂NVMe SSD不同，PMEM具有更細的通路粒度（8byte字長），

更強的随機通路能力。但我們在測試中發現，它的性能相比DRAM還有一定的差距。

PMEM目前的一種常用配置是将DRAM運作為CPU的L4 Cache，使用機關容量價格較低的PMEM作為主存，

這種方式可以使現有應用程式無痛遷移到PMEM上，且不會相比DRAM有太大的性能差異。

但是想要充分利用PMEM的性能，最佳方案仍然是設計專業的應用程式。

為此，需要使用

PMDK

等工具直接通路PMEM。

Linux等作業系統也已經位PMEM提供的DAX功能，可以繞過作業系統的頁面管理，直接寫入PMEM。

本賽題的背景即是如此。對題目的資訊進行分析，可以知道：

1. 寫入資料量大于PMEM空間，說明存在大量的覆寫寫，對Allocator的設計要求比較高
2. 記憶體相對來說比較充裕，且PMEM相比DRAM的總體性能還是有一定差距，是以應該盡量将不需要持久化的資料維護在DRAM

3. 并發寫入的線程數較多，應該盡量使用Thread Local的資料結構，避免線程間同步。

   必須要同步的地方使用細粒度鎖

此外，在測試的時候發現，本地使用DRAM虛拟的PMEM和硬體PMEM的特性差異較大，

是以需要盡量在實際硬體環境下測試才能得到有意義的結果，不能依賴本地試驗結果。

在以上分析的基礎上，我們的系統采用了如下設計。

概覽

我們設計的系統架構圖如下：

總體來說，系統分為以下三個部分：

1. Hash Index：記錄Key到Value映射的記憶體索引，實作查詢和更新操作
2. Allocator：用來管理Heap上的存儲空間，實作空間的配置設定和回收
3. Heap：用于寫入資料記錄的PMEM空間

KV Store的讀寫操作都很簡單，其中，寫入操作使用類似影子分頁

（

Shadow Paging

）

的方法：

1. 先使用Allocator配置設定一塊新的Heap空間
2. 直接将Record寫入新配置設定的空間
3. 更新Hash Index，指向新寫入的位址

讀取也很簡單：通過Hash Index找到Heap上的位址并讀取即可。

Heap

堆是存儲實際資料的地方，它的設計關系到如何實作寫入的持久化、原子性和可恢複性。

同時，寫入堆的方式和堆上記錄（Record）的寫入方法也極大地關系到寫入的性能。

下圖展示了Heap的大緻結構。

在我們的系統中，Heap被劃分為等長的Block，是以Heap記憶體的配置設定都是以Block為機關的。

Heap的第一個塊用于寫入Magic Number。Hash Index當中的Entry指向Record的位址，

而Allocator中會維護Heap中所有的空閑空間的位置。

Record是寫入在Heap上的表示，它要記錄所寫入的Key和Value，并保證可以原子地寫入資料并可以恢複。

下圖是Record的結構的展示：

Record由整數個Block構成，在Record的頭部是存儲元資訊的Header，之後是Key和Value組成的Payload，

由于Record總是由整數個Block構成，是以在Record的結尾可能會有一部分備援空間沒有被利用。

Record中最重要的是Header，它的結構包括：

• BlockSize：Record包含的Block的總數量，由于Value的長度小于1024，是以一條記錄的總長度

  總小于1048（Header+Key+Value），則BlockSize不大于17，可以用5個二進制位表示

• PayloadSize：存儲Payload的實際長度，Payload最長不超過1040位元組，是以可以用11個二進制位表示
• CRC16：由Payload的CRC校驗折疊而成。用于保證Record寫入的原子性
• Serial Number：Record的序列号，用于判斷Record的先後順序

在Heap上寫入Record的方法是先在記憶體中組裝好一個Record，并寫入Header中的字段，

然後使用

pmem_memcpy

指令的

NON_TEMPORAL

模式寫入。在記憶體中組裝Record的原因，

一方面是記憶體的通路性能仍然快于PMEM，另一方面是因為可以利用

NON_TEMPORAL

模式，

使用一次刷寫持久化一整個Record。

所謂的

NON_TEMPORAL

寫入，在一些文獻中稱為Stream寫入。簡單來說，一般CPU寫入一段記憶體空間時，

會先将對應記憶體中的一個CacheLine加載到CPU的緩存中，進行修改之後再寫回。也就是說，

正常情況下，即使你隻在某個位置寫入了幾個Byte的資料，CPU仍然會把所在的CacheLine讀入。

這在很多情況下顯然是低效的，是以現代CPU提供了對應的指令，可以實作對CacheLine的直接刷寫，

避免讀入。PMEM作為一種特殊的記憶體，也适用于這些概念。

我們發現，使用CacheLine對齊的Buffer組裝Record，并利用

NON_TEMPORAL

寫入方式寫入PMEM所得性能最高。

這也意味着我們必須将Heap上的Block設定為64Byte大小，并對齊到CacheLine。

雖然有了

NON_TEMPORAL

寫入，仍不能保證寫入Record的原子性。在這裡

我們要保證寫入的一個Record要麼完整地寫入成功，要麼寫入失敗（不影響舊值）。

這是因為PMEM隻能保證對一個字長（8Byte）寫入的原子性，即使是一個CacheLine，

它也不能保證一定是整體寫入成功或失敗的。

是以，我們在Header中內建了CRC：由于Header被壓縮在8個Byte，PMEM可以保證它的原子寫入，

是以可以通過校驗CRC判斷整個Record是否合法。

Serial Number的作用則是用來判斷Record的寫入順序，比如說有同一個Key，先後寫入了兩條資料，

第二條資料的值應該覆寫掉第一條。但是因為有記憶體回收的原因，第二條資料在檔案中的位置可能更早，

是以需要它來判斷哪一條更新，以避免恢複出舊值。我們在比賽時使用的是簡單的線程本地計數器，

為了實作線程間的有序，可以考慮使用時間戳或全局遞增計數器來實作，Serial Number也不必要放在Header裡。

在本系統中，将BlockSize和PayloadSize分開存儲，這是希望一旦一個Record的空間被配置設定出去之後，

就不再改變這一塊空間的大小。也就是說，未來如果有其他不同長度的資料寫到這裡，BlockSize仍然不變。

這是因為BlockSize改變可能會導緻恢複的問題，比如在一個原來長度10的Record所占位置寫入長度5的資料，

如果更改了BlockSize并在此時Crash，則恢複程序可能找不到下一條記錄的正确位置。

原因是可能出現Header寫入成功但内容寫入失敗的現象。如果此時恢複程序按照Header中訓示的BlockSize（5）

來跳轉，會跳轉到随機資料所在的位置。

以上設計保證了Record的寫入原子性和持久性。恢複記錄的算法就非常簡單：

1. 檢查PMEM檔案的第一個塊是否有Magic Number，如果有就開始恢複程序
2. 依次讀入記錄，進行CRC校驗，跳過校驗失敗的Record。将合法的Record登記到Hash Index上（Serial Number較大的勝出）
3. 重複以上過程直到處理完所有能讀出的Record

Hash Index

Hash Index也是系統設計中很重要的一部分，他的查詢性能是KV Store性能的基礎，

此外也需要在這上面實作合理的并發控制，保證多線程寫入的一緻性。我們設計的Hash Index

有如下特點：

1. 開放尋址（ Open Addressing
2. 線性探查（ Linear Probing
3. Record位址使用

   uint32

   表示
4. Hash函數使用 CityHash
5. 細粒度鎖

首先，受Google的

Flat Hash Map

啟發，我們對計算出的Key的Hash值做了如下圖所示處理：

Hash值總共64bit，其中後15個bit被用作H2，剩下的bit被用于H1。H1用來尋址Key應在的Bucket，

H2則存放在HashMap的Bucket裡。HashMap的Bucket具有如下圖所示的構造：

HashMap的一個Bucket是對齊到CacheLine邊界的連續三個CacheLine。

每個Bucket可以存放8條記錄，從左到右，依次是lock段、ctrl段、value段、block size段和key段。

其中lock段通過原子操作實作細粒度的SpinLock；ctrl段存放8個H2值，用于進行快速比對；

value段存放Key對應的記錄位址。block size段和key段通過将key和block size緩存在記憶體中，

避免寫入階段對PMEM的讀取。

為什麼要設計ctrl段呢？當我們使用H1找到一個Key應該在的Bucket之後，與其逐個比較每個Slot，

不如先使用H2探針來快速判斷是否有比對的Entry。具體來說，可以使用如下流程的SIMD指令，

在少數幾個Instruction的操作下，快速以很高的機率查找到比對的點。

在上述案例中，我們要查找的Key的H2值是

0x0F23

，在對應的Bucket的ctrl段在slot 2有比對的值。

通過

_mm_cmpeq_epi16

和

_mm_movemask_epi8

指令操作之後，可以快速從16byte的ctrl段找到這個位置。

這裡還利用了

__builtin_ffs

快速求解一個整型數值的第一個

1

的位置。

利用ctrl段可以減少Hash碰撞的機率和線性探查的長度：

傳統HashMap在利用Hash值定位到某個位置後，需要向後逐個對比Key值來找到比對的Entry，

通常不會存儲之後的Key的Hash以供快速檢查。使用我們（

flat_hash_map

）的解決方案，

實際相當于先用Hash的一部分尋找Bucket，再用另一部分進行快速比對，可以更充分地利用Hash值中的每一位。

在使用ctrl段找到一個比對後，還需要再檢查Key以避免碰撞的發生。在一開始的時候，我們的系統會去PMEM上讀取Key的值，

後來發現這種混合讀寫對PMEM性能傷害很大。後來我們采取了将Key緩存在Bucket中的方案，這就是Bucket中的key段的來源。

後來，Block Size也被整合進來，使得無論是寫入還是記憶體回收的時候都不需要通路PMEM，極大地提高了系統的性能。

在本系統的Hash Index的設計中，插入和更新操作會鎖定對應的Bucket，由于每個Bucket隻有8個slot，是以鎖的粒度很細。

在查找操作的探查階段，我們也不加鎖，

這是參考了

CLHT

的設計，

x86系統采用的

MESIF protocol

具有較強的Memory Order保證，

以及對短于一個字的記憶體讀寫的原子性。在查詢階段不加鎖，不但可以避免鎖等待，

還可以避免查詢Miss的情況下對記憶體的任何寫入。實際上，在多核強競争場景下寫入多核共享的CacheLine，

會導緻CacheLine同步和核間通訊，是以可能大大降低性能。

但是值得注意的是，在命中記錄開始讀取值之前，要鎖定Bucket以防止髒讀。這是因為在并發線程同時讀取一個Key時，

可能出現第1個線程先讀到了Key對應記錄的位址，第二個線程寫入同一個Key，回收了此前的記錄，

然後又在第2個寫入中利用了這個位址的情況。此時就會出現兩個線程對同一段記憶體的并發讀寫，觸發髒讀。

下圖展示了這種情況：

Allocator

Allocator是整個系統當中最核心的部分，他的性能和政策設計，直接決定了系統的性能。

在我們的系統中，每個線程都有自己本地的Allocator。Heap空間被預先配置設定給16個線程。

每個線程的配置設定政策是先從頭開始進行連續寫（類似Log-Structured），

随後開始從Allocator記錄的空閑空間開始利用，最後使用保留段。基本政策如下圖所示：

Allocator主要由塊狀連結清單組成，不同長度的空閑空間根據它們的Block長度不同，被放置在不同的塊狀連結清單中。

每個塊狀連結清單的節點存儲着一系列空閑空間的位址，并使用一個

top

指針指向下一個位址存放的位置。

塊狀連結清單的塊使用

next

指針相連。為了避免頻繁的記憶體配置設定，我們對塊狀連結清單的塊使用了Memory Pool。

使用塊狀連結清單的原因是為了在保證Alloc和Free取出和存放位址都是

O(1)

同時，避免随機記憶體通路和提高記憶體使用率。

塊狀連結清單比靜态配置設定Stack更靈活。

給定一條記錄，我們可以先計算出他所需要的Block數，然後在Allocator中從下到上尋找可以放入這條記錄的最小空閑空間。

預設不改變對應空間原來的BlockSize，有可能出現把短記錄放在很長的空閑段裡，導緻空間浪費和OOM，

為此必須要考慮修改長段的長度。在比賽中，我們采用的是在Alloc切分一段空間前，先在後面寫入塊來維護中繼資料，

保證恢複程序可以跳轉。後來跟其他參賽選手交流後發現，逐塊掃描校驗CRC也許是一種更好的實作。

下圖展示了切分段的解決方法，在将長10的空閑段切開時，先在後面寫入一塊幫助恢複程序找到跳轉位置，

再傳回前面的空間。

除此之外，我們在Allocator中加入了一個

short_alloc

字段，

用來在上述情況中，将長段的第二部分放在Allocator的頭，在alloc的時候優先檢查它。

由于大部分寫入的值長度都比較短，是以大機率

short_alloc

當中的空間會被立即使用，

之後如果有剩餘的空間仍然放在

short_alloc

裡，是以可以獲得局部的連續寫入。

上面提到，配置設定給每個Allocator管理的段在末尾還有一段保留段。

這是因為有切分塊的存在，上述政策對短塊友好，是以Heap會越切越細。

如果有長記錄的寫入到來，可能會出現找不到連續長空間的問題。

為此增加一段保留段，在Allocator配置設定不出長空間時啟用保留段，

避免OOM。

總結

我們首先實作了PMEM上高性能KV Store的基礎架構，它具有以下特性：

1. 保證了寫入的原子性和持久性
2. 實作了基于SIMD指令快速查找和細粒度鎖的Hash Index
3. 實作了簡單高效且适應性強的Allocator

在第一階段我們實作了大約54秒的測試成績。之後我們将Block Size和Key資訊緩存在Hash Index

中，使得寫入和Free空間時無需讀取PMEM，立即使得成績提升了8秒到達46秒左右。

最後我們嘗試了在記憶體中組裝Record，使用64byte的Block，

并對齊到CacheLine。再配合

NON_TEMPORAL

寫入模式，達到了我們的最佳成績36秒。

這一成績距離第2名和第3名的成績差距不到1秒，應該說是一個級别的實作方案了。

綜合來看我們的方案在實作并發控制、持久化和原子性方面的細節方面是比較周到的：

1. 使用了CRC校驗保證記錄寫入的完整性
2. 使用細粒度的Hash Index鎖保證并發性能
3. 使用Serial Number保證記錄的恢複順序
4. 對切分塊場景下的恢複提出了合理的方案

個人認為我們的方案沒有特别地利用測試程式的通路模式，通用性非常好。

雖然沒有能夠拿到更好的名次，總體來說還是非常令人滿意的。

在本方案的基礎上，參考其他隊伍的解決方案，我覺得還有以下一些可以提高的地方：

1. 使用HugePage或使用預熱TLB的方法來減少Page Fault。有其他參賽選手通過預熱TLB獲得了可觀的性能提升，

   但是我覺得在實際生産環境中配置HugePage來減少頁表大小是更好的手段。在比賽時有考慮過相關實作，

遺憾的是發現HugePage在測試環境中無法激活後我就放棄了這個方向

1. 實作記憶體碎片整理。目前的解決方案會出現不斷碎片化的問題，被切碎的空間即使相連也不會互相合并，

   這主要是考慮到實作的複雜性和性能問題。在實際生産環境中，有必要添加記憶體碎片整理機制，定期合并碎片以獲得連續段

2. 增加寫入的連續性。事實表明，順序寫入PMEM相比于随機寫仍然有相當可觀的性能提升。

   冠軍隊伍通過利用這一特性獲得了超過我們數秒的提升。

參賽感想

這是我第一次參加類似的程式設計競賽，很高興最後能拿獎。特别是在比賽的過程中還學到了很多東西：

在比賽前，我對C++程式設計語言、記憶體模型、Memory Order、并發控制等的了解都比較膚淺，在這個比賽中，

我了解到很多記憶體管理和編寫高性能應用的知識。比如：在此之前，

我從來都沒有想過記憶體對象在記憶體中的位址會對軟體的性能産生巨大影響，對齊到CacheLine之後竟然能獲得數十秒的性能提升。

也沒想過存在于同一CacheLine的兩個鎖竟然會有False Sharing，兩個線程分别對這樣的兩個鎖加鎖，

竟然會互相幹擾并導緻性能退化！可以說涉及到系統調用、TLB、指令集和CPU Cache級别的性能優化技巧讓我大開眼界。

編寫如此接近硬體的程式讓我對C++（以及其他系統程式設計語言）和高性能程式設計産生了濃厚的興趣。

希望未來還可以在這個方向上繼續學習。

最後，我們實作的KV Store

在Github上開源

，以供參考。