Gnutella 如何扩展以应对查询流量

# Gnutella 如何扩展以处理查询流量 来源：https://rickcarlino.com/notes/p2p/how-gnutella-scaled-to-handle-query-traffic.html \(这是我 Gnutella 探索系列的第二部分。如果你还不熟悉 Gnutella，请先阅读Gnutella 解释 (https://rickcarlino.com/notes/p2p/gnutella-explanation.html)一文。\) 在其巅峰时期，Limewire 安装在三分之一的台式计算机上 (https://www.eff.org/deeplinks/2007/12/limewire-1-3-desktops-world-wide)，而前一年的估算 (https://web.archive.org/web/20170810060540/http://barsoom.org/papers/gi-2006-long-term.pdf) 显示并发节点数达数百万。它在保持去中心化且无需全局文件索引或协调服务器的情况下达到了这一普及水平。更重要的是，尽管维护极少，该网络至今仍能存活。 早期版本的 Gnutella 使用一种称为**泛洪路由**的技术搜索网络。你的计算机向邻居发送查询。邻居再将其发送给它们的邻居。这个过程持续进行，直到查询的跳数耗尽或到达拥有匹配文件的机器。 泛洪路由极其简单，但对带宽使用产生了滚雪球效应。大部分收到查询的计算机并没有提供相关内容的可能。它们仍然必须接收消息、检查它、记住它，并将其转发出去。 在上一篇文章中，我描述 Gnutella 查询时，似乎它们只是简单地泛洪整个网络。这确实是事实，但为了保持文章简短，我有点撒谎了。 当 Gnutella 是一个只有几千用户的实验性网络时，泛洪路由还行得通。一旦网络达到主流普及程度，盲目打扰每一台可到达的计算机就不再可行了。根据我在互联网档案馆的考古挖掘，这种做法大概在 2003 年左右就结束了。 泛洪路由是我们为了推进解释而方便地讲述的一个半真半假的说法，就像我告诉我儿子 JavaScript 里的分号是可选的。 后来的 Gnutella 客户端（以及今天仍存活的那些）仍然通过一个对等节点网格传递查询，但它们更加有选择性地决定打扰哪些对等节点。它们在不需要中央文件索引，也不要求任何参与者透露确切共享文件列表的情况下做到这一点。 这个较新的搜索系统被称为**查询路由协议**，简称 QRP。 QRP 允许一台计算机发布其后端可用的搜索词的一个紧凑、近似的摘要。然后，一个对等节点可以在转发查询之前先问一个有用的问题：这个连接是否有任何可能通向匹配的文件？答案是两种之一：**可能**或**肯定没有**。 这个系统比第一代 Gnutella 客户端的泛洪路由系统更复杂，但它的扩展性很好。 ## 旧的路由系统 一个 Gnutella 查询从对等节点 A 经过对等节点 B 和 C，响应沿着相同的路径返回。 如果只有一个有效的实现，你很难真正称之为网络协议。那只是网络软件，而非协议。一个好的协议应该足够简单，以至于独立开发者能够实现它，而泛洪路由尽管效率低下，却达到了这个目标。 你可以把整个查询模型记在脑子里： 1. 向每一个连接的对等节点发送查询。 2. 减少其 TTL。 3. 让这些对等节点重复这个过程，直到 TTL 归零。 4. 使用查询的唯一标识符抑制重复查询。 5. 沿着记忆的逆向路径返回任何结果。 这种简单性让早期 Gnutella 拥有了多样化的客户端生态，更重要的是，人们确实在使用这个网络。然而，泛洪路由并非没有代价。 假设每个对等节点有四个连接。第一个对等节点可能会将查询转发给四个邻居。每个这样的邻居通常会排除查询来自的连接，因此一个树状的扩展将从 4 开始，然后扩展到 12、36、108，以此类推。 一个真实的网格包含环路、重复抑制以及连接数不同的对等节点，所以实际数字会有所不同。关键在于流量增长得非常快。 这些对等节点中的大多数不会拥有与搜索相关的内容，但它们必须接收消息、解析它、检查它、记住其标识符，并决定是否再次转发。 因此，网络大部分查询带宽都花费在证明对等节点没有请求的文件上。 当网络只包含几千台机器时，这是可以容忍的。当网络包含数百万台机器，且每个用户同时输入搜索时，这就变得代价高昂。 可扩展性问题最终通过那些明确做了数学计算的含科学内容 PDF (https://cs.rice.edu/%7Ealc/old/comp520/papers/ritter01gnutella-cant-scale.pdf) 得到了论证。 ## 叶子节点和超对等节点 早期的 Gnutella 是一个无差异化的对等节点网格。后来使用 QRP 的版本将节点分为两种角色： - **叶子节点**位于网络边缘。 - **超对等节点**参与高度连接的上层层级。 一个叶子节点连接到四个相互连接的超对等节点，每个超对等节点服务于一组额外的叶子节点。 这听起来可能像客户端-服务器架构，但没有永久性的服务器，也没有中央权威来决定谁能成为超对等节点。 一个超对等节点仍然是一个普通的 Gnutella 用户，运行着普通的 Gnutella 客户端。不同之处在于，超对等节点拥有足够的带宽、运行时间、内存和网络可达性来执行额外的路由工作。超对等节点通常是那些拥有 DSL 连接和配备 2 GB RAM 的高端 Windows 2000 机器的超级幸运的高级用户。 一些客户端会根据诸如运行时间、防火墙状态、可用内存、文件描述符和带宽等因素自动提升一个节点。 一个更普通的对等节点，如果处于拨号连接且位于防火墙之后，或者运行时间较短，则会作为叶子节点运行。 叶子节点为了冗余，与多个超对等节点保持连接。超对等节点与其他超对等节点保持连接，并接受其下的叶子节点集合。 ## 为什么是两层？ 一个超对等节点使用 QRP 表仅将查询转发给可能匹配的叶子节点 B 和 D，同时跳过叶子节点 C 和 E。 考虑一下叶子节点向超对等节点发送查询时会发生什么。 在纯泛洪路由下，超对等节点会将该查询发送给每一个其他连接的叶子节点，不管它们是否共享相关文件。 在 QRP 下，每个叶子节点会定期向超对等节点提供其当前文件库中所有单词的紧凑表示。这比仅仅上传一个文件名列表要复杂一些。这被称为 QRP 表，超对等节点为每个连接的叶子节点保存一个 QRP 表。 底层数据结构允许超对等节点将该索引视为一个函数，用于确定远程节点上的文件可用性。函数的输入是一个问题：**叶子节点 X 有文件 Y 吗？** 输出是**可能**或**肯定没有**。 当查询到达时，超对等节点会检查这些表。例如，如果查询是关于 `Ubuntu Server 2026 Live CD ISO`，超对等节点可能会确定叶子节点 E 和 C 肯定没有这个文件，但叶子节点 B 和 D **可能**有。因此，查询被发送给 B 和 D，而不是 C 或 E。 通过使用一个不透明的数据结构——一种**布隆过滤器** (https://en.wikipedia.org/wiki/Bloom_filter)——回答是/否问题远比将完整查询发送给每个叶子节点并等待大多数返回空结果要便宜得多。 QRP 主要应用于超对等节点网络的边缘。超对等节点将每个叶子节点接收到的 QRP 表分开存储。 每当一个关键词查询到达该超对等节点时，它会针对每个叶子节点的表检查该查询。匹配的表意味着该叶子节点可能有结果。不匹配的表意味着不应该发送该查询。 当超对等节点考虑将关键词查询转发给它的一个叶子节点时，就会发生这个检查。这是 QRP 最直接、最重要的用途。 QRP 表通常仅用于叶子节点到超对等节点的路由。它们通常不会创建整个网络的地图。一些节点支持一种称为**最后跳 QR P** 的功能，其中超对等节点创建一个所有连接叶子的合并摘要，以改善超对等节点间查询路由，但这是一个更复杂的问题。 ## 假阳性与假阴性 QRP 表是近似的。 **假阳性**发生在表显示一个对等节点连接可能匹配，但实际不存在匹配文件时。查询会沿着一个不必要的连接传递。一些带宽被浪费，但搜索仍然有效。 **假阴性**发生在表显示一个连接无法匹配，但实际存在结果时。查询被丢弃，用户永远看不到该文件。 假阳性浪费一点带宽，但假阴性隐藏了内容。 因此，QRP 的表格构建是保守的。它并不是要证明一个连接会产生结果。它只是尽力猜测，将查询路由到有用的端点。 让我们看看这些表实际上是如何工作的。 ## 前置知识：哈希函数 如果你已经知道什么是哈希函数，可以跳过这一节。 哈希函数接受一些输入，并确定性地将其转换为一个数字。 想象一个虚构的哈希函数，它产生一个从 0 到 999 的数字： `` hash("ubuntu") = 412 hash("server") = 731 hash("iso") = 044 `` 相同的输入总是产生相同的输出。 不同的输入通常会生成不同的输出，但并非总是如此。因为可能的单词比 0 到 999 的数字多得多，所以最终两个不相关的单词必定会产生相同的数字。这被称为**冲突**。 QRP 利用这个属性将单词转换为表的位置。 哈希不需要是加密安全的。我们不是保护密码或验证软件下载。我们只需要每个兼容的 Gnutella 客户端为同一个单词计算出相同的表位置。 ## 前置知识：类似布隆过滤器的概念 如果你已经理解布隆过滤器，也可以跳过这一节。 布隆过滤器是一个极其紧凑、近似的集合表示。它的主要操作是询问：**这个项在集合中吗？** 布隆过滤器可以用两种方式回答：**可能**和**肯定没有**。 它不能以 100% 的确定性可靠地回答，因为不相关的值可能会冲突并设置相同的位置。 QRP 表的感觉很像布隆过滤器，尽管它不完全符合教科书中定义的数据结构。 但有用的心智模型仍然是相同的：QRP 表是一个有损、压缩的搜索项集合。 如果一个必需的槽位缺失，则连接不可能匹配该词。如果槽位存在，则值得考虑该连接。 ## QRP 表中存储了什么？ 搜索词 Apple、Orange 和 Grape 被哈希到 QRP 表中的标记槽位。 由于 QRP 表不是一个文件列表，它不包含文字上的文件名或关于文件的信息。它只包含足够的信息来回答一个关于数据是否存在的 是/否 问题。 客户端首先将其共享文件的名称规范化为标记。这包括规范化文本——空格、大小写等——并将其分割成可搜索的单词。 一个名为： `Ubuntu Server 2026 Live CD.iso` 的文件可能贡献类似： `ubuntu` `server` `2026` `live` `cd` `iso` 的词项。 客户端不一定只插入完整的单词。 例如，一个长单词可能贡献概念上类似： `ubun` `bunt` `untu` 的形式，允许一些前缀搜索找到正确的路由，而无需插入每一个可能的子串。 每个索引形式被哈希到一个表位置： `` ubuntu → hash → 槽位 41,292 server → hash → 槽位 17,104 iso → hash → 槽位 52,881 `` 原始文本不存储在该槽位中。槽位只回答 是/否 问题，因此槽位更像一个检查清单。 重复的单词在查询匹配期间被去重，且长度小于三个字节的术语从 QRP 词向量中排除。 我使用一个包含大约 6300 个文件（文件名长度各异）的真实目录做了一个实验。以纯文本形式存储文件名需要大约 365 KiB。一个 QRP 表可以在远小于这个空间内总结这些文件名。 当压缩为每个槽位一个比特时，一个 65,536 槽位的表恰好占用 8 KiB。 表的大小选择为 2 的幂。 太小的表会变得拥挤。随着更多术语相互冲突，更多位置被标记为存在。最终，几乎每个查询看起来都匹配，表停止节省带宽。对等节点可以通过构建更大的表来响应。 ## QRP 表如何移动 四个 QRP 表合并为一个包含所有标记槽位的组合表。 一个叶子节点必须将其表发送给它连接的每个超对等节点。 每次添加或删除一个文件时都重新发送一个完全无关的结构是浪费的，因此 QRP 定义了两种重要的消息类型：**RESET** 和 **PATCH**。 RESET 消息指示一个对等节点丢弃当前与发送者关联的表，并准备一个特定大小的新空表。 RESET 建立了属性，例如新表中槽位的数量。 然后 PATCH 消息将该空表转换为发送者的当前状态。 未改变的条目以零或其他无操作值表示。由于大多数条目通常不会改变，这些长串的零在网络中压缩得非常好。 RESET 和 PATCH 消息是直接连接消息。它们不会在 Gnutella 网络中泛洪。 一个补丁序列可能被分割成多条消息，但接收者期望完成后的序列能够解释逻辑表中的每一个槽位。 ## 匹配查询与表 当搜索到达时，接收客户端执行大约与构建表时相同的规范化过程。 一个如： `ubuntu server iso` 的查询变成一个 QRP 索引词向量。 每个索引的词被哈希到一个表槽位。客户端检查这些槽位是否存在于与一个连接关联的表中。 显而易见的算法要求每个单词都出现： `` ubuntu = 存在 server = 存在 iso = 存在 `` 如果即使一个单词缺失，查询也不会被发送到那个连接。大多数客户端应用模糊匹配，在达到一定阈值时发送查询。 ## 额外功能：超对等节点间查询 我提到过，QRP 表用于叶子节点到超对等节点的通信。有时 QRP 表也可以用于超对等节点间的查询路由。 一个超对等节点可以从自己共享的文件以及符合条件的、直接连接的叶子节点提供的 QRP 表构建一个组合表。 超对等节点可以将这个组合表发送给那些宣传支持**最后跳 QRP** 的邻居超对等节点。 组合表表明超对等节点自己的文件或它直接连接的某个叶子节点可能匹配这些术语。重要的是要记住，这并不试图映射超对等节点直接连接的叶子节点之外的资源。 假设一个超对等节点正在考虑向一个邻居超对等节点发送查询。 如果查询还有多于一跳，超对等节点不会将邻居的 QRP 表作为硬性过滤器使用。邻居可能将查询进一步转发到网络中，超出其本地表所代表的文件。 如果查询恰好剩下一跳，情况就不同了。 邻居超对等节点无法将查询通过骨干网发送得更远。它所能做的就是检查自己的文件，并将查询转发给它的叶子节点。 这些正是其组合 QRP 表所代表的资源。 此时，负面的 QRP 匹配变得有用，因为它是确定