« [P2P][DHT]P2P分散プロキシの検討:その3 | トップページ | [skype]skype conference 2005 JAPANの講師陣について »

2005.05.26

[P2P][DHT]P2P型分散データベースの提案

Oracleがグリッドについて積極的に取り組んでいるが、今回はDHTを使ったスケーラブルな分散型データベースを提案したい。なお、データベースについてはDB、分散型データベースはDDBと省略する事にする。

さて、ご存知のとおりDHTを使うと、一般的にあるデータdataはNode_ID=hash(data)というノードに格納する。
DBについては一般に主キーというのがあって、これを基に検索などの処理を書けることになる。
今回はDHTによるDDBの可能性を考えるために簡単なモデルを提案する。実際にはDDBを運用する上でもっと多くの課題があるはずだし、それはこのBlogを見て頂いたみなさんと共に解決していきたい。

今、あるDBのテーブルがあるとする。このテーブルには主キーがある。
DDBを使うととても巨大なDBを扱える可能性がある。まずそれにはDDBのテーブルを分割する必要がある。

まず、主キーについてはハッシュ値を計算し、主キー(及び主キーに紐づいた他のテーブル項目)をハッシュ値の昇順でソートする。テーブルはあるハッシュ値をトリガーにして複数に分割する。つまり、全体のテーブルをTableとすると
[式1]Table=Table(0.A)+Table(A+1,B)+Table(B+1,C).....
と分割できるはずだ。なお、Table(S,Q)は主キーのハッシュ値において、SからQについて構成しているテーブルを意味している。なお、このテーブルはノードやネットワーク負荷、DBサイズによって自律的に分割、結合を行う。
なお、Table(S,Q)を保持するノードはNode_ID=Sとしよう。

これだけだと単にTableの分割を行っただけだ。そこで実際にSQL文を叩いて作業をするにはどうすればよいのだろうか?

今、バーチャルDBノードと言うのを定義する。略してVDBノードと呼ぼう。これはあるノードAがVDBノードにSQL文を投げれば、ノードAから見てVDBノードがあたかも全てのDBの処理をしているように見えるノードを意味する。

VDBノードはNode_Id=hash(Table_name)である。VDBノードは式[1]のようにテーブルを分散したときに、その分散したテーブルを保持するノードのNode_IDのリストを保持する。今、このリストを分散テーブル管理リストと呼ぼう。つまり分散テーブル管理リストは
[式2]{0,A+1,B+1,C+1.....}
となる。

これで準備が整った。
では、これからSQL文を実際に発行して処理させるようにしよう。
まず、SQL文を発行するノードAはVDBノードにSQL文を通知する。VDBノードはSQL文を分散テーブル管理リスト{0,A+1,B+1,C+1....}を保持しているので、Node_ID={0,A+1,B+1,C+1....}にSQL文をマルチキャストする。なお、VDBノードは事前処理を行い、不要なSQL文を処理に関係ないノードに送らないようにする。
分散テーブルを保持しているノードNode_ID={0,A+1,B+1,C+1....}はSQLの処理結果をVDBノードに通知する。最終的ににはノードAにSQL処理の結果を通知することになる。

異なるDBテーブルとの結合等についても処理はややこしくなるが、可能であろう。

今回はP2P型分散データベースについて簡単ながら提案・検討を行った。DHTを使うと、とても大きいサイズのDBが構築可能となるかもしれないし、それを高速に処理できるかもしれないので、研究すると面白いかもしれない。

|

« [P2P][DHT]P2P分散プロキシの検討:その3 | トップページ | [skype]skype conference 2005 JAPANの講師陣について »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/4292211

この記事へのトラックバック一覧です: [P2P][DHT]P2P型分散データベースの提案:

« [P2P][DHT]P2P分散プロキシの検討:その3 | トップページ | [skype]skype conference 2005 JAPANの講師陣について »