データベース - 第5部 : コンシステントハッシュ

Overview

コンシステントハッシュ（Consistent Hashing）とは何でしょうか？ これを知る前に、まずhashing（ハッシュ化）という言葉は「刻んで混ぜる」と理解できます。Hash Mapはインデックスにデータをマッピングしたデータ構造です。O(1)であり最も効率的だと言えます。通常はキーと値のペアで保存するのが一般的です。

ハッシュについてはこれくらいにして、分散ハッシュについて話してみましょう。

分散ハッシュ

以下のハッシュテーブルがあると仮定してみましょう。今、私たちはこのデータを分散データストアに保存しようとしています。

3台のサーバーに分けて保存すると、以下のように整理されます。 それぞれ A:0, B:1, C:2 のインデックスを持ちます。

このようにうまく使っている状況で、突然機器が1台故障したと考えてみましょう。サーバーCがダウンしたと仮定すると、再び以下のようにハッシュテーブルとサーバーにデータが割り当てられることになります。

これで A:0, B:1 の2台のストレージにデータが以下のように保存されます。

このようになると、Cに存在していたすべてのキーの位置が変更されることになり、この時、元データからの再ハッシュ（re-hashing）作業が必要となります。これはオリジンサーバーに負荷を与えることになります。そしてその間、クライアントがリクエストしたデータは失われてしまいます。

これを解決するために登場したハッシュ手法が、まさにコンシステントハッシュ（Consistent Hashing）です。

Consistent Hashing

上の画像が今回話す全てです。 上の画像に従ってハッシュ化を行うと考えてみましょう。

サーバーもハッシュテーブルに一緒に配置します。

ここで各キーが位置するサーバーを見つけるルールは一つです。

反時計回りに回る時、最も近いサーバーがそのキーが位置する保存場所です。

先ほど述べた基準でキーが保存されている場所を整理すると以下のようになります。

では、一体この手法のメリットは何でしょうか？

想像してみましょう。もしCの機器が削除されたとします。既存の手法ではすべてのキーが再ハッシュされなければなりませんでした。

まさにここで、この手法を通じて私たちはCの機器に割り当てられているキーだけ再ハッシュが必要であることを知ることができます。

A、Bのサーバーを見ているキーは、すでに最も近い位置A、Bを見ているためです。Cがなくなってもそれらのキーに変更事項はありません。Cサーバーに割り当てられたキーだけ再ハッシュが必要です。

逆に機器が追加されても K/N （キーの数 / 機器数）だけの再ハッシュが必要なだけで、すべてのキーに対して再ハッシュが必要なわけではありません。

例えばキーが3つで、機器が2つだった時。この間に機器が1つ入ると考えると、機器にキーが均等に入るように設計したと仮定すれば、3/3 = 1つのキーに対して再ハッシュが起こり得て、これは結局、機器1つにつき1つのキーが保存されるバランスの取れた姿を見せることができます。

Consistent Hashing は問題を抱えています。それはキーの偏りです。これをどうすれば緩和できるでしょうか？

Ketama Consistent Hashing

まず最も簡単な方法は、サーバーを複数のトークンに分割して Consistent Hashing Circle に配置することです。 これがまさに Ketama Consistent Hashing 手法です。AサーバーをA0-A10まで分散させ、キーの配置が極力均一になるようにします。

考察

• 結局、再ハッシュ（rehashing）は避けられない問題です。最小限の再ハッシュで済むように設計し、構築することが分散処理の要求事項だと考えられます。

サンプルプロジェクト ( 上記の理論を簡単に実装してみました )

• Reduster

Appendix

• Constant Hashing
• hashing, ketama