複製（replication）是協調式系統可擴展性的關鍵，對生成式通訊的系統尤其如此。以下先看 JavaSpaces 等系統中已探索過的標準做法，再介紹一些較新的成果——依存取模式動態、自動地放置元組。

靜態做法#

支援生成式通訊的系統，其分散式實作經常需要特別處理。這裡聚焦於 JavaSpace 伺服器的分散式實作，亦即元組實例的集合可以分散、複製在多台機器上。元組式執行期系統的實作技術綜覽見 Rowstron (2001)。

一般考量#

高效的 JavaSpace 分散式實作必須解決兩個問題：

1. 如何模擬關聯式定址（associative addressing）而不做大規模搜尋。
2. 如何把元組實例分散到各機器、之後又能找到它們。

兩個問題的關鍵，都在於觀察到每個元組是有型別的資料結構：

• 依型別劃分子空間：把元組空間切成多個子空間（subspaces），每個子空間內的元組同型別。這簡化了程式設計，也開啟了最佳化空間——因為元組有型別，write、read、take 呼叫作用在哪個子空間可在編譯期決定，於是只需搜尋元組實例集合的一小部分。
• 子空間內建雜湊表：每個子空間可用（部分的）第 i 個元組欄位作為雜湊鍵組織成雜湊表。元組實例的每個欄位都是物件的 marshal 後參照，而 JavaSpaces 不規定 marshal 的方式，因此實作可以讓 marshal 後的前幾個位元組作為物件型別的識別碼。write、read、take 呼叫即可透過計算第 i 欄的雜湊值直接定位元組實例在表中的位置——知道子空間與表格位置後，搜尋完全免除。
• 當然，若 read 或 take 的第 i 欄是 NULL，就無法雜湊，通常得完整搜尋該子空間。但謹慎選擇雜湊欄位往往能避免搜尋。
• 把 bin 分散到不同機器：上述雜湊方案把子空間的元組分進多個 bin，將搜尋限制在單一 bin。把不同 bin 放到不同機器上，既能分散負載也能利用局部性；若雜湊函數是「型別識別碼 mod 機器數」，bin 的數量會隨系統規模線性擴展〔另見 Bjornson (1993)〕。

全複製：write 廣播、read 本地#

在電腦網路上，最佳選擇取決於通訊架構。若有可靠廣播可用，一個有力的候選方案是把所有子空間完整複製到所有機器：

• write 時，新元組實例被廣播、放進每台機器上對應的子空間。
• read 或 take 時，搜尋本地子空間即可。
• 但 take 成功完成需要把元組實例從整個 JavaSpace 移除，因此需要一個刪除協定把它從所有機器移除；為避免競態條件（race conditions）與死結，可使用兩階段提交協定（two-phase commit protocol）。

這個設計直觀，但當元組實例數量與網路規模成長時可能無法良好擴展。例如把這個方案實作在廣域網路上，成本高得令人卻步。

反向設計：write 本地、read 廣播#

相反的設計是 write 在本地做：元組實例只存在產生它的機器上。

• read 或 take 時，行程必須廣播模板元組；每個接收者檢查自己是否有相符者，有就回覆。
• 若元組實例不存在、或廣播沒有到達持有元組的機器，請求機器就無限期地重送廣播，並逐步拉長間隔，直到合適的元組實例出現、請求得以滿足。
• 若送回了兩個以上的元組實例，它們被當作本地 write 處理，實例實質上從原持有機器搬移到請求機器。事實上，執行期系統甚至可以自行搬移元組來平衡負載。

Carriero 與 Gelernter（1986）就是用這個方法在 LAN 上實作 Linda 元組空間。

部分複製：格狀方案#

兩種方法可以結合成**部分複製（partial replication）**系統。簡單的例子：讓所有機器在邏輯上排成矩形網格——

• 機器 A 上的行程要 write 時，把元組廣播（或以點對點訊息送）給**其所在列（row）**的所有機器。
• 機器 B 上的行程要 read 或 take 時，把模板元組廣播給**其所在行（column）**的所有機器。
• 由於幾何性質，永遠恰好有一台機器同時看到元組實例與模板元組，由它完成比對並把元組實例送給請求行程。

這個做法類似第 7 章討論過的法定人數（quorum-based）複製。

廣域實作的困境#

上述實作都有嚴重的可擴展性問題，根源在於插入或移除元組都需要多播。元組空間的廣域實作並不存在。目前最多是讓多個不同的元組空間共存於一個系統，每個元組空間本身實作在單一伺服器或區域網路上。PageSpaces（Ciancarini et al., 1998）與 WCL（Rowstron 與 Wray, 1998）即採此法。在 WCL 中，每台元組空間伺服器負責一整個元組空間——行程永遠被導向恰好一台伺服器；不過元組空間可以遷移到另一台伺服器以提升效能。

如何開發高效的元組空間廣域實作，至今仍是開放問題。

動態複製#

協調式系統的複製一般僅限於平行應用的靜態策略（如上所述）；商業應用中看到的也是相對簡單的方案——整個資料空間、或靜態預先劃定的資料子集，套用單一策略（GigaSpaces, 2005）。受 Globule 對 Web 文件細粒度複製的啟發，若能針對資料空間中不同種類的資料採取不同的複製方式，還能進一步提升效能。GSpace 就支援這種差異化。

GSpace 概覽#

GSpace 是建立在 JavaSpaces 之上的分散式協調式系統（Russello et al., 2004, 2006）。GSpace 中元組的分佈與複製有兩個目的：提升效能與提升可用性。這個做法的核心是關注點分離（separation of concerns）：為可用性而複製的元組，可能需要與為效能而複製的元組不同的策略。因此 GSpace 的架構被設計成支援多種複製策略，且不同元組可以遵循不同策略。

其運作原理相當簡單：

• 每個應用程式得到一個提供 read、write、take 的介面，與 JavaSpaces 類似。
• 每次呼叫都由本地的呼叫處理器（invocation handler）接手，查出該呼叫應遵循的策略。策略依呼叫所帶元組／模板的型別與內容選定；每個策略以一個模板識別——與其他 Java 式共享資料空間用模板選元組的方式相同。
• 選擇的結果是一個**分佈管理器（distribution manager）**的參照：它實作同樣的介面，但依特定複製策略執行。例如在主從（master/slave）策略下，read 可以直接從本地資料空間讀取；write 則可能要求分佈管理器把更新轉發給主節點、等到確認後才在本地執行。
• 每個 GSpace 核心（kernel）都有一個本地資料空間，稱為 slice，以完整的非分散版 JavaSpaces 實作。

在這個架構中，策略描述子（policy descriptors）可以在執行期加入，分佈管理器同樣可以更換。這使元組的分佈與複製可以細粒度調校；Russello et al. (2004) 顯示，這種微調帶來的效能，遠高於對資料空間內所有元組套用任何單一固定全域策略。

適應性複製#

不過，GSpace 這類系統最重要的面向是複製管理的自動化：與其讓應用開發者自己想出最佳的策略組合，不如讓系統監控存取模式與行為，並視需要採用相應策略。

• GSpace 沿用 Globule 的做法：持續量測消耗的網路頻寬、延遲與記憶體用量，並依據其中被視為最重要的指標，把元組放到不同節點、選擇最合適的副本一致性維護方式。
• 「哪個策略對某個元組最好」的評估由一個中央協調者進行，它單純收集構成 GSpace 系統各節點的追蹤資料（traces）。

有趣的一點是：三不五時可能需要從一種複製策略切換到另一種。轉換方式有多種；由於 GSpace 力求機制與策略分離，它也能處理不同的轉換策略（transition policies）：

• 預設做法：暫時凍結該型別元組的所有操作，移除所有副本，再把元組依新選定的複製策略重新插入共享資料空間。
• 視新策略而定，也可能有更便宜的轉換方式。例如從「不複製」切換到「主從複製」時，可以在元組首次被存取時才**惰性複製（lazily copy）**到從節點。