在洪流kademlia路由表上實現find節點

Question

我已經在這個主題上回顧了許多文檔，但是有些東西不完全清楚。例如位洪流文件（http://www.bittorrent.org/beps/bep_0005.html）指出

路由表被細分成「桶」，每個覆蓋的空間的一部分 。一個空表有一個ID爲 min = 0，max = 2^160的桶。當具有ID「N」的節點插入到 表中時，它被放置在具有最大= N <最大的桶內。 空表只有一個存儲桶，因此任何節點都必須適合它。每個 存儲桶只能存放八個K節點，然後才能變爲「滿」。 當一個桶充滿已知的好節點時，除非我們自己的節點ID落入該桶的範圍內，否則不會再添加更多節點 。在那個 的情況下，該桶被兩個新桶替換，每個桶都有舊桶的 範圍的一半，舊桶的節點分配到兩個新桶中的 。對於只有一個 存儲桶的新表格，整個存儲桶始終會分成兩個新存儲桶，分別覆蓋 ，範圍爲0..2^159和2^159..2^160。

它與其他有關kademlia路由表的文檔有所不同，其中桶根據節點id的位前綴排列，但還有另一個令人困惑的事情。當我們回覆「查找節點」請求時，我們必須使用XOR操作找到8個最接近請求節點的節點。我看到一些實現只是通過執行異或操作的路由表中的每個項目，因此找到了8個最接近的項目。在我看來，CPU太浪費了。

一切都已在桶中。即使我們使用torrent文檔系統的建議，我們也可以更快地找到可能包含請求節點ID的桶，只需枚舉桶並檢查桶上的最小和最大數量即可。然後潛在的那個桶應該包含關閉的節點，但它們是最接近最近的節點，而不是XOR最近的節點（據我所知），這有點不同，但有點相似。

我跑了一個簡單的測試，使用從0到99的數字，我想找到8個XOR最接近的數字，他們在尋找的數字附近但不是靠近它。現在，考慮我們的桶，我想有可能桶中的所有節點ID都是最小的異常。所以，舉例來說，如果我們拿這個桶，從左邊和右邊一個拿一個，然後搜索XOR最接近的節點id，我們將找到我們正在尋找的東西，並且沒有必要通過路由中的所有節點表。

我是對的還是我錯過了什麼？

Answer 1

它與其他有關kademlia路由表的文檔有所不同，其中桶根據節點id的位前綴排列，但還有另一個令人困惑的事情。

bittorrent規範描述了一個路由表實現，它只能近似於kademlia paper中描述的路由表實現。實施起來比較容易，但也有一些缺點。

因此，例如，如果我們採取這種水桶，拿一個從左邊，一個從右邊並搜索XOR最接近的節點ID，我們會發現我們正在尋找，並沒有一點去通過路由表中的所有節點。

在兩種 - 充分，樹狀路由表執行和簡化BEP5變 - 每個桶可以被認爲是具有CIDR-like prefix（見this SO answer）由前綴比特的剷鬥覆蓋和掩模位計數。

在BEP5-變體中，每個桶的前綴只是從數組索引和節點自己的ID派生而來。由於存儲桶拆分/合併操作，樹狀表中的存儲桶必須跟蹤其前綴。

使用這些前綴，您可以找到涵蓋目標密鑰的存儲桶。

問題是桶不一定是滿的，如果你想發送，讓我們說20個節點在響應單個桶是不夠的。

因此，您必須以相對於目標密鑰的上升距離（XOR）順序來遍歷路由表（根據您自己的節點ID或自然距離排序）以訪問多個存儲桶。由於XOR距離度量在每個比特進位（XOR ==無進位加法）處摺疊，因此它不能很好地映射到任何路由表佈局。換句話說，訪問最近的桶不會這樣做。

Here's my implementation用於從樹形路由表中查找到特定目標密鑰的N個最近節點。

我認爲很多人只是遍歷整個路由表，因爲對於常規節點來說，它最多隻能包含幾十個桶，DHT節點看不到很多流量，所以只需要執行一些操作如果你在密集的，緩存友好的數據結構中實現這一點，那麼大部分實際上就是內存流量，而不是CPU指令進行一些XOR和比較。

I.e.全表掃描很容易實現。

---

我們假設我們有一個路由表，每個存儲桶有以下位前綴。這些字母用作方便的名字）。

A 000... 
B 00100... 
C 0010100... 
D 0010101000... 
E 0010101001... 
F 001010101... 
G 00101011... 
H 001011... 
I 0011... 
J 01... 
K 1... 

現在假設我們正在尋找這個目標的關鍵：

T = 0010011010111111001111100101011000001010010100001100100010011100000000100100000111001101100110110110101100010100111010111001101111110101001001001000100000001001 

另外，桶並不完全充分，或者我們需要比任何適合單個桶更多的條目，因此我們必須訪問多個存儲桶才能獲得所需數量。

現在，第一個要訪問的存儲區相當明顯，因爲它的前綴覆蓋了目標密鑰，所以它是B。

由於B的前綴長度爲5位，該存儲桶中的任何條目的異或距離爲T的00000???????...。 5個前綴位共享。

B是距離T最近的一個桶，這意味着不能有比相對距離更近的任何路由表條目00000...。相反，這意味着B以外的任何條目可具有的最小距離爲00001...。這意味着次最接近的桶必須覆蓋T xor 00001... -> 00101110101111110[...]。

涵蓋此的存儲桶是H。

H是不相鄰的B

最終 - 假設我們將要訪問6桶 - 訂單將是這樣的：

00100...  -> B 
001011...  -> H 
001010101... -> F 
0010101000... -> D 
0010101001... -> E 
00101011... -> G 

這似乎相當混亂。但是，如果我們繪製前綴至目標鍵的距離對於每個桶訪問它變得更加略明顯：

​​

所以算法如下：

1. 找到最初桶覆蓋靶向與目標密鑰（零掩模尾隨位）
2. 增量由前綴的至少顯著位的距離鍵
3. XOR剷鬥的前綴
4. 與目標鍵
5. XOR遞增的距離找到下一桶覆蓋XOR的關鍵
6. 轉到2

TL; DR：「只是看一個水桶左，一個右鬥」是不夠的。正確的算法相當複雜，整個表的線性掃描更容易實現。