P2P网络体系(2)

大纲 第一代P2P网络：混合式P2P体系 第二代P2P网络：无结构P2P体系 第三代P2P网络：结构化P2P体系（＊）

第三代P2P网络：结构化P2P体系 Chord&CFS CAN Tapestry&OceanStore Pastry&Past Kademlia SkipNet Viceroy Koorde Cycloid

概述 2001年，学术界P2P历史上的里程碑 IEEE成立P2P专业会议、ACM会议专题等 提出结构化P2P的几个经典模型与应用体系，如Chord、CAN、Tapestry、Pastry 著名学术团体与技术组织成立专门的P2P研究组，如MIT、UC Berkeley、Microsoft、Stanford

Chord&CFS

Chord与CFS：简单、精确的环形P2P网络 MIT与Berkeley的研究者01年正式发表http://pdos.csail.mit.edu/chord/

Chord作为一个P2P网络，是基于带弦环拓扑结构的分布式系统，提供对象的存储、查询、复制、缓存，在其上可以架构更高层的分布式数据存储系统如协同文件系统CFS

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）的第一个结点，记做n.successor

一个简单的Chord环（m=3） Successor,predecessor构成双向链

理解Chord设计

Chord结点n的路由表各项属性及其定义 finger[k].start (n+2k-1)mod2m, 1≤k≤m .interval [finger[k].start, finger[k+1].start) .node ≥n.finger[k].start的第一个结点 successor 后继结点，即finger[1].node predecessor 前驱结点

节点的加入与退出机制 当Chord中有新结点n加入时，为保持正确、一致的对象放置，原本由n的后继结点负责的对象，其中一部分必须分配给n

单纯的环可以工作，但效率太低 为此，结点维护一个有m（ID位数）项的路由表，也称“指向表”（finger table），其中第i项指向结点s，s=successor(n+2i-1)，1≤i≤m，即s是在顺时针方向到n的距离至少为2i-1的第一个结点，记做n.finger[i].node Chord路由表的特点： 每个结点只保存很少的其它结点信息，并且对离它越远的结点所知越少 Chord结点不能从自己的路由表中看出对象k的后继

为确定对象k的后继（k所在的结点）,结点n在自己的路由表中查找在k之前且离k最近的结点j，让j去找离k最近的结点，递归查找，最终可以找到对象k的前驱（在k之前离k最近的结点，记做predecessor(k)，类似，结点n的前驱记做n.predecessor） 前驱中必然有后继的路由表项，定位成功

Chord对象定位算法 定位算法的三个函数的伪代码 //请求结点n寻找id的后继 n.find_successor(id) n’=find_predecessor(id); return n’.successor; //请求结点n寻找id的前驱 n.find_predecessor(id) n’=n; while(id (n’,n’.sucessor]) n’=n’,closest_preceding_finger(id); return n’;

//返回id之前最近的finger n.closest_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.finger[3].interval即[7,3) 结点3让3.finger[3].node即结点0去找1 结点0在路由表中发现自己的后继1恰好是对象1的后继，因此将1返回给结点3 结点3由此知道对象1放在结点1中

Query Upon receiving a query for item id, a node Check whether stores the item locally If not, forwards the query to the largest node in its successor table that does not exceed id Succ. Table Items i id+2i succ 0 1 1 1 2 2 2 4 0 7 Succ. Table Items 1 7 i id+2i succ 0 2 2 1 3 6 2 5 6 1 query(7) Succ. Table 6 2 i id+2i succ 0 7 0 1 0 0 2 2 2 Succ. Table i id+2i succ 0 3 6 1 4 6 2 6 6 5 3 4

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万个数据对象 (结点所负担的对象数目集中在50左右　PDF：probability density function）

定位路径长度 理论量级为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对数据块采用后继复制以提高数据可用性，同时减少了客户获取数据的时延；采用路径缓存提高系统工作效率，同时避免热点数据的后继结点负载过重；采用“虚拟结点”和“限额”方法提供负载均衡

CFS系统架构

CFS文件结构图 文件根块（root-block）由发布者的公钥来标识， 并被相应的私钥签名。其它块被它们内容的安全散列值标识（图片来自[Dabek et al.01]）。

CAN：简单、容错的多维空间P2P网络 Content Addressable Network，内容可寻址网络，采用多维Torus环面拓扑结构，典型采用的二维空间网格，类似于笛卡尔平面，其结点编址方式也类似于点的编址 01年[Ratnasamy et al.]在ACM SIGCOMM会议发表正式论文（与Chord同年同会）

CAN

CAN的多维空间被动态地分配给其网络结点，每个结点占有一个属于自己的方块并负责该方块中所有的“点”（数据对象索引）

每个结点维护一个路由表，记录多维空间上的邻居信息，如图中结点D可以记录B、C、E的ID和地址 CAN采用逐步定位，每一步挑选当前结点路由表中离目的结点最“近”的邻居作为下一跳 对一个d维CAN来说，若维护一个有2d项的路由表，其定位效率为 ，取d=logN，即为O(logN)，其定位效率与其它结构化P2P网络一致

CAN例子：两维空间的CAN 节点覆盖了整个空间，并且空间在节点间被分割 每个节点要么占据一个正方形或者矩形区域（1:2或2:1） 空间分割示例： Node n1:(1, 2) first node that joins  cover the entire space 7 6 5 4 3 n1 2 1 1 2 3 4 5 6 7

CAN例子：两维空间的CAN Node n2:(4, 2) joins  space is divided between n1 and n2 7 6 5 4 3 n1 n2 2 1 1 2 3 4 5 6 7

CAN例子：两维空间的CAN Node n2:(4, 2) joins  space is divided between n1 and n2 7 6 n3 5 4 3 n1 n2 2 1 1 2 3 4 5 6 7

CAN例子：两维空间的CAN Nodes n4:(5, 5) and n5:(6,6) join 7 6 n5 n4 n3 5 4 3 n1 2 1 1 2 3 4 5 6 7

CAN例子：两维空间的CAN Nodes: n1:(1, 2); n2:(4,2); n3:(3, 5); n4:(5,5);n5:(6,6) Items: f1:(2,3); f2:(5,1); f3:(2,1); f4:(7,5); 7 6 n5 n4 n3 5 f4 4 f1 3 n1 n2 2 f3 1 f2 1 2 3 4 5 6 7

CAN例子：两维空间的CAN 每个item(或者key)存储在那个包容它的空间的节点上。 7 6 n5 n4 n3 5 f4 4 f1 3 2 f3 1 f2 1 2 3 4 5 6 7

CAN: 查询例子 每个节点知道它的邻居（d维空间） 查询被传递给在ID空间距离它（指key)最近的邻居 Example: assume n1 queries f4 存在多路径，能够容忍一些失败 7 6 n5 n4 n3 5 f4 4 f1 3 n1 n2 2 f3 1 f2 1 2 3 4 5 6 7

CAN: 节点加入过程 I new node 1) Discover some node “I” already in CAN（BootStrap)

CAN: 节点加入过程 (x,y) I new node 2) Pick random point in space

CAN: 节点加入过程 (x,y) J I new node 3) I routes to (x,y), discovers node J

CAN: 节点加入过程 new J 4) split J’s zone in half… new node owns one half

几个问题 节点离开或者故障 动态维护 邻居节点接管 一定能够接管吗？接管协议？区域碎片的处理？ 自适应的周期性方法，每个结点定期向邻居发送自己所负责的区域和自己的路由表信息，当发现不一致时更新

当结点离开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采用多种增强机制提高系统性能，包括多维度、多空间、多散列、区域超载技术

Tapestry&OceanStore

Tapestry与OceanStore：广域的超立方体结构P2P网络 严格讲，是基于Plaxton Mesh[1997]的网格形结构，Pastry也基于此 特点：构建覆盖网时考虑了拓扑一致性问题 00年3月UC Berkeley的Ben Y. Zhao等成立Tapestry研究组，03年6月发布2.0版 应用广泛，著名的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采用逐位匹配的后缀路由，每一跳匹配更多的后缀，如从一个结点定位到结点4598的路由过程：xxx8->xx98->x598->4598 为适应这种路由，每个Tapestry结点维护一个层次化的路由表（邻居表），每一层代表与自身nodeID匹配一定位数后缀的结点 路由的第n跳所到达的结点通常与目的结点ID至少匹配n位后缀，为找到下一跳结点，需要在当前结点的路由表的第n+1层中，查找与目的结点ID匹配更多位后缀的结点，若找不到，则意味着定位即将完成

结点0642的状态信息，包括其对象索引、热点数据管理器、对象存储空间、路由表

Tapestry路由示例，结点0325要发送一条消息给结点4598，粗线标明了路由的每一跳

几个问题 1、路由效率 2、对象的存储和查询 3、结点的加入、离开、故障 Tapestry的路由表项有logBN层，每层B项 保证在N个结点的网络中，任何一次定位一般都能在logBN跳之内完成，其中B为ID编码的进制 2、对象的存储和查询 查询的对象不能够完全匹配到（空间里对象是稀疏的） 需要对象存在根结点（或者称为代理点） 代理点失效 周期性重新发布object 3、结点的加入、离开、故障 后缀匹配 反向指针

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，同时将自己负责的对象索引分别移交给它们的新根结点

三、Tapestry体系架构

Transport Protocols：封装了网络传输层，相当于覆盖网与物理网的中间层，典型地可以使用TCP或者UDP协议 Neighbor Link Management：邻居链接管理向上层提供安全但不可靠的数据报服务，如长消息的分片和组合；负责持续的邻居链接管理和更新，如周期性的邻居结点失效检测、时延估计等，当检测到状态变化时通知上层来处理 Router：管理Tapestry结点路由表和对象指针数据库，检查所收到的消息的目的地，决定路由的下一跳；在新结点加入、旧结点离开时更新对象索引信息

Application Interface/Upcall API：Tapestry提供给其高层应用的接口

四、Tapestry总结 是一个面向广域分布式数据存取、容错的超立方体结构P2P模型，在构建网络时考虑了拓扑一致性；其最具特色的功能在于帮助用户寻找最邻近的数据副本 Tapestry中每个结点、数据对象、消息（应用）都有一个全局唯一的ID，每个数据对象有一个根结点，它是网络中nodeID与objectID最匹配的结点 每个Tapestry结点维护一个路由表，其中第i层第j项表示与当前nodeID后缀匹配位数为i-1位并且以j开头的结点，由此实现效率为O(logN)跳的后缀匹配路由

Tapestry路由表还维护“反向指针”项，很多重要操作如结点加入、离开、失效检测和修复都用到它 08.10.07第八次课

OceanStore简介 基于Tapestry的分布式数据存取系统，其目标是提供全球范围的广域、持久性数据存取服务 OceanStore的构想[Kubiatowicz et al., 2000]早于Tapestry，03年实现原型Pond[Rhea et al, 2003]，04年6月在SourceForge上发布源码http://oceanstore.sourceforge.net

OceanStore设计要点 1、数据永久保持概念（版本跟踪＋高度冗余） 数据对象以只读文件版本的方式保存，使用AGUID标识可用对象，VGUID标识对象的各个版本，BGUID标识数据块，这些ID之间以类似B树的方式组织。 深度归档：数据以冗余编码的方式分片冗余地存储在网络的多个服务器中，仅利用部分分片即可重构原文件，数据是高可用、高持久性的 任何一个数据对象都对应一个主副本环，是数据对象归档存储、更新、最新版本获得的核心设施 2、数据的快速定位 缓存＋深度归档：用户更新对象时，数据一方面被深度归档存储，一方面被分发到对象的次级副本服务器以更新缓存 OceanStore采用两种路由和定位算法：概率查询，局部，快速，但不保证成功；全局查询，后缀路由匹配，速度慢，保证成功 3、安全 多个副本的强一致性（拜占庭式容错提交协议）

OceanStore的理想：跨越全球的分布式持久数据存取

1、OceanStore的命名机制和存取控制 数据对象以只读文件版本的方式按序保存在系统中，原则上每个对象的每个版本都是永久保存的，但通常只有最新版才有意义 每个对象的每个版本包含着该版本数据和元数据（如目录）以及指向其前一个版本的指针，每个版本有自己的标识VGUIDi，对象的所有版本通过“反向指针”（与Tapestry中的不同）连成一个流，这串序列合起来有一个表示AGUID（Active GUID），唯一标识一个有效的数据对象

Active Global Unique Identification

命名机制 每个数据对象版本由许多块组成，每块有自己的标识BGUID（Block GUID），这些块自顶向下组织成一棵类似B树的结构 树根为root block，保存该版本的元数据M和向下的指针，根块的BGUID通常被作为该版本的VGUID 中间块为indirect blocks，只保存向下的指针 树底层的叶子叫做data blocks，保存真正的数据 作为索引的根块和数据块里的指针，实际上是其子块的BGUID，版本间可以通过BGUID共享数据（图中copy on write）

OceanStore有效对象AGUID的结构：由对象拥有者的公钥和可读对象名拼接起来的安全散列值 可避免对象名冲突，且起到完整性检查的作用

OceanStore的BGUID生成过程：由分片产生散列值，再逐层向上合并生成散列值 每个分片除了存储分片数据，还需要存储它从底层到顶层所需的兄弟散列值（约logN个，N为分片数），以用于验证分片的数据完整性 采用erasure code方式将数据块分片冗余存储在多个结点中，只要获得这些分片的一部分就可以重构数据块。｛如hash(frag data1)＋H2+H34+HD=BGUID｝

从对象的AGUID安全映射到其最新版本的VGUID的机制，两种方法： 每个数据对象在系统中对应一个“主环”（primary ring），由多台服务器组成，使用“拜占庭一致性协议”来维护映射，并将用户发出的对象更新操作序列化执行 若某个对象没有主环，则映射被存储在称为墓碑的结构里（图中）

OceanStore墓碑结构 Active 负责方（responsible party）的公钥和私钥密文 对象主环的公钥和私钥密文 对象最新的VGUID

数据安全控制 OceanStore对系统中数据对象提供两种原始类型的“存取控制”：读者限制和写者限制 写者限制：要求所有的写操作都必须签名，行为良好的服务器和客户可以通过存取控制链（ACL,access control list）来验证写操作。对象的存取控制链是由对象拥有者所签名的、授予特定用户对该对象的操作特权

2、OceanStore的路由和定位算法 全局查询 概率查询 Tapestry的后缀匹配路由算法，速度较慢，但保证成功 快速定位局部性的临近数据对象，速度快，但不保证成功 为网络中每条有向边保存一个Attenuated Bloom Filters数据结构，以表示沿该边可以定位到的对象信息，查询消息在Bloom filter的指导下沿着有向边路由

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下。 请自学Bloom Filter的工作原理

概率查询示例：n1查找对象X （注意rounded box &unrounded box) n1的有向边Filter显示n2可能 是一个路由到X的中间结点 将文件的所有objectid进行bloom filter得到本地的rounded box的向量V 查询关键词的objectid进行bloom filter得到在向量V中的置位位置为0,1,3 对邻居需要合并bloom filter，如n1的邻居bloomfilter数组（unrounded box)，[1]=n2的local 11100　[2]=n2的邻居bloomfilter的并集11011 Bloom Filter

3、OceanStore的更新模型 任何一个数据对象都有一个“主副本环”（primary replica，也称主环或者内环），是数据对象归档存储、更新、最新版本获得的核心设施 用户更新对象时，首先发出更新请求，通过Tapestry底层网络将请求发到对象主环，主环服务器之间序列化所收到的更新请求并执行；然后，主环服务器将新数据对象深度归档存储（提供数据持久性），并通过“分发树”（dissemination tree）将更新分发到对象的“次级副本”服务器以更新缓存（加快数据定位与获取速度）

4、OceanStore的深度归档存储 使用“冗余编码”（erasure code）将数据对象分片冗余地存储在网络的多个结点中，只要获得一部分分片就可以重构原文件 冗余编码：一种提高数据可用性的数学编码方法。假设编码前数据被分成互相独立的n片，冗余编码将这n片转换成更多相关的分片，如kn片，1/k称为冗余编码率，这些冗余、相关的分片散布到网络中后，任何时刻只要用户能取得其中任意n片，即可重构原对象

假设系统中共有n个结点，某个时刻有m个结点失效，f是对象的分片数，rf是最大容许的不可用分片数（指丢失掉的分片数不足以导致对象不能重构），则对象可用的概率为

5、OceanStore的内省优化 优化目标 内省优化包括三个循环的操作 数据对象的集群识别与流动副本管理 基于网络动态性，保持结点状态的自适应更新 基于网络异构性，利用复制、集群等方法开发结点能力 内省优化包括三个循环的操作 观察：observation，监控系统活动并记录活动信息 优化：optimization，利用观察的信息调整计算 计算：computation，完成通信、数据交换、本地计算等实际的系统工作 数据对象的集群识别与流动副本管理

OceanStore内省过程（图片来自[Kubiatowicz et al.00]）

OceanStore总结 OceanStore是一个基于Tapestry的分布式数据存取系统，其目标是提供全球范围的广域、持久性数据存取服务 数据对象以只读文件版本的方式保存，使用AGUID标识可用对象，VGUID标识对象的各个版本，BGUID标识数据块，这些ID之间以类似B树的方式组织 OceanStore采用两种路由和定位算法：概率查询，局部，快速，但不保证成功；全局查询，后缀路由匹配，速度慢，保证成功 任何一个数据对象都对应一个主副本环，是数据对象归档存储、更新、最新版本获得的核心设施

用户更新对象时，数据一方面被深度归档存储，一方面被分发到对象的次级副本服务器以更新缓存 OceanStore建立在广域、动态、不可靠的网络基础上，系统中每个结点都不可靠，因此对所有数据提供加密或认证 使用拜占庭式容错提交协议保持副本间的强一致性 深度归档存储方案中，数据以冗余编码的方式分片冗余地存储在网络的多个服务器中，仅利用部分分片即可重构原文件，数据是高可用、高持久性的 通过内省机制提高存取性能和自适应性

Pastry&PAST

Pastry与PAST：容错的混合式结构P2P网络 Pastry结合了环形结构与超立方体结构（实际是Plaxton mesh）的优点，提供高效的查询路由、确定性的对象定位和独立于具体应用的负载均衡 与Tapestry的不同在于Pastry是尽可能找到最近的副本，前者则希望副本能均匀、分散的放置 00年Microsoft Research与Rice Univ.开始设计，01年发表[Rowstron & Druschel,2001]

通用、可扩展的组通信和事件发布系统，提供应用层多播和任播 Pastry的应用 SCRIBE 通用、可扩展的组通信和事件发布系统，提供应用层多播和任播 PAST 广域、安全的P2P归档存储系统 SQUIRREL 分布式的协同Web缓存，使得用户Web浏览器之间能共享缓存 SplitStream 基于Pastry的高带宽内容流化/发布系统 POST 提供通信、协同的消息框架，可用来支持安全E-mail、安全实时消息、分布式协同应用等 Scrivener 强调P2P系统资源公平共享的架构 其他Pastry项目 PASTA：剑桥大学开发的类似PAST的文件系统 Herald：Microsoft开发的出版/订阅事件发布服务 Pastiche：密西根大学开发的P2P备份系统 DPSR：普度大学开发的有拓扑意识的结构化P2P架构与移动Ad Hoc网多跳路由协议之间的协同项目

1、Pastry路由 Pastry结点与数据对象使用128位的ID，对象索引由与对象ID最接近的结点负责 Pastry采用前缀匹配（本质同Tapestry） 每个结点维护一个路由表、一个叶集和一个邻居集；路由表分层，每列从上到下分别代表与当前节点ID前缀匹配对应位数的结点，其行数就是Pastry采用的进制数；与当前结点nodeID在该位恰好相等的项标为阴影，通常是空指针（节省存储空间） 图中每项结点ID以X-Y-Z形式表示，其中X标识匹配的前缀，Y表示第一个不匹配位，Z则是结点ID的后几位

Pastry 结点状态

叶集L中包含|L|个与当前结点ID最邻近的“叶结点”，其中|L|/2个比当前ID小，|L|/2个大；叶集的作用在于保证Pastry路由的正确性，类似Chord中的后继列表 邻居集M中包含|M|个在网络物理层与当前结点临近的结点，其作用在于增强Pastry工作的局部性，路由过程中通常不使用M Pastry结点状态=L+R+M，表中结点项数=|L|+ B*logBN+|M|，B为进制，N为网络结点总数

基于上述路由表，Pastry采用前缀逐位匹配路由，通常每一步至少比前一步多匹配一位前缀，直到无法匹配更多位数，此时的下一跳结点为ID与目的地最邻近的结点，更具体的说，是当前结点的叶集L中与目的ID最接近的结点（与Tapestry不同，　不需要代理点） 显然，Pastry定位跳数为O(logBN)，由于叶集L的存在，其路由比Tapestry更快，更容错 为提高安全性，防止恶意结点的破坏，Pastry采用“随机路由”来减少路由的确定性，如，当多个结点都符合下一跳的条件时，不一定选择最优的，而是随机选择一个，以牺牲性能来换取安全

Pastry核心路由算法 Li指叶集L中离当前结点ID第i近的结点 路由表R中第l行第Dl项 T，D匹配的前缀长度 判断D是否在叶集L内 路由表项空缺或不可达 T，D匹配的前缀长度

2、Pastry自组织和自适应 Pastry结点加入网络的三项工作 JOIN STEP1：初始化路由表、叶集和邻居集 初始化路由表、叶集和邻居集，通知其他结点自己的到来，从现存结点获取需要负责的数据 JOIN STEP1：初始化路由表、叶集和邻居集 新结点X通过众所周知结点或者“扩展环”IP多播联系到一个现存结点A，通常在物理上离X很近 X通过A发送一条以X为目的地的消息，按前缀匹配路由算法，最终到达nodeID离X最近的结点Z 加入消息所走过路径上的每个结点将它们的路由表信息发给X，X接收并优化（类似Tapestry） X直接从Z获得叶集并作修正，直接从A获得邻居集

JOIN STEP2：通知其它结点自己的到来 比Tapestry简单，只需要把X的结点状态信息发给自己的路由表、叶集、邻居集中的结点 收到更新消息的结点自己去选择用X替换表项 JOIN STEP3：新结点获取需要负责的数据 经典论文中未专门讲述，但类似于Tapestry，且更简单，只需要从叶集结点获取数据 结点的正常离开处理很简单，只需要通知自己所知的结点

结点失效的处理（周期性检测） FAIL STEP1：修正叶集 某结点发现其叶集中某个结点失效，则向叶集中离失效结点最远的结点获取叶集，从中寻找最合适的结点来修正失效的叶集项 由于叶集对Pastry正确工作有基础性的作用，因此对其修正是严格、频繁和高要求的

FAIL STEP2：修正路由表 FAIL STEP3：修正邻居集 路由表的修正要求比叶集低很多：路由表的错误只会导致效率下降；路由表项数很多，不宜频繁更新 当结点发现路由表中第l行第d项失效，会发消息给第l行未失效的任一结点，获取其路由表的第l行第d项作为替代；如果路由表第l行所有项均失效，则联系第l+1行中的结点，迭代至替换成功 FAIL STEP3：修正邻居集 通常不使用，其修正更为松散，长周期，从未失效邻居集结点获取邻居集并替换

三、Pastry的局部性 分两步实现局部性 部分体现在路由表的构造上，但其中的局部性并不准确，Pastry的局部性实际来源于邻居集M 路由表初始化以后，新结点通过邻居集M来修正路由表项，用物理网上离自己确实很近的结点来替换原有项 Pastry采用传统的ID邻近复制，同一数据对象被复制到与其ID相近的k个结点上，也提供了一定的数据存取局部性：因为ID相近的结点通常分散在整个网络中，总会有一两个离查询者很近

四、Pastry实验分析 Pastry平均路由跳数与网络结点数间关系，B=16，|L|=16，|M|=32

Pastry路由路径长度（跳数）的相对距离与网络结点数的关系，黑线是理想的最优路由

Pastry平均路由跳数与结点失效的关系， B=16，|L|=16，|M|=32，5000个结点，20万次查询

Pastry总结 Pastry是一个容错、高效、可扩展的混合式结构P2P网络，结合了环形结构与超立方体结构的优点，在物理网上构造了一个分布式、自组织、容错的覆盖网，提供高效的路由、确定性的对象定位和独立于具体应用的负载平衡，还提供了复制、缓存、错误复原等增强机制 Pastry的定位、路由类似Tapestry，但采用前缀匹配路由，由于使用叶集，更快速 Pastry结点的加入、失效算法由于叶集和邻居集的存在，比Tapestry能更简单、更快地达到自适应效果 Pastry构建网络时考虑了局部性因素，来源于邻居集 08.10.09第九次课

PAST简介 以Pastry为底层架构的归档存储系统 Rowstron & Druschel，2001，两篇论文 负载均衡与结点能力差异：均匀未必是最好的

1、PAST操作 插入：fileID=Insert(name, owner-credentials, k, file) 插入名为name的文件file，并保存k个副本，用户证书owner-credentials通常是用户的公钥，fileID一般是以上四个参数的安全散列值（有时加入salt） 用户有存储限额（storage quota） 插入文件有私钥签名的文件证书，包括fileID，文件内容散列值、副本数目、盐值、创建时间等 文件证书与文件一起路由到ID最近的结点，该结点验证文件拥有者与文件完整性后，存储副本并将插入请求路由到其它负责存储文件的结点 插入成功后，回发确认消息，每个存储结点都加入自己的存储收据（storage receipt） 有时需要加入salt－－当因节点存储受限需要重新插入时，见副本转移和文件转移 K个副本是nodeid邻近

查询：file=lookup(fileID) 同时获得文件与文件证书 多副本均匀分布使查询高效 PAST查询只能基于fileID，不支持关键码查询，系统中的文件也没有目录结构 回收：Reclaim(fileID, owner-credentials) 为删除文件，回收者提供“回收证书”，存储文件的结点认证后，回发“回收收据”，回收者恢复“存储限额”，但并不真正删除文件

2、PAST安全机制 每个PAST用户有一个smartcard（智能卡，PAST 安全机制的核心部件），带有一对密钥，其中的公钥带有smartcard issuer（发行者，权威的可信机构）的数字签名 Smartcard的作用 产生和验证各种各样的证书 维护结点的存储限额 安全性的前提 系统中大多数的用户可信 攻击者不能控制smartcard

智能卡保证nodeID和fileID的完整性，从而防止攻击者控制nodeID邻近的多个结点以完全控制某个文件所有副本的可能 存储收据防止攻击者欺骗文件插入者已存储k个副本，但实际上副本数远远不足k的可能 文件证书使得存储文件的结点和获取文件的结点都能验证文件插入者的真实性和文件内容的完整性 文件证书和回收证书配合实现存储限额机制

PAST用户也可以将文件加密后再插入系统 底层架构Pastry提供的安全性： 随机路由，降低路由确定性 对每个路由表项，或叶集、邻居集中的结点，Pastry可以要求相应结点签名后做验证、验证通过才加入表中的方法，防止恶意结点伪造表项的可能

3、PAST存储管理 目的 方法 在系统存储利用率逐步达到100%的过程中，不断平衡网络结点剩余的空闲存储空间 维护PAST的复制不变属性——每个数据对象的k个副本被存放在nodeID相近的k个结点上 方法 转移(diversion)：副本(replica)转移；文件转移 基于节点异构性，通过比较的方法控制“每结点存储容量”的分布。当新结点N加入时，PAST将N公布的存储能力与其叶集结点平均存储能力比较，高则以多个nodeID的形式加入，过低则可能被拒绝

PAST的存储管理对文件不分片 不足之处：大文件常常需要通过“副本转移”或者“文件转移”的方法存放；过大的文件经常因为放不下而被系统拒绝 好处：实现简单；避免分片带来的开销和维护的复杂度

副本转移 PAST通常让nodeID与fileID最近的k个结点保存文件的k个副本，当其中某个结点A带宽、空间严重不足而文件f又很大时，“副本转移”允许结点A叶集中的结点B来代替地保存副本，A只保存到B的指针 A将f的副本转移到B之后，必须确保 （1）B的失效将自动导致一个新副本的创建（Pastry的机制保证） （2）A的失效不会导致B上的副本不可达（在nodeID离fileID第k+1近的结点C上保存副本指针）

文件转移 当“副本转移”仍不能完成保存任务时，即叶集结点也无法容纳文件，只能回发给文件插入者一个“消极确认”(negative acknowledgement)消息 插入者使用新的盐值(salt)为该文件产生新的fileID，并重新尝试插入，称为“文件转移” 文件转移尝试四次后才放弃插入操作

4、PAST缓存管理 目的：减小文件查询时延；增加系统查询吞吐量；平衡系统查询负担 方法：路径缓存（文件插入路径或查询路径） 副本只是临时缓存，结点需要空间时可以自主替换缓存，PAST的缓存替换方法基于GD-S策略(GreedyDual-Size，原先用于缓存Web代理) GD-S为每个缓存的文件d维护一个权重H(d)，每当缓存命中，H(d)被设为c(d)/s(d)，c(d)代表和文件d相关联的某种开销，常设为1，s(d)代表文件大小；H最小的文件v首先被替换，替换后，当前每个缓存文件的H(d)被减去H(v)。该策略可最大化文件命中率

PAST总结 是一个以Pastry为底层架构的广域P2P归档存储系统，提供Internet上安全、高可用、持久性的数据存取服务

思考练习 1 本讲的路由表项都是O(logN)下的O(logN)的查找效率，有没有可能O(d)下的O(logN)查找效率？试证明理论上的可能性，并分析可能实现途径。 2 阅读论文掌握CFS的三种改进技术思想：前驱列表定位，服务器选择，ID认证 3 阅读论文掌握CAN的背景区域重分配算法的设计思想

课后阅读 S. Ratnasamy, S. Shenker, and I. Stoica. Routing algorithms for dhts:Some open questions. In Proceedings of IPTPS02, Cambridge, USA,March 2002. http://www.cs.rice.edu/Conferences/IPTPS02/.

实践环节： 用P2PSim做Chord,Tapestry 的仿真实验，并学习P2PSim是如何编程实现协议功能的。 scripts/run-simulations.pl --protocol Chord --topology example/topology.txt --logdir . --args example/chord_args

请事先阅读如下论文 Kademlia SkipNet Viceroy [Maymounkov and Mazieres.02] Petar Maymounkov and David Mazieres. Kademlia: A Peer-to-peer Information System Based on the XOR Metric. In IPTPS 2002, pp. 53-65. SkipNet [Harvey et al.03] Nicholas J. A. Harvey, John Dunagan, Michael B. Jones, Stefan Saroiu, Marvin Theimer, Alec Wolman. SkipNet: A Scalable Overlay Network with Practical Locality Properties. In the 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003),  Seattle, WA, 2003, pp. 113-126. Viceroy [Malkhi et al.02] Dahlia Malkhi, Moni Naor, David Ratajczak. Viceroy: A Scalable and Dynamic Emulation of the Butterfly. In PODC 2002, pp. 183-192.

Koorde [Kaashoek and Karger.03] M. Frans Kaashoek and David R. Karger. Koorde: A Simple degree-optimal distributed hash table. In IPTPS 2003, pp. 98-107. Cycloid [Shen et al.04] Haiying Shen, Cheng-Zhong Xu, Guihai Chen. Cycloid: A Constant-Degree and Lookup-Efficient P2P Overlay Network. In IPDPS 2004, April 2004, New Mexico, USA.

附录：Bloom Filter Bloom Filter[BLOO 1970]是为了支持成员查询而对一个集合进行概率表示的一个压缩数据结构，所谓成员查询是指“元素a是否是集合B中的元素?”这样的查询。

Bloom Filters IN OceanStore Use multiple hash functions to hash each item Use hash values to generate bit offsets Combine bits of all items together Bit vector is summary To use summary, hash new value. Value is NOT in pool if any bit=0 H1(B) H2(B) H3(B) 1 H1(A) H2(A) H3(A) Pool Summary 1 H1(C) H2(C) H3(C) 1 1 Pool

Cascaded-Pools Hierarchy Combined Downward Summary Search in local pool Check local summary Check summaries at each outgoing “Pipe” Local Summary Local Summary Downward Summary Downward Summary Local Summary Local Summary Local Summary Every pool has good randomized index structure (such as Treaps)