史 驍 宋永浩 鄭曉輝 唐宏偉 于 雷 趙曉芳

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (**中國(guó)科學(xué)院大學(xué) 北京 100049)

0 引 言

分布式對(duì)象存儲(chǔ)是云計(jì)算存儲(chǔ)的主要形式之一，其可有效滿足數(shù)據(jù)中心存儲(chǔ)服務(wù)的高擴(kuò)展性需求[1-4]，常用于存儲(chǔ)大規(guī)模的非結(jié)構(gòu)化數(shù)據(jù)，包括文本、圖片、視頻、訓(xùn)練集、機(jī)器學(xué)習(xí)模型等。為充分發(fā)揮存儲(chǔ)系統(tǒng)性能、提高存儲(chǔ)系統(tǒng)利用率，良好的系統(tǒng)I/O并行性是一個(gè)基本條件[5]。

系統(tǒng)設(shè)計(jì)人員常常通過(guò)降低系統(tǒng)的數(shù)據(jù)一致性級(jí)別來(lái)提高系統(tǒng)的I/O并行性，但弱一致性級(jí)別及相關(guān)I/O并行優(yōu)化技術(shù)無(wú)法滿足具有強(qiáng)一致性需求的應(yīng)用。最終一致性是分布式對(duì)象存儲(chǔ)中常采用的一種弱一致性模型[4]，其特點(diǎn)是：對(duì)象讀(GET)請(qǐng)求可以在任意可用的副本節(jié)點(diǎn)執(zhí)行。但是，當(dāng)應(yīng)用的I/O模式具備流水線特征時(shí)，最終一致性模型所引發(fā)的數(shù)據(jù)不一致會(huì)影響應(yīng)用計(jì)算的準(zhǔn)確性及存儲(chǔ)系統(tǒng)利用率[1]。針對(duì)弱一致性模型，現(xiàn)有工作提出了一系列借助負(fù)載均衡優(yōu)化I/O并行性的方法[5-10]。例如，C3[5]提出根據(jù)存儲(chǔ)節(jié)點(diǎn)主動(dòng)反饋的I/O請(qǐng)求隊(duì)列長(zhǎng)度，在存儲(chǔ)客戶端建立存儲(chǔ)節(jié)點(diǎn)的實(shí)時(shí)負(fù)載模型以供調(diào)度參考，從而實(shí)現(xiàn)負(fù)載均衡。其他針對(duì)一致性的研究多集中在探討如何協(xié)調(diào)復(fù)雜應(yīng)用的一致性需求及存儲(chǔ)系統(tǒng)所提供的一致性服務(wù)能力[11,12]，或如何高效、實(shí)時(shí)地對(duì)服務(wù)中出現(xiàn)的數(shù)據(jù)不一致性進(jìn)行檢測(cè)[13]。這些研究工作通常以較弱的一致性模型為基礎(chǔ)，這使得其難以移植到強(qiáng)一致性的場(chǎng)景中。

為滿足強(qiáng)一致性需求，工業(yè)界提出了一系列提高一致性保障的措施。例如，Google的分布式對(duì)象存儲(chǔ)服務(wù)利用Spanner提供跨數(shù)據(jù)中心的全局強(qiáng)一致性[1]，但其獨(dú)特的軟硬件設(shè)施(其在數(shù)據(jù)中心部署了GPS、原子鐘及相應(yīng)的時(shí)間管理API[14])不具備可復(fù)制性；Amazon S3通過(guò)保障桶信息的“寫后讀”相關(guān)性[3]提高一致性級(jí)別，但其數(shù)據(jù)一致性保障粒度仍然較粗，仍以犧牲對(duì)象的一致性來(lái)?yè)Q取I/O并行性的提升。

目前，為了實(shí)現(xiàn)強(qiáng)一致性，系統(tǒng)設(shè)計(jì)普遍采用主副本優(yōu)先調(diào)度策略?；镜亩喔北緳C(jī)制要求系統(tǒng)對(duì)任一數(shù)據(jù)對(duì)象維護(hù)指定數(shù)目的副本數(shù)據(jù)。同一數(shù)據(jù)對(duì)象在系統(tǒng)中的多個(gè)副本可構(gòu)成完整的“副本組”。用于存儲(chǔ)某一副本的存儲(chǔ)節(jié)點(diǎn)稱為“副本節(jié)點(diǎn)”。在此基礎(chǔ)上，主從多副本機(jī)制規(guī)定副本組內(nèi)的某個(gè)副本為該組的“主副本”，而其他副本為“從副本”。相應(yīng)地，主副本所在的存儲(chǔ)節(jié)點(diǎn)可稱為“主副本節(jié)點(diǎn)”。在副本主從關(guān)系的基礎(chǔ)上，主副本優(yōu)先調(diào)度策略要求各主副本節(jié)點(diǎn)執(zhí)行副本組中數(shù)據(jù)對(duì)象的所有I/O請(qǐng)求。該策略假設(shè)I/O并行性可以借助數(shù)據(jù)分布的隨機(jī)性實(shí)現(xiàn)。但實(shí)際應(yīng)用中，由于數(shù)據(jù)訪問(wèn)熱度并不均衡，該策略極易使得系統(tǒng)負(fù)載分布失衡[5-7]，從而影響I/O并行性。這在第5節(jié)所述實(shí)驗(yàn)中同樣得到了驗(yàn)證。

針對(duì)強(qiáng)一致性下I/O并行性優(yōu)化技術(shù)尚不完善的現(xiàn)狀，本文的研究目標(biāo)是在提供強(qiáng)一致性保障的同時(shí)，優(yōu)化系統(tǒng)的I/O并行性，以提高強(qiáng)一致性存儲(chǔ)服務(wù)的性能。本文提出了一種基于多副本的I/O調(diào)度策略，適用于常見(jiàn)的分布式對(duì)象存儲(chǔ)系統(tǒng)，其主要包括3個(gè)步驟。第一，I/O請(qǐng)求被發(fā)送至數(shù)據(jù)所在的主副本節(jié)點(diǎn)進(jìn)行I/O負(fù)載合并以及強(qiáng)一致性關(guān)系確認(rèn)。本文策略利用主從多副本機(jī)制，所有I/O請(qǐng)求均需被發(fā)送至所在副本集合的主節(jié)點(diǎn)上，并等待該節(jié)點(diǎn)實(shí)施有效的I/O調(diào)度。為減少相關(guān)性沖突，主副本節(jié)點(diǎn)需要在調(diào)度前結(jié)合當(dāng)前上下文中的請(qǐng)求執(zhí)行負(fù)載合并，并確定I/O請(qǐng)求之間的一致性關(guān)系。第二，針對(duì)每個(gè)I/O請(qǐng)求，分析當(dāng)前環(huán)境中其可用的I/O并行決策空間，設(shè)置相應(yīng)的執(zhí)行優(yōu)先級(jí)。優(yōu)先級(jí)一方面保障數(shù)據(jù)相關(guān)性，另一方面保障請(qǐng)求時(shí)間窗口的順序性。該機(jī)制支持來(lái)自同一副本集合的I/O請(qǐng)求在任意一個(gè)副本節(jié)點(diǎn)上進(jìn)行優(yōu)先級(jí)比較。第三，均衡I/O負(fù)載。經(jīng)過(guò)預(yù)處理后的I/O請(qǐng)求在主副本節(jié)點(diǎn)等待調(diào)度。根據(jù)多副本主從模型，所有寫請(qǐng)求由主副本節(jié)點(diǎn)協(xié)調(diào)執(zhí)行。具備相關(guān)性的I/O請(qǐng)求在主副本節(jié)點(diǎn)有序執(zhí)行。其余讀請(qǐng)求則可完全并行執(zhí)行。

本文實(shí)現(xiàn)了一個(gè)分布式對(duì)象存儲(chǔ)系統(tǒng)原型，其支持多副本的主從模型以及基于哈希的數(shù)據(jù)分布定位機(jī)制。為進(jìn)行對(duì)比實(shí)驗(yàn)，在原型系統(tǒng)中分別實(shí)現(xiàn)了主副本優(yōu)先調(diào)度、隨機(jī)調(diào)度、C3[5]、本文方法這4種調(diào)度策略。實(shí)驗(yàn)結(jié)果表明，本文策略可以在保障強(qiáng)一致性的同時(shí)，充分釋放系統(tǒng)I/O并行性，提高系統(tǒng)資源利用率。其具體包括：負(fù)載合并可有效提高存儲(chǔ)資源利用率，使得系統(tǒng)GET吞吐量最大提升6.4%；較常用強(qiáng)一致性保障策略(主副本優(yōu)先調(diào)度)，本文策略使得GET請(qǐng)求吞吐量最大提升41.8%，GET請(qǐng)求平均延遲最大降低42.5%，GET請(qǐng)求99.9th延遲最大下降15.8倍，使系統(tǒng)性能達(dá)到最終一致性下基準(zhǔn)調(diào)度策略C3的性能水平；數(shù)據(jù)相關(guān)性導(dǎo)致吞吐量下降幅度不超過(guò)7.2%。

本文的主要工作包括：

(1) 設(shè)計(jì)實(shí)現(xiàn)了強(qiáng)一致性下可執(zhí)行I/O并行性優(yōu)化的調(diào)度框架。

(2) 基于調(diào)度框架設(shè)計(jì)實(shí)現(xiàn)了負(fù)載合并器、數(shù)據(jù)相關(guān)性檢測(cè)器以及負(fù)載均衡器。

(3) 在原型系統(tǒng)上實(shí)驗(yàn)驗(yàn)證了本文工作的有效性。

本文組織結(jié)構(gòu)如下：第1節(jié)對(duì)本工作研究背景及問(wèn)題挑戰(zhàn)進(jìn)行了闡述；第2節(jié)闡述了支持強(qiáng)一致性的I/O并行優(yōu)化調(diào)度框架；第3節(jié)描述了框架內(nèi)各子模塊的輸入輸出及核心算法；第4節(jié)簡(jiǎn)述了原型系統(tǒng)的實(shí)現(xiàn)；第5節(jié)闡述了實(shí)驗(yàn)結(jié)果；第6節(jié)介紹了多副本調(diào)度以及一致性模型的相關(guān)研究；第7節(jié)對(duì)本文進(jìn)行了總結(jié)。

1 背景及挑戰(zhàn)

1.1 系統(tǒng)架構(gòu)因素

分布式對(duì)象存儲(chǔ)系統(tǒng)對(duì)數(shù)據(jù)實(shí)行扁平化的管理，具備以下特點(diǎn)：對(duì)象在整個(gè)系統(tǒng)中被唯一標(biāo)識(shí)；對(duì)象無(wú)差異地隸屬于桶或容器中；桶中的對(duì)象數(shù)量不受限制；對(duì)象是數(shù)據(jù)操作的最小單元，即標(biāo)準(zhǔn)API(application programming interface)僅支持針對(duì)對(duì)象整體的讀(GET)、寫(PUT)、刪除(DELETE)[1,3]。

分布式對(duì)象存儲(chǔ)中，以下2項(xiàng)架構(gòu)因素影響本研究工作的開(kāi)展：(1)數(shù)據(jù)可靠性機(jī)制：多副本或糾刪碼；(2)對(duì)象定位機(jī)制：哈希或元數(shù)據(jù)。數(shù)據(jù)可靠性機(jī)制影響I/O并行化的決策空間。對(duì)象定位機(jī)制影響調(diào)度器的架構(gòu)、交互方式及功能定義。本文工作針對(duì)采用多副本及一致性哈希定位的分布式對(duì)象存儲(chǔ)系統(tǒng)。

多副本機(jī)制在諸多分布式存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用，包括Ceph[2,15]、Lustre[16]、HBase[17]、Cassandra[18]以及Openstack Swift[19]等。其要求系統(tǒng)分散地維護(hù)多個(gè)數(shù)據(jù)副本，一致性保障依靠主從模型或者QUORUM等模型。主副本優(yōu)先調(diào)度便是面向主從模式的多副本機(jī)制而設(shè)計(jì)。在強(qiáng)一致性前提下，系統(tǒng)可保障任意對(duì)象的操作滿足“寫后讀”一致性要求。

一致性哈希使用對(duì)象標(biāo)識(shí)作為哈希函數(shù)的輸入，計(jì)算對(duì)象的存儲(chǔ)位置?；谝恢滦怨６ㄎ粰C(jī)制，系統(tǒng)可以分布式地計(jì)算對(duì)象的副本節(jié)點(diǎn)集合，更加靈活地支持調(diào)度框架的設(shè)計(jì)。

1.2 I/O并行化的決策空間

I/O并行化的決策空間，或稱I/O調(diào)度的決策空間，是指在滿足一致性級(jí)別的前提下，可執(zhí)行給定I/O請(qǐng)求的存儲(chǔ)節(jié)點(diǎn)構(gòu)成的集合。在主從多副本機(jī)制下，寫請(qǐng)求的調(diào)度決策空間僅包含主副本節(jié)點(diǎn)；讀請(qǐng)求的調(diào)度決策空間受到數(shù)據(jù)一致性模型影響。例如，最終一致性模型下，讀請(qǐng)求的調(diào)度決策空間為副本組內(nèi)的所有節(jié)點(diǎn)。

I/O決策空間的計(jì)算設(shè)計(jì)可劃分為2個(gè)子任務(wù)。

(1) 選擇計(jì)算架構(gòu)。計(jì)算可采取中心化或分布式的架構(gòu)。由于I/O調(diào)度服務(wù)需實(shí)時(shí)處理高并發(fā)負(fù)載，本文研究中采用分布式架構(gòu)。結(jié)合主從多副本機(jī)制的特點(diǎn)，由主副本節(jié)點(diǎn)執(zhí)行調(diào)度決策操作，一方面滿足分布式計(jì)算架構(gòu)需求，另一方面為I/O并行性空間的計(jì)算提供了基礎(chǔ)。

(2) 確立計(jì)算模型。計(jì)算模型可兼顧多項(xiàng)因素，例如可靠性機(jī)制、負(fù)載分布、網(wǎng)絡(luò)狀態(tài)等。有關(guān)分布式系統(tǒng)任務(wù)調(diào)度的相關(guān)研究常利用多副本的并行化空間進(jìn)行負(fù)載均衡，將調(diào)度決策轉(zhuǎn)化為根據(jù)模型計(jì)算最優(yōu)決策的問(wèn)題，包括負(fù)載均衡預(yù)測(cè)模型[5,8]、探索-利用模型[9]等。本文方法的計(jì)算模型的設(shè)計(jì)結(jié)合了負(fù)載均衡因素。

1.3 挑戰(zhàn)：強(qiáng)一致性對(duì)調(diào)度決策空間的限制

強(qiáng)一致性要求具備相關(guān)性的I/O請(qǐng)求按照時(shí)間序列關(guān)系線性執(zhí)行，約束了每個(gè)I/O請(qǐng)求的調(diào)度決策空間，從而影響了I/O并行性。同時(shí)，為提高I/O并行性，將I/O請(qǐng)求分配至多個(gè)節(jié)點(diǎn)上并行執(zhí)行，若后續(xù)I/O請(qǐng)求與已經(jīng)分配的I/O請(qǐng)求之間存在相關(guān)性，則系統(tǒng)需要跨節(jié)點(diǎn)維護(hù)、追蹤相關(guān)性信息。在分布式系統(tǒng)架構(gòu)中動(dòng)態(tài)實(shí)時(shí)地維護(hù)相關(guān)性信息難度較大。

表1展示了常見(jiàn)分布式存儲(chǔ)系統(tǒng)中調(diào)度策略與一致性模型的對(duì)應(yīng)關(guān)系?？梢?jiàn)，為實(shí)現(xiàn)強(qiáng)一致性，分布式對(duì)象存儲(chǔ)系統(tǒng)普遍采用主副本優(yōu)先調(diào)度策略，而這一策略未充分地挖掘調(diào)度決策空間，無(wú)助于提高I/O并行性。在主副本優(yōu)先調(diào)度中，所有屬于相同副本集合的I/O請(qǐng)求均在主副本節(jié)點(diǎn)進(jìn)行有序的排隊(duì)。例如，一同排隊(duì)的和請(qǐng)求，它們之間不存在任何數(shù)據(jù)相關(guān)性，響應(yīng)順序完全不影響二者操作的正確性。這種所有I/O請(qǐng)求在主副本節(jié)點(diǎn)上有序執(zhí)行的方式嚴(yán)重浪費(fèi)了多副本所提供的并行I/O空間。實(shí)際上，通過(guò)本文工作可以看出，強(qiáng)一致性與主副本優(yōu)先調(diào)度并不存在綁定關(guān)系。

表1 常見(jiàn)分布式存儲(chǔ)系統(tǒng)的多副本調(diào)度策略

表1中其他調(diào)度策略雖然可以利用多副本的并行I/O空間，但不能保障強(qiáng)一致性。國(guó)內(nèi)外相關(guān)研究多聚焦于使系統(tǒng)提供與應(yīng)用需求所適宜的數(shù)據(jù)一致性模型。例如，文獻(xiàn)[12]和文獻(xiàn)[13]的作者探討了在存儲(chǔ)系統(tǒng)中同時(shí)提供多種一致性模型所面臨的挑戰(zhàn)。

總之，強(qiáng)一致性下的I/O并行性優(yōu)化技術(shù)發(fā)展需要新的調(diào)度策略。

2 調(diào)度框架

本節(jié)提出了支持強(qiáng)一致性的I/O并行性優(yōu)化調(diào)度框架，如圖1所示。不同于以往的調(diào)度策略，本框架以各主副本為中心，要求客戶端將I/O請(qǐng)求發(fā)送至主副本節(jié)點(diǎn)，由各主副本節(jié)點(diǎn)獨(dú)立實(shí)施調(diào)度。調(diào)度器由以下3部分構(gòu)成。

圖1 調(diào)度框架

(1) 負(fù)載合并器。合并不同客戶端之間的同質(zhì)I/O請(qǐng)求，以節(jié)省I/O處理開(kāi)銷。所謂同質(zhì)I/O請(qǐng)求，指的是針對(duì)同一對(duì)象的同類型I/O請(qǐng)求。I/O序列中相鄰的同質(zhì)請(qǐng)求可得到相同的響應(yīng)結(jié)果。由于對(duì)象存儲(chǔ)的編程接口十分簡(jiǎn)明(主要包含GET、PUT、DELETE等)，且操作以對(duì)象為最小單元，這為合并同質(zhì)I/O請(qǐng)求提供了基礎(chǔ)。

(2) 數(shù)據(jù)相關(guān)性檢測(cè)器。數(shù)據(jù)相關(guān)性檢測(cè)器完成數(shù)據(jù)相關(guān)性的過(guò)濾以及優(yōu)先級(jí)分配。

(3) 負(fù)載均衡器。負(fù)載均衡器負(fù)責(zé)將預(yù)處理后的I/O請(qǐng)求序列在所屬的副本集合節(jié)點(diǎn)之間進(jìn)行均衡。

2.1 架 構(gòu)

根據(jù)多副本主從模型的特點(diǎn)，本文工作選擇將主副本節(jié)點(diǎn)設(shè)置為數(shù)據(jù)相關(guān)性檢測(cè)器，作為保障強(qiáng)一致性的核心模塊。在主副本節(jié)點(diǎn)實(shí)現(xiàn)數(shù)據(jù)相關(guān)性檢測(cè)具備以下優(yōu)勢(shì)：

(1) 架構(gòu)天然地利用數(shù)據(jù)分布的隨機(jī)性，對(duì)I/O的數(shù)據(jù)相關(guān)性負(fù)載進(jìn)行了分組。由于強(qiáng)一致性的數(shù)據(jù)相關(guān)性檢測(cè)以對(duì)象為單位，這要求系統(tǒng)提供統(tǒng)一視圖，以便無(wú)遺漏地比較不同客戶端之間的I/O請(qǐng)求。但實(shí)際運(yùn)行環(huán)境中出現(xiàn)的高負(fù)載現(xiàn)象要求采用分布式的數(shù)據(jù)相關(guān)性檢測(cè)器。若采用獨(dú)立的節(jié)點(diǎn)進(jìn)行相關(guān)性檢測(cè)，客戶端之間將引入大量點(diǎn)到點(diǎn)的網(wǎng)絡(luò)通信，其通信規(guī)模與客戶端的數(shù)量以及I/O負(fù)載強(qiáng)度成正比。而利用副本主節(jié)點(diǎn)實(shí)現(xiàn)分布式檢測(cè)，一方面可以減少不必要的通信，另一方面可以利用現(xiàn)有機(jī)制避免額外的負(fù)載均衡機(jī)制。

(2) 有利于I/O請(qǐng)求的數(shù)據(jù)相關(guān)性定序。數(shù)據(jù)相關(guān)性關(guān)系確定后，系統(tǒng)需保障相關(guān)I/O的線性響應(yīng)順序。如確保將具備相關(guān)性的I/O請(qǐng)求正確發(fā)送給副本節(jié)點(diǎn)，需要客戶端或檢測(cè)器與副本節(jié)點(diǎn)之間進(jìn)行額外的通信。在本架構(gòu)下，檢測(cè)器可保障相關(guān)的I/O請(qǐng)求順序插入本地I/O請(qǐng)求隊(duì)列。

(3) 減少通信開(kāi)銷。在本架構(gòu)下，調(diào)度框架對(duì)客戶端透明，客戶端將I/O請(qǐng)求發(fā)送出去后即完成任務(wù)，避免了大量低效的通信。而調(diào)度器與其他副本節(jié)點(diǎn)之間的通信采用批量發(fā)送I/O的技術(shù)，可大幅度節(jié)省通信開(kāi)銷。

在進(jìn)行相關(guān)性檢測(cè)之前，本框架通過(guò)負(fù)載合并器對(duì)同質(zhì)的I/O請(qǐng)求進(jìn)行合并。我們定義同質(zhì)的I/O請(qǐng)求為針對(duì)同一個(gè)對(duì)象的同類型操作。這樣，冗余的I/O操作可以被有效避免。例如，, 可合并為<(client1, client2), obj1, GET>。該類I/O請(qǐng)求執(zhí)行完畢后需向所有請(qǐng)求客戶端進(jìn)行響應(yīng)。

數(shù)據(jù)相關(guān)性檢測(cè)器將標(biāo)記好優(yōu)先級(jí)的I/O請(qǐng)求轉(zhuǎn)發(fā)給負(fù)載均衡器。負(fù)載均衡器負(fù)責(zé)保持本副本組內(nèi)各節(jié)點(diǎn)的負(fù)載均衡。需要注意的是，不同副本組的節(jié)點(diǎn)集合之間存在交集。各個(gè)副本組的負(fù)載均衡器實(shí)現(xiàn)的是來(lái)自本副本組內(nèi)I/O請(qǐng)求的均衡。負(fù)載均衡器通過(guò)批量調(diào)度，按各個(gè)設(shè)備的I/O處理能力對(duì)請(qǐng)求分布進(jìn)行均衡，并將同目標(biāo)節(jié)點(diǎn)的I/O請(qǐng)求打包后發(fā)送給目標(biāo)副本節(jié)點(diǎn)。

2.2 存儲(chǔ)客戶端作用域

對(duì)于存儲(chǔ)客戶端而言，I/O調(diào)度過(guò)程對(duì)其完全透明，其職責(zé)基本未發(fā)生改變。但不同于其他策略的是，存儲(chǔ)客戶端將I/O請(qǐng)求提交至主副本節(jié)點(diǎn)，而實(shí)際的請(qǐng)求響應(yīng)節(jié)點(diǎn)可能是副本組內(nèi)的任意一個(gè)節(jié)點(diǎn)，如圖2所示。

圖2 客戶端視角

2.3 調(diào)度器作用域

調(diào)度器內(nèi)數(shù)據(jù)通信通過(guò)線程通信完成，但是被調(diào)度至其他副本節(jié)點(diǎn)的I/O請(qǐng)求需要通過(guò)一次網(wǎng)絡(luò)通信進(jìn)行轉(zhuǎn)發(fā)。調(diào)度器與其他副本節(jié)點(diǎn)通信時(shí)，采用批量方式轉(zhuǎn)發(fā)待處理的I/O請(qǐng)求，如圖3所示。

圖3 調(diào)度器視角

2.4 副本節(jié)點(diǎn)作用域

副本節(jié)點(diǎn)執(zhí)行調(diào)度器提交的I/O請(qǐng)求序列，其優(yōu)先級(jí)隊(duì)列需嚴(yán)格參照調(diào)度器中所分配的優(yōu)先級(jí)。這樣，同一副本節(jié)點(diǎn)中，來(lái)自同一副本組的I/O操作的優(yōu)先級(jí)可保持一致性。

3 調(diào)度模塊

本節(jié)對(duì)調(diào)度器主要模塊的功能進(jìn)行了定義。

3.1 負(fù)載合并器

負(fù)載合并器主要實(shí)現(xiàn)2個(gè)任務(wù)。首先，負(fù)載合并器周期性地收集一組待處理的I/O請(qǐng)求。每個(gè)周期形成一個(gè)時(shí)間窗口。負(fù)載合并器分別記錄I/O請(qǐng)求的目標(biāo)對(duì)象以及I/O類型。然后，負(fù)載合并器對(duì)該組請(qǐng)求內(nèi)的同質(zhì)(同對(duì)象、同I/O類型且其間不夾雜同對(duì)象、其他I/O類型)I/O操作進(jìn)行合并。這2個(gè)任務(wù)完成后，待處理I/O請(qǐng)求的強(qiáng)一致性關(guān)系即得到確定。本文統(tǒng)一采用了向前合并的策略處理GET、PUT、DELETE操作，這里分別對(duì)它們合并的方式及影響進(jìn)行說(shuō)明：

(1) GET合并。GET合并遵從的重要原則是減少用戶應(yīng)用程序不必要的重試和過(guò)時(shí)數(shù)據(jù)的讀取，包括桶以及對(duì)象的讀取操作等。執(zhí)行合并后的GET請(qǐng)求置于第一個(gè)被合并GET請(qǐng)求的位置。

(2) PUT合并。PUT請(qǐng)求寫入或更新對(duì)象數(shù)據(jù)，按照強(qiáng)一致性的時(shí)間序列化關(guān)系，合并后的PUT請(qǐng)求寫入最后一個(gè)到達(dá)的PUT請(qǐng)求的內(nèi)容，并將其置于第一個(gè)被合并PUT請(qǐng)求的位置。

(3) DELETE合并。DELETE請(qǐng)求刪除對(duì)象數(shù)據(jù)，其操作完全冗余。DELETE請(qǐng)求合并后置于第一個(gè)被合并的DELETE請(qǐng)求的位置。

這種局部的重排序之后，后續(xù)的操作將嚴(yán)格遵守此時(shí)確定的數(shù)據(jù)相關(guān)性關(guān)系，如圖4所示。這里所討論的負(fù)載合并同操作系統(tǒng)內(nèi)核I/O調(diào)度中的I/O合并(向前或向后并)[19]的區(qū)別在于：

(1) 處理階段不同。本文負(fù)載合并在用戶態(tài)進(jìn)行；內(nèi)核I/O負(fù)載合并在內(nèi)核態(tài)執(zhí)行。

(2) 影響范圍不同。本文負(fù)載合并可影響多個(gè)節(jié)點(diǎn)，在分布式系統(tǒng)層面減少I/O負(fù)載量；內(nèi)核I/O負(fù)載合并局限于單點(diǎn)。

(3) 目標(biāo)不同。本文負(fù)載合并的一個(gè)重要目的是簡(jiǎn)化數(shù)據(jù)相關(guān)性的分析及一致性的管理；內(nèi)核I/O負(fù)載合并不存在這一目標(biāo)。

圖4 負(fù)載合并示意圖

3.2 數(shù)據(jù)相關(guān)性檢測(cè)器

負(fù)載合并器確定了一個(gè)時(shí)間窗口內(nèi)的數(shù)據(jù)強(qiáng)一致性關(guān)系，并將待調(diào)度I/O請(qǐng)求序列轉(zhuǎn)發(fā)至數(shù)據(jù)相關(guān)性檢測(cè)器。數(shù)據(jù)相關(guān)性檢測(cè)器一方面維護(hù)當(dāng)前序列中的數(shù)據(jù)相關(guān)性，另一方面需要維護(hù)不同時(shí)間窗口之間請(qǐng)求序列的數(shù)據(jù)相關(guān)性。讀操作包括系統(tǒng)內(nèi)不同粒度的GET操作，寫操作包括系統(tǒng)內(nèi)不同粒度的PUT、DELETE操作。這里針對(duì)寫后讀、讀后寫、寫后寫的處理進(jìn)行說(shuō)明。

(1) 寫后讀相關(guān)。寫后讀相關(guān)的存在不受時(shí)間窗口的限制，這種相關(guān)性維護(hù)需要在時(shí)間線上進(jìn)行宏觀的管理。

(2) 讀后寫相關(guān)。讀后寫相關(guān)的存在同樣不受時(shí)間窗口的限制。

(3) 寫后寫相關(guān)。寫后寫相關(guān)僅存在于不同時(shí)間窗口的寫、寫請(qǐng)求之間。

數(shù)據(jù)相關(guān)性檢測(cè)器將數(shù)據(jù)相關(guān)性轉(zhuǎn)換為確定的優(yōu)先級(jí)關(guān)系。優(yōu)先級(jí)以整數(shù)形式表示I/O的相對(duì)執(zhí)行順序，其數(shù)值越大，則優(yōu)先級(jí)越低。優(yōu)先級(jí)的分配需考慮時(shí)間窗口及數(shù)據(jù)相關(guān)性關(guān)系。為方便優(yōu)先級(jí)編碼，每個(gè)時(shí)間窗口內(nèi)的優(yōu)先級(jí)起始編碼為常數(shù)*時(shí)間窗口號(hào)。這表示在一個(gè)時(shí)間窗口內(nèi)，針對(duì)同一對(duì)象的I/O操作間最多可具備常數(shù)個(gè)相關(guān)性關(guān)系。本文稱之為相關(guān)性系數(shù)。當(dāng)優(yōu)先級(jí)個(gè)數(shù)不夠用時(shí)，將I/O推遲至下一時(shí)間窗口處理。在每個(gè)時(shí)間窗口內(nèi)，檢測(cè)器負(fù)責(zé)分配多個(gè)連續(xù)的優(yōu)先級(jí)，所有在相關(guān)性中需要優(yōu)先執(zhí)行的I/O請(qǐng)求、無(wú)相關(guān)性的I/O請(qǐng)求被分配較高優(yōu)先級(jí)，其他I/O請(qǐng)求被分配較低優(yōu)先級(jí)，按照相關(guān)性逐級(jí)加1，如算法1所示。

算法1: 數(shù)據(jù)相關(guān)性檢測(cè)及優(yōu)先級(jí)分配 輸入:I/O序列IOSeq,時(shí)間窗口編號(hào)WID,數(shù)據(jù)相關(guān)性記錄表relmap,優(yōu)先級(jí)累加記錄表priomap, 相關(guān)性系數(shù) R 輸出: 標(biāo)記了優(yōu)先級(jí)的I/O序列IOSeq1: Priorities={WID*R, WID*R+1, …}2: for Req in IOSeq:3: // assign lower priority4: if relmap.find(Req.obj):5: Req.priority=max(priomap[Req.obj]+1,6: WID*R);7: priomap [Req.obj] = Req.priority;8: else9: Req.priority = WID*R;10: // for future checking11: if Req.type == PUT || Req.type == DELETE:12: relmap.insert(Req.obj);

不同副本組內(nèi)分配的優(yōu)先級(jí)不具有可比性，但同副本組內(nèi)分配的優(yōu)先級(jí)在任一副本節(jié)點(diǎn)上都可比較。各副本節(jié)點(diǎn)的I/O隊(duì)列遵守該優(yōu)先級(jí)關(guān)系進(jìn)行I/O處理。例如，當(dāng)主副本節(jié)點(diǎn)將寫操作下發(fā)至某個(gè)從副本節(jié)點(diǎn)進(jìn)行數(shù)據(jù)同步時(shí)，其優(yōu)先級(jí)依舊保持原有級(jí)別，當(dāng)前從副本節(jié)點(diǎn)中若存在優(yōu)先級(jí)較高但尚未執(zhí)行的I/O請(qǐng)求，則該寫操作仍然需要等待高優(yōu)先級(jí)操作執(zhí)行完成之后方可執(zhí)行。這樣，相關(guān)性即可依靠?jī)?yōu)先級(jí)進(jìn)行保障，從而實(shí)現(xiàn)強(qiáng)一致性。

為維護(hù)一致性關(guān)系，數(shù)據(jù)相關(guān)性檢測(cè)器接受調(diào)度器的反饋，當(dāng)I/O請(qǐng)求被插入I/O隊(duì)列后，相應(yīng)的相關(guān)性約束可被釋放。數(shù)據(jù)相關(guān)性檢測(cè)器將分配好優(yōu)先級(jí)的I/O請(qǐng)求序列轉(zhuǎn)發(fā)至負(fù)載均衡器。

3.3 負(fù)載均衡器

根據(jù)多副本的主從模型，所有寫請(qǐng)求都需要遵從先主后從的執(zhí)行順序。因此，相關(guān)的寫后讀、寫后寫請(qǐng)求均直接在主副本節(jié)點(diǎn)上繼續(xù)排隊(duì)。

對(duì)于其他I/O請(qǐng)求，負(fù)載均衡器按照負(fù)載分布狀況進(jìn)行調(diào)度。由于對(duì)象存儲(chǔ)系統(tǒng)的I/O操作單元以對(duì)象為最小單位，因此，本文認(rèn)為各節(jié)點(diǎn)的負(fù)載狀況可以參考I/O隊(duì)列長(zhǎng)度進(jìn)行判斷。由于負(fù)載均衡算法并非本文研究的重點(diǎn)，這里使用了較為簡(jiǎn)單的負(fù)載均衡策略(算法2所示)——輪詢方式配合提升I/O并行性。在每次負(fù)載均衡調(diào)度時(shí)，先將具備相關(guān)性的I/O操作分配給主副本節(jié)點(diǎn)，其他I/O操作則優(yōu)先分配至當(dāng)前時(shí)間窗口內(nèi)負(fù)載量最少的節(jié)點(diǎn)。

算法2: 負(fù)載均衡策略 輸入:I/O序列IOSeq,相關(guān)性系數(shù) R 輸出: 各副本節(jié)點(diǎn)I/O序列NodeSeq1: // Schedule I/Os in data relativity first2: for Req in IOSeq:3: if Req.priority%R == 0:4: if Req.type == (PUT|DELETE):5: node = current;6: else:7: node = current8: NodeSeq[node].insert(Req);9: // Schedule other I/Os.10:for Req in IOSeq:11: if Req.priority%R== 0:12: if Req.type != (PUT|DELETE):13: node = argminnode(NodeSeq(node).size());14: NodeSeq[node].insert(Req);

4 系統(tǒng)原型實(shí)現(xiàn)

為了驗(yàn)證本文方法的有效性，本研究實(shí)現(xiàn)了一個(gè)分布式對(duì)象存儲(chǔ)系統(tǒng)的原型。該對(duì)象存儲(chǔ)系統(tǒng)包含了所需的基本功能。其數(shù)據(jù)可靠性機(jī)制采用了主從多副本機(jī)制；數(shù)據(jù)分布機(jī)制使用一致性哈希方法；客戶端模塊支持GET、PUT對(duì)象操作接口；底層的對(duì)象存儲(chǔ)利用本地文件系統(tǒng)實(shí)現(xiàn)；后端存儲(chǔ)節(jié)點(diǎn)模塊支持優(yōu)先級(jí)I/O隊(duì)列，并支持本文調(diào)度器中的優(yōu)先級(jí)規(guī)則。

除本文調(diào)度策略之外，還在系統(tǒng)原型中支持了3種調(diào)度策略：

(1) 主副本優(yōu)先調(diào)度策略(MAIN調(diào)度)。所有I/O請(qǐng)求均提交至主副本節(jié)點(diǎn)處理。該策略支持強(qiáng)一致性模型，被廣泛使用，其作為強(qiáng)一致性下的負(fù)載均衡基準(zhǔn)算法。

(2) 隨機(jī)調(diào)度策略(RANDOM調(diào)度)。調(diào)度器為讀請(qǐng)求隨機(jī)地選擇一個(gè)可用的副本節(jié)點(diǎn)。該模式僅支持最終一致性模型。

(3) C3[5]。調(diào)度器根據(jù)存儲(chǔ)結(jié)點(diǎn)I/O隊(duì)列長(zhǎng)度的實(shí)時(shí)反饋及并發(fā)隊(duì)列補(bǔ)償以模擬負(fù)載分布狀況。該調(diào)度策略提供了較好的負(fù)載均衡能力，但僅支持最終一致性模型，其作為最終一致性下的負(fù)載均衡基準(zhǔn)算法。

以上前2種調(diào)度策略均在客戶端實(shí)現(xiàn)，C3需要客戶端及各個(gè)存儲(chǔ)節(jié)點(diǎn)的交互，而本文方法在主副本節(jié)點(diǎn)模塊中實(shí)現(xiàn)。在實(shí)際工作過(guò)程中，MAIN和RANDOM調(diào)度策略均不需要借助任何網(wǎng)絡(luò)通信，僅通過(guò)一致性哈希來(lái)定位和選擇I/O請(qǐng)求的目標(biāo)執(zhí)行節(jié)點(diǎn)。C3需要借助網(wǎng)絡(luò)通信更新隊(duì)列長(zhǎng)度信息，該通信開(kāi)銷可通過(guò)I/O響應(yīng)信息來(lái)捎帶傳遞。在本文調(diào)度策略中，一個(gè)I/O請(qǐng)求的調(diào)度，至少需要1次網(wǎng)絡(luò)通信，最多需要2次網(wǎng)絡(luò)通信。第1次網(wǎng)絡(luò)通信由客戶端將I/O請(qǐng)求發(fā)送至主副本節(jié)點(diǎn)，第2次網(wǎng)絡(luò)通信由主副本節(jié)點(diǎn)將I/O請(qǐng)求根據(jù)負(fù)載均衡需求批量發(fā)送至其他副本節(jié)點(diǎn)。后續(xù)實(shí)驗(yàn)表明，網(wǎng)絡(luò)通信的開(kāi)銷未明顯增加I/O請(qǐng)求的處理延遲。

5 實(shí) 驗(yàn)

本節(jié)介紹了驗(yàn)證本文策略實(shí)際效果的方法及實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)測(cè)試集群包含5臺(tái)存儲(chǔ)服務(wù)器， 30塊HDD硬盤以及獨(dú)立的客戶端服務(wù)器。系統(tǒng)存儲(chǔ)池中包含512個(gè)副本組。測(cè)試開(kāi)始前，測(cè)試存儲(chǔ)池中預(yù)先保存了10萬(wàn)個(gè)大小均為4 kB的對(duì)象。

測(cè)試中的I/O負(fù)載利用COSBench工具[20]生成。實(shí)驗(yàn)中根據(jù)模型系統(tǒng)的接口修改了COSBench的功能。該工具通過(guò)多線程客戶端模擬并發(fā)負(fù)載場(chǎng)景。模擬程序可調(diào)節(jié)2個(gè)參數(shù)：負(fù)載并發(fā)度以及I/O讀寫比例。負(fù)載并發(fā)度指客戶端同時(shí)等待的I/O請(qǐng)求的總個(gè)數(shù)，該指標(biāo)可探索系統(tǒng)的吞吐量上限。I/O讀寫比例指的是所有客戶端所產(chǎn)生的I/O請(qǐng)求中讀請(qǐng)求和寫請(qǐng)求的個(gè)數(shù)的比值。實(shí)驗(yàn)中調(diào)度器模塊的時(shí)間窗口設(shè)置為500 μs，相關(guān)性系數(shù)設(shè)置為5。時(shí)間窗口間隔設(shè)置較小，主要為了避免時(shí)間窗口內(nèi)I/O的過(guò)量堆積，從而影響響應(yīng)延遲。受此影響，相關(guān)性系數(shù)為5基本可以滿足用于標(biāo)記一個(gè)時(shí)間窗口內(nèi)的優(yōu)先級(jí)關(guān)系的需求。測(cè)試中所有對(duì)象的大小均為4 kB。在此基礎(chǔ)上，對(duì)不同I/O負(fù)載下的調(diào)度策略所展現(xiàn)的系統(tǒng)性能進(jìn)行了度量。

實(shí)驗(yàn)結(jié)果表明，本文策略可以在保障系統(tǒng)強(qiáng)一致性下較好地發(fā)揮I/O并行性，實(shí)現(xiàn)系統(tǒng)利用率等的提升。

5.1 負(fù)載合并模擬

本節(jié)對(duì)負(fù)載合并的效果進(jìn)行了模擬實(shí)驗(yàn)。實(shí)驗(yàn)通過(guò)調(diào)節(jié)固定并發(fā)度下(并發(fā)度為64)，同質(zhì)I/O請(qǐng)求比例進(jìn)行。由于無(wú)法量化應(yīng)用中的實(shí)際同質(zhì)I/O請(qǐng)求比例，模擬針對(duì)同質(zhì)I/O比例為0～20%下負(fù)載合并的收益進(jìn)行了統(tǒng)計(jì)。其收益具體表現(xiàn)為實(shí)際I/O并發(fā)度的降低。通過(guò)記錄I/O負(fù)載合并器所提交的I/O序列長(zhǎng)度和，可得圖5所示合并效果，其他策略由于不具備負(fù)載合并策略，而保持恒定并發(fā)度。由圖5可見(jiàn)，得益于同質(zhì)I/O請(qǐng)求合并，實(shí)際的I/O并發(fā)度得以降低，從而有助于系統(tǒng)資源的節(jié)省和利用率的提升。

圖5 負(fù)載合并效果

5.2 負(fù)載均衡性能

本節(jié)對(duì)本文策略的I/O并行性優(yōu)化效果進(jìn)行測(cè)試。由于各基準(zhǔn)算法的一致性保障級(jí)別不同，而強(qiáng)一致性會(huì)引起一定的性能損耗，因此在本節(jié)評(píng)估中，通過(guò)采用100%的GET操作集合來(lái)避免數(shù)據(jù)相關(guān)場(chǎng)景及其可能引發(fā)的開(kāi)銷。同時(shí)，為進(jìn)一步度量負(fù)載合并的作用，實(shí)驗(yàn)分別測(cè)試了不啟用及啟用負(fù)載合并功能的本文策略的效果。本節(jié)使用“本文-負(fù)載合并”表示未啟用負(fù)載合并功能的策略。

該負(fù)載模式下，通過(guò)提高客戶端GET請(qǐng)求的并發(fā)度(16～2048)，測(cè)試分布式對(duì)象存儲(chǔ)系統(tǒng)的性能和服務(wù)質(zhì)量及相應(yīng)上限。測(cè)試中關(guān)注的主要指標(biāo)包括GET請(qǐng)求吞吐量、GET請(qǐng)求處理延遲(平均延遲、99百分位延遲、99.9百分位延遲)。實(shí)驗(yàn)表明，本文策略對(duì)于提高分布式對(duì)象存儲(chǔ)系統(tǒng)存儲(chǔ)資源利用率、降低請(qǐng)求服務(wù)延遲、減少請(qǐng)求延遲分布的波動(dòng)情況有明顯效果。

本文策略有助于提高分布式對(duì)象存儲(chǔ)系統(tǒng)的資源利用率。如圖6所示，在不同GET請(qǐng)求并發(fā)度下，利用本文多副本調(diào)度算法的分布式對(duì)象存儲(chǔ)系統(tǒng)表現(xiàn)出良好的GET請(qǐng)求吞吐量。隨著GET請(qǐng)求并發(fā)度的不斷提高，4種算法均提高了整體GET吞吐量，但是，MAIN遠(yuǎn)未達(dá)到系統(tǒng)吞吐量上限，RANDOM在較高并發(fā)度下接近了系統(tǒng)吞吐量上限，C3和本文-負(fù)載合并在并發(fā)度達(dá)到64后達(dá)到了系統(tǒng)上限，而本文策略較本文-負(fù)載合并進(jìn)一步提高了系統(tǒng)吞吐量，說(shuō)明負(fù)載合并效果帶來(lái)了明顯的收益。在并發(fā)度為64時(shí)，本文策略所產(chǎn)生的GET請(qǐng)求吞吐率較MAIN提高了41.8%，較RANDOM提高了29.1%，較C3提高了6.4%。這說(shuō)明，本文策略的負(fù)載均衡效果明顯優(yōu)于其他基準(zhǔn)算法。

圖6 不同策略的GET請(qǐng)求吞吐率

本文策略有助于降低GET請(qǐng)求平均延遲。如圖7所示，在不同GET請(qǐng)求并發(fā)度下，尤其是隨著并發(fā)度的提高，利用本文策略下所得的GET平均處理延遲明顯低于其他策略。并發(fā)度為64時(shí)，本文策略較其他策略優(yōu)勢(shì)最明顯，其GET請(qǐng)求平均延遲較MAIN降低了42.5%，較RANDOM降低了29.7%，與C3基本持平。

圖7 不同策略的GET請(qǐng)求平均延遲

本文策略有助于降低GET請(qǐng)求延遲分布的波動(dòng)狀態(tài)。如圖8所示，在不同GET請(qǐng)求并發(fā)度下，利用本文策略所得的GET請(qǐng)求99.9th延遲明顯低于其他策略。當(dāng)I/O并發(fā)度達(dá)到256時(shí)，本文策略效果的優(yōu)勢(shì)最為顯著，其99.9百分位延遲較MAIN策略降低了10.3倍，較RANDOM策略降低了15.8倍，與C3基本持平。這說(shuō)明，本文策略有助于提供可靠的、可預(yù)測(cè)的I/O服務(wù)。如圖9所示，在不同GET請(qǐng)求并發(fā)度下，本文策略可以有效地保障延遲分布的平穩(wěn)。

圖8 不同策略的GET請(qǐng)求99.9th延遲

圖9 本文策略的GET請(qǐng)求延遲分布

5.3 數(shù)據(jù)相關(guān)性影響

本小節(jié)對(duì)數(shù)據(jù)相關(guān)性所帶來(lái)的影響進(jìn)行分析。由于其他多副本調(diào)度策略僅適用于單一的數(shù)據(jù)一致性級(jí)別，其各自效果不受數(shù)據(jù)相關(guān)性的影響，本節(jié)僅針對(duì)本文策略的表現(xiàn)進(jìn)行了展示。實(shí)驗(yàn)表明，本文策略可以有效利用受到數(shù)據(jù)相關(guān)性影響的I/O調(diào)度決策空間，避免相關(guān)性產(chǎn)生類似于MAIN策略的巨大性能限制。

與5.2節(jié)負(fù)載不同，本小節(jié)使用讀寫比例為7:3的負(fù)載模式，并區(qū)分為無(wú)數(shù)據(jù)相關(guān)以及有數(shù)據(jù)相關(guān)的模式。由圖6可知，當(dāng)GET請(qǐng)求并發(fā)度達(dá)到64時(shí)，基本上逼近了所布署系統(tǒng)的吞吐量上限，因此本節(jié)測(cè)試設(shè)置I/O并發(fā)度為64，讀寫比例側(cè)重讀多寫少場(chǎng)景(讀寫比例為70%～100%)。例如，在讀寫比例為7:3的場(chǎng)景下，其中讀并發(fā)度為45(≈64×0.7)，寫并發(fā)度為19(=64-45)。

如圖10所示，受讀寫比例逐步提高的影響，GET請(qǐng)求并發(fā)度逐步下降，相應(yīng)地，在數(shù)據(jù)相關(guān)性的影響下，系統(tǒng)吞吐量出現(xiàn)下降。在70%GET請(qǐng)求負(fù)載的場(chǎng)景下，GET請(qǐng)求吞吐率下降比例達(dá)到最大，產(chǎn)生了7.2%的性能下降。相較于強(qiáng)一致性的MAIN策略，其對(duì)系統(tǒng)性能的約束遠(yuǎn)強(qiáng)于本文策略。因此，本文策略在克服數(shù)據(jù)相關(guān)性影響上取得了良好效果。

圖10 相關(guān)性對(duì)GET吞吐率的影響

6 相關(guān)工作

多副本調(diào)度是分布式系統(tǒng)中負(fù)載均衡研究的重要話題。C3[5]利用I/O響應(yīng)捎帶的存儲(chǔ)節(jié)點(diǎn)待處理I/O隊(duì)列信息在客戶端建模存儲(chǔ)節(jié)點(diǎn)的負(fù)載分布。CFA[8]通過(guò)提取廣域網(wǎng)的網(wǎng)絡(luò)特征，利用相似特征匹配的方式預(yù)測(cè)不同副本的負(fù)載狀況，以實(shí)現(xiàn)實(shí)時(shí)的副本選擇。Pytheas[9]通過(guò)強(qiáng)化學(xué)習(xí)方法自主地學(xué)習(xí)副本上負(fù)載的分布狀況，繼而執(zhí)行實(shí)時(shí)的副本選擇。這些方法代表了多副本選擇時(shí)的不同模型，但它們都默認(rèn)在最終一致性模型下工作，未涉及強(qiáng)一致性的討論。

在多副本系統(tǒng)中提供多種兼容的一致性具有重要意義。文獻(xiàn)[11]中討論了用戶期望的數(shù)據(jù)一致性模型與系統(tǒng)提供的一致性模型之間的差距，并指出降低一致性級(jí)別常常并未完全收獲預(yù)期的收益。文獻(xiàn)[12]設(shè)計(jì)實(shí)現(xiàn)了一個(gè)新型的多副本事務(wù)范式，以允許用戶針對(duì)數(shù)據(jù)而非事務(wù)層面制定一致性級(jí)別。文獻(xiàn)[13]實(shí)現(xiàn)了一個(gè)可以提供自適應(yīng)的一致性保障的多副本系統(tǒng)原型。以上工作均未就強(qiáng)一致性的保障提供性能上的優(yōu)化。

7 結(jié) 論

針對(duì)保障強(qiáng)一致性的分布式對(duì)象存儲(chǔ)系統(tǒng)其I/O并行性受到已有I/O調(diào)度算法的限制，本文設(shè)計(jì)實(shí)現(xiàn)了在強(qiáng)一致性要求下優(yōu)化I/O并行性的調(diào)度策略。其通過(guò)在架構(gòu)設(shè)計(jì)上結(jié)合多副本主從模型的特點(diǎn)，簡(jiǎn)化了調(diào)度過(guò)程中的一致性確定、請(qǐng)求定序、協(xié)作通信等過(guò)程。其負(fù)載合并器將單位時(shí)間窗口內(nèi)I/O請(qǐng)求的一致性需求進(jìn)行確定、簡(jiǎn)化，提交至數(shù)據(jù)相關(guān)性檢查器。數(shù)據(jù)相關(guān)性檢查器記錄并確定I/O請(qǐng)求的執(zhí)行優(yōu)先級(jí)，轉(zhuǎn)交至負(fù)載均衡器。負(fù)載均衡器根據(jù)副本集合節(jié)點(diǎn)的性能模型將I/O請(qǐng)求分散執(zhí)行，并使其滿足數(shù)據(jù)相關(guān)性要求。利用原型系統(tǒng)，我們通過(guò)實(shí)驗(yàn)證明本文策略可以在保障強(qiáng)一致性的同時(shí)優(yōu)化I/O并行性，提高系統(tǒng)資源利用率并取得高度可預(yù)測(cè)的存儲(chǔ)服務(wù)質(zhì)量。其中，負(fù)載合并可有效提高存儲(chǔ)資源利用率，使得系統(tǒng)GET吞吐量最大提升6.4%；較常見(jiàn)一致性保障策略(主副本調(diào)度策略)，本文策略可使得GET請(qǐng)求吞吐量最大提升41.8%， GET請(qǐng)求平均延遲最大降低42.5%，GET請(qǐng)求99.9th延遲最大降低15.8倍，使系統(tǒng)性能達(dá)到最終一致性下基準(zhǔn)調(diào)度策略C3的性能水平；數(shù)據(jù)相關(guān)性導(dǎo)致吞吐量下降幅度不超過(guò)7.2%。