Pastry路由协议浅析

前言

在上篇文章Mossad-本木医疗智能终端治理主要介绍了智能终端治理的整体解决方案。其中在软件升级模块介绍了基于P2P的文件传输系统。该系统解决了在带宽有限以及终端数量庞大的场景下快速完成升级包网络传输的问题。那么神秘的P2P的运行机理是怎么样的？接下来本文将带领大家深入探索一番。
Pastry是微软研究院和美国莱斯大学共同提出的用于广域网(适用于局域网)的分布式查找和路由系统。Pastry构建了一个稳定的，自组织的重叠网络。互联网上的任何计算机只要安装有Pastry相关实现软件并获取相关证书即可加入。

整体设计

Pastry是自组织的重叠网络。所谓的自组织就是Pastry能够自动的应对节点的加入，离开和失效。网络上的每一个节点都拥有一个唯一的，128bit的NodeId。NodeId用于在Pastry的圆形节点空间(0到 $2^{128}-1$)中标识自己的位置。理论上所有节点的NodeId在整个节点空间中是均匀分布的。这个目标可以通过对节点上的公钥或者IP进行HASH值计算来达到。在路由消息的时候，给定一个消息Msg以及一个关键字Key，Pastry即可把MSG路由到NodeId和Key在数值上最接近的那个节点。
假设一个Pastry网络包含N个节点，那么Pastry能够在$log_{2^b}N$的步数内将一条消息路由至任何一个节点。除非NodeId和Key临近的节点中有$L/2$(L是一个配置参数，通常设置为16或者32)个同时失效，否则Pastry可以保证在多节点失效的情况下都可以可靠的将Msg送达。至于为什么，我们分析完Pastry的路由原理就很清楚了。

状态表

为了进行路由，Pastry把NodeId和关键字(Key)标识为一串以$2^b$为基的数。节点NodeId间的逻辑距离度量用节点NodeId间所具有的相同前缀计算，具有的相同前缀越多，代表距离越近。假设有三个节点，节点X(10233102)，节点A(10233222)，节点B(10233212)。X和A具有5个相同前缀"10233"，X和B有3个相同前缀"102"，那么X相对于A的距离要小于X相对于B的距离。
所以路由的基本方法为：

当前节点(A)把消息(关键字为X)路由给下一个节点(B)时，要保证B与X具有的相同前缀数的比A与X的相同前缀数至少多一个数位(b个bit)。如果找不到这样的邻居节点，消息将转给给节点与X前缀长度相同但是数值更节点关键字的几点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。

为此，每个Pastry节点都需要维护一系列的状态表：

路由表

上表格模拟了一个NodeId为102333102的Pastry节点维护的路由表。其中参数b取值为2，所有的数是4进制的。其中路由表最上面的一行是第0行。路由表中每行的单个数字代表NodeId为102333102的节点相应的位数。路由表中每个节点的NodeId的表示格式是：

相同前缀+下一数位+NodeId剩余数位

为了方便展示，表中我用"-"对三部分做了分隔。每个节点会关联一个相应节点的ip地址，表格中并未列出。在包含N个节点的Pastry网络中，路由表一般拥有$log_{2^b}N$行，每一行有$2^b-1$个表项。在第$n$行的第$2^b-1$个表项中，每个节点的NodeId的前$n$个数位相同，而第$n+1$个数位和当前节点不同。而表项的选取原则是在众多的与当前节点具有相同前缀数的节点中选择距离最近的节点。这里的距离跟上一小节定义一样。
b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的一个折中。例如，当b取4，网络中有$10^6$个节点时，每个节点的路由表平均需要75个表项，预期的路由跳数是5。如果网络中有$10^9$个节点，则路由表平均会有105个表项，而预期的路由步数也会增加到7。
路由表的平均表项估算公式为：

叶子节点表

除了路由表，每个节点还要维护一个叶子节点表。叶子节点表维护了与本节点NodeId距离最近的节点。其中一半是NodeId大于当前节点NodeId的，另一半是NodeId小于当前节点的。叶子节点表也是路由算法的关键信息。

邻居节点表

邻居节点维护与本地节点最接近(按照给定的评测指标距离，比如round trip time)的$M$个节点。 正常的路由过程并不使用邻居节点，它的主要作用是维护路由的本地性。

路由协议

下面的伪代码是在一个节点在接收到路由请求时执行的过程。

$R_{l}^{i}$:路由表R中在l行i列的表项，其中$0<=i<2^b$, $0<=l<128/b$.
$L_i$:叶子节点集中第i个距离最接近的界定NodeId, $-L/2<=i<=L/2$.其中正负表示与当前节点NodeId的大小。
$D_i$:关键字key,第i个数位的值。
$shl(A,B)$:A与B的前缀匹配长度。

节点在收到一条消息时，首先检查消息的关键字(以$2^b$为基的数)是否落在当前节点的叶子节点范围内。如果是，则直接把消息转发给对应的节点，也就是叶子节点集中NodeId和关键字最接近的节点。如果关键字没有落在叶子节点集的范围内，节点就会把消息转发给路由表中的一个节点，该节点的NodeId和关键字的相同前缀至少要比当前节点的NodeId和关键字的相同前缀长一个数位。如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候消息将被转发给前缀长度相同但是节点号数值更接近关键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且只要叶子节点集中一半以上的节点没有同事失效，就一定可以找到满足要求的节点。根据过程的收敛性，消息一定能到达终点。

考虑路由过程中的三种情况：
1. 如果一个消息的关键字直接在叶子节点范围内，那么到达目的节点的跳数最多只有一条。
2. 如果一个消息的关键字不在叶子节点范围内，但是下一跳在路由表中找到，那么节点集中前缀与关键字匹配更长的节点因每一跳的$2^b$因子就会减少，这意味着到达目的节点的跳数将达到$log_{2^b}N$.
3. 当消息的关键字不在叶子节点集中，每一跳在路由表中也找不到，那么跳数就会增加。假设路由表是正确的而且没有节点路由失败，这意味着一个节点没有适当的前缀。

状态维护

节点加入

新节点加入时需要初始化自身的状态表，并通知其他节点自己已经加入系统。

假定新加入节点的NodeId为X(NodeId分配是应用程序的细节，典型的是使用SHA-1哈希它的IP或是公共Key)。同时假定X在加入Pastry之前知道系统中和自己距离相近的节点A。新节点X首先请求A路由一条“加入”消息，消息的关键字就是X。这条消息最终会到达NodeId和X最接近的节点Z。作为应答，节点A、节点Z以及从A到Z的路径上所有经过的节点都会把自己的状态表发送给节点X。节点X利用这些信息初始化自己的状态表，然后节点X再通知其他节点它已经加入了系统。从交换的消息数量上说，节点加入操作的复杂度为$O(log_{2^b}N)$。

邻居节点

假设A是新节点X距离相近的节点,那么A用它的邻居节点集发初始化X的邻居节点集.

叶子节点

而Z是与X的ID最接近的节点，所以它的叶子节点集X叶子节点集的初始化依据.

路由表

我们考虑一下路由表的初时化。从0行开始，通常情况下，$A$的节点NodeId和$X$的节点ID没有共同的前缀。用$A_i$表示$A$中路由表的第i行，我们意识到路由表的第0行就是跟本节点ID没有任何联系的，所以$A_0$是适用于$X_0$的。因$A$和$X$的ID是没有共同前缀的，所以$A$中的路由表的其他行对$X$的路由表初始化没有用。
适合$X_1$的值就可以从$F_1$中得到，$F$为$A$路由到$Z$的第一个节点. 这个很容易就可以想到，$F_1$和$X_1$有共同的前缀，因为$X$和$B$的NodeId的第一个位数是相同的，同样的，$X_2$的值可以从$K_2$中得到，以此类推，一直到$Z$。
最后，X把最后得到的状态复制一份发到邻居节点集，叶子节点集，路由表中的所有节点，这些节点用所收到的信息更新他们的状态。可以看出，新节点X现在具有了路由和接受消息的功能，并成功的加入到Pastry网络中。

节点离开

Pastry中节点很可能失效或者突然离开系统。若NodeId空间中的相邻节点无法和某个节点通信时，就认为该节点失效了。一旦节点检测出其叶子节点集L中的某个节点失效，它就会请求该集合中NodeId最大或最小的节点把其叶子节点集L1发送过来。（如果失效节点的NodeId比当前节点的NodeId大，则用叶子集中NodeId最大的节点，反之则用NodeId最小的节点。）当前节点将从L1中选择一个L中没有的活动节点来替代失效节点。
如果节点检测出其路由表中某项对应的节点失效，它将从该项所在的路由表行中选择另一个节点，要求该节点把路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点将从路由表的下一行中选择一个节点，这个过程将继续到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由表为止。节点也会周期性地和邻居节点集中的节点交换信息以检测这些节点是否仍在Pastry系统中，如果节点检测出其邻居节点集中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。

后话

原本神秘的P2P路由协议，在经过分析后也变得简单易懂。本文分析Pastry的路由原理不是为了实现一套自己的路由协议，而是基于工作需要和兴趣。Pastry有一套默认的开源实现FreePastry。这套开源实现具有开源软件通用的毛病：文档不够完善、一堆bug、版本兼容差等。在上手过程中，发现了很多无法理解的问题，而且解决不了。于是乎只能去看Pastry相关的论文，并修复源代码中的一些bug，才顺利完成工作。