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