協調式系統的一個重要特徵是：通訊是透過描述所要交換的資料項之特徵來進行的。因此**命名（naming）**扮演關鍵角色——在許多情況下，資料項並不由傳送者與接收者明確指名。

整體做法#

先假設資料項以一組屬性（attributes）描述：

  • 資料項被公開給其他行程讀取時，稱為被發佈（published）。
  • 訂閱者需向中介軟體遞交一份訂閱（subscription），內含它感興趣的資料項描述。描述通常由若干（屬性, 值）對組成，也可能搭配（屬性, 範圍）對——後者要求該屬性的值落在指定範圍內。有些系統允許以屬性上的各種述詞（predicates）來描述，性質上很像關聯式資料庫中的 SQL 式查詢。

於是系統面對的核心情境是：訂閱必須與資料項進行比對（matching）。比對成功後有兩種可能的處理方式：

  1. 直接轉發資料：中介軟體把發佈的資料轉發給目前擁有相符訂閱的訂閱者。此時中介軟體通常不提供資料儲存——儲存由獨立服務處理，或由訂閱者自行負責。這是一個參照解耦、但時間耦合的系統。
  2. 傳送通知（notification）：訂閱者收到通知後再執行讀取操作以取回發佈的資料項。此時中介軟體必須儲存資料項，並提供額外的資料管理操作；也可以為資料項附加租約（lease），租約到期時資料項自動刪除。

圖 13-2：發佈者與訂閱者之間交換資料項的原理。

事件與事件組合#

前述模型假設有一組固定的 n 個屬性用來描述資料項，即每個發佈的資料項都帶有一個完整的（屬性, 值）對向量。但在許多協調式系統中這個假設不成立：實際發佈的是事件（events）——可視為只帶單一屬性的資料項。

事件使訂閱處理複雜化。例如訂閱「當房間 R4.20 無人且門未上鎖時通知我」：支援這種訂閱的分散式系統，通常由獨立的感測器實作（偵測房間有無人的動作感測器、登記門鎖狀態的感測器）。依照前述做法，我們得把這些原始事件（primitive events）組合成可發佈的資料項，行程才能訂閱。事件組合（event composition）是一件困難的工作，尤其當原始事件來自散佈於分散式系統各處的來源時。

在這類協調式系統中，關鍵議題是訂閱與資料項比對的高效、可擴展實作，以及相關資料項的建構。從外部看，協調式方法因為行程的強解耦，對建構超大規模分散式系統潛力十足；但要在不喪失這種獨立性的前提下設計出可擴展的實作，並非易事。

傳統架構#

比對資料項與訂閱最簡單的解法是集中式的主從（client-server）架構。這是目前許多發佈／訂閱系統採用的典型方案，包括 IBM 的 WebSphere 與 Sun 的 JMS 的常見實作。同樣地，較複雜的生成式通訊模型實作，如 Jini 與 JavaSpaces（Freeman et al., 1999），也大多以中央伺服器為基礎。

範例：Jini 與 JavaSpaces#

Jini 是由多種相關元素混合而成的分散式系統，與 Java 語言關係密切（雖然其原理也能用其他語言實作）。系統的重要組成是生成式通訊的協調模型：Jini 透過名為 JavaSpaces 的協調系統（源自 Linda）提供行程的時間與參照解耦。

  • 一個 JavaSpace 是共享資料空間，存放的元組代表一組有型別的 Java 物件參照。單一 Jini 系統中可以同時存在多個 JavaSpaces。
  • 元組以序列化（serialized）形式儲存：行程要存入元組時，元組會先被 marshal，其所有欄位也一併被 marshal。因此若元組中有兩個欄位參照同一個物件，存進 JavaSpace 的元組會保有該物件的兩份 marshal 副本。
  • 元組以 write 操作放入 JavaSpace：先 marshal 再儲存。每次對同一元組呼叫 write，就會再存入一份 marshal 副本——每份副本稱為一個元組實例（tuple instance）。

讀取的方式是 Jini 生成式通訊有趣之處。讀取時，行程提供另一個元組作為模板（template）：

  • 模板元組同樣是有型別的物件參照集合；只有與模板同型別的元組實例才可能被讀取。
  • 模板的欄位要嘛包含實際物件的參照，要嘛是 NULL。
  • 比對時，模板照常被 marshal（包括 NULL 欄位），再與同型別的元組實例逐欄比較。兩個欄位相符的條件是：兩者持有同一參照的副本，或模板欄位為 NULL。所有欄位成對相符，該元組實例即與模板相符。
  • 找到相符的元組實例後，read 操作將其 unmarshal 並回傳給讀取行程；take 操作則額外把該實例從 JavaSpace 移除。兩種操作都會阻塞呼叫者直到找到相符元組，可以指定最長阻塞時間，也有找不到就立即返回的變體。

使用 JavaSpaces 的行程不需要同時存在。事實上，若 JavaSpace 以持久儲存實作，整個 Jini 系統可以完全關機後再重啟而不遺失任何元組。

延伸討論：中央伺服器與複雜比對、同步的關係

雖然 Jini 本身不支援，但有中央伺服器時，訂閱其實可以做得相當精緻。例如目前兩個非 NULL 欄位要完全相同才算相符；但既然每個欄位代表一個物件，也可以改用物件特定的比較運算子來評估相符與否〔另見 Picco et al. (2005)〕。若應用程式能覆寫這種運算子，幾乎任意的比較語意都能實作。

要注意的是，這類比較可能需要對目前儲存的資料項做大規模搜尋，而這種搜尋很難以分散式方式有效率地實作。正因如此，支援複雜比對規則的系統通常只見於集中式實作。

集中式實作的另一個優點是同步原語（synchronization primitives）較容易實作：行程可以阻塞等到合適的資料項被發佈，再執行破壞性讀取（destructive read）移除相符元組——這提供了行程間互不相識的同步機制。去中心化系統中的同步本質上是困難的（見第 6 章）。

範例：TIB/Rendezvous#

中央伺服器之外的另一種解法，是利用**多播（multicasting）**把發佈的資料項立即散發給相應的訂閱者。TIB/Rendezvous 採用這個原理：

  • 資料項是一則訊息，帶有描述其內容的複合關鍵字（compound keyword），例如 news.comp.os.books；訂閱者提供（部分）關鍵字來指定想收的訊息，例如 news.comp.*.books。這些關鍵字稱為訊息的主題（subject）。
  • 實作基礎是區域網路常見的廣播，但在可能時也使用更有效率的通訊方式——例如已確知訂閱者位置時，通常改用點對點訊息。
  • 網路上的每台主機執行一個 rendezvous daemon，負責依主題傳送與遞送訊息。訊息發佈時，會被多播到網路上每台執行 rendezvous daemon 的主機。多播通常利用底層網路設施實作，如 IP 多播或硬體廣播。
  • 行程向本地 daemon 遞交訂閱；daemon 建立（行程, 主題）表格。當主題 S 的訊息到達時，daemon 查表找出本地訂閱者並逐一轉發；若 S 沒有訂閱者，訊息立即丟棄。

圖 13-4：TIB/Rendezvous 中實作的發佈／訂閱系統原理。

採用多播時，訂閱其實沒有理由只停留在字串比較——因為訊息反正會轉發到每個節點，發佈資料與訂閱之間可能很複雜的比對可以完全在本地完成，不需額外網路通訊。不過如後文所述，一旦需要跨廣域網路比對，就必須使用簡單的比較規則。

點對點架構#

多數協調式系統採用的傳統架構有可擴展性問題（儘管商業廠商宣稱不然）：

  • 用中央伺服器比對訂閱與發佈資料，規模無法超過幾百個客戶端。
  • 使用多播則需要特別措施才能超出區域網路的範圍。
  • 而且若要保證可擴展性，可能還得對訂閱與資料項的描述方式加上更多限制。

許多研究致力於用點對點（peer-to-peer）技術實作協調式系統。對於使用關鍵字的情況，實作相對直接：關鍵字可以雜湊成發佈資料的唯一識別碼；（屬性, 值）對也可以這樣映射到識別碼。此時比對簡化為單純的識別碼查找，可在 DHT 式系統中高效實作。這種做法對較傳統的發佈／訂閱系統有效（Tam 與 Jacobsen, 2003），對生成式通訊也適用（Busi et al., 2004）。

當比對方案更複雜時，情況就變得棘手。其中以需要支援**範圍（range）**的情況最為困難，現有提案非常少。以下介紹其中一個，由本書作者之一與其同事提出（Voulgaris et al., 2006）。

範例：基於 Gossip 的發佈／訂閱系統#

考慮一個發佈／訂閱系統，其中資料項以 N 個屬性描述，屬性值皆可直接映射為浮點數（如 float、整數、列舉、布林值、字串）。一個訂閱 s 是（屬性, 值或範圍）對的元組，例如指定 a1 必須等於 3.0、a4 必須落在區間 [0.0, 0.5)，其餘屬性任意。為簡化說明，假設每個節點 i 只登記一個訂閱 si。

  • 每個訂閱 si 實際上指定了 N 維浮點數空間中的一個子集 Si，這種子集也稱為超空間（hyperspace）。對整個系統而言，只有描述落在聯集 S = ∪Si 中的發佈資料才值得關心。
  • 整體構想：把 S 自動劃分為 M 個互斥的超空間 S1, …, SM，使每一塊都完整落在某些訂閱超空間 Si 之內，且合起來覆蓋所有訂閱。系統並保持 M 最小（不存在塊數更少的劃分）。
  • 對每個超空間 Sm，登記恰好那些滿足 Sm ⊂ Si 的節點 i。如此一來，資料項發佈時，系統只需找出它所屬的 Sm，即可將其轉發給相關聯的節點。

為達成這個目標，節點以**流行病協定（epidemic protocol）**定期交換訂閱：

  • 若節點 i 與 j 發現彼此的訂閱相交（Sij = Si ∩ Sj ≠ ∅），就記錄這件事並保存彼此的參照。
  • 若再發現第三個節點 k 使 Sijk = Sij ∩ Sk ≠ ∅，三者會互相連接，讓落在 Sijk 的資料項 d 能有效散播。若 Sij − Sijk ≠ ∅，節點 i 與 j 仍維持相互參照，但嚴格關聯到 Sij − Sijk。

本質上，我們要把節點分群成 M 組：節點 i 與 j 屬於同一組，若且唯若其訂閱 Si 與 Sj 相交；同組節點再組織成一個覆蓋網路（overlay network），以便有效散播該組超空間內的資料項。以單一屬性為例：七個節點各有一段感興趣的值域，節點依值域重疊情況被分成若干互斥區間的群組——例如節點 3、4、7、10 一起代表區間 [16.5, 21.0]，值落在此範圍的資料項只需散播給這四個節點。

圖 13-5：在點對點系統中為支援範圍查詢而將節點分群。

延伸細節：群組的建構與環狀散播

群組的建構方式：節點先組織成 gossip 式非結構化網路。每個節點維護一份鄰居參照清單（部分視圖，partial view），並定期與某個鄰居交換（如第 2 章所述），藉此認識系統中隨機的其他節點。每個節點持續記錄所發現興趣重疊（訂閱相交）的節點。

在某個時刻，節點 i 通常已握有多個興趣重疊節點的參照。與節點 j 交換資訊時，節點 i 將這些節點依識別碼排序，選出識別碼最低、且訂閱與 j 相交的節點 i1；接著選 i2 > i1，其訂閱同樣與 j 相交、但必須涵蓋 i1 尚未覆蓋的元素。重複此程序直到檢查完所有與 i 興趣重疊的節點，得到有序清單 i1 < i2 < … < in。節點 ik 之所以入列，是因為它覆蓋了一塊 i 與 j 共同感興趣、且未被識別碼更低的節點共同覆蓋的區域 R——實際上，ik 就是 j 對落在這塊唯一區域 R 的資料項應轉發的第一個節點。此程序可以擴展，讓節點 i 建構出一個雙向環（bidirectional ring）。

資料項 d 發佈時，會盡快散播給所有感興趣的節點。憑藉每個節點手上的資訊，找到一個對 d 感興趣的節點 i 很簡單；之後 i 只需沿著 d 所落範圍對應的訂閱者環轉發 d 即可。為加速散播，每個環也維護捷徑（short-cuts）。細節見 Voulgaris et al. (2006)。

延伸討論：其他點對點提案
  • Gupta et al. (2004) 描述了一個與此 gossip 方案精神相似（同樣嘗試對屬性值空間找出劃分）、但使用 DHT 式系統的做法。
  • Bharambe (2004) 的提案中，每個屬性 ai 由一個獨立行程 Pi 負責，Pi 再把該屬性的值域切分給多個行程。資料項 d 發佈時會轉發給每個 Pi，並儲存在負責 d 的 ai 值的那個行程。

這些做法都說明了把非平凡的發佈／訂閱系統映射到點對點網路有多複雜。**這種複雜性的本質在於：屬性式命名系統中的搜尋，先天就難以用去中心化的方式建立。**討論複製時我們還會再遇到這些困難。

行動性與協調#

文獻中相當受關注的一個主題是：如何結合發佈／訂閱方案與節點行動性（node mobility）。許多情況下假設存在固定的基礎設施，行動節點透過存取點（access points）接入。在這些假設下，問題變成：如何確保訂閱者在切換存取點時，已發佈的訊息不會被重複遞送。

  • 一個實用解法：讓訂閱者自行記錄已收到的訊息，直接丟棄重複者。
  • 另一類較複雜的解法：由路由器記錄哪些訊息已送給哪些訂閱者（見 Caporuscio et al., 2003）。

範例：Lime#

在生成式通訊方面，已有多種提案讓（部分）節點為行動節點的情況下運作共享資料空間。典型例子是 Lime（Murphy et al., 2001），它與前述 JavaSpace 模型十分相似。

  • 在 Lime 中，每個行程有自己的資料空間；當行程彼此鄰近而處於「連接（connected）」狀態時，它們的資料空間就合併共享。
  • 理論上「連接」可以指聯合底層網路中存在一條讓兩行程交換資料的路徑；實務上通常指兩行程暫時位於同一實體主機，或兩者的主機能透過（單跳）無線連結通訊。形式上，行程必須是同一群組的成員並使用同一群組通訊協定。
  • 連接行程的本地資料空間形成一個暫態共享資料空間（transiently shared dataspace）：行程 P 執行 write 時，元組存入 P 的本地資料空間；原則上它會留在那裡，直到出現相符的 take 操作——可能來自此刻與 P 同組的另一個行程。因此「實際上是完全分散的共享資料空間」這件事對參與行程是透明的。
  • Lime 也允許打破這種透明性：可以明確指定元組給誰；read 與 take 也可加參數指定期望元組來自哪個行程。

圖 13-6：Lime 中本地資料空間的暫態共享。

為了更精確地控制元組的分佈，資料空間可以執行所謂的反應（reactions）：

  • 反應指定「當本地資料空間中發現符合給定模板的元組時要執行的動作」。
  • 每次資料空間變動時，隨機選出一個可執行的反應執行，往往導致資料空間進一步變動。
  • 反應的作用範圍是當前的共享資料空間，但有若干限制以確保能有效執行。例如弱反應（weak reactions）只保證相關動作最終會被執行（前提是相符資料仍可存取）。

反應的想法在 TOTA 中被進一步推展：每個元組附帶一段程式碼，明確描述該元組應如何在資料空間之間移動，甚至包含轉換（Mamei 與 Zambonelli, 2004）。

Backward 協調模型簡介 行程 Forward