## 2-4 The Potential Dangers of Causal Consistency ### Introduction :::danger 因果一致性模型的好 ::: * 因果一致性(Causal Consistency) 模型被視為有價值的的一致性模型 * 優勢： * ==容錯且低延遲==：有多個資料中心，可以本地的回覆而不是從其他會有延遲的遠端資料中心，也使他在==分區和故障時保持`A`== * ==好的用戶體驗==：提供好用的語意，不允許與人類行為矛盾的場景。 * ==隱私==：因果一致性保證只有在發生後才能觀察到效果，因為參與者看不到數據(除非其依賴項能被看到) #### Lurking Dangers, Difficult Trade-offs :::danger 這模型需要trade-off的地方 ::: * trade-off取決於兩個因素 * 資料中心的數量 * 增加資料中心的數量不增加系統的throughput，因為因果依賴沒辦法給被輕鬆的分割，以及必須被送到每一個資料中心(分區的話則throughput為零) * 增加throughput且增加資料中心會server總容量倍增 * 每個資料中心檢查依賴關係和應用寫入的新速率 * 每個數據中心必須要緩存每一次寫入操作，直到觀察到所有該寫入操作的依賴項 * ==總結來說，不是導致尖峰的throughpu限制，不然就是不能被接受的可見高延遲== :::info ps. 依賴是指一個操作對另一個操作的依賴性，即有前後關係 ::: #### Better Living Through Semantic Context :::danger 引入一些現代應用場景來緩解這些挑戰，提高throughput ::: ### A PRIMER ON CAUSAL CONSISTENCY #### Definitions :::danger 強調前後關係以及維護狀態一致之重要性 ::: * happen before relation(->)，即遵照先後順序關係(v1 -> v2 -> v3) * happen before是根據潛在因果性定義的，反映了三種關係： 1. 每個代理的程序順序(單個代理執行操作a和b，則a->b) 2. 讀寫關係(讀b返回寫a，則為a->b) 3. 傳遞性(a->b 且 b->c，則a->c) * history: write之間的前後關係，其關係圖行程一個操作上的順序 * convergent(收斂性) causal consistency: 停止更新後會讀到相同的值。收斂性是一個重要的標準，如果沒有收斂性，不透過代理來傳寫入操作可以滿足因果一致性，但可能語義是不理想的 #### Implementing Causal Consistency :::danger 遵循這模式來保證邏輯順序和正確處理依賴 ::: * 每個代理維護一組寫操作可以使本地安全的修改和讀取 * ==收到遠端代理的寫操作，代理會檢查其數據，來確保其因果依賴性滿足目前的本地storage，若滿足依賴性，代理將採用該寫入操作，不滿足(有依賴項缺失)，則等待到缺失的依賴項都被採用後再執行該寫入操作== * 可見性：只有該寫入被採用後，讀的操作才可見 * 實現等待：代理先更新其本地storage，然後用廣播方式將新的寫入操作發送給所有其他代理，這些代理將其緩存，直到其所有因果依賴相都被滿足後才採用該寫入操作 * 每個數據中心都可以作為一個因果代理，由多個server組成，因為server集群的本地網路延遲通常很低，故可以提供強的一致性，可以將數據內部中心的所有操作都視為原子性的(單一不可分割操作) ### POTENTIAL DANGERS :::danger 因果一致性要權衡多個數據中心的throughput和可見性延遲的trade-off ::: #### Throughput and Visibility Latency * 數據中心沒辦法採用新的寫入操作則必須等待直到其一來都到達，此緩存時間決定其可見性延遲 * 數據量超過數據中心的throughput限制，新操作的生成速度快於其採用的速讀則會使可見性延遲無限的增加 * 為了確保收斂，所有最終版本最終必須被廣播 #### (Not) Scaling Throughput and Datacenters * 收斂的因果一致性要求全面複製，這限制了全球寫入和throughput。 * 例子 * 有兩個數據中心，每個採用操作能力為A，為了防止寫入生成速率大於遠端被採用的速率，必須將寫入的總throughput限制在A。 * 數據中心平均分配throughput，每個數據中心可以以A/2速率生成寫入，對於N個數據中新則是A/N * 維持每個數據中的寫入throughput需要數據中心的增長的採用能力的二次方倍數 * 例如有2個數據中心以每秒生成1K新寫入，則每個數據中心必須具有2K的新寫入/s的採用能力。若想增加第三個數據中心，每個數據中心則需要3K/s的寫入能力 * N個數據中心增加到M個則需要O(M^2/N^2)容量 * 潛在危險：可持續寫入throughput受限於最慢的數據中心，所以增加數據中心並不增加throughput，擴展數據中心與寫入需要二次方的server容量，違反限制將導致極高的可見性延遲 * 結論： * 分區或數據中心故障：會使某個數據中心的採用能力變成0，導致無法處理新的寫入請求而累積大量寫入操作，長時間的故障課能通過其他數去中心同步數據恢復，這個過程可能成本很高 * 超出數據中心容量：當寫入超過數據中心超過最大容量，該數據中心會造成系統的瓶頸，需要好好規劃並預留足夠的處理能力來保證系統可持性擴展 #### Potential Histories and Cluster Capacity * 寫入throughput取決於最慢數據中心的採用寫入速度，這又依賴於因果關係圖(決定依賴性檢查數量)，其深度和連通性又決定執行檢查的併發程度。 * 以Twitter會話為例，一開始顯示20條貼文，往下滾會自動以每分鐘600條貼文的速率獲取更多貼文。如果用戶僅查看20條其他貼文後發布1條貼文，新貼文將至少有20個淺在因果歷史。因果歷史大小上限等於曾發布所有的貼文數量(當前每天為3.4億條貼文)，這需要大量依賴性檢查。 * ==潛在危險：因我關係圖有很大的扇出以及深度，限制本地採用能力也限制全球throughput== * 如果所有數據中心都採用一個版本(穩定版本)，數據中心就不用再新寫的依賴性數據中附加他或遠距檢查他。如果知道某個依賴已經被採用，就通知遠程數據中心需要檢查給定寫入的給定依賴就沒有用處，這大大減少了附加到每個項目上的依賴性。 * 但這樣會有兩個關鍵挑戰: * 要全球協調，在分區下，檢測會停滯 * 沒分區下，也會有前述的throughput違規的情況 ### AN EXPLICIT SOLUTION :::danger 提出明確因果關係(explicit causality)，即只專注重要的依賴就好，來提升性能 ::: * ==其實可以只專注在實際重要的依賴，避免處理大量不重要的依賴== * 儘管這樣無法避免要全面複製問題，但可以有效的提高throughput以及減少可見性延遲 #### Explicit Causality in the Wild :::danger 現代實際應用上對於明確因果關係的分析，觀察出實際的明確因果關係很小 ::: * 平均對話(評論、貼文、分享)深度是10.7條 * 69%的對話深度為2(即貼文+一條回覆) * 最大的長度是243條貼文 * 在Facebook的"粉絲"的因果鍊上， * 最大深度為82 * 75%鍊長度在3以下 * 98%在18以下 * 其餘部落格，互動網站，電子郵件等也都展現類似趨勢 * ==表示現代應用的因果觀性關係是小的，影響有限== * 透過這觀察，只追蹤重要的依賴關係，在現代應用上能有效的簡化因果關係圖 #### Benifits: Relieving the Pressure :::danger 明確因果關係的優點 ::: * ==檢查更快==: 依賴少則檢查更快，只需檢查少量依賴，降低可見性延遲 * ==減少數據==: 依賴少則寫入所需的數據存儲和通訊開銷也會減少 * ==增加併發性==: 每次更新或操作的因果關係圖相對小且簡單，不如潛在因果性模型可能會產生高度複雜的因果關係圖。==明確因果性只考慮特定更新，導致形成幾個較小互不相交的因果關係圖。因此寫入之間有更多的獨立性，可以平行處理== #### Application Programming Model :::danger 明確因果關係對於應用程序設計可以簡化依賴，提升性能，使應用程序更加靈活控制數據一致性及處理數據更新 ::: #### Limitation :::danger 用戶可規避因果追蹤機制 ::: * 例如: 用戶狀態更新是通過文字而非系統引用來提及，e.g. Jeremy說: "你應該看看我剛上傳的照片" * 系統不會意識到這種依賴關係，其他用戶可能找不到Jeremy的照片 ### DISCUSSION :::danger 通訊，存儲，應用level的因果性，以及潛在因果性普及的原因 ::: * 通訊和存儲API: * 明確因果性透過應用層的自主事件來記錄簡化的因果依賴，優化通訊和存儲效率 * 潛在因果性的普及原因 * 討論到register或通訊channels，在沒有更高層語義的情況下，很難去提倡明確因果性 * 用戶也不知道目前調適的錯誤的根本原因 * 現有架構的挑戰 * 本文探討的因果一致性沒討論到兩個方面 * 多數據中心的巔峰throughput有限制 * 現實世界因果圖的要求 ### CONCLUSION * ==因果一致性在可見性延遲和throughput要trade-off==，更多的數據中心加入，最大數據更新速率不會增加，所需硬體成本也要以二次方速度提升 * 為了緩解這問題，可透過==明確因果性==降低存儲和處理成本，只追蹤重要的依賴 * 以現代人類面向來看，==明確因果性依賴圖為潛在因果性圖的一小部分，這允許了更快且平行的依賴性檢查==