IIJ社における分散DB技術「ddd」（1）

キーバリューストアによる分散ストレージ

　スケールアウトに適したデータストレージということで、注目を集めているのが分散キーバリューストア（key-value store）という方式です。

　キーバリューストアとは、データを「キー」と「バリュー」の組み合わせで格納するシンプルなデータベースの一種で、それを複数のノードで分担して管理するのが分散キーバリューストアです。dddのストレージ部分も、分散キーバリューストアに分類されます。

　キーバリューストアは、RDBMSに比べるとずっと低機能で、基本的にはキーを指定して対応する値を読み書きするということしかできません。そのかわり、キーの値によって担当するノードを振り分けて分散化することに向いており、スケーラビリティを高めることができます。

　分散キーバリューストアでは、キーを担当するノードを振り分けるためのアルゴリズムが重要です。dddでは、Amazon Dynamoなどのほかの多くの分散キーバリューストアと同じく、コンシステントハッシュ法（P3参考文献［1］［2］）と呼ばれるアルゴリズムを採用しています。

　コンシステントハッシュ法では、各ノードおよびキーは、整数の目盛りが振られたリング上のどこかに配置されているものとして考えます（この配置はあくまで論理的なもので、ノードの物理的なネットワークトポロジとは無関係です）。

　リング上の整数値はハッシュ関数が返す値の範囲に対応していて、例えばdddではハッシュ関数にSHA-1を使っているため、0から2の160乗マイナス1までの範囲になります。

　このリングを基に、キーを担当するノードは次のように決定します。

1）まず、ノードにはIPアドレスをハッシュした値がノードIDとしてつけられ、対応するリング上に配置します。

2）格納したいキーも同様にハッシュして整数値に変換し、リング上の対応する位置に置きます。

3）その位置から反時計回りにまわって最初に遭遇するノードを、そのキーの担当とします（なお、担当ノードの決め方は、ほかにも時計回り方式や最近値方式などがあります）。

　コンシステントハッシュ法では、あらかじめノードの一覧表があれば、格納されているキーの数やデータの量とは無関係に、キーの値からハッシュ値を計算するだけで高速に格納ノードを割り出すことができます。

　コンシステントハッシュ法の最大のメリットは、ノードが増減した場合に、影響を受けるキーの範囲が限定されることです。例えば、図2の中でノードBが故障でなくなった場合、薄い緑色で示される範囲のキーのみ担当ノードが変わりますが、それ以外のキーは影響を受けません。

　担当ノードが変わるということは、対応するキーと値を別のノードに再配置しなければいけないことを意味しますが、コンシステントハッシュ法ではその範囲が限定され、再配置しなければならないデータを少なく抑えることができます。

　多数のノードを利用する分散システム環境では、故障や増強などによりノードが増減することを日常的なこととして想定する必要があります。コンシステントハッシュ法は、その増減に強いという利点のため、分散キーバリューストアではよく使われるアルゴリズムです。

バーチャルノードによる偏りの解消

　コンシステントハッシュ法では、キーの保有数に関係なくハッシュ関数のみにより担当ノードを決めるため、ノードによって担当するキーの数に偏りが生じることがあり得ます。

　キーが一様に分布する場合、ノードの担当するキー数は、リング上でのノード間の間隔に依存します。前のノードとの間隔が小さい場合、そのノードに割り振られるキー数は確率的に少なくなります。例えば、図2でノードBがなくなった後のケースを考えると、ノードAの担当範囲がほかのノードに比べてかなり広くなってしまいます。

　担当するキー数の偏りを少なくするために、dddではバーチャルノード（virtual node）という概念を利用しています。1台のノードに1つのIDを割り振るのではなく、繰り返しハッシュ関数を適用するなどして 1台のノードに複数のIDを割り振るというものです。

　こうすることにより、1つのノードが担当する領域が分散し、偏りが小さくなることが期待できます。参考文献［2］によると、1台のノードに100から200程度のバーチャルノードを用意するとおおむね良いバランスになるとしています。

　バーチャルノードを利用することにより、偏りを小さくするアプローチとは逆に、担当するキー数に意図的に差をつけることも可能です。あるノードの性能がほかのノードより優れている場合は、そのノードのバーチャルノード数を増やせば良いわけです。