Wir haben eine App, bei der das Python-Modul Daten in Redis-Shards schreiben wird und das Java-Modul Daten aus den Redis-Shards lesen wird, daher muss ich den genau gleichen konsistenten Hashing-Algorithmus für Java und Python implementieren, um sicherzustellen, dass die Daten gefunden werden können.
Ich habe recherchiert und verschiedene Implementierungen ausprobiert, aber festgestellt, dass die Java- und Python-Implementierungen immer unterschiedlich sind und nicht zusammen verwendet werden können. Ich benötige Ihre Hilfe.
Bearbeitung, Online-Implementierungen, die ich ausprobiert habe:
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
Bearbeitung, angehängter Java- (Google Guava lib verwendet) und Python-Code, den ich geschrieben habe. Der Code basiert auf den oben genannten Artikeln.
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);
}
}Test Code:
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-Code:
import bisect
import md5
class ConsistentHashRing(object):
"""Implementiere einen konsistenten Hashing-Ring."""
def __init__(self, replicas=100):
"""Erstelle einen neuen konsistenten Hashing-Ring.
:param replicas: Anzahl der Replikate.
"""
self.replicas = replicas
self._keys = []
self._nodes = {}
def _hash(self, key):
"""Gegeben einen Zeichenfolgen-Schlüssel, gib einen Hash-Wert zurück."""
return long(md5.md5(key).hexdigest(), 16)
def _repl_iterator(self, nodename):
"""Gegeben einen Knotennamen, gib einen Iterierbaren von Replika-Hashes zurück."""
return (self._hash("%s%s" % (nodename, i))
for i in xrange(self.replicas))
def __setitem__(self, nodename, node):
"""Füge einen Knoten hinzu, gegeben seinen Namen.
Der angegebene Knotenname wird
unter den Replikateanzahl gehasht.
"""
for hash_ in self._repl_iterator(nodename):
if hash_ in self._nodes:
raise ValueError("Knotenname %r ist "
"bereits vorhanden" % nodename)
self._nodes[hash_] = node
bisect.insort(self._keys, hash_)
def __delitem__(self, nodename):
"""Entferne einen Knoten, gegeben seinen Namen."""
for hash_ in self._repl_iterator(nodename):
# löst KeyError für nicht vorhandenen Knotennamen aus
del self._nodes[hash_]
index = bisect.bisect_left(self._keys, hash_)
del self._keys[index]
def __getitem__(self, key):
"""Gib einen Knoten zurück, gegeben einem Schlüssel.
Der Knotenreplikat mit einem Hash-Wert, der am nächsten
aber nicht kleiner als der des gegebenen
Namens ist, wird zurückgegeben. Wenn der Hash des
gegebenen Namens größer ist als der größte
Hash, wird der Knoten mit dem niedrigsten gehashten Wert zurückgegeben.
"""
hash_ = self._hash(key)
start = bisect.bisect(self._keys, hash_)
if start == len(self._keys):
start = 0
return self._nodes[self._keys[start]]Test Code:
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])
