宽带媒体服务技术之对等网络
第四章 第三代P2P网络
——结构化P2P体系
Chord、CAN、Tapestry、Pastry
宽带媒体服务技术之对等网络
章节内容
Chord与CFS：简单、精确的环形P2P网络
CAN：简单、容错的多维空间P2P网络
Tapestry与OceanStore：广域的超立方体结构
P2P网络
Pastry与PAST：容错的混合式结构P2P网络
其它结构化P2P网络：Kademlia、SkipNet等
常数度P2P模型：Viceroy、Koorde和Cycloid
结构化P2P网络的特点与分析
宽带媒体服务技术之对等网络
概述
2001年，学术界P2P历史上的里程碑
IEEE成立P2P专业会议、ACM会议专题等
提出结构化P2P的几个经典模型与应用体系，
如Chord、CAN、Tapestry、Pastry
著名学术团体与技术组织成立专门的P2P研究
组，如MIT、UC Berkeley、Microsoft、
Stanford
宽带媒体服务技术之对等网络
Chord与CFS：简单、精确的环形
P2P网络
MIT与Berkeley的研究者01年正式发表
宽带媒体服务技术之对等网络
Chord作为一个P2P网络，是基于带弦环拓扑
结构的分布式系统，提供对象的存储、查询、
复制、缓存，在其上可以架构更高层的分布式
数据存储系统如协同文件系统CFS
Chord作为一个分布式散列表，只支持结构化
P2P最简单的功能：将结点和数据对象映射到
覆盖网中，但具有几乎最优的路由效率、确定
性的对象查询、负载均衡、高可靠性以及良好
的容错性与自适应，最主要的是：简单、优美
宽带媒体服务技术之对等网络
Chord的技术特点
基于安全的一致性散列函数来分配结点ID和对象ID
在一个有N个结点的网络中，每个Chord结点保存
O(logN)个其他结点的信息
查询数据对象需要的覆盖网路由跳数也为O(logN)
当结点加入或者离开网络时，为了维持网络结构、
保持自适应性所需要的消息数在O(log2N)
宽带媒体服务技术之对等网络
一、Chord基础工作原理
Chord使用安全散列函数（如SHA-1）为每个
网络结点和数据对象分配唯一的ID
nodeID=H(node属性)，属性可以是结点IP、port、
公钥、随机数或它们的组合
objectID=H(object属性)，属性可以是数据对象的名
称、内容、大小、发布者或者它们的组合
H是散列函数，SHA系列散列函数的Hash值长度
≥160，保证ID的唯一性
宽带媒体服务技术之对等网络
Chord按照如下方法将数据对象（只是其索引）
分配到网络结点中
所有的结点按照nodeID从小到大顺时针排列在一个
环上
数据对象k（ObjectID）被分配到环上顺时针方向
紧随k（包括与k相等）的第一个结点，该结点称为
对象k的后继，记做successor(k)
Chord结点n的后继是环上紧随n（不等于n）
的第一个结点，记做
宽带媒体服务技术之对等网络
一个简单的Chord环（m=3）
宽带媒体服务技术之对等网络
当Chord中有新结点n加入时，为保持正确、
一致的对象放置，原本由n的后继结点负责的
对象，其中一部分必须分配给n
当Chord中有旧结点n离开时，原本由n负责的
所有对象，必须分配给n的后继。除此以外，
对象不需要再做移动，这正是一致性散列函数
所追求的性质（问题：异常退出？）
例：图中新加入结点7
宽带媒体服务技术之对等网络
单纯的环可以工作，但效率太低
为此，结点维护一个有m（ID位数）项的路由
表，也称“指向表”（finger table），其中第i项
指向结点s，s=successor(n+2i-1)，1≤i≤m，即
s是在顺时针方向到n的距离至少为2i-1的第一
个结点，记做[i].node
Chord路由表的特点：
每个结点只保存很少的其它结点信息，并且对离它
越远的结点所知越少
Chord结点不能从自己的路由表中看出对象k的后继
宽带媒体服务技术之对等网络
为确定对象k的后继（k所在的结点）,结点n在
自己的路由表中查找在k之前且离k最近的结点
j，让j去找离k最近的结点，递归查找，最终可
以找到对象k的前驱（在k之前离k最近的结点，
记做predecessor(k)，类似，结点n的前驱记做
）
前驱中必然有后继的路由表项，定位成功
宽带媒体服务技术之对等网络
Chord结点n的路由表各项属性及其定义
属性 定义
finger[k].start (n+2k-1)mod2m, 1≤k≤m
.interval [finger[k].start, finger[k+1].start)
.node ≥[k].start的第一个
结点
successor 后继结点，即finger[1].node
predecessor 前驱结点
宽带媒体服务技术之对等网络
二、Chord对象定位算法
定位算法的三个函数的伪代码
//请求结点n寻找id的后继
_successor(id)
n’=find_predecessor(id);
return n’.successor;
//请求结点n寻找id的前驱
_predecessor(id)
n’=n;
while(id (n’,n’.sucessor])
n’=n’,closest_preceding_finger(id);
return n’;
宽带媒体服务技术之对等网络
//返回id之前最近的finger
_preceding_finger(id)
for i=m downto 1
if (finger[i].node∈(n,id))
return finger[i].node;
return n;
该函数是在定位过程中真正被多次调用执行的过程，其作用
是：结点在自己的路由表中，从后往前找到在id前且与id最
近的结点并返回
由Chord路由表的构造和定位算法可知：每次调用第
三个函数，新找到的结点离对象id的距离通常比原来
少一半，因此一般最多调用logN次即可定位成功
宽带媒体服务技术之对等网络
Chord路由表的简单示例
假设结点3要找到对象1的后
继
在结点3的路由表中，1属
于[3].interval即
[7,3)
结点3让[3].node
即结点0去找1
结点0在路由表中发现自
己的后继1恰好是对象1的
后继，因此将1返回给结
点3
结点3由此知道对象1放在
结点1中
宽带媒体服务技术之对等网络
三、Chord结点加入算法
Chord的自适应需要保持两个不变的属性
每个结点的后继始终正确
对每个对象k，结点successor(k)始终负责k的索引
为此，新结点n的加入需要完成三个任务
初始化n的前驱和路由表项
更新网络其他结点的前驱和路由表项
告诉其后继将应该由n负责的数据对象索引传递给n
宽带媒体服务技术之对等网络
新结点n连接到某个众所周知结点n’，通过调用
join(n’)初始化自己的状态信息，并将自己加入到
Chord网络
通过结点n’初始化n的路由表：请求n’帮自己查找后继，
从而更新自己的前驱，再通过多次调用n’的后继查找
函数来初始化自己的路由表
宽带媒体服务技术之对等网络
初始化本地结点的路由表
宽带媒体服务技术之对等网络
update_others()函数更新其他结点的状态信息以反映
n的加入，当且仅当满足下面两个条件时，结点n将成
为结点p路由表的第i项：
结点p在n之前至少2i-1
结点p路由表的当前第i项结点在n之后
满足这两个条件的第一个结点p是结点(n-2i-1)的前驱，
因此，update_others()首先找到该前驱，然后调用函
数update_finger_table(n,i)，递归地更新Chord网中所
有需要更新路由表第i项的结点信息
通常情况下，一个新结点加入Chord网，需要更新信
息的结点数为O(logN)，因此寻找和更新的时间复杂
度为O(log2N)
宽带媒体服务技术之对等网络
相关伪代码
宽带媒体服务技术之对等网络
四、Chord自适应算法
以上算法完备、细致，但有未解决的问题：并
发操作；不正常操作（如结点异常退出）
解决方法：
简化join函数，仅通过n’寻找n的后继，其它什么也
不做
每个Chord结点周期性调用稳定函数stabilize和路由
表更新函数fix_fingers，前者修正结点后继并通知
其后继修正前驱，后者在此基础上随机修正自己的
路由表项
通过合适的周期保持定位高效率
宽带媒体服务技术之对等网络
宽带媒体服务技术之对等网络
五、Chord容错性和复制、缓存
Chord中正确的后继关系是一切工作的基础
无论机制如何完善，网络的动态性和不确定性都可以
导致单后继失效
因此，实际的Chord给每个结点维护一个后继列表，
其中保存了该结点在Chord环上的r个后继，典型地取
r=O(logN)，即使结点失效概率为1/2，仍能正确定位
将结点保存的数据对象复制到所有后继中，可提高数
据的可用性、持久性
在Chord定位过程中，如每个中间结点缓存数据对象，
可以提高获取数据的速度
宽带媒体服务技术之对等网络
六、Chord实验分析
负载均衡
负载均衡是使用一致性散列函数的结构化P2P网络
的共同属性
对于Chord而言，由于数据对象被分配到其后继中，
而数据对象、结点的ID都是随机、均匀产生的，因
此每个结点所负担的数据对象也应该大致均衡
此外，Chord还采用了“虚拟服务器”的方法，在一
台计算机上运行多个Chord结点，可以使得结点各
尽所能
宽带媒体服务技术之对等网络
1万个结点，50万个数据对象
宽带媒体服务技术之对等网络
宽带媒体服务技术之对等网络
定位路径长度
理论量级为O(logN)跳
实验中网络结点数取N=2k，数据对象数取100×2k，
k从3取到14
测量结果：路径长度平均约logN/2，是logN的一半，
原因是Chord路由表的指数构造，使其每次查找都
能将目的ID与当前结点ID之间的差距减小至少一半，
可推导出平均路径长度正好是logN的一半
宽带媒体服务技术之对等网络
宽带媒体服务技术之对等网络
网络结点数为212
宽带媒体服务技术之对等网络
七、Chord总结
Chord采用带弦环拓扑结构，通过一致性散列函数将
结点、数据对象映射到覆盖网上，数据对象（索引）
由其后继结点负责，简单、精确正是Chord最大的特
点
每个Chord结点维护一个很小的路由表，后继关系是
Chord定位的基础，路由表可以将定位路径长度缩短
为O(logN)跳
Chord需要保持两个不变的属性才能正确工作：后继
正确、后继对对象的索引正确
Chord采用周期性的稳定算法和路由表更新算法检查
和修正后继关系及路由表项
宽带媒体服务技术之对等网络
为保持高容错性，Chord采用后继列表避免单后继失
效，此时可以对数据对象进行复制和缓存，提高网络
效率
宽带媒体服务技术之对等网络
八、CFS（Cooperative file
system）
CFS协同文件系统是以Chord为基础的P2P协
同只读文件存储系统，文件分块存储
CFS由三层构件组成
Chord，底层定位散列表：维护路由表，定位数据
块所在的服务器
DHash，分布式数据块散列表：中间层，分布和缓
存数据块以平衡负载，复制数据块以容错，并通过
服务器选择来减少时延；使用Chord定位数据块
FS，File System，文件系统：高层，从DHash层
获得数据块并转换为文件，给更高的应用提供文件
系统接口
宽带媒体服务技术之对等网络
CFS文件系统类似UNIX文件目录结构，只是以根块
代替根目录、以元数据块代替子目录、以数据块代替
文件，而以块标识代替文件地址
CFS对Chord的改进：采用前驱列表定位以提高定位
容错性，使用服务器选择减少定位时延，对结点ID认
证以防止ID伪造和IP虚报
CFS对数据块采用后继复制以提高数据可用性，同时
减少了客户获取数据的时延；采用路径缓存提高系统
工作效率，同时避免热点数据的后继结点负载过重；
采用“虚拟结点”和“限额”方法提供负载均衡
宽带媒体服务技术之对等网络
CAN：简单、容错的多维空间P2P
网络
Content Addressable Network，内容可寻址
网络，采用多维Torus环面拓扑结构，典型采
用的二维空间网格，类似于笛卡尔平面，其结
点编址方式也类似于点的编址
01年[Ratnasamy et al.]在ACM SIGCOMM会
议发表正式论文（与Chord同年同会）
宽带媒体服务技术之对等网络
CAN的多维空间被动态地分配给其网络结点，每个结
点占有一个属于自己的方块并负责该方块中所有的“点
”（数据对象索引）
宽带媒体服务技术之对等网络
每个结点维护一个路由表，记录多维空间上的
邻居信息，如图中结点D可以记录B、C、E的
ID和地址
CAN采用逐步定位，每一步挑选当前结点路由
表中离目的结点最“近”的邻居作为下一跳
对一个d维CAN来说，若维护一个有2d项的路
由表，其定位效率为 ，取d=logN，即
为O(logN)，其定位效率与其它结构化P2P网
络一致
宽带媒体服务技术之对等网络
以2维CAN为例，新结点加入时，被映射到一个点，
其所在的方块将一分为二，一半分给新结点负责，一
半留给原来负责的结点；当旧结点离开CAN时，某个
邻居必须接管它原来负责的区域，相当于方块合并
CAN的容错性体现在路由选择的灵活性上，由于其多
维空间的拓扑结构，CAN不需要维护一些严格的不变
属性，每个邻居对结点来说都是同等地位的；在CAN
中任意两个点间存在多条路径，即使很多邻居失效，
仍能以较快的速度定位目的结点
目前还没有基于CAN的应用系统
宽带媒体服务技术之对等网络
一、CAN网络构建
结点加入步骤：自举、寻找区域、加入路由表
JOIN STEP1：自举（bootstrap）
新结点通过CAN的DNS域名获得一个众所周知结点
（自举结点、入口结点），后者提供一个列表，其
中包含一些CAN现存结点的信息
JOIN STEP2：寻找区域
新结点n随机选择CAN空间中的一个点P并向P发送
一个加入请求消息，该消息可通过列表中任意一个
现存结点发送到CAN网络中，并被逐步路由到P所
在的区域，最终到达负责P所在区域的结点n’，n’按
某种规则将负责区域分一半给n负责
宽带媒体服务技术之对等网络
JOIN STEP3：加入路由表
获得自己的区域后，n从n’获得其邻居的IP地址等信
息，并通知每个邻居更新其路由表以反映n的存在
CAN也采用了自适应的周期性方法，每个结点定期
向邻居发送自己所负责的区域和自己的路由表信息，
当发现不一致时更新
由于结点插入、离开或周期性更新时只需要通知邻
居结点，而每个结点的路由表记录O(d)个邻居，因
此其自适应开销是O(d)的，通常比Chord和大多数
P2P系统小得多
宽带媒体服务技术之对等网络
简单的CAN结点加入示例
宽带媒体服务技术之对等网络
当结点离开CAN时，通常应显式地将其区域及所负责
数据交给一个邻居，如果该邻居可以合并一个规整的
单区域，则完成合并，否则，离开结点只能将其区域
交给占有最小区域的邻居，由其暂时负责两块区域，
但并不合并
当结点n失效时，依靠周期性检测由邻居结点接管其
区域，解决冲突的方法：每个邻居做完接管工作以后，
向n的其它邻居发送TAKEOVER消息，其中包括消息
源的区域信息，收到该消息的结点比较消息源的区域
和自己的区域，如果前者大，则回发TAKEOVER消
息表明自己接管更合适，否则取消接管工作
宽带媒体服务技术之对等网络
问题：随着结点不断加入、离开，CAN网络的
区域划分将变得支离破碎，而且由一个结点负
责多个结点的情况将越来越多，直到负载超过
结点能力上限
CAN采用“背景区域重分配”（background
zone reassignment）方法合并支离破碎的区
域，并尽量让一个结点只负责一块区域，详见
论文[Ratnasamy et al.,2001]
宽带媒体服务技术之对等网络
二、CAN增强机制：多维、多空间、
多散列
多维：d接近logN，路由效率高，容错性强
多空间：使用多个不同的CAN空间，每个空间
称为一个“现实”（reality）；一个真实的网络
结点在每个CAN空间中都会被分配一块区域，
同一个数据对象的在每个空间中都会被分配给
一个结点，从而起到复制作用，提高数据可用
性；定位时，结点可以比较多个空间的邻居，
效率更高
多散列：单空间可以使用多散列，效果类似多
空间
宽带媒体服务技术之对等网络
三、CAN的“区域超载”
区域超载：将一个区域分给多个结点负责
一个结点除了维护原来的路由表，还需要维护
一个“区域超载列表”，保存和自己共同负责同
一区域的结点信息
新结点A加入时，如果它所映射到的点原先由
结点B负责，B首先检查该区域的结点数是否
超过上限，如未超过则不分割区域，而是将该
区域也给A负责，同时A从B那里获得“区域超
载列表”；若超过上限，则进行分割
宽带媒体服务技术之对等网络
区域超载的好处
减少定位跳数：让多个结点负责同一区域等效于减
少系统结点数
减少每跳时延：在选择下一跳时，由于邻居区域由
多个结点负责，可以从这多个结点中选出时延最短
的作为下一跳
提高容错性和可用性：一个区域只有在负责它的所
有结点都失效时才不可达，且该区域的数据相当于
被复制到多个结点中
宽带媒体服务技术之对等网络
CAN中的复制与缓存
三种隐式复制：多空间、多散列、区域超载
对热点数据，CAN采用显式复制到邻居区域
在定位路径上放置热点数据的缓存副本
宽带媒体服务技术之对等网络
四、CAN总结
CAN采用多维空间拓扑结构，简单、直观，CAN空间
被动态分配给其网络结点，每个结点负责一块，每个
数据对象被映射到一个点，由负责该点所在区域的结
点保持索引
每个CAN结点维护一个路由表，记录它在多维空间上
的邻居信息，d维CAN的定位效率为
CAN的高容错性体现在其路由选择的灵活性上：即任
意两个结点间存在多条路径，部分邻居信息的失效对
定位效率影响很小
新结点加入CAN分三步：自举、寻找区域、加入路由
表，从其加入区域中划分一半进行接管，采用“背景区
域重分配”方法调整区域
宽带媒体服务技术之对等网络
CAN采用多种增强机制提高系统性能，包括多
维度、多空间、多散列、区域超载技术
综上所述，CAN简单、容错性好，可扩展，高
效率
宽带媒体服务技术之对等网络
Tapestry与OceanStore：广域的超
立方体结构P2P网络
严格讲，是基于Plaxton Mesh[1997]的网格形
结构，Pastry也基于此
特点：构建覆盖网时考虑了拓扑一致性问题
00年3月UC Berkeley的Ben Y. Zhao等成立
Tapestry研究组，03年6月发布版
应用广泛，著名的OceanStore广域存储系统
宽带媒体服务技术之对等网络
Tapestry的应用
Bayeux 提供高效、容错的应用层多播
Brocade 提供界标路由（Landmark Routing）
Cashmere 提供匿名路由
Fault-Tolerant
Overlay Routing
基于Tapestry开发路由的冗余性，从而
提供容错的覆盖网路由
OceanStore 提供全球范围内广域的、持久性数据存
取服务
SpamWatch 基于Tapestry，使用基于内容相似度的
搜索引擎，提供分布式的Spam-Filtering
Warp 通过类型重定向提供快速移动服务架构
宽带媒体服务技术之对等网络
一、Tapestry路由和定位
每个结点有nodeID，数据对象有objectID，也
称为GUID（globally unique ID），每条消息
有其特定应用的AID（application ID），类似
于TCP协议中的端口号
Tapestry为每个数据对象分配一个负责结点，
称为该对象的根（root），root(objectID)=最
接近objectID的nodeID
Tapestry中也采用了多散列以提高对象可用性
与持久性
宽带媒体服务技术之对等网络
Tapestry采用逐位匹配的后缀路由，每一跳匹
配更多的后缀，如xxx8->xx98->x598->4598
为适应这种路由，每个Tapestry结点维护一个
层次化的路由表（邻居表），每一层代表与自
身nodeID匹配一定位数后缀的结点
路由的第n跳所到达的结点通常与目的结点ID
至少匹配n位后缀，为找到下一跳结点，需要
在当前结点的路由表的第n+1层中，查找与目
的结点ID匹配更多位后缀的结点，若找不到，
则意味着定位即将完成
宽带媒体服务技术之对等网络
结点0642的状态信息，包括其对象索引、热点数
据管理器、对象存储空间、路由表
宽带媒体服务技术之对等网络
Tapestry路由示例，结点0325要发送一条消息给
结点4598，粗线标明了路由的每一跳
宽带媒体服务技术之对等网络
Tapestry的路由表项有logBN层，每层B项
Tapestry的路由机制可以保证在N个结点的网
络中，任何一次定位一般都能在logBN跳之内
完成，其中B为ID编码的进制（ base，也称“
基”）
宽带媒体服务技术之对等网络
Tapestry结点S向网络插入数据对象O时，要
将其索引放到O的根结点上，为此，S向邻居
发送一条以objectID为目的地的消息，其中包
含有对象索引信息如<objectID(O)，
serverID(s)>，该消息逐步匹配对象ID直到没
有更多匹配位，此时即找到根结点，消息路径
上的所有结点都保存O的索引信息
宽带媒体服务技术之对等网络
Tapestry结点查询数据对象O时，也发送一条
以objectID为目的地的定位消息，按后缀匹配
方法逐步路由，若中间结点保存了索引，则定
位结束，否则必将到达O的根结点（根结点可
确保对象定位成功，也称为对象的“代理”结点）
由于一个Tapestry结点可能保存O的多个副本
的索引，查询时可从中找出自己认为最近、最
合适的来获取数据，即Tapestry可以自动帮助
用户获取最邻近副本
宽带媒体服务技术之对等网络
二、Tapestry动态结点算法
利用反向指针和心跳消息保持路由表的更新和
定位的容错性
反向指针：back pointer，指向那些把自己作为路
由表项的结点（反向结点）
周期性发送Heartbeat消息至反向结点，确认存在
结点发现路由表某项失败后并不立即替换它，
而是过一段时间再检测一次它是否在线，如果
还不在才替换，称为“二次机会”，防止“闪断”
路由表中每项保存一个“主项”和两个“次要项”
，以提高可用性
宽带媒体服务技术之对等网络
新结点加入：初始化自己的路由表、更新相关
结点的路由表、从相关结点移交对象索引
JOIN STEP1：初始化路由表
新结点N联系到一个现存结点G，通过G发送以N为
目的地的消息
假设第i步路由到达结点Hi，根据后缀匹配路由算法，
N和Hi应该共享长度i的后缀，则N从Hi那里获得路
由表的第i+1层项是合适的
N对复制来的项进行优化，将更好的次要项结点改
为主项，再查找新主项结点的路由表，比较N到每
项的距离，迭代优化至收敛
宽带媒体服务技术之对等网络
JOIN STEP2：更新其它结点路由表
N通过G发送往N自己的消息，在logN跳之内到达N
的根结点R
R首先计算它和N匹配的后缀位数p，然后通过自己
路由表中的“反向指针”，告诉那些与R也匹配p位后
缀的反向结点：如果N对它们是合适的，那么它们
在自己的路由表中添加N或者用N替换原来的项
宽带媒体服务技术之对等网络
JOIN STEP3：对象索引移交
最初的设计：当N发送给自己的消息到达根结点R
时，认为R正是需要移交对象索引给N的结点
由于Tapestry没有严格的结构和必须维持的不变属
性，仅让根结点R移交索引给N是不够的
后来的设计：将对象索引移交放在STEP2中完成，
对于R所通知的反向结点，不仅用N更新自己的路
由表，还将自己的对象索引中应由N负责的那部分
移交给N（维护拓扑结构）
宽带媒体服务技术之对等网络
结点N的离开
正常离开：N告诉自己的反向结点在路由表中去掉
N，同时将自己负责的对象索引分别移交给它们的
新根结点
异常离开：周期性检测并确认N失效后，通过与结
点加入过程中类似的多播方法更新路由表；对于对
象索引，采用“软状态重发布”的方法：所谓“软状态”
指对象索引都是暂时性的，“重发布”指让数据对象
的拥有者定期重新发布自己的对象索引信息，即为
数据对象更新根结点
宽带媒体服务技术之对等网络
三、Tapestry体系架构
宽带媒体服务技术之对等网络
Transport Protocols：封装了网络传输层，相当于覆
盖网与物理网的中间层，典型地可以使用TCP或者
UDP协议
Neighbor Link Management：邻居链接管理向上层提
供安全但不可靠的数据报服务，如长消息的分片和组
合；负责持续的邻居链接管理和更新，如周期性的邻
居结点失效检测、时延估计等，当检测到状态变化时
通知上层来处理
Router：管理Tapestry结点路由表和对象指针数据库，
检查所收到的消息的目的地，决定路由的下一跳；在
新结点加入、旧结点离开时更新对象索引信息
宽带媒体服务技术之对等网络
Application Interface/Upcall API：Tapestry提供给其
高层应用的接口
分布式文件系统/应用层多播/协同文本过滤：基于
Tapestry的各种上层应用，不限于这三种
宽带媒体服务技术之对等网络
四、Tapestry总结
是一个面向广域分布式数据存取、容错的超立方体结
构P2P模型，在构建网络时考虑了拓扑一致性；其最
具特色的功能在于帮助用户寻找最邻近的数据副本
Tapestry中每个结点、数据对象、消息（应用）都有
一个全局唯一的ID，每个数据对象有一个根结点，它
是网络中nodeID与objectID最匹配的结点
每个Tapestry结点维护一个路由表，其中第i层第j项表
示与当前nodeID后缀匹配位数为i-1位并且以j开头的
结点，由此实现效率为O(logN)跳的后缀匹配路由
宽带媒体服务技术之对等网络
Tapestry路由表还维护“反向指针”项，很多重
要操作如结点加入、离开、失效检测和修复都
用到它
Tapestry体系架构分为5层，分层有助于高层
应用的开发和各层的优化完善
宽带媒体服务技术之对等网络
五、OceanStore简介
基于Tapestry的分布式数据存取系统，其目标是提供
全球范围的广域、持久性数据存取服务
任何一台计算机都可以加入到OceanStore系统，贡献
自己的存储空间，同时获得他人存储的内容
OceanStore对数据提供传统的复制、缓存功能，以提
高存取速度和可用性
OceanStore建立在一个广域、动态、不可靠的网络基
础上，因此对所有数据、元数据都提供了加密或者认
证的功能
OceanStore采用“拜占庭式容错提交协议”保持副本间
的强一致性
宽带媒体服务技术之对等网络
OceanStore的数据持久性是通过基于版本的深度归档
存储方案来实现的，并以“冗余编码”的方式分片存储
每个数据对象的每个版本，部分分片即可重构原文件
OceanStore通过“内省”机制提高存取性能和容错性
OceanStore的构想[Kubiatowicz et al., 2000]早于
Tapestry，03年实现原型Pond[Rhea et al, 2003]，
04年6月在SourceForge上发布源码
宽带媒体服务技术之对等网络
六、OceanStore的命名机制和存取控
制
OceanStore中数据对象是最基本的单元，类似于文件
系统中的文件
数据对象以只读文件版本的方式按序保存在系统中，
原则上每个对象的每个版本都是永久保存的，但通常
只有最新版才有意义
每个对象的每个版本包含着该版本数据和元数据（如
目录）以及指向其前一个版本的指针，每个版本有自
己的标识VGUIDi，对象的所有版本通过“反向指针”
（与Tapestry中的不同）连成一个流，这串序列合起
来有一个表示AGUID（Active GUID），唯一标识一
个有效的数据对象
宽带媒体服务技术之对等网络
宽带媒体服务技术之对等网络
每个数据对象版本由许多块组成，每块有自己的标识
BGUID（Block GUID），这些块自顶向下组织成一
棵类似B树的结构
树根为root block，保存该版本的元数据M和向下的指针，根
块的BGUID通常被作为该版本的VGUID
中间块为indirect blocks，只保存向下的指针
树底层的叶子叫做data blocks，保存真正的数据
作为索引的根块和数据块里的指针，实际上是其子块
的BGUID，版本间可以通过BGUID共享数据（图中
copy on write）
宽带媒体服务技术之对等网络
OceanStore有效对象AGUID的结构：由对象拥有者的公
钥和可读对象名拼接起来的安全散列值
可避免对象名冲突，且起到完整性检查的作用
宽带媒体服务技术之对等网络
OceanStore的BGUID生成过程：由分片产生散
列值，再逐层向上合并生成散列值
每个分片除了存储分片数据，还需要存储它从底层到
顶层所需的兄弟散列值（约logN个，N为分片数），
以用于验证分片的数据完整性
宽带媒体服务技术之对等网络
从对象的AGUID安全映射到其最新版本的
VGUID的机制，两种方法：
每个数据对象在系统中对应一个“主环”（primary
ring），由多台服务器组成，使用“拜占庭一致性协
议”来维护映射，并将用户发出的对象更新操作序列
化执行
若某个对象没有主环，则映射被存储在称为墓碑的
结构里（图中）
宽带媒体服务技术之对等网络
OceanStore墓碑结构
Active
对象主环的公钥和私钥密文
对象最新的VGUID
负责方（responsible party）的公钥和私钥密文
宽带媒体服务技术之对等网络
OceanStore对系统中数据对象提供两种原始类型的“
存取控制”：读者限制和写者限制
读者限制：为阻止不合法的读者，OceanStore中所有
非完全公开的数据都被加密，密钥分发给那些允许读
的用户。如果要撤销原来发出的读允许，对象拥有者
要么删除数据对象，要么用新密钥加密原对象
写者限制：要求所有的写操作都必须签名，行为良好
的服务器和客户可以通过存取控制链（ACL,access
control list）来验证写操作。对象的存取控制链是由
对象拥有者所签名的、授予特定用户对该对象的操作
特权
宽带媒体服务技术之对等网络
七、OceanStore的路由和定位算法
全局查询
Tapestry的后缀匹配路由算法，速度较慢，但保证
成功
概率查询
快速定位局部性的临近数据对象，速度快，但不保
证成功
为网络中每条有向边保存一个Attenuated Bloom
Filters数据结构，以表示沿该边可以定位到的对象
信息，查询消息在Bloom filter的指导下沿着有向边
路由
宽带媒体服务技术之对等网络
Bloom Filter是一种空间效率很高的随机数据结构，它
利用位数组很简洁地表示一个集合，并能判断一个元
素是否属于这个集合。Bloom Filter的这种高效是有一
定代价的：在判断一个元素是否属于某个集合时，有
可能会把不属于这个集合的元素误认为属于这个集合
（false positive）。因此，Bloom Filter不适合那些“
零错误”的应用场合。而在能容忍低错误率的应用场合
下，Bloom Filter通过极少的错误换取了存储空间的极
大节省。
请自学Bloom Filter的工作原理
宽带媒体服务技术之对等网络
概率查询示例：n1查找对象X
Bloom Filter
n1的有向边Filter显示n2可能
是一个路由到X的中间结点
宽带媒体服务技术之对等网络
八、OceanStore的更新模型
任何一个数据对象都有一个“主副本环”（primary
replica，也称主环或者内环），是数据对象归档存储、
更新、最新版本获得的核心设施
用户更新对象时，首先发出更新请求，通过Tapestry
底层网络将请求发到对象主环，主环服务器之间序列
化所收到的更新请求并执行；然后，主环服务器将新
数据对象深度归档存储（提供数据持久性），并通过
“分发树”（dissemination tree）将更新分发到对象的“
次级副本”服务器以更新缓存（加快数据定位与获取速
度）
宽带媒体服务技术之对等网络
宽带媒体服务技术之对等网络
九、OceanStore的深度归档存储
使用“冗余编码”（erasure code）将数据对象
分片冗余地存储在网络的多个结点中，只要获
得一部分分片就可以重构原文件
冗余编码：一种提高数据可用性的数学编码方
法。假设编码前数据被分成互相独立的n片，
冗余编码将这n片转换成更多相关的分片，如
kn片，1/k称为冗余编码率，这些冗余、相关
的分片散布到网络中后，任何时刻只要用户能
取得其中任意n片，即可重构原对象
宽带媒体服务技术之对等网络
假设系统中共有n个结点，某个时刻有m个结点失效，
f是对象的分片数，rf是最大容许的不可用分片数（指
丢失掉的分片数不足以导致对象不能重构），则对象
可用的概率为
假定n取100万，m取10万，即10%的结点失效，简单
复制方法提供的对象可用性是99%；而采用1/2的冗
余编码，在消耗相同存储容量的前提下，对象可用性
将达到%
宽带媒体服务技术之对等网络
十、OceanStore的内省优化
优化目标
基于网络动态性，保持结点状态的自适应更新
基于网络异构性，利用复制、集群等方法开发结点
能力
内省优化包括三个循环的操作
观察：observation，监控系统活动并记录活动信息
优化：optimization，利用观察的信息调整计算
计算：computation，完成通信、数据交换、本地
计算等实际的系统工作
数据对象的集群识别与流动副本管理
宽带媒体服务技术之对等网络
OceanStore总结
OceanStore是一个基于Tapestry的分布式数据存取系
统，其目标是提供全球范围的广域、持久性数据存取
服务
数据对象以只读文件版本的方式保存，使用AGUID标
识可用对象，VGUID标识对象的各个版本，BGUID标
识数据块，这些ID之间以类似B树的方式组织
OceanStore采用两种路由和定位算法：概率查询，局
部，快速，但不保证成功；全局查询，后缀路由匹配，
速度慢，保证成功
任何一个数据对象都对应一个主副本环，是数据对象
归档存储、更新、最新版本获得的核心设施
宽带媒体服务技术之对等网络
用户更新对象时，数据一方面被深度归档存储，一方
面被分发到对象的次级副本服务器以更新缓存
OceanStore建立在广域、动态、不可靠的网络基础上，
系统中每个结点都不可靠，因此对所有数据提供加密
或认证
使用拜占庭式容错提交协议保持副本间的强一致性
深度归档存储方案中，数据以冗余编码的方式分片冗
余地存储在网络的多个服务器中，仅利用部分分片即
可重构原文件，数据是高可用、高持久性的
通过内省机制提高存取性能和自适应性
