つれづれインフラぶろぐ

インフラエンジニアとして学んだことを書きます

0からわかるコンシステント・ハッシング

ろのだよ。仕事でmemcachedを触ることになったんだけども、

「とりあえずコンシステント・ハッシングと
 スラブ・アロケーターくらいはわかっておかないとね」

と言われたのでまずはコンシステント・ハッシングを調べてみました。

memcachedとは

コンシステント・ハッシングの記事ですが、
memcachedにおけるハッシュ法の記事になるので少し解説させてください。
memcachedとは、分散メモリキャッシュサーバです。DBの負荷を軽減したり、
DBを利用するシステムの高速化を図る目的で用いられます。
分散というくらいなのでmemcahcedのサーバは複数存在しています。
キャッシュするレコードに対して1つのサーバを選択してキャッシュをさせるのですが、
それらのサーバを一意に選択する際にハッシュを用います。

シンプルなハッシュ法

ハッシュやハッシュテーブルについては割愛させて下さい。(理解がある前提で書きます)
よくある動きとしては、
「keyをハッシュにかけて、サーバーの台数で割った余りを出す」 というのがあります。
これはサーバーの台数が決まっている場合には正常に動作しますが、
昨今のインフラでは急増したアクセスに対応する必要があります。

方法としては
「サーバーのスペックを増強する」
「サーバーの台数を増やす」
の2種類があります。
前者はお金も手間もかかるため、基本的には後者を選択することが多い気がします。

しかし、前述したよくある動きを適用している場合に、
サーバーの追加を行うとハッシュの再計算が起きます。
ハッシュの再計算が起きるとキャッシュヒット率の低下によって、
データベースへのアクセスが増大してしまいます。
このようなケースに対応するのがコンシステント・ハッシングです。

コンシステント・ハッシングとは

次の図はレコードがキャッシュされる際の動きです。
(mixi engineer blogさんからお借りしました、ありがとうございますm(__)m)

f:id:ronorono_45:20180121184032p:plain

コンシステント・ハッシングにおけるノードは100~200の仮想ノードにハッシュされます。
それらの仮想ノードは0~232の整数の連続体(以降円と呼びます)の中に配置されます。
新たなレコードのハッシュは円の中の点にマッチすると、
その次に大きいノードに対して格納されます。

f:id:ronorono_45:20180121185955p:plain

この円からノードCを取り除こうとした場合、
ノードCより小さく、ノードBより大きいハッシュのレコードのみが円から取り除かれます。
再度捨てられたレコードが呼ばれた場合は、ノードB以上でノードD以下となるため、
ノードDに格納される、ということになります。
以上の通り、コンシステント・ハッシングはデータロスが少ない
ハッシュ方法だと言うことがお分かりいただけたと思います。

コンシステント・ハッシングのデータ損失率について

これについてはmixi engineer blogさんの記事で検証されていたので是非ご覧ください。 alpha.mixi.co.jp

まとめ

とりあえず一通り理解は出来た。
以下、理解のために訪れたサイト一覧です。ありがとうございました。
ConsistentHashing - コンシステント・ハッシュ法
スマートな分散で快適キャッシュライフ - mixi engineer blog
第1回 memcachedの基本:memcachedを知り尽くす|gihyo.jp … 技術評論社