コンシステンシハッシュアルゴリズムのKetamaアルゴリズム

テキスト
コンシステンシハッシュアルゴリズムの原理とその応用について議論する文章はすでに十分であり、コンシステンシハッシュアルゴリズムに概念が少しもない学生はまずこの文章を参考にすることができる:コンシステンシハッシュ.
対照的に,コンシステンシハッシュアルゴリズムの原理は比較的理解しやすいが,日常開発の過程で,ほとんどの同僚がコンシステンシハッシュアルゴリズムの原理を大まかに認識しているが,このアルゴリズムの具体的な実現を知ることができる人は少ないことが分かった.もちろん一致性ハッシュアルゴリズムの実現には異なる言語に異なる実現方式があり、その中で有名な実現はKetamaアルゴリズムと呼ばれ、このアルゴリズムは最初はLastである.fmのプログラマーは実現し,広く応用されており,spymemcached,twemproxyなどのオープンソースフレームワークにはこのアルゴリズムの実現が内蔵されている.
本文は主にspymemcachedのソースコードから出発して,Ketamaアルゴリズムの具体的な実現を分析する.
クラスではJAvaにはsetKetamaNodes()メソッドがあり、コンシステンシハッシュループの初期化を担当しています.コードは次のとおりです.

    protected void setKetamaNodes(List nodes) {
        TreeMap newNodeMap = new TreeMap();
        int numReps = config.getNodeRepetitions();

        for (MemcachedNode node : nodes) {
          // Ketama does some special work with md5 where it reuses chunks.
          if (hashAlg == DefaultHashAlgorithm.KETAMA_HASH) {
            for (int i = 0; i < numReps / 4; i++) {
              byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));
              for (int h = 0; h < 4; h++) {
                Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
                        | ((long) (digest[2 + h * 4] & 0xFF) << 16)
                        | ((long) (digest[1 + h * 4] & 0xFF) << 8)
                        | (digest[h * 4] & 0xFF);

                newNodeMap.put(k, node);
                getLogger().debug("Adding node %s in position %d", node, k);
              }
            }
          } else {
            for (int i = 0; i < numReps; i++) {
              newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
            }
          }
        }
        assert newNodeMap.size() == numReps * nodes.size();
        ketamaNodes = newNodeMap;
    }

次にsetKetamaNodes関数の実装を具体的に解析し,まずMemcachedNodeというクラスがMemcachedノードのネットワーク接続パラメータと方法をカプセル化した.ここでTreeMapを用いて,整合性ハッシュリングの環状構造をシミュレートした.

    int numReps = config.getNodeRepetitions();

getNodeRepetitions()メソッドは、構成情報の読み取りを担当し、実際のMemcachedノードに対応する仮想ノード数を返し、デフォルトでは160を返します.つまり、Memcachedノードがコンシステンシハッシュリング上で160個の仮想ノードに対応しています.

    config.getKeyForNode(node, i)

getKeyForNode()は、転送されたMemcacheNodeオブジェクトと変数iに基づいてkey値を生成し、戻り値の例:「127.0.0.1:1311-0」を返します.
computeMd 5()はkeyに基づいて16ビットのMD 5要約を生成するので、digest配列は合計16ビットである.

    byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));

digest配列を4ビットごとにグループ化し、ビット操作により最大32ビットの長い整数を生成します.32ビットであるのは、コンシステンシハッシュループの値範囲が0〜2^32であるためである.上記の例に戻ると、Memcachedノード、例えば「127.0.0.1:1311」について、forループによって「127.0.0.1:1311-0」、「127.0.0.1:1311-1」、「127.0.0.1:1311-1」が生成される..."127.0.0.1:1311-39"の合計40個のコピー、例えば"127.0.0.1:1311-0"のようなコピーごとに、4個の長さの整数が生成され、コンシステンシハッシュリング上の4つの位置に対応するので、デフォルト構成の場合、1つのMemcachedノードはコンシステンシハッシュリング上で4つの位置を占める×40=160の位置です.

    Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
            | ((long) (digest[2 + h * 4] & 0xFF) << 16)
            | ((long) (digest[1 + h * 4] & 0xFF) << 8)
            | (digest[h * 4] & 0xFF);

kをキーとしてMemcacheNodeオブジェクトをTreeMapに配置します.

    newNodeMap.put(k, node);

TreeMapにおけるvalueはKey順であるため,一致ハッシュの環状構造をTreeMapによってシミュレートすることができ,k値が小さい方が前,k値が大きい方が後ろである.
以上がコンシステンシハッシュループ初期化プロセスの基本的な解析であり、次にクエリのプロセスを見てみましょう.getPrimary()関数はkey、例えば「123」を入力し、まずそのkeyのハッシュ値を計算します.

    public MemcachedNode getPrimary(final String k) {
        MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
        assert rv != null : "Found no node for key " + k;
        return rv;
      }


    MemcachedNode getNodeForKey(long hash) {
        final MemcachedNode rv;
        if (!ketamaNodes.containsKey(hash)) {
          // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
          // in a lot of places, so I'm doing this myself.
          SortedMap tailMap = getKetamaNodes().tailMap(hash);
          if (tailMap.isEmpty()) {
            hash = getKetamaNodes().firstKey();
          } else {
            hash = tailMap.firstKey();
          }
        }
        rv = getKetamaNodes().get(hash);
        return rv;
    }   

ここで、TreeMapのtailMap()メソッドは、1つのSortedMapオブジェクトtailMapを返します.tailMapに含まれるすべてのキー値は、パラメータhashよりも大きくなります.この操作は、指定されたhash値に相当し、コンシステンシハッシュループから時計回りにノードを検索し、最初のキー値がパラメータhashよりも大きいノードを検索するまで、このノードはhash値に対応するMemcachedノードである.

    SortedMap tailMap = getKetamaNodes().tailMap(hash);

以上,SypmencachedソースコードにおけるKetamaアルゴリズムの実装解析である.