扁平名稱與結構化名稱提供的是唯一、位置無關的實體指涉方式；結構化名稱更進一步讓人方便地命名與存取實體。但這兩者通常都假設一個名稱只指涉單一實體。隨著可取得的資訊越來越多，有效搜尋實體變得重要——使用者只提供一段「想找什麼」的描述，就該找得到。

分散式系統中流行的描述方式，是以**（屬性, 值）配對描述實體，稱為屬性式命名（attribute-based naming）**：每個實體帶一組屬性，各屬性描述實體的某個面向；使用者指定某些屬性應有的值，即是在限縮感興趣的實體集合，命名系統負責回傳一或多個符合描述的實體。

目錄服務#

屬性式命名系統又稱目錄服務（directory services）；支援結構化命名的系統則一般稱為命名系統。目錄服務中，實體帶有一組可供搜尋的屬性。

設計一組合適的屬性並不簡單，多半得靠人工。即使對「用哪些屬性」有了共識，讓一群背景各異的人一致地設定屬性值又是另一個難題——用過網路音樂、影片資料庫的人多半深有體會。電子郵件是另一例：寄件者、收件者、主旨等屬性容易，但一旦需要其他類型的描述子，光是開發能依描述子過濾郵件的規則就很困難。

為了統一資源的描述方式，一個特別相關的發展是資源描述框架（Resource Description Framework, RDF）：

• 資源以**（主詞, 述詞, 受詞）三元組**描述，例如 (Person, name, Alice) 描述一個名為 Alice 的 Person 資源。
• 三元組的每個成分本身都可以是資源：Alice 可實作為一個可再取回的檔案的引用；述詞對應的資源可含該述詞的文字說明。RDF 中的引用本質上是 URL。
• 存下資源描述後，就能以屬性式命名系統常見的方式查詢：例如查「名為 Alice 的人」，得到對應 Person 資源的引用，應用程式再取回該資源。

屬性式命名的查找與結構化命名根本不同：本質上需要窮舉搜尋所有描述子。描述集中在單一資料儲存時效能還不是大問題；一旦資料分散在多台可能相距遙遠的電腦上，就需要專門的技術。以下即是分散式環境下的幾類解法。

階層式實作：LDAP#

處理分散式目錄服務的常見做法是結合結構化命名與屬性式命名，Microsoft 的 Active Directory 等眾多系統廣泛採用；其中多數使用或依賴輕量級目錄存取協定（Lightweight Directory Access Protocol, LDAP）。LDAP 目錄服務衍生自 OSI 的 X.500 目錄服務——如同許多 OSI 服務，其實作品質阻礙了普及，得靠簡化才變得可用。

資料模型#

• LDAP 目錄服務由一組紀錄構成，稱目錄項目（directory entry），地位相當於 DNS 的資源紀錄。每筆紀錄是一組（屬性, 值）配對，屬性有型別，並區分單值與多值屬性（多值通常代表陣列或清單）。
• LDAP 標準定義了一套命名慣例：屬性 Country（縮寫 C）、Locality（L）、Organization（O）、OrganizationalUnit（OU）、CommonName（CN）分別描述國家、地點、組織、部門與常用名稱。CN 常作為在目錄局部範圍內（可能有歧義的）識別名稱——例如在其他四個屬性已定的前提下，「Main server」也許就足以找到某筆項目。範例中的多值屬性如 Mail_Servers 可同時列出多台郵件伺服器。

• 全部目錄項目的集合稱目錄資訊庫（Directory Information Base, DIB）。DIB 的關鍵是每筆紀錄有全域唯一名稱，可供查找：唯一名稱由紀錄中一串命名屬性組成，每個命名屬性稱相對辨別名稱（Relative Distinguished Name, RDN）。例如以 C、O、OU 依序組成 /C=NL/O=Vrije Universiteit/OU=Comp. Sc.，類比於 DNS 名稱 nl.vu.cs。
• 依序列出 RDN 形成的階層稱目錄資訊樹（Directory Information Tree, DIT）：它就是 LDAP 目錄服務的命名圖，每個節點代表一筆目錄項目，同時也可以像傳統目錄一樣有子節點。例如代表 /C=NL/O=Vrije Universiteit/OU=Comp. Sc./CN=Main server 的節點 N，可再以 Host_Name 作為額外的 RDN，掛上代表主機 star、zephyr 等項目的子節點。

節點的雙重角色由兩種查找操作支援：

• read：給定 DIT 中的路徑名稱，讀回單筆紀錄。
• list：列出給定節點所有外向邊的名稱（每個名稱對應一個子節點），不回傳任何紀錄。

實作與搜尋#

實作 LDAP 目錄服務的方式與實作 DNS 這類命名服務大同小異，差別在 LDAP 支援更多查找操作：

• 大規模目錄的 DIT 會分割並分散到多台伺服器，稱目錄服務代理（Directory Service Agent, DSA）；每個分割相當於 DNS 的一個區。DSA 的行為與一般名稱伺服器類似，但額外提供進階搜尋等典型目錄服務。
• 用戶端以**目錄使用者代理（Directory User Agent, DUA）**代表，類似結構化命名中的名稱解析器，依標準化存取協定與 DSA 交換資訊。
• LDAP 與 DNS 實作的真正差異在對 DIB 的搜尋設施：可給定一組屬性準則搜尋目錄項目。例如列出 Vrije Universiteit 所有主伺服器：

answer = search("&(C=NL)(O=Vrije Universiteit)(OU=*)(CN=Main server)")

此查詢不限定部門（OU=*），但要求每筆結果的 CN 等於 Main server。

目錄服務的搜尋一般是昂貴操作：上例得搜遍每個部門的所有項目、再合併結果，通常意味著存取 DIT 的多個葉節點、動用多台 DSA。相比之下，命名服務的查找常只需存取單一葉節點。

進一步的規模化與其極限：

• Active Directory 允許多棵樹並存互連，形成 LDAP 網域的森林（forest），搜尋複雜度隨之暴增。因應之道是假設有一台可先行查詢的全域索引伺服器（global catalog），由索引指出還需搜尋哪些 LDAP 網域。
• LDAP 本身雖已利用階層取得擴展性，仍常與 DNS 結合：每棵 LDAP 樹須可從根（Active Directory 稱 domain controller）存取，根常以 DNS 名稱為人所知，而該名稱又可透過 SRV 紀錄查得。
• LDAP 是支援屬性式命名的標準方式。循此傳統路線的較新目錄服務也出現在網格計算與 Web 服務領域，如 UDDI（universal directory and discovery integration）。這類服務假設由一個或少數節點合作維護簡單的分散式資料庫，技術上並無新意；其基本模式一律是：讓應用程式可存取多個這種資料庫，由應用程式自己分別查詢各資料庫再彙整結果——中介軟體的支援也就僅止於此。

去中心化實作#

隨著 P2P 系統興起，研究者也在尋找去中心化屬性式命名的解法。關鍵問題是把（屬性, 值）配對有效地映射開來，讓搜尋不必窮舉整個屬性空間。

映射到分散式雜湊表：INS/Twine#

先考慮以 DHT 支援（屬性, 值）配對、且查詢是配對的連言（conjunction）（如 LDAP：使用者列出屬性與各屬性想要的唯一值）的情形。這類查詢的好處是不需支援範圍——範圍查詢會顯著增加映射到 DHT 的複雜度。

INS/Twine 系統（Balazinska 等人，2002）支援這種單值查詢：

• 每個實體（稱資源）以可能階層化的屬性描述，描述先轉成屬性值樹（attribute-value tree, AVTree），再據以編碼、映射到 DHT。
• 核心手法：對每一條從根出發的路徑各算一個雜湊值——路徑以連結（屬性）開頭，結束於節點（值）或另一個連結。以「type: book, author: Tolkien, title: LOTR; genre: fantasy」的描述為例，會產生六個雜湊：hash(type-book)、hash(type-book-author)、hash(type-book-author-Tolkien)、hash(type-book-title)、hash(type-book-title-LOTR)、hash(genre-fantasy)。

• 負責各雜湊值的節點都保存（指向）實際資源的引用——此例中有六個節點存放這本書的資訊。冗餘的回報是支援部分查詢：查「Tolkien 寫的書」轉成 AVTree 後只算出前三個雜湊，送往存有 Tolkien 書籍資訊的節點，至少會回傳 Lord of the Rings。

• 像 hash(type-book) 這種過於一般、會大量產生的雜湊可從系統中濾除；而且不難看出只需評估最專一的那些雜湊。

支援範圍查詢：SWORD#

找房子的人通常要指定價格落在某區間——查詢含範圍時怎麼辦？SWORD 資源探索系統（Oppenheimer 等人，2005）的做法：

• 資源描述的（屬性, 值）配對先轉成 DHT 的鍵。注意描述裡的配對永遠是單值，只有查詢可能含範圍。
• 計算雜湊時屬性名稱與值分開編碼：鍵中特定位元識別屬性名稱、其他位元識別值，另加若干隨機位元保證唯一性。如此屬性空間被妥善分割：n 位元編屬性名稱就能有 2^n 個伺服器群組（每個屬性名稱一組）；m 位元編值則可在群組內再分割。DHT 只用於散布屬性名稱。
• 每個屬性名稱的值域切成子範圍，每個子範圍指派一台伺服器。例：屬性 a1 值域 [1..10]、a2 值域 [101..200]；S11 管 a1 的 [1..5]、S12 管 [6..10]；S21 管 a2 的 [101..150]、S22 管 [151..200]。資源取值 (a1 = 7, a2 = 175) 時，須通知 S12 與 S22。
• 優點：範圍查詢容易支援——查「a2 介於 165 與 189 的資源」可直接轉給 S22 回答。缺點：更新得送往多台伺服器；而且負載均衡並不明朗——若某些範圍查詢特別熱門，特定伺服器會接下大部分查詢（DHT 系統的這個負載均衡問題見 Bharambe 等人，2004）。

語意重疊網路#

去中心化實作已展現節點越來越高的自主性（比分散式 LDAP 系統更不怕節點加入退出）。當節點手上的資源描述沒有任何事先決定的散布方案、單純等著被別人發現時，自主性又更進一步——節點被迫自己去發現所求資源在哪，這正是第 2 章談過的非結構化重疊網路的典型情境。

要讓搜尋有效率，節點必須握有「最可能答得出自己查詢」的鄰居引用。若假設節點 P 發出的查詢與 P 自己持有的資源強相關，我們要給 P 的就是一組語意相近鄰居的連結（這種清單即部分視圖，partial view）。語意鄰近可以有不同定義，但歸結起來就是追蹤資源相似的節點；節點與這些連結構成語意重疊網路（semantic overlay network）。

• 共同資料綱要（schema）路線：假設各節點維護的中介資訊有共同性——所有節點以同一組屬性（更精確說同一資料綱要）描述資源（Crespo 與 Garcia-Molina，2003）。有綱要就能定義節點間的相似度函式，每個節點只保留 K 個最相似鄰居的連結，找資料先問它們。這只在「查詢與本節點內容相關」的假設下才合理。

假設資料綱要有共同性通常是錯的：實務上各節點的資源中介資訊高度不一致，要對「描述什麼、怎麼描述」達成共識幾近不可能。語意重疊網路一般得另尋相似度的定義。

• 被動建構：乾脆拋開屬性，只用檔名這類極簡描述子，靠記錄「哪些節點對檔案搜尋給過肯定回應」來建構重疊網路。例如 Sripanidkulchai 等人（2003）先把查詢送給語意鄰居，沒找到才做（有限的）廣播，廣播結果可能回頭更新語意鄰居清單。有趣的是，若請語意鄰居把查詢再轉給它們的語意鄰居，效果微乎其微（Handrukande 等人，2004）——可用**小世界效應（small-world effect）**解釋：Alice 的朋友們彼此也是朋友（Watts，1999）。
• 主動建構：Voulgaris 與 van Steen（2005）在節點 P、Q 的檔案清單 FL_P 與 FL_Q 上定義簡單的語意鄰近函式——數兩者共有的檔案數，目標是讓每個節點只保留共同檔案最多的鄰居。作法是雙層 gossip：底層跑流行病協定，維護一份均勻隨機節點的部分視圖；頂層透過 gossip 維護語意相近鄰居清單——P 從目前清單隨機選鄰居 Q 交換，但訣竅是 P 只送出「對 Q 而言語意最近」的項目；P 收到 Q 的項目後，最終保留的部分視圖只剩語意最近的節點。事實證明頂層的部分視圖會快速收斂到最佳解。

語意重疊網路與去中心化搜尋關係密切——這也呼應本章開頭的觀察：屬性式命名正逐步以分散式搜尋技術取代傳統名稱解析。各類 P2P 系統中搜尋技術的完整綜覽見 Risson 與 Moors（2006）。