前言

多副本和糾刪碼(EC，Erasure Code)是存儲系統(tǒng)中常見的兩種數(shù)據(jù)可靠性方法。與多副本冗余不同，EC將m個原始數(shù)據(jù)塊編碼生成k個檢驗塊，形成一個EC組，之后系統(tǒng)可最多容忍任意k個原始數(shù)據(jù)塊或校驗塊損壞，都不會產(chǎn)生數(shù)據(jù)丟失。糾刪碼可將數(shù)據(jù)存儲的冗余度降低50%以上，大大降低了存儲成本，在許多大規(guī)模分布式存儲系統(tǒng)中已得到實際應(yīng)用。

EC給寫操作帶來了很大的額外開銷，包括編解碼計算開銷和流程性開銷兩部分。在向量指令集SSE、AVX等的幫助下，一個現(xiàn)代CPU核心的EC編解碼能力就可以達(dá)到幾GB到十幾GB每秒，遠(yuǎn)遠(yuǎn)大于存儲設(shè)備的I/O吞吐率。這使得流程性開銷成為EC寫入性能的最重要制約因素。若一次寫操作的偏移和長度沒有對齊EC組，就需要部分更新涉及的EC組，因而將此類操作稱為部分寫。部分寫帶來了大部分的流程性開銷。

[[193275]]

處理部分寫的最直接辦法是將不被寫的數(shù)據(jù)塊讀出來，跟新數(shù)據(jù)組合在一起，然后再整體編碼并寫入。目前Ceph、Sheepdog等系統(tǒng)都采用了這種辦法。一種簡單有效的改進(jìn)是將被覆蓋數(shù)據(jù)的原始值讀出來，然后根據(jù)新舊數(shù)據(jù)的差值來進(jìn)行增量編碼，得到各個校驗塊的差值，并“加”到各個校驗塊上。這種方法可以顯著減少系統(tǒng)總體I/O次數(shù)，然而它需要對涉及的數(shù)據(jù)塊和所有校驗塊進(jìn)行原地讀寫(即在同一位置進(jìn)行先讀后寫)，在沒有緩存的情況下(常態(tài))，HDD需要花費8.3毫秒(7200RPM)的時間旋轉(zhuǎn)一周才能完成寫入請求，跟一次隨機(jī)I/O的平均尋道時間相當(dāng)。這樣的流程極大地影響了寫入效率，即便應(yīng)用層面發(fā)出的是順序?qū)懖僮?，最終得到的性能也跟隨機(jī)寫差不多。

在實際應(yīng)用當(dāng)中，只有寫操作的偏移和長度都恰好跟EC組對齊才可以避免部分寫，然而應(yīng)用往往無法照顧到底層存儲的實現(xiàn)細(xì)節(jié)和參數(shù)，所以部分寫構(gòu)成了寫操作的主體，決定了EC存儲系統(tǒng)的實際寫性能。EC模式的部分寫性能大大低于三副本寫，這使得EC尚不適用于寫操作較多的場合，如云硬盤。

目前業(yè)內(nèi)已有許多工作對這一問題進(jìn)行改進(jìn)，其中最具代表性的工作是2014年發(fā)表在FAST技術(shù)會議上的“Parity Logging with Reserved Space: Towards Efficient Updates and Recovery in Erasure-coded Clustered Storage”，它的核心思路是通過在校驗塊上記變更日志的方式來減少其上不必要的讀操作，同時將隨機(jī)寫變成順序追加寫，以改善寫入性能。然而它并不能改善原始數(shù)據(jù)塊上的寫流程，這構(gòu)成了大多數(shù)的寫操作，所以系統(tǒng)總體寫性能改善有限。

我們的改進(jìn)思路仍然是在校驗塊上使用變更日志，但與傳統(tǒng)方法有顯著區(qū)別：(1)日志中記錄的是數(shù)據(jù)本身，而不是校驗數(shù)據(jù)的增量差值;(2)對于變更日志中涉及的每一個數(shù)據(jù)塊，都需要額外記錄1次且僅1次其變更前的數(shù)據(jù)，稱為d(0)d(0);(3)校驗塊的更新由數(shù)據(jù)塊發(fā)起，并且首次請求不附帶d(0)d(0)，若校驗塊的響應(yīng)明確表示需要d(0)d(0)，數(shù)據(jù)塊再將d(0)d(0)發(fā)送過去。通過這樣的設(shè)計，系統(tǒng)可以實現(xiàn)在大多數(shù)情況下不需要讀取并發(fā)送d(0)d(0)到校驗塊，此為投機(jī)成功;在少數(shù)情況下投機(jī)失敗，仍然需要讀取并發(fā)送d(0)d(0)給校驗塊，但投機(jī)失敗的代價僅僅是增加一次網(wǎng)絡(luò)交互延遲(大約0.1~0.2毫秒)，相對于機(jī)械硬盤的尋道延遲(平均幾毫秒)可以忽略不計，因而這幾乎是一個“穩(wěn)賺不賠”的優(yōu)化。

投機(jī)性部分寫：原理、設(shè)計與實現(xiàn)

考慮針對同一個數(shù)據(jù)條帶didi的一系列rr次寫操作d(1)i,d(2)i,⋯,d(r)idi(1),di(2),⋯,di(r)，校驗塊為pj(j=1,2,⋯,k)pj(j=1,2,⋯,k)，令 d(0)idi(0) 和 p(0)jpj(0) 分別表示 didi 和 pjpj 的原始值。根據(jù)增量編碼公式

Δpj=aij×ΔdiΔpj=aij×Δdi 

我們有 Δp(1)j=aij×Δd(1)i,Δp(2)j=aij×Δd(2)i,⋯,Δp(r)j=aij×Δd(r)iΔpj(1)=aij×Δdi(1),Δpj(2)=aij×Δdi(2),⋯,Δpj(r)=aij×Δdi(r)，因而可以得到

p(r)j=p(0)j+∑x=1rΔp(x)j=p(0)j+∑x=1raij(d(x)i−d(x−1)i)=p(0)j+aij×(d(r)i−d(0)i)pj(r)=pj(0)+∑x=1rΔpj(x)=pj(0)+∑x=1raij(di(x)−di(x−1))=pj(0)+aij×(di(r)−di(0)) 

根據(jù)這一公式，最終的校驗數(shù)據(jù) p(r)j(j=1,2,⋯,k)pj(r)(j=1,2,⋯,k) 只取決于p(0)jpj(0), d(0)idi(0) 和 d(r)idi(r)。這一結(jié)論允許我們不必每次計算校驗差值，而使用數(shù)據(jù)的最終值和原始值(即 d(r)d(r) 和 d(0)d(0)，省略下標(biāo))之間的差值來等價計算整個過程的校驗值增量。因而 d(0)d(0) 只需要讀取一次(在寫入 d(1)d(1) 的時候)。對于這一系列的rr次寫操作，投機(jī)只會在第一次失敗，在之后的r−1r−1次均成功，直到日志被合并進(jìn)入校驗數(shù)據(jù)塊或遇到全量寫操作。對于失敗的投機(jī)，校驗塊會返回一個特定的錯誤碼，以通知數(shù)據(jù)塊將d0d0發(fā)送過來，這僅僅帶來一次網(wǎng)絡(luò)RTT的額外開銷，大約0.1ms~0.2ms，相對于磁盤I/O時間來說可以忽略。

現(xiàn)實當(dāng)中的I/O負(fù)載也存在大塊順序的操作，這將產(chǎn)生整個EC組的全量寫操作。對于這種操作，我們將直接計算出校驗數(shù)據(jù)，并將其寫入校驗塊，同時在變更日志中記錄一個特殊操作I，表示將I之前的變更記錄取消掉，因為最新的數(shù)據(jù)已經(jīng)直接寫到校驗塊內(nèi)了。

根據(jù)上述原理，我們設(shè)計出如下圖所示的部分寫流程(以三個校驗塊為例)：

我們基于美團(tuán)云現(xiàn)有的分布式塊存儲系統(tǒng)(參見之前的博客文章“分布式塊存儲系統(tǒng)Ursa的設(shè)計與實現(xiàn)”)將這一設(shè)計實現(xiàn)出來，稱為PBS，提供強一致性保障。系統(tǒng)的寫操作流程整體如下圖所示(以兩個校驗塊為例)：

實驗

EC編解碼性能

我們針對EC(4,2)、EC(6,3)、EC(8,4)、EC(10,4)等多種配置測試了編解碼運算性能。如下圖所示，在SSE、AVX等向量運算指令集的幫助下，現(xiàn)代CPU的1個核心每秒就能完成5~13GB數(shù)據(jù)量的編解碼工作，遠(yuǎn)遠(yuǎn)大于同時期各種外部存儲設(shè)備的吞吐率，所以編解碼運算已不再成為EC存儲系統(tǒng)的瓶頸。測試中所用CPU型號為Xeon E5-2650v3 @ 2.3GHz，圖中encode表示編碼，decode 1和2分別表示解碼1個和2個數(shù)據(jù)塊。

PBS部分寫的性能

所有的測試均在虛擬機(jī)內(nèi)掛載PBS完成。我們的測試環(huán)境為3臺服務(wù)器，每臺配備10塊硬盤，7200RPM。測試了隨機(jī)寫IOPS，以及隨機(jī)寫的延遲，來衡量部分寫的性能，其中I/O大小為4KB，EC組的條帶大小為16KB。測試結(jié)果分別如下圖所示，其中HDD表示單塊7200RPM的物理硬盤的基準(zhǔn)性能，R3表示三副本模式，PBS-1和PBS-2分別表示PBS在投機(jī)失敗(首次寫)和投機(jī)成功(第二次及以后)的情況，EC表示增量編碼方法，EC-PLog表示前文所述的在FAST'14技術(shù)大會發(fā)表的工作，代表了已有方法中的最好結(jié)果。

從結(jié)果可以看出，各種情況下的讀性能大致相當(dāng)，PBS-1(投機(jī)失敗，小概率)比EC-PLog略低，PBS-2(投機(jī)成功，大概率)遠(yuǎn)遠(yuǎn)好于EC-PLog，甚至可以與三副本模式的性能相媲美。

故障恢復(fù)

我們在內(nèi)存中為日志建立了索引，因而在(故障恢復(fù)中)讀取日志時可以快速定位數(shù)據(jù)偏移。如下圖所示，測試結(jié)果表明日志大小對故障恢復(fù)速度的影響有限。