趙雪章
(佛山職業(yè)技術(shù)學(xué)院,廣東 佛山 528137)
海量數(shù)據(jù)的一致性研究
趙雪章
(佛山職業(yè)技術(shù)學(xué)院,廣東 佛山 528137)
實(shí)現(xiàn)海量數(shù)據(jù)管理的關(guān)鍵技術(shù)之一是數(shù)據(jù)復(fù)制,維護(hù)多節(jié)點(diǎn)副本間數(shù)據(jù)的一致性是提高分布式數(shù)據(jù)庫的容錯(cuò)能力與性能的重要保證。文章在介紹數(shù)據(jù)一致性基本理論和比較分析各種數(shù)據(jù)一致性維護(hù)方法的基礎(chǔ)上,對(duì)海量數(shù)據(jù)一致性維護(hù)過程中出現(xiàn)的更新傳播模型、更新傳播內(nèi)容及解決更新沖突等進(jìn)行分析,并提出了相應(yīng)的解決辦法。
海量數(shù)據(jù);數(shù)據(jù)一致性;數(shù)據(jù)維護(hù)
海量數(shù)據(jù)的支撐是諸多互聯(lián)網(wǎng)應(yīng)用必不可少的條件和前提,并且要求海量數(shù)據(jù)保持高度的完備性和一致性,需要研究合適的分布存儲(chǔ)機(jī)制,特別是對(duì)分布式存儲(chǔ)環(huán)境下數(shù)據(jù)一致性維護(hù)的研究,以滿足海量數(shù)據(jù)處理需求,大幅提升計(jì)算速度和準(zhǔn)確度。
一般分布式存儲(chǔ)機(jī)制通常采用結(jié)構(gòu)化數(shù)據(jù)庫管理原數(shù)據(jù),由分散多處的獨(dú)立設(shè)備和結(jié)點(diǎn)組成存儲(chǔ)集群和存儲(chǔ)網(wǎng)絡(luò),設(shè)計(jì)這些系統(tǒng)結(jié)構(gòu)首先考慮可擴(kuò)展性,避免存儲(chǔ)任務(wù)承擔(dān)過高的負(fù)荷,保證整個(gè)系統(tǒng)的工作效率和可靠程度,必然在數(shù)據(jù)一致性方面有一定程度的犧牲和妥協(xié),但數(shù)據(jù)是動(dòng)態(tài)變化的,用戶在每個(gè)副本結(jié)點(diǎn)都有可能更新訪問到數(shù)據(jù),必須對(duì)同一數(shù)據(jù)對(duì)象的所有副本進(jìn)行一致性維護(hù),向外界提供統(tǒng)一的視圖。因此研究海量數(shù)據(jù)存儲(chǔ)機(jī)制和數(shù)據(jù)一致性維護(hù),將海量數(shù)據(jù)分布存儲(chǔ)在各地的數(shù)據(jù)結(jié)點(diǎn),在多結(jié)點(diǎn)間實(shí)現(xiàn)完備的數(shù)據(jù)復(fù)制處理機(jī)制,為復(fù)雜運(yùn)算提供高效可靠的數(shù)據(jù)支撐,保證數(shù)據(jù)處理的速度和精度是重要的研究課題。
2.1 數(shù)據(jù)的一致性
事務(wù)處理模型中,各個(gè)事務(wù)隔離執(zhí)行能夠保證數(shù)據(jù)從一個(gè)一致性狀態(tài)變成另一個(gè)一致性狀態(tài),海量數(shù)據(jù)由一組數(shù)據(jù)變量D組成,對(duì)數(shù)據(jù)變量d∈D,Dom(d)表示d的域,且包含數(shù)據(jù)常量、集合、列表、字符串常量等。數(shù)據(jù)狀態(tài)將各個(gè)數(shù)據(jù)項(xiàng)d映射到值V,V∈Dom(d)。一個(gè)數(shù)據(jù)項(xiàng)狀態(tài)DS可以表示成d中數(shù)據(jù)變量及其值的有序?qū)?/p>
DS=(d,v):d∈D∧v∈Dom(d),假設(shè)(d,v1)∈DS∧(d,v2)∈DS,則v1=v2。即各個(gè)數(shù)據(jù)項(xiàng)在某一時(shí)刻具有唯一值。所有可能的數(shù)據(jù)變量狀態(tài)的子集被定義成完整性約束,如果一個(gè)數(shù)據(jù)項(xiàng)狀態(tài)屬于該子集,則維護(hù)了數(shù)據(jù)的一致性。
2.2 數(shù)據(jù)一致性方法比較
數(shù)據(jù)一致性方法比較,如表1所示。
表1 數(shù)據(jù)一致性方法的比較
2.2.1 事務(wù)控制法
事務(wù)控制法通過2PL協(xié)議來保證事務(wù)執(zhí)行的可串行性,也就是保證事務(wù)執(zhí)行的一致性調(diào)度,及通過兩段鎖協(xié)議來同步更新各副本數(shù)據(jù),這對(duì)事務(wù)執(zhí)行時(shí)間短、數(shù)據(jù)操作范圍窄的情況下有效。但在海量數(shù)據(jù)環(huán)境下2PL協(xié)議嚴(yán)重影響事務(wù)并發(fā)程度,同時(shí),2PC協(xié)議對(duì)網(wǎng)絡(luò)資源需求高,會(huì)使事務(wù)重啟或事務(wù)持鎖時(shí)間過長而陷入長期等待狀態(tài),難以達(dá)成一致性要求。
2.2.2 消息隊(duì)列法
消息隊(duì)列法由兩個(gè)以上的進(jìn)程間通過共享的系統(tǒng)消息隊(duì)列來交換信息,通過異步更新實(shí)現(xiàn)可靠信息收發(fā)的一種機(jī)制,進(jìn)而維護(hù)多節(jié)點(diǎn)數(shù)據(jù)的一致,涉及的消息隊(duì)列有發(fā)送、應(yīng)答、接收和管理隊(duì)列。當(dāng)某個(gè)節(jié)點(diǎn)完成一次數(shù)據(jù)更新后,將節(jié)點(diǎn)數(shù)據(jù)同步信息及本地應(yīng)答與管理隊(duì)列信息存放到消息中,發(fā)送到另一節(jié)點(diǎn)接收隊(duì)列中,同時(shí),每個(gè)節(jié)點(diǎn)上的監(jiān)控守護(hù)程序一旦發(fā)現(xiàn)本節(jié)點(diǎn)上的接收隊(duì)列有新消息到達(dá),系統(tǒng)解析消息,并處理本節(jié)點(diǎn)上的相應(yīng)數(shù)據(jù)副本所解析的更新處理。若數(shù)據(jù)更新一致則結(jié)束;否則根據(jù)應(yīng)答隊(duì)列的地址發(fā)出錯(cuò)信息,節(jié)點(diǎn)上的監(jiān)控守護(hù)程序根據(jù)收到的錯(cuò)誤信息,它將在本節(jié)點(diǎn)上試圖撤消相應(yīng)的更新操作。消息隊(duì)列法有穩(wěn)定的跨平臺(tái)性、良好的可擴(kuò)展移植性。其中穩(wěn)定的跨平臺(tái)性能保證消息一經(jīng)發(fā)送,就肯定可以傳送到消息接收端,而且保證消息的一次性接收。穩(wěn)定的可擴(kuò)展移植性為用戶方便地在分布式環(huán)境下多節(jié)點(diǎn)數(shù)據(jù)間進(jìn)程級(jí)別上加入復(fù)雜更新處理程序,從而滿足系統(tǒng)的某些特定功能。
2.2.3 數(shù)據(jù)復(fù)制控制法
數(shù)據(jù)復(fù)制就是將數(shù)據(jù)從一個(gè)節(jié)點(diǎn)復(fù)制到另一節(jié)點(diǎn),可分為同步復(fù)制和異步復(fù)制,同步復(fù)制是當(dāng)事務(wù)對(duì)某一數(shù)據(jù)復(fù)制副本進(jìn)行了更新時(shí),事務(wù)管理系統(tǒng)必須向其他節(jié)點(diǎn)的副本數(shù)據(jù)強(qiáng)制更新信息以保持?jǐn)?shù)據(jù)各副本一致,如果節(jié)點(diǎn)出現(xiàn)故障,則需要等待節(jié)點(diǎn)恢復(fù)正常再進(jìn)行處理,但頻繁地?cái)?shù)據(jù)的更新操作和向系統(tǒng)發(fā)送的復(fù)制信息,導(dǎo)致內(nèi)部系統(tǒng)通信量大,整體處理速度受到影響和制約。與同步復(fù)制機(jī)制不同的是:當(dāng)某一節(jié)點(diǎn)數(shù)據(jù)發(fā)生更新后,系統(tǒng)并不是立即將所有數(shù)據(jù)副本保持一致,而是在一段時(shí)間后再作信息更新,在某一時(shí)刻不同節(jié)點(diǎn)數(shù)據(jù)暫不同步。異步復(fù)制法主要解決兩個(gè)問題,即如何捕捉更新數(shù)據(jù)和選取復(fù)制時(shí)機(jī)。
一般情況下維護(hù)數(shù)據(jù)一致性的流程:當(dāng)用戶需要更新某一節(jié)點(diǎn)的數(shù)據(jù)對(duì)象并提交到系統(tǒng)中時(shí);系統(tǒng)根據(jù)維護(hù)一致性方法在多個(gè)節(jié)點(diǎn)副本間進(jìn)行更新;副本按照相對(duì)應(yīng)的順序接收更新,然后按照設(shè)計(jì)的規(guī)則更新數(shù)據(jù),達(dá)到數(shù)據(jù)一致性。
3.1 更新傳播模型
一個(gè)系統(tǒng)中多節(jié)點(diǎn)數(shù)據(jù)對(duì)象有很多個(gè)副本時(shí),會(huì)產(chǎn)生傳播延遲增加、更新頻率、沖突增加等一系列問題,系統(tǒng)的性能受更新傳輸模型的影響比較大。副本間更新傳播的方式有:ditect-mial方式,原理是盡可能地將更新傳播到多個(gè)副本,這是一種不可靠的組播方式;rumor-mongery方式是將最新的更新從一個(gè)副本傳播給另一個(gè)副本;會(huì)話方式是兩個(gè)副本階段性地交換自身已知的更新。在這3種傳播方式中,anit-entorpy會(huì)話有基于拓?fù)涞牟呗?、確定性策略和隨機(jī)選擇策略等幾種選擇,并且可以解決單主本發(fā)布更新遇到的問題,同時(shí)anit-entorpy方式可以確保更新被傳遞到副本圖。每個(gè)副本確定一個(gè)時(shí)間向量存儲(chǔ)其他副本的更新進(jìn)度,每次選擇進(jìn)度最慢的副本相互更新。將所有副本形成樹形結(jié)構(gòu),可以通過樹中多個(gè)節(jié)點(diǎn)發(fā)布更新,通過“捷徑”提高更新傳播的速度,比采用組播協(xié)議更有效。
3.2 更新傳播內(nèi)容
傳輸更新日志需要對(duì)更新日志進(jìn)行維護(hù),可以更靈活地操作更新沖突、減少網(wǎng)絡(luò)開銷和計(jì)算。日志更新主要依賴的不是數(shù)據(jù)對(duì)象的大小而是更新發(fā)生的頻率及本身的大小,因此傳輸日志更新更適宜大型數(shù)據(jù)對(duì)象。同時(shí)數(shù)據(jù)對(duì)象本身較大、更新力度很強(qiáng),也會(huì)產(chǎn)生海量的更新日志。當(dāng)海量數(shù)據(jù)出現(xiàn)更新日志中,通過對(duì)系統(tǒng)更新確認(rèn)效率的提高,減小本地存儲(chǔ)的更新日志歷史紀(jì)錄的長度,來解決在維護(hù)更新日志時(shí)占用較多的本地存儲(chǔ)空間;通過設(shè)計(jì)日志更新策略,在不造成維護(hù)一致性較大影響的條件下,有效取舍日志內(nèi)容,減少更新傳輸時(shí)增加的網(wǎng)絡(luò)負(fù)載和更新傳播延遲,提高系統(tǒng)實(shí)用性。由于維護(hù)數(shù)據(jù)副本一致性中需要較多的控制更新傳播,需要將更新傳播策略與提高傳輸效率兩者結(jié)合起來。
3.3 解決更新沖突
系統(tǒng)中在某個(gè)時(shí)間段或同一時(shí)間內(nèi),可能存在多個(gè)節(jié)點(diǎn)副本同時(shí)發(fā)布多個(gè)更新,即使數(shù)據(jù)副本接收到相同的一致更新,也不能確保達(dá)到最終一致,因?yàn)楦北究赡芤圆煌捻樞蚪邮盏礁北靖?,維護(hù)一致性協(xié)議中必須解決哪些更新被確認(rèn)及按什么順序確認(rèn)的問題,目前解決更新沖突主要有全排序和部分排序。
全排序基本原理是所有節(jié)點(diǎn)數(shù)據(jù)副本必須依據(jù)系統(tǒng)設(shè)計(jì)的相同順序檢測到某次更新操作之前所有的更新,然后再提交這次更新操作。全排序?qū)λ械臄?shù)據(jù)副本分散執(zhí)行,按照相同的順序執(zhí)行更新,最終確保所有數(shù)據(jù)副本一致。優(yōu)點(diǎn)是不會(huì)放棄任何更新,需要設(shè)計(jì)嚴(yán)格的排序算法,且不能保存各副本之間更新的相互依賴關(guān)系和語義關(guān)系,某個(gè)副本失效可能阻止所有其他副本前進(jìn),可能導(dǎo)致長時(shí)間的更新應(yīng)用延遲。
為克服全排序的缺點(diǎn),部分排序方法充分利用更新可交換性的特點(diǎn)。解決辦法有:數(shù)值節(jié)點(diǎn)上的加減法運(yùn)算、文件系統(tǒng)中同目錄內(nèi)多個(gè)文件的創(chuàng)建;給每個(gè)更新附加上上一次更新的名稱;后續(xù)更新一定等到所有前更新執(zhí)行之后。目前大多數(shù)系統(tǒng)對(duì)節(jié)點(diǎn)數(shù)據(jù)的更新是采用全排序,再適當(dāng)引入部分排序解決較高更新頻率的問題。
隨著互聯(lián)網(wǎng)的發(fā)展,海量數(shù)據(jù)逐漸成了數(shù)據(jù)處理領(lǐng)域的一個(gè)主流,維護(hù)副本數(shù)據(jù)一致性也成為一個(gè)主攻方向。本文在介紹數(shù)據(jù)一致性基本理論和比較分析各種數(shù)據(jù)一致性維護(hù)方法的基礎(chǔ)上,對(duì)維護(hù)海量數(shù)據(jù)一致性過程中出現(xiàn)的更新傳播模型、更新傳播內(nèi)容及解決更新沖突等進(jìn)行分析,并提出了相應(yīng)的解決辦法。下一步將深入研究相應(yīng)的解決辦法,提出解決方案并模擬實(shí)驗(yàn)。
[1]盧正鼎,楊玉萍,李長磊,等.多數(shù)據(jù)庫系統(tǒng)中的一致性維護(hù)[J].計(jì)算機(jī)研究與發(fā)展,2001(2):158-162.
[2]GANTI V,GEHRKE J,RAMAKRISHNAN R.Mining very large databases[J].Computer,1999(8):38-45.
[3]張斌.虛擬專用網(wǎng)環(huán)境中保持?jǐn)?shù)據(jù)庫一致性的一種方法[J].計(jì)算機(jī)工程,2000(10):134.
[4]謝夢.一種基于MANET的協(xié)作緩存一致性模型及維護(hù)機(jī)制[D].廣州:中山大學(xué),2010.
[5]黃宇.移動(dòng)自組網(wǎng)環(huán)境下協(xié)作緩存一致性維護(hù)機(jī)制研究[D].合肥:中國科學(xué)技術(shù)大學(xué),2007.
Study of mass data consistency
Zhao Xuezhang
(Foshan Polytechnic,F(xiàn)oshan 528137,China)
Data replication is one of the key technologies to realize mass data management.To maintain data consistency between nodes copy is the important guarantee of improving the tolerance and performance of the distributed database.Based on the introduction of basic theory of data consistency and maintenance method of comparative analysis of all kinds of data consistency,this paper analyzed the update propagation model and the update content of the communication in the process of the consistency maintenance of massive data and resolving the update conflict and so on,then the corresponding solution was proposed.
mass data;data consistency;data maintenance
趙雪章(1972—),男,河南南陽,碩士,副教授;研究方向:圖像及數(shù)據(jù)處理。