Pastry協(xié)議分析

于莉

摘 要：本文主要介紹Pastry協(xié)議的設計理論基礎，包括協(xié)議的設計背景、在Pastry網絡中節(jié)點的體系結構，以及協(xié)議最核心的路由算法。

關鍵詞：Pastry 協(xié)議 路由表 鄰近節(jié)點 葉子節(jié)點

一、Pastry分布式網絡協(xié)議概念

Pastry 屬于一種混合式結構的P2P網絡，具有高效、可以擴展等特點。此外，Pastry還是眾多分布式應用的底層架構。Pastry使用SHA-1算法將節(jié)點和消息都映射到一個128位的空間中。每個節(jié)點負責管理與它的位置（以下稱為NodeID）在數值上面最接近的消息（以下稱為ObjID）。這與Chord協(xié)議有點像。Pastry協(xié)議將這128位劃分為若干個組，每一組有連續(xù)的2^b位，通常b取3或4。在這種情況下，每一個ID可以被看做若干層，其中第l層所指的是從第b*l到b*（l+1）-1位。Pastry將環(huán)形結構和超立方體機構的優(yōu)點完美地結合起來，將分布式的對象定位、單獨于具體應用的負載平衡和高效的查詢路由提供出來。 Pastry將使用一致性的哈希作為哈希算法，哈希所獲得的鍵值就是一維，Pastry沒有對使用哪一種哈希算法進行明確的規(guī)定。在Pastry協(xié)議中，所有的節(jié)點均有一個128bit的標識（Node Id）。為了使每個節(jié)點有唯一的128bit的標識，一般要通過哈希獲得唯一的Node Id。 在Pastry中，所有的節(jié)點都有路由表R一個，鄰近節(jié)點集M一個，葉子節(jié)點集合L一個，而節(jié)點的狀態(tài)表就是由這些構成的。

二、Pastry節(jié)點體系結構

1.路由表

路由表由行和2b項組成。其中可以發(fā)現，路由表越往下空缺項越多，也就使得找到符合條件的節(jié)點變得很難。然而，空缺項不會對Pastry正確路由造成影響，只不過會使路由的速度有變慢的可能。

2. 葉節(jié)點表

葉節(jié)點表L中包含丨L丨個與當前節(jié)點ID最鄰近的“葉節(jié)點”。葉節(jié)點表的作用在于保證Pastry路由的正確性。

3. 鄰近節(jié)點表

為了使Pastry工作的局部性有所增強，鄰近節(jié)點表M將在物理網絡層和離當前節(jié)點最近丨M丨個節(jié)點的ID和IP地址保存下來。

4. Pastry路由算法

以Pastry核心路由算法為例（見圖1），A表示當前節(jié)點的ID，D表示目的地節(jié)點ID。

（1）if（L-「丨L丨/2」≤D≤L「丨L丨/2」）{

（2） //D is within range of our leaf set

（3） forward to Li，s.th.丨D-Li丨 is minimal

（4） } else {

（5） //use the routing table

（6） Letl=shl（D，A）；

（7） if（R≠null）{

（8） fourward to R

（9） }

（10） else{

（11） //rare case

（12） forward to T∈L∪R∪M，s.th.

（13） shl（T，D）≥l，

（14） 丨T-D丨<丨A-D丨

（15） }

（16） }

圖1 Pastry核心路由算法

在上述的路由算法中，第（1）～（3）行檢查的是節(jié)點D在沒在目前節(jié)點的葉節(jié)點表的范圍之內。若它在，則直接將消息傳給葉節(jié)點表中離D最近的節(jié)點，這個節(jié)點是和D實際對應的；否則要將路由表使用起來，一般情況下，路由會將消息帶到前綴至少多匹配一位的節(jié)點，也就是第（5）～（9）行。然而，有的時候，路由的該項會出現空缺或者沒有抵達，這個時候不能和更多位匹配，故路由將消息帶到和D離得更近的表項，也就是第（10）～（15）行，該項從L、R、M中選取。

上述的算法表明，有兩種可能性，一是Pastry路由至少多匹配一位，一是Pastry路由能夠找到比當前節(jié)點離目的節(jié)點D更近的ID。所以，通常在路由表項內容正確和無節(jié)點失效的情況下，Pastry路由跳步數為。而在系統(tǒng)中節(jié)點同時失效，正常節(jié)點在更新它們的表項內容時，最壞情況下的路由跳步數可能會接近N。但是如果對參數丨L丨合理選擇，這樣的可能性幾乎是不可能的。

三、Pastry的自組織和自適應機制

1.節(jié)點的加入

要想節(jié)點加入，應當做好三項工作：（1）將自己的路由表、葉節(jié)點表和鄰居節(jié)點表初始化；（2）讓其他節(jié)點知道自己要來了；（3）需要讓現在的節(jié)點提供該節(jié)點要負責的數據和文件。

2.節(jié)點的離開

節(jié)點的離開，有主動離開的可能性，有沒有預兆、突然離開的可能性。更容易處理的是第一種方式，因為節(jié)點在離開之前，只需讓它所知節(jié)點知道它要離開就行。

離開步驟1：修正葉節(jié)點表

離開步驟2：修正路由表

離開步驟3：修正鄰居節(jié)點表

四、Pastry的局部性

Pastry的局部性分兩部分來實現：第一步是體現在路由表的構造上，但是路由表項中的局部性并不準確；在路由表初始化之后，第二步，新節(jié)點通過鄰居節(jié)點表M修正路由表項，以M為參考標準，用物理網絡上離自己很近的節(jié)點替換原有項。第二個步驟對于Pastry的局部性有本質的意義，故Pastry的局部性是以鄰居節(jié)點表為依據的。

以實例加以說明，因為A與X在物理網絡上很近，用數學歸納法，假設Pastry在X加入之前，每次為新節(jié)點構造路由表時都考慮了局部性，那么在三角關系近似滿足的情況下可以推出：當X從A中復制第0行作為自己的路由表第0行、從A中復制鄰居節(jié)點表M作為自己的鄰居集、并用M來修正過第0行后，X的路由表第0行節(jié)點跟X在物理上都是鄰近的。隨著跳數的增加，局部性將變差，三件關系越來越不成立，因此X離其路由表中第1行節(jié)點會比較遠，離第2行節(jié)點會更遠，依次類推。這樣的局部性關系反映在圖2中。

圖2 Pastry路由表局部性關系

Pastry采用傳統(tǒng)的ID鄰近復制，同一數據文件被復制到與其ID相近的k個節(jié)點上。這實際上也提供了一定的數據存取局部性：因為Pastry中節(jié)點ID與節(jié)點本身屬性無關，因此ID鄰近的節(jié)點通常分散在整個網絡中，而Pastry定位對象時主要依靠ID，如果要查詢某個文件，定位機制通常會在大致相當的時間里找到這些節(jié)點，然后由查詢者決定需要哪個副本。由于k個副本通常均勻分散，所以總會有一兩個離查詢者很近。

五、結束語

在Pastry的網絡系統(tǒng)中，節(jié)點ID是整個系統(tǒng)能正常工作的基礎，每個節(jié)點通過維護三個表優(yōu)化和加速整個路由過程。在優(yōu)良的自適應算法的支持下，Pastry網絡具有容錯、自組織能力。一個文件在系統(tǒng)中會分散保存在一系列的節(jié)點中，這樣也能為用戶對信息的查找提供巨大的便利。endprint

摘 要：本文主要介紹Pastry協(xié)議的設計理論基礎，包括協(xié)議的設計背景、在Pastry網絡中節(jié)點的體系結構，以及協(xié)議最核心的路由算法。

關鍵詞：Pastry 協(xié)議 路由表 鄰近節(jié)點 葉子節(jié)點

一、Pastry分布式網絡協(xié)議概念

Pastry 屬于一種混合式結構的P2P網絡，具有高效、可以擴展等特點。此外，Pastry還是眾多分布式應用的底層架構。Pastry使用SHA-1算法將節(jié)點和消息都映射到一個128位的空間中。每個節(jié)點負責管理與它的位置（以下稱為NodeID）在數值上面最接近的消息（以下稱為ObjID）。這與Chord協(xié)議有點像。Pastry協(xié)議將這128位劃分為若干個組，每一組有連續(xù)的2^b位，通常b取3或4。在這種情況下，每一個ID可以被看做若干層，其中第l層所指的是從第b*l到b*（l+1）-1位。Pastry將環(huán)形結構和超立方體機構的優(yōu)點完美地結合起來，將分布式的對象定位、單獨于具體應用的負載平衡和高效的查詢路由提供出來。 Pastry將使用一致性的哈希作為哈希算法，哈希所獲得的鍵值就是一維，Pastry沒有對使用哪一種哈希算法進行明確的規(guī)定。在Pastry協(xié)議中，所有的節(jié)點均有一個128bit的標識（Node Id）。為了使每個節(jié)點有唯一的128bit的標識，一般要通過哈希獲得唯一的Node Id。 在Pastry中，所有的節(jié)點都有路由表R一個，鄰近節(jié)點集M一個，葉子節(jié)點集合L一個，而節(jié)點的狀態(tài)表就是由這些構成的。

二、Pastry節(jié)點體系結構

1.路由表

路由表由行和2b項組成。其中可以發(fā)現，路由表越往下空缺項越多，也就使得找到符合條件的節(jié)點變得很難。然而，空缺項不會對Pastry正確路由造成影響，只不過會使路由的速度有變慢的可能。

2. 葉節(jié)點表

葉節(jié)點表L中包含丨L丨個與當前節(jié)點ID最鄰近的“葉節(jié)點”。葉節(jié)點表的作用在于保證Pastry路由的正確性。

3. 鄰近節(jié)點表

為了使Pastry工作的局部性有所增強，鄰近節(jié)點表M將在物理網絡層和離當前節(jié)點最近丨M丨個節(jié)點的ID和IP地址保存下來。

4. Pastry路由算法

以Pastry核心路由算法為例（見圖1），A表示當前節(jié)點的ID，D表示目的地節(jié)點ID。

（1）if（L-「丨L丨/2」≤D≤L「丨L丨/2」）{

（2） //D is within range of our leaf set

（3） forward to Li，s.th.丨D-Li丨 is minimal

（4） } else {

（5） //use the routing table

（6） Letl=shl（D，A）；

（7） if（R≠null）{

（8） fourward to R

（9） }

（10） else{

（11） //rare case

（12） forward to T∈L∪R∪M，s.th.

（13） shl（T，D）≥l，

（14） 丨T-D丨<丨A-D丨

（15） }

（16） }

圖1 Pastry核心路由算法

在上述的路由算法中，第（1）～（3）行檢查的是節(jié)點D在沒在目前節(jié)點的葉節(jié)點表的范圍之內。若它在，則直接將消息傳給葉節(jié)點表中離D最近的節(jié)點，這個節(jié)點是和D實際對應的；否則要將路由表使用起來，一般情況下，路由會將消息帶到前綴至少多匹配一位的節(jié)點，也就是第（5）～（9）行。然而，有的時候，路由的該項會出現空缺或者沒有抵達，這個時候不能和更多位匹配，故路由將消息帶到和D離得更近的表項，也就是第（10）～（15）行，該項從L、R、M中選取。

上述的算法表明，有兩種可能性，一是Pastry路由至少多匹配一位，一是Pastry路由能夠找到比當前節(jié)點離目的節(jié)點D更近的ID。所以，通常在路由表項內容正確和無節(jié)點失效的情況下，Pastry路由跳步數為。而在系統(tǒng)中節(jié)點同時失效，正常節(jié)點在更新它們的表項內容時，最壞情況下的路由跳步數可能會接近N。但是如果對參數丨L丨合理選擇，這樣的可能性幾乎是不可能的。

三、Pastry的自組織和自適應機制

1.節(jié)點的加入

要想節(jié)點加入，應當做好三項工作：（1）將自己的路由表、葉節(jié)點表和鄰居節(jié)點表初始化；（2）讓其他節(jié)點知道自己要來了；（3）需要讓現在的節(jié)點提供該節(jié)點要負責的數據和文件。

2.節(jié)點的離開

節(jié)點的離開，有主動離開的可能性，有沒有預兆、突然離開的可能性。更容易處理的是第一種方式，因為節(jié)點在離開之前，只需讓它所知節(jié)點知道它要離開就行。

離開步驟1：修正葉節(jié)點表

離開步驟2：修正路由表

離開步驟3：修正鄰居節(jié)點表

四、Pastry的局部性

Pastry的局部性分兩部分來實現：第一步是體現在路由表的構造上，但是路由表項中的局部性并不準確；在路由表初始化之后，第二步，新節(jié)點通過鄰居節(jié)點表M修正路由表項，以M為參考標準，用物理網絡上離自己很近的節(jié)點替換原有項。第二個步驟對于Pastry的局部性有本質的意義，故Pastry的局部性是以鄰居節(jié)點表為依據的。

以實例加以說明，因為A與X在物理網絡上很近，用數學歸納法，假設Pastry在X加入之前，每次為新節(jié)點構造路由表時都考慮了局部性，那么在三角關系近似滿足的情況下可以推出：當X從A中復制第0行作為自己的路由表第0行、從A中復制鄰居節(jié)點表M作為自己的鄰居集、并用M來修正過第0行后，X的路由表第0行節(jié)點跟X在物理上都是鄰近的。隨著跳數的增加，局部性將變差，三件關系越來越不成立，因此X離其路由表中第1行節(jié)點會比較遠，離第2行節(jié)點會更遠，依次類推。這樣的局部性關系反映在圖2中。

圖2 Pastry路由表局部性關系

Pastry采用傳統(tǒng)的ID鄰近復制，同一數據文件被復制到與其ID相近的k個節(jié)點上。這實際上也提供了一定的數據存取局部性：因為Pastry中節(jié)點ID與節(jié)點本身屬性無關，因此ID鄰近的節(jié)點通常分散在整個網絡中，而Pastry定位對象時主要依靠ID，如果要查詢某個文件，定位機制通常會在大致相當的時間里找到這些節(jié)點，然后由查詢者決定需要哪個副本。由于k個副本通常均勻分散，所以總會有一兩個離查詢者很近。

五、結束語

在Pastry的網絡系統(tǒng)中，節(jié)點ID是整個系統(tǒng)能正常工作的基礎，每個節(jié)點通過維護三個表優(yōu)化和加速整個路由過程。在優(yōu)良的自適應算法的支持下，Pastry網絡具有容錯、自組織能力。一個文件在系統(tǒng)中會分散保存在一系列的節(jié)點中，這樣也能為用戶對信息的查找提供巨大的便利。endprint

摘 要：本文主要介紹Pastry協(xié)議的設計理論基礎，包括協(xié)議的設計背景、在Pastry網絡中節(jié)點的體系結構，以及協(xié)議最核心的路由算法。

關鍵詞：Pastry 協(xié)議 路由表 鄰近節(jié)點 葉子節(jié)點

一、Pastry分布式網絡協(xié)議概念

Pastry 屬于一種混合式結構的P2P網絡，具有高效、可以擴展等特點。此外，Pastry還是眾多分布式應用的底層架構。Pastry使用SHA-1算法將節(jié)點和消息都映射到一個128位的空間中。每個節(jié)點負責管理與它的位置（以下稱為NodeID）在數值上面最接近的消息（以下稱為ObjID）。這與Chord協(xié)議有點像。Pastry協(xié)議將這128位劃分為若干個組，每一組有連續(xù)的2^b位，通常b取3或4。在這種情況下，每一個ID可以被看做若干層，其中第l層所指的是從第b*l到b*（l+1）-1位。Pastry將環(huán)形結構和超立方體機構的優(yōu)點完美地結合起來，將分布式的對象定位、單獨于具體應用的負載平衡和高效的查詢路由提供出來。 Pastry將使用一致性的哈希作為哈希算法，哈希所獲得的鍵值就是一維，Pastry沒有對使用哪一種哈希算法進行明確的規(guī)定。在Pastry協(xié)議中，所有的節(jié)點均有一個128bit的標識（Node Id）。為了使每個節(jié)點有唯一的128bit的標識，一般要通過哈希獲得唯一的Node Id。 在Pastry中，所有的節(jié)點都有路由表R一個，鄰近節(jié)點集M一個，葉子節(jié)點集合L一個，而節(jié)點的狀態(tài)表就是由這些構成的。

二、Pastry節(jié)點體系結構

1.路由表

路由表由行和2b項組成。其中可以發(fā)現，路由表越往下空缺項越多，也就使得找到符合條件的節(jié)點變得很難。然而，空缺項不會對Pastry正確路由造成影響，只不過會使路由的速度有變慢的可能。

2. 葉節(jié)點表

葉節(jié)點表L中包含丨L丨個與當前節(jié)點ID最鄰近的“葉節(jié)點”。葉節(jié)點表的作用在于保證Pastry路由的正確性。

3. 鄰近節(jié)點表

為了使Pastry工作的局部性有所增強，鄰近節(jié)點表M將在物理網絡層和離當前節(jié)點最近丨M丨個節(jié)點的ID和IP地址保存下來。

4. Pastry路由算法

以Pastry核心路由算法為例（見圖1），A表示當前節(jié)點的ID，D表示目的地節(jié)點ID。

（1）if（L-「丨L丨/2」≤D≤L「丨L丨/2」）{

（2） //D is within range of our leaf set

（3） forward to Li，s.th.丨D-Li丨 is minimal

（4） } else {

（5） //use the routing table

（6） Letl=shl（D，A）；

（7） if（R≠null）{

（8） fourward to R

（9） }

（10） else{

（11） //rare case

（12） forward to T∈L∪R∪M，s.th.

（13） shl（T，D）≥l，

（14） 丨T-D丨<丨A-D丨

（15） }

（16） }

圖1 Pastry核心路由算法

在上述的路由算法中，第（1）～（3）行檢查的是節(jié)點D在沒在目前節(jié)點的葉節(jié)點表的范圍之內。若它在，則直接將消息傳給葉節(jié)點表中離D最近的節(jié)點，這個節(jié)點是和D實際對應的；否則要將路由表使用起來，一般情況下，路由會將消息帶到前綴至少多匹配一位的節(jié)點，也就是第（5）～（9）行。然而，有的時候，路由的該項會出現空缺或者沒有抵達，這個時候不能和更多位匹配，故路由將消息帶到和D離得更近的表項，也就是第（10）～（15）行，該項從L、R、M中選取。

上述的算法表明，有兩種可能性，一是Pastry路由至少多匹配一位，一是Pastry路由能夠找到比當前節(jié)點離目的節(jié)點D更近的ID。所以，通常在路由表項內容正確和無節(jié)點失效的情況下，Pastry路由跳步數為。而在系統(tǒng)中節(jié)點同時失效，正常節(jié)點在更新它們的表項內容時，最壞情況下的路由跳步數可能會接近N。但是如果對參數丨L丨合理選擇，這樣的可能性幾乎是不可能的。

三、Pastry的自組織和自適應機制

1.節(jié)點的加入

要想節(jié)點加入，應當做好三項工作：（1）將自己的路由表、葉節(jié)點表和鄰居節(jié)點表初始化；（2）讓其他節(jié)點知道自己要來了；（3）需要讓現在的節(jié)點提供該節(jié)點要負責的數據和文件。

2.節(jié)點的離開

節(jié)點的離開，有主動離開的可能性，有沒有預兆、突然離開的可能性。更容易處理的是第一種方式，因為節(jié)點在離開之前，只需讓它所知節(jié)點知道它要離開就行。

離開步驟1：修正葉節(jié)點表

離開步驟2：修正路由表

離開步驟3：修正鄰居節(jié)點表

四、Pastry的局部性

Pastry的局部性分兩部分來實現：第一步是體現在路由表的構造上，但是路由表項中的局部性并不準確；在路由表初始化之后，第二步，新節(jié)點通過鄰居節(jié)點表M修正路由表項，以M為參考標準，用物理網絡上離自己很近的節(jié)點替換原有項。第二個步驟對于Pastry的局部性有本質的意義，故Pastry的局部性是以鄰居節(jié)點表為依據的。

以實例加以說明，因為A與X在物理網絡上很近，用數學歸納法，假設Pastry在X加入之前，每次為新節(jié)點構造路由表時都考慮了局部性，那么在三角關系近似滿足的情況下可以推出：當X從A中復制第0行作為自己的路由表第0行、從A中復制鄰居節(jié)點表M作為自己的鄰居集、并用M來修正過第0行后，X的路由表第0行節(jié)點跟X在物理上都是鄰近的。隨著跳數的增加，局部性將變差，三件關系越來越不成立，因此X離其路由表中第1行節(jié)點會比較遠，離第2行節(jié)點會更遠，依次類推。這樣的局部性關系反映在圖2中。

圖2 Pastry路由表局部性關系

Pastry采用傳統(tǒng)的ID鄰近復制，同一數據文件被復制到與其ID相近的k個節(jié)點上。這實際上也提供了一定的數據存取局部性：因為Pastry中節(jié)點ID與節(jié)點本身屬性無關，因此ID鄰近的節(jié)點通常分散在整個網絡中，而Pastry定位對象時主要依靠ID，如果要查詢某個文件，定位機制通常會在大致相當的時間里找到這些節(jié)點，然后由查詢者決定需要哪個副本。由于k個副本通常均勻分散，所以總會有一兩個離查詢者很近。

五、結束語

在Pastry的網絡系統(tǒng)中，節(jié)點ID是整個系統(tǒng)能正常工作的基礎，每個節(jié)點通過維護三個表優(yōu)化和加速整個路由過程。在優(yōu)良的自適應算法的支持下，Pastry網絡具有容錯、自組織能力。一個文件在系統(tǒng)中會分散保存在一系列的節(jié)點中，這樣也能為用戶對信息的查找提供巨大的便利。endprint