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

無(wú)效

• 申請(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ì)

1.一種基于時(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表；所述發(fā)送-接收對(duì)SRP信息為有序二元組(T(S(m_i，j))，T(R(m_i，j)))，由消息m_i，j的發(fā)送事件邏輯時(shí)間和接收事件邏輯時(shí)間構(gòu)成；

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

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

(5)根據(jù)已形成的時(shí)間映射分割，再次掃描兩個(gè)記錄文件，并根據(jù)時(shí)間映射分割中分割塊的類型對(duì)所述分割塊中的事件進(jìn)行排序；所述的時(shí)間映射分割中分割塊類型共分為四種類型，即A型分割塊、B型分割塊、C型分割塊和D型分割塊，將分割塊的四個(gè)頂點(diǎn)分別定義為α_u、α_d、β_u、β_d，其中α_u、α_d是分別是位于掃描基準(zhǔn)文件中的上、下兩個(gè)點(diǎn)，β_u、β_d是則分別是位于另一記錄文件中的上、下兩個(gè)點(diǎn)；每個(gè)分割塊由其四個(gè)頂點(diǎn)和它的類型唯一表示，即α_u，α_d，β_u，β_d；連接α_u、β_u的帶箭頭的線，即位置在上的線，稱為該分割塊的上邊界；連接α_d、β_d的帶箭頭的線，即位置在下的線，稱為該分割塊的下邊界；A型分割塊的上邊界和下邊界的箭頭走向均是從掃描基準(zhǔn)文件指向另一文件；B型分割塊的上邊界由掃描基準(zhǔn)文件指向另一文件，下邊界的指向相反；C型分割塊的上邊界和下邊界的箭頭走向均是從另一文件指向掃描基準(zhǔn)文件；D型分割塊的上邊界是由另一文件指向掃描基準(zhǔn)文件，下邊界指向相反；

所述步驟(2)具體實(shí)現(xiàn)步驟如下：采用a.log和b.log分別表示兩個(gè)待排序的記錄文件；

(2.1)順次掃描a.log，若a.log中的當(dāng)前記錄是來(lái)自b.log的消息的接收事件，將該接收事件在a.log中的位置信息記錄到b.log的待形成的SRP表的對(duì)應(yīng)項(xiàng)中，同時(shí)記錄該接收事件的發(fā)送方和發(fā)送消息句柄；

(2.2)順次掃描b.log，若b.log中的當(dāng)前記錄為來(lái)自a.log的消息的接收事件，將該接收事件在b.log中的位置信息記錄到a.log的待形成的SRP表的對(duì)應(yīng)項(xiàng)中，同時(shí)記錄該接收事件的發(fā)送方和發(fā)送消息句柄；若b.log的當(dāng)前記錄為消息的發(fā)送事件，則掃描b.log的待形成的SRP表，在b.log中檢查是否有同一消息的接收事件存在，如果有，則在b.log的待形成的SRP表的相應(yīng)位置記下當(dāng)前記錄在b.log中的位置信息，從而形成b.log的SRP表；

(2.3)再次掃描a.log，若a.log中的當(dāng)前記錄為消息的發(fā)送事件，則掃描a.log的待形成的SRP表，在a.log中檢查是否有同一消息的接收事件存在，如果有，則在a.log待形成的SRP表的相應(yīng)位置記下當(dāng)前記錄在a.log中的位置信息，從而形成a.log的SRP表；

所述步驟(3)中消除存在矛盾的步驟如下：

A.交換兩個(gè)SRP表項(xiàng)；

B.采用后一個(gè)SRP表項(xiàng)的第二項(xiàng)取代前一個(gè)SRP表項(xiàng)的第二項(xiàng)；

所述步驟(4)中確定掃描基準(zhǔn)文件的方法為：根據(jù)兩個(gè)待排序記錄文件的第一條與對(duì)方的交互消息的位置關(guān)系來(lái)確定掃描基準(zhǔn)文件，位置關(guān)系分為兩種情況，第一種情況為：自兩個(gè)待排序記錄文件發(fā)出的第一條與對(duì)方的交互消息在時(shí)間映射圖中沒(méi)有發(fā)生交叉，此時(shí)選擇發(fā)出第一條交互消息較早的記錄文件為掃描基準(zhǔn)文件；第二種情況，自兩個(gè)待排序記錄文件發(fā)出的第一條與對(duì)方的交互消息在時(shí)間映射圖中發(fā)生交叉，此時(shí)兩個(gè)待排序記錄文件任選一個(gè)作為掃描基準(zhǔn)文件；

所述步驟(4)中形成時(shí)間映射分割的方法為：

(4.1)設(shè)掃描基準(zhǔn)文件的SRP表有N項(xiàng)，則N個(gè)表項(xiàng)將兩個(gè)待排序記錄文件的時(shí)間映射圖分成頭部、N-1個(gè)A型分割塊、尾部；掃描已確定的掃描基準(zhǔn)文件的SRP表項(xiàng)，將N-1個(gè)A型分割塊按照順序關(guān)系插入待形成的分割塊表；

(4.2)掃描另一個(gè)記錄文件的SRP表項(xiàng)，檢查是否對(duì)所述的N-1個(gè)分割塊形成新的分割，如果有，則判斷新的分割塊的類型，并將新的分割按照新的分割塊出現(xiàn)的位置插入到待形成的分割塊表中，從而形成時(shí)間映射分割；

所述步驟(5)實(shí)現(xiàn)如下：

(5.1)對(duì)時(shí)間映射圖的頭部和尾部的排序方式為：依次讀取兩個(gè)記錄文件中位于時(shí)間映射圖頭部或尾部的記錄，并插入中間文件尾；所述中間文件為在排序過(guò)程中產(chǎn)生的臨時(shí)文件；

(5.2)對(duì)于分割塊的排序方式則要依據(jù)所述分割塊的類型采用不同的處理方式：

①當(dāng)分割塊為A或B型時(shí)，步驟如下：

a.將A型或B分割塊的左上頂點(diǎn)α_u代表的記錄插入中間文件尾；

b.依次掃描另一記錄文件中位于右上頂點(diǎn)β_u和右下頂點(diǎn)之間的β_d的記錄；

c.若右上頂點(diǎn)β_u和右下頂點(diǎn)之間的β_d的記錄是兩個(gè)記錄文件間交互信息的接收事件，則跳過(guò)；否則，將右上頂點(diǎn)β_u和右下頂點(diǎn)之間的β_d的記錄插入中間文件尾；

d.將α_u到α_d之間的記錄依次插入中間文件尾，α_d以及標(biāo)識(shí)來(lái)自另一記錄文件的消息的接收事件的記錄除外；

②當(dāng)分割塊為C或D型時(shí)，步驟如下：

a.將右上頂點(diǎn)β_u代表的記錄插入中間文件尾；

b.依次掃描所確定的掃描基準(zhǔn)文件中位于左上頂點(diǎn)α_u和左下頂點(diǎn)α_d之間的記錄；

c.若左上頂點(diǎn)α_u和左下頂點(diǎn)α_d之間的記錄是兩個(gè)記錄文件間交互信息的接收事件，則跳過(guò)；否則，將左上頂點(diǎn)α_u和左下頂點(diǎn)α_d之間的記錄插入中間文件尾；

d.將右上頂點(diǎn)β_u到右下頂點(diǎn)之間的β_d之間的記錄依次插入中間文件尾，右下頂點(diǎn)之間的β_d以及標(biāo)識(shí)來(lái)自掃描基準(zhǔn)文件的消息的接收事件的記錄除外。