糾刪碼存儲系統中的投機性部分寫技術

04-19

前言

近日，美團雲存儲研發專家李慧霸和張志明聯合撰寫的《糾刪碼存儲系統中的投機性部分寫技術》論文在USENIX ATC 2017發表。

今年的USENIX ATC於7月12日-14日在SANTA CLARA 舉辦。USENIX ATC是計算機系統領域的頂級國際學術會議，也是中國計算機學會推薦的A類系統會議，活動主辦方USENIX 是計算機系統領域極具影響力的組織之一，該組織主辦的ODSI, NSDI, USENIXATC, FAST, USENIX Security等會議在學術界及業界均享有盛譽。

USENIX ATC17的論文錄用率大約在20%左右。此前，計算機系統領域中Oak語言(Java的前身)、TCL、QEMU、ZooKeeper、Raft等一系列有影響力的研究成果都是在USENIX ATC發表或公布的，其中QEMU、ZooKeeper、Raft已成為現今雲計算技術、互聯網技術的基石。

此次被收錄的《糾刪碼存儲系統中的投機性部分寫技術》便是這嚴選中的一篇，本文提出了一種通過在校驗塊上使用變更日誌的方法來改進糾刪碼寫性能的技術，該方法相較傳統的改進方法能夠減少I/O操作，從而大幅提升性能。

相比傳統改進方法，此篇論文中的改進方式存在以下3點不同：

日誌中記錄的是數據本身，而不是校驗數據的增量差值；
對於變更日誌中涉及的每一個數據塊，都需要額外記錄1次且僅1次其變更前的數據，稱為d(0)；
校驗塊的更新由數據塊發起，並且首次請求不附帶d(0)，若校驗塊的響應明確表示需要d(0)，數據塊再將d(0)發送過去。

通過這樣的設計，系統可以實現在大多數情況下不需要讀取並發送d(0)到校驗塊，此為投機成功；在少數情況下投機失敗，仍然需要讀取並發送d(0)給校驗塊，但投機失敗的代價僅僅是增加一次網路交互延遲（大約0.1~0.2毫秒），相對於機械硬碟的尋道延遲（平均幾毫秒）可以忽略不計，因而這幾乎是一個「穩賺不賠」的優化。

投機性部分寫的原理、設計與實現

這一結論允許我們不必每次計算校驗差值，而使用數據的最終值和原始值（即 d(r)和d(0)，省略下標）之間的差值來等價計算整個過程的校驗值增量。因而 d(0)只需要讀取一次（在寫入 d(1) 的時候）。對於這一系列的r次寫操作，投機只會在第一次失敗，在之後的r?1次均成功，直到日誌被合併進入校驗數據塊或遇到全量寫操作。

對於失敗的投機，校驗塊會返回一個特定的錯誤碼，以通知數據塊將d0發送過來，這僅僅帶來一次網路RTT的額外開銷，大約0.1ms~0.2ms，相對於磁碟I/O時間來說可以忽略。

現實當中的I/O負載也存在大塊順序的操作，這將產生整個EC組的全量寫操作。對於這種操作，我們將直接計算出校驗數據，並將其寫入校驗塊，同時在變更日誌中記錄一個特殊操作I，表示將I之前的變更記錄取消掉，因為最新的數據已經直接寫到校驗塊內了。

根據上述原理，我們設計出如下圖所示的部分寫流程（以三個校驗塊為例，如圖1），並基於美團雲現有的分散式塊存儲系統將這一設計實現出來，稱為PBS，提供強一致性保障，系統的寫操作流程整體如圖2所示（以兩個校驗塊為例）

（圖1）

（圖2）

實驗

EC編解碼性能

針對EC(4,2)、EC(6,3)、EC(8,4)、EC(10,4)等多種配置進行編解碼測試的實驗結果顯示，在SSE、AVX等向量運算指令集的幫助下，現代CPU的1個核心每秒就能完成5~13GB數據量的編解碼工作，遠遠大於同時期各種外部存儲設備的吞吐率，所以編解碼運算已不再成為EC存儲系統的瓶頸。

（圖3）

PBS部分寫的性能

所有的測試均在虛擬機內掛載PBS完成。我們的測試環境為3台伺服器，每台配備10塊硬碟，7200RPM。測試了隨機寫IOPS，以及隨機寫的延遲，來衡量部分寫的性能，其中I/O大小為4KB，EC組的條帶大小為16KB。

測試結果分別如圖4、圖5所示，其中HDD表示單塊7200RPM的物理硬碟的基準性能，R3表示三副本模式，PBS-1和PBS-2分別表示PBS在投機失敗（首次寫）和投機成功（第二次及以後）的情況，EC表示增量編碼方法，PLog表示按照傳統改進方法所能達到的最好結果。

（圖4）

（圖5）

從結果可以看出，各種情況下的讀性能大致相當，PBS-1（投機失敗，小概率）比PLog略低，PBS-2（投機成功，大概率）遠遠好於PLog，甚至可以與三副本模式的性能相媲美。

故障恢復

我們在內存中為日誌建立了索引，因而在（故障恢復中）讀取日誌時可以快速定位數據偏移。如圖6所示，測試結果表明日誌大小對故障恢復速度的影響有限。

（圖6）

結語

糾刪碼（Erasure Code）作為存儲系統中常見的兩種數據可靠性方法之一，與多副本冗餘不同，EC將m個原始數據塊編碼生成k個檢驗塊，形成一個EC組，之後系統可最多容忍任意k個原始數據塊或校驗塊損壞，都不會產生數據丟失，並且可將數據存儲的冗餘度降低50%以上，大大降低了存儲成本，在許多大規模分散式存儲系統中已得到實際應用。

該篇論文中所述的投機性部分寫技術將會應用在美團雲的存儲系統中，讀者可以通過註冊美團雲賬戶體驗、對比。