識別碼很適合用來唯一代表實體，而且常常就是隨機位元字串，我們稱之為非結構化名稱或扁平名稱（flat name）。扁平名稱的重要特性是：名稱本身完全不含任何「如何找到其實體存取點」的資訊。本節探討扁平名稱如何解析——等價地說，只給識別碼時要如何定位實體。

簡單解法#

以下兩種解法只適用於區域網路，但在那個環境中通常表現稱職，簡單就是它們的魅力。

廣播與群播#

在提供高效廣播設施的網路（所有機器連在同一條纜線或其邏輯等價物上的區域網路、無線區域網路）中，定位實體很簡單：

• 把含有實體識別碼的訊息廣播給每台機器，要求各機器檢查自己是否擁有該實體。
• 只有能提供該實體存取點的機器回覆，附上存取點的位址。

網際網路的**位址解析協定（Address Resolution Protocol, ARP）**正是這個原理：只知道 IP 位址時，廣播詢問「誰擁有這個 IP」，擁有者回覆其 Ethernet 位址。

網路一大，廣播就變得低效：不只浪費頻寬，更嚴重的是太多主機被自己根本答不了的請求打斷。

解法之一是改用群播（multicasting），讓請求只送達一小群主機。Ethernet 在硬體層直接支援資料鏈結層群播；網際網路則支援網路層群播——主機可加入以群播位址識別的群組，送往該位址的訊息會以盡力而為的方式送達所有成員。群播位址的兩種用法：

• 通用定位服務：例如組織內每台行動電腦連上網路時取得動態 IP 並加入特定群播群組；想找電腦 A 的行程對群組發出「A 在哪？」，A 若在線就回覆目前 IP。
• 找最近的複本：把群播位址關聯到一個被複製的實體，各複本以自己的一般 IP 回覆。粗略的挑法是選最先回覆的；但事實證明，挑選最近複本通常沒那麼簡單（後續章節再談）。

轉送指標#

定位行動實體的另一個流行做法是轉送指標（forwarding pointers）（Fowler，1985）：實體從 A 移到 B 時，在 A 留下一個指向 B 新位置的引用。優點是簡單——只要先用傳統命名服務定位到實體一次，之後沿著指標鏈就能找到目前位址。缺點也很明確：

• 高度移動的實體會留下過長的鏈，定位成本高得不划算。
• 鏈上所有中間位置都得維護自己那段指標，想丟也丟不掉。
• 脆弱：任何一個指標遺失，實體就再也找不到了。

因此關鍵是讓鏈保持夠短，並確保指標足夠強健。

延伸案例：SSP chains——以（client stub, server stub）實作轉送指標

以可用遠端程序呼叫存取的遠端物件為例，SSP chains（Shapiro 等人，1992）把每個轉送指標實作成一對（client stub, server stub）。（Shapiro 原始術語稱 server stub 為 scion，即（stub, scion）配對。）server stub 存的是指向實際物件的本地引用，或指向該物件某個遠端 client stub 的本地引用。

• 物件從位址空間 A 移到 B 時，在 A 原地留下 client stub，並在 B 安裝指向自己的 server stub。遷移對用戶端完全透明：用戶端只看得到 client stub，呼叫轉送到哪裡完全被隱藏。注意這不是「查位址」——用戶端的請求是沿鏈一路被轉送到實際物件。

• 縮短鏈：物件呼叫會攜帶起始 client stub 的識別（用戶端傳輸層位址＋本地產生的編號）。呼叫抵達物件目前位置後，回應直接送回起始 client stub（通常不再走回鏈），並夾帶目前位置；client stub 隨即把配對的 server stub 調整為物件目前位置的那一個。取捨在於：直接回起始 stub 較快，但只有它被修正；沿反向鏈回覆則能修正所有中間 stub。

• 不再被任何 client 引用的 server stub 可以移除——這與分散式垃圾回收密切相關，是個遠非平凡的問題。
• 傳遞引用：行程 P1 把對物件 O 的引用傳給 P2 時，是在 P2 的位址空間安裝 client stub 的副本，指向同一個 server stub，轉送機制照常運作。
• 斷鏈：鏈上有行程崩潰或失聯時的一種解法（Emerald 與 LII 系統採用），是讓物件的建立地（家位置，home location）永遠以容錯方式保存其目前位置的引用；鏈斷了就問家。若家位置本身也要能搬，可用傳統命名服務記錄目前的家。

家位置法#

廣播與轉送指標都有擴展性問題：廣播／群播在大型網路難以高效實作，長指標鏈則有效能與斷鏈問題。在大型網路支援行動實體的流行做法，是引入**家位置（home location）**來追蹤實體目前位置，家通常選在實體的建立地。前述轉送指標方案就以它作為後備機制。

另一個例子是 Mobile IP：

• 每台行動主機有固定 IP 位址，所有通訊先導向該 IP 對應的家代理（home agent）——位於該 IP 網路位址所屬的區域網路（IPv6 中實作為網路層元件）。
• 主機移到其他網路後申請一個**轉交位址（care-of address）**並註冊到家代理。
• 家代理收到給行動主機的封包時：主機在本地網路就直接轉送；否則把封包包進 IP 封包隧道（tunnel）到轉交位址，同時把主機目前位置告知傳送者，讓後續封包直達。此時固定 IP 實質上是行動主機的識別碼。

家位置法的兩個固有缺點：其一，通訊得先繞到家，而家可能離實體目前位置很遠（增加通訊延遲）；其二，家位置是固定的——必須保證它永遠存在，而長壽實體若永久搬到網路的另一頭，家卻留在原地就很不划算。緩解方式是把家註冊到傳統命名服務、讓用戶端先查家的位置；因為家的位置相對穩定，查過即可有效快取。

分散式雜湊表#

接著看較新的做法：如何用**分散式雜湊表（Distributed Hash Table, DHT）**把識別碼解析成位址。這裡以最易講解的 Chord 為代表，先看不考慮網路鄰近性的基本機制，再看網路感知的改良。

一般機制#

Chord（Stoica 等人，2003）是眾多 DHT 系統的代表。它使用 m 位元識別碼空間（m 通常為 128 或 160，視雜湊函式而定），隨機指派識別碼給節點、也指派鍵給實體（檔案、行程等皆可）。鍵 k 的實體歸屬於識別碼 id ≥ k 中最小者的節點，稱為 k 的後繼（successor），記為 succ(k)。

核心問題是高效地把鍵 k 解析成 succ(k) 的位址：

• 線性做法（不可擴展）：每個節點 p 只記後繼 succ(p+1) 與前驅 pred(p)，收到解析請求就往合適的鄰居轉送；若 pred(p) < k ≤ p 則回傳自己的位址。
• 指叉表（finger table）：每個 Chord 節點改為維護至多 m 筆項目的指叉表，FT_p[i] = succ(p + 2^(i-1))，亦即第 i 筆指向「距離 p 至少 2^(i-1)」的第一個節點。這些引用是識別碼空間中的捷徑，捷徑距離隨索引呈指數成長。查找鍵 k 時，節點 p 直接把請求轉給指叉表中索引 j 滿足 FT_p[j] ≤ k < FT_p[j+1] 的節點 q（此處為求清楚忽略模運算）。

以書中的 Chord 環為例：從節點 1 解析 k = 26 時，節點 1 查表發現 26 超過 FT₁[5]，轉給節點 18 = FT₁[5]；節點 18 依 FT₁₈[2] < k ≤ FT₁₈[3] 選節點 20；請求再從 20 到 21、從 21 到 28——節點 28 正是 k = 26 的負責者，其位址回傳給節點 1，解析完成。可以證明查找一般需要 O(log N) 步（N 為系統節點數）。

成員變動與維護#

大型分散式系統的參與節點隨時在變：節點自願加入與離開，也會故障（等同離開）再復原（重新加入）。

• 加入很簡單：節點 p 聯絡系統中任一節點請求查找 succ(p+1)，找到後把自己插入環中。離開同樣簡單（節點也會記錄前驅）。
• 複雜的是維持指叉表正確，其中最要緊的是每個節點 q 的 FT_q[1]（環上的下一個節點）：
  • 各節點 q 定期向 succ(q+1) 索取 pred(succ(q+1))。若等於 q 自己，代表資訊一致；若否，表示有新節點 p 插入（q < p ≤ succ(q+1)），q 便把 FT_q[1] 調整為 p，並檢查 p 是否已把 q 記為前驅，不然再調整一次。
  • 其他指叉表項目同理：對每個 i 發出 succ(q + 2^(i-1)) 的解析請求即可更新，Chord 以背景行程定期執行。
  • 各節點也定期檢查前驅是否存活；前驅故障就把 pred(q) 設為「未知」。當某節點更新環上下一個節點的連結時，發現 succ(q+1) 的前驅是「未知」，就通知對方「我懷疑我是你的前驅」。

這些簡單程序大致可讓 Chord 系統維持一致，頂多少數節點暫時例外。

利用網路鄰近性#

Chord 這類系統的潛在問題是請求可能在網際網路上亂繞：假設環上相鄰幾步的節點分別在阿姆斯特丹、聖地牙哥、又回到阿姆斯特丹、又到聖地牙哥，一次解析就要三趟廣域傳輸，其實一趟就該夠了。Castro 等人（2002）區分三種讓 DHT 感知底層網路的方式：

• 拓撲式識別碼指派（topology-based assignment of node identifiers）：讓網路上相近的節點拿到相近的識別碼。但對 Chord 這種一維識別碼空間的系統問題很大：把邏輯環映到網際網路極不容易，而且容易暴露相關性故障——同一企業網路的節點識別碼集中在小區間，該網路一斷線，識別碼分布就出現整段空洞。
• 鄰近路由（proximity routing）：節點為每個轉送選擇保留多個候選。例如 Chord 的每筆指叉表項目 FT_p[i] 都改記該區間 [p + 2^(i-1), p + 2^i − 1] 內的 r 個節點；轉送時挑其中離自己最近、且識別碼仍小於目標鍵的那個。附帶好處：單一節點故障不會立刻讓查找失敗，因為還有多條路可走。
• 鄰近鄰居選擇（proximity neighbor selection）：在「有得選」的前提下，建路由表時就直接挑最近的節點當鄰居。Chord 通常沒得選；但像 Pastry 這類協定，節點加入時會從多個節點取得目前重疊網路的資訊來建表，自然可以挑最好的。

鄰近路由與鄰近鄰居選擇的界線未必清楚：把 Chord 改成每筆指叉表項目記 r 個後繼後，鄰近鄰居選擇就變成找出最近的 r 個鄰居，與鄰近路由幾乎是一回事（Dabek 等人，2004）。

最後還可區分**迭代式（iterative）與遞迴式（recursive）**查找：前者是被詢問的節點把「下一個節點的位址」回傳給請求行程，由行程再去問下一個節點；後者（也就是前文一路採用的講法）是節點直接把查找請求轉送給下一個節點。兩者各有利弊，本章稍後（結構化命名）詳談。

階層式做法#

最後介紹一種通用的階層式定位方案，並附帶幾個最佳化。此做法以 Globe 定位服務為本（Ballintijn，2003；van Steen 等人，1998），也代表了許多為個人通訊系統（Personal Communication Systems）提出的階層式定位服務。

組織結構#

• 網路劃分為一組網域（domain）：單一頂層網域涵蓋整個網路，每個網域可再切成多個子網域；最低層網域稱葉網域（leaf domain），通常對應一個區域網路或行動電話網的一個基地台涵蓋區（cell）。
• 每個網域 D 有一個目錄節點（directory node） dir(D) 追蹤該網域內的實體，形成一棵目錄節點樹；頂層網域的目錄節點稱根（目錄）節點，知道所有實體。
• 位於網域 D 的實體 E 在 dir(D) 中以一筆位置紀錄（location record）表示：葉網域的目錄節點存實體在該網域的實際位址；上一層網域的目錄節點只存指向下層節點的指標，層層向上直到根。因此根節點對每個實體都有一筆紀錄，指向實體目前所在的下一層子網域的目錄節點。

• 實體可有多個位址（例如被複製）：若實體在葉網域 D1 與 D2 各有位址，包含兩者的最小網域，其目錄節點就有兩個指標，各指向一個含位址的子網域。

查找#

用戶端要定位實體 E 時，向自己所在葉網域的目錄節點發出查找請求：

• 該節點若無 E 的位置紀錄，表示 E 不在此網域，請求轉給父節點（代表更大的網域），依此類推。
• 一旦抵達存有 E 位置紀錄的節點 M，就知道 E 在 M 代表的網域內；請求沿紀錄中的指標往下轉送，直到葉節點取得 E 的實際位址，回傳給用戶端。

階層式定位服務的查找利用了局部性：本質上是以請求者為中心、逐圈擴大的搜尋——每往上一層，搜尋範圍就擴大一次；最壞情況到根為止，之後必能沿指標往下找到。實體離用戶端越近，越快找到。

更新#

插入與刪除同樣利用局部性：

• 插入：實體 E 在葉網域 D 建立複本後，從 dir(D) 發出插入請求並往上轉送，直到遇上已有 E 紀錄的節點 M。M 在紀錄中加入指向來源子節點的指標；該子節點建立 E 的紀錄並指向再下層——如此一路往下回到發起的葉節點，最後由葉節點存入實際位址。
• 這是由上而下安裝指標鏈。另一種做法是先建好本層紀錄再把請求傳給父節點，即由下而上建鏈：優點是位址盡早可供查找——就算父節點暫時不可達，本網域內仍查得到。

• 刪除與插入對稱：從葉網域的紀錄移除位址；紀錄空了就整筆刪除並通知父節點移除指標，父節點的紀錄若也變空就繼續往上，直到某筆紀錄移除指標後仍非空、或到根為止。