隨著全球數據量的不斷增長以及各種應用程序的層出不窮，如何高效而又可靠地存儲如此龐大的數據成為近年來人們研究的熱點問題。本文主要針對基于HBase的地理分布副本管理機制進行了一些論述，文章是一篇科技職稱論文發表范文。

　　摘要：針對分布式存儲系統中數據通常在多個數據中心有冗余的副本進行備份，需要健壯的機制維護各個副本的一致性，對分布式系統的副本復制理論作了深入研究后，提出了一套管理地理分布副本的算法。微軟研究院提出服務等級協議，把用戶對一致性的要求分成若干級別，每個級別與用戶可容忍的延遲有關。系統保證在可容忍的延遲范圍內，用戶能擁有較高的服務等級。Tuba系統拓展了Pileus，允許系統根據所有用戶發送的統計信息動態地改變主從副本存放的位置，以提高系統的平均性能，但Tuba系統的復制只是基于單個目標單位進行。對Tuba系統中的方法作出改進，提出了一套改變主從副本存放位置的算法，并在HBase分布式系統的副本復制中實現了該機制。系統完成后，通過實驗驗證了在改變主從副本存放位置時綜合考慮兩個region的相關性可以提高系統整體的效用。

　　關鍵詞：分布式系統,一致性,服務等級協議,復制,地理分布

　　0引言

　　分布式存儲系統，如非關系型數據庫(Not only SQL， NoSQL)，被設計用來滿足從社交網絡到電子商務等各種不同應用的需求。一個大型的應用往往擁有多個數據中心，每個數據中心內都存在分布式存儲系統。為了向用戶提供高性能的服務，一份數據通常會在多個數據中心內都有拷貝。這就需要一個健壯的機制來維護不同系統間數據的一致性。根據CAP(Consistency，Availability，Partition tolerance)理論[1]，一致性和可用性無法同時滿足，因此需要根據實際應用的特點在一致性和可用性之間作權衡。

　　分布式系統間的復制有多種模式，主從復制作為最常見的一種模式，已被各種商業軟件實現。對于主從復制來說，需要確定主從副本分別位于哪些數據中心里。本文主要研究基于地理位置分布的復制方法，這種方法把用戶的位置信息作為權衡一致性和可用性的依據。很多應用都是直接面向全球的互聯網用戶，并提供多個數據中心供用戶選擇。理想情況下，用戶會優先選擇距離最近的數據中心，但最近的數據中心不一定擁有最新的數據。根據用戶訪問數據時的位置來確定主從副本應該位于哪些數據中心，可以有效地提高整體應用的性能。

　　分布式系統間的復制都是基于一定單位的，比如關系型數據庫里的一張表就可以作為一個復制單位。本文使用了客戶端服務等級協議，在放置主從副本位置時綜合考慮不同復制單位間的相關性來使整個系統達到更好的性能，并在HBase集群間實現了這種復制方法。

　　1副本管理的基本機制及研究現狀

　　副本機制是提高系統可靠性和可用性的重要方法。通過在多臺機器上部署和相互協調來使所有的副本達到一致的狀態，如果某些副本在提供服務的過程中出現了故障，整個系統并不會受影響，仍然可以正常提供服務。

　　一致性問題廣泛存在于分布式文件系統、數據庫、緩存等分布式系統中，分布式系統必須保證每一步操作都是由一個一致的狀態進入到下一個一致的狀態。一致性按照由強到弱可包含如下幾類：強一致性[2]、順序一致性、因果一致性和弱一致性[3-4]。

　　副本管理的研究包括很多個方面，其中狀態機和事務處理是當前研究得比較多的方向。在狀態機方法[2]中，來自不同客戶端的請求按順序被所有的可用副本依次執行，最終所有的副本會達到相同的狀態[5-6]。基于事務的復制是一種多主副本的被動性復制方法[7]。在這種方法中，副本之間的協作通信并不要求在客戶端請求之前完成，每個請求都會被特定的一個副本使用原子事務的方式執行。在事務方法中，原子廣播比原子提交更有優勢，比如避免了死鎖的發生[8]。狀態機和事務機制都有各自的優缺點，兩者之間并沒有絕對的優劣之分，只能根據合適的應用場景選擇相對應的方法[9]，選擇時的度量參數可以包括工作負載的類型、多核CPU的并行性以及網絡擁塞狀況等。

　　在不同的數據中心，用戶訪問量會出現顯著的差異。用戶量大的數據中心應該具有更多數據的副本，用戶量小的數據中心只需擁有某一部分數據的副本即可滿足用戶的需求。因此，如果系統能夠根據用戶的訪問情況對數據的副本存放位置作出相應調整，即可有效提升系統性能，節約存儲空間[10-11]。

　　2地理分布副本管理系統GeoHBase設計

　　本章對Tuba[12-13]系統作出了改進，在改變副本位置時，綜合考慮多個復制單位的情況，并提出了自己的一套改變副本位置的算法。本文將該系統命名為GeoHBase。下面先介紹服務等級協議，再給出系統的整體概述，接著描述配置服務的功能。

　　2.1服務等級協議

　　用戶在使用由多個數據中心組成的系統時，針對每一個讀寫操作，需要確定把請求發送給哪一個數據中心。不同的數據中心對用戶的選擇有兩個影響：第一是延遲，這個與用戶的地理位置相關;第二是數據中心可滿足的一致性級別，即這個數據中心內的數據是不是當前的最新版本。延遲和一致性級別即可確定服務等級協議SLA(Service Level Agreement)[13]中的一個條目。多個條目按照優先級排列即構成了應用的SLA。一個典型的SLA如表1所示。

　　排名一致性級別延遲/s效用

　　1強一致性0.11.0

　　2順序一致性0.30.8

　　3弱一致性1.00.2

　　表1中包含3個條目，每個條目包括一致性級別、延遲和效用信息，表示的含義是若在某一延遲之內可以滿足特定的一致性級別，則獲得相應的效用，效用值用來決定SLA條目的優先級。若應用能容忍較寬松的一致性，并且在滿足較高一致性時有較好的性能，那么該應用適合使用SLA。

　　2.2系統設計概述 　　系統的整體設計如圖1所示。非關系型數據庫使用tablet[12]表示一定范圍內的數據，對于每一個復制單位tablet來說，可能有多個主從副本。圖中表示數據中心A中沒有tablet的副本，數據中心B中存放主副本，數據中心C中存放從副本。所有的寫操作只能在主副本上進行，主從副本都可以響應讀請求。當主副本響應讀請求時，客戶端得到的數據是強一致性的，當從副本響應讀請求時，只能提供較弱的一致性級別。配置服務可單獨運行在一臺服務器上。客戶端表示具體的用戶應用。

　　系統內的通信主要有4種：

　　1)客戶端與配置服務之間。客戶端在會話運行期間，把每一個讀寫請求的情況都記錄下來，并且定期向配置服務發送到各數據中心的延遲信息、使用的SLA以及SLA的命中率，并從配置服務那里獲取tablet的配置信息，即主從副本分別存放在哪些數據中心內。

　　2)配置服務與數據中心之間。配置服務根據客戶端的請求，決定tablet的主從副本分別位于哪些數據中心內，當配置信息改變時，即需要告知相應的數據中心。

　　3)數據中心與數據中心之間。從副本要定期從主副本處更新數據，當配置信息改變時，主從副本需完成相應的更新操作。

　　4)客戶端與數據中心之間。客戶端需要定期維護到數據中心之間的延遲信息。當獲取到特定tablet的配置信息時，即根據自身的SLA來選取相應的副本進行讀寫操作。

　　2.3配置服務功能

　　配置服務運行在單獨的一臺服務器上，接收客戶端發來的請求與統計信息。對于每個tablet，配置服務為每個客戶端維護如表2所示的結構信息。

　　成員名成員作用

　　count總請求次數

　　slas客戶端對該tablet使用的服務等級協議

　　slaRatio服務等級協議各條目的命中率

　　latency客戶端到各數據中心的平均延遲

　　配置服務在對配置進行修改時，首先考慮對主副本存放位置的修改，等確定主副本位置后，再考慮對從副本位置的修改。選擇不同配置方案的依據是把總效用值除以總開銷后得到的結果作為最終的效用值，選擇最大的那個作為最終的配置方案。在單個tablet的情況下，我們把總開銷設置為常量1，故直接使用原本的效用值即可，在下面的算法中就只顯示了原效用的情況。在多個tablet的情況下，總開銷要小于1，以表示對資源的節約情況，這一點在后面介紹多主副本融合算法時會有更加詳細的描述。

　　考慮對主副本修改時，算法1先根據客戶端的統計數據，生成所有可能的配置方案。

　　算法先遍歷所有客戶端結構信息，對所有服務等級協議中含有強一致性條目的客戶端結構信息判斷其強一致性條目命中率的高低。若命中率低于一定的閾值，就考慮將主副本靠近該客戶端。算法根據客戶端結構信息，選出離該客戶端最近的數據中心，若該數據中心已經是主副本，則沒有為該客戶端生成主副本; 否則，將該數據中心變為主副本，生成了一個新的配置。算法中的BASE_RATIO為預先定義的常量值。

　　Input： client_param_set， currentConf

　　1

　　Function GeneratePrimaryConfigurations(client_param_set，

　　currentConf)

　　2)

　　confs={};

　　3)

　　foreach param in client_param_set

　　4)

　　if(param.sla[0]=STRONG_CONSISTENCY &&

　　5)

　　param.slaRatio[0]< BASE_RATIO)

　　6)

　　tmpLatency=∞;

　　7)

　　Tartget=-1;

　　8)

　　for i in [0...param.latency.length]

　　9)

　　if(param.latency[i] < tmpLatency)

　　10)

　　tmpLatency=param.latency[i];

　　11)

　　Target=i;

　　12)

　　if(tmpLatency < param.sla[0].latency &&

　　13)

　　NotPrimary(currentConf，Target))

　　14)

　　tmpConf=CreateConf(currentConf， i);

　　15)

　　if(CheckPrimaryConfigurations(tmpConf))

　　16)

　　confs=confs+tmpConf;

　　17)

　　return confs;

　　18)

　　end function

　　程序后

　　在生成主副本的所有可選方案后，配置服務還需對其作驗證。此處主要檢查系統的約束條件，比如有的副本不經常使用，最多只能存3份，有的副本訪問頻率很高，最少要存2份等。通過驗證的主副本配置方案可能還有很多種，此時需要根據不同配置方案下系統的整體效用來選取針對該tablet的最優方案。

　　很多時候客戶端要訪問的數據涉及到多個tablet，配置服務可以綜合多個tablet的情況進行配置，本文只考慮每個tablet均只有一個主副本的情況。對每一個客戶端，配置服務會根據不同tablet的client_param結構生成這些tablet的關聯結構體，如表3所示。 　　表格(有表名)

　　表3client_associate結構體

　　成員名成員作用

　　params客戶端的統計信息

　　sites各個集群的編號

　　confs臨時配置方案

　　utility臨時配置方案對應的效用值

　　對于強一致性級別，如果客戶端要訪問的多個tablet的主副本在不同的數據中心里，則客戶端需要向多個數據中心同時發送連接請求，造成更多的開銷。如果多個tablet的主副本在同一個數據中心內，則配置服務在計算系統整體性能時，會考慮到對資源的節省情況，即消耗值會小于1，以此作為選擇配置方案的依據。算法2中的COST為常量。

　　算法2融合主副本配置算法。

　　程序前

　　Input： params， utility， confs， sites

　　1

　　Function MergePrimaryConfigurations(params， utility， confs，

　　sites)

　　2)

　　util=0;

　　3)

　　bestConf={};

　　4)

　　for i in [0...utility.length]

　　5)

　　util=util+utility[i][0];

　　6)

　　bestConf=bestConf+confs[i][0];

　　7)

　　for i in [0...sites.length]

　　8)

　　tmpUtil=0;

　　9)

　　tmpConf={};

　　10)

　　num=0;

　　11)

　　for j in [0...confs.length]

　　12)

　　for m in [0...confs[j].length]

　　13)

　　if(sites[i]=confs[j][m].primary)

　　14)

　　for k in [0...params[j].length]

　　15)

　　for n in [0...params[j][k].slas.length]

　　16)

　　if(params[j][k].slas[n].consistency=

　　STRONG_CONSISTENCY&&

　　latency[j][sites[i]]<

　　params[j][k].slas[n]].latency)

　　17)

　　tmpUtil=tmpUtil+utility[j][m]/COST;

　　18)

　　num=num+1;

　　19)

　　tmpConf=tmpConf+confs[j][m];

　　20)

　　if(num=confs.length && util < tmpUtil)

　　21)

　　util=tmpUtil;

　　22)

　　bestConf=tmpConf;

　　23)

　　return bestConf;

　　24)

　　end function

　　程序后

　　該算法在初始化時擁有每一個tablet的臨時配置方案，且按照效用值由高到低排好序，分別對每個tablet調用算法1即可得到對應的臨時配置方案。首先分別取出各個tablet效用值最大的配置方案，將其累加得到一個初始的效用值; 接著對于每一個集群，從每個tablet的配置方案中選擇出主副本在該集群上的配置方案，并計算其效用值，此時代價值不再是1，而是小于1的常量，以表示對資源的節省情況; 得到所有tablet的效用值之和后與初始的效用值比較，若高于初始值，則用該值替換掉初始值，并記錄下各個tablet對應的配置信息。以此類推，遍歷所有的集群，最終得到最大的效用值，函數返回此時各個tablet的配置信息。

　　配置服務在考慮重新改變配置信息時，先確定對主副本的放置策略，如果未生成新的配置，才考慮從副本的情況。對于從副本，先考慮縮小從副本的同步時間。若是這一步沒有生成新的配置，再考慮添加、刪除從副本。改變從副本的粗略和改變主副本的策略類似，這里不再贅述。

　　配置服務負責周期性地改變所有tablet的配置信息，以提高系統整體的效用。配置服務共有以下幾種配置策略：調整從副本與主副本同步的時間間隔、添加或刪除從副本、改變主副本的位置。

　　3測試及實驗

　　本文系統實現基于HBase，通過修改HBase源代碼來實現上一章所描述的GeoHBase系統。對于主副本融合算法，本文只考慮了兩個region的相關情況。客戶端的讀寫操作是對HBase提供的客戶端API進行了封裝，以實現與配置服務的通信。

　　實驗部署了3個HBase集群，分別編號為0、1、2。每個集群內部包含1臺主服務器和3臺region服務器。由于沒有地理位置隔離的數據中心可供使用，本文在實驗時通過在讀寫過程中增加一定的延遲值來模擬不同數據中心之間的延遲情況，如圖2所示。

　　圖片

　　圖2集群間的延遲情況

　　以上3個集群分別位于不同的地理位置，客戶端訪問與自己地理位置相同的集群時不需要額外添加延遲，否則需要根據集群的地理位置添加適當的延遲信息。 　　為了模擬不同地理位置的客戶端在訪問數據時的特點，本文假設客戶端的訪問次數服從正態分布，其標準差為3，數學期望值在不同集群間的偏移量為8，以表明不同地理位置在時區上的差異。3個集群周圍客戶端訪問次數的概率密度曲線如圖3所示。

　　圖片

　　圖3客戶端訪問次數的概率密度曲線

　　本文在實驗過程中創建了一張表table1，列族名為colfam1，根據行鍵值row0、row1、row2、row3、row4共劃分出6個region，實驗過程中只關注其中有首尾行健值的4個region，分別為table1row0row1、table1row1row2、table1row2row3、table1row3row4。配置服務給4個region分配默認的配置信息，即0號集群為主副本，1號集群為從副本，從副本的同步時間為5min。接著在0號集群上往每個region里插入100行數據，等待從副本更新數據后，完成初始化操作。客戶端使用統一的服務等級協議，如表4所示。

　　YCSB(Yahoo! Cloud Serving Benchmark)[14]是雅虎公司用來對云服務進行基礎測試的工具，其中B類型負載包括95%的讀操作和5%的寫操作，本文在客戶端都使用這種類型的負載。實驗過程中分別在三個集群所在的地理位置各模擬1000次客戶端操作，對于一個特定的地理位置，客戶端在不同時間段訪問次數的概率情況如圖3所示。客戶端在每次進行讀寫數據時隨機從上述region選定一個作為操作對象，再從該region里隨機讀寫一行的數據。

　　實驗過程中考慮3種情況：始終不改變配置、只改變主副本存放位置和同時運用3種改變算法。這3種情況的服務等級協議命中率如圖4所示。

　　圖4中橫坐標中的1、2、3分別表示強一致性、順序一致性和弱一致性級別。由圖可以看出，改變主副本配置可以有效提高強一致性的命中率，同時運用3種改變配置方案的算法可以有效提升強一致性和順序一致性的命中率，從而提高系統整體的性能。

　　為了觀察考慮兩個region之間的相關性對系統性能的提升，實驗過程中考慮table1row3row4和table1row2row3這兩個region的關聯情況。把靠近0號、1號、2號集群的客戶端分別用客戶端A、B、C代替。將table1row2row3記作region P，table1row3row4記作region Q。客戶端A訪問region P共400次，訪問region Q共400次。客戶端B訪問region P共550次，訪問region Q共700次。客戶端C訪問region P共600次，訪問region Q共500次。

　　對于region P，綜合所有客戶端的服務等級協議命中率，強一致性為24.8%，順序一致性為20.4%，弱一致性為54.8%。若單獨考慮該region的情況，配置服務會根據客戶端B、C的強一致性命中率創建兩種臨時配置方案，分別將1號集群和2號集群作為主副本，這兩種配置方案的效用值分別為523、570，而原配置方案(0號集群為主副本)的效用值僅為380。最終配置服務將根據效用值選擇2號集群作為該region的配置方案。

　　對于region Q，綜合所有客戶端的服務等級協議命中率，強一致性為24.8%，順序一致性為10.4%，弱一致性為64.8%。若單獨考慮該region的情況，配置服務會根據客戶端B、C的強一致性命中率創建兩種臨時配置方案，分別將1號集群和2號集群作為主副本，這兩種配置方案的效用值分別為665、475，而原配置方案(0號集群為主副本)的效用值僅為380。最終配置服務將根據效用值選擇1號集群作為該region的配置方案。

　　單獨考慮P和Q兩個region時，P的主副本在2號集群上效用最高，Q的主副本在1號集群上效用最高，此時兩者的效用值之和為1235。綜合考慮region P和region Q的相關性，把算法2中的COST值設為0.9，則P、Q兩個region主副本在同一個集群上時，效用值會有提升，如表5所示。

　　表5說明當兩個region的主副本都在1號集群上時，可以達到的總效用是1320，高于單獨考慮時的最大效用值之和。因此配置服務會更新P、Q兩個region的配置信息，將1號集群作為主副本，并將配置信息通知給各個集群。

　　本章通過在讀寫操作的延遲基礎上添加一個額外的延遲值來模擬不同地理位置的數據中心之間的延遲，并對改變配置信息的3種方案分別進行了測試，發現改變主副本存放位置時對系統性能的提高最為明顯。縮小從副本同步時間和改變從副本的存放位置，都能一定程度提高順序一致性的命中率。實驗最后分析了改變主副本配置信息時，考慮兩個region之間的相關性對系統整體效用的提高情況。實驗結果表明，綜合考慮兩個region時的效用要高于分別考慮單個region的效用。

　　4結語

　　本文通過研究微軟研究院的Tuba系統，自主提出了一套改變主從副本存放位置的算法，并在管理副本時考慮兩個目標單元之間的相關性，從而提升了系統的整體性能。本文在分布式存儲系統HBase中實現了上述副本管理的機制即GeoHBase，并通過實驗說明了綜合考慮不同region的相關性確實可以提升系統整體性能。

　　參考文獻：

　　[1]SILBERSCHATZ A， KORTH H F， SUDARSHAN S. Database system concepts[M]. New York： McGrawHill Science/Engineering/Math， 2010：852.

　　[2]SCHNEIDER F B. Implementing faulttolerant services using the state machine approach： a tutorial[J]. ACM Computing Surveys， 1990， 22(4)： 299-319. 　　[3]TERRY D B， THEIMER M M， PETERSEN K， et al. Managing update conflicts in Bayou， a weakly connected replicated storage system[C]// Proceedings of the 15th ACM Symposium on Operating System Principles. New York： ACM， 1995： 172-183.

　　[4]MAHAJAN P， SETTY S， LEE S， et al. Depot： cloud storage with minimal trust[J]. ACM Transactions on Computer Systems， 2011， 29(4)： 12.

　　科技職稱論文發表期刊推薦《計算機工程與應用》雜志是由中華人民共和國工業和信息化部華北計算技術研究所主辦的、面向中高級計算機專業工作者的學術刊物。《計算機工程與應用》是一本面向計算機全行業的綜合性學術刊物，覆蓋面寬、信息量大、報道及時是本刊的服務宗旨。