深度探秘

沒有老闆，大家都是員工也都是客人

Peer-to-Peer 到底是什麼

我們最熟悉的網路模式是 client-server（用戶端-伺服器）：你的瀏覽器（client）去跟某台強大的伺服器要資料。所有資源都集中在伺服器這一邊。

但 peer-to-peer（P2P，點對點） 完全翻轉了這個想法：

P2P 的目標是消除對中央伺服器的需求，靠著網路邊緣那些一般人的個人電腦，把資料與資源大規模地分享出去。

在 P2P 裡，每一台參與的電腦都叫做一個 peer（對等節點），它們有幾個共同特徵：

• 每個使用者都貢獻資源：你想用別人的東西，自己也得拿出儲存空間、頻寬或運算力。
• 所有節點功能對等：雖然各自貢獻的多寡可能不同，但每個節點的能力與責任是一樣的，沒有誰天生比較特別。
• 不依賴中央管理：系統能正確運作，不需要任何由單一機構集中管理的設備。
• 可提供一定程度的匿名性給資源的提供者與使用者。

換句話說，P2P 就是一群地位平等的電腦，互相幫忙、共同撐起一個服務。

生活妙喻

社區共享冰箱 vs 便利商店

便利商店與社區共享冰箱

想像兩種拿食物的方式：

• client-server 像便利商店：所有商品都放在店裡，店家負責進貨、管理、結帳。你只是顧客，只負責拿。店越大，能服務的人越多，但一旦店面塞爆或停電，大家就都沒得買了。
• P2P 像社區共享冰箱：每戶人家都把自己多的食材放進公用冰箱，也可以去拿別人放的。沒有「老闆」，每一戶既是提供者也是取用者。

這個比喻剛好對應 P2P 的特徵：

而且有個好處：就算某幾戶搬走了，冰箱裡別人放的東西還在，服務不會整個垮掉。

實用超能力

為什麼要這麼麻煩？因為規模

P2P 解決的真實問題：擴展性

為什麼不乾脆把伺服器蓋大一點就好？因為 client-server 有兩個天花板：

1. 管理與故障成本：所有主機都得由服務提供者自己擁有與管理，電腦一多，管理和修復的成本就會主導一切。
2. 網路頻寬限制：單一伺服器站點能拉到的實體頻寬有限，再多人連也擠不進來。

P2P 把這個問題分散掉。它的設計目標是：

打造一個完全去中心化、自我組織的服務，隨著電腦加入與離開，動態地把儲存與運算負載平衡到所有參與的電腦上。

flowchart TD
  A[使用者需求成長到全球規模] --> B{用 client-server}
  B --> C[伺服器與頻寬成為瓶頸]
  A --> D{用 P2P}
  D --> E[把負載分散到數十萬台個人電腦]
  E --> F[去中心化 自我組織 動態負載平衡]

真實例子：當寬頻普及後，大量桌機 24 小時開機上網，就成了適合分享資源的平台。SETI@home 就靠全球 391 萬台志願者電腦的零碎運算力，分析無線電望遠鏡資料尋找外星訊號，創下當時最大單一運算紀錄。這就是 P2P 的超能力——把散落各處的閒置資源聚沙成塔。

深度探秘

用內容的指紋當名字

GUID：用安全雜湊產生的全球唯一名字

P2P 系統裡的資源（檔案、資料物件）要怎麼命名？答案是 GUID（globally unique identifier，全球唯一識別碼）。

GUID 通常是把資源的部分或全部內容丟進一個安全雜湊函數（secure hash）（例如 SHA-1）算出來的值。

安全雜湊有個神奇特性：內容只要差一點點，算出的雜湊值就完全不同；而且幾乎不可能找到兩份不同內容算出相同雜湊。這帶來一個關鍵好處：

• 自我認證（self-certifying）：客戶端拿到資源後，可以自己重算一次雜湊，跟 GUID 比對。一致就代表內容沒被竄改。

這招很厲害，因為 P2P 的資料是存在不受信任的陌生人電腦上的，自我認證讓你不必信任存放者也能驗證內容。

但天下沒有白吃的午餐：

因為 GUID 是從內容算出來的，一旦內容改變，雜湊值就變了，原本的 GUID 就失效。所以這招要求資源的內容是**不可變（immutable）**的。

這就是為什麼 P2P 儲存系統「天生最適合存不可變的物件」，例如音樂、影片這類發布後就不再修改的檔案。

生活妙喻

封蠟印章與會變心的菜單

蓋了封蠟印章的信

把 GUID 想成一封信的封蠟印章：

• 你把信的內容拿去蓋一個獨一無二的印章（雜湊），任何人收到信都可以檢查印章對不對。
• 只要有人偷改信的一個字，印章就對不起來了——你立刻知道信被動過手腳。這就是自我認證。

但這個印章有個前提：信的內容不能改。一旦你想改信，就得重蓋一個全新的印章（新的 GUID），舊印章就作廢了。

所以這套機制：

• 對不會再改的東西超好用：一首歌、一部電影，發布後內容固定，封蠟印章永遠有效。
• 對會一直改的東西很麻煩：像一份每天更新的菜單，每改一次就要換印章，所有指著舊印章的目錄全都要跟著更新。

這正是為什麼課本說 P2P 儲存「天生適合不可變物件」。要存會變的資料，得另外請『可信的伺服器』來管理版本（OceanStore、Ivy 就是這樣做）。

實用超能力

看懂 P2P 的三代演進史

P2P 發展的三個世代

了解這段演進史，能幫你把整章後面的內容串起來：

flowchart TD
  A[第一代 Napster] --> B[中央索引 找檔案 檔案存使用者電腦]
  C[第二代 Gnutella Freenet Kazaa BitTorrent] --> D[分散式索引 更高擴展性 匿名 容錯]
  E[第三代 中介軟體 Pastry Tapestry CAN Chord] --> F[與應用無關 保證有限跳數內送達 結構化放置副本]

第三代的關鍵突破是：它保證在有界的網路跳數內把請求送到，並有結構地把副本放在可用主機上，同時考慮主機的不穩定、可信度與負載平衡。後面幾章我們就會深入第三代的 Pastry 與 Tapestry。

深度探秘

中央索引 + 邊緣檔案的混合招式

Napster 怎麼運作

Napster 在 1999 年推出，是第一個爆紅的 P2P 檔案分享服務，巔峰時有數百萬註冊用戶、數千人同時交換音樂。它的設計很巧妙：

索引集中、檔案分散——Napster 用一個（有複製的）中央索引記錄『誰有什麼檔案』，但實際的音樂檔案存在使用者自己的電腦上。

它的運作可以拆成五個步驟：

sequenceDiagram
  participant C as 客戶端
  participant S as Napster 索引伺服器
  participant P as 持有檔案的對等節點
  C->>S: 1 查詢檔案位置
  S->>C: 2 回傳擁有該檔案的對等節點清單
  C->>P: 3 直接向對方請求檔案
  P->>C: 4 對方直接傳送檔案
  C->>S: 5 把自己的檔案更新到索引

注意第 3、4 步：檔案傳輸是兩台使用者電腦之間直接進行的，索引伺服器完全沒碰到檔案內容。第 5 步也很關鍵——客戶端會把自己擁有的檔案連結回報給索引，這樣資源池才會越來越大。

Napster 成功的關鍵，就是讓全網際網路的使用者能取用一大批分散在各處的檔案，實現了「分享網路邊緣資源」的理念。

生活妙喻

社區的『誰有什麼』公佈欄

社區公佈欄與借東西

想像一個社區有個中央公佈欄：

• 每戶人家把『我有的東西』（一台梯子、一本書、一片 DVD）登記到公佈欄上。這就是 Napster 的索引。
• 你想借梯子，就去看公佈欄（步驟 1、2：查詢、拿到清單），發現三號住戶有。
• 然後你直接走去三號家借（步驟 3、4：直接向對方拿東西）。公佈欄管理員根本不用碰到那把梯子。
• 你借到後，也把自己有的東西登記上去（步驟 5：更新索引）。

這個比喻清楚點出 Napster 的精髓與弱點：

• 精髓：東西（檔案）都在各家手上，分散而豐富。
• 致命弱點：那個公佈欄是唯一的、位置固定的。如果有人想關掉整個借東西的活動，只要去拆掉公佈欄就好——不必一家一家去處理。Napster 的索引伺服器正是因為位置固定、無法匿名，最後成了法律訴訟的目標。

實用超能力

為什麼被關，以及匿名性的兩難

Napster 為何被迫關閉

Napster 最後因版權訴訟被關。它的開發者辯稱：「複製過程完全發生在使用者電腦之間，我們沒參與，所以不該負責。」但這個論點失敗了：

索引伺服器被認定是整個過程不可或缺的一環。而且因為索引伺服器位於眾所周知的固定位址，營運者無法匿名，因此成了訴訟的明確目標。

課本給的啟示很深刻：一個更徹底分散的檔案分享服務，可能達成更好的責任分離——把責任攤到所有使用者身上，讓法律追訴變得極為困難。這也是第二代系統往「分散式索引」與「匿名」發展的動機之一。

匿名性：技術與社會的拉扯

匿名性對 P2P 設計者是個重要議題：

• 在節點眾多的系統裡，可以讓請求與結果的路由繞得很曲折來隱藏來源，也可以把檔案內容拆散存到多個節點。
• 如果檔案在上傳前先加密，存放者甚至能合理地宣稱『我不知道我存了什麼』。

但匿名也有正當的社會價值：在壓迫的社會中，對抗審查、保護吹哨者、維護言論自由，都可能需要匿名。當然，這些匿名技術會增加成本，而且研究顯示現有匿名性在某些攻擊下其實很脆弱。

深度探秘

統一索引：成也索引，敗也索引

統一索引的限制

Napster 證明了「幾乎完全靠一般網路使用者的資料與電腦」就能蓋出有用的大規模服務。但它有個結構性限制：

Napster 用一個（有複製的）統一索引（unified index），記錄所有可用的音樂檔案。

為什麼這對音樂分享還行，對很多應用卻是問題？

• 對音樂分享而言，索引副本之間的一致性要求不強：就算某副本稍微過時、某首歌暫時搜不到，使用者晚點再下載也沒差，所以不太影響效能。
• 但對許多其他應用來說，這就是個大限制了。課本點出關鍵原則：

除非存取資料物件的路徑被分散開來，否則物件的探索與定址很可能成為瓶頸。

換句話說，把『找東西』這件事集中在一處，遲早會塞車。後面第三代中介軟體最重要的工作，就是把這個「定位」的責任分散到整個網路。

生活妙喻

只有一個服務台的大賣場

只有一個櫃台的大賣場

想像一間超大賣場，東西（檔案）擺得到處都是，但只有一個服務台負責回答「某商品在哪一櫃」。

• 平日人不多時，這個服務台應付得來——就像音樂分享，大家不急、晚點查到也行。
• 但一旦來客暴增，所有人都得排到同一個服務台問路，隊伍立刻大排長龍。商品再多、賣場再大都沒用，瓶頸在那個唯一的問路櫃台。

這正是課本說的：「存取路徑若不分散，物件探索與定址會成為瓶頸。」

解法是什麼？把問路的服務分散——每個區域都設自己的小服務台，各自熟悉一部分商品的位置。這樣大家就近問路，不會全擠在一處。第三代 P2P 中介軟體做的就是這件事：把『知道東西在哪』這份知識分割並分散到所有節點上。

實用超能力

Napster 偷吃步的兩個前提

Napster 借了音樂應用的東風

Napster 之所以能用相對簡單的設計成功，是因為它取巧地利用了音樂分享這個應用的特殊性質。看懂這兩點，你就懂為什麼同樣手法不能直接套到別的應用：

換句話說，Napster 巧妙地把問題的『難的部分』給避開了：

• 不用煩惱一致性（因為內容不變）。
• 不用煩惱高可用性（因為晚點拿也行）。

flowchart TD
  A[音樂檔案不會更新] --> B[不需維持副本一致性]
  C[不要求單檔可用性保證] --> D[不需個別電腦高可靠]
  B --> E[簡單設計就能成功]
  D --> E

這給後人的啟示是：當你要設計支援會更新的資料或需要高可用保證的 P2P 系統時，就必須正面解決這些被 Napster 繞過的難題——這正是 OceanStore、Ivy 等後續系統的挑戰。

深度探秘

中介軟體要做的『功能』與要達到的『品質』

P2P 中介軟體要解決什麼

P2P 應用的核心難題是：讓客戶端能快速又可靠地存取資料，不論資料散落在網路何處。 第三代中介軟體就是專門來自動處理『放置』與『定位』這兩件事的。

它的需求分成兩類：

功能需求（Functional）——它要『做到什麼』

• 讓客戶端能定位並與任一資源溝通，即使資源散布在許多主機上。
• 能隨意新增與移除資源，也能新增與移除主機。
• 提供一個簡單、與資源型別無關的程式介面給應用開發者（就像其他中介軟體一樣）。

非功能需求（Non-functional）——它要『做得多好』

功能需求講的是『能不能做』，非功能需求講的是『做得夠不夠好』，下一步會逐一介紹。簡單說，它必須在極大規模、會頻繁變動、且彼此不太信任的環境下，依然跑得又快又穩。

把功能需求想成『菜單上有沒有這道菜』，把非功能需求想成『上菜快不快、味道穩不穩、衛不衛生』。

生活妙喻

全球快遞公司的服務承諾

全球快遞公司

把 P2P 中介軟體想成一家全球快遞公司，客戶（應用程式）只要說「把這件東西送到收件人手上」，剩下的路線規劃全交給它。

它的功能很單純：收件、送件、可以隨時開新據點或關掉舊據點。但真正考驗它的是這些服務品質（非功能需求）：

一家只會收送件、卻常常爆倉、走冤枉路、站點一倒就找不到包裹的快遞公司，是沒人敢用的。非功能需求才是真正的勝負關鍵。

實用超能力

為什麼『主機隨時會落跑』是最大魔王

高度動態：P2P 最棘手的非功能需求

在這些非功能需求裡，最折磨人的是容忍高度動態的主機進出。因為 P2P 的主機是一般人的電腦，沒人保證它會一直開機、連線、不出錯。

課本舉了驚人的對比數據：

差距為何這麼大？因為一般網路使用者會關機、斷線、隨興進出；而企業內網的機器通常整天開著、由專人管理。

這代表中介軟體必須能：

flowchart TD
  A[主機加入] --> B[整合進系統並重新分配負載以利用其資源]
  C[主機離開 自願或故障] --> D[偵測其離開並把負載與資源重新分配給其他節點]

換句話說，系統要像一支永遠在換人卻不能停賽的球隊：隨時有人上場、有人離場，但比賽要持續進行。這種「在不穩定的基礎上提供穩定服務」的能力，正是 P2P 中介軟體最核心的本事。

深度探秘

在應用層自己蓋一套路由系統

什麼是 Routing Overlay

P2P 中介軟體的核心是一個叫 routing overlay（路由覆蓋層） 的分散式演算法，負責定位節點與物件。

它叫 overlay（覆蓋層），是因為它在應用層自己實作了一套路由機制，獨立於底層的 IP 路由之上。

routing overlay 的主要任務與其他職責：

• 路由請求到物件：客戶端把含有物件 GUID 的請求交給 overlay，overlay 就把它路由到存有該物件副本的節點。若物件有多個副本，overlay 會送到最近的『活著』的節點。
• 插入物件：節點為新物件算出 GUID 並通知 overlay，使其可被所有人取用。
• 刪除物件、節點加入與移除：節點進出時，overlay 會重新分配責任。

這裡的 GUID 是所謂的純名稱（pure name），又稱不透明識別碼（opaque identifier）：

它完全不透露物件的位置——光看 GUID 你猜不出東西放在哪。

生活妙喻

一群只認得鄰居的接力郵差

接力傳遞的郵差網路

想像一個沒有總郵局、沒有完整地址簿的世界，只有一群郵差，每個郵差只認得一小部分的鄰居，並大致知道整個世界的方向感。

你要寄信給一個只知道『編號』（GUID）的收件人：

• 你把信交給身邊任一個郵差。
• 這個郵差看編號，把信轉給他認識的、編號離目標更近的那個郵差。
• 下一個郵差再做同樣的事……一棒接一棒，最後信就到了最接近目標編號的郵差手上。

這就是 routing overlay 的精神：沒有人需要知道全世界所有東西在哪，每個節點只要維護一小部分的『鄰居知識』，靠接力就能把請求送到目的地。

而那個『編號』（GUID）很特別——它是純名稱：純粹是個身分代號，完全看不出收件人住哪。這跟我們平常的地址（含國家、城市、街道，看得出位置）完全不同。位置的事，交給接力郵差們合力解決就好。

實用超能力

兩種 API：DHT 與 DOLR

DHT 與 DOLR：兩種存取風格

因為 GUID 是隨機分布的識別碼，且被用來決定物件放哪、又怎麼取回，所以 routing overlay 常被稱為分散式雜湊表（DHT，Distributed Hash Table）。它有兩種常見的 API 風格：

DHT 風格（如 Pastry 上的 PAST）

put(GUID, data)   把資料存到所有負責此 GUID 的節點上（含副本）
remove(GUID)      刪除 GUID 與其關聯資料
value = get(GUID) 從負責節點之一取回資料

特點：你只管 put / get，由 DHT 層自己決定資料放哪、複製到哪。 資料放在 GUID 數值最接近的節點，以及接下來最接近的 r 個主機（r 是複製因子）。

DOLR 風格（如 Tapestry）

publish(GUID)              讓執行此操作的節點成為該 GUID 物件的主機
unpublish(GUID)            讓該物件無法被存取
sendToObj(msg, GUID, [n])  把訊息送給物件 可選送給 n 個副本

特點：物件可以放在任何地方，由你（應用）決定，DOLR 層只負責維護 GUID 與『副本所在節點位址』的對應，並把請求路由到最近的副本。

簡單記：DHT 像你把東西寄到『置物櫃中心』讓系統決定放哪格；DOLR 像你自己保管東西，只去登記『它在我這』。

深度探秘

既然有 IP 路由，為何還要疊一層？

一個合理的疑問

routing overlay 乍看跟網際網路最底層的 IP 封包路由很像——都是在『把訊息送到目的地』。那為什麼 P2P 還要在 IP 之上再疊一層應用層路由？

課本用一張比較表回答（Figure 10.1），從五個面向看出兩者的差異。我們先看前三個：

關鍵洞察：IP 的設計受限於它身為網際網路主協定的『歷史包袱』，這些限制太根深柢固，無法直接改造來支援 P2P，所以乾脆在它之上另蓋一層。

生活妙喻

國家行政區劃 vs 興趣社團名冊

行政地址 vs 社團編號

把 IP 位址想成國家的行政地址：「X 國 Y 市 Z 街 5 號」。它是階層化的，而且各區段早就被劃分好、分配給特定行政單位。好處是好管理，壞處是僵硬——你不能隨便把一個門牌搬到地球另一端。

把 GUID 想成一個全球興趣社團的會員編號：純粹是一串隨機號碼，不綁任何地點。社團名冊很大很平坦，誰都能加入拿一個號碼，而且這個號碼和你住哪完全無關。

這個比喻解釋了兩者的差異：

• 規模：行政地址受限於既有劃分；社團編號空間巨大又平坦，能容納更多會員。
• 負載平衡：行政地址綁定地理，流量跟著地理走；社團編號隨機分布，可以讓事情故意打散，不跟地理綁在一起。
• 更新速度：改行政區劃要走漫長的官僚流程（約 1 小時級別）；社團名冊只要動動滑鼠就更新（幾分之一秒）。

所以 P2P 選擇用『社團編號』這套更靈活的命名系統，疊在僵硬的『行政地址』之上。

實用超能力

容錯、最近副本與匿名：後兩個面向

Overlay 在容錯、定位與安全上的優勢

比較表還有後三個面向，這些正是 P2P 真正想要的超能力：

flowchart TD
  A[容錯] --> A1[IP 由管理者設計冗餘 容忍單一故障 n 倍複製昂貴]
  A --> A2[Overlay 路由與物件參考可 n 倍複製 容忍 n 個節點或連線故障]
  B[目標識別] --> B1[IP 每個位址對應唯一目標節點]
  B --> B2[Overlay 可路由到目標物件的最近副本]
  C[安全與匿名] --> C1[IP 僅在所有節點受信任時安全 無法匿名]
  C --> C2[Overlay 在有限信任環境也能達成安全 可提供一定匿名]

逐項看：

• 容錯：IP 的冗餘由管理者設計，通常只能容忍單一路由器或連線故障，做 n 倍複製成本高昂；Overlay 則可把路由與物件參考複製 n 份，容忍 n 個節點或連線故障。
• 目標識別：每個 IP 位址只對應唯一一個目標節點；Overlay 卻能把訊息路由到目標物件的最近副本——這對效能與可用性是巨大優勢。
• 安全與匿名：IP 定址只有在所有節點都受信任時才安全，且位址擁有者無法匿名；Overlay 則能在信任有限的環境下達成安全，並提供一定程度的匿名。

總結：Overlay 不是要取代 IP，而是借助 IP 來傳送，同時在上層補上 IP 給不了的：超大平坦命名、隨機放置、n 倍複製容錯、最近副本路由，以及有限信任下的安全與匿名。

深度探秘

在一個環形的數字空間裡找路

Pastry 是什麼

Pastry 是一個實作 DHT 的 routing overlay。它的關鍵特性：

• 所有節點與物件都有 128 位元的 GUID。節點的 GUID 由其公鑰的安全雜湊算出，物件的由名稱或內容算出，因此 GUID 隨機散布在 0 到 2¹²⁸−1 之間。
• 在有 N 個節點的網路中，Pastry 能在 O(log N) 步內，正確把訊息路由到任一 GUID。
• 若該 GUID 對應的節點正活著，訊息就送給它；否則送給數值上最接近它的活著節點。

這裡有個重要觀念：

Pastry 講的『接近（closeness）』是在一個完全人造的空間——GUID 的數字空間——而不是真實的地理或網路距離。

而且這個數字空間被當成環形（circular）：GUID 0 的下方鄰居是 2¹²⁸−1，首尾相接。實際在網際網路上把訊息從一個 Pastry 節點送到另一個，可能要走很多個 IP 跳；為了不繞遠路，Pastry 會用 locality metric（在地性度量，如跳數或往返延遲） 來挑選鄰居，盡量讓 GUID 上的鄰居在真實網路上也近。

生活妙喻

圍成一圈的人傳紙條

圍成一圈、按號碼傳紙條

想像一大群人圍成一個圓圈，每人胸前有一個隨機號碼（GUID），號碼首尾相接（最大號旁邊就是 0 號）。你要把紙條送到『某個號碼』手上。

招式一：只認得左右鄰居（leaf set）

最笨但保證正確的方法：每個人只記得號碼上離自己最近的左右各幾位鄰居（這叫 leaf set，葉節點集合）。你拿到紙條，就看目標號碼，把紙條傳給你左右鄰居中號碼最接近目標的那個人。

• 好處：一定送得到。
• 壞處：超慢！一圈這麼多人，一位一位傳，平均要傳 N/2l 次。

招式二：認得『各種開頭』的遠方朋友（routing table）

聰明的做法：每個人除了左右鄰居，還準備一張通訊錄（routing table），裡面有號碼開頭各不相同的遠方朋友。要送紙條時，先看目標號碼前面幾位和自己一樣，就直接跳給一個『開頭更接近目標』的遠方朋友。一跳就拉近一大段，所以只要 O(log N) 次就到。

這就是 prefix routing（前綴路由） 的精神：每跳都讓『開頭相符的位數』多一位，像在玩猜數字一樣快速逼近。

實用超能力

看懂 prefix routing 的兩階段演算法

Pastry 路由演算法（兩階段理解）

GUID 用十六進位來看。routing table 依 GUID 的十六進位前綴分類，有 32 列（128÷4），每列 15 個項目（每個可能的十六進位值各一，扣掉自己那個值）。

路由時的判斷流程（簡化版）：

flowchart TD
  A[收到要送往 D 的訊息] --> B{D 落在我的 leaf set 範圍內嗎}
  B -- 是 --> C[轉給 leaf set 中數值最接近 D 的節點或就是我]
  B -- 否 --> D[找出 D 與我 GUID 的最長共同前綴長度 p]
  D --> E{routing table 該位置有項目嗎}
  E -- 有 --> F[轉給該節點 它與 D 多共享一位前綴]
  E -- 無 --> G[轉給 leaf set 或 table 中前綴同樣長但數值更接近 D 的節點]

關鍵在 prefix routing：比較目標 D 與自己 A 的十六進位數字，由左到右找出最長共同前綴的長度 p，然後用 p 當列、D 的第 p+1 位當行，去 routing table 取出一個『與 D 多共享一位前綴』的節點當下一跳。

用一個課本例子感受一下：從 65A1FC 送到 D46A1C，靠 routing table 大約 log₁₆(N) 跳就能送達，路徑像這樣逐步逼近：65A1FC → D13DA3 → D4213F → D462BA → D46A1C，每一跳開頭相符的位數都在增加。

這就是 Pastry 的超能力：在龐大網路中，只靠每個節點維護一小張表，就能用對數級的跳數精準找到任何東西。

深度探秘

新節點如何加入，舊節點如何離開

節點加入：O(log N) 訊息就搞定

Pastry 是完全自我組織的。新節點加入時，會用一個加入協定來取得自己的 routing table 與 leaf set，並通知其他節點更新：

1. 新節點先算出自己的 GUID（通常用 SHA-1 雜湊公鑰），然後聯絡一個附近的 Pastry 節點 A。
2. A 透過 Pastry 把一個 join 訊息路由出去，最後會到達 GUID 數值上最接近新節點 X 的現有節點 Z。
3. 沿途經過的所有節點（A、B、C…、Z）都把自己相關的 routing table 與 leaf set 內容傳給 X。
4. X 拼湊出自己的表：A 的第一列適合當 X 的第一列、B 的第二列適合 X 的第二列…而 Z 的 leaf set 幾乎就是 X 想要的 leaf set（只差一個成員）。
5. 最後 X 把自己的表內容送給所有相關節點，讓它們也更新。

整個加入過程只需要 O(log N) 則訊息。

節點失效或離開

當一個節點的直接鄰居（GUID 空間上的）再也聯絡不上它時，就認定它失效。此時要修復含有該失效節點的 leaf set：發現者找一個靠近失效節點的活節點，要它的 leaf set 副本，從中找到合適的替補。routing table 的修復則是**『發現時才修』**——路由失敗時就改用同一列的另一個項目。

生活妙喻

新鄰居搬進社區，老鄰居搬走

社區的迎新與補位

把 Pastry 想成一個自我管理的社區：

迎新（節點加入）

新住戶 X 搬來，先找一個附近的老鄰居 A 打招呼。A 幫他把一封『自我介紹信』（join 訊息）沿著社區傳出去，傳到號碼跟 X 最像的住戶 Z。沿途每戶都把自己的通訊錄分享一部分給 X：

• A 離 X 近，A 的『第一頁通訊錄』很適合借給 X 當第一頁。
• 一路上各戶各借一頁最合適的。
• 號碼最像 X 的 Z，他的『左右鄰居名單』幾乎就是 X 要的，只差一位。

這樣 X 很快就湊出自己完整的通訊錄，再把自己加進大家的名單。整個迎新成本很低（O(log N) 則訊息）。

補位（節點失效）

如果某戶突然失聯（左右鄰居敲門都沒人應），鄰居就知道他失效了。發現的人去找另一個靠近失聯者的鄰居，借來他的『左右鄰居名單』，從裡面挑一位來補上空缺。至於通訊錄裡的遠方朋友若搬走了，不急著全面更新，等下次寄信失敗時，再換同一頁的另一個朋友即可。

實用超能力

在地性、heartbeat 與對抗惡意節點

三招讓 Pastry 又快又穩又安全

在地性（locality）：讓路由走近路

Pastry 的路由結構高度冗餘——任兩節點間有很多條路。建表時，每個位置常有好幾個候選節點，Pastry 用 proximity neighbour selection（鄰近鄰居選擇） 配合 locality metric（IP 跳數或延遲）挑最近的。雖然資訊不完整無法達到全域最佳，但模擬顯示路由平均只比最佳路徑長約 30–50%。

Heartbeat（心跳）：偵測失效

所有節點會定期向 leaf set 中的鄰居發心跳訊息（固定間隔發送、表示『我還活著』）。若太久沒收到某鄰居的心跳，就啟動修復程序。MSPastry 還在每一跳加上確認（acknowledgement）：沒收到確認就改走另一條路重送，並把該節點標記為疑似失效。此外用 gossip protocol（八卦協定） 約每 20 分鐘交換一次路由表資訊，修補失效項目、防止在地性慢慢退化。

對抗惡意節點：引入隨機性

flowchart TD
  A[標準 prefix routing 走最佳路徑] --> B{少數情況隨機調整}
  B --> C[故意取較短的共同前綴 改用較早一列的路由]
  C --> D[產生不同但較不最佳的路徑]
  D --> E[搭配客戶端重送 即使有少量惡意節點也能最終成功]

因為 heartbeat 不一定夠快、也擋不住故意搗亂的惡意節點，所以：依賴可靠送達的客戶端要採 at-least-once（至少一次） 機制、重送請求數次，給 Pastry 時間偵測與修復；同時在路由選擇中引入少量隨機性，讓重送能繞過卡住的惡意節點，最終成功。

深度探秘

同樣 prefix routing，但換了一種介面

Tapestry 與 Pastry 的異同

Tapestry 也實作 DHT、也用 prefix routing 路由訊息，這點和 Pastry 一樣。但它對外露出的是 DOLR 介面（見上一章的 publish / sendToObj），把底層的 DHT 藏起來。

關鍵差異在『誰決定物件放哪』：

在 Tapestry，持有資源的節點用 publish(GUID) 把資源宣告給系統，而資源仍由持有者自己保管。

如果同一份資源被複製到多處，每個持有副本的節點都用相同的 GUID 去 publish，於是 Tapestry 的路由結構裡會有多筆指向不同節點的對應。

Tapestry 用 160 位元的識別碼：

• NodeId：指向執行路由動作的電腦。
• GUID：指向物件。
• 對任何 GUID 為 G 的資源，存在一個唯一的 root node（根節點），其 GUID（記為 R_G）在數值上最接近 G。

生活妙喻

圖書館的『館藏登記處』

自己保管書，去登記處掛號

把 Tapestry 想成一套圖書館館藏登記系統，但每本書是放在各個讀者自己家裡的：

• 你手上有一本《Phil 的書》（GUID = 4378），你不必把書交出去，只要去登記處掛號：『這本書（4378）在我這裡』——這就是 publish(GUID)。
• 每本書都有一個固定的主管登記員（root node），就是號碼跟這本書最接近的那位（例如 4377 負責管 4378）。你的掛號訊息會沿路被送到這位主管登記員那裡。
• 沿途經過的登記員都會順手記下『4378 在某某讀者家』這個對應（cache），主管登記員當然也記下。
• 如果有別人也有同一本書的副本，他也用同樣的書號去掛號，於是系統裡就有好幾筆『4378 在不同人家』的記錄。

之後有人想借 4378，系統就沿著這些掛號記錄，把他導向離他最近的那位持有者（這些記錄會依網路距離排序）。

這跟 DHT（把書直接交給置物櫃中心、由系統決定放哪格）不同：Tapestry 讓你自己保管書，只去登記它在哪。

實用超能力

DOLR 的彈性：把副本放在使用者身邊

Tapestry 給應用的彈性

DOLR 介面讓物件可以放在任何地方、由應用決定，這帶來一個實用的超能力：

應用可以把副本放在（網路距離上）常存取它的使用者附近，藉此降低延遲、減少網路負載，或確保對網路與主機故障的容忍。

flowchart TD
  A[持有副本的節點] -->|publish 相同 GUID| B[沿路送往 root node]
  B --> C[沿途節點快取 GUID 到持有者 IP 的對應]
  C --> D[多筆對應依網路距離排序]
  D --> E[借取時導向最近可用的副本]

不過課本提醒：Pastry 與 Tapestry 的這個差別並非根本性的。

• Pastry 應用也能達成類似彈性：只要讓 GUID 對應的物件當作『代理（proxy）』，指向更複雜的應用層物件即可。
• 反過來，Tapestry 也能用它的 DOLR API 來實作一個 DHT。

換句話說，DHT 與 DOLR 比較像是同一套底層能力的兩種包裝風格，而非兩種完全不同的技術。

實務上，Tapestry 收到對同一 GUID 的多筆 (G, IP) 對應時，會依到該 IP 的網路距離（往返時間）排序，所以對被複製的物件而言，後續訊息會自然被送往最近可用的副本。Tapestry 正是後面 OceanStore 檔案儲存系統的底層基礎。

深度探秘

有規劃 vs 隨遇而安的兩種 P2P

結構化 vs 非結構化

前面的 Pastry、Tapestry 都是結構化（structured） 的：

結構化系統有一套全域政策管理網路拓樸、物件放置與搜尋／路由函數，底層有一個明確的分散式資料結構（如 DHT 與環狀結構）和對應的演算法。

好處是保證能找到物件、且有時間與複雜度的上限、訊息開銷相對低；代價是得維護這些複雜結構，在高度動態的環境下既困難又昂貴。

相對地，非結構化（unstructured） 系統：

對拓樸與物件放置沒有全域控制。overlay 是臨時拼湊出來的——每個加入的節點只遵循一些簡單的本地規則去建立連線（連上一組鄰居，鄰居又連著別的鄰居……）。

好處是自我組織、天生抗節點故障；代價是要找物件只能搜尋整個網路，無法保證找得到、效能不可預測，還可能產生過量訊息流量。

有趣的是，儘管有這些缺點，非結構化反而是網際網路上的主流——Gnutella、FreeNet、BitTorrent 都採非結構化。一份 2008/9 的研究指出 P2P 檔案分享佔了全網際網路 43%–70% 的流量。

生活妙喻

圖書館 vs 在市集裡問人

找書的兩種方式

結構化＝有編目的圖書館

圖書館每本書都按一套全域規則（杜威分類法）擺放，你查目錄就能保證找到，而且很快。代價是：得有人持續維護這套編目系統，書一進一出都要重新上架歸位，工程浩大。

非結構化＝在熱鬧市集裡問人

市集裡沒有目錄，你想找某樣東西，只能逢人就問：『你有嗎？沒有的話，幫我問問你認識的人？』每個攤販只認得身邊幾個攤販，問題就這樣一傳十、十傳百。

• 好處：完全不用維護任何目錄，攤販來來去去都沒差，市集自己就運轉起來（自我組織、抗故障）。
• 壞處：你不保證問得到（也許東西就在某個沒被問到的角落），而且如果每個人都對所有鄰居大喊大叫，市集很快就會被吵到塞爆。

這個『逢人就問、一傳十十傳百』的笨方法，就叫 flooding（洪泛），正是早期 Gnutella 0.4 的做法——簡單，但完全不可擴展。

實用超能力

聰明搜尋與 Gnutella 0.6 的進化

讓非結構化搜尋變聰明

為了改善 flooding 的問題，發展出幾種搜尋策略：

這些策略搭配內容複製（整檔複製、或把檔案碎片散布各處，如 BitTorrent），能大幅降低搜尋開銷、提升可擴展性。

Gnutella 0.6：兩大關鍵改良

flowchart TD
  A[Leaf node 葉節點] -->|連上少數| B[Ultrapeer 超級節點]
  B -->|彼此重度連接 32 以上連線| C[Ultrapeer 超級節點]
  A2[Leaf node] -->|送出 QRT 檔案雜湊| B
  B -->|合併 QRT 只往有結果的路徑轉送查詢| C

1. Ultrapeer 階層（hybrid 架構）：不再人人平等，把資源較多的節點選為 ultrapeer（超級節點），彼此重度連接（各 32 條以上連線）；一般節點當 leaf（葉節點），只連上少數 ultrapeer。這大幅減少了徹底搜尋所需的最大跳數。Skype 也採這種混合架構。
2. Query Routing Protocol（QRP，查詢路由協定）：節點把自己檔名雜湊出的數字組成 Query Routing Table（QRT） 送給 ultrapeer；ultrapeer 合併所有葉節點與自己的 QRT 再彼此交換。這樣 ultrapeer 就能只往『可能有結果』的路徑轉送查詢，大幅減少無謂流量。

此外，查詢中帶有發起 ultrapeer 的網路位址，所以一旦找到檔案，可直接用 UDP 回傳，不必沿原路繞回去。

深度探秘

先搞懂網頁快取在做什麼

網頁快取的基本原理

瀏覽器發出 HTTP GET 請求要網頁、圖片等物件時，這些請求可能由三個地方滿足：瀏覽器本機快取、代理快取（proxy cache）、或來源伺服器（origin server）——看誰手上有『夠新鮮』的副本。

收到 GET 請求時有三種情況：物件不可快取、快取未命中（miss）、或在快取中找到。前兩種會往來源伺服器方向轉發；找到時，則要檢查這份快取夠不夠新鮮。

物件存放時附帶一些 metadata：

• 最後修改時間戳 T、可選的存活時間 t（time-to-live）、或 eTag（內容算出的雜湊）。
• 若 T + t 晚於現在時間，就視為新鮮，直接回傳給客戶端，不必聯絡來源伺服器。
• 否則發出 conditional GET（cGET） 去驗證：可能是 If-Modified-Since（帶上次修改時間戳）或 If-None-Match（帶 eTag）。來源伺服器回傳完整物件，或一個『未修改』訊息。

傳統做法是用一台專用伺服器或叢集跑代理快取，需要可觀的專用運算資源。

生活妙喻

辦公室的『共用冰箱便當』

不用專人採買，大家湊出一個共用快取

傳統代理快取像辦公室請了一位專職採買：他有一台大冰箱（專用伺服器），所有人要吃的都先問他有沒有現貨。好用，但要養這個人和那台大冰箱（專用運算資源）。

Squirrel 的想法是：不必請專人，讓每位同事各自分出冰箱一格湊成一個共用快取。

• 每個網頁物件用它的 URL 算 SHA-1 雜湊得到 128 位元的 Pastry GUID。
• GUID 數值最接近該物件的那位同事，就成為這個物件的 home node（家節點），負責保管它的快取副本。
• 你要某個網頁時，本機沒有新鮮副本，就透過 Pastry 把請求路由到那位 home node 同事。

有趣的是：因為這個 GUID 不是用來驗證內容的（只是用來決定誰負責），所以它不需要根據整個網頁內容來算，光用 URL 算就好。Squirrel 作者用 end-to-end 論證辯護這點：網頁從來源到客戶端途中本來就可能在很多點被破壞，快取頁的認證幫助不大；真要安全，該用 HTTPS（端到端 TLS）。

實用超能力

它真的夠用嗎？看評估數據

Squirrel 的運作與評估

每個客戶端都跑一個本地 Squirrel proxy 程序：本機沒有新鮮副本時，就把 Get 或 cGet 透過 Pastry 送到 home node。

flowchart TD
  A[客戶端要網頁] --> B{本機快取有新鮮副本}
  B -- 有 --> C[直接用]
  B -- 沒有 --> D[經 Pastry 送請求到 home node]
  D --> E{home node 有新鮮副本}
  E -- 有 --> F[直接回客戶端 未修改或新副本]
  E -- 沒有 --> G[home node 向來源伺服器發 Get 或 cGet]
  G --> H[取得後回傳客戶端 並視情況快取]

Squirrel 用微軟兩個真實環境的流量軌跡模擬評估（劍橋 105 台、雷德蒙德 3.6 萬台以上），和集中式快取比較三個面向：

結論：Squirrel 效能可媲美集中式快取，而加在每台桌機上的額外負載低到使用者幾乎感覺不到。後來它被部署為 52 台機器區網的主要快取，結果證實了這些結論。

深度探秘

用『一連串不可變版本』來支援可變資料

OceanStore 想解決的難題

還記得 P2P 雜湊命名最適合不可變資料嗎？OceanStore（建在 Tapestry 之上）偏偏要支援可變（mutable）檔案——要在不斷變動的網路與運算資源中，提供超大規模、可持久、可靠的儲存。

它的聰明解法是：

每個物件被表示成一串有序的、不可變的版本（versions），原則上永久保存。任何更新都會產生一個新版本。

而且各版本之間用 copy-on-write（寫時複製） 共享未變動的區塊：

兩個版本只有小差異時，只需要少量額外儲存——沒改到的資料塊大家共用。

物件的結構很像 Unix 檔案系統：資料塊透過一個叫 root block（根區塊） 的 metadata 區塊來組織與存取，必要時還有 indirection block（間接區塊），就像 Unix 的 i-node。再上一層，用一個持久的、外部可見的名稱（如檔案路徑）來對應到這一串版本。

生活妙喻

Google 文件的版本歷史

像文件的『版本歷史』

你用過協作文件的『版本歷史』功能嗎？OceanStore 的精神幾乎一模一樣：

• 你從不真的『覆蓋』舊內容。每次存檔都產生一個新版本，舊版本永久留著。
• 而且系統很省空間：新版本只記錄『這次改了哪幾頁』，沒改的頁面直接沿用舊版本的——這就是 copy-on-write。

再來是命名的巧思。因為內容會變，不能用內容雜湊當物件的長期名字（內容一變雜湊就變，所有指向它的索引就壞了）。所以 OceanStore 用三種識別碼：

關鍵：AGUID 是這份文件的永久身分證，不管你改幾次都不變；而每次存檔產生新的 VGUID。AGUID 由『應用層名稱（如檔名）＋擁有者公鑰』雜湊產生，永遠固定。

實用超能力

inner ring 的 Byzantine 共識與 erasure coding

在不可信的世界裡保證正確與可用

問題來了：AGUID 指向『目前是哪個版本』這件事會變，存在不可信的陌生人電腦上，怎麼確保它沒被亂改？

OceanStore 的答案是：

AGUID 與版本序列的對應，記在一張簽署過的憑證（certificate）裡。憑證含目前版本的 VGUID，而每個版本的 root block 又含前一版本的 VGUID，形成一條可往回追溯的版本鏈。

更新憑證需要一小群主機——稱為 inner ring（內環）——達成共識：

flowchart TD
  A[要更新物件 產生新版本] --> B[inner ring 用 Byzantine 共識協定]
  B --> C[即使部分成員失效或惡意 仍能正確簽署新憑證]
  C --> D[新憑證取代 primary copy 並散布到較多 secondary copy]

• inner ring 用 Byzantine agreement（拜占庭共識） 協定來更新並簽署憑證，即使部分成員失效或惡意也能維持正確。
• 但 Byzantine 共識的成本隨主機數平方成長，所以 inner ring 刻意保持很小，再用 primary copy（主動複製）把憑證散布到更多 secondary copy。

資料塊用 erasure coding 省空間又容錯

唯讀的資料塊則用更省儲存的方式複製：把每個區塊切成 m 個碎片，用 erasure code（抹除碼） 編成 n 個碎片（n > m）。

神奇特性：只要拿到任意 m 個碎片就能重建整個區塊。所以系統可容忍多達 n − m 台主機遺失而資料仍在。Pond 實作用 m=16、n=32，儲存成本加倍，就能容忍多達 16 台主機故障而不丟資料。

深度探秘

不存『檔案』，只存『更新日誌』

Ivy 的核心點子

Ivy 和 OceanStore 一樣，是建在 overlay 路由與分散式雜湊儲存之上的讀寫檔案系統，支援多讀者多寫者。但 Ivy 模擬的是 Sun NFS 伺服器。它最特別的設計是：

Ivy 不直接儲存檔案狀態，而是把檔案存成一份份更新日誌（logs）——記錄客戶端發出的每一次檔案更新請求。需要讀檔時，就掃描這些日誌來重建檔案。

日誌記錄存在 DHash 這個分散式雜湊儲存服務裡（它的介面就像前面的 put/get DHT）。

Ivy 的結構：

• 一個 Ivy 檔案系統由一組更新日誌組成，每位參與者各一份。
• 每位參與者只能往自己的日誌追加（append-only），但可以讀取所有人的日誌。
• 一份 Ivy 日誌是一個反向時間排序的鏈結串列，每筆是帶時間戳的更新記錄。DHash 用記錄內容的 SHA-1 雜湊當鍵來存取，並把記錄依時間戳串接。
• 每位參與者還維護一個可變的 log-head，指向自己最新的日誌記錄。

生活妙喻

每個人各記一本帳本，對帳算出總帳

大家各記一本流水帳

把 Ivy 想成幾個合夥人共管一筆帳，但沒有一本統一的總帳，而是每個人各記自己的一本流水帳（log）：

• 你只能在自己的帳本上往後加新記錄（append-only），不能改別人的，也不能改自己寫過的。
• 但你可以翻閱所有人的帳本。
• 想知道『現在帳目總狀態』（讀檔案），就把大家的帳本攤開，按時間順序對帳，算出結果。

問題是：每個人各記各的、沒有全域時鐘，怎麼知道哪筆在前哪筆在後？Ivy 用 version vectors（版本向量／向量時間戳） 來替多本日誌的記錄排出一個全序。

而且每本帳本有個『最新頁書籤』（log-head）：

• log-head 是個可變區塊，由擁有者用公私鑰對簽章。內容用私鑰簽、用對應公鑰驗證。
• 任何拿到某人公鑰的參與者，都能取得他的 log-head，順著它讀到那本帳的所有記錄。

簡單記：Ivy 不維護一本會被搶著改的總帳（那容易出事），而是讓大家各記不可竄改的流水帳，要用時再對帳合併。

實用超能力

view、snapshot 與部分信任

Ivy 如何處理『部分信任』與惡意參與者

Ivy 最大的貢獻，是在『主機只能部分信任、可能被攻擊』的環境下管理安全與完整性。它的關鍵武器是 view（視圖）：

view 是由一組參與者的更新日誌所建構出來的檔案系統狀態表示。可以移除某些參與者，再重算一個不含他們更新的 view。

flowchart TD
  A[偵測到某參與者惡意 例如惡意刪檔] --> B[把他從 view 中移除]
  B --> C[不再用他的日誌計算檔案系統內容]
  C --> D[他刪掉的檔案在新 view 中重新出現]

因為每個人的更新存在各自獨立的日誌裡，所以能整本回滾：一旦發現安全漏洞或一致性問題，就把那位惡意參與者踢出 view，他的破壞自然消失。

snapshot：讓掃描不會慢死

每次讀檔都從頭掃描所有日誌會非常慢。Ivy 用本地快取與 snapshot（快照） 加速：snapshot 是各參與者在使用日誌時順手算出、存在本地的檔案系統表示。它是『軟性的（soft）』——若某參與者被踢出 view，snapshot 可能就失效要重算。

一致性與衝突

• Ivy 採 close-to-open 一致性：對檔案的更新要等到檔案關閉後才對其他行程可見，這樣可把一檔的多次寫入累積成單一日誌記錄。
• 因為各 Ivy 伺服器自主寫各自的日誌、不互相協調，序列化要在讀取合併時才做。多數更新可用向量時間戳排序，但仍可能有衝突更新，需用類似 Coda 的應用層方法（自動或人工）解決。