12

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 コード。コードは上記の記事に基づいています。

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])
4

7 に答える 7

10

エンコードの問題と表現の問題という 2 つの問題が同時に発生しているようです。

特に、Python 2 を使用しているように見えるため、エンコードの問題が発生します。Python 2 のstr型は Java の型とはまったく異なりString、実際には Java のbyte. しかし、JavaString.getBytes()は Python と同じ内容のバイト配列を提供するとは保証されていませんstr(おそらく互換性のあるエンコーディングを使用していますが、保証されていません。この修正で状況が変わらなくても、一般的には次のようにすることをお勧めします)。将来の問題を回避します)。

したがって、これを回避するには、Java の のように動作する Python 型を使用し、String両方の言語の対応するオブジェクトを同じエンコーディングを指定するバイトに変換します。Python 側から見るとunicode、これは、Python 3 を使用している場合はデフォルトの文字列リテラル型である型を使用するか、これを .py ファイルの先頭近くに配置することを意味します。

from __future__ import unicode_literals

どちらもオプションでない場合は、次の方法で文字列リテラルを指定します。

u'text'

先頭のuは、強制的にユニコードにします。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。どちらもバイトを提供するため、出力は同等である必要があります。

一方、 Pythonzlib.crc32と Javajava.util.zip.CRC32はどちらも数値結果を返しますが、Java は常に符号なし 64 ビット数であり、Python (Python 2) は符号付き 32 ビット数です (Python 3 では、現在は符号なし 32 ビット数です)。 、したがって、この問題はなくなります)。署名付きの結果を署名なしの結果に変換するには、次result & 0xffffffffのようにします。結果は Java の結果と同等になるはずです。

于 2012-09-11T08:02:41.190 に答える
3

このハッシュ関数の分析によると:

Murmur2、Meiyan、SBox、および CRC32 は、あらゆる種類のキーに対して優れたパフォーマンスを提供します。これらは、x86 での汎用ハッシュ関数として推奨できます。

ハードウェア アクセラレーション CRC (表では iSCSI CRC とラベル付けされています) は、最近の Core i5/i7 プロセッサで最速のハッシュ関数です。ただし、CRC32 命令は、AMD およびそれ以前の Intel プロセッサではサポートされていません。

Python にはzlib.crc32があり、Java にはCRC32 クラスがあります。これは標準的なアルゴリズムであるため、両方の言語で同じ結果が得られるはずです。

MurmurHash 3 は、Google Guava (非常に便利な Java ライブラリ) と Python のpyfasthashで利用できます。

これらは暗号化ハッシュ関数ではないため、高速ですが、同じ保証は提供されないことに注意してください。これらのハッシュがセキュリティにとって重要な場合は、暗号化ハッシュを使用してください。

于 2012-09-11T03:51:38.570 に答える
2

ハッシュ アルゴリズムの言語実装が異なっても、ハッシュ値は異なりません。SHA-1Java または Python で生成されたハッシュは同じになります。

于 2012-09-11T03:51:13.907 に答える
2

私は Redis に詳しくありませんが、Python の例はキーをハッシュしているように見えるので、ある種の HashMap 実装について話していると仮定しています。

Python の例では MD5 ハッシュを使用しているように見えますが、これは Java と Python の両方で同じになります。

Java での MD5 ハッシュの例を次に示します。

http://www.dzone.com/snippets/get-md5-hash-few-lines-java

そしてPythonで:

http://docs.python.org/library/md5.html

ここで、より高速なハッシュ アルゴリズムを見つけたいと思うかもしれません。MD5 は暗号化セキュリティに重点を置いていますが、この場合は実際には必要ありません。

于 2012-09-11T03:53:14.027 に答える
2

これは、キーに対して python と java の両方で同じ結果を生成する単純なハッシュ関数です。

パイソン

def hash(key):
        h = 0
        for c in key:
                h = ((h*37) + ord(c)) & 0xFFFFFFFF
        return h;

ジャワ

public static int hash(String key) {
    int h = 0;
    for (char c : key.toCharArray())
        h = (h * 37 + c) & 0xFFFFFFFF;
    return h;
}

これには、暗号的に安全なハッシュは必要ありません。それはやり過ぎです。

于 2012-09-11T14:30:31.607 に答える
1

これをはっきりさせましょう:異なる環境/実装 (Python、Java、...) で同じハッシュ関数 (SHA-1、MD5、...) への同じバイナリ入力は、同じバイナリ出力を生成ます。これは、これらのハッシュ関数が標準に従って実装されているためです。

したがって、次の質問に答えると、発生する問題の原因がわかります。

  • 両方のハッシュ関数に同じバイナリ入力を提供しますか (Python と Java の MD5 など)?

  • 両方のハッシュ関数 (Python と Java の MD5 など) のバイナリ出力を同等に解釈しますか?

@lvc の回答では、これらの質問についてさらに詳しく説明しています。

于 2012-09-11T08:58:56.110 に答える
0

Java バージョンの場合、128 ビットの文字列結果を生成する MD5 を使用することをお勧めします。結果は BigInteger に変換できます (Integer と Long では 128 ビット データを保持するには不十分です)。

サンプルコードはこちら:

private static class HashFunc {

    static MessageDigest md5;

    static {
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            //
        }
    }

    public synchronized int hash(String s) {
        md5.update(StandardCharsets.UTF_8.encode(s));
        return new BigInteger(1, md5.digest()).intValue();
    }
}

ご了承ください:

java.math.BigInteger.intValue() は、この BigInteger を int に変換します。この変換は、long から int への縮小プリミティブ変換に似ています。このBigInteger が大きすぎて int に収まらない場合は、下位 32 ビットのみが返されます。この変換により、BigInteger 値の全体的な大きさに関する情報が失われるだけでなく、反対の符号の結果が返される可能性があります。

于 2016-10-25T17:24:29.577 に答える