前切換：P2P 共享文件備份技術研究

鄭曉健，李 彤

（1.昆明理工大學津橋學院電氣與信息工程學院，云南昆明 650106；2.云南農業大學大數據學院，云南昆明 650201）

0 引言

讓用戶能夠持續有效地共享網絡資源是P2P 網絡研究重點，然而在非結構化P2P 網絡中，由于提供共享文件資源的節點頻繁而自由地加入和退出網絡，對系統的共享文件服務質量產生影響，尤其是節點退出網絡可能會減少網絡中的共享資源量，造成資源需求節點查詢不到共享文件資源情況，降低了系統查詢成功率，也影響到系統可用性［1］。有研究提出采用文件備份技術，將共享文件資源的多個備份分布到網絡中，以形成一定程度的有效冗余［2］，通過提高文件備份在網絡節點中的占有率來改善文件查詢成功率［3-7］，同時提高系統可用性。

通常P2P 架構的文件共享系統采用被動式方法實現文件備份［8-10］，在節點加入網絡時就選擇合適的備份節點并進行文件備份。如果備份節點先于主節點退出網絡，還應該尋找其它節點作為備份節點。為使共享文件在網絡中持續存在，設置系統服務節點監測網絡中節點的在線狀況。各節點定期向系統服務節點發送心跳信號通報在線狀態，系統服務節點在規定的心跳周期時間內未接收到節點的心跳信號即可斷定該節點已經退出網絡。系統服務節點會將主節點的服務切換到備份節點，讓備份節點接替其服務成為新的主節點，而后再選擇新的備份節點。

系統服務節點按照設定的監測周期，在每個監測周期末期通過檢查各共享文件節點是否存在超期未發送心跳信號現象來發現節點的退出工況。從節點退出到系統服務節點發現節點退出這段時間存在一段檢索服務盲區。如果節點退出發生在系統服務節點監測周期開始階段，要經過幾乎整個監測周期直到監測周期末才會發現節點離線，再加上節點切換所耗時間，盲區時間甚至會超過一個監測周期。在此期間網絡周期節點對退出節點文件的請求都會失敗，原因是系統服務節點返回的節點檢索信息為已離線節點的連接信息。本文將這種在被動式系統中存在的檢索服務暫時性失敗或檢索時間延長現象稱為“顛簸問題”（Bumpy Problem）。實驗顯示，顛簸事件發生的幾率較低，所以未引起人們重視。

本文對顛簸問題進行研究，提出一種更加簡便實用的改進方法，即前切換方法（PreSwitching Mechanism，PSM）。通過對混合型P2P 架構的共享文件系統網絡中節點的停留時間預測節點的動態特征，對在線節點提前進行主備份節點切換，切換完成后備份節點可以接替主節點向網絡提供服務。為了降低節點切換頻度，在備份節點選擇可能會有更長存留時間的節點，以有效減少系統顛簸發生，減少資源消耗。

1 相關工作

采用備份技術提高共享文件的占有率是有效提高文件查詢成功率［11-12］和資源可用性的重要方法。在非結構化P2P 網絡環境中，文獻［1］采用主動策略搜索識別稀有共享文件，在搜索過程中獲取共享文件的局部需求信息，然后按照用戶的需求信息備份共享文件，有針對性地提高文件在網絡中的流行度，從而提高稀有資源查詢的點擊率和可用性，但是獲取共享文件資源的整體流行度不容易；文獻［2］提出一種主動復制資源技術，用隨機漫步的方式對節點上的共享資源進行自搜索，用探測函數確定資源的稀有性，各節點用保存資源的需求閾值確定是否對資源進行搜索和復制，該方式有效降低了資源探測和復制的額外網絡開銷；文獻［3］根據待選節點的存儲能力及與主節點的物理距離作為選擇節點條件，將備份文件布置到存儲空間充足和物理位置更近的節點上，使維護消耗更低，檢索成功率得到改善；文獻［4］將備份文件保存到能夠長時間存留于網絡的節點上，提高系統在動態變化時的適應性。還有研究將文件備份布置到以往成功檢索所形成的路徑上，即放在檢索需求點和目標文件節點之間，以提高資源在網絡中的流行度，降低網絡資源消耗。文獻［5］提出采用基于位置信息和流行度的備份資源管理算法PLAR，利用混合式服務器選擇策略以及遠程增強策略，使資源下載平均速率明顯提高，有效提高共享速度并減少帶寬消耗；文獻［6］提出一種動態備份文件資源分布方法，即按所設計的備份文件目錄和信息的獲取方法獲得資源的所有備份信息，并對訪問頻率高和平均響應時間長的資源進行備份，提供用戶訪問特征和節點的實時帶寬等信息，計算存放備份的節點，使備份的分布能夠適應訪問請求和網絡帶寬的動態變化；文獻［7］提出將備份文件部署到網絡的骨干節點或骨干鏈路上，提高檢索成功率，但是識別這些特殊路徑開銷較大。

以上備份方法主要采用被動式方法備份文件，重點解決的是文件檢索成功率，這些方法確實能夠改善系統檢索性能并在一定程度上提高系統可用性，但由于P2P 網絡的動態性，主備份節點都可能退出系統，使花費大量時間布置的備份文件隨節點的退出而減少，造成檢索失敗，所以采用持續備份技術機制很有必要。

2 檢索文件時的顛簸問題

2.1 場景描述

以下將P2P 網絡中自主產生和提供共享文件的節點稱為主節點，存放主節點的備份文件節點稱為備份節點，對主節點提出資源請求的節點稱為需求節點。主節點和備份節點在資源服務方面形成互補和相互依存關系。為了快速方便地搜尋到主節點或備份節點，在混合型P2P 網絡中，系統服務節點存儲各主節點以及對應的備份節點網絡連接信息和共享文件目錄信息，并向所有資源需求節點提供共享文件檢索服務。資源需求節點從系統服務節點檢索到主節點的網絡連接信息和共享文件信息后，就可向主節點發出文件請求消息，再通過文件交換，資源需求節點就可獲得文件資源。系統服務節點還負責在主節點退出網絡后刷新節點連接信息，使主節點提供的服務切換到備份節點上。

在混合型P2P 網絡中，一些網絡事件會導致節點的狀態發生變化，呈現為加入、在線、刷新、顛簸和離線5 種狀態，形成節點的生命周期。

（1）加入狀態。當節點進入網絡時，先向系統服務節點發送加入網絡請求，在等待對方回復的這段時間節點處于加入狀態。此時系統將節點的連接信息和共享文件信息記錄下來，準備為其它資源需求節點提供檢索服務。

（2）在線狀態。節點收到系統服務節點的回復消息后進入在線狀態。

（3）刷新狀態。在線狀態下的主節點和備份節點均可能轉變為刷新狀態。如果本節點是主節點，當它共享的文件內容發生變化時須通知系統服務節點和備份節點，刷新文件信息和內容，以便保持主節點和備份節點文件一致；如果節點是備份節點，在收到主節點發送過來的刷新消息后即開始與主節點交換備份文件內容，以上兩種情況下節點都處于刷新狀態。

（4）顛簸狀態。在線狀態下的需求節點向系統服務節點發出檢索共享文件消息，系統服務節點收到消息后查詢共享文件，向需求節點回復提供共享文件的主節點連接信息和相關信息。假設主節點在此前已經退出網絡，離線時又沒有通知系統服務節點，而系統服務節點的監測周期還未結束就不能發現該主節點已經退出，所以它回復的依舊是主節點退出前的信息，按此狀態去連接主節點將失敗，這時節點處于顛簸狀態。

（5）離線狀態。即節點退出網絡時的狀態。P2P 節點退出和加入網絡是自由的，加入和退出網絡時是否通知系統服務節點不確定。

5 種節點狀態相互變換過程如圖1 所示。

Fig.1 Node lifetime process圖1 節點生命期過程

P2P 網絡中節點具有動態性［13-14］，節點的加入和退出對網絡共享文件資源分布及數量狀況產生明顯影響，從而對網絡中相關資源的服務產生影響。因此，P2P 網絡是一個資源動態變化的網絡。

2.2 問題定義

主節點退出網絡時，網絡中需求節點對主節點的共享文件請求會失敗。隨著系統將主節點服務轉移到備份節點上，之前的服務將恢復并延續。本文通過對顛簸、后切換、前切換等概念和性質的討論得出前切換策略。

定義1（顛簸）將從主節點退出網絡到系統完成主節點至備份節點的切換這一時段內，資源需求節點對主節點的服務請求出現暫時性失敗的現象稱為服務顛簸或顛簸。

定義2（后切換）將系統服務節點發現主節點退出后再安排主節點服務切換到備份節點的切換方法稱為被動式切換或后切換。

定義3（前切換）將節點未發生退出事件前就進行主節點到備份節點的切換方法稱為主動式切換或前切換。

2.3 顛簸事件性質

在P2P 網絡中，節點退出和節點被檢索都是隨機發生的，所以顛簸的發生也具有隨機性，產生顛簸的時間是連續型隨機變量。下面從備份過程分析顛簸產生的原因和概率相關因素。

引理1主節點退出和需求節點對主節點共享文件的檢索是相互獨立事件。

定理1從主節點退出網絡到系統服務節點發現主節點退出，再到啟動并完成節點的切換，這段時間內對節點文件的檢索和訪問會失敗。

證明：設?a∈Node，Node 為網絡節點集合，時間段(0,tq]為節點a 兩次心跳之間的時間間隔，其中tq＞0，tq是節點的心跳周期。

（1）若t0∈(0,tq]時節點a 退出，那么系統服務節點在[t0,tq]不會接收到節點a 的心跳信號，因而(0,tq]期間不能斷定節點是否已經退出；tq時刻之后，系統服務節點將可以推斷節點a 已經退出網絡。

（2）在(tq,th],tq＜th時段，系統服務節點將節點a 的服務切換到備份節點。

（3）若其他資源需求節點檢索節點a 文件的事件在(t0,th]時間內發生，那么由（1）可知系統服務節點在[t0,tq]期間還沒有發現節點a 退出，所以提供的還是節點a 的檢索信息。由（2）可知系統服務節點在(tq,th]時間內盡管已經發現節點退出，但還沒有完成節點a 到備份節點的切換，所以不能提供節點a 的備份節點正確信息，因此在[t0,th]時段內，資源需求節點對節點a 文件的檢索將失敗。

本文將時間段[t0,tq]稱為退出節點發現期，(tq,th]時間段稱為節點切換期。

定理2當節點退出網絡時，檢索該節點文件失敗的概率只與節點退出的概率密度函數以及從節點退出到完成節點切換的時間長短有關。

證明：設?a∈Node，Node 為網絡節點集合，節點a 退出網絡的時間為連續型隨機變量Q，且Q 在(t1,t2),t1＜t2上的概率密度函數為（fq）。這里以節點退出網絡為前提條件，所以P（Q）＞0，?b∈Node，節點b 向節點a 發送檢索文件消息，檢索時間為連續型隨機變量R，R 在(t1,t2)上的概率密度函數為h（r），t1＜q＜t2，t1＜r＜t2，同時?t∈(t1,t2)，且(t,t+ε)?(t1,t2)，其中t 是節點b 檢索節點a 的時間，ε=th-t，th是節點切換結束的時間，則節點在(t,t+ε)期間節點a 退出網絡的概率為：

在（t，t+ε）期間，網絡中節點b 檢索節點a 的文件概率為：

在（t，t+ε）期間，當節點a 退出網絡時，節點b 檢索節點a 的文件概率為：

在式（3）中，由引理1 知R 和Q 相互獨立，即：

而由定理1，（t，t+ε）時間段內如果發生對節點a 的檢索事件則檢索失敗。由式（4）可知檢索失敗的概率等于檢索事件發生的概率。由式（2）可知，從節點退出網絡到節點切換完成期間，檢索節點a 中文件的概率只與其概率密度函數、發現節點退出和切換所用的時間有關。

3 前切換策略

通過對顛簸問題的分析和實驗驗證，本文提出一種新的主節點和備份節點切換方法，即前切換算法PSM。在系統服務節點控制下，從在線節點中預測即將退出的節點，提前進行節點切換，由備份節點繼續提供服務。

有些方法可保持檢索服務成功率，但是要付出一定代價。如系統服務節點回應資源需求節點檢索時，同時向其提供主節點和備份節點的網絡連接信息。資源需求節點對主節點和備份節點同時發起資源請求，收到它們反饋的檢索結果后進行仲裁，再選擇利用，或者采用一些無需檢索信息支持的搜索方法，如洪泛、隨機漫步等搜索方式。這些方法帶來的問題是產生大量的網絡帶寬消耗或更長的檢索時間［15］。

3.1 前切換性質

由引理1 可知節點退出事件和對節點共享文件的檢索事件獨立，但不能保證它們的交事件為空，即存在節點退出事件和對節點共享文件的檢索事件同時發生的可能性。盡管前切換算法也有產生顛簸的風險，但是前切換與后切換產生顛簸的概率呈現下面性質。

定理3節點前切換時發生顛簸的概率小于等于后切換時發生顛簸的概率。

證明：前切換算法的顛簸來自于節點切換期(tq,th]，即在切換過程中如果遇到節點退出將產生顛簸。后切換發生顛簸的時段包括退出節點發現期和節點切換期，即[t0,th]，而(tq,th]?[t0,th]，且(tq,th]∩[t0,th]=?，由概率的有限可加性得：

式（5）中P{t0＜R＜tq}≥0，則有：

即前切換遇到顛簸概率小于等于后切換。

3.2 前切換機制

前切換需完成兩個階段任務：

（1）第一階段完成共享文件的備份和一致性維護。①共享文件備份。節點加入和退出網絡要由系統服務節點按照備份節點選擇算法尋找合適的備份節點，記錄主備份節點的連接信息和共享文件信息，然后向主節點和備份節點發送消息，將主節點文件發送到備份節點，使得共享文件在2 個或以上節點中存在；②共享文件一致性維護。當主節點的共享文件發生變化時，通過系統服務節點的備份節點連接信息向備份節點發送消息，刷新備份節點文件內容，以保持主節點和備份節點文件的一致性。

（2）第二階段進行主節點和備份節點的前切換。系統服務節點預測即將退出網絡主節點，在它退出前，通過更新系統服務節點信息表將主節點轉換為備份節點，以實現節點切換。切換完成后，所有對主節點的共享文件檢索將提供備份節點連接信息，需求節點可繼續訪問共享文件。

在切換中主節點與備份節點間的共享文件交換需要消耗網絡帶寬及備份節點存儲的資源，頻繁切換會增大資源消耗，甚至丟失備份文件［8-10］。根據文獻［4］的研究，節點存留于網絡的時間對于系統可用性有影響，即節點存留于網絡的時間長度與保存在節點上的文件可用性成正比。通過統計設定在線節點集合的平均存留時間作為衡量指標，找到存留時間更長的節點使節點切換延后。

設在系統服務節點各監測周期∑t時段內，?ai∈Node，i=1，2，…，n，Node為有n 個網絡節點的集合。

定義4（節點存留時間）時間?t內，節點ai在網絡中的存留時間為?ti=tie-tis，其中tis為ai加入網絡的時間，tie為ai退出網絡的時間。

定義5（節點平均存留時間）時間?t內，網絡節點的平均存留時間為：

其中,?ti為ai的節點存留時間，fi是節點存留時間為?ti的節點數。

定義6（節點在線時間）時刻t網絡中在線節點ai的在線時間為?tiL=t-tis，其中tis為節點ai加入網絡的時間。

定義7（節點平均在線時間）設t時刻網絡在線節點平均在線時間為：

其中，?tiL為節點ai的在線時間，fi是在線時間為?tiL的節點數。

系統服務節點為了記錄節點和共享文件信息，設置節點信息表NIT、備份節點表CIT、共享文件信息表SIT。NIT的每個記錄為＜ai，s，t1，t2＞，其中ai為節點號，s 為狀態，加入時間為t1，當前在線時間為t2。CIT的每個記錄為＜am，ab＞，其中am為主節點號，ab為備份節點號，SIT的每個記錄為＜ID，file，am，t＞，其中ID為記錄編號，file為共享文件名，am為主節點號，t為更新時間。

共享文件備份和一致性維護［14-15］時，選擇備份節點以存留時間超過網絡的平均存留時間為條件。在線節點的存留時間由系統服務節點的存留時間算法實現。當系統服務節點接收到節點的心跳信號時會更新節點信息表NIT的信息，然后按照定義5 計算并刷新網絡的節點平均存留時間E，以提供給備份節點選擇算法使用。

算法1 備份節點選擇算法

輸入：節點信息表NIT，T時間段內網絡節點平均存留時間E

輸出：選擇出的備份節點

步驟1：按條件ai.s=0 且ai.tie-ai.tis＞E查詢節點信息表NIT，得節點記錄集NTiL：

如果NTiL≠ ?，則執行步驟2；

如果NTiL=?，則amax=?，執行步驟6；

步驟2：移動到NTiL的第一個記錄ak∈NTiL；

步驟3：amax=ak；

步驟4：移動到NTiL的下一個記錄ak∈NTiL；

步驟5：如果amax.tie-amax.tis＜ak.tie-ak.tis，則amax=ak，執行步驟4；

否則執行步驟6；

步驟6：返回amax。

系統服務節點心跳周期結束時執行前切換算法。

算法2 前切換算法

輸入：節點信息表NIT，節點平均在線時間EL

輸出：選出的節點切換到備份節點

步驟1：按條件ai.s=1 且t-ai.tiL＞EL查詢節點信息表NIT，得節點記錄集NITs：

如果NITs≠ ?則執行步驟2；

如果NITs=?則執行步驟8；

步驟2：移動到NITs的第一個記錄aj∈NITs；

步驟3：更新SIT 的所有記錄rec∈SIT,rec.am=aj,aj∈NITs，為rec.am=aj；

步驟4：調用備份節點選擇算法，選擇備份節點an；

如果an=?，則執行步驟7；

如果an≠ ?，則執行步驟5；

步驟5：更新CIT 的記錄＜am，ab＞，am=aj,ab=an；

步驟6：發送消息給節點am，通知它可以退出網絡；

步驟7：移動到NITs的下一個記錄：如果NITs≠ ?則執行步驟3；

如果NITs=?則執行步驟8；

步驟8：返回切換節點數量。

4 實驗與結果分析

4.1 實驗設置

先驗證不同網絡規模下［16］節點退出網絡時檢索該節點文件失敗的概率與節點退出的概率，用后切換作對比，對前切換算法進行性能測試，以檢驗本文提出的前切換算法降低顛簸事件的有效性。系統仿真環境為：操作系統Windows VistaTHHome Basic，處理器Intel（R）Core（TH）2 Duo CPU P8600 @2.40GHz 2.40GHz，內存2.0GB。測試平臺采用VB6.0 編程實現。

4.2 顛簸事件性質驗證

為清晰呈現發生顛簸事件情況，測試參數設置如下：節點加入和退出網絡事件的頻度為1 節點/s，退出節點隨機產生；隨機挑選在線節點發送檢索請求事件，檢索事件產生頻度為10 次/s；系統服務節點的心跳周期設置為0.5s；所有節點規模的測試時間長度均為1 800s。模擬測試節點數量規模分別為100 個、500 個、1 000 個、2 000 個；顛簸事件測試結果如圖2 所示。

測試結果證實了定理2，即在不同網絡規模情況下產生顛簸的概率只與節點退出的概率密度函數以及從節點退出到完成節點切換的時間長短有關。當網絡節點規模較小而節點退出切換到備份節點完成時間較長時，發生顛簸幾率較大，顛簸發生次數增長較快。當網絡中節點規模逐漸增大時，節點退出到切換到備份節點完成時間即便較長，顛簸事件發生的幾率仍在增長，但增長速度會比較平緩。顛簸事件發生幾率與檢索事件發生率直接相關。

Fig.2 Turbulence event test results圖2 顛簸事件測試結果

4.3 前切換算法有效性驗證

為評價減少顛簸事件時前切換算法的有效性，將它與后切換進行對比。設置測試參數如下：節點加入和退出網絡事件的頻度為1 節點/s，退出節點隨機產生；隨機選擇在線節點發送檢索資源請求，檢索事件產生頻度為10 次/s；系統服務節點的心跳周期和節點切換處理周期設為1s，各種節點規模測試時間長度均設為1 800s。模擬測試節點數量分別為100 個、500 個、1 000 個、1 500 個、2 000 個；將前切換和后切換發生顛簸事件切換處理時間為1、3 和5s 時測試結果進行比較，如圖3、圖4、圖5 所示。

Fig.3 Comparison of pre-switching Switch before and after switching turbulence event（1 second switching time）圖3 前切換與后切換顛簸事件比較（1s 切換時間）

Fig.4 Comparison of pre-switching and after switching turbulence event（3 seconds switching time）圖4 前切換與后切換顛簸事件比較（3s 切換時間）

從圖中可以看出，前切換測試結果比較穩定，后切換方法存在明顯的顛簸現象，隨著節點數量的增加顛簸事件發生有所減少，但是發生率仍然很高。前切換方法顛簸事件發生率比較低且保持穩定狀態，主要原因在于前切換排除了節點退出發現期的顛簸事件問題。實驗證實了定理3的結果，即在不同網絡規模下，節點前切換時發生顛簸的概率明顯小于等于后切換，而且隨著網絡規模的增大，顛簸事件的發生幾率也在下降。所以，前切換在避免顛簸事件上效果較好。

Fig.5 Comparison of pre-switching and after switching turbulence event（5 seconds switching time）圖5 前切換與后切換顛簸事件比較（5s 切換時間）

5 結語

為提高非結構P2P 網絡［17-18］中共享文件系統可用性，本文從共享文件備份技術著手，對主、備份節點的切換技術進行了研究。發現影響系統可用性［19-20］的主要因素是顛簸事件的發生，而顛簸產生在系統節點退出時段和切換處理時段。為了減少顛簸現象發生，提出一種基于主動切換策略的前切換方法，它比后切換方法減少了系統服務節點退出這一過程。實驗結果證實前切換方法在降低顛簸事件發生方面明顯優于后切換方法。后續將在網絡節點退出的預測方法上進一步研究以提高預測準確性，從而進一步降低節點切換頻度和資源消耗，提高系統可用性。