我正在研究在我正在编写的一些java代码中使用一致的哈希算法.番石榴哈希库有一个consistentHash(HashCode, int)方法,但文档相当缺乏.我最初的希望是,我可以使用consistentHash()简单的会话亲和性来有效地在一组后端服务器上分配负载.

有没有人有一个如何使用这种方法的现实世界的例子？特别是我关心的是管理从目标范围中移除铲斗.

例如:

@Test
public void testConsistentHash() {
    List<String> servers = Lists.newArrayList("server1", "server2", "server3", "server4", "server5");

    int bucket = Hashing.consistentHash(Hashing.md5().hashString("someId"), servers.size());
    System.out.println("First time routed to: " + servers.get(bucket));

    // one of the back end servers is removed from the (middle of the) pool
    servers.remove(1);

    bucket = Hashing.consistentHash(Hashing.md5().hashString("blah"), servers.size());
    System.out.println("Second time routed to: " + servers.get(bucket));
}

导致输出:

First time routed to: server4
Second time routed to: server5

我想要的是在清除列表中较早的服务器之后将该标识符("someId")映射到同一服务器.所以在上面的示例中,删除后我想我想要桶0映射到"server1",桶1映射到"server3",桶2映射到"server4",桶3映射到"server5".

我是否应该维护一个单独的(比列表更复杂)数据结构来管理存储桶删除和添加？我想我可能已经设想了一个更复杂的Hashing API,可以在为我添加和删除特定存储桶后管理重新映射.

注意: …

网上有很多关于一致性散列的信息,以及可用的多种语言的实现.该主题的Wikipedia条目引用了具有相同目标的另一种算法:

会合哈希

该算法看起来更简单,并且不需要在环周围添加复制品/虚拟来处理不均匀的加载问题.正如文章所提到的,它似乎在O(n)中运行,这对于大n来说是一个问题,但引用一篇文章说明它可以被构造为在O(log n)中运行.

对于在这方面有经验的人来说,我的问题是,为什么人们会选择一致的哈希而不是HRW,反之亦然？是否存在其中一种解决方案是更好的选择的用例？

非常感谢.

我一直在努力用PHP来理解和编写Memcache,但我在几点上感到困惑.我已经阅读了很多文章,几乎所有与此相关的SO问题都找不到确切的答案.

1)在PHP中创建Consistent Hashed Key的代码是什么？我必须安装哪些库以及我真正需要做什么？有什么好文章要经历吗？

2)假设,我已经成功存储了一致的哈希密钥,现在如果我的任何服务器关闭或添加了新的服务器,即使我使用的是一致的哈希密钥等,它会有什么不同吗？

3)如果在http://ru.php.net/manual/en/memcached.addserver.php中说明,使用Memcached :: addServers()而不是Memcached :: addServer()会对Consistent Hashing产生任何影响.那不是什么意思？

$m = new Memcached();
$m->setOption(Memcached::OPT_DISTRIBUTION, Memcached::DISTRIBUTION_CONSISTENT);
$m->addServers($servers);

4)使用上面的代码是否足以进行Consistent Hashing,然后添加/删除服务器对密钥没有任何影响？

5)什么是Ketama图书馆？如果Memcached :: DISTRIBUTION_CONSISTENT可以更好地工作,为什么要使用它？关注http://www.last.fm/user/RJ/journal/2007/04/10/rz_libketama_-_a_consistent_hashing_algo_for_memcache_clients

6)我是否必须以某种方式哈希我的密钥或只提供我的密钥并让Memcached处理剩下的事情？

请大家,我需要您真正的支持,以便尽快了解并实施我的生产环境.你的答案让我明白我应该为什么编码更好.

故事

我有3个memcached服务器运行,我关闭其中一个,以调查PHP-memcached在服务器无法访问时的行为方式.

我在PHP中定义了4个服务器,1个用于模拟大部分离线的服务器(备用服务器).当我关闭1台服务器(=> 2仍在线)时,第三台->get()给我一个结果.

当我再关闭一台服务器(=> 1仍在线)时,它将找不到推送到最后一台服务器的对象.

样本输出

首次运行,4台服务器中的3台:

Entity not found in cache on 1st try: NOT FOUND
Entity not found in cache on 2nd try: NOT FOUND
Entity not found in cache on 3rd try: NOT FOUND
Entity not found in cache on 4th try: NOT FOUND

第二次运行,4台服务器中的3台:

Entity found in Cache: SUCCESS

第三次运行,4台服务器中的2台:

Entity not found in cache on 1st try: CONNECTION FAILURE
Entity not found in cache on 2nd try: SERVER IS MARKED DEAD
Entity …

我遇到MessageDigest在不同计算机上返回不同哈希值的问题.

一台计算机在Windows Vista上运行32位Java,另一台在Mac OS上运行64位Java.我不确定是不是因为MessageDigest是依赖于机器的,或者我需要在某处明确指定字符编码,或者可能是其他东西.这是代码:

public static boolean authenticate(String salt, String encryptedPassword, 
    char[] plainTextPassword ) throws NoSuchAlgorithmException {

    // do I need to explcitly specify character encoding here? -->
    String saltPlusPlainTextPassword = salt + new String(plainTextPassword);

    MessageDigest sha = MessageDigest.getInstance("SHA-512");

    // is this machine dependent? -->
    sha.update(saltPlusPlainTextPassword.getBytes());
    byte[] hashedByteArray = sha.digest();

    // or... perhaps theres a translation problem here? -->
    String hashed = new String(hashedByteArray);

    return hashed.equals(encryptedPassword);
}

这些代码应该在这两台不同的机器上执 如果它与我编写它的方式是机器相关的,那么还有另一种方法来散列这些更便携的密码吗？谢谢!

编辑:::::

这是我用来生成盐的代码:

public static String getSalt() {
   int size = 16; …

我们有一个应用程序,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/ - 绝对最简单 - 一致 - 散列 - 示例/
http://amix.dk/blog/post/19367

编辑,附加Java(使用Google Guava lib)和我编写的Python代码.代码基于上述文章.

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;
import com.google.common.hash.HashFunction;

public class ConsistentHash<T> {
    private final HashFunction hashFunction;
    private final int numberOfReplicas;
    private final SortedMap<Long, T> circle = new TreeMap<Long, T>();

    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
            Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;

        for (T node : nodes) {
            add(node);
        }
    }

    public void add(T node) { …

要求在给定 Kafka 主题的同一分区中进行排序是很常见的。也就是说，具有相同密钥的消息应该发送到相同的分区。现在，如果我想在正在运行的主题中添加新分区，如何制作并保持一致性？

据我了解，默认的分区策略是对 num-of-partition 进行 mod 。当分区数量改变时（例如4到5），一些消息可能会落入与之前具有相同键的消息不同的分区中。

我可以想象实现一致的散列来定制分区行为，但这可能会造成干扰。

或者，停止所有生产者，直到所有消息被消耗完；然后部署新分区并重新启动所有生产者。

还有更好的想法吗？

我对一致性哈希的理解是，您采用一个密钥空间，对密钥进行哈希处理，然后按 360 进行取模，然后将值放入一个环中。然后，在该环上均匀分布节点。您可以通过从散列密钥所在的位置顺时针查看来选择处理该密钥的节点。

然后在许多解释中他们继续描述Vnode。在引用 dynamo 论文的riak 文档中，他们说：

The basic consistent hashing algorithm presents some challenges. First, the random position assignment of each node on the ring leads to non-uniform data and load distribution.

然后他们继续提出 Vnodes 作为确保输入密钥空间在环周围均匀分布的一种方法。据我了解，要点是 Vnode 划分范围的次数比机器多得多。假设您有 10 台机器，则可能有 100 个 Vnode，并且单个机器的 Vnode 将随机分散在环周围。

现在我的问题是为什么需要这个额外的 Vnode 步骤。哈希函数应该提供其输出的均匀分布，因此这似乎是不必要的。根据这个答案，即使哈希函数的模仍然是均匀分布的。

我有一个生产者,我想通过一致的散列在消费者中一致地分配工作.例如,对于消费者节点X和Y,任务A,B,C应始终转到消费者X,而D,E,F应转到消费者Y.但如果Z加入消费者池,则可能会转移一点.

我不想处理编写自己的逻辑来连接到消费者节点,特别是不管理节点加入和离开池,所以我走了使用RabbitMQ的路径,每个消费者节点都有一个独占队列.

我遇到的一个问题是列出这些队列,因为生产者需要在分配工作之前知道所有可用的队列.AMQP甚至不支持列表队列,这使我不确定我的整个方法.RabbitMQ和Alice(目前已经破碎)添加了这个功能:是否有用于在RabbitMQ上列出队列和交换的API？

这是一个明智的使用兔子？我应该使用消息队列吗？有没有更好的设计,所以队列可以在消费者之间不断分配我的工作,而不是我需要这样做？

我试图了解一致性哈希是如何工作的。这是我试图遵循但无法遵循的文章，首先我的问题是：

1. 我明白，服务器被映射到哈希码范围内，数据分布更加固定，看起来也很容易。但是这如何处理集群中添加新节点的问题呢？

2. 示例 java 代码不起作用，任何基于简单java的一致散列的建议。

更新

1. 一致性哈希的任何替代方案？