[[350070]]

本文要介紹的是 2019 年 SOSP 期刊中的論文 —— KVell: the Design and Implementation of a Fast Persistent Key-Value Store[^1]，該論文實(shí)現(xiàn)的 KVell 是為現(xiàn)代 SSD 開發(fā)的鍵值存儲系統(tǒng)，與使用 LSM 樹(Log-structured merge-tree)或者 B 樹的主流鍵值存儲不同，KVell 為了充分利用新設(shè)備的性能并降低 CPU 的開銷使用了完全不同的設(shè)計(jì)。

作為軟件工程師，我們直接與硬件打交道的概率其實(shí)很少，大多數(shù)時(shí)間都會通過操作系統(tǒng)以和 POSIX 間接操作不同的硬件。雖然看起來過去 10 年磁盤等存儲硬件的演變與更新非常緩慢，但是實(shí)際上：

• 磁盤遠(yuǎn)比 10 年前要快得多;
• 磁盤的隨機(jī)和順序 I/O 性能差距變小;

圖 1 - 磁盤的演進(jìn)[^2]

磁盤性能和特性的演進(jìn)使得在過去很多鍵值存儲成立的設(shè)計(jì)變得無效，例如：隨機(jī) I/O 的速度遠(yuǎn)遠(yuǎn)慢于順序 I/O，很多數(shù)據(jù)庫為了減少隨機(jī) I/O 的次數(shù)會使用特定的數(shù)據(jù)結(jié)構(gòu)并犧牲一些 CPU 計(jì)算資源，但是在最新的硬件上已經(jīng)沒有太多的必要了。

KVell 的論文中不止提到了目前主流鍵值存儲在新存儲設(shè)備上各種問題，還給出了最新的設(shè)計(jì)原則、實(shí)現(xiàn)方式以及對性能的評估。我們在這里不會面面俱到的介紹論文中全部的內(nèi)容，主要會分析主流鍵值存儲的問題以及最新的設(shè)計(jì)原則，其余的內(nèi)容各位讀者可以在論文中自行探索。

實(shí)現(xiàn)問題

目前的大多數(shù)的鍵值存儲系統(tǒng)都會使用 LSM 樹或者 B 樹作為主要的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，這兩種不同的數(shù)據(jù)結(jié)構(gòu)適合用于不同類型的工作負(fù)載：

LSM 樹：適合寫密集型的負(fù)載;

B 樹：適合讀密集型的負(fù)載;

圖 2 - LSM 和 B 樹

RocksDB 和 Cassandra 等數(shù)據(jù)庫都使用 LSM 樹，而 MongoDB 以及其他的數(shù)據(jù)庫都會使用 B 樹和它的變種。雖然這兩者設(shè)計(jì)在過去都有著優(yōu)異的表現(xiàn)，不過這兩種設(shè)計(jì)在 NVMe SSD 這種較新的硬件上表現(xiàn)地并不好，CPU 成為了瓶頸并導(dǎo)致嚴(yán)重的性能波動。

LSM 樹

LSM 樹是為寫密集型負(fù)載特別優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，在 LSM 樹中，我們使用內(nèi)存緩存接收所有的寫操作并將變更批量寫入磁盤，內(nèi)存緩存中的數(shù)據(jù)會被后臺線程合并到持久存儲里的樹形結(jié)構(gòu)中。

圖 3 - LSM 樹

磁盤中的數(shù)據(jù)結(jié)構(gòu)包含多個(gè)層級，每個(gè)層級都會包含多個(gè)不可變的、排序后的文件，同一個(gè)層級中文件的鍵范圍也不會有重疊。為了保證上述特性，LSM 引入了 CPU 和 I/O 密集的操作 — 壓縮，如上圖所示，壓縮會將多個(gè)低層級的文件合并成更高層級的文件，保證鍵值對的順序并刪掉其中重復(fù)的鍵。這也使得 CPU 在新的存儲設(shè)備上已經(jīng)成為 LSM 樹的主要瓶頸，這種設(shè)計(jì)讓我們在舊設(shè)備上花費(fèi) CPU 時(shí)間保證數(shù)據(jù)的順序并降低掃描操作順序訪問磁盤時(shí)的延遲。

除了 CPU 成為瓶頸之外，使用 LSM 樹的鍵值存儲的負(fù)載在數(shù)據(jù)壓縮時(shí)會受到顯著的影響，論文中的數(shù)據(jù)表示 RocksDB 在壓縮期間的性能可能會降低一個(gè)數(shù)量級，雖然有一些技術(shù)可以緩解數(shù)據(jù)壓縮的影響，但是這些方法在高端的 SSD 上卻并不適用。

B 樹

B+ 樹只在葉節(jié)點(diǎn)存儲鍵值對數(shù)據(jù)，內(nèi)部的節(jié)點(diǎn)只包含用于路由的鍵，每個(gè)葉節(jié)點(diǎn)都包含一組排序后的鍵值對，所有的葉節(jié)點(diǎn)會組成方便掃描的鏈表。最先進(jìn)的 B+ 樹為了實(shí)現(xiàn)優(yōu)異的性能都會依賴緩存，大多數(shù)的寫操作也都會先寫入提交日志再寫入緩存，當(dāng)緩存中的數(shù)據(jù)被驅(qū)逐時(shí)，B+ 樹中的信息才會被更新。

圖 4 - B 樹

B+ 樹中有兩種操作可以持久化其中的數(shù)據(jù)，也就是檢查點(diǎn)(Checkpoint)和驅(qū)逐(Eviction);其中，前者是按照固定頻率觸發(fā)的，當(dāng)日志的大小達(dá)到了特定的閾值后才會觸發(fā)，這樣可以保證提交日志的大小在固定范圍內(nèi)，而驅(qū)逐會從緩存向樹中寫入臟數(shù)據(jù)，它也會在緩存達(dá)到特定閾值時(shí)觸發(fā)寫入。

這種設(shè)計(jì)更容易受到同步(Synchronization)額外開銷的影響，論文在測試中發(fā)現(xiàn)只有 18% 的時(shí)間用于處理客戶端的請求，而其他時(shí)間都用于不同的等待，內(nèi)核中 75% 的時(shí)間都在等待 futex 和 yield 等函數(shù)調(diào)用。

當(dāng)內(nèi)存中數(shù)據(jù)的驅(qū)逐不能快速完成時(shí)，B 樹的性能也會受到影響，論文中的數(shù)據(jù)表示 WiredTiger 的吞吐量會在延遲期間從 120 Kops/s 降低到 8.5Kops/s，這種巨大的影響持續(xù)幾秒鐘的時(shí)間才會恢復(fù)。

設(shè)計(jì)原則

為了利用新存儲設(shè)備的特性并減少鍵值存儲的 CPU 開銷，我們在現(xiàn)代 SSD 上開發(fā)的 KVell 會遵循如下所示的設(shè)計(jì)原則提高鍵值存儲的性能：

• 不共享數(shù)據(jù)：所有的數(shù)據(jù)結(jié)構(gòu)都分片存儲在不同的 CPU 上，所有的 CPU 也就不需要在執(zhí)行計(jì)算時(shí)同步數(shù)據(jù);
• 磁盤中的數(shù)據(jù)不排序、內(nèi)存中的索引排序：在磁盤上存儲未經(jīng)排序的數(shù)據(jù)，避免昂貴的重排操作;
• 減少系統(tǒng)調(diào)用、而不是順序 I/O：因?yàn)楝F(xiàn)代 SSD 上的隨機(jī) I/O 和順序 I/O 有著相似的性能，所以減少批處理 I/O 能夠降低 CPU 的額外開銷;
• 不需要提交日志：不在內(nèi)存中緩存數(shù)據(jù)的更新，避免不必要的 I/O 操作;

不共享數(shù)據(jù)

在多線程的軟件系統(tǒng)中，稍微有常識的人都知道不同線程之間同步數(shù)據(jù)會對性能帶來比較大的影響，讓多個(gè)線程之間不共享數(shù)據(jù)就可以避免上述的同步開銷，減少線程等待帶來的性能損失。

圖 5 - 不共享數(shù)據(jù)的設(shè)計(jì)

為了實(shí)現(xiàn)這一目標(biāo)，KVell 的每個(gè)線程都會處理一組特定鍵的操作并維護(hù)這些鍵相關(guān)的私有數(shù)據(jù)結(jié)構(gòu)：

1. 輕量級的、內(nèi)存中的 B 樹索引 — 存儲了鍵在持久存儲的位置;
2. I/O 隊(duì)列 — 負(fù)責(zé)從持久存儲中快速讀取或者寫入數(shù)據(jù);
3. 空閑列表 — 內(nèi)存中的用于存儲鍵值對的硬盤塊;
4. 頁面緩存 — 使用內(nèi)部的頁面緩存，不依賴于操作系統(tǒng);

鍵值存儲的大多數(shù)操作都只是對單個(gè)鍵的增刪改查，這些操作都不需要多線程之間的數(shù)據(jù)同步，只有遍歷鍵值的掃描才需要不同線程之間同步內(nèi)存中的 B 樹索引。

磁盤不排序

因?yàn)?KVell 不會在磁盤上按照順序排序數(shù)據(jù)，所以鍵值對在磁盤中初始位置就是它的最終位置，這種不排序的方式不僅可以減少插入項(xiàng)目的額外開銷，而且可以消除磁盤維護(hù)操作帶來的 CPU 開銷。

無序的鍵值對雖然可以降低寫操作的開銷，但是也會影響掃描時(shí)的性能，不過根據(jù)論文中的測試，掃描的操作在遇到中等大小的負(fù)載以及大鍵值對時(shí)不會被明顯地影響，所以這個(gè)結(jié)果在多數(shù)情況下是可以接受的。

減少系統(tǒng)調(diào)用

在 KVell 中，所有的操作都會在磁盤中執(zhí)行隨機(jī)的讀寫，所以它不會浪費(fèi) CPU 時(shí)間將隨機(jī) I/O 轉(zhuǎn)換成順序 I/O。與 LSM 鍵值對類似，KVell 會將 I/O 請求批量轉(zhuǎn)發(fā)給磁盤，它的主要目的是減少系統(tǒng)調(diào)用的次數(shù)，即 CPU 的額外開銷。有效地鍵值存儲應(yīng)該向磁盤發(fā)出足夠的請求保證磁盤擁有足夠的工作，但是不應(yīng)該發(fā)出過多的工作影響磁盤的性能并帶來較高的延遲。

移除提交日志

KVell 不會依賴提交日志決定數(shù)據(jù)是否被系統(tǒng)持久化，它只會在更新寫入到磁盤的最終位置時(shí)確認(rèn)更新，一旦更新被工作線程提交，它會在下一批 I/O 請求中處理。提交日志的作用其實(shí)是將隨機(jī) I/O 變成順序 I/O，解決崩潰帶來的一致性影響，但是因?yàn)榻裉斓碾S機(jī) I/O 與順序 I/O 已經(jīng)有著類似的性能，所以提交日志在鍵值存儲中已經(jīng)失去了過去的作用，移除提交日志可以減少磁盤帶寬的占用。

總結(jié)

KVell 作為基于最新硬件的鍵值存儲系統(tǒng)，它在特定場景下有著非常優(yōu)異的性能表現(xiàn)，論文中給出了它與主流的鍵值存儲在不同負(fù)載下的吞吐量對比，其中 YCSB A、YCSB B、YCSB C 和 YCSDN E 分別是寫密集型、讀密集型、只讀和掃描密集型地任務(wù)，從中我們可以看出，在除了掃描密集型地任務(wù)之外的其他負(fù)載中，KVell 的表現(xiàn)都遠(yuǎn)好于 RocksDB 等主流鍵值存儲：

圖 6 - KVell 吞吐量對比

作為軟件工程師，雖然說操作系統(tǒng)為我們提供了操作硬件的標(biāo)準(zhǔn)接口，使得我們不用于硬件直接接觸，可以將更多的精力放到軟件上，但是我們?nèi)匀灰獣r(shí)刻牢記硬件對軟件系統(tǒng)的諸多影響和限制并用發(fā)展的眼光看待硬件的進(jìn)步，也只有軟硬件結(jié)合才能帶來極致的性能。

本文轉(zhuǎn)載自微信公眾號「真沒什么邏輯」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系真沒什么邏輯公眾號。