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

摘 "要： 在分布式系統(tǒng)中，由于復(fù)制能夠增強(qiáng)性能，提供高可用性和容錯(cuò)能力，因此它是保證分布式系統(tǒng)有效性的一個(gè)關(guān)鍵技術(shù)。為了保證數(shù)據(jù)安全、可用、可靠、可擴(kuò)展性和服務(wù)的高效、連續(xù)性，分布式存儲(chǔ)系統(tǒng)需要完善的數(shù)據(jù)管理機(jī)制。主要討論數(shù)據(jù)復(fù)制的基本原則，用于復(fù)制數(shù)據(jù)管理的基本體系結(jié)構(gòu)模型，副本對(duì)象上進(jìn)行的一個(gè)操作通常涉及的5個(gè)階段，以及在這個(gè)模型下不同的復(fù)制數(shù)據(jù)的方式是如何提供容錯(cuò)服務(wù)的，并在數(shù)據(jù)量大的情況下，對(duì)復(fù)制模型提出改進(jìn)的方式。

關(guān)鍵詞： 分布式系統(tǒng); 數(shù)據(jù)復(fù)制; 副本管理器; 容錯(cuò)

中圖分類(lèi)號(hào)： TN964?34 " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A " " " " " " " " " " " " " "文章編號(hào)： 1004?373X（2015）02?0035?04

Research on data replication of distributed system

ZHANG Qian， XIN Da?xin

（Xi’An Technological University， Xi’an 710021， China）

Abstract： In a distributed system， the replication can enhance performance， improve the capabilities of high availability and fault tolerance， so it is a key technology to ensure the effectiveness of the distributed system. In order to ensure data security， availability， reliability， scalability， efficiency and continuity of service， the distributed storage system needs a perfect data management mechanism. The basic principles of data replication， basic architecture model of the replicated data management， five stages usually involved in an action on a replica object， and principle how to provide fault tolerance service in different data replication modes with this model are discussed. An improving way of the replication model for dealing with large amount of data is proposed.

Keywords： distributed system; data replication; replica manager; fault tolerance

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)訪(fǎng)問(wèn)請(qǐng)求的處理任務(wù)，可以在一定程度上降低節(jié)點(diǎn)失效率，縮短用戶(hù)響應(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í)，用戶(hù)不需要知道存在多少個(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è)更新。但是如果不同的客戶(hù)對(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所示副本管理的一般模型，副本管理器集合給用戶(hù)提供了某種服務(wù)。副本管理器存儲(chǔ)在服務(wù)器上，前端（Front End，F(xiàn)E）組件作為用戶(hù)訪(fǎng)問(wèn)服務(wù)器的門(mén)戶(hù)，每個(gè)客戶(hù)發(fā)出的請(qǐng)求首先被一個(gè)前端組件處理，它的作用是由消息傳遞的方式，代替客戶(hù)，與多個(gè)副本管理器進(jìn)行通信，而不是直接讓客戶(hù)進(jìn)行通信。這種手段保證了復(fù)制透明性[6]。

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201502＼Image＼05t1.tifgt;

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

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

（1） 請(qǐng)求。前端將來(lái)自客戶(hù)的請(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é)果返回給客戶(hù)。

副本的撤銷(xiāo)也是一種必要情況，引起副本撤銷(xiāo)的原因有很多，例如副本所在節(jié)點(diǎn)的存儲(chǔ)空間不夠; 副本生命周期結(jié)束; 副本所在節(jié)點(diǎn)的處理能力達(dá)到極限;副本被訪(fǎng)問(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)銷(xiāo);

（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ù)的訪(fǎng)問(wèn)歷史記錄，新建一份訪(fǎng)問(wèn)率較高的副本，并發(fā)送給頻繁請(qǐng)求該副本的節(jié)點(diǎn)的鄰節(jié)點(diǎn)，當(dāng)該節(jié)點(diǎn)再次請(qǐng)求訪(fǎ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)用戶(hù)請(qǐng)求，同時(shí)用戶(hù)并不能區(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 "線(xiàn)性化能力

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

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

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

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

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

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

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

2.2 "順序一致性

線(xiàn)性化能力中要求的實(shí)時(shí)性是現(xiàn)實(shí)中所需要的，客戶(hù)應(yīng)該收到最新最近的數(shù)據(jù)。但是這是一種理想條件，受到網(wǎng)絡(luò)延遲及其他因素的制約。一個(gè)更能滿(mǎn)足現(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)程寫(xiě)入的，它只保證所有進(jìn)程以相同的順序看見(jiàn)存儲(chǔ)器訪(fǎng)問(wèn)[11]。

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

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

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201502＼Image＼05t2.tifgt;

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

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

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

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

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

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

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

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

lt;E：＼王芳＼現(xiàn)代電子技術(shù)201502＼Image＼05t3.tifgt;

圖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)并不具有線(xiàn)性化能力，因?yàn)楦北竟芾砥魈幚碚?qǐng)求的全排序未必和客戶(hù)發(fā)出這些請(qǐng)求的實(shí)時(shí)次序相一致。

3 "結(jié) "語(yǔ)

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

參考文獻(xiàn)

[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)副本訪(fǎng)問(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 Statistical 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 unstructured 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 networks [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.