公平DHT的实施
Implementation of fair DHT
我正在考虑一种基础架构，其中许多用户连接到一台服务器，并使用哈希存储键值对。
存在许多这样的服务器，每个服务器都为自己的用户存储键值对。我们假设键不会冲突。
服务器 S1 上的用户 U1 可能会查找密钥为 K2 的对象，该对象位于服务器 S2 上（用户尚不知道）。我们需要某种分布式哈希 table 来将键映射到 server_addr，这样我们就可以在该服务器上查询该对象。
这样的DHT有很多，比如Tapesry，Chord等等，我一直在思考如何做一个这样公平的系统。
例如在三台服务器的系统中，一台服务器S1可能有1000个用户，S2有2个用户，S3有5个用户。如果我们假设用户每人创建 10 个对象，并且我们统一分配密钥-space，则服务器 S2 和 S3 将分别存储大约 3500 个密钥，这比他们自己消耗的密钥大一个或两个数量级。
我想要一种方法让 S1 对其在 DHT 中公平分配的密钥负责。
我的一个想法类似于审计系统，其中每个对等方询问其他人他们在 DHT 中存储了多少密钥，然后检查他们是否也对那部分密钥负责 space .
但是，这会导致大量的带宽使用来获取每个节点的消耗。
还有其他想法吗？
有几种可能的方法
什么都不做
在野外 DHT 并不是完全均匀的环境。一些节点比其他节点拥有更多资源（嵌入式设备与胖服务器）。有些节点比其他节点创建更多 activity。
节点可以根据其能力简单地提供服务（路由、存储），并在达到其容量后拒绝请求（通过丢弃它们或返回否定响应）。
发出请求的节点将简单地将它们视为故障并绕过故障点。
您基本上应该检查节点消耗的资源比其他节点多几个数量级的情况是否常见到足以保证任何平衡。
自愿措施
导致更多流量的节点可能只是为了提供更多资源而设计的。例如。它可以 运行 多个虚拟节点分散在整个密钥空间中，从而为更多密钥提供存储和路由。
对于具有高正常运行时间、带宽和低延迟的服务器-class 机器来说，这应该特别容易。
执法
这就是它变得棘手的地方。在分布式系统中，您没有信任或监管机构。在您提供服务其请求之前，节点必须证明它提供了足够的服务。
第一个明显的措施是其他节点保证它确实提供了它声称的服务。但这仅提供了它提供某些服务的证据，并没有说明提供资源和消耗资源之间的比率。而且您还需要一种机制来验证它确实存储了它声称的数据，而不仅仅是返回肯定的响应然后丢弃它们。
所以你需要会计、验证和信任网络，因为单程凭证可能不够用。
如您所见，复杂性迅速爆炸。
您可能应该放眼大局，确定网络中的攻击者和好公民可能拥有的激励措施。
- 消耗过多的资源有什么好处
- 验证成本是多少（复杂性、人力、与阻止的恶意流量相关的流量开销）
- 离群值会造成多大的负担？
等等
我正在考虑一种基础架构，其中许多用户连接到一台服务器，并使用哈希存储键值对。
存在许多这样的服务器，每个服务器都为自己的用户存储键值对。我们假设键不会冲突。
服务器 S1 上的用户 U1 可能会查找密钥为 K2 的对象，该对象位于服务器 S2 上（用户尚不知道）。我们需要某种分布式哈希 table 来将键映射到 server_addr，这样我们就可以在该服务器上查询该对象。
这样的DHT有很多，比如Tapesry，Chord等等，我一直在思考如何做一个这样公平的系统。
例如在三台服务器的系统中，一台服务器S1可能有1000个用户，S2有2个用户，S3有5个用户。如果我们假设用户每人创建 10 个对象，并且我们统一分配密钥-space，则服务器 S2 和 S3 将分别存储大约 3500 个密钥，这比他们自己消耗的密钥大一个或两个数量级。
我想要一种方法让 S1 对其在 DHT 中公平分配的密钥负责。
我的一个想法类似于审计系统，其中每个对等方询问其他人他们在 DHT 中存储了多少密钥，然后检查他们是否也对那部分密钥负责 space .
但是，这会导致大量的带宽使用来获取每个节点的消耗。
还有其他想法吗？
有几种可能的方法
什么都不做
在野外 DHT 并不是完全均匀的环境。一些节点比其他节点拥有更多资源（嵌入式设备与胖服务器）。有些节点比其他节点创建更多 activity。
节点可以根据其能力简单地提供服务（路由、存储），并在达到其容量后拒绝请求（通过丢弃它们或返回否定响应）。
发出请求的节点将简单地将它们视为故障并绕过故障点。
您基本上应该检查节点消耗的资源比其他节点多几个数量级的情况是否常见到足以保证任何平衡。
自愿措施
导致更多流量的节点可能只是为了提供更多资源而设计的。例如。它可以 运行 多个虚拟节点分散在整个密钥空间中，从而为更多密钥提供存储和路由。
对于具有高正常运行时间、带宽和低延迟的服务器-class 机器来说，这应该特别容易。
执法
这就是它变得棘手的地方。在分布式系统中，您没有信任或监管机构。在您提供服务其请求之前，节点必须证明它提供了足够的服务。
第一个明显的措施是其他节点保证它确实提供了它声称的服务。但这仅提供了它提供某些服务的证据，并没有说明提供资源和消耗资源之间的比率。而且您还需要一种机制来验证它确实存储了它声称的数据，而不仅仅是返回肯定的响应然后丢弃它们。
所以你需要会计、验证和信任网络，因为单程凭证可能不够用。
如您所见，复杂性迅速爆炸。
您可能应该放眼大局，确定网络中的攻击者和好公民可能拥有的激励措施。
- 消耗过多的资源有什么好处
- 验证成本是多少（复杂性、人力、与阻止的恶意流量相关的流量开销）
- 离群值会造成多大的负担？
等等