KademliaのkBucketを利用している

• 距離はXOR

• kBucketでRootingTableを構築している

Torrentで採用されているDHTは、「Kademlia」と呼ばれているものです。本章では、KademliaのなかでもkBucketを用いたRootingTableについて紹介して行きます。

XORで距離を定義する。

前章で説明した通り、DHTでは距離を定義する必要がありました。Kademliaでは、この距離にxorを利用します。xorの距離とはどのようなものでしょうか?具体的にみていきましょう。

- 数字は2進数で表現できる

コンピュータプログラムでは、数字を2進数で表現できる事はご存じてじょうか。2進数とは、1と0のみで数字を表す方法の事で、256は二進数で、11111111 と表現できます。同様に、1 は 00000001、2は00000010、3は00000011、5は、0000101と表現できます。 例えば、00000011を10進数にもどす場合は、「1 + (0×2) + (1×(2×2))=5」と計算します。同様に10進数に戻す場合は、00000010は、「0+ (1×2)=2」と計算できます。

- XORはこの二進数にした値について行う

XOR距離は、この2進数に直した値にxorをする事をいいます。AとBの xor距離をとる事を、 A ^ B と書く事にしましょう。

ますば、xorとは何か? 与えられ値の何れかが、1の時、1となる計算方法のことです。

値A	値B	A ^ B
1	1	0
1	0	1
0	1	1
0	0	0

これを、おのおの桁ごとに計算していきます。 「256(11111111) ^ 3(00000011) --> 252 (11111100)」、同様に「252 (11111100) ^ 256(11111111) --> 3(00000011)」といった感じで計算できます。

xorは対称距離

xorは、A ^ B と B ^ A は同じ値になります。例えば、「256(11111111) ^ 3(00000011) --> 252 (11111100)」「 3(00000011) ^ 256(11111111) --> 252 (11111100)」といった感じです。

xorを距離として使うと、Peer間の距離が、お互いに同じになります。 これは。 Peer A から見た Peer B も Peer B から見た Peer A も同じ距離になるわけです。

これと、kBucket の RootingTable が合わさるともっと、綺麗な特徴が見えてきます。

kBucket の RootingTableを利用している

前章で、DHTでは各PeerがPeerの一覧を持っいると説明しました。そして、その一覧には偏りがあり自分に近いPeerについてはより詳しいのでした。Kademliaでは、kBucketのRootingTableでPeerの一覧を管理しています。 kBucketは、K個のPeerの情報をグローピングする入れ物です。それだけです。K個以上保持する事ができないので、それ以上のPeerを追加するには、kBucketから不要なPeerを削除する必要があります。

Kademlia の RootingTableは、0〜160の161個のkBucketを所持する事ができます。それぞれのkBucketは、Peerからの距離が、2の0乗より小さい、2の1乗より小さい、2の2乗より小さい.....2の160乗より小さい値を所持する事がでます。

ちょっと複雑ですね。具体的に見ていきましょう。

図に直すと直感的な構造をしている

まずは、具体的にXOR距離がどのようなものか見ていきましょう。IDとして使用可能な160bit(20byte)を扱って説明するのは助長なので、ここでは、3bitのIDとして説明していきます。 本質は扱うIDに依存しませんので、気にせずに読み進めてください。

値	2進数	A ^ 010	table index
0	000	2	2
1	001	3	2
2	010	0	0
3	011	1	1
4	100	6	3
5	101	7	3
6	110	4	3
7	111	5	3

010 の値を持つPeerとしてDHTに参加する場合について、上記の表にまとてみました。

各値に応じて、xor距離、どのkBucketに記録されるかが解るようにしました。

例えば、ID 010 のPeerとのxor距離は 0 です。そして、0番目のkBucketに格納されます。 同IDの場合の説明は当然すぎるので、IDが101の場合も見てみましょう。Peerとのxor距離は 7、 4番目のkBucketに格納されます。

良いだすかね。格納するkBucketの位置の求め方が難しかったかもしれません。xorの値によって決まり、「0, 1, 2〜4, 4〜8」という範囲で0〜3のkBucketに選別されます。

次は図で見てみましょう。どうでしょうか。各Peerごとに、kBucketに格納される位置は直感的な配置になっているのではないでしょうか? 枝が移動するごとにの、格納するindexが大きくなっているのが解るでしょう。

このように、xor距離は、図形的に見ると直感的で合理的な構造になっているのです。

Kyorohiro work

http://kyorohiro.strikingly.com