实施公平的DHT

Question

我正在考虑一种基础设施，其中许多用户连接到一台服务器，并使用哈希存储密钥-值对。

许多这样的服务器存在，每个服务器都为自己的用户存储密钥-值对。我们假设钥匙不会碰撞。

服务器S1上的用户S1可以使用键K2查找对象，该对象位于服务器S2上(用户还不知道这一点)。我们需要某种类型的分布式哈希表来将密钥映射到server_addr，这样我们就可以查询服务器中的对象。

有许多这样的DHT，如磁带，和弦等。我一直在考虑如何使这样一个系统公平。

例如，在有三个服务器的系统中，服务器S1可能有1000个用户，S2有2个用户，S3有5个用户。如果我们假设用户每个创建10个对象，并且均匀地分配密钥空间，服务器S2和S3将分别存储大约3500个密钥，这比他们自己的密钥消耗大一个数量级或两个数量级。

我希望S1能够为它在DHT中的公平份额承担责任。

我的一个想法是类似于审计系统，每个对等点都会询问其他每个人他们在DHT中存储了多少密钥，然后检查他们是否也对密钥空间的那一部分负责。

然而，这导致了大量的带宽使用，以获得每个节点的消耗。

还有其他想法吗？

Answer 1

有几种可能的方法

什么也不做

在野外，DHT并不是完全同质的环境。有些节点比其他节点拥有更多的资源(嵌入式设备与fat服务器)。有些节点比其他节点创建更多的活动。

节点可以根据其能力简单地呈现服务(路由、存储)，并在达到其容量后拒绝请求(通过删除请求或返回负面响应)。

发出请求的节点将简单地将它们视为故障，并在故障点周围路由。

基本上，您应该检查节点消耗的资源比其他节点多几个数量级的情况是否足够普遍，足以保证任何平衡。

自愿措施

导致更多通信量的节点可以设计为提供更多的资源。例如，它可以运行分散在密钥空间中的多个虚拟节点，从而为更多密钥提供存储和路由。

对于具有高正常运行时间、带宽和低延迟的服务器类计算机来说，这尤其容易.

强制执行

这才是棘手的地方。在分布式系统中，您没有信任或管理权限。节点在提供服务请求之前必须证明它提供了足够的服务。

第一个明显的措施是其他节点，证明它确实提供了它声称的服务。但这只是提供了一些服务的证据，并没有提到提供的资源和消耗的资源之间的比率。您还需要一种机制来验证它确实存储了它声称的数据，而不仅仅是返回积极的响应，然后丢弃它们。

因此，你需要会计、核实和信任网络，因为一跳代金券可能是不够的。

正如你所看到的，复杂性迅速爆炸。

您可能应该考虑更大的情况，并确定攻击者和您的网络中的优秀公民可能具有的激励措施。

• 过度消耗资源有什么好处？
• 验证的成本是多少(复杂性、人为努力、与恶意通信相比的通信开销)？
• 异常值会造成多大的负担？

等。