糾刪碼存儲(chǔ)系統(tǒng)中的投機(jī)性部分寫(xiě)技術(shù)

作者：佚名 2017-06-07 14:47:39

前言

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

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

[[193275]]

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

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

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

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

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

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

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

根據(jù)上述原理，我們?cè)O(shè)計(jì)出如下圖所示的部分寫(xiě)流程(以三個(gè)校驗(yàn)塊為例)：

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

實(shí)驗(yàn)

EC編解碼性能

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

PBS部分寫(xiě)的性能

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