---
# System prepended metadata

title: 2-4 The Potential Dangers of Causal Consistency
tags: [Consistency Protocol]

---

## 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==，更多的數據中心加入，最大數據更新速率不會增加，所需硬體成本也要以二次方速度提升
* 為了緩解這問題，可透過==明確因果性==降低存儲和處理成本，只追蹤重要的依賴
* 以現代人類面向來看，==明確因果性依賴圖為潛在因果性圖的一小部分，這允許了更快且平行的依賴性檢查==