于莉
摘 要:本文主要介紹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
內蒙古教育·職教版2014年10期