寫在前面的話
Stay Hungry Stay Foolish?。?！
每天進步一點點?。?！
《每日一讀》是博主每日學(xué)習(xí)的一篇文章所記錄的筆記，大多數(shù)是提取文章中關(guān)鍵內(nèi)容而成；文章類型不限，內(nèi)容不限。
意義：培養(yǎng)自己的閱讀能力，學(xué)習(xí)更多的知識
鄭重聲明：如果涉及到文章侵權(quán)深感抱歉，請及時聯(lián)系我我會第一時間刪除，謝謝?。?/p>
總結(jié)
收獲：
- 去中心化的節(jié)點通信：很好的將現(xiàn)實中找人的模式來實現(xiàn)。
- 距離計算使用XOR的巧妙之處
正文
背景
三位IT大神由于對P2P網(wǎng)絡(luò)及分布式系統(tǒng)感興趣，于是就用Ruby開發(fā)了BitTorrent(BT)的系統(tǒng)。
ps：值得學(xué)習(xí)的精神，從事IT行業(yè)的人員不得不具備的一個元素，否則很容易被后浪給拍死
研究
P2P網(wǎng)絡(luò)的兩代網(wǎng)絡(luò)架構(gòu)：
1） 集中式系統(tǒng)：通過中央索引服務(wù)器來索引到所有文件信息，這里舉例的是Napster
- 中央索引服務(wù)器：包含所有Node持有的文件信息
- Node節(jié)點：存儲了文件信息
【缺點】
- 中央服務(wù)器易受攻擊
- 存在單點故障的風(fēng)險
- 缺乏可擴展性
2）去中心化系統(tǒng)：每個Node節(jié)點充當(dāng)客戶端/服務(wù)端，維護自己的文件查找索引片段；Node之間可通信
典型系統(tǒng)：BitTorrent、Gnutella、Freenet
建設(shè)
P2P網(wǎng)絡(luò)構(gòu)建的基礎(chǔ)條件：
- 分布式哈希表（DHT）
- 文件切分/索引機制
- 節(jié)點通信機制
分布式哈希表
幾種分布式哈希表
這里選用的是Kademlia，原因：
- 普及率
- 最簡單的遠(yuǎn)程過程調(diào)用
- 信息的自動傳播
涉及到的概念：
- 節(jié)點
- 路由表
- 桶(buckets)
- 異或距離
- 路由算法
- 遠(yuǎn)程過程調(diào)用(remote procedure calls, RPC)
Kademlia
一個Kademlia由許多節(jié)點組成
1）節(jié)點信息：
- 具有唯一的160位ID
- 維護包含其他節(jié)點聯(lián)系信息的路由表：路由表被劃分為
桶，其包含與當(dāng)前節(jié)點的特定距離的節(jié)點的聯(lián)系信息- 聯(lián)系信息包含其他節(jié)點的ID、IP地址和端口號
- 維護較大的分布式哈希表中那些自己的段
- 通過4個遠(yuǎn)程過程調(diào)用與其他節(jié)點通信
2）節(jié)點通信：
-
PING：探活 -
FIND NODE：需要特定節(jié)點的ID；- 查找過程：路由表查找，并返回一組最接近的該ID的聯(lián)系節(jié)點
-
FIND VALUE：需要特定文件的ID；- 查找過程：從分布式哈希表段中查找，找到則返回value；否則返回最接近該文件ID的聯(lián)系節(jié)點列表
-
STORE：在分布式哈希表段中存儲key/value對(file_id/location)，并更新彼此的聯(lián)系信息
3）尋找對等點和文件
如果一個節(jié)點要從網(wǎng)絡(luò)中檢索一條信息（一個文件），其過程為：
- 該節(jié)點發(fā)送 FIND VALUE 的遠(yuǎn)程過程調(diào)用到它自己的聯(lián)系節(jié)點子集，這些聯(lián)系節(jié)點的 ID 與它要查找的文件的 ID“最為接近”。
- 如果任何接收節(jié)點在其分布式哈希表段中有這個 ID，則它們將返回相應(yīng)的 value，
- 否則，它們將返回更接近所查詢的 value 的節(jié)點列表。
4）距離的計算
節(jié)點之間的距離定義為節(jié)點ID的按位異或(XOR)
注：之后的運算基于4位秘鑰空間的節(jié)點（只有0~15的ID是可能的）
XOR度量的一個重要特征：如果節(jié)點 ID 和當(dāng)前節(jié)點的 ID 的二進制表示所共有的位相同個數(shù)越多，那么計算得到的 XOR 結(jié)果就越小。
ps：使用XOR最大的意義莫過于能更好的劃分桶，使得一個桶中的ID具有連續(xù)性，聯(lián)系程度越高
5）網(wǎng)絡(luò)及路由表
Kademlia網(wǎng)絡(luò)是由二叉樹構(gòu)成，其查找的時間復(fù)雜度為O(log n)
路由表：之前提到路由表被劃分為桶，桶劃分的過程：
劃重點：每個桶中包含了一定距離的節(jié)點，而距離就是共享位長度，是通過節(jié)點ID和當(dāng)前ID進行XOR運算得到
舉個栗子，假設(shè)當(dāng)前節(jié)點ID為11，則桶分布為：
- bukets0：0-7
- bukets1：12-15
- bukets2：8-9
- bukets3：10
解釋：其 ID 與當(dāng)前節(jié)點共享前 3 位前綴的節(jié)點存儲在一個桶中，而 ID 與當(dāng)前節(jié)點共享前 2 位前綴的節(jié)點存儲在另一個桶中，以此類推。
11的二進制為：1011
10的二進制為：1010，與1011共享位為3位
8-9共享位為2位
12-15共享位為1位
0-7共享位為0位
6）文件切分和檢索
文件切分是將文件切分成更小的片段，命名為切片，并將 files/names 記錄在一個清單文件（即種子）中，這樣它們就可以按照適當(dāng)?shù)捻樞驒z索和重新合并。
文件切分提高了 P2P 網(wǎng)絡(luò)的分布性和可靠性，因為多個節(jié)點可以存儲共享文件的部分或全部切片。如果包含切片下載信息的節(jié)點離線了，此時可以從不同的源檢索該切片信息。
文件切分還可以節(jié)省網(wǎng)絡(luò)帶寬，共享潛在大文件的負(fù)載分布在許多節(jié)點中。
過程：
- 計算文件內(nèi)容的
SHA1哈希值作為ID，ID被用作種子的文件名，擴展名為”.xro“ - 原始文件被切分成
1MB塊,如果文件小于1MB，則切分為原始文件大小的50% - 切片被寫入磁盤，名稱即為其內(nèi)容的
SHA1哈希值；并將名稱按順序?qū)懭敕N子文件，以及原始文件名和文件大小 - 種子和切片位置信息通過 STORE 遠(yuǎn)程過程調(diào)用廣播給對等節(jié)點。對于每個 shard/manifest，宿主節(jié)點在自己的路由表中查找與文件 ID 最接近的節(jié)點。這些對等節(jié)點都接收包含文件的 ID 和位置的 STORE 遠(yuǎn)程過程調(diào)用。
種子內(nèi)容json格式：
{
// 真實的文件名
"file_name" : "",
// 文件大小
"length" : 1000,
"pieces" : [
// 切片順序?qū)懭氲腟HA1哈希值
]
}
開發(fā)
開發(fā)策略：從本地環(huán)境模擬并擴展網(wǎng)絡(luò)應(yīng)用到真實網(wǎng)絡(luò)
1）測試模式：
- 本地沙箱測試
-
Fake Network Adapter(偽網(wǎng)卡)：本質(zhì)上是一個由其他節(jié)點組成的數(shù)組，帶有一些用于查找和遠(yuǎn)程過程調(diào)用代理的方法。
2）HTTP遠(yuǎn)程調(diào)用
-
Real Network Adapter （真網(wǎng)卡）:從所提供的聯(lián)系節(jié)點信息和對應(yīng)于遠(yuǎn)程過程調(diào)用的路由中列出的 IP / 端口處理一個 HTTP Post 請求，可能包括請求主體中的相關(guān)數(shù)據(jù)——請求節(jié)點的聯(lián)系信息、查詢信息等。
3）RPC/HTTP在互聯(lián)網(wǎng)環(huán)境下傳遞
-
Ngrok：第三方隧道服務(wù)
4）靈活的節(jié)點實例化和啟動腳本
- 節(jié)點廣播機制
系統(tǒng)架構(gòu)
頂級對象是 XorroNode，它是一個模塊化的 Sinatra 應(yīng)用程序。
每個 XorroNode 包含：
- 一個單獨的 Kademlia 節(jié)點，負(fù)責(zé)維護自己的路由表和分布式哈希表。
- 用于向其他節(jié)點發(fā)起遠(yuǎn)程過程調(diào)用的網(wǎng)卡。
- 用于從其他節(jié)點、Web UI 和文件傳輸接收遠(yuǎn)程過程調(diào)用的 Sinatra 端點。
- 用于文件接收、切分和清單文件的創(chuàng)建。
