支援複製的分散式系統都得回答一個關鍵問題：副本應該放在哪裡、何時放、由誰放，以及之後用什麼機制維持一致。放置問題本身應拆成兩個子問題：

• 副本伺服器放置（replica-server placement）：找出放置「能承載（部分）資料儲存的伺服器」的最佳位置。
• 內容放置（content placement）：找出放置內容的最佳伺服器——常常是在為單一資料項找最佳位置。

兩者差異微妙但重要，卻常被混為一談。顯然，內容放置之前必須先完成伺服器放置。以下先看這兩個放置問題，再討論管理複製內容的基本機制。

副本伺服器放置#

副本伺服器的放置並不是被深入研究的問題，原因很簡單：它往往更像管理與商業決策，而非最佳化問題。儘管如此，分析客戶端與網路特性仍有助於做出明智決定。

計算最佳放置的方法很多，但都可歸結為「從 N 個位置中選出最好的 K 個（K < N）」的最佳化問題——已知是計算上困難的問題，只能靠啟發式（heuristics）求解：

• Qiu 等人（2001）：以客戶端與位置之間的距離（以延遲或頻寬度量）為出發點，每次選一台伺服器，使「在已放置 k 台的前提下，該伺服器與其客戶端的平均距離最小」。
• Radoslavov 等人（2001）：忽略客戶端位置，只看由自治系統（Autonomous System, AS）構成的網際網路拓撲。AS 可視為「節點都跑同一路由協定、由單一組織管理」的網路（2006 年 1 月時全球約兩萬多個）。演算法先取最大的 AS，把伺服器放在網路介面（連結）數最多的路由器上，再對次大的 AS 重複，依此類推。

結果顯示，在「客戶端相對於既有拓撲均勻分布於網際網路」的假設下，不看客戶端的放置法與看客戶端的放置法效果相近——但這個假設有多真實並不清楚，尚未被好好研究。

這些演算法的共同問題是計算太昂貴：兩者複雜度都高於 O(N²)，位置數達數千時一次計算可能要跑數十分鐘。遇到**閃電人潮（flash crowd，某網站突然湧入大量請求，網路上經常發生）**時，這是無法接受的——此時必須迅速判斷哪裡需要副本伺服器。

延伸做法：Szymaniak 等人的快速區域選擇法

Szymaniak 等人（2006）發展了能快速找出「適合放副本的區域」的方法。**區域（region）**指「存取相同內容、且彼此間延遲很低」的一群節點；演算法目標是先選出需求最大（節點最多）的區域，再讓區域中的一個節點擔任副本伺服器。

• 假設節點位於 m 維幾何空間中（如前一章所述），基本想法是找出 K 個最大的叢集（cluster），每個叢集指派一個節點承載複製內容。
• 做法是把整個空間切割成格子（cell，m 維超立方體；二維時就是矩形），選出密度最高的 K 個格子放副本伺服器。
• 格子大小是關鍵：太大則多個叢集擠進同一格，選出的伺服器太少；太小則單一叢集橫跨多格，選出的伺服器太多。
• 適當的格子大小可由「節點平均距離」與「所需副本數」的簡單函數算出。用這個格子大小，效果可媲美 Qiu 等人接近最佳的演算法，複雜度卻低得多：O(N × max{log(N), K})。實驗顯示，為 64,000 個節點計算 20 個最佳副本位置約快 50,000 倍，使副本伺服器放置得以即時完成。

內容複製與放置#

談完伺服器放置，接著看內容放置。就內容的複製與放置而言，邏輯上可區分三種副本，可組織成三個同心圓環：最內圈是永久副本，中圈是伺服器發起的副本，外圈是客戶端發起的副本。

永久副本#

**永久副本（permanent replicas）**是構成分散式資料儲存的初始副本集合，數量通常很少。以網站為例，其分散通常是兩種形式之一：

• 網站檔案複製到同一地點的少數幾台伺服器上，請求進來後（例如以輪詢 round-robin 策略）轉發給其中一台。
• 鏡像（mirroring）：網站複製到地理上散布於網際網路的少數幾台鏡像站（mirror sites），客戶端從清單中自行挑選一個。兩種形式的共同點是副本數量少、且大致是靜態配置的。

類似的靜態組織也出現在分散式資料庫（Özsu 與 Valduriez，1999）：資料庫可分散並複製到組成叢集的多台伺服器上——常稱為無共享架構（shared-nothing architecture），強調處理器之間磁碟與主記憶體皆不共享；或者分散到地理上分開的多個站點，這種架構常見於聯邦式資料庫（federated databases）（Sheth 與 Larson，1990）。

伺服器發起的副本#

**伺服器發起的副本（server-initiated replicas）**是為了提升效能、由資料儲存（的擁有者）主動建立的拷貝。例如放在紐約的 Web 伺服器平時應付自如，卻在幾天內突然湧入來自遠方某地的大量請求——此時值得在請求來源區域臨時安裝一批副本。

動態放置副本的問題在 **Web 代管服務（Web hosting services）**中也被積極處理：這類服務提供一組（相對靜態的）散布於網際網路的伺服器，代管第三方的 Web 檔案，並可把檔案動態複製到需要之處（貼近需求量大的客戶端群）。既然副本伺服器已就位，決定內容放哪裡就比伺服器放置容易。

延伸案例：Rabinovich 等人的動態複製演算法

Rabinovich 等人（1999）描述了 Web 代管服務中檔案動態複製的演算法。它為網頁設計，因此假設更新相對於讀取罕見，以檔案為資料單位。演算法考量兩件事：為伺服器減載而複製，以及把特定檔案遷移或複製到「發出大量請求的客戶端」附近——以下聚焦後者：

• 每台伺服器統計每個檔案的存取次數與請求來源。假設對客戶端 C，每台伺服器都能判斷服務中哪台伺服器離 C 最近（可由路由資料庫得知）。若 C1 與 C2 的「最近伺服器」同為 P，則兩者對伺服器 Q 上檔案 F 的請求，在 Q 合併登記為單一計數 cntQ(P,F)。

• 刪除門檻 del(S,F)：檔案 F 在伺服器 S 的請求數低於此值時可從 S 移除（副本數因此減少，可能推高其他伺服器負載）。系統採取特別措施確保每個檔案至少留存一份拷貝。
• 複製門檻 rep(S,F)（一定高於刪除門檻）：請求數高於此值時，值得把 F 複製到另一台伺服器。請求數落在兩門檻之間時，檔案只允許遷移（至少維持副本數不變）。
• 伺服器 Q 重新評估檔案放置時：F 的總請求數低於 del(Q,F) 就刪除（除非是最後一份）；若某伺服器 P 的 cntQ(P,F) 超過 Q 上 F 總請求的一半，就請 P 接手這份拷貝（遷移）。遷移可能失敗（P 過載或磁碟不足），此時 Q 轉而嘗試複製到其他伺服器——但複製只在總請求數超過 rep(Q,F) 時進行：Q 從最遠的伺服器開始檢查，若某伺服器 R 的 cntQ(R,F) 超過 F 在 Q 總請求的一定比例，就嘗試把 F 複製到 R。

伺服器發起的複製日益流行，尤其在 Web 代管服務的脈絡中。只要能保證每個資料項至少由一台伺服器承載，甚至可以只用伺服器發起的複製、完全不設永久副本。不過永久副本仍常有用處：作為備援設施，或作為唯一允許被修改的副本以保障一致性——此時伺服器發起的副本用來把唯讀拷貝放到客戶端附近。

客戶端發起的副本#

**客戶端發起的副本（client-initiated replicas）**更常被稱為（客戶端）快取（cache）：客戶端用來暫存剛請求過的資料的本地儲存設施。原則上快取完全由客戶端管理，資料儲存不負責保持快取資料一致——不過在許多場合，客戶端可以倚賴資料儲存的協助，得知快取資料何時已過期。

• 快取的唯一目的是改善存取時間。當多數操作只是讀取時，讓客戶端把請求到的資料存在附近的快取（客戶端本機，或同一區域網路內的另一台機器），下次讀取直接從快取拿——只要資料在此期間沒被修改，這個方案就運作良好。
• 資料通常只在快取中保留一段有限時間：防止用到過期太久的資料，或單純為了騰出空間。能從本地快取取得請求資料時，稱為快取命中（cache hit）。
• 為提升命中率可以讓多個客戶端共享快取，前提假設是 C1 請求過的資料對附近的 C2 也可能有用。

共享快取是否划算，高度取決於資料儲存的類型。例如傳統檔案系統中資料檔案幾乎不被共享（Muntz 與 Honeyman，1992；Blaze，1993），共享快取因此無用武之地。同樣地，用 Web 快取共享資料也逐漸失勢——部分原因是網路與伺服器效能的提升，伺服器發起的複製方案正變得更有效。

快取的放置相對單純：通常放在客戶端本機，或同一區域網路內的共享機器。某些情況下，系統管理者會再加上額外層級——在多個部門或組織之間放共享快取，甚至為整個地區（省或國家）設置共享快取。另一種做法是把（快取）伺服器放在廣域網路的特定節點，讓客戶端找出最近的伺服器，並請它保存客戶端先前從別處抓取的資料拷貝（Noble 等人，1999）。

內容散布#

副本管理也包含把（更新後的）內容傳播到相關副本伺服器，其中有幾組取捨。

傳播什麼：狀態 vs. 操作#

實際要傳播的東西基本上有三種可能：

1. 只傳播更新通知——這是**作廢協定（invalidation protocols）**的做法：告知其他拷貝「資料已更新、你手上的已失效」（可指明失效的部分）。之後有人要操作已作廢的拷貝時，通常得先更新它（視要支援的一致性模型而定）。
   • 主要優點：幾乎不耗網路頻寬——只需傳「哪些資料失效」。
   • 適用於讀寫比（read-to-write ratio）低的場景：更新頻繁而讀取少時，兩次更新之間可能根本沒有讀取，傳播第一次更新的完整內容純屬浪費（馬上被第二次蓋掉），只送通知更有效率。
2. 在拷貝之間傳輸資料——適用於讀寫比高的場景：修改過的資料在下次更新前被讀到的機率高，傳輸才划算。也可以改為記錄變更日誌、只傳日誌省頻寬；傳輸還常被彙整（aggregate）——多筆修改打包成一則訊息，節省通訊開銷。
3. 傳播更新操作本身——不傳資料，而是告訴每個副本該執行哪個操作（只附上操作需要的參數值）。這種做法也稱為主動複製（active replication），假設每個副本由一個能「主動」執行操作的行程代表（Schneider，1990）。
   • 好處：只要操作參數不大，更新傳播的頻寬成本極低；且操作可以任意複雜，有利於進一步維持副本一致。
   • 代價：每個副本可能需要更多處理能力，操作複雜時尤甚。

推送 vs. 拉取#

另一個設計課題是更新由誰發動：

• 推送式（push-based）做法（也稱伺服器式協定，server-based protocols）：更新主動傳播給其他副本，對方沒開口也照送。常用於永久副本與伺服器發起的副本之間，也可用於推送到客戶端快取。適用於副本需要維持較高一致程度（副本需保持相同）的情況——永久副本、伺服器發起的副本與大型共享快取通常被許多以讀取為主的客戶端共享，讀取更新比高，每筆推送的更新大概率會被至少一個讀者用到；而且推送讓一致的資料隨要隨有。
• 拉取式（pull-based）做法（也稱客戶端式協定，client-based protocols）：由伺服器或客戶端向另一台伺服器索取其手上的更新。常用於客戶端快取，例如 Web 快取的常見策略：收到請求時先向原始伺服器查核快取項是否被改過，被改過就先取回新資料再回覆，否則直接回快取內容——即客戶端輪詢（poll）伺服器判斷是否需要更新。適用於讀取更新比低的情況（如只有單一客戶端的非共享快取）；主要缺點是快取未命中時回應時間變長。

以「單一非分散伺服器＋多個各有快取的客戶端」比較兩者：

推送式協定要求伺服器追蹤所有客戶端快取。有狀態伺服器不僅容錯性較差（見第 3 章），追蹤本身開銷也可觀——Web 伺服器可能得追蹤數萬個客戶端快取，每次頁面更新都要走遍持有該頁的快取清單逐一傳播；更糟的是，客戶端因空間不足清掉頁面時還得通知伺服器，造成更多通訊。

折衷：租約#

這些取捨催生了以**租約（lease）**為基礎的混合式更新傳播。租約是伺服器的一個承諾：在指定期間內主動推送更新給客戶端。租約到期後，客戶端就得改為輪詢伺服器、自行拉取修改過的資料，或者申請一份新租約。租約最早由葛雷（Cary Gray）與雀里頓（David Cheriton）（1989）提出，提供了在推送與拉取策略之間動態切換的便利機制。

Duvvuri 等人（2003）描述了一種可動態調整到期時間的彈性租約系統，區分三種租約（租約未到期前更新一律由伺服器推送）：

• 年齡式（age-based）租約：依資料項上次修改時間發放——很久沒被改的資料，預期還會有一陣子不被改（這個假設在 Web 資料上已被證明合理）。給這類資料長租約，可大幅減少更新訊息數量。
• 更新頻率式（renewal-frequency-based）租約：常來要求刷新快取的客戶端拿到長租約，偶爾才問一次的客戶端拿到短租約。效果是伺服器實質上只追蹤「資料在那裡很受歡迎」的客戶端，並給這些客戶端高度一致性。
• 狀態空間開銷式（state-space overhead）租約：伺服器發現自己逐漸過載時，調低新租約的到期時間。租約更快到期，需要追蹤的客戶端就更少——伺服器動態切換到更無狀態（stateless）的運作模式，為自己減載以便更有效率地處理請求。

單播 vs. 多播#

與推拉相關的還有該用**單播（unicasting）還是多播（multicasting）**傳遞更新：

• 單播：資料儲存中的伺服器要把更新送給 N 台伺服器時，發送 N 則獨立訊息，一台一則。
• 多播：由底層網路負責把一則訊息有效率地送達多個接收者。

多播常常更便宜——極端情況是所有副本位於同一個區域網路且硬體支援廣播，此時廣播或多播一則訊息的成本與單一點對點訊息無異，單播反而低效。多播與推送式傳播天作之合：伺服器決定推送更新時，用一個多播群組一次送出即可。反之，拉取式通常是單一客戶端或伺服器請求更新自己的拷貝，此時單播可能才是最有效率的選擇。