一貫性のあるハッシュアルゴリズムとJava実装

コンシステントハッシュアルゴリズムは、1997 年にマサチューセッツ工科大学によって提案された分散ハッシュ (DHT) 実装アルゴリズムです。その設計目標は、インターネット上のホットスポット問題を解決することです。その本来の意図は CARP と非常に似ています。一貫性ハッシュは、CARP で使用される単純なハッシュアルゴリズムによって発生する問題を修正し、分散ハッシュ (DHT) を P2P 環境で実際に適用できるようにします。

一貫性のあるハッシュアルゴリズムでは、動的に変化するキャッシュ環境におけるハッシュアルゴリズムの品質を決定するための 4 つの定義が提案されています。

1. バランス: バランスとは、ハッシュ結果を可能な限りすべてのバッファに分散し、すべてのバッファスペースを活用できることを意味します。多くのハッシュアルゴリズムがこの条件を満たすことができます。

2. 単調性: 単調性とは、ハッシュによって対応するバッファに何らかのコンテンツが割り当てられている場合に、新しいバッファがシステムに追加されることを意味します。ハッシュ結果により、元の割り当てられたコンテンツが元のバッファまたは新しいバッファにマップできるが、古いバッファセット内の他のバッファにはマップできないことが保証されます。

3. 拡散: 分散環境では、端末はすべてのバッファではなく、その一部のみを認識する場合があります。端末がハッシュ処理を通じてコンテンツをバッファにマッピングする場合、異なる端末は異なるバッファ範囲を認識する可能性があり、ハッシュ結果に一貫性がなくなる可能性があります。最終的には、同じコンテンツが異なる端末によって異なるバッファにマッピングされることになります。この状況は、同じコンテンツが異なるバッファーに保存され、システムストレージの効率が低下するため、明らかに回避する必要があります。分散は、上記が発生する度合いとして定義されます。優れたハッシュアルゴリズムは、矛盾を可能な限り回避し、つまり分散を可能な限り削減できる必要があります。

4. 負荷: 負荷の問題は、実際には分散の問題を別の観点から見ていることになります。異なる端末では同じコンテンツが異なるバッファにマップされる可能性があるため、特定のバッファは異なるユーザーによって異なるコンテンツにマップされる可能性があります。分散と同様に、この状況は回避する必要があるため、優れたハッシュアルゴリズムでは、バッファ負荷を可能な限り削減できる必要があります。

分散クラスターでは、マシンの追加や削除、またはマシンの障害発生後にクラスターから自動的に離脱することが、分散クラスター管理の最も基本的な機能です。一般的に使用される hash(object)%N アルゴリズムを使用すると、マシンが追加または削除された後に元のデータの多くが見つからなくなり、単調性原理に重大な違反が発生します。次に、主にコンシステント・ハッシュ・アルゴリズムの設計方法について説明します。

リングハッシュスペース

一般的に使用されるハッシュアルゴリズムによれば、対応するキーは 2^32 個のバケットを持つ空間、つまり 0 から (2^32)-1 までのデジタル空間にハッシュされます。ここで、これらの数字を端から端までつなげて、閉じた円として想像してみましょう。下記の通り

データは特定のハッシュアルゴリズムによって処理され、リングにマッピングされます

ここで、特定のハッシュ関数を使用して、4 つのオブジェクト object1、object2、object3、object4 の対応するキー値を計算し、それらをハッシュリングにハッシュします。以下のように表示されます。

ハッシュ(オブジェクト1) = キー1;

ハッシュ(オブジェクト2) = キー2;

ハッシュ(オブジェクト3) = キー3;

ハッシュ(オブジェクト4) = キー4;

ハッシュアルゴリズムを使用してマシンをリングにマッピングする

一貫性のあるハッシュアルゴリズムを使用する分散クラスターに新しいマシンを追加する場合、原則として、オブジェクトストレージと同じハッシュアルゴリズムを使用してマシンをリングにマップし (通常、マシンのハッシュ計算では、マシンの IP またはマシンの一意のエイリアスを入力値として使用します)、時計回りに計算して、最も近いマシンにすべてのオブジェクトを保存します。

NODE1、NODE2、NODE3 の 3 つのマシンがあるとします。対応する KEY 値はハッシュアルゴリズムを通じて取得され、リングにマッピングされます。概略図は次のとおりです。

ハッシュ(NODE1) = KEY1;

ハッシュ(NODE2) = KEY2;

ハッシュ(NODE3) = KEY3;

上の図から、オブジェクトとマシンが同じハッシュ空間にあることがわかります。時計回りに、object1 は NODE1 に格納され、object3 は NODE2 に格納され、object2 と object4 は NODE3 に格納されます。このような展開環境では、ハッシュリングは変化しません。そのため、オブジェクトのハッシュ値を計算することで、対応するマシンをすばやく見つけることができ、オブジェクトの実際の保存場所を見つけることができます。

マシンの削除と追加

通常のハッシュ剰余アルゴリズムの最も不適切な点は、マシンが追加または削除された後に多数のオブジェクトストレージの場所が無効になり、単調性要件に大きく違反することです。一貫性ハッシュアルゴリズムがどのように処理されるかを分析してみましょう。

1. ノード（マシン）の削除

上記の分布を例にとると、NODE2 に障害が発生して削除された場合、時計回りの移行方法に従って object3 が NODE3 に移行されます。このように、object3 のマッピング位置のみが変更され、他のオブジェクトは変更されません。以下のように表示されます。

2. ノード（マシン）の追加

新しいノード NODE4 がクラスターに追加されると、次に示すように、対応するハッシュアルゴリズムを通じて KEY4 が取得され、リングにマッピングされます。

時計回りの移行ルールに従って、object2 は NODE4 に移行され、他のオブジェクトは元の保存場所を保持します。一貫性のあるハッシュアルゴリズムは、ノードの追加と削除の分析を通じて、単調性を維持しながらデータ移行を最小限に抑えることができます。このようなアルゴリズムは分散クラスターに非常に適しており、大量のデータ移行を回避し、サーバーの負荷を軽減します。

バランス

上記のグラフ分析によると、コンシステントハッシュアルゴリズムは、一般的なハッシュアルゴリズムの分散化だけでなく、単調性と負荷分散の特性も満たしていますが、まだバランスが欠けているため、これが広く使用されている理由とは見なされません。以下では、コンシステント・ハッシュ・アルゴリズムがバランス要件をどのように満たすかを分析します。ハッシュアルゴリズムはバランスを保証するものではありません。例えば、NODE1とNODE3のみが展開されている上記ケース（NODE2が削除された図）では、object1はNODE1に格納され、object2、object3、object4はすべてNODE3に格納されるため、非常にアンバランスな状態になります。コンシステントハッシュアルゴリズムでは、可能な限りバランスを実現するために仮想ノードが導入されます。

——「仮想ノード」とは、ハッシュ空間における実ノード（マシン）のレプリカです。1 つの実ノード（マシン）は複数の「仮想ノード」に対応しており、この対応数は「レプリカ数」とも呼ばれます。「仮想ノード」はハッシュ値とともにハッシュ空間に配置されます。

上記の NODE1 と NODE3 のみがデプロイされている場合 (NODE2 が削除された図) を例に挙げます。以前のマシン上のオブジェクトの分布は非常に不均一でした。ここで、2 つのコピー (コピーの数) を例に挙げてみましょう。このように、ハッシュリング全体に 4 つの仮想ノードがあります。 *** オブジェクトマッピングの関係図は次のとおりです。

上図によれば、オブジェクトのマッピング関係は、object1->NODE1-1、object2->NODE1-2、object3->NODE3-2、object4->NODE3-1 となります。仮想ノードを導入することで、オブジェクトの分散がよりバランスよくなります。では、実際のオブジェクトクエリは実際にはどのように機能するのでしょうか。オブジェクトをハッシュから仮想ノード、そして実際のノードに変換する様子を次の図に示します。

「仮想ノード」のハッシュ計算は、対応するノードの IP アドレスに数値サフィックスを追加することによって実行できます。たとえば、NODE1 の IP アドレスが 192.168.1.100 であるとします。「仮想ノード」を導入する前に、キャッシュ A のハッシュ値を計算します。

ハッシュ("192.168.1.100");

「仮想ノード」を導入した後、「仮想ノード」NODE1-1とNODE1-2のハッシュ値を計算します。

ハッシュ("192.168.1.100#1"); // NODE1-1

ハッシュ("192.168.1.100#2"); // NODE1-2

Java実装:

 public class Shard<S> { // クラス S は、名前、パスワード、IP、ポートなどのマシン ノードの情報をカプセル化します。
    private TreeMap<Long, S> nodes; // 仮想ノード
    private List<S> shards; // 実際のマシンノード
    private final int NODE_NUM = 100; // 各マシンノードに関連付けられた仮想ノードの数
パブリックシャード(リスト<S> シャード) {
        素晴らしい（）;
        this.shards = 破片;
        初期化();
    }
    private void init() { // 一貫性のあるハッシュリングを初期化する
        ノード = 新しい TreeMap<Long, S>();
 for ( int i = 0; i != shards.size ( ); ++i) { // 各実マシンノードは仮想ノードに関連付ける必要があります
            最終的なS shardInfo = shards.get(i);
 ( int n = 0; n < NODE_NUM; n++)の場合
                // 実マシンノードはNODE_NUM仮想ノードに関連付けられます
                nodes.put(hash( "SHARD-" + i + "-NODE-" + n), shardInfo);
        }
    }
パブリックS getShardInfo(文字列キー) {
        SortedMap<Long, S> tail = nodes.tailMap(hash( key )); // リングの時計回り方向に沿って仮想ノードを見つける
        （テールサイズ（）== 0）の場合{
ノードを返します。get(ノード.firstKey());
        }
 return tail.get(tail.firstKey()); // 仮想ノードに対応する実機ノードの情報を返します
    }
    /**
     * MurMurHash アルゴリズムは、高性能な非暗号化 HASH アルゴリズムです。
     * 従来のCRC32、MD5、SHA-1と比較すると（これら2つのアルゴリズムは暗号化されたHASHアルゴリズムであり、複雑さが非常に高く、パフォーマンスの低下は避けられません）
     * HASH アルゴリズムははるかに高速であり、このアルゴリズムの衝突率は非常に低いと言われています。
     * http://murmurhash.googlepages.com/
     */
    プライベートLongハッシュ(文字列キー) {
        ByteBuffer buf = ByteBuffer.wrap(キー.getBytes() );
整数シード = 0x1234ABCD;
        バイト順序 byteOrder = buf.order ();
        buf.order (ByteOrder.LITTLE_ENDIAN);
        長いm = 0xc6a4a7935bd1e995L;
整数r = 47;
        長い h = シード ^ (buf.remaining() * m);
        長いk;
        (buf.remaining() >= 8) の間 {
            buf の戻り値:
            k*=m;
            k ^= k >>> r;
            k*=m;
            h^=k;
            h*=m;
        }
        buf.remaining() > 0 の場合 {
            ByteBuffer 終了 = ByteBuffer.allocate(8) .order (
                    バイト順序.LITTLE_ENDIAN);
            //ビッグエンディアン版の場合は、まずこれを実行します:
            // 終了位置(8-buf.remaining());
            終了。buf に巻き戻し() を入れる。
            h ^= 終了.getLong();
            h*=m;
        }
        h ^= h >>> r;
        h*=m;
        h ^= h >>> r;
        buf.order (バイト順序);
 hを返します。
    }
 }