質問: Kademliaの論文を読んでいて、`k-bucket`の説明に関してよく分からない箇所がありました。 2.2 の **Node state** では、 > > For each 0≤i<160, every node keeps a list of < IP address, UDP port, > NodeID > triples for nodes of distance between 2i and > 2i+1 from itself. We call these lists k-buckets. > > > 各ノードに160個のk-bucketがあり、ノードとのIDの距離によってルーティング情報が各k-bucketに割り当てられていると読めます。 しかし、後の2.4 **Routing table** のセクションでは、 > > Initially, a node *u*’s routing tree has a single node — one k-bucket > covering entire ID space. When u learns of a new contact, it attempts > to insert the contact in the appropriate k-bucket. If that bucket is > not full, the new contact is simply inserted. Otherwise, if the > k-bucket’s range includes *u*’s own node ID, then the bucket is split > into two new buckets, the old contents divided between the two, and > the insertion attempt repeated. > > > 初期状態では各ノードに1つのk-bucketしかなく、距離ではなくIDそのものを基準として割り当てを行うことになっています。 このように、k-bucketに関する説明が2箇所で異なっている理由が読み取れず混乱しているのですが、この2つのk-bucketはDHT上で別の役割をしているということなのでしょうか。それとも単なるテーブルの実装方法の違いということなのでしょうか。
回答: 論文を今読んだだけの理解レベルですが: 2.4 Routing Table は、k-bucketを動的に増やす実装の一例である、と考えればよいと思います。 Goによる実装例を解説した記事では、初めから全てのk-bucketを持っておくという実装になっています (`Update`関数)。そして、ノードを探索する時点で、そのノードが入っているはずのk-bucketから徐々に近傍のk-bucketに探索対象範囲を広げるということをしています (`FindClosest`関数)。 > > 2.2 の **Node state**: 各ノードに160個のk-bucketがあり、ノードとのIDの距離によってルーティング情報が各k-bucketに割り当てられていると読めます。 > > > その通りだと思います。これは、k-bucketの概念を説明するため、仮にルーティング情報が全充填された場合の状態を説明したものと思います。 出だしの一文で「ノード探索用の通信をルーティングするため、各ノードに既知のノード情報を保存する」("Kademlia nodes store contact information about each other to route query messages.") とあるので、2.2 の説明内容はルーティングに使うものであると読めます。つまり 2.4 Routing Tableと同じ用途のものであると考えられます。 > > 2.4 **Routing Table**: 初期状態では各ノードに1つのk-bucketしかなく、 > > > ここでは、あるノードが初期状態からルーティングテーブルを段々埋めていく手順を説明しています。初期状態では、既知のノードは自分自身しかないので、初めはk-bucketを1つだけ持っておけば十分、という実装です。 ``` 初期状態: 自分 |--------------------------------o| <- 全ノードの空間 (右にいくほど近い) 仮k-bucket [2^0-2^160) とても遠いノードを追加: |-------o--------|---------------o| k-bucket(i=159) 仮k-bucket [2^0-2^159) ``` 初期状態のk-bucketを「仮」としたのは私の個人的解釈で、論文ではそう書かれてはいません。2.2 節で「各k-bucketは距離 2i から 2i+1 の範囲を担当する」としているのとダイレクトに矛盾するので、説明不足なのだと思います。 > > 距離ではなくIDそのものを基準として割り当てを行うことになっています。 > > > Kademliaでは、ノード間の距離がIDによって決まるので、「ID空間 (ID space)」を距離空間と同じ意味で使っているように思います。この節の冒頭の段落で: > > Each *k*-bucket contains nodes with some common prefix of their IDs. > > 各k-bucketに含まれるノードは、IDの前半部分が一定の長さで共通したものになる。 > > > とあるように、ノードのIDを見れば、どのk-bucketに入れればいいかが決まります。というのも、 * IDの高次ビットが共通している場合、 * → その共通部分は XOR の結果がゼロになる * → そのノードとの距離は一定の範囲内に限定される: 最大値は共通部分から下のビットが全て 1 になる場合、最小値は共通部分の次のビット以外が全て 0 になる場合 * → 割り当てるべき k-bucket が決まる (各k-bucketが担当する距離の範囲は 2i ~ 2i+1、と2.2で定義されている) からです。ノード自身のIDとの比較なので、どのIDがどのk-bucketに入るかはノードによって違うということにはなります。 ``` self 0 1 0 0 ..(160個).. 1 0 1 0 other 0 1 1 1 ..(160個).. 0 0 0 0XOR 0 0 1 1 ..(160個).. 1 0 1 0 = 距離 = 2^157~2^158 k-bucket u u u u ..(160個).. u u u u ^このk-bucketにotherが入る ```