Chord：一个可扩展的网络应用p2p传输服务

概要

p2p应用面临的基本问题是有效的指派节点存储在特定的数据区域。这个paper提出了Chord，一个分布式的检索协议来解决这个问题。Chord只是提供了一个操作给定一个key映射到节点中。通过结合key和每个数据项数据分配可以很容易的Chord上实现，将键/数据存储在键所映射的节点上。Chord有效的模拟了节点的加入和离开系统，并且回应查询，即便系统多次修改。理论分析、模拟和实验结果表明了Chord是可扩展的，通信成本和每个节维护的状态随着Chord的节点呈现对数增加。

1 介绍

p2p系统和分布系统应用不包含任何去中心化的控制和层级结构，其中节点上运行的软件在功能上是相同的。最近的p2p应用的总览能得到一个长列表：冗余存储，性能，就近的服务器选择，匿名，查询，认证，分层命名。尽管有那么丰富的功能，大多数p2p系统的核心操作时有效的指派数据项。本文研究了一个节点频繁到达和离开的动态对等系统的可扩展查找协议。

Chord协议只支持了一个操作，给定一个key，映射到节点中。依赖于使用Chord的应用程序，该节点可能存储于键相关联的值。Chord使用了一致性哈希的变体来指派键到Chord节点上。一致性哈希趋向于负载均衡，因此每个节点接受到的键大致相同，并且当一个节点加入或者离开系统设计到相对较少的键移动。之前在一致性哈希上的工作假设，节点知道系统中大多数的其他节点，使得扩展到大部分的节点变得不切实际。作为对比，每个Chord节点只需要几个其他节点的路由信息。因为路由表是分布式的，一个节点的与其他几个节点通信来解析哈希函数在稳定状态中N个节点的系统，每个节点维护logn个其他节点，通过O（log N）发送给其他节点消息解决所有的查找问题。Chord在节点加入和离开时维护它的路由信息；在很大的概率下，每个这样的事件不超过$O(log^2N)$条。将Chord与其他许多对等查找协议区分开来的三个特性简单，可证明的正确性，可证明的性能。Chord是简单的，路由键穿过O(log N)序列去往目的地的其他地点。Chord需要关于O(log N)哥其他节点的信息，以便有效的路由，但当这些信息过期时，性能会优雅的下降。在在现实中很重要，因为节点将加入和反复离开即便O(log N)状态也可能很难维护。为了让Chord保持正确（虽然很慢），每个节点只需要一条信息是正确的.Chord有简单的算法以维护动态环境下的信息.

本文的其余部分结构如下。第2节将Chord与相关工作进行比较。第3节介绍了激发Chord协议的系统模型。第4节给出了基础Chord协议并证明了它的几个属性，而第5节则介绍了处理并发连接和故障的扩展。第6节通过在已部署的原型上进行模拟和实验，演示了我们对Chord性能的断言。最后，我们在第7节概述了未来工作的项目，并在第8节总结了我们的贡献。

2 相关工作

3 系统模型

通过解决几个困难的问题，Chord简化了P2p系统和应用的设计

• 负载均衡：Chord的行为就像一个分布式哈希函数，划分key平均的跨越节点；这提供了自然的负载均衡读
• 去中心化： Chord是完全分布的：没有节点比其他节点更重要。这提高了健壮性，并且让Chord更合适于松散组织的p2p系统
• 扩展能力：Chord查询增长的代价是节点数量的指数级， 即便非常大的系统也是可行的。实现这种缩放不需要任何参数调优。
• 可用性：Chord自动的调节内部表反应新加入的节点以及节点的故障，确保这一点除非底层网络出现重大故障，节点的key总是能够被找到。即便是系统一直在修改中也能保证这一点。
• 灵活的名称：Chord对于它查找的键结构没有限制：Chord的键空间是平的。这给了应用大量的灵活性在如何映射名称到Chord key。

Chord使用软件的形式来连接客户端和它使用的服务应用。应用以俩中主要的形式和Chord交互。首先，Chord提供一个lookup(key)算法，生成负责秘钥的IP地址。第二，每个节点上的Chord软件通知应用它负责的一组key的修改。这允许应用软件在新的节点加入时，移动应用的值到新的位置。

应用使用Chord以负责提供任何的身份验证，缓存，副本和用户友好的数据命名。Chord的平面键空间简化了这些功能的实现。例如，一个应用可能需要通过将数据存储在由加密哈希生成的Chord键下，来实现对数据进行身份验证。类似的一个应用可以通过存储将数据存储在数据程序标识符生成的俩个不同的Chord下键下来复制数据。

机械来是一个应用程序事例，Chord将会提供良好的基础：

协同镜像 如同最近提案的概述一样。想象一组开发人员，它们每个人都希望发布一个发行版。对于每个发行版需求可能会有非常大的不同，新版发布后非常受欢迎到版本之间相对不受欢迎。一种有效的方法是是开发人员彼此写作本地镜像彼此的发行版。理想情况下，镜像系统将在所有服务器上平衡负载，复制和缓存数据，并确保真实性。为了保证可靠性，这样的系统应该去中心化，因为它们没有自然的中心管理员。

时分共享存储 为了节点的内部联通。如果一个人想要一些数据永远是可用的，它是它的机器只是偶尔可用，它们可以在别人在线时提供数据存储，作为交换，它们的数据会在宕机时存储在其他地方。数据的名称可以用作标识在任何给定时间负责存储数据项的（活动）Chord节点的键。一些写作镜像应用程序中出现了相同的问题，尽管这里的重点是可用性而不是负载均衡。

分布式索引 为了支持以支持Gnutella或Napster类似的关键词查询。此应用程序中的关键字可以从所需的关键字得到，而值可以是带有这些关键词的文档机器的列表。

大尺度的组合查询 如果代码被破坏。在这个例子中，key是候选的解决方案（比如加密秘钥）；Chord将这些键映射到负责测试它们的机器作为解决方案。

图1：基于Chord的分布式存储系统的结构例子

图1展示了一个协同镜像系统可能的三层结构。最上层将会为用户提供一个文件系统接口，包括用户友好的名称，以及鉴权。这个文件系统层可能实现了命名目录和文件，映射它们的操作到低级别的块之上。下一层是块存储层，它实现了块操作。它将负责块的存储，缓存和复制。块存储将会使用Chord来定义负责存储块的节点，然后与该节点上的块存储服务进行通信，读取或写入块。

4 基于块的协议

Chord协议指名了如何找到一个key的位置，新的节点如何加入系统，如何从失败中恢复（或者计划离开）现有的节点。这个章节描述了协议的简单版本呢，它不处理并发或者失败。章节5描述了协议的增强已处理加入和失败。

4.1 总览

在其核心，Chord提供了哈希函数快速分布式计算映射键到负责它们的节点。它使用了一致性哈希，它有几个良好的特性。伴随高概率哈希函数均衡负载（所有节点接受几乎相同数量的key）。也随着高啊概率，当第n个节点加入（或者离开）网络，只有O(1/N)key的部分移动到不同的位置-这显然是维持负载的最小值

Chord提升了一致性的哈希的可扩展性，通过避免每个节点需要知道每个其他节点。Chord节点只需要知道其他少量节点的路由信息。因为这个信息是分布式的，一个节点通过与其他节点进行沟通解析哈希函数。在N个节点的网络中，每个节点只维护大约O(log N)其他节点的信息，并且查找需要的O(log N)信息。

当节点加入或者离开网络，Chord必须路由信息；加入或者离开需要O(log^2N)信息。

4.2 一致性哈希

一致性哈希函数基于哈希函数HSA-1，指派每个节点和键n位标识符。节点的标识符是通过对节点的ip地址取哈希来的，而键标识符是通过对键进行散列来进行的。我们使用术语key是指的是原始的秘钥以及在哈希函数下的图像，因为上下文中可以清楚的了解其含义。类似的，术语节点指的是哈希函数下的节点以及其标识符。标识符的长度m必须足够长来让让使用俩个节点或键散列到同一标识符的概率可以忽略不计。

一致性哈希使用如下方法指定键到node节点中。标识符按照标识符圆圈的方式排序，采用$2^m$的模运算。key k被分配标识符空间中标识符定于或紧跟（的标识符）的第一个节点。通过successor(k) 这个节点叫做键k的继承者节点。如果标识符被表示为一圈数字从0-$2^m -1$，然后successor(k)是k的顺时针第一个节点。

图2：由三个节点组成的标识圆，在这个例子中，key 1被分配到节点1，key2 在节点3，key6在节点0上。

图2展示了标识圆，其中m=3。圆中有三个节点，0,1和3。标识符的successor 1是节点1，类似的2是被定位到节点3，key6被定位到节点0。

一致性哈希的设计目的为让节点以最小的终端进入和离开网络。已维护当节点n加入网络维护哈希的映射，特定的key先前被分配给n的继承者的现在分配给n。当节点n离开了网络，所有分配key所有的key重新分配给继任者网络。不需要对节点的键做其他的更改。在上面的例子中，如果节点要用标识符7进行连接，它将会从标识符为0的节点捕获标识符为6的节点。以下实验结果在一致性哈希的论文中得到了证明。

理论1对于任何n个节点和k个键的几何，具有很高的概率：

这个性质是关于一致性哈希在负载分配中的均匀性。假设有 NNN 个节点加入到哈希环中，理论上每个节点应该负责大约n分之一的哈希空间。如果每个节点能够处理的键的数量接近这个均值，就说明负载均衡较好。$\epsilon$是允许的误差范围。这个误差是由于数据和虚拟节点之间的映射关系造成的，通常是为了确保系统的鲁棒性和高效性。

当一个节点离开时，原本由它负责的键会被该节点顺时针方向的下一个节点接管，同样，也仅有 O(K/N)O(K / N)O(K/N) 个键需要转移。即只有离开节点负责的那一段哈希空间内的键需要迁移，其他节点的负载不受影响。（加入同理）。

1. 每个节点最多负责 $(1+\epsilon)/N$ key
2. 当第N+1个节点加入或者离开网络， 对于O(K/N)key负责转移（并且只能指向离开连接节点）。

我们的一致性哈希如上所述，理论证明$\epsilon$=O(log N)。一致性哈希paper中展示了，通过每个节点运行O(log n)个虚拟节点在标识符中，$\epsilon$可以被规约为任意小的常数。

“非对抗性的世界模型”这个概念，通常出现在人工智能、游戏理论、模拟系统等领域，指的是一种假设或模型，其中参与者（或系统）之间没有直接的竞争或对抗关系，而是以协作、平稳或者非冲突的方式进行交互。

极有可能这个短语值得讨论，一个简单的解释是这是因为节点和key是随机选择的，在一个非对抗性的世界模型中，这是合理的。概率分布是随机选择key和节点，并表示这样的随机选择不太可能产生不平衡的分布。然而一旦出现错误，关于攻击者故意选择相同的标识符的所有哈希键，以破坏负载的平衡属性。一致性哈希论文使用k个全局哈希函数，来避提供特定的保证，即便是在非随机key的例子中。

简单来说就是SHA-1是抗碰撞的。

我们使用了标准的SHA-1函数作为我们的哈希函数，而不是k个全局哈希函数。这让我们的协议具有确定性，因此高概率的说法不再有意义。然而生成一组在SHA-1发生冲突的秘钥可以看到，在某种意义上，就像对SHA-1函数的反转或者解密。这已经被认为非常难以进行。因此，与其声明我们的定理有高概率成立，我们可以声明它们“基于标准硬度假设”成立。

具体来说（主要指陈述），我们假设免除了对虚拟节点的使用。在这个例子中，节点上的负载可能会拆过平均水平，这是因为在高概率下最多有O(log N)的因子（或者在我们的例子中，基于标准的硬度假设）。避免虚拟节点的一个原因是所需节点的数量是由系统中节点的数量决定的，这可能很难确定。当然，人们可以选择使用系统中节点数量的先验上界；例如我们可以假设Chord服务最多有一个IPv4地址。在这种情况下，每个物理节点运行32个虚拟节点将提供良好的负载平衡

下面懒得翻译了
Chord 通过节点的复制来实现容灾。在 Chord 中，每个数据项（键值对）通常会被存储在环上一个节点的责任范围内，但为了增加数据的可靠性，Chord 会将数据项复制到其邻近节点上，通常是下一个节点。这是通过 "finger table" 和 "successor list" 实现的。

Finger Table 的作用

1. 加速查找：Chord协议通过路由查找的方式来定位键值所在的节点。每个节点维护一个指向其他节点的Finger Table，指向的是一些特定位置的节点（这些节点的ID在环上与当前节点的ID有特定关系）。通过Finger Table，查找操作不需要线性遍历所有节点，而是可以跳跃式地进行，减少查找的次数。
2. 路由优化：Finger Table 中的每个条目指向的是距离当前节点2^i（i=0, 1, 2, …）个节点的节点。例如，指向当前节点后第1个、2个、4个、8个位置的节点。这使得节点能够在O(log N)的时间复杂度内找到目标节点（假设环中有N个节点）。

这里补充一下原来一致性哈希查找是在数组中查找logn。现在这里变成了要跳跃logn次，进行$\log^2n$此查找。