问题标签 [consistent-hashing]

我们有一个应用程序，Python 模块会将数据写入 redis 分片，而 Java 模块将从 redis 分片读取数据，因此我需要为 Java 和 Python 实现完全相同的一致哈希算法，以确保可以找到数据。

我用谷歌搜索并尝试了几种实现，但发现 Java 和 Python 的实现总是不同的，不能一起使用。需要你的帮助。

编辑，我尝试过的在线实现：
Java：http
://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html Python：http://techspot.zzzeek.org/2012/07/07 /the-absolutely-simplest-consistent-hashing-example/
http://amix.dk/blog/post/19367

编辑、附加 Java（使用 Google Guava lib）和我编写的 Python 代码。代码基于以上文章。

测试代码：

Python代码：

测试代码：

几年来，我一直在使用以下代码来处理对我们数据库表的查找。我们目前在 6 个主机上分片我们的表。查找代码为：

这种“算法”具有快速且非常随机的优点。但是，每当我向集群添加一个新节点时，重新平衡需要相当长的时间，因为似乎有不必要的表必须移动到不同的主机上。这不是一个大问题，因为我能够构建重新平衡脚本，因此在重新平衡发生时没有停机时间。相反，在它完成之前只有很小的性能损失。

我的问题是，是否还有其他算法可以在添加新主机时完成这种形式的一致散列而不需要大量的重新平衡？我正在继续研究这个主题，但我认为 Stack Overflow 会有一些聪明的解决方案，人们已经看到这些解决方案在生产中运行良好。

我们的项目需要一个分布式可扩展的 no-sql 数据库。为了安全起见，每个数据记录都必须存储在多个数据服务器（一个主服务器和一些从服务器）中。

我们希望系统能够动态地增加或减少服务器而不丢失任何数据记录。有没有相同的一致性哈希功能的算法？

假设我们有这样一个类：

现在，假设两个MyClass实例在它们的SomeValue属性相等时是相等的。因此，我覆盖了Object.Equals()和Object.GetHashCode()表示它的方法。Object.GetHashCode()返回SomeValue.GetHashCode()但同时我需要遵循以下规则：

1. 如果一个对象的两个实例相等，它们应该返回相同的哈希码。
2. 哈希码不应在整个运行时更改。

但显然，SomeValue可以改变，我们之前得到的哈希码可能会失效。

我只能考虑使该类不可变，但我想知道其他人在这种情况下会做什么。

在这种情况下你会怎么做？拥有这样一个类是否代表了设计决策中的一个更微妙的问题？

假设我一开始有两个 memcached 节点（节点 A，B），当我添加一个新节点 C时，部分键被重新映射，并且由于一致散列，只有其中一些键被重新映射。

让我们假设最初在服务器 A 的键为“ foo ”的值现在被映射到服务器 C。

当我最终删除节点 C 时，密钥应该再次映射到节点 A，但当时节点 A 仅包含陈旧数据。

那么，刷新数据是解决这个问题的唯一方法吗？

我不是在谈论分布式键/值系统，例如通常与 memcached 一起使用的，它使用一致的散列来使添加/删除节点成为一个相对便宜的过程。

我说的是你的标准内存哈希表，比如 python 的 dict 或 perl 的哈希。

通过降低调整哈希表大小的成本，使用一致散列的好处似乎也适用于这些标准数据结构。实时系统（和其他对延迟敏感的系统）将受益于/需要针对低成本增长优化的哈希表，即使整体吞吐量略有下降。

维基百科提到“增量调整大小”，但基本上是在谈论调整大小的热/冷替换方法；有一篇关于“可扩展散列”的单独文章使用 trie 进行存储桶查找来完成廉价的重新散列。

只是好奇是否有人听说过使用一致哈希来降低增长成本的核心单节点哈希表。还是使用其他方法（上面列出的两个维基百科位）更好地满足此要求？

或者......我的整个问题是否被误导了？内存分页考虑是否使复杂性不值得？也就是说，一致性哈希的额外间接性让您只重新哈希总键的一小部分，但这可能并不重要，因为您可能必须从每个现有页面中读取，因此内存延迟是您的主要因素，以及是否与内存访问的成本相比，您重新散列部分或全部键并不重要......但另一方面，通过一致的散列，您的所有键重映射都有相同的目标页面，所以会有与您的键重新映射到任何现有页面相比，内存抖动更少。

编辑：添加“数据结构”标签，澄清最后一句说“页面”而不是“桶”。

我想启用 memcached 一致性哈希。我看过 phpinfo(); 我可以看到以下内容 - 最后一行“memcached.sess_consistent_hash”：

是否应该将其设置为 1 以启用一致的散列，或者我是否会朝着错误的方向前进？我正在使用 spymemcached。有不同的方法可以做到这一点吗？

谢谢你

** 另外我该如何启用它 - 我在 php.ini 中找不到条目

给定一组静态目标，循环散列算法提供一致性。例如：

1. 我有一组初始目标，我们称它们A为B和C。
2. 我有钥匙，我们就叫它吧x
3. 我有一个循环哈希函数，我们称之为hash(key, targets)
4. 当我打电话时hash(x, [A,B,C])，x总是哈希到A

似乎足够明显。A我总是得到的事实x代表了我在使用循环哈希时所期望的一致性。但是，现在让我们考虑如果我添加一个新节点会发生什么D：

1. 我的目标集重新平衡以包括A、B、C和D
2. 我重新申请我的x钥匙hash(x, [A,B,C,D])
3. 因为圈子重新平衡了，我不能保证再A得到

我错过了什么还是我只是运气不好？当您开始重新排序节点（例如hash(x, [B,A,D,C])）或在现有节点列表的中间插入新节点（例如 ）时，问题会进一步恶化hash(x, [A,AA,B,C,D])。我对循环散列的学术方面进行了一些研究，这种类型的“缩放一致性”似乎并不是它的主要关注点之一。也许我只是使用了错误类型的哈希算法？

尝试横向扩展 Redis 实例作为Python-RQ.

据我所知，最好的方法是将分片逻辑（很可能使用Consistent Hashing）添加到自定义ConnectionPool和/或Connection类中。我宁愿为一致性哈希机制使用一个库——因为它似乎应该是可用的，并且很可能比本土解决方案更好/更久经考验。

做这样的事情有什么好的模式？是否有一些我应该研究的图书馆？有什么我应该考虑的遗漏吗？

非常感谢！

我想在 java 中设置 Memcache 值并通过 c 客户端获得相同的值。

是否可以用于多个 memcache 环境。两者都使用相同的哈希标准吗？