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

1、基于gossip機(jī)制的節(jié)點采樣技術(shù)概述（gossip-based peer sampling）一、這是什么技術(shù)，為什么需要這個技術(shù)Gossip機(jī)制，即流言機(jī)制，作為一種簡單可靠的拓?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é)點規(guī)模的可擴(kuò)展性與消息分發(fā)的可靠性難以得到有效保證?；趃ossip機(jī)制的覆蓋網(wǎng)絡(luò)協(xié)議模仿流言傳播的特性，系統(tǒng)中的每個節(jié)點定期的從鄰居表中選擇一個節(jié)點子集，然后與這個子集中的節(jié)點進(jìn)行拓?fù)湫畔ⅲㄠ従颖硇畔ⅲ┑慕粨Q，來維持一種

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

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

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

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

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

7、符的存活時間，時間戳的值越大則表明這個描述符存在于節(jié)點的局部視圖中的時間越長?？梢哉J(rèn)為節(jié)點的局部視圖是一個數(shù)據(jù)結(jié)構(gòu)，在這之上定義了一組操作集合。這意味著除非某個特殊的操作施加于局部視圖，否則局部視圖中的元素順序不會顯式變化。同時規(guī)定局部視圖中不允許存在相同網(wǎng)絡(luò)地址的兩個描述符。節(jié)點定期持續(xù)進(jìn)行g(shù)ossip的交換過程來保證局部視圖中的描述符是系統(tǒng)全局拓?fù)湫畔⒌囊粋€隨機(jī)集合，使得局部視圖可以反映系統(tǒng)的動態(tài)變化。下面給出具體實現(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é)議包含兩個線程：主動線程用于初始化與其他節(jié)點的通信；被動線程用于接受其他節(jié)點的請求并響應(yīng)。（對于view.select(c, H, S, buffer(p)函數(shù)，其每一句代碼都很重要，實質(zhì)就是對view這個數(shù)據(jù)結(jié)構(gòu)進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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