kitsune_dht

DHT子库，用于kitsune-p2p。

此库定义了“量化DHT”、其中存在的对象以及这些对象上的操作。

kitsune_p2p_dht_arc 库最终可能被整合到这个库中。

许可证：Apache-2.0

lib.rs:

定义了DHT的结构、其中存在的对象以及这些对象上的操作。

DHT的结构和内容

DHT由代理和操作组成。代理将新的操作引入DHT，并负责存储自己的操作和其他代理的操作。

每个代理都有一个固定位置，每个操作都有一个固定位置和固定时间戳。

位置是一维的，最好将其视为圆圈上的位置。它们由一个表示自UNIX纪元以来微秒数的i64表示。位置维度是圆形的，时间维度是线性的。

每个代理都有一个弧，该弧标记出位置圆圈的一部分。弧有一个固定的起点，并随时间“顺时针”扩展一定长度，这个长度由Kitsune选择并随时间变化。每个代理负责持有任何与自己的弧重叠位置的操作。正如我们稍后将会看到的，弧是“量化”的。

几何解释

此库大量使用了二维圆柱形“时空”表面的概念——这个库中的所有术语都是基于这个模型构建的，所以在这里稍作解释。

如果我们把位置看作一个空间维度，把时间看作一个时间维度，那么我们可以把DHT看作是一个二维的时空。

位置维度是环形的，即端点是相连的，但时间维度是线性的且不断扩展。因此，这两个维度形成了一个圆柱面，其底部在网络的初始时间，随着时间向前推移，高度不断增大。

因此

• 一个Op可以看作是在这个圆柱面某个位置的一个点，
• 一个Agent可以看作是垂直于底面的一条线，横跨整个圆柱的长度。
• 一个Arc可以看作是由Agent线扫过Arc长度指定的距离所形成的矩形“条带”。
• 区域是时空的一个任意矩形区域。

量子化

这个DHT空间的一个关键特征是它在两个维度上都是量子化的。你可以把它想象成一个覆盖时空的网格，这会将Agent和Op分组到由网格单元指定的桶中。另一种思考方式是我们只通过它们出现在哪个网格单元来引用项，而不是通过它们的绝对坐标。

拓扑和量子坐标

量子化由一个称为2^p的参数指定。这个结构定义了如何将量子化网格覆盖到时空上，并指定了如何将“绝对”坐标（位置和时间戳）转换为“量子”坐标（网格单元）。

每个Kitsune空间可以自由选择自己的拓扑（并且该空间中的所有节点都必须同意使用相同的拓扑）。然而，在实践中，我们目前为所有空间使用相同的拓扑。

• 标准空间量子大小为2^12
• 标准时间量子大小为5分钟

此外，我们在拓扑中包含了一个“时间原点”组件，它描述了量子化网格时间维度原点的时间偏移。换句话说，时间原点指定了哪个时间戳对应于网格时间维度的原点坐标。

为了术语，我们把这些矩形网格单元称为时空量子。这些矩形的边是空间量子和时间量子。

段（块）和对数坐标（待定）

为了我们的Gossip算法，我们用“段”或“块”来指定Arc。段是一组连续的量子，数量为2^p，其中p是一个整数。因此，段总是量子大小的2的幂次倍数。此外，从原点的偏移量也必须是2的幂次。因此，所有可能的段集合暗示了一个由量子网格层叠的均匀网格集合，每个网格比下面的网格粗两倍。

因此，我们可以用一个单独的整数来引用量化粗化的连续级别，这被称为“幂”，因为它具有2^p的形式。0次幂指的是量子网格本身。1次幂是两倍粗，依此类推。

Arc由同一幂的连续段集合指定。

量子化Gossip

对时空进行这种详细的量子化的原因是为了有效地实现历史上的Agent之间的Gossip。每个Agent都有自己的Arc，表示它负责存储和传播给其他Agent的Ops。当两个Agent进行Gossip时，他们必须迅速有效地确定他们已经共有的Ops以及他们需要互相发送的Ops。

这是通过代理交换他们共同拥有的时空区域的情报来实现的。这需要最小程度的协调，这也是为什么我们使用时空的统一量化——如果将时空分割成区域的方式有限，那么代理更有可能拥有关于确切相同区域的情报。

具体来说，当代理八卦时，他们会与对方交换他们共同拥有的每个区域的“指纹”，对于指纹不匹配的区域，每个代理都会将那个区域的所有操作发送给对方。对于匹配的区域，双方都理解他们在那些区域持有相同的数据，不需要在这些区域上进行进一步的八卦。因此，将时空分割成区域的方式很重要，当区域指纹出现不匹配时，它们只涉及少量的数据；或者如果它们涉及大量数据，那么不匹配应该是罕见的。同时，我们不想分割成太多区域，因为这会导致更大的开销而收益最小。

时空量化

每个代理根据其对网络条件的观察为其弧选择一个功率级别。理想情况下，每个代理看到相似的网络视图，并选择与其他附近代理相同的功率级别。当功率级别匹配时，两个代理以相同的粒度跟踪空间，可以更容易地协调。在功率级别不同的情况下，其中一个代理必须进行一些额外计算来调和差异。

不深入细节的话，功率级别主要是一个函数，表示附近有多少其他代理。代理开始时使用高功率级别，用一个粗略分割的弧覆盖DHT的大片区域，随着更多代理的加入，他们降低功率级别，拥有更小的片段，并以更细的分辨率跟踪操作。

使用标准的弧大小调整参数，可以保证代理的弧始终包含8到15个片段。

时间量化

还需要考虑时间维度。代理根据周围的其他人划分空间。他们对时间的划分方式不同，也更为简单：特定时间越老，它将成为更大时间片段的一部分。这样做的原因是，老数据经历的变化远少于新数据，因此，两个代理之间老区域相似的可能性非常大，因此他们可以在比新数据更大的区域中比较老数据，新数据预计会经历更频繁的变化。

这也具有一个很好的特性，即我们使用的时间片段的数量只以对数方式随着时间的流逝而增加，因为老区域在时间维度上是新区域的两倍长。

由于弧中的空间片段数量具有恒定的上限和下限，而时间片段的数量以对数方式增加，因此随着网络的扩大，协调的总开销只以对数方式增加。因此，即使长期存在的网络也能有效地进行历史八卦。