快取與複製在分散式檔案系統中舉足輕重，尤其是為廣域網路設計的系統。本節依序考察用戶端快取、伺服器端複製，以及點對點檔案共享系統與 Grid 系統中的複製。

用戶端快取#

以 NFS 與 Coda 兩個範例系統來看快取在實務上如何部署。

NFS 的快取#

NFSv3 基本上把快取留在協定之外，導致各實作採取不同的快取策略，多數從不保證一致性：好一點的情況是快取資料比伺服器落後幾秒，也有實作允許落後 30 秒而用戶端渾然不覺——這種狀況並不理想。NFSv4 解決了部分一致性問題，但快取一致性本質上仍交由實作自行決定。

NFS 假設的一般快取模型：每個用戶端可有記憶體快取，存放先前從伺服器讀到的資料；此外還可有磁碟快取作為記憶體快取的延伸，採用相同的一致性參數。用戶端通常快取四類東西：檔案資料、屬性、file handle 與目錄，各有不同的一致性策略。

檔案資料的快取——NFSv4 支援兩種方式。最簡單的一種：用戶端開檔後把讀到的資料放進快取，寫入也可先在快取進行；關檔時若有修改，必須把快取資料沖回伺服器——這正對應前一節的 session semantics。此外：

• 檔案（部分）被快取後，關檔了資料仍可留在快取；同一機器上的多個用戶端可共享一份快取。
• NFS 要求：重新開啟先前關閉且已（部分）快取的檔案時，用戶端必須**立即重新驗證（revalidate）**快取資料——檢查檔案最後修改時間，若快取已過時則使其失效。

開檔委派（open delegation）——NFSv4 中伺服器可在開檔時把部分權利委派給用戶端：允許用戶端機器在本地處理來自同機其他用戶端的 open 與 close。正常情況下，開檔能否成功（例如要考量 share reservation）由伺服器把關；有了 open delegation，用戶端機器有時可以自行裁決，免去聯絡伺服器。

• 例如伺服器把某檔案的開啟委派給一個要求寫權限的用戶端後，同機其他用戶端的檔案鎖定請求也能在本地處理；其他機器的用戶端的鎖定請求仍由伺服器處理（直接拒絕其存取即可）。
• 這套方案對只要求讀權限的委派行不通：同機的其他本地用戶端想要寫權限時，必須聯絡伺服器，無法在本地處理。

委派的重要後果是伺服器必須能收回（recall）委派，例如另一台機器上的用戶端需要取得該檔案的存取權時。收回需要伺服器對用戶端做回呼（callback），以底層 RPC 機制實作。

回呼要求伺服器記住它把檔案委派給了哪些用戶端——又一個 NFS 伺服器無法維持無狀態的例子。而且委派加上有狀態伺服器，在用戶端與伺服器故障時會產生各種問題：例如檔案委派給了一個此後毫無回應的用戶端，伺服器該怎麼辦？實務上**租約（lease）**通常就是恰當的解法。

屬性、file handle 與目錄的快取——用戶端可以快取屬性值，但一致性大致自理：同一檔案的屬性被兩個用戶端快取，除非它們自行互相同步，否則可能不同。屬性的修改應立即轉送伺服器，即採寫穿（write-through）快取一致性策略。file handle（名稱到 handle 的映射）與目錄的快取也採類似做法。為緩解不一致的影響，NFS 對快取的屬性、handle 與目錄使用租約：時間一到，快取項目自動失效，再次使用前必須重新驗證。

Coda 的用戶端快取#

用戶端快取對 Coda 的運作至關重要，理由有二：一是擴展性，二是提高容錯度——用戶端因此較不依賴伺服器的可用性。基於這兩點，Coda 的用戶端永遠快取整個檔案：檔案一被開啟（無論讀寫），完整副本就傳到用戶端快取起來。

Coda 的快取一致性以回呼（callback）維護。伺服器為每個檔案追蹤哪些用戶端快取了本地副本：伺服器對用戶端記錄一個回呼承諾（callback promise）。用戶端第一次更新其本地副本時通知伺服器，伺服器隨即向其他用戶端發送失效訊息——這種失效訊息稱為回呼撤銷（callback break），因為伺服器發出後便丟棄它對該用戶端持有的回呼承諾。

這套方案的妙處：只要用戶端知道自己在伺服器那裡仍有未撤銷的回呼承諾，就能安全地在本地存取檔案。用戶端開檔時發現檔案還在快取裡，先向伺服器確認承諾是否仍有效；若有效，就不必重新從伺服器傳檔。

以兩個 session 為例：A 開啟 session S_A 時伺服器記下回呼承諾，B 開啟 S_B 時亦然。B 關閉 S_B（傳回更新）時，伺服器對 A 發出 callback break、撤銷對 A 的承諾。由於 Coda 的交易式語意，A 關閉 S_A 時不會發生任何特別的事，關閉照常被接受。其後果是：A 之後想再開新 session 時會發現本地副本已失效，必須向伺服器抓取最新版本；而 B 再開 session 時會發現伺服器仍持有對它的回呼承諾，可直接重用上個 session 留下的本地副本。

可攜式裝置的用戶端快取#

許多儲存裝置已不能假設永遠連著網路：PDA、筆電、影音播放器等常是透過底座（cradle/docking station）半永久連接。多數情況下這些裝置採顯式的上傳/下載模型維護檔案；若把儲存裝置視為分散式檔案系統的一部分，事情可以簡化——存取檔案時，可能從本地裝置取，也可能經連線從系統其他地方取，兩種情況必須區分。

一種很簡單的做法（Tolia 等人提出）：在可攜裝置上本地儲存檔案內容的密碼學雜湊，用以重導向對應內容的請求。例如本地存目錄清單時，不存每個列出檔案的資料，只存算出的雜湊；抓檔時系統先檢查檔案是否在本地且為最新——過時的檔案雜湊會與目錄清單中存的不同。檔案在本地就直接回傳，否則才需要資料傳輸。

裝置斷線時當然無法傳輸資料。要以高機率確保「可能會用到的檔案」已存於裝置上，需要**檔案預取（prefetching）**技術，而非一般快取固有的隨需傳輸；不過對許多可攜式儲存裝置，可以預期使用者會用專門程式預先安裝檔案。

伺服器端複製#

與用戶端快取相比，分散式檔案系統的伺服器端複製較不常見。為了可用性當然會複製，但就效能而言，把整個檔案（或其大部分）放到用戶端本地的快取更划算。用戶端快取之所以流行，是因為實務顯示檔案共享相對罕見，即使共享也多半只是讀取——此時快取是絕佳解法。

為效能做伺服器端複製還有一個問題：高複製度加上低讀寫比可能反而拖垮效能。原因很好懂：每次更新都得在每個複本執行——N 份複本的檔案，一個更新請求變成 N 倍的更新操作；並行更新還需要同步，帶來更多通訊與效能損失。

因此，檔案伺服器一般只為容錯而複製。以下以 Coda 說明。

Coda 的伺服器複製#

Coda 允許複製檔案伺服器，複製單位是稱為**卷（volume）的檔案集合。volume 本質上對應一個 UNIX 磁碟分割區（即作業系統直接支援的傳統檔案系統），只是通常小得多。持有某 volume 副本的 Coda 伺服器集合稱為該 volume 的 Volume Storage Group（VSG）；故障之下，用戶端未必能連上 VSG 的所有成員——用戶端當下能聯絡到的 VSG 子集稱為其 Accessible Volume Storage Group（AVSG）。AVSG 為空時，用戶端即處於斷線（disconnected）**狀態。

Coda 用複製寫入協定維護複製 volume 的一致性，具體是 Read-One, Write-All（ROWA）的變體：讀檔時聯絡 AVSG 中的一個成員；關閉更新過的檔案的 session 時，把檔案平行傳給 AVSG 的每個成員（用前面介紹的 MultiRPC 完成）。

只要沒有故障（每個用戶端的 AVSG 等於 VSG），一切正常；有故障就可能出事。考慮一個 volume 複製在三台伺服器 S1、S2、S3：用戶端 A 的 AVSG 只涵蓋 S1 與 S2，用戶端 B 只連得上 S3。

Coda 對檔案複製採樂觀策略：A 與 B 都被允許開檔寫入 f、各自更新、把副本傳回各自 AVSG 的成員——VSG 裡於是存了不同版本的 f。問題是如何偵測並解決這種不一致。

Coda 的解法是版本向量方案：VSG 中的伺服器 S_i 為其中每個檔案 f 維護 Coda 版本向量 CVV_i(f)。CVV_i(f)[j] = k 表示 S_i 知道 S_j 至少已看過 f 的第 k 版；CVV_i(f)[i] 是 S_i 上目前存放的 f 的版本號，f 在 S_i 的更新會使其遞增。版本向量與向量時戳完全類似。

點對點檔案系統中的複製#

在點對點檔案共享系統中，複製也很重要——主要為了加速搜尋與查找，也用於節點間的負載平衡。這些系統的重要性質是幾乎所有檔案都唯讀，更新只以「新增檔案」的形式出現。討論需區分非結構化與結構化系統。

非結構化點對點系統#

非結構化系統的根本特徵：查找資料等於在網路中搜尋資料——節點把搜尋查詢廣播給鄰居，鄰居再轉發，依此類推。純靠廣播搜尋通常不是好主意，需要特別措施避免效能問題。無論如何限制廣播，檔案有複本，搜尋就更容易更快。極端做法是把檔案複製到所有節點，搜尋任何檔案都能完全在本地完成；但節點容量有限，全複製不可行。問題於是變成尋找最佳複製策略，最佳性以「找到檔案前需處理查詢的不同節點數」定義。

Cohen 與 Shenker 在「複製可受控」的假設下研究了這個問題，考慮兩個極端策略：

• 均勻（uniform）策略：每個檔案的 n 份副本均勻散布全網，無視不同檔案的請求率（受歡迎程度）差異。
• 熱門（popular）策略：依搜尋頻率複製——檔案越熱門，建立並散布的複本越多。

出人意料的結果：就「平均需查詢的節點數」而言，均勻與熱門兩種策略表現一樣好——兩者的查詢分布相同，且熱門策略下文件的分布跟著查詢分布走。更有趣的是，介於兩者「之間」的任何配置都更好；求得這樣的配置可行但不容易。

結構化點對點系統#

結構化系統的查找本來就有效率，複製主要用於節點間的負載平衡。（先前章節提過，一種「結構化」的複製甚至能把平均查找步數壓到 O(1)。）就負載平衡而言，需要不同的做法：

• 常用方法是沿查詢路徑複製：把檔案沿查詢從來源到目的地走過的路徑複製。效果是多數複本落在負責存放該檔案的節點附近，請求率高時確實能為其卸載；但此策略不考慮其他節點的負載，容易造成系統失衡。
• Gopalakrishnan 等人提出考量查詢路徑上節點當前負載的方案：把複本存到查詢的來源節點，並在路徑節點快取指向複本的指標。具體而言，查詢從節點 P 經 R 路由到 Q 時，R 檢查自己是否該把某些檔案卸載給 P：R 看自己的查詢負載，若相對於 P 的負載，它為自己存放的檔案服務了太多查找請求，就可以請 P 安裝 R 最熱門檔案的副本。若 P 接受了檔案 f，從 P 到 R 路徑上經過的每個節點都會安裝「f 的複本可在 P 找到」的指標。

要讓這套方案運作，散布複本位置資訊很重要：查詢在覆蓋網路中路由時，節點可順帶傳遞自己所存複本的資訊，促成更多指標的安裝，讓節點能做出把請求重導向到複本持有者的明智決定。這些指標放在容量有限的快取中，以簡單的 LRU（least-recently used）策略汰換——從沒人問的檔案的指標很快被移除。

Grid 系統中的檔案複製#

最後看 Grid 計算中的複製。效能在此至關緊要：許多 Grid 應用高度計算密集，還常需處理巨量資料，因此大量心力投入「把檔案複製到應用執行之處」。手段卻（有點）出乎意料地簡單。

關鍵觀察：許多 Grid 應用的資料是唯讀的——資料常來自感測器或其他應用，產生並儲存後很少更新或修改。因此資料複製可以放手大量使用，實際上也正是如此。

• 資料集有時大到需要特別措施，避免資料提供者（存放資料集的機器）因需要傳輸的資料量而過載；另一方面，因為資料被大量複製，取用副本的負載平衡反而不是大問題。
• Grid 的複製主要圍繞著找出最佳的複製來源。這可由專門的**複本定位服務（replica location service）**解決，與命名系統的定位服務非常類似。Globus toolkit 發展出的一種明顯做法，是用 Chord 這類 DHT 系統做複本的去中心化查找：用戶端把檔名交給服務的任一節點，檔名被轉成鍵後查找，回傳給用戶端的資訊即含所求檔案的聯絡位址。
• 為求簡單，定位到的檔案用類 FTP 協定從各站點下載，之後用戶端可把自己的複本註冊到複本定位服務。整體架構相當直接了當。