目次
はじめに
Kademliaとは分散ハッシュテーブルの一種であり、高いChurn耐性（後述）を持つため、実用的なP2Pアプリケーションにて多く利用されています。
そもそも分散ハッシュテーブル(Distributed Hash Table, DHT)とはkeyとvalueの対のハッシュテーブルを複数のノードが協力して管理するシステムです。効率よくkeyやvalueを探すための仕組みや、ノードの接続管理の方法によって様々な種類の分散ハッシュテーブルが存在します、代表的なものにChordや今回解説するKademliaがあります。
Churnとは絶え間ないノードの出入りという意味で、それに対する耐性（Churnによるパフォーマンスへの影響が出にくい）性質をChurn耐性と呼びます。実際のP2Pネットワークでは、新しくノードが参加してきたり、また何らかの原因(停電やネットワーク関連のエラーなど)によってノードがネットワークから切断されることが多くあります。このChurnの問題に対して非常に強力なのがKademliaというアルゴリズムです。
本記事は、過去にコンセンサス・ベイスが主宰していたオンラインサロンの記事です。記事は2017年~2018年にかけて執筆されたため、一部は、既に古くなっている可能性があります。あらかじめご了承ください。
関連する記事
Kademliaの解説と実装 2
Kademliaの解説と実装 3
採用例
それでは、Kademliaがどういったところで使われているのかを調べてみましょう。
| サービス名 | 使用箇所 |
| Torrent | magnetURLという機能を用いてファイルをダウンロードする際に目的のファイルを持っているノードを探索するのにKademliaを用いています。Torrentはアクティブユーザと転送量という点で見ると世界で最も成功したP2Pのシステムであり、そのシステムにKademliaはおおいに貢献していると言えます。 |
| ethereum | Node Discovery Protocol v4 というノードの探索プロトコルに用いられているようです。 |
| IPFS | IPFSとは複数のノードが協調して一つの大きなストレージまたはHTTPの置き換えとして機能することを目的としているシステムです。IPFSは完全にKademliaをベースとして開発されており、基本的にはKademliaの機能拡張のようにも見えます。 IPFSに関しては、過去記事でも取り上げていますのでご覧ください。 |
| その他のファイル共有ソフト | KademliaはChurn耐性がある上に実装が比較的容易なため、多くのファイル共有ソフトに用いられています。 |
アルゴリズムの解説
ノードIDとキー
Kademliaにおける個々のノードには固有のノードIDが割り振られます。このノードIDは160bitと定義されています。ノードIDの決定方法は、ランダムな値にsha1というハッシュ関数を適用し、160bitの値を取り出すのが一般的です。また、ハッシュテーブルに保存するバリューと対になるキーも160bitと定義されています。
経路表
分散ハッシュテーブルのアルゴリズムによってノードを管理する経路表の形は様々です。例えば、Chordという分散ハッシュテーブルの場合は環状の経路表を持っています。Kademliaの場合はk-bucketsという160個のbucketからなる経路表を持っています。一つのk-bucketにはK個(たいていの実装例では20個。本記事でも20とする。)のノードが登録でき、自身のノードとの距離に応じたk-bucketにそれぞれのノードが登録されていきます。ノード間の距離はノードID同士をXORで掛け合わした結果を用います。
例として、３ビットのノードID(本来は160ビットですが簡略化のため)でノード間の距離を求めてみます。
ノードID_A 111 ⊕ ノードID_B 010
↓
距離 101
この101を10進数に直すと5になるのでノードID_AとノードID_Bの距離は5であることがわかります。
以上を踏まえてkeyとノードIDが３ビットで、注目する自身のノードIDが101とした場合のk-bucketsを表に表してみます。
| k-bucket ( i 番目 ) | ノード101からの距離 | k-bucketの内容 |
| 0 | 1 | 100 |
| 1 | 2 ~ 3 | 110,111 |
| 2 | 4 ~ 7 | 000,001,010,011 |
また、このk-bucketsは２分木として表すことができます。
プロトコル
Kademliaには４種類の通信問い合わせがあります。名称と内容についてまとめます。
| 名称 | 内容 |
| PING | 対象のノードがオンラインかどうかを問い合わせる。 |
| STORE(key,value) | 対象ノードにkey,valueの組を保持させる。保持させる際のルールは、自身のk-bucketsから最もkeyにXORの距離が近いノードを選択し、そのノードにkey,valueを与える。受け取ったノードは更に自身のk-bucketsから最も受け取ったkeyに近いノードを選択し、key,valueを与える。この動作を何度も繰り返す。最終的にはネットワーク上で最もkeyに距離が近いノードが目的のkey,valueを持つことになる。 |
| FIND_NODE(key) | 自身のk-bucketsのうち最もkeyにXOR距離の近いノードに自身のノードIDと距離が近い上位K個のノードの情報を送らせる。 |
| FIND_VALUE(key) | 自身のk-bucketsのうち最もkeyにXOR距離の近いノードにkeyと対応するvalueを持っているか問い合わせる。持っている場合はそのvalueを、持っていない場合は問い合わせられたノード自身のk-bucketsのうち、keyに最も近いノードの情報を返す。 |
ノードの管理
KademliaのChurn耐性の高さはこのノードの管理方法にあります。Kademliaのノード管理は上記の4つのプロトコルの通信を行うついでに行われます。そのため、ノードの離脱の際の処理が必要なく、Churnを考慮することなくネットワークを維持することができます。
経路表の更新
ノードの管理のうちの経路表の更新から見ていきましょう。
ノードは4つのプロトコルのいずれかのメッセージを受け取った際に送信元が該当するk-bucketの中にあった場合そのノードをk-bucketの末尾に移します。
| 先頭 | target | x | x | x | x | x | x | x | 末尾 |
↓
| 先頭 | x | x | x | x | x | x | x | target | 末尾 |
送信元が該当するk-bucketの中に存在せず、k-bucketがすでに満杯な場合、そのk-bucket中の先頭のノードがオンラインかどうかをPINGで確認します。オンラインなら先頭のノードを残し、そうでなければ送信元の新しいノードをk-bucketに追加します。こうすることで長時間オンラインになっているノードが優先的にk-bucketに残るため、ネットワークの安定性に寄与します。
ノードの新規参加
新規参加するノードは、まず接続先のノードに対して自身のノードIDをkeyとしてFIND_NODEします。問い合わせを受けたノードは送信元のkeyに近い最大K個のノードの情報を送信元にSTOREします。そうすることで、新規参加するノードはまず最大K個のノードに接続します。このあと、さらに自身のk-bucketsのうち最も自身のノードIDにXOR距離が近いノードに対し自身のノードIDをkeyとしたFIND_NODEを繰り返すことで接続先のノードを増やすことができます。
ノードの離脱
何も行いません。
データの共有、探索
以上のことを踏まえてKademliaの応用的な使い方について見ていきましょう。IPFSは基本的にこの手法に沿ってネットワーク上にデータを保存、検索していると考えられます。
例えばある動画Aをネットワーク上で共有するケースを考えてみましょう。
まず動画Aのバイナリにsha1関数をかけて160bitのハッシュ値を入手します。ここでSTOREを使うのですが、key,valueのvalueにはファイルを共有しようとしている自分自身のノードIDと動画のハッシュ値を結合したものを入れます。keyにはとノードIDと動画のハッシュ値を結合して更にsha1関数にかけたハッシュ値を入れます。
次に先程の動画Aを入手するパターンを考えましょう。
動画Aのkeyを予め知っているとします、FIND_VALUEのkeyを動画のkeyとしてvalueを探します。valueを持っているノードがもし動画を持っていれば、そのノードに動画を送ってもらいます。もし持っていなければvalueに入っているノードIDをkeyとしてFIND_VALUEを行い、最終的にファイルを共有しようとしたオリジナルのノードに動画を送ってもらいます。動画をダウンロードできたら自身のハッシュテーブルに動画のkey,とvalueを登録し、今後、他のノードがこの動画を探索した時、自分に対してFIND_VALUEを送ってきた場合に動画ファイルを送り返せるようにします。
このようにしてハッシュテーブルに直接大きなファイルを置くことなく、ファイルを共有することができます。この方式だと、人気のあるファイルはすぐに見つかります。
ですが、人気のないファイルは見つからないか、もしくはオリジナルをアップロードしたノードがいなくなった上に誰もそのファイルをダウンロードしたことがなければネットワーク上から消滅するリスクがあります。
ですので、valueに直接ファイルを格納するパターンと、この項目で説明した間接的な情報を格納するパターンの使い分けを開発者は意識する必要があるでしょう。
まとめ、次回予告
今回はKademliaの解説と実装の前編としてKademliaのアルゴリズムの解説を行いました。次回では今回の各セクションと対応するように機能の実装をJavaScriptで行っていきます。
