一種適用于分布式存儲集群的糾刪碼數據更新方法

章紫琳 劉 鐸 譚玉娟 吳 宇 羅龍攀 王緯略 喬 磊

1(重慶大學計算機學院 重慶 400044) 2(北京控制工程研究所 北京 100080)

分布式存儲集群(如Azure[1]，HDFS(Hadoop distributed storage system)，Dynamo[2]等)多數采用大量的跨地域節點存儲海量數據并提供數據訪問服務.這些服務節點的失效率很高[3-4]，為了提供容錯能力，傳統的存儲集群普遍采用存儲開銷成倍增長的多副本技術。而糾刪碼在保證同等的容錯性能時，能盡可能減少存儲開銷[5-6]，因此目前大多數存儲集群結合糾刪碼來保證數據的可靠性及可用性[7-10].

然而數據更新時，結合糾刪碼的分布式存儲集群的磁盤I/O開銷至少是采用多副本技術的存儲集群的2倍.原因在于糾刪碼是將原始數據分塊得到數據塊，再對數據塊進行線性計算得到校驗塊.當數據塊更新時，校驗塊也需要重新編碼計算，這會導致額外的磁盤I/O開銷[11]，特別是更新數據塊的一小部分時，磁盤I/O開銷更高.而在真實工作負載下如MSR Cambridge traces[12]，所有更新請求的大小都小于512 KB，其中大部分軌跡(trace)超過60%的更新請求小于4 KB；在Harvard NFS traces[13]中，平均更新大小為10.58 KB，并且在所有寫請求中，超過91%的請求都是更新請求(除去第1次寫請求)[14].由此可見存儲集群的更新操作是頻繁的且小寫請求占大部分，因此降低糾刪碼數據更新的磁盤I/O開銷對分布式存儲集群寫性能的提升至關重要.

存儲集群中糾刪碼數據更新方式主要分為2種：即時更新和基于日志更新[15].前者指每次更新都會立即將新的數據寫入塊中，在更新密集的存儲集群中這種頻繁地寫磁盤會嚴重影響系統的性能；后者是將新的數據寫入日志中，當有需要或者系統空閑時進行日志重播.經典的分布式文件系統如GFS(Google file system)[16]就是采用基于日志的更新方式.這2種更新方式也可以結合，如在PL(parity logging)[17-18]更新方法中，數據塊是即時更新，校驗塊是基于日志更新.這樣既保證了數據塊實時更新的需求，又降低了頻繁寫校驗塊的磁盤I/O開銷.

然而，現有的基于日志的數據更新方法都沒有同時克服2個缺陷：1)每次更新時需要對數據塊執行讀后寫操作，例如PLR(parity logging with reserved space)[14]及FO(full overwrite)[19]策略，每次計算校驗增量時需要先讀取原始數據塊再寫入新的數據.經過在7 200 r/min的硬盤驅動器(hard disk drive, HDD)上的測試，這種讀后寫操作大約需要8.3 ms，是高于純寫的延時(由于更多的磁盤尋道)[20]，這導致PLR的隨機寫和順序寫的性能有時仍然低于傳統的PL策略.2)讀寫日志時需要額外的磁盤尋道開銷[21]，例如PARIX(speculative partial write)[20]策略，其在預測失敗的情況下，由于需要向日志寫入原始數據塊，額外的磁盤尋道開銷使得隨機I/O延時略高于傳統的PL策略.以上兩者是影響分布式存儲集群寫性能的重要因素，大多數基于日志的更新策略沒有同時兼顧這兩者的優化，導致其更新吞吐率遠不如副本.

因此，本文針對這個問題提出了PARD(parity logging with reserved space and data delta)數據更新方法，從減少讀后寫操作和磁盤尋道開銷2個方面來極大化糾刪碼存儲集群的數據更新性能.首先根據數據塊和校驗塊的訪問頻率不一樣，采用數據塊即時更新、校驗塊日志重播更新的方式；其次利用計算校驗塊的算術特性構建基于數據增量的日志，使得在多次更新中只有第1次更新需要讀取原始數據塊，后續的更新直接向數據節點寫入新的數據，避免每次更新都要讀取原始數據塊再寫入新的數據所帶來的讀后寫開銷；最后，在校驗數據末尾為日志預留空間，以此減少讀寫日志的磁盤尋道開銷.本文的貢獻有2個方面：

1) 提出PARD數據更新方法，采用基于數據增量的日志和預留空間的方式減少分布式存儲集群中糾刪碼數據更新時的磁盤I/O開銷.

2) 設計PARD實驗原型，用真實工作負載下的軌跡對PARD進行性能評估，并與多種最新的數據更新策略如PLR，PARIX，FO進行比較.

1 背景與相關工作

1.1 糾刪碼基本原理

糾刪碼首先將原始數據劃分成k個同等大小的數據塊，然后在有限域GF(2w)(一般w=8)內對數據塊進行編碼運算得到m個校驗塊.如圖1所示，以經典的RS(Reed-Solomon)(k+m,k)[22-23]糾刪碼為例描述糾刪碼編碼的基本原理.RS(6,4)將原始數據劃分成4個數據塊Dj,j=1,2,3,4，編碼得到的校驗塊為Pi,i=1,2，eij為Pi在生成矩陣中對應Dj的編碼系數，為1個常量.由此可見，每個校驗塊都是數據塊線性運算的結果，且涉及的運算一般是有限域的加法和乘法[24].

Fig. 1 Basic principle of erasure coding encoding圖1 糾刪碼編碼基本原理

(1)

(2)

(3)

基本的FO[19]策略即采用式(2)實現數據更新，更新流程示例如圖2所示.假設每個節點均保存4個塊，編碼塊間的運算為ai+bi=c1i,ai-bi=c2i，其中i=1,2,3,4.第t+1次更新數據塊b3的一部分時，首先需要讀取原始數據塊來計算校驗增量，再寫入新的數據塊；每更新1個校驗塊，校驗節點需要先讀取原始校驗塊，將其和接收的校驗增量執行異或運算獲得新的校驗塊，再寫入指定偏移處.整個過程總共4次磁盤訪問.

Fig. 2 Data update process in erasure coding with RS(4,2)圖2 以RS(4,2)為例的糾刪碼數據更新流程

為了減少磁盤訪問，目前的數據更新策略都會利用糾刪碼線性運算的特性.如傳統的PL策略利用式(2)構建基于校驗增量的日志進行數據更新，將對校驗塊的隨機寫轉換為對日志的順序寫[17-18].即每次更新都會將此次更新的校驗增量追加寫入日志中，日志滿時再將原始校驗塊和日志中的增量進行線性運算得到最新的校驗塊，避免頻繁地讀寫校驗塊.本文也會圍繞這個特性來進一步優化數據更新性能.

1.2 相關工作

1.2.1 磁盤陣列系統中的數據更新策略

磁盤陣列系統的數據更新策略主要分為滿條帶寫(full-stripes writes)、重構寫(reconstruct writes, RCW)、讀修改寫(read-modify writes, RMW).假設1個條帶分為k個數據塊和m個校驗塊，滿條帶寫[25]指的是對整條條帶進行更新，適用于更新所有數據塊的情況.滿條帶寫將新的數據塊編碼得到新的校驗塊，不需要額外地讀寫數據塊或者校驗塊，性能達到最優.RCW[26]適用于更新i(0

為了降低小寫懲罰，LSA(log-structured arrays)采取的策略是將多個小更新緩存到DAC cache中[28]，最后聚合到一起進行滿條帶更新.Fu等人[29]構造出Short Code編碼方式，通過在磁盤陣列中添加對角校驗元素來減少更新時的磁盤I/O.與Fu等人不同的是，Wu等人[30]提出一種基于異或運算的混合碼(hybrid code, H-Code)，將反對角校驗元素分布在磁盤陣列中，實現了更加均衡的I/O分布，并保證任意2個連續的數據元素能夠和同一個校驗元素相關聯.Shen等人[31]將共享校驗元素的思想延伸到采用任意一種異或糾刪碼的磁盤陣列中，通過PDP(parity-switched data placement)數據布局算法來保證任意2個連續的數據元素在同一個校驗鏈中.Du等人[32]則根據小寫I/O的分布特征來調整數據塊的存儲位置，通過校驗共享來最小化寫校驗塊數目，并在這個階段將待遷移的數據塊和即將到來的寫請求進行聚合.文獻[28-32]都是將同一個校驗鏈的多個小寫請求聚合成1個大寫請求，從而減少寫校驗塊的磁盤I/O.而DCD(disk cache disk)[33]結合智能緩存的思想達到寫聚合，降低了磁盤讀寫I/O，提升小寫性能.對于基于固態硬盤的磁盤陣列，Wu等人[34]將小寫請求緩存在作為鏡像緩存區的日志磁盤中，再將他們合并成對固態硬盤的大寫請求.

文獻[28-34]的更新策略均是采用寫聚合的思想來降低小寫懲罰.針對于內存存儲，Huang等人[35]則根據分組的思想提出GU(grouped-updating)更新機制，思想是在內存中將更新請求分組，1個組中的多個小更新可以并發執行，從而降低更新延時.

然而運用在磁盤陣列系統上的數據更新策略都有一定的局限性，如日志文件系統(log-structured file system, LFS)[15]中的滿條帶寫將每個磁盤看作可追加的日志，每次更新都將新的數據附在末尾，使得檢索更新時需要額外的磁盤尋道開銷[21].而RMW和RCW是針對單機設計的更新策略，在數據塊和校驗塊分布在跨地域機器的分布式環境下，RMW和RCW的性能顯著降低[36].其他的策略也是針對磁盤陣列所設計的，不能很好地適應分布式環境.

1.2.2 分布式環境中的數據更新策略

為了適應存儲集群的分布式環境，目前有許多基于校驗增量的數據更新方法，如FO，FL(full logging)，PL等，這些更新方法都利用了糾刪碼線性運算的特性.每次更新時，數據節點會讀取被修改范圍的原始數據并將原始數據和新的數據進行線性運算得出校驗增量；然后數據節點再在指定偏移處寫入新的數據并將校驗增量發送給校驗節點；校驗節點接收到數據節點傳輸的校驗增量后，根據具體的更新策略進行即時更新或將其寫入日志中.

FO[19]是最簡單易實現的基于校驗增量的數據更新策略，數據塊和校驗塊均采用即時更新.任意時刻，數據塊和校驗塊的版本都是最新的，保證了數據的一致性.然而頻繁地讀寫磁盤導致更新性能低下，類似于磁盤陣列系統中的RMW策略[26]，存在小寫懲罰的問題.

而FL[1,16]通過日志的方式將大量對數據塊的隨機小寫操作轉換為對日志的順序寫操作，避免了頻繁的磁盤尋道，從而降低了寫時的磁盤I/O開銷.但是在真實情況下，數據塊是熱數據，訪問頻率很高.每次讀數據塊FL都需要重播日志得到最新的數據，即將隨機分布在日志中的所有更新數據讀出來和數據塊進行合并[37]，這仍然需要頻繁的讀寫操作，會嚴重滯后讀取性能.

鑒于FO中的小寫懲罰問題及FL只適用于讀寫冷數據的問題，Stodolsky等人[18]提出只包含校驗增量日志的PL更新策略.PL結合了FO和FL的思想，采用數據塊即時更新、校驗塊基于日志更新的方式.既減少了寫操作時讀寫校驗塊的磁盤I/O開銷，又提升了后續讀數據塊的性能，但是合并日志中的校驗增量時仍然需要額外的磁盤尋道開銷.為了解決這一問題，PLR[14]在每個校驗塊末尾預留空間(默認為塊大小)作為日志用途，使得校驗塊和日志中的校驗增量可以被順序檢索.

FO,FL,PL和PLR的數據更新策略均是基于校驗增量.每次更新時，為了得到校驗增量，數據節點均需要讀取原始數據再寫入新的數據，頻繁的讀后寫操作嚴重滯后了存儲集群的更新性能.為了減少讀后寫操作，近幾年提出的PARIX[20]采用基于數據增量的更新方式.在連續多次更新中，數據節點只在第1次更新時有讀后寫操作，后續只寫入新的數據.在日志重播時，校驗節點利用日志中的數據增量即可獲得最新的校驗塊.

FO,FL,PL,PLR和PARIX策略均是對磁盤I/O的優化，而針對跨機架環境，小寫操作的網絡傳輸開銷也是影響更新性能的重要因素.針對這一問題，Zhang等人[38]提出PUM-P和PDN-P更新策略.PUM-P是將計算增量的任務交給管理節點，管理節點再將校驗增量傳輸給每個校驗節點，減少了讀取原始校驗塊的網絡傳輸開銷；PDN-P是將計算增量的任務交給數據節點，數據節點再向校驗節點發送計算結果，減少了讀取原始數據塊的網絡傳輸開銷.然而PUM-P和PDN-P更新策略采用的是星型數據傳輸結構，沒有充分利用各節點間的帶寬，發送校驗增量的節點甚至會成為網絡瓶頸，導致網絡擁塞情況的出現.T-Update[39]和TA-Update[40]利用自頂向下的樹型傳輸結構，充分利用各節點間的帶寬資源來傳輸增量，消除了星型結構的網絡瓶頸問題.

然而PUM-P,PDN-P,T-Update,TA-Update策略只適用于單節點更新，而對于多節點小寫更新，CASO(correlation-aware stripe organization)[41]根據更新數據的相關性來組織條帶，將關聯的數據放在1個條帶內，減少小寫更新時數據節點和校驗節點間的網絡傳輸.CAU(cross-rack-aware updates)[42]則借鑒PARIX的思想來降低數據節點和校驗節點間的網絡傳輸，在多次更新中，數據節點根據原始數據和最新的數據計算出增量，并向每個校驗節點傳輸1次數據增量.

Fig. 3 Update throughput when using four update strategies to replay traces圖3 在4種更新策略下重播軌跡的更新吞吐率

1.3 問題描述與研究動機

為了探索影響分布式存儲集群的糾刪碼數據更新性能的主要因素，本文在6臺機器上對FO,PL,PLR和PARIX策略進行了更新性能對比實驗(在多數情況下，數據塊的訪問頻率很高，目前普遍采用PL策略而不是FL策略，所以此處不與FL策略比較).圖3是在RS(4,2)的配置下，采用不同更新策略重播4個軌跡wdev_1，wdev_3，rsrch_1，src2_1的更新吞吐率.實驗結果表明，FO的更新性能是最差的，這也和之前的分析相符；PARIX和PLR實現了最高的更新吞吐率，說明磁盤尋道和讀后寫操作是影響分布式存儲集群更新性能的主要因素.

為了更直觀地驗證圖3的結論，本文利用filefrag-v命令記錄了在不同的更新策略下重播每個軌跡后所有數據文件和日志文件的磁盤碎片數(碎片數目高表示磁盤尋道開銷大).由于4個軌跡的大致規律相同，本文只展示重播rsrch_1的碎片數目以及讀后寫操作數目，如表1所示.實驗結果表明，和FO相較，PARIX有少量的碎片但是讀后寫操作數目最少，實現了最優的更新性能；而PLR雖然沒有碎片，但是讀后寫操作數目的減少比例沒有PARIX高，更新性能和PARIX近似；此外，PLR在PL的基礎上采用預留空間的方式降低磁盤尋道開銷從而提升了更新性能.以上結論再次驗證了磁盤尋道和讀后寫操作是影響存儲集群更新性能的主要因素.

Table 1 Numbers of Fragments and Write-After-Read When Replaying rsrch_1

綜上所述，PLR和PARIX是目前最優的更新策略.但是PLR仍然需要額外地讀取原始數據塊，再寫入新的數據，大量的讀后寫操作降低了更新吞吐率.而PARIX也有少量的碎片，導致合并日志時需要額外的磁盤尋道開銷，對更新性能有一定的影響.因此，為了更進一步地提升糾刪碼存儲集群的數據更新性能，本文將這2種策略進行結合，從減少數據更新時的讀后寫操作和讀寫日志時的磁盤尋道開銷2方面來優化數據更新性能.

2 PARD介紹

本文提出一種新型的適用于大規模分布式存儲集群的糾刪碼數據更新方法，目的在于減少數據更新路徑上的讀后寫操作和進一步更新校驗塊的磁盤尋道開銷.本文的PARD方法主要從2方面來提升更新性能：

1) 構建基于數據增量的日志.利用糾刪碼計算的線性特性構建基于數據增量的日志，使得每次更新數據塊時只需要寫數據節點(除了第1次更新需要讀取原始數據塊并寫入新的數據)，減少傳統的FO，PLR等更新策略中對數據塊的讀后寫操作.

2) 在校驗塊末尾為日志預留空間(默認為塊大小).將數據節點傳輸的原始數據和新的數據順序寫入預留的日志空間中，使得日志重播時校驗塊和日志中的數據增量能被順序檢索，從而降低磁盤尋道開銷.

2.1 基于數據增量的日志

正如1.2節所述，基于校驗增量的更新策略的日志是存儲如式(3)的校驗增量，這種策略的弊端在于頻繁的讀后寫操作.因為獲得校驗增量需要先從數據節點讀取原始數據塊，計算得到校驗增量后再寫入新的數據.針對這一問題，本文將采用基于數據增量的日志來盡量避免讀取原始數據塊的操作，實現純寫.

(4)

正如圖4所示(為了簡潔，圖4中省略了下標p)，根據基于校驗增量的日志進行數據更新的策略每次更新都需要從數據節點讀取當前的原始數據塊，再寫入新的數據，最后將校驗增量寫入校驗節點的日志中；而根據基于數據增量的日志進行校驗更新的策略只有在第1次更新時需讀取原始數據塊，后續的更新只需對數據節點執行純寫.最終，日志中存放的數據是D(0),D(1),….觸發日志合并的條件可設為更新數據大小或更新條帶數達到閾值，校驗節點合并完日志獲得最新的校驗塊后會清空日志中的數據.下次更新時，校驗節點又向數據節點發送1個請求當前原始數據塊D′(0)(此時數據塊已發生變化，記為D′)的標志位，并將新的增量寫入日志.

Fig. 4 Comparison between log based on parity delta and log based on data delta圖4 基于校驗增量的日志和基于數據增量的日志的區別

綜上所述，基于數據增量的日志相較基于校驗增量的日志顯著減少了讀后寫操作.唯一的開銷是第1次更新或者合并完日志后，數據節點需要向校驗節點傳輸原始數據塊.這需要1段額外的網絡往返時延(round-trip time,RTT)，RTT的取值范圍是0.1～0.2 ms[20]，在現代的網絡環境下這是微不足道的開銷，不會影響本文方法的更新性能.

2.2 預留空間

1.2節中的FL，PL，PARIX更新策略的日志文件和存放編碼塊的數據文件是不同的，即兩者在磁盤存放的物理位置不連續.合并日志時，校驗節點需要讀取隨機分布在日志文件中的所有增量并將其和數據文件進行合并，這引入了額外的磁盤尋道開銷.針對這一問題，本文采用為日志預留空間的策略，使增量和校驗塊可以被順序檢索，從而降低磁盤尋道時間.

本文將采用預留空間的PARD方法和最基本的數據更新策略(FO)、最新的數據更新策略(PLR，PARIX)進行了示例對比，如圖5所示.以RS(3,2)為例，假設數據節點1和數據節點2均保存2個數據塊，且均有1處數據更新，分別在第1個數據塊和第2個數據塊.

FO策略是在指定偏移處即時更新數據塊和校驗塊，保證了數據塊和校驗塊的實時一致性.但是每次更新都需讀寫原始數據塊、原始校驗塊，磁盤I/O開銷是副本的4倍.對于磁盤I/O是性能瓶頸的糾刪碼存儲集群，采用FO數據更新策略會嚴重影響系統的讀寫性能.

PLR策略和FO的不同之處在于PLR是將大量對校驗塊的小寫操作轉換為對日志的順序寫操作.每次更新時PLR會將此次更新的校驗增量寫入日志，等到日志滿時再將其和數據文件進行合并獲取最新的校驗塊.由此對同一校驗塊的更新可批量處理，降低了數據更新時讀寫校驗塊的磁盤I/O開銷.此外，PLR采用在校驗數據末尾為日志預留空間的方式減少了校驗節點合并日志的磁盤尋道開銷.

Fig. 5 Comparison of update illustrations between PARD and other data update strategies圖5 PARD方法和其他數據更新策略的更新示例對比

Fig. 6 Architecture of PARD with RS(4,2)圖6 以RS(4,2)為例的PARD體系架構

PARIX策略和FO策略、PLR策略的區別在于每次更新寫入日志的是數據增量而不是校驗增量，正如2.1節所述，這從根本上減少了對數據塊的讀后寫操作.但是由于沒有給日志預留空間，合并日志時仍然需要額外的磁盤尋道開銷.

本文的PARD方法采用基于數據增量的日志和在校驗數據末尾為日志預留空間的方式，減少了更新路徑上的讀后寫操作以及后續更新校驗塊時合并日志的磁盤尋道開銷，極大限度地提升了存儲集群的糾刪碼數據更新性能.

2.3 體系架構

采用PARD方法進行數據更新的體系架構如圖6所示.客戶端負責向整個集群發起寫請求.元數據服務器根據數據塊號計算其對應的條帶號，并將其存放的數據節點、相應的校驗塊存放的校驗節點的位置信息及存放的具體偏移保存在元數據信息中.數據節點保存數據塊，校驗節點保存校驗塊，并將數據節點傳輸的增量寫入預留的日志空間內.校驗節點記錄了3類元數據用于合并日志：記錄更新條帶號和更新條帶數目的更新條帶元數據；記錄增量在預留空間的偏移和長度的增量元數據；記錄原始數據塊在預留空間的偏移和長度的原始數據塊元數據.

1次更新請求的執行流程包括6個步驟.

1) 客戶端將對指定數據塊的寫請求發送給元數據服務器.

2) 元數據服務器根據數據塊號返回其所在的位置信息，以及對應的校驗塊的位置信息.

3) 客戶端根據這些元數據向對應的數據節點發起更新請求，并向數據節點轉發新的數據及其在數據塊中偏移和長度等信息.

4) 數據節點將新的數據寫入指定的偏移處，并將數據增量及更新范圍等信息轉發給對應的校驗節點.

5) 校驗節點接收到數據增量后，主要執行3個步驟：

① 判斷當前是否需要合并日志.本文默認更新數據量達到預留空間的大小即預留空間滿時合并日志.校驗節點根據本地管理的更新條帶元數據、增量元數據、原始數據塊元數據進行逐條帶校驗更新，合并完日志后，以上元數據都將恢復成初始狀態.

② 將新的數據以追加的方式寫入本地預留的日志空間中，并且將數據節點傳輸的更新條帶號、數據塊號、更新范圍等分別記錄在更新條帶元數據和增量元數據中.

③ 根據原始數據塊元數據判斷待更新的數據所在的原始數據塊是否已讀取.如果沒有則向數據節點發送需要原始數據塊的標志位.數據節點偵聽到標志位后，將整個塊讀取出來并傳輸給校驗節點.校驗節點再將原始數據塊寫入日志中并更新原始數據塊元數據.

6) 校驗節點向數據節點上報更新完成的答復信息，數據節點再向客戶端發送確認.需要說明的是，為了模擬數據，本文在數據節點采用fallocate命令產生了60 GB的數據文件，在校驗節點采用fallocate命令產生總大小為60 GB+預留空間的數據文件.本文的預留空間默認為塊大小即4 MB，所以PARD方法的預留空間開銷和數據文件相較忽略不計.在校驗節點中，數據增量包含2種數據：新的數據和原始數據塊.為了區分兩者，本文將新的數據存放在數據文件預留的日志空間內，原始數據塊存放在另一個預留的日志空間內.

3 實驗與分析

本節實驗在18臺虛擬機上進行，每臺機器運行Ubuntu 20.04.1 LTS，配有2.40 GHz的Xeon Silver 4210R CPU，125 GB內存，7 200r/min的硬盤(1T B).首先，本節基于2.3節的體系架構設計了PARD實驗原型，并實現了PARD，PLR，PARIX及基本的FO策略；然后在商業界普遍采用的2種編碼配置即RS(9,6)和RS(16,12)下對實驗采用的軌跡進行分析，主要研究真實工作負載下寫請求的規律；最后分析編碼配置、軌跡的更新密集度、塊大小對PARD的更新吞吐率、每秒完成的寫操作數、讀后寫操作數的影響，并與基本的FO更新策略及最新的PLR，PARIX更新策略比較.

3.1 軌跡分析

為了模擬真實負載環境下的數據更新，實驗采用Microsoft Research Cambridge發布的塊級磁盤I/O軌跡[12]來測試更新策略的性能.該軌跡集記錄了1周內，外部對存儲集群中36個卷的I/O請求.每個軌跡包含時間戳、主機名、磁盤號、讀寫類型、寫偏移、寫大小及響應時間.為了反映不同軌跡的更新密集度，本文定義1個稱為寫局部性的變量，并且將1個軌跡的寫請求劃分為n個工作集，每個工作集包含a個連續寫請求.假設每個工作集對應的更新條帶數為si(1≤i≤n)，則寫局部性可表示為

(5)

?越大，代表該軌跡的寫局部性越高即更新密集度越高.

默認塊大小為4 MB，a=500，本文在RS(9,6)和RS(16,12)兩種配置下測量軌跡的寫局部性.為了限制后續測試更新性能的實驗周期，本文選取了5個寫局部性最高的和5個寫局部性最低的軌跡，如表2所示.寫操作數目指該軌跡中寫請求的數目，總操作數目指所有讀寫請求數目，寫操作數目占比指寫請求在所有請求中的占比.它們的寫操作數目在600～2 000 000之間并且涵蓋了多種工作負載類型，表明PARD方法不局限于特定工作負載下的糾刪碼數據更新.表2中所有軌跡的平均寫大小均小于21 KB，說明大部分寫請求都是小寫.其中web_3的寫局部性最高，RS(9,6)配置下每500個寫請求平均有3.8(a/?=3.8)個條帶更新.而對于寫局部性最低的stg_1，每500個寫請求平均覆蓋71.1個條帶，更新范圍最廣.此外，RS(16,12)配置下的寫局部性比RS(9,6)的大，原因是數據塊增多，1個條帶的數據范圍更廣.

3.2 性能評估

本節首先將軌跡的寫偏移及寫大小按照4 MB劃分，為了和軌跡中最大的寫偏移對應，實驗采用fallocate命令在每個數據節點上產生60 GB的數據文件，由此，客戶端順序重播軌跡中的寫請求時，每個寫請求都會作為更新請求處理并觸發校驗更新.每個校驗節點也采用fallocate命令產生總大小為60 GB+預留空間(默認為塊大小即4 MB)的數據文件，校驗更新時根據所采用的更新策略將增量寫入相應的文件或即時更新.實驗默認當更新數據量達到預留空間的大小時觸發合并日志操作，并在合并完成時將日志格式化回到初始狀態.在每次重播前，為了保證數據更新性能只受更新策略的影響，每個校驗節點上的日志文件也會清空.

Table 2 Analysis for 10 Traces表2 對10個軌跡的分析

3.2.1 RS(9,6)下更新密集度實驗

圖7是在RS(9,6)下，重播不同寫局部性的軌跡時，不同更新策略的平均更新時間開銷比較，平均更新時間指總更新時間除以更新操作數.圖7表明在所有的軌跡中，PARD實現了最低的平均更新時間開銷，相較于FO，PARIX，PLR分別平均減少了46.8%，38.3%，34.3%.當重播寫局部性高的軌跡時PARD的優化效果更顯著.例如當重播wdev_1時，PARD的平均更新時間開銷相較于FO，PARIX，PLR分別減少了61.5%，48.1%，46.8%；而對于stg_0，PARD相較于FO，PARIX，PLR分別減少了49.5%，38.0%，30.7%.

Fig. 7 Average update time when replaying traces with RS(9,6)圖7 RS(9,6)下重播不同軌跡的平均更新時間開銷

在圖7(a)中，FO的平均更新時間穩定在0.040 s左右；PARIX，PLR的平均更新時間都穩定在0.029 s左右，兩者更新時間開銷差距不大，這是因為PLR采用預留空間的技術減少了磁盤尋道開銷，但是讀后寫操作數目的減少比例沒有PARIX高，平均更新時間開銷和PARIX近似；PARD的平均更新時間穩定在0.017 s左右.在圖7(b)中，FO的平均更新時間仍然穩定在0.040 s左右；PARIX，PLR的平均更新時間都穩定在0.032 s左右；PARD的平均更新時間穩定在0.022 s左右.對于PARIX，PLR，PARD，圖7(a)中的平均更新時間開銷的穩定值低于圖7(b)的平均更新時間開銷的穩定值，這是因為重播寫局部性高的軌跡時，更多的寫請求可以被批量處理，讀取原始數據塊或校驗塊的磁盤I/O數降低，導致更新時間降低.

圖8是在RS(9,6)下，重播不同寫局部性的軌跡時，不同更新策略的更新吞吐率比較.圖8表明在所有軌跡中，PARD達到了最高的更新吞吐率，相較于FO，PARIX，PLR分別平均提升了112%，63.3%，54.8%.當重播寫局部性高的軌跡時PARD的優化效果更顯著.例如當重播wdev_1時，PARD相較于FO，PARIX，PLR分別提升了160%，92.6%，87.9%；而對于stg_0，PARD相較于FO，PARIX，PLR分別提升了97.9%，61.2%，44.3%.這是因為當客戶端對同一條帶發起連續多個更新請求時，每個數據節點只需要向校驗節點發送1次原始數據塊；而對于寫局部性低的軌跡，客戶端每次都向不同的條帶發起更新請求.數據節點向校驗節點傳輸原始數據次數增加，導致性能優化比例降低，但是PARD仍然顯著提升了更新性能.

Fig. 8 Update throughput when replaying traces with RS(9,6)圖8 RS(9,6)下重播不同軌跡的更新吞吐率

圖9是重播不同寫局部性的軌跡時，不同更新策略每秒完成的寫操作數的比較.從總體來看，重播不同軌跡時FO和PLR的每秒寫操作總數波動較小.而圖9(a)中PARIX和PARD的每秒寫操作總數略高于圖9(b)，提升比例分別為17.0%和33.0%.原因在于重播寫局部性高的軌跡時，對同一條帶的連續多個寫請求可被批量處理，使得日志重播時只需要讀取1次原始數據塊和校驗塊；而寫局部性低的軌跡的寫請求對應多個不同的條帶，校驗更新時需要讀取多次數據塊和校驗塊，I/O開銷增大.重播寫局部性高的軌跡時，PARD相較于其他策略平均提升了73.1%～141%；而重播寫局部性低的軌跡時，PARD平均提升了36.4%～82.0%.

Fig. 9 Aggregate numbers of write completed per second when replaying traces with RS(9,6)圖9 RS(9,6)下重播不同軌跡的每秒寫操作總數

3.2.2 RS(16,12)下更新密集度實驗

圖10是在RS(16,12)下，重播不同寫局部性的軌跡時，不同更新策略的平均更新時間開銷的比較.和RS(9,6)相較，RS(16,12)下PARD的優化效果更顯著.在所有軌跡中，PARD的更新時間開銷相較于FO，PARIX，PLR分別平均減少了47.9%，41.2%，36.3%.這是由于RS(16,12)的數據塊增多，幾乎所有軌跡的寫局部性都得到提升(如表2所示)，更多的寫請求可以被批量處理導致RS(16,12)下PARD的優化效果更顯著.

和RS(9,6)相較，重播相同的軌跡時，RS(16,12)下每種策略的平均更新時間開銷增加.例如，在圖10(a)中，FO的平均更新時間穩定在0.044 s左右；PARIX，PLR的平均更新時間都穩定在0.032 s左右；PARD的平均更新時間穩定在0.018 s左右.而在圖7(a)中，FO的平均更新時間穩定在0.040 s左右；PARIX，PLR的平均更新時間都穩定在0.029 s左右；PARD的平均更新時間穩定在0.017 s左右.這是因為RS(16,12)下需更新的校驗塊增多，磁盤I/O開銷增加，導致平均更新時間增加.

其他的大致規律和RS(9,6)下的相同，如重播寫局部性高的軌跡時PARD相較于其他策略的減少比例更高.例如當重播wdev_1時，PARD的平均更新時間開銷相較于FO，PARIX，PLR分別減少了65.0%，52.7%，52.5%；而對于stg_0，PARD相較于FO，PARIX，PLR分別減少了49.5%，40.4%，31.8%.

此外，對于PARIX，PLR，PARD，圖10(a)中的平均更新時間開銷低于圖10(b)，而FO的大致相同.

圖11是在RS(16,12)下，4種更新策略重播不同軌跡的更新吞吐率的比較.和RS(9,6)相較，RS(16,12)下PARD的優化效果更顯著，其更新吞吐率相較于FO，PARIX，PLR分別平均提升了118%，72.8%，60.6%.這也是由于RS(16,12)的配置下，所有軌跡的寫局部性都得到提升(如表2所示)，更多的寫請求可以被批量處理導致RS(16,12)下PARD的優化效果更顯著.當重播寫局部性高的軌跡時，PARD相較于其他策略的提升比例更高.例如當重播wdev_1時，PARD相較于FO，PARIX，PLR分別提升了186%，111%，111%；而對于stg_0，PARD相較于FO，PARIX，PLR分別提升了98.1%，67.7%，46.7%.

Fig. 11 Update throughput when replaying traces with RS(16,12)圖11 RS(16,12)下重播不同軌跡的更新吞吐率

圖12是在RS(16,12)下，重播不同寫局部性的軌跡時，不同更新策略每秒完成的寫操作數的比較.大致規律和RS(9,6)下相似，唯一不同在于RS(16,12)下PARD的每秒寫操作總數相較于其他策略提升比例增加.重播寫局部性高的軌跡時，PARD相較于其他策略平均提升了81.3%～148%；而重播寫局部性低的軌跡時，PARD相較于其他策略平均提升了40.0%～87.7%.

Fig. 12 Aggregate numbers of write completed per second when replaying traces with RS(16,12)圖12 RS(16,12)下重播不同軌跡的每秒寫操作總數

3.2.3 塊大小對讀后寫操作的影響

本文在3.2.1節和3.2.2節的實驗均是在4 MB塊大小下進行測試的.為了研究塊大小對PARD優化效果的影響，本節測試了0.25～4 MB塊大小下PARD相較于PLR，PARIX，Baseline(FO)的讀后寫操作數減少比例.為了對比不同更新密集度的軌跡對塊大小的敏感度，本文選取了更新密集度高的wdev_1和更新密集度低的rsrch_1進行測試，編碼配置為RS(16,12).

圖13和圖14為PARD相較于其他策略的讀后寫操作減少比例.首先，PARD相較PLR和Baseline的減少比例隨著塊大小的增加而增大.對于wdev_1，其減少比例最高分別為99.0%和99.8%；而對于rsrch_1，其減少比例最高分別為87.0%和97.4%.由于PARIX也是采用基于數據增量的日志進行校驗更新，故讀后寫操作和PARD一樣，對應的優化比例為0.但是PARD采用了預留空間的技術，故更新吞吐率比PARIX高，具體如圖15和圖16所示.由于PARD對塊進行第1次更新時需要1次讀后寫操作，所以當重播寫請求較為分散的rsrch_1時，PARD的讀后寫操作相較于重播wdev_1時增加.因此，在相同的塊大小下，圖14中PARD相較PLR和Baseline的讀后寫操作減少比例低于圖11.此外，rsrch_1對塊大小更敏感，減少比例的增長速度高于wdev_1.

Fig. 13 Reduction proportion of write-after-read when replaying wdev_1 with different chunk sizes圖13 不同塊大小下重播wdev_1的讀后寫操作減少比例

Fig. 14 Reduction proportion of write-after-read when replaying rsrch_1 with different chunk sizes圖14 不同塊大小下重播rsrch_1的讀后寫操作減少比例

3.2.4 塊大小對更新吞吐率的影響

PARD相較于其他策略的更新吞吐率優化比例如圖15和圖16所示.總體來看，對于2種更新密集度的軌跡，PARD相較于其他策略的更新吞吐率優化比例均隨著塊大小的增加而增大.圖15中，PARD相較于PLR，PARIX，Baseline的優化比例最高分別達110%，110%，186%.圖16中，PARD相較于PLR，PARIX，Baseline的優化比例最高分別達41.1%，64.2%，87.1%.和3.2.2節的實驗一樣，在相同的塊大小下，圖15的更新吞吐率優化比例高于圖16.兩者對塊大小的敏感度趨勢大致相似，唯一明顯的不同在于塊大小為1～4 MB時，圖16中PARD-Baseline的增長速度低于圖15的.此外，重播wdev_1時PARD相較PLR的優化比例略高于相較PARIX的優化比例，而重播rsrch_1時相反.這是由于重播更新密集度高的軌跡時，對1個塊的連續寫請求PARD只需要1次讀后寫操作，而PLR每次更新均需要1次讀后寫操作.對于寫請求分布在不同條帶上的rsrch_1，PARD相較于PLR的讀后寫操作減少比例降低，且數據節點和校驗節點間傳輸原始數據塊的次數增加，導致PARD相較于PLR的更新吞吐率優化效果降低.

Fig. 15 Optimization proportion of update throughputwhen replaying wdev_1 with different chunk sizes圖15 不同塊大小下重播wdev_1的更新吞吐率優化比例

Fig. 16 Optimization proportion of update throughputwhen replaying rsrch_1 with different chunk sizes圖16 不同塊大小下重播rsrch_1的更新吞吐率優化比例

3.2.5 RS(9,6)下的整體性能

本節在3.2.1節和3.2.4節的實驗已經驗證PARD在更新性能方面優于其他對比策略，為測試PARD在整體性能上的優化效果，本節從表2中選取6個寫操作數目占比最低的軌跡進行實驗，其中web_3，hm_1，web_1的寫局部性高于proj_4，src2_1，stg_1.選取寫操作數目占比低的軌跡進行實驗的原因在于占比越高，整體性能的優化效果越接近更新性能的優化效果，為了降低更新性能對整體性能的影響，本節選取寫操作數目占比最低的6個軌跡進行實驗.

圖17是在RS(9,6)下，重播不同寫局部性的軌跡時，不同更新策略的讀寫吞吐率比較.從總體來看，PARD的讀寫吞吐率相較于FO，PARIX，PLR分別平均提升了50.5%，26.3%，24.8%.重播寫操作數目占比高的軌跡時，PARD的優化效果更顯著.例如當重播web_3時，其相較于FO，PARIX，PLR分別提升了120%，59.0%，63.8%；而對于寫操作數目占比最低的proj_4，其相較于FO，PARIX，PLR分別提升了7.1%，4.6%，1.9%.原因主要在于PARD降低更新操作的時間開銷，不同策略間讀操作的時間開銷大致相同，當寫操作數目占比低時，PARD對整體性能的優化效果降低，但是盡管是寫操作數目占比只有1.48%的proj_4，PARD仍然達到了最高的讀寫吞吐率.

Fig. 17 Read-write throughput when replaying traces with RS(9,6)圖17 RS(9,6)下重播不同軌跡的讀寫吞吐率

圖18是在RS(9,6)下，重播不同寫局部性的軌跡時，不同更新策略每秒完成的讀寫操作數比較.從總體來看，由于讀操作的時間開銷遠低于寫操作的時間開銷，當讀請求占多數時，整體的IOPS會增加.即重播寫操作數目占比低的軌跡時，每秒讀寫操作數更高.當重播寫操作數目為占比最低的proj_4時，FO，PARIX，PLR，PARD的每秒讀寫操作數最高，分別為226，231，237，242個.重播寫操作數目占比高的軌跡時，PARD的每秒讀寫操作數相較于其他策略的提升比例增加，提升比例和圖17一樣，主要是因為PARD降低更新操作的時間開銷，當寫操作數目占比高時，PARD對整體性能的優化效果增加.

Fig. 18 Aggregate numbers of read and write completed per second when replaying traces with RS(9,6)圖18 RS(9,6)下重播不同軌跡的每秒讀寫操作總數

3.2.6 RS(16,12)下的整體性能

圖19是在RS(16,12)下，4種更新策略重播不同軌跡的讀寫吞吐率比較.和RS(9,6)相較，RS(16,12)下PARD的優化效果更顯著，其讀寫吞吐率相較于FO，PARIX，PLR分別平均提升了59.2%，29.7%，29.9%.這是由于RS(16,12)下軌跡的寫局部性提高，更多的寫請求可以被批量處理導致RS(16,12)下PARD的優化效果更顯著.重播寫操作數目占比高的軌跡時，PARD的優化效果更顯著.例如當重播web_3時，其相較于FO，PARIX，PLR分別提升了140%，66.3%，74.7%；而對于寫操作數目占比最低的proj_4，其相較于FO，PARIX，PLR分別提升了7.4%，5.6%，2.1%.

Fig. 19 Read-write throughput when replaying traces with RS(16,12)圖19 RS(16,12)下重播不同軌跡的讀寫吞吐率

圖20是在RS(16,12)下，重播不同寫局部性的軌跡時，不同更新策略每秒完成的讀寫操作數比較.大致規律和RS(9,6)下相似，唯一不同在于RS(16,12)下PARD的每秒完成的讀寫操作數相較于其他策略提升比例增加.RS(9,6)下PARD相較于FO,PARIX,PLR分別平均提升了50.5%，26.3%，24.8%；RS(16,12)下PARD相較于FO,PARIX,PLR分別平均提升了59.2%，29.7%，29.9%.

Fig. 20 Aggregate numbers of read and write completedper second when replaying traces with RS(16,12)圖20 RS(16,12)下重播不同軌跡的每秒讀寫操作總數

4 結 論

相較于傳統的基于校驗增量和基于數據增量的糾刪碼數據更新方法，本文提出的PARD更新方法極大限度地從減少更新路徑上的讀后寫操作及后續更新校驗塊的磁盤尋道開銷2個方面來提升分布式存儲集群的數據更新性能.此外，本文設計的PARD原型實現了多種最新的數據更新策略，并用真實工作負載下的軌跡對不同更新策略的寫性能進行測試.實驗結果表明，PARD策略顯著提升了糾刪碼存儲集群數據更新性能.在未來本工作計劃探索如何在PARD的基礎上，進一步減少跨機架環境下數據更新時的網絡傳輸開銷，并測試PARD的單節點和多節點的修復效率.

作者貢獻聲明：章紫琳提出數據更新方法思路，負責完成實驗并撰寫論文；劉鐸提出實驗方案，修改并審核論文；譚玉娟提出指導意見；吳宇參與論文校對；羅龍攀參與圖表修正；王緯略負責調研文獻；喬磊參與實驗數據審查.