538
《雲數據管理：挑戰與機遇》2.1.5 基於廣播和多播的組通信
本節書摘來自華章出版社《雲數據管理》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看
基於廣播和多播的組通信
如果數據被複製到多個節點上進行存儲，數據更新操作需要發送給所有的副本。廣播或多播操作是一種簡單的通信原語。一般來說，廣播方式把同一條消息發送給係統中的所有站點，而多播隻發送給部分站點。不失一般性，我們用多播來表示發送信息到特定的節點集合。下麵將介紹已經提出的多種不同的原語，這些原語已經在分布式係統和數據中心等不同場景中得到了應用。
FIFO多播或發送者有序的多播：消息按照被發送的順序傳輸（單個發送者）。
因果序多播：如果發送m1和m2兩個消息，並且m1的發送事件在m2的發送事件之前發生，那麼在所有相同的目的地上，m1都必須先於m2傳輸。
全序（或原子）多播：所有消息都以相同的順序發送給接收者。
實現不同多播協議的關鍵在於如何設計一種方法從而保證順序一致性約束。假設底層網絡隻支持點對點通信，不支持任何多播原語。另外，需要把網絡中消息的接收者和應用層中消息的實際傳輸者進行區分。接收到一條消息之後，該消息被插入到隊列中，當序列條件滿足時，消息才能開始傳輸。下麵將對實現這些原語的協議進行描述。圖2-5展示了一個包含3個因果相關多播e1、e2和e3的示例。如果這些多播都是因果相關多播，那麼，部分消息的傳輸就需要推遲，直到因果序條件得到滿足以後才能繼續傳輸。例如，雖然進程r接收到e2的時間比e1的接收者時間早，但是因為e1發生在e2之前，所以，必須等到r對e1完成接收和傳輸之後才能對e2開始傳輸。同樣，e3必須等到e1和e2傳輸完成之後才能開始傳輸。再看另外一個例子，圖2-6也包含了3個多播e1、e2和e3。盡管e1和e2不是因果相關，並且是從不同的進程p和q發出的，如果它們是全序多播的話，那麼所有的站點都要按照相同的順序進行傳輸，而與它們的接收順序無關。例如，雖然進程r接收e2的時間比接收e1的時間早，而在進程s中該順序剛好相反，但是，所有的站點都必須按照相同的順序來傳輸這兩個多播，比如先傳輸e2，再傳輸e1。需要說明的是，即使發送操作是因果相關的，全序也不需要一定要滿足因果序。例如，e2和e3是因果相關的，並且e2發生在e3之前，但是所有的進程仍可能是先傳輸e3，再傳輸e2。
圖2-5 因果序
圖2-6 全序
FIFO多播可以用一種類TCP傳輸協議來簡單地實現，即消息發送者可以設置一個有序的消息標識符，任意一條消息在其之前的消息完成接收和傳輸之前都需要等待。如果有消息丟失了，接受者可以向發送者請求丟失的消息。
因果多播可以通過如下方式來實現：要求每一個廣播消息都攜帶所有因果前置消息。在傳輸之前，接受者必須通過傳輸任何丟失的因果前置消息來確保因果關係。但是，這種協議的開銷非常大。還有另外一種可供選擇的協議（ISIS [Birman, 1985]），該協議使用向量時鍾來延遲消息的傳輸，直到所有的因果前置消息都被傳輸完成。每一個進程負責維護一個長度為n的向量時鍾V，n是係統中節點的數量。V的元素被初始化為0。當節點i發送一個新的消息m時，對應節點i的元素值就加1。每一個消息都與發送者的本地向量組合在一起。當節點發送消息時，該節點需要利用如下方式對其向量進行更新：選擇本地向量和隨消息到達的向量之間的元素的較大值來更新。節點i利用向量VT發送消息m，如果向量VT中與發送者相對應的元素剛好比接收端本地向量中的發送者元素大1（即是下一條消息），並且，本地向量的所有元素都大於等於VT中的對應元素，那麼接收者就接收到了所有的因果前置消息。
全序多播可以通過集中式方法來實現，例如固定的協調者（使用在Amoeba [Kaashoek et al., 1989]中），或者移動令牌等[Défago et al., 2004]。另外，ISIS [Birman, 1985]也提出了分布式協議。在ISIS分布式協議中，所有進程通過三輪來對序號（或優先級）達成一致意見。發送者將具有唯一標識符的消息m發送給所有接收者。接受者會建議一個優先級（序號），並把建議的優先級反饋給發送者。發送者收集完所有的優先級建議，並確定一個最終的優先級（通過進程編號打破關係），然後針對消息的重新發送最終達成一致意見的優先級。最後，接收者再按照最終的優先級來傳輸消息m。最後更新：2017-05-19 13:32:11