基于gossip的節(jié)點(diǎn)采樣技術(shù)介紹(gossip-based peer sampling)

1、基于gossip機(jī)制的節(jié)點(diǎn)采樣技術(shù)概述（gossip-based peer sampling）一、這是什么技術(shù)，為什么需要這個(gè)技術(shù)Gossip機(jī)制，即流言機(jī)制，作為一種簡(jiǎn)單可靠的拓?fù)涔芾砼c消息分發(fā)機(jī)制，在大規(guī)模的分布式系統(tǒng)中得到了廣泛的應(yīng)用，其主要應(yīng)用包括信息分發(fā)，數(shù)據(jù)收集，拓?fù)涔芾淼确矫?。其產(chǎn)生原因主要由于在大規(guī)模的分布式系統(tǒng)中，底層物理鏈路存在數(shù)據(jù)丟包與鏈路斷開等現(xiàn)象，節(jié)點(diǎn)規(guī)模的可擴(kuò)展性與消息分發(fā)的可靠性難以得到有效保證?；趃ossip機(jī)制的覆蓋網(wǎng)絡(luò)協(xié)議模仿流言傳播的特性，系統(tǒng)中的每個(gè)節(jié)點(diǎn)定期的從鄰居表中選擇一個(gè)節(jié)點(diǎn)子集，然后與這個(gè)子集中的節(jié)點(diǎn)進(jìn)行拓?fù)湫畔ⅲㄠ従颖硇畔ⅲ┑慕粨Q，來維持一種

2、動(dòng)態(tài)的覆蓋拓?fù)浣Y(jié)構(gòu)。如何進(jìn)行子集的選擇對(duì)于基于gossip機(jī)制的消息分發(fā)是至關(guān)重要的。理想的情況下希望從分布式系統(tǒng)的所有節(jié)點(diǎn)中均勻隨機(jī)的選擇鄰居節(jié)點(diǎn)。基于這個(gè)假設(shè)而衍生出的gossip協(xié)議已經(jīng)得到了很多良好的特性：如可擴(kuò)展、可靠、有效。在實(shí)際應(yīng)用中，假設(shè)一個(gè)節(jié)點(diǎn)可以知道系統(tǒng)中的其他所有節(jié)點(diǎn)是不現(xiàn)實(shí)的。因?yàn)楫?dāng)前的大規(guī)模分布式系統(tǒng)規(guī)?？梢赃_(dá)到10萬(wàn)或以上級(jí)別，同時(shí)節(jié)點(diǎn)可能頻繁加入或離開系統(tǒng)（稱之為churn現(xiàn)象），前者需要巨大的存儲(chǔ)開銷，后者需要節(jié)點(diǎn)維持大量的對(duì)鄰居節(jié)點(diǎn)的同步信息開銷，這導(dǎo)致了節(jié)點(diǎn)以及整個(gè)系統(tǒng)的性能嚴(yán)重下降。所以采取一種分布式的拓?fù)涔芾聿呗詠硖娲值耐負(fù)涔芾聿呗赃M(jìn)行g(shù)ossip機(jī)

3、制的協(xié)議部署顯得至關(guān)重要。節(jié)點(diǎn)采樣服務(wù)，是一種獨(dú)立于應(yīng)用的服務(wù)，就是在某個(gè)時(shí)刻系統(tǒng)中任意一個(gè)節(jié)點(diǎn)通過這個(gè)服務(wù)可以獲取一個(gè)系統(tǒng)中的隨機(jī)選擇節(jié)點(diǎn)。節(jié)點(diǎn)采樣服務(wù)可以應(yīng)用于消息分發(fā)，數(shù)據(jù)收集，負(fù)載均衡以及網(wǎng)絡(luò)管理。采樣服務(wù)提供了任何節(jié)點(diǎn)與其他節(jié)點(diǎn)進(jìn)行通信連接的可能性。節(jié)點(diǎn)采樣服務(wù)的基本原理本身基于gossip機(jī)制的特征，每個(gè)節(jié)點(diǎn)都維持一個(gè)本地的有限數(shù)目的鄰居表，鄰居表中包含若干個(gè)系統(tǒng)中的其他節(jié)點(diǎn)信息（稱之為節(jié)點(diǎn)描述符），每隔一段時(shí)間節(jié)點(diǎn)使用gossip機(jī)制與某個(gè)或某幾個(gè)鄰居進(jìn)行各自鄰居表信息的交換來刷新自己的鄰居表。（但是很明顯存在若干問題有待解決：1. 單個(gè)節(jié)點(diǎn)從本地鄰居表中選擇的節(jié)點(diǎn)的隨機(jī)性，即本

4、地的有限數(shù)目鄰居表如何映射系統(tǒng)中的所有節(jié)點(diǎn)來保證節(jié)點(diǎn)選擇的隨機(jī)性？2. 當(dāng)系統(tǒng)中存在節(jié)點(diǎn)失效、消息丟包以及網(wǎng)絡(luò)擾動(dòng)時(shí)如何保證此時(shí)節(jié)點(diǎn)的選擇依然保持良好的隨機(jī)性？3. 由于系統(tǒng)中的節(jié)點(diǎn)分布不同，如何避免某個(gè)節(jié)點(diǎn)被采樣的次數(shù)過多，即避免出現(xiàn)網(wǎng)絡(luò)熱點(diǎn)，保證負(fù)載均衡。）事實(shí)已經(jīng)證明：采用push-pull模式要優(yōu)于純push或是純pull模式。同時(shí)事實(shí)已證明，在進(jìn)行成員策略管理時(shí)要兼顧負(fù)載均衡與抗網(wǎng)絡(luò)擾動(dòng)與節(jié)點(diǎn)失效。（這引出了本文認(rèn)為很重要的可能的一個(gè)研究點(diǎn)：基于gossip的節(jié)點(diǎn)采樣服務(wù)存在負(fù)載均衡與抗網(wǎng)絡(luò)擾動(dòng)與節(jié)點(diǎn)失效這兩個(gè)需求，如何通過環(huán)境的變化來動(dòng)態(tài)調(diào)整若干關(guān)鍵參數(shù)來同時(shí)部分滿足這兩個(gè)需求？即

5、某個(gè)時(shí)刻根據(jù)網(wǎng)絡(luò)環(huán)境偏向于滿足某個(gè)需求）二、基于gossip機(jī)制的節(jié)點(diǎn)采樣服務(wù)的基本實(shí)現(xiàn)框架基于gossip的節(jié)點(diǎn)采樣服務(wù)就是為某個(gè)節(jié)點(diǎn)提供一個(gè)獲取系統(tǒng)中隨機(jī)節(jié)點(diǎn)的方法。其主要的方法只有兩個(gè)，如下：1. init()：init方法用于對(duì)剛加入覆蓋網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行初始化的一系列操作，這個(gè)操作是應(yīng)用相關(guān)的（比如針對(duì)消息分發(fā)，數(shù)據(jù)收集等等）。2. getPeer()：getPeer方法返回一個(gè)系統(tǒng)中隨機(jī)選擇的節(jié)點(diǎn)。理想情況下這個(gè)采樣是獨(dú)立的無偏采樣，被采樣節(jié)點(diǎn)的特性是與實(shí)驗(yàn)有關(guān)的（被采樣節(jié)點(diǎn)的隨機(jī)性在時(shí)間上和空間上可能存在關(guān)聯(lián)）。重點(diǎn)就在研究getPeer方法的不同實(shí)現(xiàn)版本，找出每種版本最適合于什么

6、應(yīng)用，然后針對(duì)總體環(huán)境在優(yōu)化均衡考慮或直接針對(duì)某個(gè)場(chǎng)景做優(yōu)化。三、協(xié)議的總體描述考慮網(wǎng)絡(luò)中一系列連通的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)地址用于消息的發(fā)送，每個(gè)節(jié)點(diǎn)都有一個(gè)本地鄰居表用來代表節(jié)點(diǎn)對(duì)全局成員關(guān)系的部分感知。理想情況下本地鄰居表包含網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)，但實(shí)際中本地鄰居表不可能包含所有的節(jié)點(diǎn)。如果本地鄰居表包含所有其他節(jié)點(diǎn)信息，稱之為節(jié)點(diǎn)持有網(wǎng)絡(luò)的全局視圖；如果本地鄰居表僅僅包含所有節(jié)點(diǎn)的一個(gè)子集，則稱之為節(jié)點(diǎn)持有網(wǎng)絡(luò)的局部視圖。局部視圖是c（c為常數(shù)）個(gè)節(jié)點(diǎn)描述符的列表。每個(gè)節(jié)點(diǎn)都持有相同大小的局部視圖。一個(gè)節(jié)點(diǎn)描述符表示一個(gè)網(wǎng)絡(luò)地址（例如一個(gè)IP地址）和一個(gè)時(shí)間戳。時(shí)間戳用于表示這個(gè)節(jié)點(diǎn)描述

7、符的存活時(shí)間，時(shí)間戳的值越大則表明這個(gè)描述符存在于節(jié)點(diǎn)的局部視圖中的時(shí)間越長(zhǎng)?？梢哉J(rèn)為節(jié)點(diǎn)的局部視圖是一個(gè)數(shù)據(jù)結(jié)構(gòu)，在這之上定義了一組操作集合。這意味著除非某個(gè)特殊的操作施加于局部視圖，否則局部視圖中的元素順序不會(huì)顯式變化。同時(shí)規(guī)定局部視圖中不允許存在相同網(wǎng)絡(luò)地址的兩個(gè)描述符。節(jié)點(diǎn)定期持續(xù)進(jìn)行g(shù)ossip的交換過程來保證局部視圖中的描述符是系統(tǒng)全局拓?fù)湫畔⒌囊粋€(gè)隨機(jī)集合，使得局部視圖可以反映系統(tǒng)的動(dòng)態(tài)變化。下面給出具體實(shí)現(xiàn)：method view.select(c, H, S, buffer(p)view.append(buffer(p)view.removeDuplicats()view.r

8、emoveOldItems(min(H, view.size-c)view.removeHead(min(S, view.size-c)view.removeAtRandom(view.size-c)(a) method view.select(c, H, S, buffer(p)do foreverreceive buffer(p) from pP view.selectPeer()if pull then/ 0 is initial agebuffer (MyAddress, 0)/ shuffle the viewview.permute()move oldest H items to

9、end of viewbuffer.append(view.head(c/2 - 1)send buffer to pview.select(c, H, S, buffer(p)view.increaseAge()(b) passive threaddo foreverwait(T time units)P view.selectPeer()if push then/ 0 is initial agebuffer (MyAddress, 0)/ shuffle the viewview.permute()move oldest H items to end of viewbuffer.appe

10、nd(view.head(c/2 - 1)send buffer to pelse / empty view to trigger responsesend (null) to pif pull thenreceive buffer(p) from pview.select(c, H, S, buffer(p)view.increaseAge()(c) active thread協(xié)議包含兩個(gè)線程：主動(dòng)線程用于初始化與其他節(jié)點(diǎn)的通信；被動(dòng)線程用于接受其他節(jié)點(diǎn)的請(qǐng)求并響應(yīng)。（對(duì)于view.select(c, H, S, buffer(p)函數(shù)，其每一句代碼都很重要，實(shí)質(zhì)就是對(duì)view這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)

11、行一系列的操作達(dá)到想要的效果）我們將系統(tǒng)看作一個(gè)非同步的系統(tǒng)（即節(jié)點(diǎn)發(fā)起的請(qǐng)求-應(yīng)答過程無需阻塞等待），將時(shí)間看作一系列離散的時(shí)間單元，在每個(gè)時(shí)間單元內(nèi)節(jié)點(diǎn)只能執(zhí)行一次局部視圖的拓?fù)湫畔⒔粨Q。關(guān)鍵的參數(shù)為c，H，S。其中c表示節(jié)點(diǎn)的局部視圖大小，為常量；H表示需要從view中刪除的age值偏大的節(jié)點(diǎn)描述符個(gè)數(shù)（下文解釋）；S表示需要從view的頭部刪除的節(jié)點(diǎn)描述符個(gè)數(shù)（其中H，S小于c/2，下文解釋）。鑒于被動(dòng)線程的內(nèi)容與主動(dòng)線程類似，在此僅僅解釋主動(dòng)線程的內(nèi)容。過程描述如下：1）由selectPeer方法返回一個(gè)目標(biāo)節(jié)點(diǎn)進(jìn)行g(shù)ossip信息交換。selectPeer的具體實(shí)現(xiàn)會(huì)對(duì)最終結(jié)果產(chǎn)生

12、影響，下文將詳細(xì)闡述。2）發(fā)送緩沖區(qū)buffer：首先將當(dāng)前運(yùn)行主動(dòng)線程的節(jié)點(diǎn)描述符置入緩沖區(qū)內(nèi)。然后在view上執(zhí)行亂序排列，以此保證從view中選出的c/2-1個(gè)元素是隨機(jī)的，但是選出的c/2-1個(gè)元素不包括age值最大的H個(gè)元素（利用時(shí)間戳起到自動(dòng)剔除可能已失效的節(jié)點(diǎn)）。但若選出的元素不足(c/2-1)個(gè)，也可以從age值最大的H個(gè)元素中選出若干來補(bǔ)足。3）select(c, H, S, buffer)方法：當(dāng)收到應(yīng)答后將參數(shù)buffer傳遞給函數(shù)view.select(c, H, S, buffer)。這個(gè)函數(shù)根據(jù)4個(gè)參數(shù)通過一系列操作得到節(jié)點(diǎn)的新view（算法的核心關(guān)鍵所在）。首先將

13、buffer的內(nèi)容附在view的后面，然后刪除重復(fù)的節(jié)點(diǎn)描述符，這之后view的大小至少是其原大小。然后執(zhí)行三個(gè)刪除操作將view的大小裁剪到其原始大小。4）removeOldItems(min(H, view.size-c)：首先刪除age值最大的H個(gè)元素。H越大，刪除的age值偏大的元素越多，這樣做的目的是因?yàn)閍ge值偏大的元素可能已經(jīng)是失效節(jié)點(diǎn)（根據(jù)大規(guī)模P2P系統(tǒng)中節(jié)點(diǎn)存活時(shí)間服從Pareto分布的原則），將其刪除就直接避免了與失效節(jié)點(diǎn)保持一個(gè)無效的連接（H表示Healing）。4）removeHead(min(S, view.size-c)：然后再?gòu)膙iew的頭部刪除S個(gè)元素。S越大

14、，刪除的view中原有的元素越多。這樣做將使得最終節(jié)點(diǎn)收到的節(jié)點(diǎn)描述符信息有更高的概率留在view中，因?yàn)槊看蝏uffer的內(nèi)容是附在view的原有內(nèi)容之后，從頭部刪除S個(gè)元素，刪除越多則可以留更多空間來裝載接收的buffer內(nèi)容，使得buffer中的內(nèi)容有更高的概率留在view中。實(shí)質(zhì)上參數(shù)S控制了節(jié)點(diǎn)局部視圖中拓?fù)湫畔⒔粨Q的概率，S越高，交換概率越高（S表示Swapped）。S很低會(huì)導(dǎo)致進(jìn)行g(shù)ossip交換的雙方以較高的概率保持原有view的內(nèi)容而非進(jìn)行交換。這會(huì)導(dǎo)致網(wǎng)絡(luò)中只存唯一存在的節(jié)點(diǎn)描述符被刪除（降低了魯棒性）；如果S很高，進(jìn)行g(shù)ossip交換的雙方會(huì)以較高的概率進(jìn)行內(nèi)容交換，可以

15、降低網(wǎng)絡(luò)中唯一存在的節(jié)點(diǎn)描述符被刪除的可能性。5）removeAtRandom(view.size-c)：最終view的大小被隨機(jī)刪除若干元素裁剪到原大小c。具體設(shè)計(jì)準(zhǔn)則組合：主要包含三種準(zhǔn)則，目標(biāo)gossip節(jié)點(diǎn)選擇，局部視圖的推送方式，局部視圖的元素選擇方式。目標(biāo)gossip節(jié)點(diǎn)選擇：有兩種方式，隨機(jī)或選擇age值最大的節(jié)點(diǎn)。rand從view中隨機(jī)選擇一個(gè)目標(biāo)gossip節(jié)點(diǎn)tail從view中選擇一個(gè)age值最大的節(jié)點(diǎn)局部視圖的推送方式：有三種，push，pushpull，pull。push推方式，即節(jié)點(diǎn)主動(dòng)發(fā)起連接pushpull推拉結(jié)合方式，節(jié)點(diǎn)主動(dòng)發(fā)起連接同時(shí)被動(dòng)接受連接請(qǐng)求pu

16、ll拉方式，即節(jié)點(diǎn)別動(dòng)接受連接請(qǐng)求（效率太低被拋棄，除非接收到一個(gè)請(qǐng)求，節(jié)點(diǎn)不能主動(dòng)向網(wǎng)絡(luò)中注入自身的節(jié)點(diǎn)描述符信息）局部視圖的元素選擇方式：盲選（blind），恢復(fù)式（healer），交換式（swapper）。blindH=0, S=0任何時(shí)候采取隨機(jī)選擇方式healerH=c/2保持最新鮮的節(jié)點(diǎn)描述符在view中swapperH=0, S=c/2Gossip雙方以更高概率交換拓?fù)湫畔⒆ⅲ篐的范圍是0, c/2，S的范圍是0, c/2-H，H+S<c/2。四、具體實(shí)現(xiàn)init方法與getPeer方法。getPeer方法是從節(jié)點(diǎn)當(dāng)前持有的局部視圖中返回一個(gè)節(jié)點(diǎn)描述符。如果要增加返回的節(jié)點(diǎn)

17、描述符的隨機(jī)性，采樣服務(wù)必須做到在一定的時(shí)間間隔內(nèi)不對(duì)同一個(gè)節(jié)點(diǎn)采樣兩次：這樣做明顯引入了偏好性而破壞了采樣服務(wù)的質(zhì)量。所以服務(wù)將會(huì)維持一個(gè)隊(duì)列，用于存儲(chǔ)沒有被采樣到的節(jié)點(diǎn)。getPeer方法將每次返回隊(duì)列中的第一個(gè)元素并將這個(gè)元素刪除。當(dāng)服務(wù)接到一個(gè)局部視圖更新的通知時(shí)，不在當(dāng)前隊(duì)列中的所有元素將被刪除，而新加入到局部視圖中的元素將被添加到隊(duì)列中來。如果隊(duì)列為空，那服務(wù)將返回當(dāng)前view的隨機(jī)采樣。實(shí)驗(yàn)證明，很多參數(shù)組合不能獲取到較好的顯示結(jié)果，但是也沒有一種方案可以在各種應(yīng)用中取得都比較理想的結(jié)果。需要考慮應(yīng)用差異性采取均衡的參數(shù)設(shè)置策略。五、節(jié)點(diǎn)采樣全局隨機(jī)性分析節(jié)點(diǎn)可以很容易的從本地局

18、部視圖中進(jìn)行隨機(jī)的節(jié)點(diǎn)采樣服務(wù)，但是單個(gè)節(jié)點(diǎn)的局部隨機(jī)采樣與獨(dú)立采樣特性的統(tǒng)計(jì)特征可能隱藏了網(wǎng)絡(luò)作為一個(gè)整體呈現(xiàn)出的某些結(jié)構(gòu)屬性特征。為了便于進(jìn)行全局的隨機(jī)性分析，將網(wǎng)絡(luò)轉(zhuǎn)化為一個(gè)有向圖。圖的定義如下：如果節(jié)點(diǎn)a的view中存在節(jié)點(diǎn)b的描述符，則認(rèn)為從a到b直接可達(dá)，在圖中存在有向邊(a, b)從a指向b。問題是這個(gè)覆蓋拓?fù)渑c一個(gè)隨機(jī)圖有多相似？使得這個(gè)覆蓋拓?fù)渲忻總€(gè)view中的節(jié)點(diǎn)描述符集合代表整個(gè)節(jié)點(diǎn)集合的均勻獨(dú)立隨機(jī)采樣。在圖屬性分析中最重要的特性就是度分布。節(jié)點(diǎn)i的度定義為：如果某個(gè)節(jié)點(diǎn)將i的節(jié)點(diǎn)描述符存儲(chǔ)于各自的局部視圖中，則所有這些節(jié)點(diǎn)的個(gè)數(shù)之和為節(jié)點(diǎn)i的度。每個(gè)節(jié)點(diǎn)的出度是個(gè)常數(shù)

19、c，等于其局部視圖大小。度分布決定了節(jié)點(diǎn)通信中是否存在通信熱點(diǎn)與瓶頸，即負(fù)載均衡由度分布決定。同時(shí)度分布與節(jié)點(diǎn)失效與可靠性有直接的關(guān)系。除開度分布還有兩個(gè)參數(shù)集群系數(shù)（Clustering Coefficient）與平均路徑長(zhǎng)度（Average Path Length）。注：但是入度則并非一個(gè)常數(shù)，存在一定的時(shí)間關(guān)聯(lián)性（節(jié)點(diǎn)入度與時(shí)間有關(guān)）與空間關(guān)聯(lián)性（節(jié)點(diǎn)入度與節(jié)點(diǎn)初始的拓?fù)溆嘘P(guān)），能否通過DTMC建立節(jié)點(diǎn)入度的概率轉(zhuǎn)移矩陣？能否給出時(shí)間關(guān)聯(lián)性與空間關(guān)聯(lián)性的具體定義？并通過某個(gè)算法盡量降低這兩個(gè)關(guān)聯(lián)性。第一個(gè)問題：對(duì)于一個(gè)特定的協(xié)議實(shí)現(xiàn)，通過一系列持續(xù)的協(xié)議執(zhí)行，通信圖是否存在穩(wěn)定的屬性？換

20、句話說通信圖是否存在收斂行為（隨著協(xié)議的執(zhí)行，圖會(huì)演化到某個(gè)屬性收斂的狀態(tài)）。我們希望覆蓋網(wǎng)絡(luò)可以收斂于某個(gè)特定狀態(tài)而與網(wǎng)絡(luò)的初始拓?fù)錈o關(guān)。這種屬性稱之為自組織性。我們希望在各種場(chǎng)景下運(yùn)行的協(xié)議實(shí)例都可以產(chǎn)生一致的、可預(yù)期的行為。第二個(gè)問題：如果存在收斂，什么樣的通信圖使得協(xié)議實(shí)例可以收斂？第三個(gè)問題：本地的動(dòng)態(tài)屬性與全局度分布的關(guān)系？即度分布與其全局屬性如度的最大值，方差，均值等不變時(shí)單個(gè)節(jié)點(diǎn)的度卻在變化，這種現(xiàn)象是否可能？如果是這樣就導(dǎo)出了一個(gè)很重要的現(xiàn)象：即通信圖中如果存在瓶頸，那么瓶頸不會(huì)始終都存在于一個(gè)節(jié)點(diǎn)上，換句話說瓶頸會(huì)發(fā)生轉(zhuǎn)移，這樣就達(dá)到了負(fù)載均衡，增強(qiáng)了網(wǎng)絡(luò)的魯棒性。a）度分

21、布：給出了三種初始的網(wǎng)絡(luò)拓?fù)洌撼醪皆黾拥模ǔ跏脊?jié)點(diǎn)為一個(gè)，每個(gè)時(shí)間間隔加入500個(gè)節(jié)點(diǎn)，執(zhí)行20次加入）；晶格網(wǎng)（規(guī)則網(wǎng)）；隨機(jī)圖。一個(gè)首要的基本條件是協(xié)議的運(yùn)行不能導(dǎo)致網(wǎng)絡(luò)分區(qū)現(xiàn)象的產(chǎn)生。push模式會(huì)導(dǎo)致網(wǎng)絡(luò)分區(qū)，而pushpull模式不會(huì)導(dǎo)致這種現(xiàn)象發(fā)生。根據(jù)實(shí)驗(yàn)，在度分布上pushpull模式明顯優(yōu)于push模式，pushpull可以很好的均衡節(jié)點(diǎn)入度分布，起到負(fù)載均衡的作用。缺乏自適應(yīng)性與魯棒性使得純push模式不可用。swapper模式可以取得較好的度分布（度分布的方差較?。?；healer模式次之，blind模式最差。1）靜態(tài)屬性：考慮度與參數(shù)H，S的關(guān)系。H確定，S增大可以減少度

22、分布的不均勻性；而S確定，H增大同樣可以減少度分布的不均勻性。2）動(dòng)態(tài)屬性：考慮節(jié)點(diǎn)入度的變化速度，變化的快不快。入度變化慢意味著入度高的節(jié)點(diǎn)在較長(zhǎng)時(shí)間內(nèi)處于熱點(diǎn)狀態(tài)，不利于負(fù)載均衡。首先，根據(jù)實(shí)驗(yàn)節(jié)點(diǎn)入度并非一成不變。對(duì)于一段連續(xù)時(shí)間間隔中的某個(gè)給定節(jié)點(diǎn)，考察這個(gè)節(jié)點(diǎn)度的自相關(guān)性（即在不同時(shí)刻節(jié)點(diǎn)入度的關(guān)聯(lián)性），假設(shè)節(jié)點(diǎn)入度為d1，d2，dk。則在時(shí)間間隔k內(nèi)序列d1，d2，dk的自相關(guān)性定義為rk。，自相關(guān)性高說明隨機(jī)性差，自相關(guān)性為0說明隨機(jī)性好。實(shí)驗(yàn)表明，healer模式的自相關(guān)性降低最快。也就是說，healer模式有助于負(fù)載均衡（節(jié)點(diǎn)度變化趨向隨機(jī)，變化較快，不會(huì)出現(xiàn)某個(gè)節(jié)點(diǎn)長(zhǎng)期處于

23、熱點(diǎn)狀態(tài)）。b）平均路徑長(zhǎng)度：節(jié)點(diǎn)a與b的最短路徑定義為從a到b需要經(jīng)過的最少的邊，而圖的最短路徑定義為所有節(jié)點(diǎn)之間最短路徑的平均值。研究最短路徑的動(dòng)機(jī)在于進(jìn)行消息分發(fā)的應(yīng)用時(shí)，最短路徑反映了一個(gè)節(jié)點(diǎn)可達(dá)的時(shí)間與開銷的下限。實(shí)驗(yàn)表明所有的H與S取值都可以獲取較低的平均路徑長(zhǎng)度，但較大的S值可以獲取接近隨機(jī)圖的效果。c）集群系數(shù)：集群系數(shù)反映節(jié)點(diǎn)a的鄰居之間是否也是鄰居的可能性。分析集群系數(shù)的動(dòng)機(jī)在于消息分發(fā)的應(yīng)用與自修復(fù)時(shí)，高集群系數(shù)可能破壞消息分發(fā)（增加了冗余消息）與自修復(fù)（增加了分區(qū)的概率）的效果。H值越大，則集群系數(shù)越高，這是因?yàn)镠值偏大表示節(jié)點(diǎn)都僅僅保留最新鮮的節(jié)點(diǎn)描述符使得各自的vi

24、ew重合部分較多。S值越大則可以降低集群系數(shù)，這是因?yàn)镾值偏大可以控制節(jié)點(diǎn)view彼此之間拓?fù)湫畔⒁愿吒怕式粨Q而不是保持一致。六、容錯(cuò)分析主要是引入節(jié)點(diǎn)失效的劇變場(chǎng)景與網(wǎng)絡(luò)擾動(dòng)場(chǎng)景來評(píng)估協(xié)議的魯棒性。a）節(jié)點(diǎn)失效劇變場(chǎng)景：如何建立收斂后的拓?fù)涞淖孕迯?fù)能力與節(jié)點(diǎn)失效個(gè)數(shù)之間的函數(shù)關(guān)系？在靜態(tài)場(chǎng)景中對(duì)隨機(jī)網(wǎng)絡(luò)圖實(shí)施突然的節(jié)點(diǎn)刪除，根據(jù)實(shí)驗(yàn)，最終直到刪除67%的隨機(jī)節(jié)點(diǎn)網(wǎng)絡(luò)才出現(xiàn)分區(qū)。在動(dòng)態(tài)場(chǎng)景中我們從收斂的隨機(jī)拓?fù)渲袆h除50%的節(jié)點(diǎn)來觀察其行為，發(fā)現(xiàn)H值偏大可以導(dǎo)致很快的拓?fù)湫迯?fù)。b）網(wǎng)絡(luò)擾動(dòng)場(chǎng)景：關(guān)注擾動(dòng)率與重啟動(dòng)方法（bootstrapping）。擾動(dòng)率分為正常擾動(dòng)率，一般為1%-2%；和劇烈

25、擾動(dòng)率，一般為30%。假設(shè)存在兩種重啟動(dòng)方法，中心化和隨機(jī)。H值增大可以降低擾動(dòng)時(shí)view中的無效節(jié)點(diǎn)，加速無效節(jié)點(diǎn)的刪除。healer模式可以容忍劇烈的擾動(dòng)。七、結(jié)論與討論1） 關(guān)于隨機(jī)性：swapper模式的隨機(jī)性最好，可以獲得比隨機(jī)圖還小的度的方差（就是節(jié)點(diǎn)的入度變化很?。黾親值會(huì)增大集群系數(shù)。在所有模式下平均路徑長(zhǎng)度都接近隨機(jī)圖。隨機(jī)性與應(yīng)用程序的需求本質(zhì)相關(guān)，比如將信息洪泛到網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)只與網(wǎng)絡(luò)半徑有關(guān)，而與度分布和集群系數(shù)無關(guān)。故如果需要計(jì)算本地的一些對(duì)全局的統(tǒng)計(jì)估值，如網(wǎng)絡(luò)容量，或全局可用資源等屬性不需要全局隨機(jī)性（這個(gè)觀點(diǎn)好像不對(duì)，應(yīng)該和全局隨機(jī)性有關(guān)，全局的隨機(jī)性利于更

26、快的aggregation）。2） 關(guān)于負(fù)載均衡：負(fù)載均衡與度分布有關(guān)，如果一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)描述符被很多其他節(jié)點(diǎn)都持有在view中，則這個(gè)節(jié)點(diǎn)具有更高概率作為目標(biāo)節(jié)點(diǎn)與其他節(jié)點(diǎn)發(fā)生gossip通信，也具有更高概率被采樣到提供給上層應(yīng)用使用，而導(dǎo)致這個(gè)節(jié)點(diǎn)產(chǎn)生更多的流量，引發(fā)負(fù)載不均衡。達(dá)到負(fù)載均衡最好的模式是swapper模式。如果H值固定，增大S可以減少節(jié)點(diǎn)入度的方差；但如果S值固定，增加H同樣可以減少節(jié)點(diǎn)入度的方差。3） 關(guān)于容錯(cuò)：H值越大越好，H值越大有助于快速的刪除失效鏈路，實(shí)現(xiàn)快速的修復(fù)。注：與楊朱二人討論中，二人提到：1）當(dāng)a向b發(fā)送緩存的節(jié)點(diǎn)描述符中，除了a自身的age被初始化為0

27、，其他節(jié)點(diǎn)描述符的age是否也初始化為0？個(gè)人觀點(diǎn)，如果其他節(jié)點(diǎn)描述符的age不初始化為0，則在執(zhí)行函數(shù)removeOldestItems(min(H, view.size-c)時(shí)，若buffer中的元素age都偏大，則會(huì)直接刪除很多元素，這樣難以實(shí)現(xiàn)swapper模式。（節(jié)點(diǎn)描述符只有通過自己主動(dòng)向網(wǎng)絡(luò)中注入，即除了節(jié)點(diǎn)會(huì)將自己的age出師化為0發(fā)送外，其他選入buffer中的描述符age維持原值不變）2）針對(duì)函數(shù)view.removeDuplicates()，如果兩個(gè)address相同的元素，到底是刪除age值小的還是age值大的（如果刪除age值大的，就傾向于保留新鮮節(jié)點(diǎn)，如果刪除age

28、值小的，就傾向于維持原有view不變化）。（保留較新的，剔除較老的）附：基于RW的隨機(jī)采樣技術(shù)（on unbiased peer sampling for unstructured peer-to-peer networks）本文闡述真實(shí)的p2p系統(tǒng)的動(dòng)態(tài)性與異構(gòu)性如何引入了節(jié)點(diǎn)采樣時(shí)發(fā)生的偏見性。并提出Metropolized Random Walk with Backtracking（MRWB）作為一個(gè)重要的技術(shù)來收集無偏采樣節(jié)點(diǎn)。背景：采樣是利用輕量級(jí)的數(shù)據(jù)收集方法來了解系統(tǒng)的一些屬性。過去的采樣傾向引入偏見，有兩個(gè)原因：1.節(jié)點(diǎn)的動(dòng)態(tài)特性可能引起偏向于那些生命周期短的節(jié)點(diǎn)；2.覆蓋拓?fù)?/p>

29、的異構(gòu)性導(dǎo)致偏向于連接度高的節(jié)點(diǎn)。本文的貢獻(xiàn)：1.對(duì)p2p系統(tǒng)使用了詳細(xì)的檢查方法檢查采樣在時(shí)空維度上的質(zhì)量。2.深度探索MRWB采樣方法的可用性。采樣偏向性產(chǎn)生的第一個(gè)原因來自系統(tǒng)的動(dòng)態(tài)性，新peer到達(dá)，存在的peer在任意時(shí)間可以離開，文章表明這樣容易導(dǎo)致采樣偏向于存活時(shí)間短的節(jié)點(diǎn)。第二個(gè)產(chǎn)生偏向的原因是P2P系統(tǒng)的連通結(jié)構(gòu)（采樣可以用于給網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行拓?fù)鋱D推測(cè)），每個(gè)鏈路更有可能導(dǎo)致采樣到一個(gè)高連接度節(jié)點(diǎn)而非低連接度節(jié)點(diǎn)。相關(guān)對(duì)比技術(shù)：1.圖采樣Cooper等的方法是利用隨機(jī)算法生成一系列圖，這些圖具有所有需求的圖屬性。本文目的在于：并非從一類圖中采樣一個(gè)圖，而是從一個(gè)未知大規(guī)模動(dòng)態(tài)改

30、變的圖中進(jìn)行節(jié)點(diǎn)采樣。另一個(gè)相關(guān)的問題是通過從少量主機(jī)向大量目標(biāo)執(zhí)行tracerout來采樣internet路由器，目的是發(fā)現(xiàn)internet級(jí)別的拓?fù)?。但是探測(cè)路由器拓?fù)浜蚉2P拓?fù)湓趫D的探測(cè)方面的基本操作各不相同。使用tracerout的目的在于“到目的地的路徑是什么”，而P2P網(wǎng)絡(luò)中基本問題是：這個(gè)節(jié)點(diǎn)的鄰居是誰(shuí)？。此外，internet路由器拓?fù)涓淖兒苈蚁鄬?duì)很穩(wěn)定，而P2P覆蓋網(wǎng)絡(luò)的拓?fù)鋭?dòng)態(tài)性強(qiáng)。另一個(gè)相關(guān)問題是從一系列web pages中均勻隨機(jī)選擇web page。web page通過超鏈接相連，具有有向性，易于發(fā)現(xiàn)關(guān)系。2.RW的圖采樣就作者了解，從一個(gè)動(dòng)態(tài)圖中進(jìn)行均勻隨機(jī)的R

31、W采樣沒有被研究過。很多論文將RW作為無結(jié)構(gòu)P2P網(wǎng)絡(luò)中的偏好搜索。搜索只需要沿著路徑定位某一個(gè)資源數(shù)據(jù)，不會(huì)全局考慮節(jié)點(diǎn)的采樣。Awan提到了P2P網(wǎng)絡(luò)中的均勻采樣，使用了幾種RW算法包括Metroplis-Hastings方法，但是需要假設(shè)圖結(jié)構(gòu)沒有動(dòng)態(tài)改變，同時(shí)還需要某些P2P應(yīng)用的底層支撐（使用的是power-law模型）。3.在隱藏的Populations中采樣P2P網(wǎng)絡(luò)中的隱藏節(jié)點(diǎn)指由于沒有中心存儲(chǔ)結(jié)構(gòu)使得可以查詢所有的節(jié)點(diǎn)，節(jié)點(diǎn)必須通過查詢其他節(jié)點(diǎn)的鄰居才能被發(fā)現(xiàn)。最有名的是respondent-driven sampling方法，這是一種滾雪球式的辦法。這個(gè)方法首先用采樣推測(cè)底

32、層網(wǎng)絡(luò)結(jié)構(gòu)，然后使用與網(wǎng)絡(luò)有關(guān)的估值來獲取不同感興趣領(lǐng)域的subpopulations。這個(gè)方法同樣不能適用于動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境。4.動(dòng)態(tài)圖這些模型不適合P2P系統(tǒng).網(wǎng)絡(luò)被看作是一個(gè)圖G=G(V, E)，網(wǎng)絡(luò)中的節(jié)點(diǎn)被看作頂點(diǎn)集合V，節(jié)點(diǎn)之間的連接被看作邊集合E。由于系統(tǒng)是一個(gè)動(dòng)態(tài)變化的系統(tǒng)，故將時(shí)間參數(shù)整合到系統(tǒng)中。整個(gè)網(wǎng)絡(luò)被看作基于時(shí)間索引的圖的無限集合。從這個(gè)圖的集合中進(jìn)行采樣的一個(gè)通用方法就是定義一個(gè)測(cè)量窗口，。并且從那些在窗口時(shí)間內(nèi)一直存活的節(jié)點(diǎn)中均勻隨機(jī)的選擇節(jié)點(diǎn)：。因此在不同時(shí)間出現(xiàn)的同一個(gè)節(jié)點(diǎn)不會(huì)被區(qū)分。當(dāng)前測(cè)量方法表明，節(jié)點(diǎn)的存活時(shí)間長(zhǎng)度非常不均勻，并不符合指數(shù)分布規(guī)律。大量節(jié)點(diǎn)的存活時(shí)間很短（幾分鐘），但少量節(jié)點(diǎn)長(zhǎng)期存在。故當(dāng)增大時(shí)間窗口長(zhǎng)度，集合將會(huì)包含更多的存活時(shí)間短的節(jié)點(diǎn)。本文目的不在于從集合采樣一個(gè)節(jié)點(diǎn)vi，而在于采樣在某個(gè)特定時(shí)刻t的節(jié)點(diǎn)vi的某個(gè)屬性（一個(gè)節(jié)點(diǎn)的