[發(fā)明專利]一種基于時(shí)間映射的事件一致性實(shí)現(xiàn)方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200910081464.9
• 申請(qǐng)日: 2009-04-03
• 公開（公告）號(hào): CN101520740A
• 公開（公告）日: 2009-09-02
• 發(fā)明（設(shè)計(jì)）人: 周忠;趙沁平;仲婧;吳威
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46;H04L29/08
• 代理公司: 北京科迪生專利代理有限責(zé)任公司
• 代理人: 成金玉;盧 紀(jì)

技術(shù)領(lǐng)域

本發(fā)明屬于分布式系統(tǒng)與計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域，具體地說是一種基于時(shí)間映射的事件一致性實(shí)現(xiàn)方法，用于解決分布式系統(tǒng)運(yùn)行結(jié)束后，各節(jié)點(diǎn)記錄的本地事件整合時(shí)的事件順序一致性問題。

背景技術(shù)

分布式系統(tǒng)是指通過網(wǎng)絡(luò)將地理上分散的節(jié)點(diǎn)加以連接，從而構(gòu)成的物理分布、邏輯一致的計(jì)算機(jī)系統(tǒng)。它使置于其中的各個(gè)節(jié)點(diǎn)可以互相協(xié)調(diào)工作，共同完成一項(xiàng)任務(wù)。分布式系統(tǒng)以其強(qiáng)大的計(jì)算能力和廣泛的應(yīng)用空間成為計(jì)算機(jī)學(xué)科的重要研究領(lǐng)域之一。

在集中式系統(tǒng)中，時(shí)間的概念很清楚，要取得事件的一致性很容易；然而在分布式系統(tǒng)中，由于傳播延遲抖動(dòng)的不可測(cè)性，并且沒有共用的時(shí)鐘或其他精確的全局時(shí)間資源，使得取得事件的一致性變得困難。在分布式系統(tǒng)運(yùn)行中，往往需要一個(gè)記錄者對(duì)整個(gè)運(yùn)行過程進(jìn)行記錄，便于運(yùn)行結(jié)束后檢索事件、回放運(yùn)行過程。由于時(shí)鐘不一致，從各個(gè)節(jié)點(diǎn)采集到的事件無法僅依據(jù)本地時(shí)戳排序，因此需要事件一致性算法來保證全局事件的一致性。另外，一致性算法還應(yīng)盡量減少對(duì)分布式系統(tǒng)運(yùn)行實(shí)時(shí)性的影響。

應(yīng)用于分布式環(huán)境的事件一致性算法大致分為三種：基于時(shí)間服務(wù)器的一致性算法、邏輯事件一致性算法和仿真時(shí)間一致性算法。基于時(shí)間服務(wù)器的一致性算法，在整個(gè)系統(tǒng)中，有一臺(tái)機(jī)器作為時(shí)間服務(wù)器，其他所有的機(jī)器與它同步。時(shí)間服務(wù)器的算法原理簡(jiǎn)單，易于實(shí)現(xiàn)。但是由于網(wǎng)絡(luò)傳播時(shí)延的不可測(cè)性、不確定性，使得所謂“統(tǒng)一的對(duì)時(shí)結(jié)果”并不可靠。另外，各個(gè)機(jī)器時(shí)鐘的頻率不完全相同，即使對(duì)時(shí)的結(jié)果一致，隨著時(shí)間的推移，各個(gè)機(jī)器的時(shí)間也會(huì)偏離全局時(shí)鐘。因此，這種方法僅適用于對(duì)時(shí)鐘精度要求較低的情況。邏輯時(shí)間一致性算法，定義了向量時(shí)鐘的概念，使用n維的整數(shù)向量表示時(shí)間(n為節(jié)點(diǎn)數(shù)目)，并在此基礎(chǔ)上規(guī)定了時(shí)鐘進(jìn)展的規(guī)則。這種算法能夠完全捕獲事件間的因果或并發(fā)關(guān)系，然而，Charron-Bost證明為了維護(hù)時(shí)鐘同構(gòu)，向量時(shí)鐘的大小必須至少等于系統(tǒng)中的進(jìn)程數(shù)目，這樣，存儲(chǔ)和通訊的額外耗費(fèi)隨著系統(tǒng)大小線性增長(zhǎng)，使大規(guī)模分布式系統(tǒng)中使用向量時(shí)鐘的成本高，可擴(kuò)展性差，并犧牲了實(shí)時(shí)性。仿真時(shí)間一致性算法的核心在于所有仿真節(jié)點(diǎn)選擇一個(gè)相同的精確時(shí)鐘，確保在仿真過程中所發(fā)生的事件在邏輯上的正確性，以及所發(fā)送的消息在邏輯上的有序性。但由于能精確保證事件一致性，使得算法的效率在三種類型的算法中最低，嚴(yán)重影響系統(tǒng)運(yùn)行的效率。

綜上所述，三種算法都不能很好的滿足分布式系統(tǒng)記錄整合的要求，尤其是以低延遲、高更新速率(low?latency，high?updating?rate)為系統(tǒng)的基本要求之一的分布式虛擬環(huán)境。為此，需要設(shè)計(jì)一種新的一致性算法，能夠應(yīng)用到分布式系統(tǒng)記錄整合中，在保證一致性精度的前提下，盡量降低對(duì)分布式系統(tǒng)運(yùn)行實(shí)時(shí)性的影響。

發(fā)明內(nèi)容

本發(fā)明的技術(shù)解決問題：克服現(xiàn)有技術(shù)的不足，提供一種基于時(shí)間映射的事件一致性實(shí)現(xiàn)方法，該方法能夠在分布式系統(tǒng)運(yùn)行結(jié)束后，保證因果一致性的條件下，對(duì)事件進(jìn)行排序，便于事件檢索、系統(tǒng)評(píng)估等，并盡量減少對(duì)系統(tǒng)實(shí)時(shí)性的影響。

本發(fā)明采用的技術(shù)方案為：一種基于時(shí)間映射的事件一致性實(shí)現(xiàn)方法，在分布式系統(tǒng)運(yùn)行結(jié)束后，執(zhí)行以下步驟：

(1)確定待排序的兩個(gè)記錄文件，提取記錄文件中記錄節(jié)點(diǎn)的信息，所述的記錄節(jié)點(diǎn)的信息包括發(fā)送方和接收方；

(2)根據(jù)已提取的記錄節(jié)點(diǎn)的信息，提取待排序的兩個(gè)記錄文件的發(fā)送-接收對(duì)(SRP)信息，形成所述兩個(gè)記錄文件各自的SRP表；

(3)掃描形成的兩個(gè)SRP表，檢測(cè)是否存在矛盾，如果存在矛盾，則并消除該矛盾；所述的存在矛盾是指：在兩個(gè)記錄文件中事件的發(fā)生順序不一致；

(4)從兩個(gè)記錄文件中確定掃描基準(zhǔn)文件，然后分別掃描兩個(gè)記錄文件，形成時(shí)間映射分割；所述的時(shí)間映射分割為：在時(shí)間映射圖中由兩垂直線之間的相鄰的帶箭頭的線將兩垂直線之間的平面區(qū)域劃分成矩形或三角形；所述的時(shí)間映射圖為：在時(shí)空視圖中以水平方向代表空間，垂直方向代表時(shí)間，帶標(biāo)志的點(diǎn)表示事件，帶箭頭的線代表消息，帶標(biāo)志的垂直線表示記錄文件；