每日一讀-如何從頭開始構(gòu)建類似BitTorrent的P2P網(wǎng)絡(luò)

寫在前面的話

Stay Hungry Stay FoolishH搜俊M浮!
每天進(jìn)步一點點S┨i夏ā!

《每日一讀》是博主每日學(xué)習(xí)的一篇文章所記錄的筆記惕味,大多數(shù)是提取文章中關(guān)鍵內(nèi)容而成楼誓;文章類型不限,內(nèi)容不限名挥。

意義:培養(yǎng)自己的閱讀能力疟羹,學(xué)習(xí)更多的知識

鄭重聲明:如果涉及到文章侵權(quán)深感抱歉,請及時聯(lián)系我我會第一時間刪除禀倔,謝謝i凇!

總結(jié)

收獲:

  1. 去中心化的節(jié)點通信:很好的將現(xiàn)實中找人的模式來實現(xiàn)救湖。
  2. 距離計算使用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

  1. 中央索引服務(wù)器:包含所有Node持有的文件信息
  2. Node節(jié)點:存儲了文件信息
中心化

【缺點】

  • 中央服務(wù)器易受攻擊
  • 存在單點故障的風(fēng)險
  • 缺乏可擴(kuò)展性

2)去中心化系統(tǒng):每個Node節(jié)點充當(dāng)客戶端/服務(wù)端邑闺,維護(hù)自己的文件查找索引片段跌前;Node之間可通信

典型系統(tǒng):BitTorrentGnutella检吆、Freenet

去中心化

建設(shè)

P2P網(wǎng)絡(luò)構(gòu)建的基礎(chǔ)條件:

  • 分布式哈希表(DHT)
  • 文件切分/索引機(jī)制
  • 節(jié)點通信機(jī)制

分布式哈希表

幾種分布式哈希表

這里選用的是Kademlia舒萎,原因:

  1. 普及率
  2. 最簡單的遠(yuǎn)程過程調(diào)用
  3. 信息的自動傳播

涉及到的概念:

  • 節(jié)點
  • 路由表
  • 桶(buckets)
  • 異或距離
  • 路由算法
  • 遠(yuǎn)程過程調(diào)用(remote procedure calls, RPC)

Kademlia

一個Kademlia由許多節(jié)點組成

1)節(jié)點信息:

  • 具有唯一的160位ID
  • 維護(hù)包含其他節(jié)點聯(lián)系信息的路由表:路由表被劃分為,其包含與當(dāng)前節(jié)點的特定距離的節(jié)點的聯(lián)系信息
    • 聯(lián)系信息包含其他節(jié)點的ID蹭沛、IP地址和端口號
  • 維護(hù)較大的分布式哈希表中那些自己的段
  • 通過4個遠(yuǎn)程過程調(diào)用與其他節(jié)點通信
Node節(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ò)中檢索一條信息(一個文件)掏缎,其過程為:

  1. 該節(jié)點發(fā)送 FIND VALUE 的遠(yuǎn)程過程調(diào)用到它自己的聯(lián)系節(jié)點子集皱蹦,這些聯(lián)系節(jié)點的 ID 與它要查找的文件的 ID“最為接近”。
  2. 如果任何接收節(jié)點在其分布式哈希表段中有這個 ID眷蜈,則它們將返回相應(yīng)的 value沪哺,
  3. 否則,它們將返回更接近所查詢的 value 的節(jié)點列表酌儒。

4)距離的計算
節(jié)點之間的距離定義為節(jié)點ID的按位異或(XOR)

注:之后的運(yùn)算基于4位秘鑰空間的節(jié)點(只有0~15的ID是可能的)

XOR

XOR度量的一個重要特征:如果節(jié)點 ID 和當(dāng)前節(jié)點的 ID 的二進(jìn)制表示所共有的位相同個數(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進(jìn)行XOR運(yùn)算得到

舉個栗子鸥印,假設(shè)當(dāng)前節(jié)點ID為11勋功,則桶分布為:

  1. bukets0:0-7
  2. bukets1:12-15
  3. bukets2:8-9
  4. bukets3:10

解釋:其 ID 與當(dāng)前節(jié)點共享前 3 位前綴的節(jié)點存儲在一個桶中,而 ID 與當(dāng)前節(jié)點共享前 2 位前綴的節(jié)點存儲在另一個桶中辅甥,以此類推酝润。

11的二進(jìn)制為:1011
10的二進(jìn)制為:1010燎竖,與1011共享位為3位
8-9共享位為2位
12-15共享位為1位
0-7共享位為0位
image.png

6)文件切分和檢索

文件切分是將文件切分成更小的片段璃弄,命名為切片,并將 files/names 記錄在一個清單文件(即種子)中构回,這樣它們就可以按照適當(dāng)?shù)捻樞驒z索和重新合并夏块。
文件切分提高了 P2P 網(wǎng)絡(luò)的分布性和可靠性,因為多個節(jié)點可以存儲共享文件的部分或全部切片纤掸。如果包含切片下載信息的節(jié)點離線了脐供,此時可以從不同的源檢索該切片信息。
文件切分還可以節(jié)省網(wǎng)絡(luò)帶寬借跪,共享潛在大文件的負(fù)載分布在許多節(jié)點中政己。

文件切分

過程:

  1. 計算文件內(nèi)容的SHA1哈希值作為ID,ID被用作種子的文件名掏愁,擴(kuò)展名為”.xro“
  2. 原始文件被切分成1MB塊,如果文件小于1MB歇由,則切分為原始文件大小的50%
  3. 切片被寫入磁盤,名稱即為其內(nèi)容的SHA1哈希值果港;并將名稱按順序?qū)懭敕N子文件沦泌,以及原始文件名和文件大小
  4. 種子和切片位置信息通過 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)境模擬并擴(kuò)展網(wǎng)絡(luò)應(yīng)用到真實網(wǎng)絡(luò)

1)測試模式:

  • 本地沙箱測試
  • Fake Network Adapter(偽網(wǎng)卡):本質(zhì)上是一個由其他節(jié)點組成的數(shù)組,帶有一些用于查找和遠(yuǎn)程過程調(diào)用代理的方法葡兑。
image.png

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)系信息、查詢信息等千劈。
image.png

3)RPC/HTTP在互聯(lián)網(wǎng)環(huán)境下傳遞

  • Ngrok:第三方隧道服務(wù)
image.png

4)靈活的節(jié)點實例化和啟動腳本

  • 節(jié)點廣播機(jī)制

系統(tǒng)架構(gòu)

系統(tǒng)架構(gòu).png

頂級對象是 XorroNode镜撩,它是一個模塊化的 Sinatra 應(yīng)用程序。

每個 XorroNode 包含:

  • 一個單獨的 Kademlia 節(jié)點队塘,負(fù)責(zé)維護(hù)自己的路由表和分布式哈希表袁梗。
  • 用于向其他節(jié)點發(fā)起遠(yuǎn)程過程調(diào)用的網(wǎng)卡。
  • 用于從其他節(jié)點憔古、Web UI 和文件傳輸接收遠(yuǎn)程過程調(diào)用的 Sinatra 端點遮怜。
  • 用于文件接收、切分和清單文件的創(chuàng)建鸿市。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末锯梁,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子焰情,更是在濱河造成了極大的恐慌陌凳,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,817評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件内舟,死亡現(xiàn)場離奇詭異合敦,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)验游,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,329評論 3 385
  • 文/潘曉璐 我一進(jìn)店門充岛,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人耕蝉,你說我怎么就攤上這事崔梗。” “怎么了垒在?”我有些...
    開封第一講書人閱讀 157,354評論 0 348
  • 文/不壞的土叔 我叫張陵蒜魄,是天一觀的道長。 經(jīng)常有香客問我场躯,道長谈为,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,498評論 1 284
  • 正文 為了忘掉前任推盛,我火速辦了婚禮峦阁,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘耘成。我一直安慰自己榔昔,他們只是感情好驹闰,可當(dāng)我...
    茶點故事閱讀 65,600評論 6 386
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著撒会,像睡著了一般嘹朗。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上诵肛,一...
    開封第一講書人閱讀 49,829評論 1 290
  • 那天屹培,我揣著相機(jī)與錄音,去河邊找鬼怔檩。 笑死褪秀,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的薛训。 我是一名探鬼主播媒吗,決...
    沈念sama閱讀 38,979評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼乙埃!你這毒婦竟也來了闸英?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,722評論 0 266
  • 序言:老撾萬榮一對情侶失蹤介袜,失蹤者是張志新(化名)和其女友劉穎甫何,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體遇伞,經(jīng)...
    沈念sama閱讀 44,189評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡辙喂,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,519評論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了赃额。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片加派。...
    茶點故事閱讀 38,654評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖跳芳,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情竹勉,我是刑警寧澤飞盆,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布,位于F島的核電站次乓,受9級特大地震影響吓歇,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜票腰,卻給世界環(huán)境...
    茶點故事閱讀 39,940評論 3 313
  • 文/蒙蒙 一城看、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧杏慰,春花似錦测柠、人聲如沸炼鞠。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,762評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽谒主。三九已至,卻和暖如春赃阀,著一層夾襖步出監(jiān)牢的瞬間霎肯,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,993評論 1 266
  • 我被黑心中介騙來泰國打工榛斯, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留观游,地道東北人。 一個月前我還...
    沈念sama閱讀 46,382評論 2 360
  • 正文 我出身青樓驮俗,卻偏偏與公主長得像备典,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子意述,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 43,543評論 2 349

推薦閱讀更多精彩內(nèi)容