扁平名稱對機器友善，對人卻不方便。命名系統因此普遍支援由簡單、人可讀的名稱組合而成的結構化名稱（structured names）——檔案命名如此，網際網路的主機命名也如此。本節討論結構化名稱及其解析成位址的方式。

名稱空間#

名稱通常組織在名稱空間（name space）中。結構化名稱的名稱空間可表示為帶標籤的有向圖，即命名圖（naming graph），含兩類節點：

• 葉節點（leaf node）：代表被命名的實體，沒有外向邊。通常存放實體的資訊（如位址），或直接存放實體狀態（如檔案系統的葉節點存放完整檔案內容）。
• 目錄節點（directory node）：有多條外向邊，每條邊帶一個名稱標籤。目錄節點存放一張目錄表（directory table），每筆是（邊標籤, 節點識別碼）配對。命名圖中每個節點本身也是分散式系統中的實體，各有識別碼。

其他關鍵概念：

• 只有外向邊、沒有內向邊的節點是命名圖的根（root）。命名圖可以有多個根，但多數命名系統為求簡單只有一個。
• 圖中一條路徑可用其邊標籤序列表示：N:<label-1, label-2, ..., label-n>，N 是路徑起點節點。這種序列稱路徑名稱（path name）；起點是根的稱絕對路徑名稱，否則是相對路徑名稱。
• 檔案系統慣用單一字串表示路徑名稱，以分隔字元（如 /）串接標籤，並以其標示是否為絕對路徑：n0:<home, steen, mbox> 慣寫成 /home/steen/mbox。多條路徑通往同一節點時，該節點就有多個路徑名稱。這種字串表示法不限於檔案系統——Plan 9 把行程、主機、I/O 裝置、網路介面等所有資源都當成檔案來命名，相當於用單一命名圖涵蓋全系統資源。

名稱永遠是相對於某個目錄節點定義的，因此「絕對名稱」一詞其實有點誤導。同樣容易混淆的是全域與本地名稱：**全域名稱（global name）**不論在系統何處使用都指同一實體（永遠相對於同一個目錄節點解讀）；**本地名稱（local name）**的解讀則取決於使用場合——本質上是「所在目錄被隱含知道」的相對名稱。

名稱空間的組織方式很多：多數只有單一根節點；許多還是嚴格階層式的（命名圖是樹，除根外每個節點恰有一條內向邊，因此每個節點恰有一個絕對路徑名稱）；也有組織成**有向無環圖（DAG）**的（節點可有多條內向邊，但不允許環）；還有連這個限制都沒有的名稱空間。

具體化：UNIX 檔案系統的命名圖實作

傳統 UNIX 檔案系統中，目錄節點對應檔案目錄、葉節點對應檔案，有單一根目錄。命名圖的實作是檔案系統實作不可分割的一部分：邏輯磁碟上的連續區塊，一般分為開機區塊（boot block）、超級區塊（superblock）、一串索引節點（inode）與檔案資料區塊。

• boot block：開機時自動載入主記憶體的特殊區塊，用來載入作業系統。
• superblock：整個檔案系統的資訊——大小、哪些磁碟區塊未配置、哪些 inode 未使用等。
• inode：以索引編號指涉，0 號保留給根目錄的 inode。每個 inode 記錄其檔案資料在磁碟上的位置，以及擁有者、建立與修改時間、保護資訊等；給定 inode 編號即可存取對應檔案。
• 每個目錄本身也實作為檔案（根目錄亦然），內容是檔名到 inode 編號的映射。可見 inode 編號正對應命名圖中的節點識別碼。

名稱解析#

名稱空間提供了以名稱存取實體資訊的便利機制：給定路徑名稱，應能查出該名稱所指節點中存放的資訊。查找名稱的過程稱名稱解析（name resolution）。

解析 N:<label1, label2, ..., labeln> 的流程：從節點 N 開始，在其目錄表查 label1，得到下一個節點的識別碼；到該節點的目錄表查 label2；依此類推。若路徑確實存在，解析停在最後一個節點並回傳其內容。以 UNIX 為例，節點識別碼是 inode 編號，「存取下一個節點的目錄表」意謂先讀 inode 找出資料位置、再讀含目錄表的資料區塊。

閉包機制#

名稱解析必須知道從哪裡、怎麼開始——這就是閉包機制（closure mechanism）：選定名稱空間中解析的起始節點（Radia，1989）。閉包機制之所以難懂，是因為它必然部分隱含於系統之中，而且各系統做法差異極大：

• UNIX 解析 /home/steen/mbox 前，必須已能存取根節點的目錄表；但根節點本身無從被「查找」——它靠的是「根目錄的 inode 是邏輯磁碟第一個 inode」這個約定，實際位移由 superblock 欄位加上作業系統寫死的 superblock 內部結構知識算出。解析要能開始，必得有某個既存機制。
• 字串「0031204430784」多數人不知如何處置，直到被告知這是電話號碼——這個資訊就足以啟動解析（撥號），其餘交給電話系統。
• 環境變數是典型的本地名稱：UNIX 的 HOME 指向使用者的家目錄，每個使用者有自己的副本，初始化為對應的全系統名稱。環境變數的閉包機制確保變數名稱是在使用者專屬的表中查找解析的。

連結與掛載#

與名稱解析密切相關的是別名（alias）——同一實體的另一個名稱（環境變數即一例）。命名圖中有兩種實作方式：

• 硬連結（hard link）：直接允許多個絕對路徑名稱指向同一節點。例如 /keys 與 /home/steen/keys 都指向節點 n5。
• 符號連結（symbolic link）：以葉節點 N 代表實體，但 N 存的不是位址或狀態，而是一個絕對路徑名稱。解析走到 N 時，先取回其中存的路徑名稱，再繼續解析那個新名稱。例如 /home/steen/keys 指向的節點存著 /keys，即是指向 n5 的符號連結。

名稱解析還能用來透明地合併不同的名稱空間，即掛載（mounting）：

• 讓一個目錄節點存放另一個名稱空間（外部名稱空間，foreign name space）中某目錄節點的識別碼。存放識別碼的節點稱掛載點（mount point），外部名稱空間中被指向的節點稱被掛載點（mounting point），通常是外部名稱空間的根。解析經過掛載點時，改到被掛載點的目錄表繼續。
• 在分散式系統中，各名稱空間可能由不同機器上的不同伺服器實作，掛載外部名稱空間至少需要三項資訊：存取協定的名稱（解析成協定實作）、伺服器的名稱（解析成位址）、外部名稱空間中被掛載點的名稱（由外部名稱空間的伺服器解析成節點識別碼）。這三個名稱可合併表示為一個 URL。非分散式系統則三者可能都不需要——UNIX 掛載沒有存取協定與伺服器，被掛載點就是外部名稱空間的根目錄。

延伸案例：以 NFS URL 掛載遠端名稱空間

使用者的筆電要存取遠端檔案伺服器上的檔案，雙方都配置了 Sun 的網路檔案系統（Network File System, NFS）。NFS URL 如 nfs://flits.cs.vu.nl//home/steen，命名了 NFS 伺服器 flits.cs.vu.nl 上的目錄 /home/steen，並指明以 NFS 協定存取。其中 nfs 是全球公認如何解讀的知名名稱，解析成 NFS 協定的實作；伺服器名稱由 DNS 解析成位址；/home/steen 由外部名稱空間的伺服器解析。

用戶端機器上，根目錄下的子目錄 /remote 專門收納外部名稱空間的掛載點，其中 /remote/vu 這個目錄節點存著上述 URL。解析 /remote/vu/mbox 時：從本機根目錄一路走到 /remote/vu，取回 URL，據此以 NFS 協定聯絡 flits.cs.vu.nl、存取 /home/steen，再讀取其中的 mbox，解析結束。使用者只要執行：

cd /remote/vu
ls -l

就能列出遠端 /home/steen 的檔案，完全不必理會實際的遠端存取細節——本機名稱空間與遠端以 /home/steen 為根的名稱空間，在用戶端看來就是單一名稱空間，理想上只察覺得到些許效能損失。

名稱空間的實作#

名稱空間是**命名服務（naming service）的核心：讓使用者與行程新增、移除、查找名稱的服務，由名稱伺服器（name server）**實作。侷限於區域網路的系統常可用單一名稱伺服器；但大規模、實體可能遍布廣大地理範圍的分散式系統，必須把名稱空間的實作分散到多台名稱伺服器上。

名稱空間的分層#

大規模（乃至全球）名稱空間通常是階層式的（假設單一根節點）。Cheriton 與 Mann（1989）把它劃分成三個邏輯層：

• 全域層（global layer）：根節點與邏輯上接近根的高層目錄節點。特徵是穩定——目錄表極少變動，節點常代表組織或組織群。
• 管理層（administrational layer）：同一組織內共同管理的目錄節點，代表屬於同一組織或行政單位的實體群——如各部門一個目錄節點、存放所有主機的節點、命名所有使用者的起點節點等。相對穩定，但變動頻率高於全域層。
• 經營層（managerial layer）：經常變動的節點——本地網路的主機、共享檔案（程式庫、二進位檔）、使用者自訂的目錄與檔案。此層不只由系統管理員維護，一般使用者也會維護。

DNS 名稱空間的劃分即為一例：名稱空間切成互不重疊的區（zone），每個區由一台獨立的名稱伺服器實作。

各層名稱伺服器的可用性與效能需求截然不同：

全域層與管理層的名稱伺服器最難實作：為了可用性與效能而必須採用的複製與快取，本身會引入一致性問題；快取與複本又散布在廣域網路上，通訊延遲長，同步更加困難。

迭代式與遞迴式名稱解析#

名稱空間分散在多台伺服器上，會影響解析的實作。假設暫不考慮複製與用戶端快取，每個用戶端透過本地的**名稱解析器（name resolver）**負責執行解析。以解析 root:<nl, vu, cs, ftp, pub, globe, index.html>（即 ftp://ftp.cs.vu.nl/pub/globe/index.html）為例，有兩種實作：

• 迭代式名稱解析（iterative name resolution）：解析器把完整名稱交給（位址眾所周知的）根名稱伺服器。根伺服器盡力解析——此例只能解析 nl——回傳對應名稱伺服器的位址；用戶端再把剩餘名稱 nl:<vu, cs, ftp, ...> 交給那台伺服器，依此類推：vu、cs、ftp 逐段解析，最後取得 FTP 伺服器位址。實務上，最後聯絡 FTP 伺服器取檔的那一步由用戶端行程另行執行——用戶端通常只把 root:<nl, vu, cs, ftp> 交給解析器，取回 FTP 伺服器的位址即可。

• 遞迴式名稱解析（recursive name resolution）：名稱伺服器不把中間結果回給用戶端解析器，而是直接把剩餘名稱交給下一台名稱伺服器：根伺服器找到 nl 節點的伺服器後，請它解析 nl:<vu, cs, ftp, ...>；層層遞迴，結果一路回傳到根，再回給用戶端。

兩者的取捨：

• 遞迴式的缺點是對每台名稱伺服器的效能要求較高——伺服器得負責整段路徑的解析。負擔之重，使得全域層的名稱伺服器通常只支援迭代式解析。
• 遞迴式的第一個優點是快取更有效：每台名稱伺服器能逐步學到下層各節點的伺服器位址。例如根伺服器解析完 root:<nl, vu, cs, ftp> 後可快取結果；中間查找結果（如 nl 伺服器查到的 vu 伺服器位址）也能隨遞迴回傳、在沿途各伺服器快取。之後另一用戶端請求 root:<nl, vu, cs, flits> 時，根可直接轉給 cs 節點的伺服器解析剩餘的 cs:<flits>。而迭代式的快取必然侷限在用戶端解析器：A 解析過的名稱，B 再解析還是得走一遍同樣的伺服器。折衷做法是組織內設一台共享的本地中介名稱伺服器，統一處理並快取所有解析請求——管理上也方便，只有它需要知道根伺服器在哪。

• 第二個優點是通訊成本常較低。假設用戶端在舊金山、要解析 root:<nl, vu, cs, ftp> 且已知 nl 伺服器位址：遞迴式只需一趟「舊金山 ↔ 荷蘭 nl 伺服器」的越洋往返，其餘（nl→vu、vu→cs）都是荷蘭境內通訊；迭代式則要用戶端分別與 nl、vu、cs 三台伺服器越洋往返，總成本約為三倍。

實例：網域名稱系統（DNS）#

**網域名稱系統（Domain Name System, DNS）**是當今最大的分散式命名服務之一，主要用來查找主機與郵件伺服器的 IP 位址。

Levien（2005）對 DNS 的評估得出一個有點意外的結論：即便過了這麼多年，DNS 毫無需要被替換的跡象。主因可歸於設計者對「把事情保持簡單」的深刻理解——分散式系統其他領域的實踐顯示，有這種天分的人並不多。

DNS 名稱空間#

• 階層式的有根樹。標籤（label）是不分大小寫的英數字串，最長 63 字元；完整路徑名稱最長 255 字元。
• 字串表示法從最右邊的標籤列起、以點（.）分隔；根以一個點表示。root:<nl, vu, cs, flits> 寫成 flits.cs.vu.nl.（最右邊的點表示根節點，通常省略）。
• 除根之外每個節點恰有一條內向邊，該邊的標籤同時作為節點名稱。子樹稱網域（domain），指向其根節點的路徑名稱稱網域名稱（domain name）——與路徑名稱一樣有絕對與相對之分。
• 節點的內容是一組資源紀錄（resource records）。一個節點常同時代表多個實體：如 vu.nl 既代表網域、也代表區（domain 可由多個互不重疊的 zone 實作）。

主要的資源紀錄類型：

• SOA（start of authority）：區的權責資訊——管理者信箱、可取得區資料的主機名稱等。
• A（address）：主機的 IP 位址；多宿主機每個位址一筆 A 紀錄。
• MX（mail exchange）：形同指向郵件伺服器節點的符號連結，例如 cs.vu.nl 的 MX 紀錄指向處理 cs.vu.nl 網域來信的郵件伺服器；可有多筆。
• SRV：特定服務的伺服器名稱，服務以「名稱＋協定」識別。好處是用戶端不必知道提供服務的主機 DNS 名稱，只要服務名稱標準化即可查出主機。
• NS（name server）：實作該區的名稱伺服器名稱。原則上每個節點都能存 NS 紀錄，實作上只有代表區的節點需要。
• CNAME：存放主機的正規名稱（canonical name），實作別名——存 CNAME 紀錄的節點名稱就是符號連結。
• PTR（pointer）：IP 位址到主機名稱的反向映射。DNS 維護 in-addr.arpa 網域，其中節點以 IP 位址命名，例如 IP 為 130.37.20.20 的主機對應節點 20.20.37.130.in-addr.arpa，其 PTR 紀錄存正規主機名稱。
• HINFO（host info）：主機的機型與作業系統等補充資訊。
• TXT：使用者覺得有用的任意其他資料。

DNS 實作#

DNS 名稱空間大致可分為全域層與管理層；經營層（一般是本地檔案系統）正式上不屬於 DNS、也不由它管理。

• 每個區由一台名稱伺服器實作，幾乎必然複製以確保可用性。更新由主要名稱伺服器（primary name server）處理——直接修改其本地 DNS 資料庫；次要伺服器不直接動資料庫，而是向主要伺服器請求傳送內容，稱區轉移（zone transfer）。
• DNS 資料庫是一小組檔案，最重要的一個含該區所有節點的全部資源紀錄；節點直接以網域名稱識別，「節點識別碼」化約為檔案中的隱含索引。

延伸案例：cs.vu.nl 區的資料庫內容

書中展示了 cs.vu.nl 區資料庫檔案的節選，可看出典型配置：

• 節點 cs.vu.nl 同時代表網域與區：SOA 紀錄存此檔案的有效性資訊；四筆 NS 紀錄以正規主機名稱指出四台名稱伺服器；TXT 紀錄補充區的說明（名稱伺服器無法自動處理）；MX 紀錄指定收信的郵件伺服器，名稱前的數字是選擇優先權——寄信方應先嘗試數字最小的。
• 名稱伺服器 star.cs.vu.nl 配了兩張網路介面、各有一筆 A 紀錄：一條網路連結壞了伺服器仍可達，提高強健性。
• 郵件伺服器 zephyr.cs.vu.nl 另有備援郵件伺服器 tornado.cs.vu.nl。
• 部門的 Web 與 FTP 伺服器由同一台機器 soling.cs.vu.nl 實作（且該機基本上只跑網際網路服務）：兩個伺服器對檔案系統的視角一致，管理更簡單——WWW 與 FTP 服務常見這種做法。
• 其餘還有舊伺服器叢集與兩台主要印表機的紀錄；印表機位址落在 192.168.0.0–192.168.255.255 的私有位址範圍，只能從本地網路存取。

cs.vu.nl 實作為單一區，故該檔不引用其他區。要指涉實作在另一個區的子網域節點，做法是在上層網域（vu.nl）的描述中給出子網域名稱伺服器的網域名稱與 IP 位址；解析落在 cs.vu.nl 網域內的名稱時，解析會在適當時點改讀 cs.vu.nl 名稱伺服器存放的資料庫。

去中心化的 DNS 實作#

標準 DNS 是伺服器階層：13 台知名根伺服器起頭、數以百萬計的葉端伺服器收尾。高層節點收到的請求遠多於低層，只有靠快取高層的名稱—位址繫結才能避免請求灌爆它們。完全去中心化的方案能徹底避開這些擴展性問題：把 DNS 名稱雜湊成鍵，再到 DHT（或根節點完全分割的階層式定位服務）查找。

• 代價：失去原名稱的結構，可能無法高效實作「找出某網域的所有子節點」這類操作。
• 好處：擴展性。如 Walfish 等人（2004）所論，當需要大量名稱時，以識別碼作為語意中立的資料存取途徑，可讓不同系統共用同一個命名系統——因為如何高效支撐巨量扁平名稱已是被充分理解的問題；要做的只是維護識別碼到名稱的映射，名稱可以來自 DNS 空間、可以是 URL 等等。搭配讓使用者或組織採用嚴格的本地名稱空間（完全類比於電腦上維護私有的環境變數設定），識別碼的使用可以更簡便。