用于Java和Python程序的相同一致哈希算法实现

Question

我们有一个应用程序,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) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hashString(node.toString() + i).asLong(),
                    node);
        }
    }

    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hashString(node.toString() + i).asLong());
        }
    }

    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        long hash = hashFunction.hashString(key.toString()).asLong();
        if (!circle.containsKey(hash)) {
            SortedMap<Long, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash);
    }
}

测试代码:

        ArrayList<String> al = new ArrayList<String>(); 
        al.add("redis1");
        al.add("redis2");
        al.add("redis3");
        al.add("redis4");

        String[] userIds = 
        {"-84942321036308",
        "-76029520310209",
        "-68343931116147",
        "-54921760962352"
        };
        HashFunction hf = Hashing.md5();

        ConsistentHash<String> consistentHash = new ConsistentHash<String>(hf, 100, al); 
        for (String userId : userIds) {
            System.out.println(consistentHash.get(userId));
        }

Python代码:

import bisect
import md5

class ConsistentHashRing(object):
    """Implement a consistent hashing ring."""

    def __init__(self, replicas=100):
        """Create a new ConsistentHashRing.

        :param replicas: number of replicas.

        """
        self.replicas = replicas
        self._keys = []
        self._nodes = {}

    def _hash(self, key):
        """Given a string key, return a hash value."""

        return long(md5.md5(key).hexdigest(), 16)

    def _repl_iterator(self, nodename):
        """Given a node name, return an iterable of replica hashes."""

        return (self._hash("%s%s" % (nodename, i))
                for i in xrange(self.replicas))

    def __setitem__(self, nodename, node):
        """Add a node, given its name.

        The given nodename is hashed
        among the number of replicas.

        """
        for hash_ in self._repl_iterator(nodename):
            if hash_ in self._nodes:
                raise ValueError("Node name %r is "
                            "already present" % nodename)
            self._nodes[hash_] = node
            bisect.insort(self._keys, hash_)

    def __delitem__(self, nodename):
        """Remove a node, given its name."""

        for hash_ in self._repl_iterator(nodename):
            # will raise KeyError for nonexistent node name
            del self._nodes[hash_]
            index = bisect.bisect_left(self._keys, hash_)
            del self._keys[index]

    def __getitem__(self, key):
        """Return a node, given a key.

        The node replica with a hash value nearest
        but not less than that of the given
        name is returned.   If the hash of the
        given name is greater than the greatest
        hash, returns the lowest hashed node.

        """
        hash_ = self._hash(key)
        start = bisect.bisect(self._keys, hash_)
        if start == len(self._keys):
            start = 0
        return self._nodes[self._keys[start]]

测试代码:

import ConsistentHashRing

if __name__ == '__main__':
    server_infos = ["redis1", "redis2", "redis3", "redis4"];
    hash_ring = ConsistentHashRing()
    test_keys = ["-84942321036308",
        "-76029520310209",
        "-68343931116147",
        "-54921760962352",
        "-53401599829545"
        ];

    for server in server_infos:
        hash_ring[server] = server

    for key in test_keys:
        print str(hash_ring[key])

Answer 1

您似乎同时遇到两个问题:编码问题和表示问题.

编码问题特别是因为您似乎使用Python 2 - Python 2的str类型根本不像Java的String类型,实际上更像是Java数组byte.但是Java String.getBytes()并不能保证给你一个与Python相同内容的字节数组str(它们可能使用兼容的编码,但不能保证 - 即使这个修复不改变东西,一般来说这是一个好主意.避免将来出现问题).

因此,解决这个问题的方法是使用类似于Java的Python类型,String并将相应的对象从两种语言转换为指定相同编码的字节.从Python方面来说,这意味着您要使用unicode类型,如果您使用的是Python 3,则使用默认的字符串文字类型,或者将其放在.py文件的顶部附近:

from __future__ import unicode_literals

如果这两个都不是选项,请以这种方式指定字符串文字:

u'text'

该u在前面强制它为Unicode.然后可以使用其encode方法将其转换为字节,这需要(不出所料)编码:

u'text'.encode('utf-8')

从Java方面来看,有一个重载版本String.getBytes需要一个编码 - 但它需要它作为一个java.nio.Charset而不是一个字符串 - 所以,你会想做:

"text".getBytes(java.nio.charset.Charset.forName("UTF-8"))

这些将为您提供两种语言中等效的字节序列,以便散列具有相同的输入并为您提供相同的答案.

您可能遇到的另一个问题是表示,具体取决于您使用的哈希函数.Python hashlib(从Python 2.5开始,它是md5和其他加密哈希的首选实现)与Java完全兼容MessageDigest- 它们都给出了字节,所以它们的输出应该是等价的.

另一方面,Python zlib.crc32和Java java.util.zip.CRC32都提供了数字结果 - 但Java总是一个无符号的64位数,而Python(在Python 2中)是一个带符号的32位数(在Python 3中,它现在是一个无符号的32位数) ,所以这个问题就消失了).要将签名结果转换为无符号结果,请执行:result & 0xffffffff,结果应与Java结果相当.