KVell: the Design and Implementation of a Fast Persistent Key-Va
1.Background
傳統(tǒng)的存儲設(shè)備和CPU之間存在巨大的速度差異，隨機訪問和順序訪問之間也存在巨大的速度差異。
訪存速度是KVs的瓶頸。為此通過投入一些CPU時鐘周期去優(yōu)化訪存的速度是一種良好的策略。為了提高訪存速度，傳統(tǒng)的KVs通過投入一些消耗CPU的操作，避免隨機訪問實現(xiàn)順序訪問，如數(shù)據(jù)在磁盤上的有序性和同步等操作。
現(xiàn)代的塊尋址的SSD設(shè)備提供了非常高的帶寬，相似的隨機和順序讀寫性能。
2.Problem
1.傳統(tǒng)的KVs沒有考慮新型SSD的新特性，原有的一些優(yōu)化反而加重了CPU的負擔(dān)，得CPU成為了KVs的瓶頸。
RocksDB：CPU的60%的時間都需要花費在Compaction上(合并：28%；構(gòu)建索引：15%；剩下的時間用于：讀寫磁盤數(shù)據(jù) )
B-tree：CPU的主要開銷在同步操作上，47%的時間用于等待日志的插槽（全局的序列號更新的不夠快）；12%的時間用于從page cache中evication dirty data；5%的時間用于管理commit log；25%的時間用于內(nèi)核讀寫調(diào)用；18%的時間用于執(zhí)行客戶端請求；
B∈ tree：CPU的主要開銷在同步操作上，30%的時間用于鎖或者原子操作用于保護共享頁；多于20%的時間用于將數(shù)據(jù)從buffer移動到在磁盤上所在的位置。
2.LSM 和 B tree KVs會有顯著的性能波動(延遲也會波動，可能導(dǎo)致尾延遲大)，也會導(dǎo)致性能和尾延遲不好預(yù)測。
LSM tree：updates 需要等待compactions完成（第一層滿，原因還是在于compaction消耗大量cpu，cpu是瓶頸）
B tree：evictions 操作不夠快。
LSM 和 B tree其根本原因都在于其維護操作不夠快從而導(dǎo)致客戶端請求阻塞。
3.Motivation
1.針對新設(shè)備的特性設(shè)計出一種能夠充分利用磁盤帶寬的KVs設(shè)計準(zhǔn)則。
2.新的KVs應(yīng)該更加關(guān)注如何充分利用CPU
4.KVell design principles
強調(diào)CPU的低開銷
4.1Share nothing
目的：不共享有助于并行和最小化各個線程之間通信的CPU開銷；
實現(xiàn)機制：每個線程獨立的處理讀寫請求，每個線程只負責(zé)處理給定keys集合的一個子集，每個線程維護了一個私有的數(shù)據(jù)結(jié)構(gòu)去管理這個key的子集。
數(shù)據(jù)結(jié)構(gòu)包括：
在內(nèi)存中的輕量級索引：B-Tree索引用于追蹤key在持久化存儲上的位置
I/O隊列：有效地存儲和從持久存儲器中檢索信息。
Free list：在內(nèi)存中的磁盤塊列表，其中記錄了適合存儲項的空閑位置。
page cache：使用自己的頁面緩存，不使用OS的。
掃描操作是唯一需要線程同步的操作
Share nothing 通過分區(qū)來實現(xiàn)，但分區(qū)的請求可能導(dǎo)致負載不均衡。
4.2Do not sort on disk，but keep indexes in memory
目的：減少key插入(不需要先找到合適的位置)的開銷，消除維護磁盤上的數(shù)據(jù)結(jié)構(gòu)的CPU開銷。
每個工作線程不需要對它工作集中的key進行排序，直接將它存儲到磁盤上的最終位置，可以有效降低寫操作的延遲。
4.3Aim for fewer syscalls，not for sequential I/O
目的：使用批處理隨機I/O，隨機I/O是為了消除原有為了實現(xiàn)順序I/O而浪費的CPU時鐘周期，批處理是為了減少系統(tǒng)調(diào)用次數(shù)從而減少CPU開銷。
批處理隨機I/O：在新型SSD上順序I/O≈隨機I/O，所以采用隨機I/O。批處理需要在peak IOPS和latency之間進行權(quán)衡。
每個工作線程只能將文件存儲在一個磁盤上。這樣做的考慮是限制每個磁盤上的請求數(shù)量。
因為share nothing的設(shè)計，所以各個工作線程之間不會通信，他們不能知道其它工作線程給某個磁盤發(fā)送了多少請求。
如果每個工作線程只能將數(shù)據(jù)存儲到一個磁盤上，那這個磁盤上的最多請求數(shù)為batch size * 該磁盤上的工作線程數(shù)。
如果每個工作線程能將數(shù)據(jù)存儲到所有的磁盤上，那一個磁盤上的最多請求數(shù)為batch size * 所有的工作線程數(shù)。
請求分發(fā)給工作線程是根據(jù)他們的key值，此外工作線程只訪問一個磁盤，可能存在一個傾斜的工作負載（大部分data都訪問同一個磁盤，從而讓其它磁盤空閑）
4.4No commit log
KVell:只有當(dāng)數(shù)據(jù)持久化到磁盤上以后才會承認(rèn)更新，所以不需要提交日志。
不采用提交日志可以充分利用磁盤帶寬去處理客戶端處理請求。
5.KVell implementation
https://github.com/BLepers/KVell
5.1Client operations interface
writes: Update(k,v); reads: Get(k);Scan(k1,k2);
5.2On-disk data structures
目的：為了避免磁盤碎片化，將item放入與item大小想匹配的file/slab中。
KVell以塊粒度訪問slabs，它的大小跟page一樣大(4KB)。
如果item size 小于 page size，KVell會在slab的item前添加時間戳、key size和value size等信息。
如果item size大于 page size，在其所使用的每個塊的開始位置添加時間戳頭。
對于更新操作：
item size < page size： 就地更新
item size > page size: ? ?將更新追加到slab中，然后在原來的位置寫入tombstone。
item size發(fā)生改變：首先在新的slab中寫入item，接下來刪除舊的item。
5.3 In-memory data structures
Index
目的：查詢item在磁盤上的位置。
KVell為每個工作線程創(chuàng)建了一個在內(nèi)存中的索引（用來存儲磁盤上項的位置）。
Items通過它們的前綴進行所以，沒有采用hash的原因是為了方便掃描操作。
對于中型和大型的items，B樹的性能差，占據(jù)過多的內(nèi)存空間。
prefix、location information、B-tree structure
Page cache
目的：避免頻繁訪問持久化存儲設(shè)備。
頁面緩存會記錄緩存了索引中那個page和那些page按照LRU的順序從cache中被驅(qū)逐。
Free list
free list = slab's free list，一些已經(jīng)釋放的slab list/stack。
當(dāng)刪除一個item時，它所在的slab會被插入每個slab在內(nèi)存中的堆棧(slab's free list)，同時在item 在disk上的位置寫入tombstone。
限制在內(nèi)存中的大小，同時保留批處理I/O一次重用多個塊的能力(不需要額外的磁盤訪問)。
5.4 Efficiently performing I/O
采用AIO，通過批處理的方式，可以決定隊列深度，通過多個請求來攤分系統(tǒng)調(diào)用的開銷。
MMap I/O依賴于OS級的page cache、所以當(dāng)數(shù)據(jù)集不能全部裝入RAM中時，內(nèi)核需要進行頻繁的map和un-map頁面替換，影響CPU性能。
單線程：一次只能發(fā)出一個磁盤讀請求；臟頁定期刷新到磁盤上會導(dǎo)致I/O的爆發(fā)，SSD隊列深度大部分時間處于次優(yōu)狀態(tài)；
多線程：當(dāng)頁面LRU時，需要lock；使TLB條目無效；使所有訪問過該page的核上的虛擬地址到物理地址的映射無效，產(chǎn)生顯著的IPI通信開銷。
Direct I/O：同步的I/O，不需要處理復(fù)雜的map和un-map問題。
5.5 Client operation implementation
update：modify就地modify；delet的value = tombstone，將其slab加入free list中；add有空閑塊則重用，沒有則append。
scan：1從索引中獲取keys的位置；2讀相應(yīng)的頁；KVell需要掃描所有線程的索引，對所有索引進行加鎖，然后輪流解鎖。
5.6 Failure model and recovery
當(dāng)系統(tǒng)崩潰時，通過掃描所有的slab塊然后重新構(gòu)建在內(nèi)存中的索引。
如果一個item被掃描到兩次，選擇將most recent item保存在內(nèi)存索引中，另一個釋放掉。
5.Evaluation
詳見原文
6.寫在最后的話
以上內(nèi)容為閱讀完的自我總結(jié)，英文原文請自行搜索，中文翻譯版可參考：
[KVell: the Design&Implementation of Persistent KVs - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/328243422)
