我正在实现一个完全分散的数据库。任何人都可以随时向其上传任何类型的数据。适合这个问题的一个很好的解决方案是不可变的分布式哈希表。值是用它们的散列键控的。不变性确保此映射始终有效，简化数据完整性检查并避免同步。
为了提供一些数据检索设施，将实施基于标签的分类。任何键（与单个唯一值相关联）都可以用任意标签（任意字节序列）进行标记。为了简单起见，我想使用相同的分布式哈希表来存储这个标签哈希索引。
为了实现这个数据库，我需要一些方法来维持对什么是实际有效的标签哈希索引的去中心化共识。不变性迫使我使用某种链接数据结构。我怎样才能找到根？如何同步条目添加？如何确保每个人都有一个共享根？
在分布式哈希表中，您可以将节点构建在一个环中，其中环中的每个节点都知道环中的至少一个其他节点（以保持连接）。为了使环更具容错性，请确保每个节点都了解环中多个其他节点，以便在某个节点崩溃时仍能够连接。在 DHT 术语中，这称为“继任者列表”。当节点在具有唯一 ID 和一些稳定协议的环中构建时，您可以通过环路由来查找负责某个密钥的节点。
如何同步条目添加？
如果你不想要复制，去中心化共识的弱版本就足够了，那就是每个节点都有自己的唯一 ID，并且他们知道环结构，这可以通过周期性稳定协议来实现，就像在 Chord 中一样：http ://nms.lcs.mit.edu/papers/chord.pdf
稳定协议让每个节点定期与其后继节点通信，以查看它是否是环中的真正后继节点，或者新节点是否已加入环中，或者后继节点已崩溃并且必须更新环。由于不使用复制，因此要进行一致的插入，环是稳定的就足够了，这样对等方就可以将插入路由到将其插入其存储的正确节点。每个项目仅由 DHT 中的单个节点持有，无需复制。
这个稳定过程可以给你很好的概率，环总是稳定的，你最小化不一致性，但它不能保证强一致性，当节点加入或离开时，环可能会暂时不稳定。在不一致期间，可能会发生数据丢失、重复、覆盖等。
如果您的应用程序需要强一致性，DHT 并不是最好的架构，在 DHT 中实现这种一致性将非常复杂。首先，您需要复制，您还需要在稳定协议中添加大量 ACK 和同步，例如为每次插入使用 2PC 协议或 paxos 协议，以确保每个副本都获得新值。
我怎样才能找到根？如何确保每个人都有一个共享根？
通常，DHT 与一些查找服务（集中式）相关联，其中包含节点的 IP/ID 和服务中的新节点注册。该服务还可以确保每个新节点都获得一个唯一的 ID。由于此服务仅管理 ID 和简单查找，因此它不会承受任何高负载或崩溃风险，因此在不损害容错性的情况下将其集中是“可以的”，但当然您也可以分发查找服务，并进行同步他们使用像 Paxos 这样的共识协议。