1. Overview
对等系统需要有:
- 系统中每个结点都能向系统提供资源
- 结点在同一对等系统中有相同的功能和职责
- 系统不依赖一个中心管理系统
- 系统提供给资源生产者和消费者一定的匿名性
- 系统要实现一个选择放置资源、访问资源结点的算法（实现负载均衡、高可用、减少不必要的开销）
2. 遗留系统 - Napster文件系统
其包含一系列用户结点（对等的），并维护一个集中式索引。
其动作分为5步：
- 用户结点向索引服务器发出文件位置请求，以获取有该文件的结点列表
- 索引服务器返回该文件的结点列表
- 向这些结点发送文件请求
- 那些结点进行文件传输
- 最后向索引服务器进行索引更新（说明自己已有这个文件）
优点：
上述5步实现了一个负载均衡的机制，且可伸缩，避免单个用户的计算资源和网络连接的拥塞
局限：
建立的统一的集中索引（可复制），其副本不保证一致性。若要强一致，其方法有局限性，对象发现和得可能成为性能瓶颈。
应用依赖：
- 假定文件内容副本不会被更新，无副本之间的一致性需求
- 不需要保证单个文件的可用性
3. 对等中间件
3.1. 功能性需求
- 实现定位单个资源的位置并与其通信
- 能随意添加新资源/删除旧资源
- 能添加/删除结点
- 实现简单的编程接口
3.2. 非功能性需求
- 全球可伸缩，支持访问数万台主机上数百万计的资源
- 负载平衡
- 优化相邻结点间的本地交互，将资源放置在靠近经常访问它们的结点
- 适应高度动态的主机可用性，主机加入系统时主机必须集成道系统中，主机退出时，系统要检测它们的退出，负载和资源都要重新分配
- 在不同信任体系下，保证数据的安全性
- 匿名、可否能力和对审查的抵抗
对象的位置信息必须分区且分布于整个网络。
结点负责维护一部分结点的位置信息和对象位置信息，并对整个拓扑结构有一个整体了解。
通过大量复制保证系统的高可用性。
4. 路由覆盖
负责定位结点和对象的算法。该算法把全球路由到目标对象的主机上，不需客户参与，且在应用层实现（与网络层路由分离）。[即确保请求通过一系列结点和各个结点关于目标对象的知识，确保任意一个结点可访问任意一个对象]
主要任务：
- 路由请求到目标对象：请求包含一个GUID（全局唯一标识符），路由覆盖把请求路由到一个含有该对象副本的结点上
- 插入对象：先计算对象的GUID（如通过SHA-1），然后通知路由覆盖，它会确保所有其它客户能访问到这个对象
- 删除对象：移除对象后，路由覆盖必须使这些对象不可用
- 结点增加/删除：负载和资源分布等需要重新分布（而且需要保证开销尽量小）
路由覆盖有时被称为分布式散列表（DHT），可有如下接口：
put(GUID, data): 数据存储到由GUID确定的结点上remove(GUID): 删除所有GUID的引用和数据value = get(GUID): 从相关结点获取GUID相关联的数据在该模型下：
- 数据
data的GUIDdata.GUID = x被存在一个结点node上，node.GUID最接近于data.GUID- 数据
data的GUIDdata.GUID = x还被存在r个结点上，r为复制因子，这些结点的GUID次接近于data.GUID应用：Pastry
- 保存叶子集合，包含了2l个与当前结点GUID最相近的其它结点的GUID和IP地址（l个大于，l个小于）
- 并应用前缀法保存[GUID, IP]信息，通过匹配前缀来决定下一跳的地址，且添加/删除节点时有最近邻居算法，保证路由路径变短
分布式对象定位和路由（DOLR）提供比DHT更灵活的API：
publish(GUID): 执行该操作的结点和该GUID资源进行绑定unpublish(GUID): 使得GUID对应的对象不可访问sendToObj(msg, GUID, n): 发送一个消息到GUID对应的对象，最后的参数表示传给n个对应的副本在该模型下：数据对象副本位置由路由层外决定，每个副本的主机位置通过
publish(GUID)来通知DOLR层应用：Tapestry
Pastry路由算法
当前结点的GUID是A, 目标结点的GUID是D, 消息为M, R[p, i]为路由表中的第p行第i列元素(值包含了[GUID, IP]), L为叶子集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(L[-l] < D < L[l])
forward(M, L[i]); // 这里L[i]的GUID是离目标D/当前A最小的
else
{
prefix = findLongestPrefix(D, A);
p = prefix.length; // 公共前缀长度
i = D[p]; // D的第p+1位十六进制位
if(R[p, i] != NULL)
forward(M, R[p, i]);
else
{
nextHop = 从L或R的公共前缀中寻找一个离D最近的地址;
forward(M, nextHop);
}
}
