由于我们对 P2P 网络和分布式系统感兴趣，因此我们决定开始用 Ruby 从头开始构建自己的类似 BitTorrent（BT）的系统。目前可用的版本是我们发布的 alpha 测试版本，提供了一个有效的概念验证：完整的分布式路由表，节点间的通信和基本的文件传输。在本文末列出了未来要新增的功能，我们将会继续改进 Xorro。

本文记录了我们构建 Xorro P2P 的过程。希望读者阅读本文后能对 P2P 系统有更深一层的认识。

Xorro P2P 运行界面

研究

作为严格意义上的 P2P 系统的最终用户，我们开始了开发旅程，面临着非常陡峭的学习曲线。我们必须进行大量的研究来了解 P2P 相关的历史和内部组成。我们进行了搜集和阅读 P2P 相关资料，从旧到新依次有：Napster、Gnutella、Freenet。BitTorrent、IPFS……

集中式系统 vs 去中心化系统

需要理解的一个重要概念是集中式和去中心化系统之间的区别。第一代和第二代网络架构的比较有助于描述这两者之间的区别。

Napster：集中式系统

Napster 是一种 P2P 文件共享服务，主要用于传输音乐文件，在 1999~2001 年非常流行，据估计，在鼎盛时期大约有 8000 万注册用户。Napster 的工作原理是让所有节点都连接到中央索引服务器，该服务器包含所有关于谁拥有哪些文件的信息。

集中式 P2P 网络的一个示例

因为其本身为集中式的结构，Napster 中央服务器很容易遭受到攻击，以及文件传送的方式备受争议，营运两年后在法院的判决下被迫关闭。除此之外，中央索引服务器还意味着存在单点故障，以及缺乏可扩展性。

BitTorrent、Gnutella、Freenet：去中心化系统

下一代 P2P 网络通过采用去中心化的模式避免了与 Napster 相同的命运。

在像 BitTorrent 这样的去中心化系统中，每台计算机 / 节点都充当客户端和服务器，维护自己的文件查找索引片段。节点可以通过其他节点来查找文件的位置，免除了对中央服务器的依赖。

去中心化 P2P 网络的一个示例

P2P 文件共享系统的深入介绍

了解新一代 P2P 系统的优点后，我们继续深入研究它们的特性。幸运的是，P2P 网络是已经发展一段时间的技术，因此网上有许多资源可供我们利用。其中分布式哈希表（distributed hash tables ，DHT）是 P2P 网络中最重要的技术，因此分布式哈希表是当前 P2P 网络的基础。我们花了很多时间进行阅读及研究白皮书、规范文档、博文和 Stackflow 问答，在开始编程之前，我们要确保对分布式哈希表有深刻的了解。

我们找到的有用资源的列表在这里：

功能的选择

BitTorrent 主要功能

经过比较许多 P2P 网络之后，我们最终锁定了 BitTorrent 的一组功能，作为我们开发应用的第一个版本的蓝本。这些功能将在下文中将进一步详细描述。

分布式哈希表（DHT）

文件切分

节点既作为客户端又作为服务器

演示

在深入了解 Xorro P2P 的实现细节之前，请先查看下面的动图，该动图解说了文件下载过程的实际情况。

首先，清单文件（即 BT 种子，下同）会被下载，然后依据种子中列出的文件切分信息下载各个文件切片。下载完所有的切片后，将它们重新合并回原始文件。

分布式哈希表的实现

先评估几种分布式哈希表的优缺点：Chord、Pastry、Apache Cassandra、Kademlia 等等，再以此为考量作为我们选择的依据。我们最终决定就其普及率、最简单的远程过程调用和信息的自动传播等优点，选择了 Kademlia。

事实证明，由于大量的新概念：节点、路由表、桶（buckets）、异或距离、路由算法、远程过程调用（remote procedure calls，RPC）……，使得 Kademlia 的实施极具挑战性。虽然当时网上已经有一些 Ruby 的实现，但我们只依据规范和白皮书，因为我们要从头开始构建分布式哈希表。

Kademlia

一个 Kademlia 网络由许多节点组成。

每一个节点都有：

具有唯一的 160 位 ID。

维护包含其他节点联系信息的路由表。

维护较大的分布式哈希表中那些自己的段。

通过 4 个远程过程调用与其他节点通信。

每个节点的路由表被划分为“桶”，每个桶包含与当前节点的特定“距离”的节点的联系信息。我们会在后面更详细介绍关于距离的概念。

每个联系信息都包含其他节点的 ID、IP 地址和端口号。

由于 Xorro 是一个文件共享应用程序，因此分布式哈希表段将包含 key/value 对，其中，每个 key 是一个文件的 ID，对应的 value 是文件的位置。

Kademlia 规范中描述的节点构成。

节点通信

Kademlia 节点发送和响应有四种基本的远程过程调用。

PING

与互联网控制消息协议（Internet Control Message Protocol，ICMP）中的 Ping 非常相似，它是用于验证另一个节点是否仍处于活动状态。

FIND NODE

发送此远程过程调用时要找到特定节点的 ID。此远程过程调用的接收节点在自己的路由表中查找，并返回一组最接近正在查找的 ID 的联系节点。

FIND VALUE

发送此远程过程调用时要带有要定位的特定文件 ID。如果接收节点在自己的分布式哈希表段中找到这个 ID，它将返回响应的 Value（URL）。反之，则接收节点返回最接近文件 ID 的联系节点列表。

STORE

此远程过程调用用于在接收节点的分布式哈希表段中存储 key/value 对（file_id/location）。

每次成功完成远程过程调用后，发送节点和接收节点都会在各自的路由表中插入或更新彼此的联系信息。

寻找对等点和文件

一个节点如何在 Kademlia 网络中找到其他节点或者文件呢？我们可以用现实生活中的例子来举例。

如果某个人想找到另一个不认识的人，他可能会采取以下步骤：

他可以询问离目标人物更近的朋友。也许这些朋友和目标人物在同一个行业工作，或者在同一个城市居住。

如果其中一个朋友知道目标人物在哪里，那么就可以提供目标人物的联系信息，这样查找就完成了。

如果这些朋友都不认识目标人物，他们可以给你提供可能认识目标人物的朋友的联系信息。

然后你再询问这些人，看看他们是否知道目标人物，重复这一过程，直到找到目标人物，或者达到某种停止查找的条件。

Kademlia 节点在执行查找时就遵循类似的模式。

如果一个节点要从网络中检索一条信息（一个文件），它将发送 FIND VALUE 的远程过程调用到它自己的联系节点子集，这些联系节点的 ID 与它要查找的文件的 ID“最为接近”。如果任何接收节点在其分布式哈希表段中有这个 ID，则它们将返回相应的 value，否则，它们将返回更接近所查询的 value 的节点列表。

下一个要讨论的问题是如何在 Kademlia 网络中确定“距离”。

距离的计算

Kademlia 将节点之间的距离定义为节点 ID 的“按位异或”（XOR）。XOR 运算比较两个输入值：如果这些输入相同，则结果为 false(0)；如果输入不同，则结果为 true(1)。两个数字的异或是通过在这两个数字的二进制表示中找到每一位的 XOR 来计算的。

例如，下图假设 4 位密钥空间中的节点 ID 为 11（只有 0~15 的的 ID 是可能的）。为证明这个概念，我们使用一些其他 ID 来计算 11 的 XOR。

在第一个例子中，我们计算节点 ID 11 和节点 ID 10 的 XOR 结果。两个 ID 的前三位是相同的，只有最后一位不同。ID 11 和 ID 10 进行 XOR 运算的结果是二进制的 0001，或者十进制的 1。

接下来我们计算 ID 11 和 ID 12 的 XOR 结果，只有第一位是相同的，而其他部分都是不同的。ID 11 和 ID 12 的 XOR 运算的结果是二进制的 0111，或十进制的 7。

我们最后的一个例子是计算 ID 11 和 ID 4 的 XOR 结果。这里所有的位都不相同，结果是二进制的 1111，十进制为 15。

从这些结果中，你会注意到 Kademlia 的 XOR 度量的一个重要特征：如果节点 ID 和当前节点的 ID 的二进制表示所共有的位相同个数越多，那么计算得到的 XOR 结果就越小。

Kademlia 网络和路由表

Kademlia 中的每个节点都可以看做是二叉树中的叶子。下面我们在 4 位密钥空间中画出所有可能的 ID：0~15，从根（root）出发，每一步往左则在该位上新增一个“0”，往右则在该位上新增一个“1”。

与 Kademlia 网络相关的二叉树最重要的特性是 O(log n) 查找时间。在 Kademlia 网络中查找节点或文件是非常有效率的过程。

如前所述，路由表将联系节点进行分组并存储到桶中，每个桶中包含一定距离的节点。这个距离就是“共享位长度”，它是通过节点 ID 与当前 ID 进行 XOR 运算得到结果来得到的。

从下图我们将看到这些桶是如何在一个 4 位密钥空间中以 ID 11 的节点中组织的。其 ID 与当前节点共享前 3 位前缀的节点存储在一个桶中，而 ID 与当前节点共享前 2 位前缀的节点存储在另一个桶中，以此类推。

文件切分和检索

文件切分是将文件切分成更小的片段，命名为切片，并将 files/names 记录在一个清单文件（即种子）中，这样它们就可以按照适当的顺序检索和重新合并。

文件切分提高了 P2P 网络的分布性和可靠性，因为多个节点可以存储共享文件的部分或全部切片。如果包含切片下载信息的节点离线了，此时可以从不同的源检索该切片信息。

文件切分还可以节省网络带宽，共享潜在大文件的负载分布在许多节点中。

文件切分过程中会生成多个切片和一个清单文件（种子）。

在我们的实现中，文件添加和切分的过程是这样的：

通过拖放将要共享的文件上传到网络中。

通过计算文件内容的 SHA1 哈希值为文件创建 ID。

这个 ID 被重新用作种子的文件名，扩展名为“.xro”。这个过程对用户来说是透明的，用户只需知道 ID 即可。

原始文件切分成 1 MB 块，如果小于 1 MB，则切分为原始大小的 50%。

每个切片都被写入磁盘，切片的名称就是其内容的 SHA1 哈希值。

切片名称是按照顺序写入种子文件的，以及原始文件名和文件大小（以字节为单位）。

种子和切片位置信息通过 STORE 远程过程调用广播给对等节点。对于每个 shard/manifest，宿主节点在自己的路由表中查找与文件 ID 最接近的节点。这些对等节点都接收包含文件的 ID 和位置的 STORE 远程过程调用。

下面是 JSON 格式的种子内容：

复制代码

{

file_name:banana.mp4,

length:9137395,

pieces:[

,

,

,

,

,

,

,

,

]

}

文件检索的处理方式也是类似的：

用户输入他们想要从网络中检索的文件的 ID。这个 ID 是文件内容的哈希值，也恰好是他们首先检索的清单文件的名称。

通过向最接近清单文件 ID 的对等节点发出 FIND VALUE 远程过程调用，从网络中检索清单文件。

下载清单文件后，节点为清单文件中记录的每个切片重复查找和下载过程（FIND VALUR 远程过程调用）。

下载完所有切片后，将它们重新合并到原始文件中。

然后，节点向最接近文件各自 ID 的对等节点广播其获取的切片和清单的位置信息。

从 Xorro P2P 网络中检索文件的例子。

开发策略：从本地环境模拟并扩展网络应用到真实网络。

第一阶段：测试模式

我们是如何着手构建和测试的？

在项目的早期阶段，我们需要测试节点间的通信，但我们只有类和测试套件，没有网络，没有远程过程调用传输，甚至也没有几台计算机。

我们经常启动 Ruby 的交互式 Shell（IRB），将几个节点进行实例化，并让它们手动通信。当然，这可以通过脚本来实现。但一旦引入真正的网络环境，并且节点对象不能在相同的 Ruby 进程中直接使用，否则它就会很快崩溃。

我们需要某种代理对象，它在测试和本地开发期间以一种方式运行，在实际网络环境中部署时又以另一种方式运行。

我们的解决方案是让每个节点将所有网络通信都委托给先前存在的网卡（Network Adapter）对象。

在测试时，在这个网卡对象实际上是一个“Fake Network Adapter”（伪网卡），本质上是一个由其他节点组成的数组，带有一些用于查找和远程过程调用代理的方法。这允许我们在没有远程过程调用传输协议的情况下在本地沙箱中测试节点的交互过程。

典型的工作流程如下图所示：

节点 A 要求网络向节点 B 发送远程过程调用，节点 A 提供联系节点的 ID、IP 和端口。

网络查找节点 B 是否存在于 Fake Network （伪网络）环境中，这是通过联系节点的 ID 来完成的。

网络直接调用节点 B 上的方法，改变状态和 / 或返回一些数据作为响应。

网络将该响应传递回节点 A，节点 A 反过来改变状态或对这些信息做出响应。

第二阶段：在本地沙箱中通过 HTTP 进行远程过程调用

我们的下一步是引入 HTTP 协议作为构建远程过程调用方法的基础协议。

为此，我们实现了一个 Real Network Adapter （真网卡）对象。它与我们的 Fake Network Adapter 具有相同的接口，但不是通过 ID 查找接收节点并直接调用该方法的，Real Network Adapter 从所提供的联系节点信息和对应于远程过程调用的路由中列出的 IP / 端口处理一个 HTTP Post 请求，可能包括请求主体中的相关数据——请求节点的联系信息、查询信息等。

典型工作流程与上图类似：

节点 A 要求网络向节点 B 提供远程过程调用，节点 A 提供联系节点的 ID、IP 和端口。

网络为 IP、端口和远程过程调用路径生成 HTTP POST 请求，并将其与任何有效负载数据一起发送。

接收节点的 HTTP 端点接收 POST 请求，并调用 Node 对象上的接收远程过程调用的方法。

此接收远程过程调用方法的返回值通过 HTTP 端点转换为 HTTP 响应，并发送回调用节点的网卡。

网络接收响应，并将其传递给节点 A，节点 A 反过来更改状态或对这些新信息做出响应。

正如你所见到的，从节点的角度来看，并没有什么变化：每个节点都发送和接收相同的信息，但是网络对象和 HTTP 端点抽象出节点之间的通信。

第三阶段：RPC/HTTP 在互联网环境下传递

一旦我们知道节点间的通信使用 HTTP 协议，我们的下一步就是将节点部署到互联网上的多个系统上。如果系统直接在公共互联网上运行，或者它们位于已配置打开端口的防火墙之后，这种方法就可以很好地工作。

NAT 防火墙后的节点则是另一回事。它们可以很好地加入网络并检索文件，但如果没有端口转发的话，它们就不能接收传入的 HTTP 连接，因此不能对网络做出贡献。

从长远来看，目标是基于 TCP / UDP 协议的远程过程调用和文件传输协议，同时支持 STUN 和 TURN 服务器来处理公共 IP / 端口发现和传入连接。但是，在这个项目中，我们需要一种快速绕过 NAT 和防火墙的方法。

为此，我们构建了对 Ngrok 的支持，这是一个第三方隧道服务，这样，防火墙后面的节点就可以成为我们网络中完全正常运行、功能齐全的成员。

灵活的节点实例化和启动脚本

我们意识到现在有许多不同的节点配置 / 环境需要支持和测试。此外，我们还需要一种能够在这些配置之间快速、无缝切换的方法。

在每个环境中，一个节点广播它的 IP / 端口，以及它所托管的每个切片或种子的完整 URL / 路径。

如果我们只在本地环境中工作的话，那么所有节点都在不同的 TCP 端口从“本地”进行广播。

如果节点直接在互联网上，它应该广播自己的公共 IP 和端口。

如果节点具有完全限定的域名，那么该节点应该广播该域名，而不是数字 IP 地址。

如果节点位于防火墙之后，且防火墙已正确配置用于 NAT 转换 / 端口转发，则该节点仍然可以依赖它的公共 IP 和端口。

如果节点位于没有转发端口的防火墙后面，则需要：

建立到 Ngrok 服务器的隧道，并注意到它唯一的 Ngrok 地址，这样它就可以将地址广播给其他节点。

要知道它是一个 “Leech” 节点，而不是广播它所托管的任何文件的位置信息。

我们确定了节点可能拥有的许多配置，并创建了环境变量来表示这些选项。我们的节点实例化代码对这些变量做出反应，我们设计了一系列 Bash 脚本，来为我们工作的每个环境标准化这些配置：测试、本地、局域网、广域网等。

系统架构

我们最终的系统架构如下所示：

顶级对象是 XorroNode，它是一个模块化的 Sinatra 应用程序。

每个 XorroNode 包含：

一个单独的 Kademlia 节点，负责维护自己的路由表和分布式哈希表。

用于向其他节点发起远程过程调用的网卡。

用于从其他节点、Web UI 和文件传输接收远程过程调用的 Sinatra 端点。

用于文件接收、切分和清单文件的创建。谢谢