Rendezvous 哈希可以高效添加节点吗？
Wikipedia rendezvous哈希（
我看到Rendezvous Hashhing的唯一方法是使空语可作为缓存并由数据库支持。然后，如果一个节点没有对象，则可以从数据库中获取。同样，如果一个节点具有对象，但是该对象的键不再映射到该节点，则节点的高速缓存算法将驱逐它（通过LRU/LFU）。
我是否正确理解这一点？有没有办法解决此问题？
The wikipedia article for Rendezvous hashing (https://en.wikipedia.org/wiki/Rendezvous_hashing) doesn't explain what happens when you add a node to the hash table. The way I understand it, if you add a node to a hash table implemented via Rendezvous hashing, there may be objects in other nodes that should actually map to this new node since it's hash values for those objects are higher than the ones for the nodes those objects are currently in. In order to fix this problem, you would need to scan the entire hash table, recompute the hash values, and move objects if needed. This is extremely costly performance wise.
The only way I see rendezvous hashing making any sense is if the hashtable acts as a cache and is backed by a database. Then if a node doesn't have an object, it can be fetched from the database. Also, if a node has an object but the key for that object no longer maps to that node, the node's cache algorithm will evict it (through LRU/LFU).
Am I understanding this correctly? Is there a way to fix this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
好问题！维基百科文章实际上涉及该主题“如果一个对象已经在系统中......它将被重新获取并缓存”。
基本上，该算法的建议领域是您可以缓存值的情况，但稍后重新缓存它是可以的。虽然它确实需要额外的处理，但实现本身非常简单。这种方法的一个现实示例是 memcached - 它使用这种确切的方法，并且不关心您是否添加/删除节点 - 现有键不会发生重新哈希。
另一个有趣的注释是关于 Rendezvous 和一致性哈希的关系 - 一致性哈希旨在仅移动一些键，即映射到新分区的键。在 Rendezvous 哈希情况下，将移动相同数量的键；更好的是，平均每个现有节点都会放弃相同百分比的密钥 - 但这是以必须重新处理所有密钥为代价的。
Great question! The wikipedia article actually touches that topic "If an object already in the system at ... it will be fetched afresh and cached".
Basically, the proposed area for this algorithm is cases where you can cache a value, but it is ok to recache it later. While it does require extra processing, the implementation itself is dead simple. A real world example for this approach would be memcached - it uses this exact approach and does not care if you add/remove nodes - no rehashing is happening for existing keys.
Another interesting note is about relation of Rendezvous and Consistent Hashing - Consistent hashing aims to move only some keys, the ones which map into the new partition. In Rendezvous hashing case, the same number of keys will be moved; even better that every existing node on average will give away same percentage of keys - but this comes at a cost of all keys have to be reprocessed.
未必。您可以以懒惰的方式完成此操作：通过保持传统的哈希表，除了集合外，您知道是否已在系统中插入了键。
在这种情况下，如果确定对象在新节点上，但不存在，则必须在其他节点之一中，并且您可以以哈希分数的降低来寻找它。一旦找到，就可以将对象移至新节点。
Not necessarily. You can accomplish this in a lazy way: by maintaining a traditional hash table in addition to the rendezvous, you know if a key has been inserted in the system.
In that case, if an object is determined to be on the new node but isn’t there, then it must be in one of the other nodes, and you can look for it in decreasing order of hash scores. Once located, the object can be moved to the new node.