這些技術不知道，還混什麼存儲圈！

過去半年閱讀了 30 多篇論文，堅持每 1~2 周寫一篇 Newsletter，大部分都和存儲相關。今天在這裡進行一個總結，供大家作為了解存儲技術熱點和趨勢的參考。本文包含了全新的技術領域，如 Open-Channel SSD，Machine Learning for Systems；也包含老話題的新進展，如 NVM，LSM-Tree，Crash Consistency；以及工業界的進展。

Open-Channel SSD

Open-Channel SSD在國內關注的人比較少。和傳統 SSD 相比，Open-Channel SSD 僅提供一個最簡化的 SSD，只包含 NAND 晶元和控制器，並不包含 Flash Translation Layer（FTL）。原有 FTL 中的功能，例如 Logical Address Mapping，Wear Leveling，Garbage Collection 等，需要由上層實現，可能是操作系統，也可能是某個應用程序。也就是說，Open-Channel SSD 提供了一個裸 SSD，用戶可以根據自己的需要設計和實現自己的 FTL，以達到最佳效果。

我們通過一個具體場景來描述 Open-Channel SSD 的價值。RocksDB 作為一個單機存儲引擎，被廣泛應用在很多分散式存儲的場景中。RocksDB 的數據存儲採用 LSM-Tree + WAL 的方式，其中，LSM-Tree 用於存儲數據和索引，WAL 用於保證數據寫入的完整性（Data Integrity）。由於目前在 RocksDB 的實現中，LSM-Tree 中的 SSTable 和 WAL 都是文件系統上的一個文件，所以數據寫入 WAL 的過程中，也會觸發文件系統的數據保護機制，例如 Journaling。而文件系統在將數據寫入 Journal 時，也會觸發 SSD FTL 層的數據保護機制。所以，一次 RocksDB 的寫請求會經過三個 IO 子系統：RocksDB，File System，FTL。每一層子系統為了保證數據完整性，都會產生寫放大（Write Amplification），使得一次寫入被放大幾十甚至上百倍。這個現象可以被形象的描述為『Log-On-Log』的現象。

而實際上，對於 RocksDB 的 WAL，以及文件系統的 Journal，實際上都是臨時性的寫入，並不需要底層系統額外的數據保護機制。Open-Channel SSD 的出現提供了打破這個現象的機會，如果在 RocksDB 可以繞過文件系統層以及 FTL，則可以將三層 Log 合併為一層，避免寫入放大，最大化發揮 SSD 的性能。

除了避免寫放大之外，在 LSM-Tree 數據結中，由於 SSTable 是只讀不可修改的，而 SSD 的 Block 也是只讀的（如果要寫入必須先擦寫），那麼 RocksDB 可以利用 SSD 的這個特點，讓 SSTable 與 Block 對齊，將 LSM-Tree 中的刪除 SSTable 操作與 SSD 的 Block 回收操作合併，避免 SSD Block 回收時產生的數據拷貝操作，避免 GC 對性能產生影響。在『An Efficient Design and Implementation of LSM-Tree based Key-Value Store on Open-Channel SSD』中，就實現了將 LevelDB 直接運行在 Open-Channel SSD 上。

除了避免寫放大，Open-Channel SSD 還提供了實現 IO Isolation 的可能性。由於 SSD 的物理特性，SSD 的性能和數據的物理布局緊密相關。SSD 的性能來自於每一個 NAND 晶元的性能的總和。每一個 NAND 晶元提供的 IO 性能很低，但由於 NAND 晶元之間可以進行並行化，這使得 SSD 的整體性能非常高。換句話說，數據的布局決定了 IO 性能。然而由於傳統的 SSD 上運行了 FTL，FTL 不僅會對數據的布局進行重映射，同時在後台還會運行 GC 任務，這使得 SSD 的性能是無法預測的，也無法進行隔離。Open-Channel SSD 將底層信息暴露給上層應用，通過將數據放置在不同的 NAND 晶元上，可以在物理層面達到數據分布隔離，同時也就打到了性能的隔離的效果。

為了方便的管理和操作 Open-Channel SSD，LightNVM應運而生。LightNVM 是在 Linux Kernel 中一個針對 Open-Channel SSD 的 Subsystem。LightNVM 提供了一套新的介面，用於管理 Open-Channel SSD，以及執行 IO 操作。為了和 Kernel 中現有的 IO 子系統協同工作，還存在 pblk（Physical Block Device）層。他在 LightNVM 的基礎上實現了 FTL 的功能，同時對上層暴露傳統的 Block 層介面，使得現有的文件系統可以通過 pblk 直接運行在 Open-Channel SSD 上。2017 年 FAST 上的一篇 paper：『LightNVM: The Linux Open-Channel SSD Subsystem』專門介紹了 LightNVM。

目前 LightNVM 已經被合併入 Kernel 的主線。而對於用戶態的程序來說，可以通過 liblightnvm 操作 Open-Channel SSD。

2018 年 1 月，Open-Channel SSD 發布了2.0版本的標準。但無論是 Open-Channel SSD，還是 LightNVM 都還處於非常早期的階段，目前在市面上很難見到 Open-Channel SSD，不適合直接投入到生產中。儘管如此，Open-Channel SSD 和 Host based FTL 帶來的好處是非常巨大的。對於追求極致存儲性能的場景，在未來很可能會採用 Open-Channel SSD + LightNVM 的實現方式。

Non-volative Memory（NVM）

NVM，或者 PM（persistent memory），SCM（storage class memory），實際上都是一個意思，指的都是非易失性內存。NVM 在學術界火了很多年了， 相關的研究在不斷向前推進。

一直以來，由於 2：8 定律的特性，計算機系統的存儲一直是採用分層的結構，從上到下依次是 CPU Cache，DRAM，SSD，HDD。 其中，CPU Cache 和 DRAM 是易失性的（volatile），SSD 和 HDD 是非易失性的（non-volatile）。儘管 SSD 的速度遠高於 HDD，但和 DDR 相比，還是有一定的差距。SSD 提供 10us 級別的響應時間，而 DRAM 只有 ns 級別，這中間有一萬倍的差距。由於 DRAM 和 SSD 之間巨大的性能差距，使得應用程序需要非常仔細的設計 IO 相關的操作，避免 IO 成為系統的性能瓶頸。

而 NVM 的出現彌補了這個差距。NVM 在保持非易失性的前提下，將響應時間降低到 10ns 級別，同時單位容量價格低於 DRAM。此外，NVM 是按位元組訪問（byte-addressable），而不像磁碟按照塊（Block）訪問。NVM 的出現打破了傳統的存儲層次，將對軟體架構設計產生巨大的影響。

NVM 看上去很美好，但目前並不能像內存或磁碟一樣，做到即插即用。在傳統的操作系統中，Virtual Memory Manager（VMM）負責管理易失性內存，文件系統負責管理存儲。而 NVM 既像內存一樣可以通過位元組訪問，又像磁碟一樣具有非易失性的特點。使用 NVM 的方式主要有兩種：

將 NVM 當做事務性內存（Persistant Transactional Memory）使用，包括採用 Redo Logging，Undo Logging，以及 Log-Structured 等管理方式。

將 NVM 當做磁碟使用，提供塊以及文件的介面。例如在 Linux 中引入的Direct Access（DAX），可以將對現有的文件系統進行擴展，使得其可以運行在 NVM 上，例如 Ext4-DAX。也有類似於PMFS，NOVA等專門為 NVM 定製的文件系統。

面向 NVM 進行編程和面向傳統的內存或磁碟編程是非常不同，這裡我們舉一個非常簡單的例子。例如，有一個函數用於執行雙鏈表插入操作：

void list_add_tail(struct cds_list_head *newp, struct cds_list_head *head) { head->prev->next = newp; newp->next = head; newp->prev = head->prev; head->prev = newp;}

然而對於 NVM 來說，由於是非易失性的，假設在執行到函數的第一行後發生了斷電，當系統恢復後，鏈表處於一個異常且無法恢復的狀態。同時，由於 CPU 和 NVM 之間還有 CPU Cache 作為緩存，以及 CPU 執行具有亂序執行的特性，所以 NVM 需要使用特殊的編程模型，也就是 NVM Programming Model。通過顯示的指定 Transaction，達到原子性操作的語義，保證當系統恢復時，不會產生中間狀態。

在分散式場景下，如果要充分發揮 NVM 的性能，就必須和 RDMA 結合。由於 NVM 的超高的性能，Byte Addressable 的訪問特性，以及 RDMA 的訪問方式，使得分散式的 NVM + RDMA 需要全新的架構設計，包括單機數據結構，分散式數據結構，分散式一致性演算法等等。在這方面，清華計算機系高性能所去年發表的Octopus提供了一個思路，通過 NVM + RDMA 實現了分散式文件系統，同時在自己實現一套基於 RDMA 的 RPC 用於進行節點間的通信。

然而尷尬的是，儘管學術界在 NVM 上已經研究了數十年，但在工業界目前還沒有可以大規模商用的 NVM 產品，大家還只能基於模擬器進行研究。Intel 和 Micro 在 2012 年合作一起研發 3D XPoint 技術，被認為是最接近能商用的 NVM 產品。Intel 在 2017 年發布了基於 3D XPoint 技術的磁碟產品 Optane，而 NVM 產品（代號 Apache Pass）還沒有明確的發布時間。

然而即使 NVM 產品面世，由於 NVM 的價格和容量的限制，以及複雜的編程模式，在實際生產中很少會出現純 NVM 的場景，更多的還是 tiering 的形式，也就是 NVM + SSD + HDD 的組合。在這個方面，2017 SOSP 上的一篇論文Strata也提供了一個不錯的思路。

Machine Learning for Systems

去年 Jeff Dean 所在的 Google Brain 團隊發表了一篇非常重要的論文『The Case for Learned Index Structures』。可以說從這篇文章開始，系統領域展開了一個新的方向，Machine Learning 與系統相結合。不得不讚歎 Jeff Dean 對計算機科學的影響力。

這篇文章，以及 Jeff Dean 在 NIPS17 ML Systems Workshop 上的talk，都釋放出了一個很強的信號，計算機系統中包含了大量的 Heuristics 演算法，用於做各種各樣的決策，例如 TCP 窗口應該設置為多大，是否應該對數據進行緩存，應該調度哪一個任務等等。而每一種演算法都存在性能，資源消耗，錯誤率，以及其他方面的 Tradeoff，需要大量的人工成本進行選擇和調優。而這些正是Machine Learning 可以發揮的地方。

在『The Case for Learned Index Structures』文章中，作者提到了一個典型的場景，資料庫的索引。傳統的索引通常採用 B 樹，或 B 樹的變種。然而這些數據結構通常是為了一個通用的場景，以及最差的數據分布而進行設計的，並沒有考慮到實際應用中數據分布情況。對於很多特殊的數據分布場景，B 樹並不能夠達到最優的時間和空間複雜度。為了達到最佳效果，需要投入大量的人力進行數據結構的優化。同時，由於數據的分布在不斷的變化，調優的工作也是持續不斷的。作者提出的的 Learned Index，則是通過與 Machine Learning 技術結合，避免人工調優的開銷。

在這篇文章中，作者把索引數據結構當做一個 Model，這個 Model 的輸入是一個 Key，輸出是這個 Key 對應的 Value 在磁碟中的位置。而 B 樹或其他的數據結構只是實現這個 Model 的一種方式，而這個 Model 也可以存在其他的實現形式，例如神經網路。

和 B 樹相比，神經網路具有很大的優勢：

由於不需要在內存中保存 key，所以佔用內存空間極小。尤其當索引量巨大時，避免產生磁碟訪問。

由於避免了樹遍歷引入的條件判斷，查找速度更快

通過進行離線的模型訓練，犧牲一定的計算資源，可以達到節省內存資源，以及提高性能的效果。

當然，這種方法也存在一定的局限性。其中最重要的一點，就是 Learned Index 只能索引固定數據分布的數據。當有數據插入時導致數據分布發生了變更，原有的模型就會失效。解決的方案是對於新增的數據，依然採用傳統的數據結構進行索引，Learned Index 只負責索引原有數據。當新增數據積累到一定程度時，將新數據與原有數據進行合併，並根據新的數據分布訓練出新的模型。這種方法是很可行的，畢竟和新增數據量相比，全量數據是非常大的。如果能對全量數據的索引進行優化，那應用價值也是巨大的。

儘管存在一定的局限性，Learned Index 還是有很多適用的場景，例如 Google 已經將其應用在了 BigTable 中。相信 Learned Index 只是一個開端，未來會有越來越多的 System 和 Machine Learning 結合的工作出現。

LSM-Tree 優化

LSM-Tree 是 LevelDB，以及 LevelDB 的變種，RocksDB，HyperDB 等單機存儲引擎的核心數據結構。

LSM-Tree 本身的原理我們不過多介紹。目前 LSM-Tree 最大的痛點是讀寫放大，這使得性能往往只能提供裸硬體的不到 10%。所以關於解決 LSM-Tree 讀寫放大問題成為近些年研究的熱點。

在 2016 年 FAST 會議上發表的論文WiscKey提出了將 Key 與 Value 分開存放的方法。傳統 LSM-Tree 將 Key 和 Value 相鄰存放，保證 Key 和 Value 在磁碟上都是有序的。這提高了 Range Query 的效率。然而，當進行 Compaction 時，由於需要同時操作 Key 和 Value，所以造成了較大讀寫比例放大。而在 WiscKey 中，通過將 Key 和 Value 分開存放，Key 保持 LSM-Tree 結構，保證 Key 在磁碟上的有序性，而 Value 使用所謂 『Value Log』 結構，很像 Log-Structured File System 中的一個 Segment。通過在 Key 中保存 Value 在磁碟上的位置，使得可以通過 Key 讀取到 Value。由於 LSM-Tree 中只保存 Key，不保存 Value，且 Key 的大小通常遠小於 Value 的大小，所以 WiscKey 中的 LSM-Tree 的大小遠小於傳統 LSM-Tree 的大小，因此 Compaction 引入的讀寫放大可以控制在非常小的比例。WiscKey 的缺點是犧牲了 Range Query 的性能。由於相鄰 Key 的 Value 在磁碟上並沒有存在相鄰的位置，WiscKey 中對連續的 Key 讀取被轉化成隨機磁碟讀取操作。而作者通過將預讀（Prefetching）IO 並行化的方式，儘可能降低對順序讀性能的影響。

而在 2017 年 SOSP 上發表的論文PebblesDB提出了另外一種思路。在傳統 LSM-Tree 中，每一層由多個 SSTable 組成，每一個 SSTable 中保存了一組排好序 Key-Value，相同層的 SSTable 之間的 Key 沒有重疊。當進行 Compaction 時，上層的 SSTable 需要與下層的 SSTable 進行合併，也就是將上層的 SSTable 和下層的 SSTable 讀取到內存中，進行合併排序後，組成新的 SSTable，並寫回到磁碟中。由於 Compaction 的過程中需要讀取和寫入下層的 SSTable，所以造成了讀寫放大，影響應能。

PebblesDB 將 LSM-Tree 和 Skip-List 數據結構進行結合。在 LSM-Tree 中每一層引入 Guard 概念。 每一層中包含多個 Guard，Guard 和 Guard 之間的 Key 的範圍是有序的，且沒有重疊，但 Guard 內部包含多個 SSTable，這些 SSTable 的 Key 的範圍允許重疊。

當需要進行 Compaction 時，只需要將上層的 SSTable 讀入內存，並按照下層的 Guard 將 SSTable 切分成多個新的 SSTable，並存放到下層對應的 Guard 中。在這個過程中不需要讀取下層的 SSTable，也就在一定程度上避免了讀寫放大。作者將這種數據結構命名為 Fragemented Log-Structured Tree（FLSM）。PebblesDB 最多可以減低 6.7 倍的寫放大，寫入性能最多提升 105%。

和 WiscKey 類似，PebblesDB 也會多 Range Query 的性能造成影響。這是由於 Guard 內部的 SSTable 的 Key 存在重疊，所以在讀取連續的 Key 時，需要同時讀取 Guard 中所有的 SSTable，才能夠獲得正確的結果。

WiscKey 和 PebblesDB 都已經開源，但在目前最主流的單機存儲引擎 LevelDB 和 RocksDB 中，相關優化還並沒有得到體現。我們也期待未來能有更多的關於 LSM-Tree 相關的優化演算法出現。

Crash Consistency

Crash Consistency 的意思是，存儲系統可以在故障發生後，保證系統數據的正確性以及數據，元數據的一致性。可以說 Crash Consistency 是存儲領域永恆不變的話題。

早些年大家熱衷於通過各種方法在已實現的文件系統中尋找 Bug，而這兩年構造一個新的 Bug Free 的文件系統成為熱門的方向。在這方面最早做出突破的是 MIT 的團隊的FSCQ。FSCQ 通過 Coq 作為輔助的形式化驗證工具，在 Crash Hoare Logic 的基礎上，實現了一個被證明過 Crash Safty 的文件系統。

然而使用 Coq 的代價是需要人工手動完成證明過程，這使得完成一個文件系統的工作量被放大了幾倍，例如 FSCQ 的證明過程花費了 1.5 年。

而 Washington 大學提出的Yggdrasil則基於 Z3，將文件系統證明過程自動化，也就是最近非常流行的『Push-Button Verification』 的方法。

值得注意的是，無論是 FSCQ 還是 Yggdrasil 都存在著巨大的局限性，例如不支持多線程訪問，文件系統功能並不完備，性能較弱，以及代碼生成過程中依賴一些沒有被驗證過的工具等等。我們距離構建一個在通用場景下可以完全替代已有文件系統（如 ext4）還有很長的路要走。這也依賴於形式化驗證方面的技術突破。

工業界進展

隨著虛擬化技術的成熟和普及，存儲的接入端逐漸從 HBA 卡或傳統操作系統，轉變為 Hypervisor。在 Linux KVM 方面，隨著存儲性能逐漸提高，原有的 virtio 架構逐漸成為了性能瓶頸，vhost 逐漸開始普及。所謂 vhost 就是把原有 Qemu 對於 IO 設備模擬的代碼放到了 Kernel 中，包含了 vhost-blk，以及 vhost-net。由 Kernel 直接將 IO 請求發給設備。通過減少上下文的切換，避免額外的性能開銷。

在容器方面，隨著 K8S 的應用和成熟，在 K8S 的存儲方面也誕生了一些新的項目。比如rook.io是基於 K8S 的編排工具。而 K8S 本身也發布了Container Storage Interface（CSI），用於第三方存儲廠商更好的開發 K8S 的存儲插件。未來也會看到越來越多的存儲廠商對 K8S 進行支持。

2017 年 Linux Kernel 共發布了 5 個版本，從 4.10 到 4.14，目前最新的版本是 4.15。其中存儲相關比較值得注意的變化包括：AIO 改進，Block Layer 錯誤處理改進，基於 MQ 的調度器 Kyber等等。然而比較悲傷的消息是，為了修復 Meltdown 和 Spectrue 漏洞，Kernel 引入了Kernel Page Table Isolation（KPTI）技術，這導致系統調用和上下文切換的開銷變得更大。Brendan Gregg 在他的博客中詳細分析了 KPTI 對性能產生的影響。對於系統調用與上下文切換越頻繁的應用，對性能的影響越大。也就是說，IO 密集型的應用將受到比較大的影響，而計算密集型的應用則影響不大。

在企業級存儲方面，去年有很多存儲廠商都開始向純軟體廠商進行轉型，包括 Nutanix，Kaminario 以及 E8 等等。向軟體化轉型並不是處於技術的原因，而是商業的考慮。考慮到 Dell 和 EMC 的合併，存儲硬體的利潤率必定會不斷下降。軟體化最大的好處，就是可以提升財務報表中的利潤率，使得公司的財務狀況更加健康，也避免了和 Dell EMC 的存儲硬體發生競爭。

在資本市場方面，2017 年可以說是波瀾不驚。上圖是 2017 年存儲行業發生的併購案。其中 Toshiba Memory 被收購的案件是存儲行業歷史上第三大收購案（第一名是 Dell 收購 EMC）。

總結

以上是作者對當前存儲熱點和趨勢的不完整的總結。希望幫助讀者對存儲領域增加一點點了解，或者是對存儲技術產生一點點的興趣。也歡迎大家把自己感興趣的話題寫在評論里，我們將在後面儘可能的為大家進行介紹。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！