「一致性ハッシュアルゴリズムの登場は新たな問題も伴っている、即ち某サーバーノードが崩れた後、それの任務はそれの次のサーバーノードへ分配され、分散式システム中においてバランスを満足しないといけない要求と乖離するのである。」
なだれ効果

 サーバーに一部のデータが常にアクセスされるものがある、これらのデータのアクセス回数はその他のデータおり遥かに多いため、ホットポイントデータと呼ばれる、もちろん分散式サーバーでこれらのホットポイントデータを支えるサーバーの負荷もその他のサーバーより大きい。ホットポイントに対するアクセス量がサーバーが受け入れられる限界を超えたときに、サーバーが崩壊してしまうのである。

 一致性ハッシュアルゴリズムに基づいて、このサーバーのデータは次のサーバーに移行される、次のサーバーも当然こんなに大きなアクセス量を担うことができず、同じように崩れて、さらに次のサーバーも崩れ、そして最後は全体のサーバーが崩れてしまう。これはいわゆるなだれである。

最適化方案

 ここに二つの最適化方案がある、一つは簡単で乱暴、つまりホットポイントデータを担うサーバーの数量を増やす。もうひとつもっといい方案はバーチャルノード技術を使用することである、この方法の原理は一つの物理ノードを数個のバーチャルノードに分解して、これらのバーチャルノードを均等にハッシュリングに分散させるのである。そうすることによって某ノードが削除されたあと、それのデータ資源の分配が不均衡の問題を解決した。

https://images.ihuoqiu.com/article/2018/04/01/huoqiuwang_201804011810233481.jpg

 上記図の赤いノード3はホットポイントデータを積載するサーバーと相当で、右の図のように全ての物理ノードを二つのバーチャルノードに分解して、均等にハッシュリングに分散している。

 このような解決方案のメリットはノードを増やす時に、新しいノードがその他のノードから資源を引っ張ることによるノード資源の分布が不均等という問題も同時に解決したのである。

 例えば、ABDの三つのノードに百個の資源を分配した、BDの間にノードCを加えようとした時に、Cノードは直接Dノードからノードを引っ張る、そうするとABに分配される資源は必ずCDが分配される資源より多いため、当然サーバーの負荷の均衡要求に満足できない。一つの物理ノードを挿入する時に、それをいくつかのバーチャルノードとして分解して、それらを均等にハッシュリングに分散させれば、この問題が解決できる。

時間の複雑度

 ここまでできれば、一致性ハッシュはすでに完璧に見えるようだが、我々はもう一つの問題を見落とした、それは一致性ハッシュの時間をサーチする複雑度である。一致性ハッシュは一般ハッシュと違って、時間の複雑度は0(1)で、これは普通のハッシュは数値グループに基づいており、一方、一致性ハッシュは伸縮性に満足するためにチェーンテーブルを選択して基礎データの構造とするのが一般的である。そうすると時間の複雑度が0(N)になる。

最適化方案

 ここでは0(N)の時間の複雑度はハッシュアルゴリズムにとって堪えられないことである、なので我々はジャンプテーブルと呼ばれる技術を使用してこの問題を解決する。

clip_image0021.jpg 
上記図のように、このジャンプテーブルの中に、各ノードは自分に1、2、4の距離に離れている数字が保存されるノードを記録する、そうするとサーチがどのノードに落ちても、全体のハッシュリングに対するあらゆるサーチは最低でも半分のサーチスペースが省けられる、こうのように再帰すればすぐにデータがどのノードに保存されているかが追跡できる。そうすれば、時間複雑度が0(LogN)まで下がる。ただし、この方法は同様にサーバーの保存スペースを占用する問題を齎すことがある。

 第二種の解決方案は、チェーンテーブルを基礎のデータ構造として使用せず、バイナリサーチツリー構造に変える。ハッシュサーチのプロセスは実際バイナリサーチツリーの中でサーチ数値以上の最小数値をサーチする過程である、なので我々は需要に基づいてAVLツリーを選択して、レッドブラックツリーを基礎データ構造とする。そうすることによって、時間複雑度を0(logN)まで下げることができる。