# 2-4 The Potential Dangers of Causal Consistency and an Explicit Solution

## Introduction
- 此篇論文說明 Casual Consistency 的系統為何在擴展性上會有問題，以及對於現今龐大的系統，要如何應對複雜的因果關係，而持續保持因果一致性

## Casual Consistency
- 保證結果一定在原因發生後才發生，以下情境，操作 a b c 是有因果關係存在
1. Lewis 在留言 "Jenny在醫院處於無意識狀態" -> 操作a
2. Jenny 醒來，Lewis 更新留言 "Jenny 終於醒來了" -> 操作b
3. Mary 看到 Jenny 醒來的消息，留言 "真是太好了<b>(What terrific news!)</b>" -> 操作c

- 假如不存在因果一致性，其他使用者有可能只看到 操作a 和 操作c，認為 Mary 在咒罵 Jenny

### 定義
- 每個 agent (我認為是意指 process) 讀到的資料版本有一定的順序，而這些資料版本遵守 `happens-before` 這個特性，用 $\rightarrow$ 表示
- 假如一個資料有 v1 $\rightarrow$ v2 $\rightarrow$ v3 的版本變化，則一個 agent 做 兩次的 read 有可能先獲得 v1，再來是v3。v3 絕對不可能比 v1, v2 早讀出來。

- `happens-before` 是根據潛在因果關係 (`potential causality`) 決定出來的，而潛在因果關係反映了 3 種特性
- 操作順序的一致性，先操作 a 再 b，a $\rightarrow$ b
- 讀取出 b 的這個結果，是因為原先寫入 a，a $\rightarrow$ b，此種 write 也叫做 `casual history`
- 遞移性，先 a 再 b，a $\rightarrow$ b；然後再先 b 再 c，b $\rightarrow$ c，a $\rightarrow$ c

- 收斂的因果一致性 (convergent causal consistency)
- 當更新停止時，所有的 agent 在`最終`都會讀取到相同的值

### 步驟
- 每個 agent 在其本地紀錄一系列的寫行為，當遠端有一個寫行為要進來時，agent 需檢查與這個寫行為有相關的所有寫行為必須完成，agent 才能夠允許這個寫行為寫入本地。否則就持續等待直到其依賴的所有寫行為完成。
- 今天有一系列行為是 w1 -> w2 -> w3，某一 agent 收到了 w1, w3
- w1 可成功寫入，但 w3 須等到 w2 完成，w3 才可以進行

### 為什麼要等待
- 一個例子: Mary "喜歡" Greenpeace。
- "喜歡"有這樣的一個關係: `使用者ID` <-> `公司ID`。而 `使用者ID` 對於使用者表也有關聯， `公司ID` 對於公司表也有關聯
- 因此在更新這樣的一個狀態會有 3 個寫動作
- 查找使用者對應 ID，並把 ID 寫入狀態裡的 `使用者ID` : w1
- 查找公司對應 ID，並把 ID 寫入狀態裡的 `公司ID` : w2
- 最終把這關係寫入 : w3
- 有這樣的關聯: w1 -> w3 ; w2 -> w3
- 假如在 "Greenpeace" 找到其 `公司ID` 之前，就做了狀態寫入，就會變只傳 `{Mary的使用者ID}` <-> `{空的}`
- 我們必須等待 "Greenpeace" 找到其 ID，才能做狀態更新，但這只是暫時性的，因為我們相信公司ID最終一定會回傳回來

### 實作等待
- 當在做寫入時，會先有一個 agent 寫入，並通知其他 agents
- 此時其他 agent 會先 buffer 這個寫入，因為他們每個要確定這個 write 的之前所有關聯 write 都已經正確寫入，他才能把這個新的 write 寫入
- 於現實生活的資料中心，每個資料中心就是一個 agent。
- 雖然資料中心裡頭有很多伺服器，但因為是本地網路，這些伺服器的延遲很低，可以採用 strong consistency 來管理。

## 拓展 Casual Consistency 的潛在危險
### 吞吐量以及可見性延遲 (Throughput and Visibility Latency)
- 可見性延遲
- 某個 write 因為其 dependency 還沒寫入，而持續卡住，也代表這個寫入還無法被使用者看到，這段時間就是可見性延遲
- - 與網路延遲以及 dependency checking 的速度(apply-capacity)有關
- apply-capacity
- 一個 data center 做 dependency checking 的速度
- 吞吐量
- 整體系統單位時間內產生寫入行為的數量
- 全局吞吐量就被受限於 apply-capacity 最小的那個 data center，因為因果一致性須確保所有的 data center 在最終都會有一樣的值 (convergent)
- 在 apply-capacity 固定的情況下
- 吞吐量高，可見性延遲就會長；反之相反

### 在因果一致性的情況下拓展 data centers
- data center 的處理速度會被受限於最慢的一個 (論文的舉例讓我很困惑 點點點)
- 假設 data center 的 apply capacity 是 A，為了避免 data center 因為過多的寫入行為，而導致需排隊一直等待 dependency checking，因此不能讓全域吞吐量超過 A
- 今次有兩個 apply capacity 都是 A 的 data center，我們可以平分整個系統產生的吞吐量，因此每個 data center 處理的速度是 A/2
- N個 data center 就是 A/N，但整個系統的吞吐量還是只能處理 A
- 而且假如有 data center 處理速度較慢，大家都必須配合他維持相同的速度，造成全域吞吐量降低
- 一個 data center 的 apply-capacity 會與 data center 數量成正比
- 假如每個 data center 產生的吞吐量為 1K
- 只有 1 個 data center，全域吞吐量為 1K，data center apply-capacity 為 1K
- 有 2 個 data center，全域吞吐量為 2K，每個 data center 的 apply-capacity 也必須升級為 2K
- 有 3 個 data center，每個 data center 的 apply capacity 升級為 3K
- 原有的 2 個 data center，從 2K 升級成 3K => (3-2)/2 = 50%
- 新的 data center 因為本來沒有，需額外增加，而一加進來的 apply capacity 須是 3K => 3/(2+2) = 75%
- 全域吞吐量從 2K 變 3K => (3-2)/3 = 33%
- 需要升級 data center 的效能 50+75=125%，整個系統的處理量卻只增加 33%
:::warning
在因果一致性下，處理速度會受限於最慢的實體。並且越多的實體，每個實體的效能也要增加
:::

### 過度複雜的關係依賴圖
- 在龐大的因果一致性系統，潛在的因果關係影響的深度很遠，導致 dependency check 會變得很久
- 假如一個使用在滑過 10 個貼文後留言，這 10 個貼文跟這個留言就有潛在的因果關係
- 每個貼文背後可能又是因為其他貼文，因果關係無窮無盡
:::warning
檢查 potentail casuality 導致 apply-capacity 降低，進而影響全域吞吐量
:::

- 也許加入一個 "stable version" 來確定其背後的 dependency 都有寫入了，就可以免除 dependency check 的過程，但是
1. 只要有分區，stable version 就會不一樣，只能等待分區問題解決
2. datacenters may slow in applying new versions, in turn decreasing the rate of stabilization. (?)

## Explict Casaulity
- 比起追蹤所有的潛在因果關係，何不追蹤最有關係的那個(Explict Casaulity)即可
- A 喜歡 B 的貼文，雖然 B 的貼文背後可能又有很多因果關係，但 A 最主要是只跟 B 的貼文有強烈關係
- 改成只追蹤 Explict Casaulity
- 關係依賴圖將變得簡單且淺層，而且可能會產生多個不交集關係圖，進而可以平行地做 dependency check 以及 write
- 大幅降低 dependency check 的次數，進而改善 apply capacity 以及 total global throughput
- 此種關係通常從應用層即可知道
- 應用程式要寫入 "A 喜歡 B 的貼文" 的狀態，就有: "B 貼文" $\rightarrow$ "A 喜歡 B 的貼文" 的關係
- 我們不須再透過資料庫層，去看 B 的貼文背後還有哪些因果關係，因為我們只在乎 "A 喜歡 B 的貼文" 這件事
- 只是此種關係的定義就必須讓程式撰寫者去撰寫
- 與潛在因果關係的比較
- 潛在因果關係通常只會在資料庫層連結，並是使用"物理性"的特性紀錄，像是收發時間
- Explict Casaulity 使用應用層 API 即可傳遞關係，且通常是易於理解的
- 限制
1. 使用者可以繞過此種關係
- A 告訴 B "你一定要看看這些照片"，會有這樣的關係: "照片 object" $\rightarrow$ "你一定要看看這些照片"
- 但單從這句話無法知道照片是指哪些照片
- 因此要有對應的機制去修補這樣的因果關係
2. 在不知道應用的 domain knowledge 之前，Explict Casaulity 很難判斷