为什么在chord p2p系统中，手指table不存储所有其他节点的信息？
Why in chord p2p system, the finger table don't store all the information about the other nodes?
我正在学习和弦系统。但我对它的查询算法有疑问。为什么chord中的手指table只存储了successor(n+2^{i-1})的信息，而没有存储环中所有其他节点的信息？就像这张图，
如果我要在节点1上查找key 7，如果节点1存储了环上所有节点的地址，既然我们明明知道7的后继是0，那我们就可以直接找0了，为什么要先去6号节点，用6号节点路由到0，我有点懵
为了可扩展性。想象一下，环中有 10,000,000 个节点。跟踪所有这些变得非常困难（由于内存限制以及信号和处理节点所需的通信工作 joins/leaves）。
相反，您可以利用节点 ID 在环中排序的事实。然后您可以使用它们来避免必须对整个环进行线性搜索。例如：在节点 0 中，您仅存储有关 9 个节点的信息（假设 ID 从 0 到 10,000,000）：1,000,000、2,000,000、3,000,000、...和 9,000,000。然后如果你想到达一个随机节点，比如 1,337,000，你只需要在 1,000,000 到 2,000,000 之间搜索。因此，通过存储有关 9 个节点的信息，您将工作量减少了 10 倍。
但你可以做得更好。如果节点 1,000,000、1,000,001 等使用快捷方式，就像节点 0 一样，彼此间隔 1,000,000，从 1,000,000 到 1,337,000 仍然需要大量工作（337,000 步）。如果从节点 0 开始有 9 个间隔为 1M 的快捷方式，然后从节点 1M 到 2M 也有 9 个间隔为 100k 的快捷方式不是很好吗？那么你将不得不在 1,300,000 到 1,400,000 段中进行查找。
您可以更进一步，让每个节点以 10k 的间隔为其后的节点维护 9 个快捷方式，并以 1k 的间隔维护另外 9 个快捷方式等。
因此，总而言之，查找将像这样工作：
- 我们向节点 0 询问来自节点 1,337,000 的信息。
- 节点0不知道如何直接到达节点1,337,000，但它知道如何到达1,000,000和2,000,000。 1,000,000 是最接近的，因此它将查询发送到那里。
- 节点 1,000,000 不知道如何直接到达节点 1,337,000，但它知道如何到达 1,100,000、1,200,000、1,300,000 等。节点 1,300,000 是最近的节点，因此它将查询发送到那里。
- 节点 1,300,000 不知道如何直接到达节点 1,337,000，但它知道如何到达 1,310,000、1,320,000、1,330,000 等。因此它将查询发送到 1,330,000。
- 节点 1,330,000 知道如何达到 1,337,000，因为它在它的手指中 table（它知道如何达到 1,331,000、1,332,000、1,333,000 等）
所以你只用了4个步骤就得到了回复。让我们看看您的手指 table 需要多少存储空间。
任何具有 id n 的节点都需要存储以下信息：
- 9个节点，间隔1M，从n开始；
- 9个节点，间隔100k，从n开始；
- 9个节点，间隔10k，从n开始；
- 9个节点，间隔1k，从n开始；
- 9个节点，间隔100，从n开始；
- 9个节点，间隔10，从n开始，到此为止。
所以每个节点只需要存储其他54个节点的信息。在最坏的情况下，您将需要 6 + 9 = 15 次查找才能到达一个节点。这比没有手指 tables.
所需的 10M-1 查找要好得多
Chord 使用基数 2 而不是基数 10 来划分环。因此，您在论文中看到的是 2 而不是 10 的幂。
我不记得这是否正是 Chord 的工作方式；但这是相同的想法。分布式二进制搜索。
我正在学习和弦系统。但我对它的查询算法有疑问。为什么chord中的手指table只存储了successor(n+2^{i-1})的信息，而没有存储环中所有其他节点的信息？就像这张图，
如果我要在节点1上查找key 7，如果节点1存储了环上所有节点的地址，既然我们明明知道7的后继是0，那我们就可以直接找0了，为什么要先去6号节点，用6号节点路由到0，我有点懵
为了可扩展性。想象一下，环中有 10,000,000 个节点。跟踪所有这些变得非常困难（由于内存限制以及信号和处理节点所需的通信工作 joins/leaves）。
相反，您可以利用节点 ID 在环中排序的事实。然后您可以使用它们来避免必须对整个环进行线性搜索。例如：在节点 0 中，您仅存储有关 9 个节点的信息（假设 ID 从 0 到 10,000,000）：1,000,000、2,000,000、3,000,000、...和 9,000,000。然后如果你想到达一个随机节点，比如 1,337,000，你只需要在 1,000,000 到 2,000,000 之间搜索。因此，通过存储有关 9 个节点的信息，您将工作量减少了 10 倍。
但你可以做得更好。如果节点 1,000,000、1,000,001 等使用快捷方式，就像节点 0 一样，彼此间隔 1,000,000，从 1,000,000 到 1,337,000 仍然需要大量工作（337,000 步）。如果从节点 0 开始有 9 个间隔为 1M 的快捷方式，然后从节点 1M 到 2M 也有 9 个间隔为 100k 的快捷方式不是很好吗？那么你将不得不在 1,300,000 到 1,400,000 段中进行查找。
您可以更进一步，让每个节点以 10k 的间隔为其后的节点维护 9 个快捷方式，并以 1k 的间隔维护另外 9 个快捷方式等。
因此，总而言之，查找将像这样工作：
- 我们向节点 0 询问来自节点 1,337,000 的信息。
- 节点0不知道如何直接到达节点1,337,000，但它知道如何到达1,000,000和2,000,000。 1,000,000 是最接近的，因此它将查询发送到那里。
- 节点 1,000,000 不知道如何直接到达节点 1,337,000，但它知道如何到达 1,100,000、1,200,000、1,300,000 等。节点 1,300,000 是最近的节点，因此它将查询发送到那里。
- 节点 1,300,000 不知道如何直接到达节点 1,337,000，但它知道如何到达 1,310,000、1,320,000、1,330,000 等。因此它将查询发送到 1,330,000。
- 节点 1,330,000 知道如何达到 1,337,000，因为它在它的手指中 table（它知道如何达到 1,331,000、1,332,000、1,333,000 等）
所以你只用了4个步骤就得到了回复。让我们看看您的手指 table 需要多少存储空间。
任何具有 id n 的节点都需要存储以下信息：
- 9个节点，间隔1M，从n开始；
- 9个节点，间隔100k，从n开始；
- 9个节点，间隔10k，从n开始；
- 9个节点，间隔1k，从n开始；
- 9个节点，间隔100，从n开始；
- 9个节点，间隔10，从n开始，到此为止。
所以每个节点只需要存储其他54个节点的信息。在最坏的情况下，您将需要 6 + 9 = 15 次查找才能到达一个节点。这比没有手指 tables.
所需的 10M-1 查找要好得多Chord 使用基数 2 而不是基数 10 来划分环。因此，您在论文中看到的是 2 而不是 10 的幂。
我不记得这是否正是 Chord 的工作方式；但这是相同的想法。分布式二进制搜索。