用Rust编写一个BitTorrent引擎
rust bittorrent长大后，洪流对我来说是一件大事。我一直很好奇它是如何工作的。
好奇心只有在我开始编程并了解更多细节之后才会增加。有一项技术是如此有效而又简单，以至于在没有任何营销的情况下，由于纯粹的技术优势而获得了广泛的采用。它只是有效，人们使用了它。
那么为什么不写一个呢？我试过用C ++。它从未完成过，而且可能更好。算了吧
快进几年了。我进入Rust并需要熟悉的运动场语言。我做了在这种情况下任何人都可以做的事情：我编写了另一个洪流引擎。它是洪流引擎。
这样就诞生了cratetorrent。该名称是C ++ libtorrent库上的文字游戏。在我第一次尝试时，它的代码和博客具有很高的教育意义。这是我的感谢。
以下是BitTorrent V1协议的简要概述。对于那些熟悉的人，请随时跳到下一部分。
BitTorrent是一种主要是分散式的文件共享协议：它由可能交换任意数据的许多对称客户端组成。
与从单个主机下载相比，它的优势在于，负载是在torrent中的所有参与者之间分配的，从而提高了可用性，可伸缩性，并且通常还提高了下载速度。
它曾经非常流行，因为每个人都使用它来共享……Linux发行版，是的，还有其他绝对合法的内容。如今，它仍在使用中，但其使用案例更为微妙： Windows 10使用BitTorrent或类似工具在其用户中分发更新。
舞台上的第一个演员是torrent元信息文件。它包含有关洪流的基本元数据，最重要的是其名称，带有其路径和长度的文件以及其跟踪器。这些文件通常由洪流站点托管，这是您在开始洪流时下载的文件。
那么这些跟踪器是什么？虽然内容下载本身是完全分散的，但客户端需要知道可以从哪些其他客户端下载。种子流中的其他客户端也称为对等端。拥有所有数据的同伴是种子，其余都是水ches。有点不舒服。
因此，在下载开始时，客户端会向跟踪者询问对等点。跟踪器是协议的唯一集中部分。 1完成后，客户端将连接这些对等端并开始下载数据。
一个种子文件可能具有一个或多个文件，但从有线协议的角度来看，它们只是一个大的连续字节序列。
该字节序列被切成相等大小的片段，再被切成16 KiB块。对等方交换这些数据块，然后使用它们重新组装torrent的文件。 2
对等方只能共享其完整的部分。但是，将碎片分割成多个块可以从多个对等方下载它，从而有可能更快地完成。完成后，对等方可以立即与其他对等方共享它，即使它本身并没有全部内容。这增加了可用性，这是该协议的关键特征。
这里一个棘手的部分是，文件没有填充以与片段边界对齐。
因此，在将块写入磁盘时，可能必须将其拆分为多个文件。如果做得最好的话，逻辑可能会变得很粗糙。 3
然后，客户端从它选择的4个片段中请求一个块，其对等体将其发送，然后客户端将其保存。
就是这样，但也许没人会感到惊讶，现实世界中的实现会复杂得多。让我们来看看一些复杂性。
一个幼稚的实现可能会执行上面概述的操作：依次发送请求，即在处理上一个请求之后发送一个请求。问题在于它没有利用连接的容量。
为此，我们尝试为客户端从中下载的每个对等方估算连接的带宽延迟乘积。这是在任何给定时间链接上可以存在的最大数据量，即已发送但尚未接收的字节。
因此，为了获得最佳性能，我们会尽可能多地处理未解决的请求，以填满链接的容量。
显而易见，在相同的时间内，可以满足更多的请求。这是最重要的最重要的优化方法，由规范本身强烈建议。
Cratetorrent通过假设等待时间恒定为1秒，使用运行平均值作为下载速率和BDP的简化模型，以获取请求队列大小：
为简单起见，选择了1秒的值，但这是合理的猜测，如果我们采用链接来表示从一个对等磁盘到另一个磁盘的完整请求往返。
上面的内容提出了一个有趣的问题：达到链接容量的最快方法是什么？花时间去达到这个最佳数量会花费时间。不好。
事实证明，这是一个已解决的问题。为了找到答案，我们只需要在网络堆栈中窥视下面的一层：TCP。
建立TCP连接后，协议会尝试找到正确的拥塞窗口大小。这是一种奇特的说法，“发送的字节数不会阻塞远程主机及其之间的所有其他内容，但仍会占用网络容量。”我们的目的是相似的。
每次接收到所有的ACK时，窗口大小都会加倍。这种增长是指数级的，但该算法却被混淆地称为“慢启动”（大概以它试图避免的事物来命名）。
当检测到第一个超时或丢失的段时，TCP停止扩大窗口。这很难在用户空间中复制，因此cratetorrent每次都会增加请求队列的大小，而在下载速率不再增加时停止。 5
对于每个服务的请求，将发送更多请求，并且连接越来越接近完全使用可用带宽（非蓝色区域正在缩小）。
我注意到有时下载的最后阶段停滞不前，从一个块到另一个块几乎没有进行。
当从速度较慢的对等方下载最后待处理的片段时，会发生这种情况，这可能会使下载完成延迟令人惊讶的数量。 6
通常，通常从单个对等方请求每个块，但是应该以“谁先发送”为基础，从所有对等方下载最后一个块中的块。一旦到达，对较慢对等方的请求将被简单地取消。这浪费了一些带宽，但节省了大量时间。
就它们如何影响性能而言，这些是最重要的设计选择。还有更多，但您或我永远都没有。因此，让我们继续前进，看看所有这些如何转换成Rust。
Cratetorrent在网络侧使用异步IO，而在磁盘侧使用线程池支持的阻塞IO。对于Rust中事实上的异步IOruntime，两者都使用Tokio。
一个或多个种子，每个对应一个种子上载/下载。他们管理自己的同伴和跟踪者。
洪流有任意数量的对等会话，代表从头到尾与对等的连接。该实体实现BitTorrent有线协议，因此位于最低层。
磁盘IO由其自己的实体处理，以使关注点更加清晰和分离。
所有这些都是单独的任务（本质上是应用程序级别的绿线程）。因为从借用检查器的角度来看，任务区域可以作为单独的线程使用，所以如果没有同步，则不允许共享访问。有两种方法可以做到这一点。
任务之间的控制流主要通过使用多生产者单消费者通道的异步消息传递来实现。每个任务都是反应性的：它有一个事件循环，并且对其他任务的内部事件和消息做出反应。
洪流和对等会话会执行一次周期性的“滴答”（例如时钟滴答），当前每秒一次，以更新其内部状态和广播消息。这是在发送警报（例如定期下载统计信息或“下载完成”）时例如库用户。 7
循环{选择！ {//周期滴答_ = tick_timer.select_next_some（）=＆gt; {self.tick（）。等待吗？ } //想要连接的对等点peer_conn_result = entry.select_next_some（）=＆gt; {如果让Ok（socket）= peer_conn_result {self.handle_incoming_peer（socket）？; }} //来自引擎其他部分的命令cmd = self.cmd_rx.select_next_some（）=＆gt; {self.handle_cmd（cmd）。等待吗？ }}}
（select！是一个宏，它等待所有流并返回由第一个就绪流产生的项目。流只是最终随着时间的推移会产生值流的类型。）
就是这样。这种方法干净利落地分离了关注点，并使其轻而易举地扩展了代码。但是在极少数情况下，这不是最符合人体工程学的方法。
尽管大多数任务都与自己的数据有关，但是，torrent中的对等会话需要访问或突变torrent状态的一部分。
对于只读共享数据（占大多数），这是一个简单的弧线。但是对于共享的可变访问，这在我开始时还不清楚：我使用锁还是全通道往返？
更具体地说，对等会话需要始终与之交互的两个实体：
片段选择器：跟踪已下载的内容，所有会话都使用它来选择下一个要下载的片段。
分段下载：待处理的下载。它用于继续现有的下载并管理收到的块。
可以将它们保留在torrent中，并让对等会话使用消息来操纵它们，但是由于它们在许多地方都使用过，因此使用锁更直接。不过，从性能角度来看，哪一个是更好的整体解决方案？两者之间有巨大的差异，这会使选择一个显而易见的解决方案吗？
我不相信自己的直觉，因此我建立了一个综合基准来模拟这两种方法。尽管我不能完全代表现实世界，但我想有一个大概的想法来指导我的决定。
这很简单：生成指定数量的任务，让每个模拟对象一次“请求”一个块，在“接收”该块的同时将任务延迟一段时间，最后向主任务发送通知以进行管理。然后重复进行，直到“下载”所有片段。 （没有实际的networkIO发生，因此没有引号。）
如果将延迟设置为0，则左通道锁定在灰尘中。随着任务数量的增加，这种差异尤为明显。
但是令人惊讶的是，延迟只有10毫秒，结果甚至可以达到500个任务。
此后，即使设置了延迟，频道也开始取得胜利。因此，这里是一个收获（不仅限于Rust）：如果您需要非常高的并发性，那么消息传递是必经之路。 8
每个torrent的同行人数预计不会超过100。大多数客户将默认值设置为50。因此，如果此解决方案可以扩展到500左右，那么我认为对于MVP来说已经足够了。
实际上，还有一个模拟下载逻辑的方法并非易事：超时和抢救后期块。超出了解释范围，但这意味着在其他地方访问上述数据将使基于通道的解决方案更加复杂。
我会在一篇专门的文章中详细介绍一下，因为我觉得这很有趣。
我提到读写磁盘使用阻塞的IO。为什么不使用tokio :: fs（它提供了等效的标准lib库版本）？这需要一些解释……
尽管我尝试不进行过多的过早优化，但torrent客户端是性能至关重要的应用程序类型：除了实际下载内容外，第二重要的事情是它的速度要尽可能快。
与此相符，我做出了两个假设来做出决定，我认为这是明智的：
许多上下文切换（和系统调用）都很昂贵，并且由于近来的推测性执行缓解而变得更加复杂。尽可能使用批处理。
避免复制可能有很多的块缓冲区。复制许多16 KiBbuffer是不必要的。
这样，一块的下载块在写缓冲区中排队，并且仅在块完成后才写入磁盘。使用singlesyscall且没有其他缓冲区副本，而使用位置向量IO：pwritev，会发生这种情况。
该内核API允许通过一次原子操作在文件中给定位置写入字节缓冲区列表。 9无需查找，那里的noris可以分别写入每个块，或将缓冲区合并为单个缓冲区。 10
是开始之前我问自己的第一件事。我不确定如何最轻松地进行端到端集成和功能测试。
我的年轻孩子在这时第一次被击穿的原因是因为我没有进行适当的测试。我现在知道了。
由于我打算分步骤进行迭代，所以我知道我没有针对另一个cratetorrent实例测试cratetorrent所需的完整功能集（基本上需要MVP中提供的所有功能）。这是我所做的：
我使用Docker在我的本地主机上创建了一个虚拟LAN，可以在其中生成充当不同主机的容器。
我使用了一个知名的torrent客户端（传输），生成了一些实例作为种子，然后将其与我的cratetorrent客户端连接。
我在编写任何Rust代码之前进行了设置。一旦开始学习，实际上就测试了交换握手，发送协议消息，然后进行单独下载以及完全下载后不久的所有操作，这些操作都是毫不费力的。
这非常好用。它使我一次专注于一项功能，从而导致了快速迭代。例如，我在播种过程的后期添加了种子，但在此之前我已经能够测试完整的下载。
另一个好处是，即使所有内容都是本地的并且大部分都是可复制的，我仍在针对真实客户进行测试。这意味着它确保我的实施与生态系统的其余部分兼容。
如果您想知道所有设置如何，可以在此处查看。
没什么可写的（尽管可以说这正是我正在做的事情），但是如果没有任何微优化，只需进行少量分析，并且大多数情况下只有合理的架构决策，那么性能就非常好。
第一次运行时，饱和缓存的速度为160-20 MBps，第二次为270 MBps。
传输设置相同（关闭速率限制），最大速度为35 MBps！慢了4-7倍！但是我会在某个时候进行适当的摊牌。 :)
真！有一个板条箱（或库），以及一个非常贫乏的CLI应用程序。
由于上述对仅Linux的系统调用的使用，因此它目前仅在Linux上有效。 12
没有限制资源使用的设施（例如背压或速率限制），因此它可能不适用于速度较慢的系统。
还有很多事情要做：概要分析和优化，讨论基于cratetorrent和tokio的应用程序的其他有趣方面，以及许多功能等等。
另外，我在reddit上被问及当前的设计在理论上是否适合千兆吞吐量（125 MBps）。如上所述，似乎如此！但是在实践中不太可能：找到可以推动这些数字的种子，ISP的限制，网络硬件的缓慢运行等。但是我相信我可以进一步做到这一点-如前所述，代码尚未真正优化。千兆字节吞吐量如何？
如今，跟踪器已被分布式哈希表（DHT）或分布式数据存储所取代，DHT是一个分散的数据存储，在BitTorrent的情况下，该存储包含对等项和它们可用的种子。但即使如此，也需要在第一次运行时进行引导。 ↩︎
有趣的是，规范未指定16 KiB的大小，只是说这往往是所使用的值。如此之多，以至于不切实际的客户只能处理这些区块，并且可能会拒绝对不同大小的区块的请求。我不太确定为什么要精确设置为16KiB。在当今的互联网速度下，这个值似乎有点低端。大概是20年前BitTorrent创立时，它的选择是为了与互联网速度相匹配。 ↩︎
通常，同龄人会选择集群中最少可用的组件，以再次提高可用性。 ↩︎
真。经过一些测试，最后几段花费了整个下载时间的惊人30％！ ↩︎
滴答声每秒发生一次，因为不需要更频繁地发送统计信息，并且内部没有其他需要更频繁的滴答声了。顺便说一下，大多数客户端每秒或什至每隔几秒钟更新一次UI，因此几乎不需要做更多的工作。但是当然可能还有其他用例，因此将来可能会进行配置。 ↩︎
对于大量任务（支持通道），我们说的是150ms与25s之间的差异。但是，这并不令人惊讶：由于实际完成的工作很少，所以在没有延迟或任务数量很高的情况下，任务之间的大部分时间都花在争夺锁上。这无法扩展，因为任务多，CPU时间少，因为它们都需要处理相同的数据。更糟糕的是，每次更改时，CPU都必须同步其缓存，从而进一步降低程序速度。鉴于基于通道的解决方案，数据只能由一个CPU修改，因此不会发生缓存污染。而且通过通道发送消息非常便宜，因为根据通道的实现，它很可能使用无锁队列，这使它成为唯一CPU必须彼此同步的位置。 ↩︎
但是，内核API不能保证将所有缓冲区的全部内容写入磁盘。因此，大多数实现（包括cratetorrent）都会重复调用pwritev，直到写入所有字节为止。 ↩︎
也有Write :: write_all_vectored，但是它仍然需要查找，并且尽管在跨平台上，但在Windows上实际上只是重复调用Write :: write的填充程序，这比将块复制到单个缓冲区中和执行一次写操作（由于反复将上下文切换到内核空间而产生的累积成本）。 ↩︎
性能分析指向磁盘读取例程，其中preadv和__memset_avgx2__erms各自占用那里大约一半的CPU时间。 我怀疑这可能是什么，但我会再说一遍。 ↩︎ 将这些功能添加到Linux并在其他平台上使用不同的后备功能是相当容易的。 我不想使这个MVP复杂化，但是我可能很快就会这样做。 ↩︎ 例如。 您可以将此博客添加到RSS阅读器中，但我还将发布到reddit.com/r/rust和news.ycombinator.com。 ↩︎
