iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 27
0

前言

前面介紹了兩個搭配Data Partitioning使用的DHT演算法 CHORDKademlia

今天特別拉出來介紹一下這個現在已經退流行的P2P應用 - BitTorrent。

BitTorrent

不知道現在還有沒有人還在用P2P下載檔案,必竟現在Streaming技術非常成熟,各種娛樂也不再是負擔不起的時代。但是BitTorrent從技術面探討仍然有非常多值得學習的地方。

如同之前所說,為了能夠將檔案放到網路上讓大家下載,有幾個主要的問題。

  1. 如果只存放一個檔案到系統的某個電腦,當該電腦下線檔案就不見了
    • 一種很直觀的想法就是Data Partitioning成好幾個Chunks然後再做Replication,存到多台電腦之上。
    • 這邊就可以利用DHT演算法來維護Data Chunks與Node的關係
  2. 當一個Client想要下載檔案時
    • 如何定位Data Chunks位置?
    • 整個系統的每個Nodes都在上傳下載,怎樣可以最快讓大家都完成任務?

而BitTorrent就是一個綜合了各種策略的P2P檔案分享分散式系統。

組成

  1. Web server: 提供Client下載.torrent檔
  2. Tracker: 維護一個List內含正在下載或是上傳檔案的Clients
  3. Client: P2P裡面的一個Peer可以下載也可以上傳檔案

Client(Peer)

Client也分成兩種

  1. Leechers: 下載檔案的Client,而他們已經下載的Data Chunks也可以再提供別的Client下載。
  2. Seeders: 已經完成下載的Client,可以提供所有的Data Chunks給別的Client下載

Swarming

為了增加下載速度與維護檔案完整並備份

  • 檔案被分成好幾個Data Chunks

  • 下載可以指定從某個Peers那邊下載特定的Data Chunks

  • Swarming:

    • 因此Client下載檔案時,可以同時平行的從好幾個Peers下載不同的 Data Chunks
    • 我們稱 Swarm 為一組正在下載同一個檔案的 Clients(Peers)
    • 而若Client下載了某個Data Chunks的,他可以立即提供該Data Chunks給別的Peer下載
  • 此種方法可以做到快速將Data Chunks複製分散到好幾個Peers身上,避免某些Peer下線後Data Chunks消失,後續的Clients無法下載完整檔案。

而因為P2P系統 Peers會不斷加入與離開,而目前每一個Peers手上存的Data Chunks為了避免不斷重新分配,且紀錄彼此位置,就可以使用Kademlia這種Consistenct Hashing來處理。

.torrent file

有經驗的都知道下載檔案最重要的就是BT種子(?
一般說的就是這個.torrent檔,究竟裡面有什麼東西呢?

  • Tracker的URL位置: 通過Tracker才知道有哪些Peers也在上傳下載該檔案
  • 檔名與簡介
  • Data Chunks大小 (一般一個chunks為512kB)
  • Data Chunks數量
  • 每一個Data Chunks的SHA-1 Hash值,用來比對正確性

BitTorrent下載步驟

  1. 使用者首先下載 .torrent,然後塞給某個BitTorrent Client (迅X?)
  2. 從.torrent裡找到Tracker,從那裡取的所有其他 Peers (Leechers/Seeders) 的位置
  3. Client根據資訊詢問每一個Peers手上手哪些Data Chunks
  4. 根據實作的不同策略,向不同的Peers請求不同的Data Chunks

Chunk selection policy

  • Rarest First: 優先下載稀有的Data Chunks

    • 可以增加此檔案在此P2P系統的完整性,以避免某個有完整檔案的Peer下線且也沒有其他Peer有此Data Chunks,那後續所有Peer就不可能下載完整的檔案
  • Random First: 第一個Data Chunks隨機選則下載

    • 雖說Rarest First有很大的好處,但也因此可想而知會有很多Peers搶著要跟有稀缺Data Chunks的Peer下載檔案,導致下載速度過慢
    • 對於剛開始下載的Client,因為手上一個Data Chunks都沒有,因此建議隨機選一個先下載,就可以越早開始提供Data Chunks給別人下載
    • 當手上有Data Chunks也可以服務其他的Peers時,在切換成Rarest First
  • Endgame Mode: 當一個檔案下載到最後只差一兩個Data Chunks,就不特別找某個Peers下載,而是直接Broadcast請求給所有的Peers,以避免花過久的時間下載最後一兩個Data Chunks,更快成為有完整檔案的Seeders

總結

以上就是BitTorrent的介紹,雖然現在已經很少有人在下載BT了。
但是這樣的一種檔案分享系統,還是值得學習做一個參考。

Reference:

  • TU Dresden - Internet and Web Application - File Sharing

上一篇
Day 26 - Data Partitioning - Distributed Hash Table and Consistent Hashing - Kademlia
下一篇
Day 28 - Cloud Computing - Platform as a Service - Kubernetes (上)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言