P2Pネットワークを用いたNoSQLについて

Question

P2Pネットワークを使ったNoSQLとして有名なDynamoDBやCassandraですが、これらNoSQLと呼ばれるものについて疑問があり質問いたします。これらのシステムではハッシュを使って保存先の割り出しが行われていると思うのですが、一度ハッシュ値によって決まったサーバーから移動したい(ハッシュ値で割り当てられたところからの移動)という要求が一切ないものなのでしょうか(例えばこのデータとこのデータは同時に参照されるから等)? もしある場合は単なるハッシュのみでは保存先がわからなくなると思うのですがこれに対する解決法などは考えられているのでしょうか？

Answer 1

一度ハッシュ値によって決まったサーバーから移動したい(ハッシュ値で割り当てられたところからの移動)という要求が一切ないものなのでしょうか

クラスタの構成が変わらないのならそういうことはありません。質問者さんの指摘どおり、それが起こるとキーに対してどのサーバに問い合わせればいいのかわからなくなってしまいます。しかしクラスタの構成が変わった場合はこの限りではありません。

説明のため、0～15の4bitのハッシュ空間で例をあげます。

ノード4台あって、
Aが0～3、Bが4～7、Cが8～11、Dが12～15
のハッシュ領域を担当しているとします(ConsistencyLevelは1とします)。ここでノードEを追加したとき、それがDの後ろに入ったとします。
Aが0～3、Bが4～7、Cが8～11、Dが12～13、Eが14～15
実際はもっともキー数の多い場所や管理者が指定した場所にノードが追加されたりしますが、この例でもノードDにあったハッシュ空間14～15のキー/データがノードEに移動した、と言うことができます。ここでは4bitの狭いハッシュ空間でしたが、これはCassandraでは64bitあります。

---

でもこの「移動」という言葉には少し注意してください。詳細に立ち入らない場合は「移動」で済むのですが、コンピュータの場合、移動している瞬間を見ると「あっちに複製して、確認したらこっちを削除」であることがわかります。FAXやメールも「送る」と表現するものの、やってることは相手側への複製です。

Comments

[kkkmokotan]

回答ありがとうございます。ノードの追加については確かにこのハッシュの担当箇所の変更による移動が起こると考えられますね。もしこの"移動"が要求として発生するのとを想定する場合、移動先のID(IP)を管理する方法はないかと考えています。

[sharow]

実用的かどうかは置いといて、できるかもしれませんが、でもなにゆえに？？

昨今のHDDはみんなLBA(論理ブロックアドレス)で扱われています。私はファイルを保存しますが、HDDのどのシリンダ/セクタ/トラックに保存されるのかには興味はありません。たしかによく使うファイルをシリンダの外周に「移動」できると効率が良いかもしれません。でもそういう最適化をやっているのは一部のDBベンダーくらいです。

同じようにDynamo系のDBの場合、普通は論理的なハッシュ空間の中の特定の「キー」が「どのノードに」という事は関心の対象外です。関心はまず「よく分散させること」であって、あるノードに偏ったから移動させる、というようなテーブル設計の失敗を想定した上での救済策、みたいなものは用意されていません。そもそも失敗するな、という話になっているのです。

私には移動を要求する理由が分かりません。移動させる「理由」を突き詰めていくと疑問の解消につながるのではないでしょうか。

[kkkmokotan]

回答ありがとうございます。P2Pネットワークを用いたNoSQLにおいて局所性の高いデータを同時に同じサーバにおいておくことによりデータに効果的にアクセスする方法はないかと考えておりました。その観点からみるとDHTではその局所性を考慮していないため、データ局所性を考慮したDHTなどが存在しないものかと疑問に思っていたのです。お答えしていただき本当にありがとうございます。

[sharow]

なるほど。おそらく質問者さんの興味のあるところはNoSQL(DynamoDB)というよりP2P上の分散ストレージ、のようなものではないでしょうか。Cassandraに限った話をすると、人気のあるカラムだけ複製を増やす、ということはインデックス機能を捨てるということです。あるいはテーブル全体の複製(インデックス含む)を増やすということになってしまいデータベースとしてあまり現実的ではありません(結果整合性を得るためのコストが増大してしまう)。

私は立ち読み程度しか見たこと無いのですが、金子勇氏の「Winnyの技術 」という本は分散システムにおける局所性や遅いノードなど、実世界の問題の話が載っていてお勧めです。やりとりを見ていると、既にご覧になっているかもしれませんが。

[kkkmokotan]

なんども回答いただきありがとうございました。とても楽しい話題なのでこのまま盛り上がってしまいそうですが、とりあえずBAとさせていただきます！本の方も見てみたいと思います。