分布式系統(tǒng)數(shù)據(jù)復(fù)制的研究

張 倩，辛大欣

（西安工業(yè)大學(xué)，陜西 西安 710021）

0 引 言

在分布式存儲(chǔ)系統(tǒng)中，對(duì)數(shù)據(jù)的拷貝能夠增強(qiáng)性能，提供高可用性和容錯(cuò)能力，因此它是保證分布式系統(tǒng)有效性的一個(gè)關(guān)鍵技術(shù)。將創(chuàng)建的多個(gè)數(shù)據(jù)副本合理地分布在多個(gè)服務(wù)器節(jié)點(diǎn)上，用來(lái)分擔(dān)訪問(wèn)請(qǐng)求的處理任務(wù)，可以在一定程度上降低節(jié)點(diǎn)失效率，縮短用戶響應(yīng)時(shí)間[1?2]。本文將討論在數(shù)據(jù)復(fù)制過(guò)程中，副本管理器采用何種復(fù)制方式能夠更準(zhǔn)確高效地完成數(shù)據(jù)副本的更新工作，分布式系統(tǒng)的復(fù)制模型，以及數(shù)據(jù)拷貝的方式。

1 復(fù)制數(shù)據(jù)管理

在分布式存儲(chǔ)系統(tǒng)中不僅數(shù)據(jù)量巨大，而且為了保證系統(tǒng)的可靠性，每份數(shù)據(jù)對(duì)象的副本數(shù)量也很多，因此，維護(hù)各個(gè)節(jié)點(diǎn)中副本的一致性就成了一個(gè)很重要的問(wèn)題[3]。在計(jì)算機(jī)科學(xué)領(lǐng)域中，數(shù)據(jù)的一致性問(wèn)題已經(jīng)存在了很長(zhǎng)的時(shí)間，構(gòu)成了分布式計(jì)算的基礎(chǔ)[4]。而實(shí)際上，統(tǒng)計(jì)學(xué)和管理科學(xué)是對(duì)于一致性問(wèn)題較正式的研究源頭[5]。

1.1 數(shù)據(jù)復(fù)制的基本原則

當(dāng)執(zhí)行一個(gè)操作時(shí)，用戶不需要知道存在多少個(gè)數(shù)據(jù)副本，僅僅對(duì)其中一項(xiàng)操作，而不管事實(shí)上的操作可能是針對(duì)一個(gè)以上的拷貝一起進(jìn)行的，這是數(shù)據(jù)復(fù)制的其中一項(xiàng)原則即復(fù)制透明性。一致性是數(shù)據(jù)復(fù)制的另一項(xiàng)基本原則，然而，在不同的具體情況下，數(shù)據(jù)一致性在強(qiáng)度上是會(huì)有所不同的。給定對(duì)象的副本不一定是完全相同的，至少不要求在任何時(shí)間點(diǎn)都一樣，一些副本可能已經(jīng)更新了最新的數(shù)據(jù)，但是一些副本可能還沒(méi)有收到這個(gè)更新。但是如果不同的客戶對(duì)同一個(gè)對(duì)象發(fā)出請(qǐng)求，卻得到不一致的結(jié)果，這通常是不可接受的。

1.2 系統(tǒng)模型

副本由不同的副本管理器（Replica Manager，RM）來(lái)管理，副本管理器是包含了特定計(jì)算機(jī)上的副本，并且直接操作這些副本的組件。副本管理器所組成的集合可以是靜態(tài)的，也可以是動(dòng)態(tài)的。在動(dòng)態(tài)系統(tǒng)中，新的副本管理器可能會(huì)不斷出現(xiàn)，副本管理器可能崩潰，接著他們被認(rèn)為離開(kāi)了系統(tǒng)。而這在靜態(tài)的系統(tǒng)中不允許出現(xiàn)新的副本管理器，也不會(huì)出現(xiàn)新的副本管理器，但它們可能暫停工作很長(zhǎng)時(shí)間。

如圖1所示副本管理的一般模型，副本管理器集合給用戶提供了某種服務(wù)。副本管理器存儲(chǔ)在服務(wù)器上，前端（Front End，F(xiàn)E）組件作為用戶訪問(wèn)服務(wù)器的門戶，每個(gè)客戶發(fā)出的請(qǐng)求首先被一個(gè)前端組件處理，它的作用是由消息傳遞的方式，代替客戶，與多個(gè)副本管理器進(jìn)行通信，而不是直接讓客戶進(jìn)行通信。這種手段保證了復(fù)制透明性[6]。

圖1 用于復(fù)制數(shù)據(jù)管理的基本的體系結(jié)構(gòu)模型

副本對(duì)象上進(jìn)行的一個(gè)操作通常涉及5個(gè)階段，但是對(duì)于不同類型的系統(tǒng)，每個(gè)階段的動(dòng)作都是不一樣的。

（1）請(qǐng)求。前端將來(lái)自客戶的請(qǐng)求分給一個(gè)或多個(gè)副本管理器。一種形式是前端只和某一個(gè)副本管理器通信，然后由這個(gè)副本管理器與其他副本管理器通信；另一種形式是將這些副本管理器看成一個(gè)組，由前端將請(qǐng)求組播到各個(gè)副本管理器；

（2）協(xié)調(diào)。接到請(qǐng)求后，副本管理器需要進(jìn)行協(xié)調(diào)來(lái)保證執(zhí)行的一致性，它們會(huì)對(duì)是否執(zhí)行請(qǐng)求達(dá)成一致，并同時(shí)決定該請(qǐng)求相對(duì)于其他請(qǐng)求的次序；

（3）執(zhí)行。副本管理器執(zhí)行請(qǐng)求，也包括執(zhí)行的效果可以去除的試探性請(qǐng)求；

（4）協(xié)定。副本管理器對(duì)將要提交的處理結(jié)果達(dá)成一致；

（5）響應(yīng)。一個(gè)或多個(gè)副本管理器給前端應(yīng)答。一種形式是由一個(gè)副本管理器響應(yīng)前端，還有一種情況是由前端接受一組副本管理器的應(yīng)答，然后選擇或綜合成一個(gè)結(jié)果返回給客戶。

副本的撤銷也是一種必要情況，引起副本撤銷的原因有很多，例如副本所在節(jié)點(diǎn)的存儲(chǔ)空間不夠；副本生命周期結(jié)束；副本所在節(jié)點(diǎn)的處理能力達(dá)到極限；副本被訪問(wèn)的頻率很低。生成一個(gè)副本的代價(jià)是比較高的，所以無(wú)謂的副本刪除要盡量避免[7]。

1.3 副本復(fù)制策略

副本復(fù)制策略有5種，路徑復(fù)制、源請(qǐng)求復(fù)制、優(yōu)先級(jí)復(fù)制、鄰居節(jié)點(diǎn)復(fù)制和隨機(jī)復(fù)制[8?9]：

（1）路徑復(fù)制。將副本發(fā)送給請(qǐng)求路徑上的所有節(jié)點(diǎn)。實(shí)現(xiàn)原理簡(jiǎn)單是它的優(yōu)點(diǎn)，也很方便數(shù)據(jù)的查找；但是創(chuàng)建的副本數(shù)量會(huì)遠(yuǎn)遠(yuǎn)大于需求量，這就會(huì)增加維護(hù)副本的一致性的開(kāi)銷；

（2）源請(qǐng)求復(fù)制。只將副本發(fā)送給請(qǐng)求節(jié)點(diǎn)。當(dāng)對(duì)目的節(jié)點(diǎn)請(qǐng)求時(shí)，若目的節(jié)點(diǎn)沒(méi)有過(guò)載，那么就可以讀取數(shù)據(jù)，若目標(biāo)節(jié)點(diǎn)沒(méi)有多余的能力處理，就創(chuàng)建一個(gè)新副本，并且是在請(qǐng)求節(jié)點(diǎn)未過(guò)載的情況下，才把創(chuàng)建的新副本發(fā)給它，同時(shí)通知路徑上所有節(jié)點(diǎn)此請(qǐng)求節(jié)點(diǎn)上也存儲(chǔ)了該數(shù)據(jù)副本；

（3）優(yōu)先級(jí)復(fù)制。優(yōu)先將副本發(fā)送向已經(jīng)有副本的節(jié)點(diǎn)，直至這些節(jié)點(diǎn)達(dá)到飽和，再選擇其他節(jié)點(diǎn)來(lái)存儲(chǔ)數(shù)據(jù)副本；

（4）鄰居節(jié)點(diǎn)復(fù)制。保存所有網(wǎng)絡(luò)數(shù)據(jù)的訪問(wèn)歷史記錄，新建一份訪問(wèn)率較高的副本，并發(fā)送給頻繁請(qǐng)求該副本的節(jié)點(diǎn)的鄰節(jié)點(diǎn)，當(dāng)該節(jié)點(diǎn)再次請(qǐng)求訪問(wèn)該數(shù)據(jù)時(shí)，就可以到它的鄰居節(jié)點(diǎn)上直接讀取數(shù)據(jù)；

（5）隨機(jī)復(fù)制。在選擇一個(gè)或多個(gè)節(jié)點(diǎn)來(lái)存放數(shù)據(jù)副本時(shí)，采用隨機(jī)的方式，而隨機(jī)選擇的對(duì)象分為兩種，請(qǐng)求路徑上的節(jié)點(diǎn)以及整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)。

2 容錯(cuò)服務(wù)

如果在副本管理器發(fā)生故障的條件下，服務(wù)還能夠保持響應(yīng)用戶請(qǐng)求，同時(shí)用戶并不能區(qū)分該服務(wù)是在副本數(shù)據(jù)上實(shí)現(xiàn)的，還是被一個(gè)正確的副本管理器提供的，那么這個(gè)基于復(fù)制的服務(wù)就是正確的。

在可靠性理論中，一般都會(huì)用RAS來(lái)描述系統(tǒng)的健壯與完整性。RAS也就是可靠性（Reliability），可用性（Availability）和可維護(hù)性（Serviceablility）[10]。

2.1 線性化能力

假設(shè)一個(gè)系統(tǒng)中的兩個(gè)副本管理器分別位于A和B兩個(gè)計(jì)算機(jī)上，它們都維護(hù)x和y兩個(gè)銀行賬戶的副本?？蛻粼诒镜赜?jì)算機(jī)上查看和更新賬戶，如果本地的服務(wù)器出現(xiàn)故障，那么使用另一個(gè)服務(wù)器。當(dāng)對(duì)客戶的操作響應(yīng)結(jié)束后，副本管理器會(huì)在后臺(tái)相互傳播更新。x和y的初始余額為0.00。如表1所示。

客戶1在本地的副本管理器A上更新賬戶x余額為1.00，然后更新y余額為2.00，但是此時(shí)A發(fā)生故障，于是客戶1將這個(gè)操作放在副本管理器B上?，F(xiàn)在客戶2在他的本地副本管理器B上讀取數(shù)據(jù)，查詢到y(tǒng)余額為2.00，但x仍為0.00，這是因?yàn)锳發(fā)生故障，應(yīng)用在它上的x的更新還沒(méi)有傳遞過(guò)來(lái)。

這個(gè)執(zhí)行不符合銀行賬戶的規(guī)約，也就是不正確的，而對(duì)于復(fù)制對(duì)象有不同的正確性準(zhǔn)則，最嚴(yán)格的正確系統(tǒng)是可線性化的，這個(gè)性質(zhì)就是可線性化能力。

表1 不同客戶更新及查詢數(shù)據(jù)

一個(gè)被復(fù)制的共享對(duì)象服務(wù)，如果對(duì)于任何執(zhí)行，存在一個(gè)由全體用戶發(fā)出的執(zhí)行序列，并滿足下面的兩個(gè)準(zhǔn)則，那么這個(gè)服務(wù)就認(rèn)為是可線性化的：

（1）操作的交錯(cuò)序列，符合對(duì)象的單個(gè)正確副本所遵循的規(guī)約。

（2）操作的交錯(cuò)執(zhí)行次序與實(shí)際運(yùn)行中的次序?qū)崟r(shí)一致。

2.2 順序一致性

線性化能力中要求的實(shí)時(shí)性是現(xiàn)實(shí)中所需要的，客戶應(yīng)該收到最新最近的數(shù)據(jù)。但是這是一種理想條件，受到網(wǎng)絡(luò)延遲及其他因素的制約。一個(gè)更能滿足現(xiàn)實(shí)需要并且相對(duì)嚴(yán)格的條件是順序一致性（Sequential Consistency）。在不要求實(shí)時(shí)的情況下，這個(gè)條件抓住了處理請(qǐng)求的順序?qū)嵸|(zhì)。它規(guī)定：如果所有的進(jìn)程以一定的順序執(zhí)行操作，每一個(gè)進(jìn)程的操作都以程序規(guī)定的順序出現(xiàn)，則任何操作的結(jié)果都是一樣的。順序一致存儲(chǔ)器不保證讀返回的值是1 nm，1 ms甚至1 min以前另一個(gè)進(jìn)程寫入的，它只保證所有進(jìn)程以相同的順序看見(jiàn)存儲(chǔ)器訪問(wèn)[11]。

一個(gè)被復(fù)制的共享對(duì)象服務(wù)，如果對(duì)于任何執(zhí)行，存在一個(gè)由全體用戶發(fā)出的執(zhí)行序列，并滿足下面的2個(gè)準(zhǔn)則，那么這個(gè)服務(wù)就認(rèn)為是順序一致的：

（1）操作的交錯(cuò)序列符合對(duì)象的單個(gè)正確副本所遵循的規(guī)約。

（2）操作在交錯(cuò)執(zhí)行中的次序，和在每個(gè)客戶程序中執(zhí)行的次序一致。

2.3 被動(dòng)復(fù)制

在圖2中的復(fù)制模型中，任何時(shí)候都有一個(gè)主副本管理器和至少一個(gè)次副本管理器，稱為“從管理器”或“備份”。這個(gè)模型的實(shí)質(zhì)就是在上面2.2節(jié)中提到的前端與服務(wù)交互方式中的一種情況，前端只和主副本管理器通信，然后由主副本管理器執(zhí)行操作并將更新操作發(fā)送到服務(wù)中的其他備份管理器。如果主副本管理器出現(xiàn)故障，那么將從剩余的備份管理中提升一個(gè)稱為新的主副本管理器。

圖2 被動(dòng)（主備份）模型

在主備份管理器出現(xiàn)故障時(shí)，如果某個(gè)備份變成新的主備份管理器并且新的系統(tǒng)配置從故障點(diǎn)正確接管的話，即滿足下面條件時(shí)，系統(tǒng)仍具有線性化能力：

（1）主副本管理器被惟一的備份副本管理器代替

（2）當(dāng)接管主副本管理器時(shí)，剩余的副本管理器在哪些操作已經(jīng)被執(zhí)行上達(dá)成一致。

被動(dòng)復(fù)制的缺點(diǎn)是開(kāi)銷相對(duì)較大，試圖同步通信在每次組播時(shí)需要要幾個(gè)回合的通信，而且當(dāng)主副本管理器發(fā)生故障時(shí)，組通信系統(tǒng)需要進(jìn)行協(xié)商并傳遞試圖，這會(huì)導(dǎo)致更多的延時(shí)。

考慮到當(dāng)用戶較多，與服務(wù)通信數(shù)量較大的問(wèn)題，可以將這個(gè)模型做一些改進(jìn)，客戶可以將讀的請(qǐng)求發(fā)送給備份副本管理器，這樣可以減輕主副本管理器的負(fù)載，雖然不能保證線性化，但是仍能提供具有順序一致性的服務(wù)給用戶。

2.4 主動(dòng)復(fù)制

如圖3中所示的主動(dòng)復(fù)制模型中，副本管理器是一個(gè)狀態(tài)機(jī)，所有副本管理器被組織成一個(gè)組，并充當(dāng)同等的角色。前端將用戶發(fā)出的請(qǐng)求消息組播到副本管理器組，組內(nèi)的副本管理器按相同但獨(dú)立的方式來(lái)處理請(qǐng)求并作出響應(yīng)。

圖3 主動(dòng)復(fù)制模型

可以看出任何一個(gè)副本管理器的崩潰都不會(huì)對(duì)服務(wù)的性能產(chǎn)生影響，因?yàn)槭Ｏ碌母北竟芾砥髂芾^續(xù)正常處理請(qǐng)求并做出應(yīng)答。這個(gè)系統(tǒng)具有順序一致性，所有的副本管理器處理同樣次序的請(qǐng)求，組播的可靠性保證每一個(gè)正確的副本管理器處理同樣的請(qǐng)求集合，全序保證以同樣的順序處理他們。主動(dòng)復(fù)制系統(tǒng)并不具有線性化能力，因?yàn)楦北竟芾砥魈幚碚?qǐng)求的全排序未必和客戶發(fā)出這些請(qǐng)求的實(shí)時(shí)次序相一致。

3 結(jié) 語(yǔ)

本文分析了分布式系統(tǒng)中的用于復(fù)制數(shù)據(jù)管理的基本的體系結(jié)構(gòu)模型及它的執(zhí)行過(guò)程，進(jìn)而討論了向用戶提供容錯(cuò)服務(wù)的復(fù)制模型，并在這個(gè)基礎(chǔ)上提出了一些改進(jìn)。然而，現(xiàn)實(shí)中的實(shí)際情況是多變而復(fù)雜的，在解決實(shí)際問(wèn)題時(shí)需要根據(jù)具體情況做出相應(yīng)的處理，才能使得系統(tǒng)有更好的可用性和安全性。

[1]徐小龍，鄒勤文，楊康.分布式存儲(chǔ)系統(tǒng)中數(shù)據(jù)副本管理機(jī)制[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013（2）：245?249.

[2]葛建清.異質(zhì)結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)動(dòng)態(tài)副本訪問(wèn)負(fù)載均衡策略研究[D].上海：華東師范大學(xué)，2010.

[3]王泰格，邵玉如，楊翌.分布式存儲(chǔ)系統(tǒng)介紹及其數(shù)據(jù)一致性實(shí)現(xiàn)方法探究[J].企業(yè)技術(shù)開(kāi)發(fā)，2012（8）：18?19.

[4]LYNCH N A.Distributed algorithms[M].San Franciso，CA：Morgan Kaufmann，1997.

[5]DE GROOT M H.Reaching a consensus[J].American Statisti?cal Association，1974，69（345）：118?121.

[6]COULOURIS George，DOLLIMORE Jean，KINDBERG Tim.Distributed systems concepts and design[M].金蓓弘，馬應(yīng)龍，譯.北京：機(jī)械工業(yè)出版社，2013.

[7]陳賡，余宏亮，張堃.對(duì)等網(wǎng)絡(luò)中基于位置信息和文件流行度的自適應(yīng)復(fù)本管理機(jī)制算法[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（10）：1927?1937.

[8]Lü Q，CAO P，COHEN E，et al.Search and replication in un?structured peer?to?peer networks[C]//16th International Conference on Supercomputing.New York： ACM Press，2002：11?15.

[9]BASSAM A A，CHEN W，ZHOU B B，et al.Effects of replica placement algorithms on performance of structured overlay net?works[C]//Parallel and Distributed Processing Symposium.Nice：IPDPS，2007：111?117.

[10]王偉娜.分布式存儲(chǔ)系統(tǒng)中容錯(cuò)子系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].沈陽(yáng)：東北大學(xué)，2008.

[11]楊玲，李俊峰.分布式系統(tǒng)中存儲(chǔ)器的一致性問(wèn)題[J].現(xiàn)在計(jì)算機(jī)，2005（4）：2?9.