# 2-2 Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS

==本文定義了一致性模型：causal+，帶有收斂衝突 (convergent conflict) 處理的因果一致性，並介紹能夠在廣域提供這種一致性模型的鍵值儲存 COPS 的設計和實現。==

## 1. Introduction

現代 Web 服務絕大多數選擇以強一致性為代價來擁抱可用性和分區容錯性，使這些系統能夠為客戶端操作提供低延遲和高可擴展性。再者，早期的大規模網路服務（通常專注於網路搜尋）幾乎沒有理由加強一致性，而隨著**社群網路應用程式等互動式服務的興起**，這種情況正在改變。

:::info
- **++ALPS system++**: 具有 Availability、low Latency、Partition-tolerance 和 high Scalability 四種性質的系統。
:::

有鑑於 ALPS 系統需犧牲強一致性 (linearizability)，我們尋找在這些限制條件下的 strogest consistency model。

- **++Why stronger consistency?++**
- It makes systems easier for a programmer to reason about.

本文考慮**收斂衝突處理的因果一致性**，稱為 **causal+ consistency**。許多先前的系統被認為實現了較弱的因果一致性，實際上實現了更有用的 causal+ consistency，儘管**沒有一個系統以可擴展的方式這麼做**。

- **++Causal dependencies++**: 因果相依性。舉例，使用者上傳一張圖片至網站，圖片被儲存，然後對該圖片的引用被加到使用者的相簿中，此時引用依賴著保存的圖片。

### Causal+一致性

- **因果元件 (causal component)** 確保**資料儲存尊重操作之間的因果相依性**。
- **收斂衝突處理元件 (convergent conflict handling component)** 確保**副本不會永久分歧，並且對於相同鍵 (key) 的衝突更新在所有網站上都能得到相同的處理**。
- 與較弱保證（例如最終一致性，可能會暴露紛亂無序的版本）不同，程式設計師不必處理可以獲得圖片引用但無法獲得圖片本身的情況。
- Causal+一致性確保客戶端看到一個**在因果上正確、無衝突且 always-progressing 的資料儲存**。

### COPS 系統 (Clusters of Order-Preserving Servers)

- 提供 causal+一致性，旨在支援由少量大型資料中心託管的複雜線上應用程式，每個資料中心均由前端伺服器（COPS 的客戶端）和後端鍵值資料儲存組成。
- COPS 以線性化的方式在本地資料中心執行所有 put 和 get 操作，並在背景以 causal+一致的順序跨資料中心複製資料。
- **Regular version**: 在資料儲存中的各個項目之間提供可擴展的 **causal+一致性**，即使它們的因果相依性分佈在本地資料中心的許多不同機器上。效能和開銷與先前的系統類似，但同時提供了**更大的可擴展性**。
- **COPS-GT**: 擴展版本，**提供了 get transactions**，讓客戶端能夠在多個鍵的情況下獲得一致的視圖。即使在完全可線性化的系統中，也需要 get transactions 來獲得多個鍵的一致視圖。我們的 get transactions **不需要鎖**，是**非阻塞**的，並且最多需要兩個平行的資料中心請求回合。比起 COPS 的常規版本，COPS-GT 對於某些工作負載（例如，寫入密集型）的效率較低，並且對於長時間的網絡分區和資料中心故障的響應能力也較弱。

---
- ALPS 系統的**可擴展性**要求是COPS與先前 causal+一致性系統之間的最大區別。


## 2. ALPS Systems and Trade-Offs

- **++Availability++**: 所有操作都會成功完成。不會永遠阻塞或傳回資料不可用的錯誤。
- **++Low Latency++**: 迅速完成客戶的操作。商業服務水準目標建議平均效能為幾毫秒，最壞情況下的效能為 10 秒或 100 毫秒。
- **++Partition Tolerance++**: 資料中心之間發生網路分區時依然可用。
- **++High Scalability++**: 資料儲存線性擴充。在系統中新增 $N$ 個資源可將總吞吐量和儲存容量增加 $O(N)$。

CAP 證明了有 AP 屬性的共享資料系統無法達成 linearzability（強一致性），低延遲也無法與 linearzability 和 sequential consistency 相容，為達成 ALPS，定義了中等的一致性模型 causal+。

## 3. Causal+ Consistency

兩個**操作**
- put(key, val)
- get(key)=val

**邏輯副本 (logical replica)**
- 儲存和檢索值的地方
- 每個邏輯副本託管一整個 key space
- 邏輯副本在 COPS 中對應的是一整個本地叢集的節點

:::info
**潛在因果關係 (potential causality)**：以 $\leadsto$ 表示
- 執行緒內 (Execution Thread)：若 $a$ 和 $b$ 為單一執行緒中的兩個操作，且 $a$ 早於 $b$ 發生，則 $a \leadsto b$。
- 讀取 (Gets From)：若 $a$ 是 `put` 且 $b$ 是 `get` $a$ 寫入的值，則 $a \leadsto b$。
- 遞移 (Transitivity)：若 $a \leadsto b$ 且 $b \leadsto c$，則 $a \leadsto c$。

不允許執行緒間直接通訊，要求所有通訊都透過資料儲存進行。


| *Execution Thread* Rule | *Gets From* Rule | *Transitivity* Rule |
| ---------------- | ---------------- | ---------------- |
| get(y)=2 $\leadsto$ put(x,4) | put(y,2) $\leadsto$ get(y)=2 | put(y,2) $\leadsto$ put(x,4) |

:::

### 3.1 Definition

==Causal+一致性==被定義為兩個屬性的組合：因果一致性和收斂衝突處理。

- ==**++Causal Consistency++**: `get`在副本讀到的值和 $\leadsto$ 順序的結果一致。==
- 不排序並發的操作
- 若 $a \not\leadsto b$ 且 $b \not\leadsto a$，則 $a$ 和 $b$ 為並發的
- 通常這會提升效率，因為不需要排序，可用任何順序複製兩者
- 但若兩者 put 到同樣的 key，則發生 conflict
- 不要 conflict 的兩個原因
- 未排序，副本可能永遠發散
- 可能代表一個需要特殊處理的特殊情況
- ==**++Convergent Conflict Handling++**: 在全部的副本中，所有衝突的`put`操作都是以相同的方式 (handler function $h$) 處理的。==
- handler function $h$
- 必須**滿足結合律和交換律**
- 副本可以用收到衝突的順序處理它們，且處理的結果會收斂
- COPS 可以自定義 handler function 但預設是 last-writer-wins

### 3.2 Causal+ vs. Other Consistency Models

:::info
:::

| Consistency Model | Consistency Ensured | Achievable for ALPS Systems |
| ----------------- | ---------------- | ---------------- |
| linearizability | 全域實時的排序 | X |
| sequential | 全域的排序 | X |
| causal | 相依操作間的部分排序 | O |
| FIFO (PRAM) | 執行緒內的部分排序 | O |
| per-key sequential | 對單個 key 有全域排序及最終一致性 | O |

### 3.3 Causal+ in COPS

COPS 系統使用兩個抽象幫助理解 causal+一致性：

- **++Version++**: 以 $key_{version}$ 表示，COPS 中若 $x_i \leadsto y_j$，則 $i < j$。一旦 COPS 中的副本回傳 $x_i$，causal+一致性確保它將僅回傳該版本或因果上較新的版本 (causal+ consistency’s *progressing property*)
- **++Dependencies++**: $y_j$ 依賴於 $x_i$ $\iff$ put($x_i$) $\leadsto$ put($y_j$)。

COPS 為在複製期間提供 causal+一致性，只會在寫完所有的 dependencies 後才會寫 version。

### 3.4 Scalable Causality

這是第一次正式命名並定義 causal+一致性。先前的幾個系統實際上是有保證到 causal+程度的一致性，但 Log-exchange-based serialization 抑制了副本的可擴展性，而 COPS 採用不同的方法以實現可擴展性。

- 每個資料中心的節點負責 key space 的不同分區，但可以追蹤並強制儲存在不同節點上的 key 之間的依賴關係
- 明確將每個 key 版本關聯的依賴關係寫進 metadata
- 當遠端複製 key 時，接收的資料中心會檢查相依性才提交傳入的版本

## 4. System Design of COPS

### 4.1 Overview of COPS

COPS 可以跨幾個資料中心執行


每個資料中心有
- 本地的 COPS 叢集
- 有儲存資料的完整副本，線性化（強一致性）鍵值儲存
- 每個節點（或單鏈節點）儲存 keyspace 的一個 partition
- 叢集內的操作是線性化的（低延遲）
- 叢集之間的複製是非同步進行的，以確保用戶端操作的低延遲以及面對外部分區時的可用性
- COPS 的用戶端
- 使用 COPS client library 直接 call COPS 鍵-值儲存的應用程式
- 只和在同個資料中心的本地 COPS 叢集進行通訊

#### 系統元件

- **++Key-value store++**
- 每個鍵值配對有關連的 metadata。COPS 中是版本號，COPS-GT中包含版本號跟相依性清單（其他的 key 和版本）
- export 三個附加操作：`get_by_version`, `put_after`, `dep_check`
- COPS-GT 保留舊版本的鍵值配對，以確保它可以提供 get transaction [(4.3)](#43-Client-Library-and-Interface)
- **++Client library++**:
- 向應用程式 export 兩個主要操作
- 讀取：get (COPS)、get_trans (COPS-GT)
- 寫入：put
- 透過 context 參數維護有關用戶端目前依賴項的狀態

#### 目標

用和現存的最終一致性系統相似的資源和開銷，提供 causal+一致性。

- 減少保持一致性的複製的開銷
- (COPS-GT) 減少空間需求，用 aggressive garbage collection 剪除 old state [(5.1)](#51-Garbage-Collection-Subsystem)
- (COPS-GT) 確保快速的 get_trans 操作，在最多兩輪的本地 get_by_version 內完成

### 4.2 The COPS Key-Value Store

- Traditional: <key, val>
- COPS: {key: (val, **version**)}，最新版本
- COPS-GT: {key: (val, version, **deps**)}
- deps = [(dependency_key, dependency_version), ...]

每個叢集都維護自己的鍵值儲存副本
- 可擴展性：用一致雜湊跨叢集節點對鍵空間進行分區，也可以透過其他技術（例如基於目錄的方法）
- 容錯：每個 key 都跨少量節點複製（使用鏈複製 (chain replication)）
- get 和 put 在叢集內是線性化的，叢集之間的操作是非同步的

**等價節點 (equivalent nodes)**
- 每個 key 在每個叢集中的主節點
- 一致雜湊為每個節點分配了不同的 key range，不同資料中心的 key range 可能有不同的 size 和 node mapping
- 個數與資料中心的數量成正比（不同資料中心的節點之間的通訊不是 all-to-all）

**相依性檢查機制**
- 在本地完成寫入後，主節點將其放入 replication queue
- 非同步傳到等價節點
- 等價節點會等到它們的本地叢集中滿足該值的依賴關係，再 commit
- 確保寫入以因果一致的順序發生，且讀取永遠不會阻塞

### 4.3 Client Library and Interface


client API 包含**四個操作**：

- **++COPS-GT Client Library++**
- 當用戶端 get 一個 key 時，將 key 和它的因果相依性加到 context
- 當用戶端 put 一個 value 時，將 put 的依賴項設定為當前 context 中每個 key 的最新版本
- 成功的寫入會回傳指定給寫入值的版本號 $v$
- 將 $<key, v, D>$ 加到 context
- 關於因果關係圖潛在大小的兩個問題
- 減少使用的空間：[5.1](#51-Garbage-Collection-Subsystem) 描述的 garbage collection，在 commit 到所有的 COPS 副本後移除 dependencies。
- 減少檢查的開銷：只檢查最近的 dependencies，client library 需在用戶端 write 之前先計算好才能做這項最佳化。
- 足夠提供 causal+ consistency 了


- **++COPS Client Library++**
- 只存 <key, version>
- get 操作時，將獲得的 <key, version> 加到 context
- put 操作時，用當時的 context 當作最近的 dependencies，清空 context，用寫入的結果填入 context
- 依賴於所有先前的 key-version pair，是最近的，所以不需要像 COPS-GT 存最近的 denpendencies

### 4.4 Writing Values in COPS and COPS-GT

所有的寫入先寫到用戶端的本地叢集，然後非同步的傳播到遠端的叢集。兩者都是透過下方的 API：


- 寫入本地叢集
- 過程
- 用戶端呼叫 put(key, val, ctx_id) 時，library 計算完整的依賴關係 deps，並識別出其中最近的依賴關係
- library 不帶 version 參數呼叫 put_after，COPS 不需要傳 deps
- 本地叢集中，key 的主節點指定版本號後將其回傳給用戶端 library
- 每個用戶端被限制只能有一個未完成的 put，因為後來的 put 需要知道前面的 put 的版本號
- put_after 確保 val 只會在依賴清單的項目都寫入後才會 commit 到每個叢集
- 本地：線性化
- 遠端：下面討論
- 主節點使用 Lamport timestamp 給每個 update 一個獨一無二的版本號
- high-order bits: Lamport clock
- low-order bits: unique node identifier
- 透過比較 Lamport timestamp，以及 last-writer-wins，偵測並解決衝突 [(5.3)](#53-Conflict-Detection)，得到每個 key 的所有寫入的全域排序
- Lamport timestamp 以尊重潛在因果關係的方式提供所有分散式事件的部分排序，因此全域排序與 COPS 的因果一致性相容
- 叢集間的複製
- 本地 commit 後，主節點呼叫 put_after（包含版本號），將資料非同步複製到其它群集的等價節點
- 其他叢集中收到 put_after 請求的節點需確認該值的最近依賴關係已在本地滿足
- 收到 dep_check 的節點檢查 local state 確認依賴的值是否已寫入
- 是，立刻回傳
- 否，block 直到所有依賴的值都寫入
- 如果對最近依賴的所有 dep_check 都成功，則處理 put_after 的節點 commit 寫入的值
- dep_check 逾時則重試，重新執行中若發生故障，則可能重新分配給另一個節點來處理

### 4.5 Reading Values in COPS

讀取透過下方的 API 完成：

COPS 中的 get_by_version 永遠是要求最新的，跟一般的 get 一樣。收到回覆後，library 將 <key, version[, deps]> 加到用戶端 context，回傳值到 calling node。

### 4.6 Get Transactions in COPS-GT

因為使用 get(key) 介面在讀取一組有依賴關係的 key 時無法確保 causal+一致性，所以COPS-GT client library 提供 get_trans 介面。

:::warning
**為什麼需要 get_trans？**

問題情境：time-to-check-to-time-to-use
- Alice 先將相簿 ACL 權限設置成僅好友可見，再寫入新的敘述，然後新增相片。
- 直覺但錯誤的做法：取得 ACL，再確認權限，然後讀相簿敘述和相片。
- 可能發生非好友的 Eve 取得舊的 ACL，確認權限後，ACL 被 Alice 修改了，Eve 卻讀到僅好友可見的相簿敘述和相片。

---

改成先 get(album) 再 get(ACL)？問題變成 time-of-check-to-time-of-use
- Alice 在更新相簿後刪除部分隱私相片並重寫敘述，再打開 ACL。
- 可能拿到舊的私人相簿，然後取得公開的 ACL，讀到隱私照片。
:::

- 用 get_trans 可以解決，能取得多個 key 的 causal+一致視圖。


- 第一輪：平行的對 get_trans 的 keys 中的每個 key 都開一個 get_by_version
- 檢查相依性，記錄滿足因果相依性的版本
- 第二輪：平行的取得需要的版本（如果第一輪取得的版本不滿足因果相依性的話）
- 更新 context，取得 consistent view

:::success
相簿舉例：第一輪拿到 public ACL 和 private album，因為 private album 依賴於 "friends only" ACL，第二輪會拿新版的 ACL。
:::

Causal+一致性在這裡提供兩個重要的特性：
- get_by_version 立刻完成，因為本地叢集必有所要求的版本
- 不會需要再為第二輪的 get_by_version 解決因果相依性，已由遞移 (Transitivity) 滿足

## 5. Garbage, Faults, and Conflicts

### 5.1 Garbage Collection Subsystem

#### Version Garbage Collection. (COPS-GT only)

- 為了響應 get_by_version 存了多版本
- get_trans 的演算法讓需要的版本限制在一個範圍內，所以能限制 get_trans 在參數 trans_time 內完成
- 若逾時則重新呼叫 get_trans 並用新版的 key 滿足 transaction，預計這個情況只會在叢集中的多個節點 crash 時發生
- 新版的 key 寫入後，只須保存 trans_time 加上 clock 誤差內的舊版本

#### Dependency Garbage Collection. (COPS-GT only)

- 為了提供 consistent view 存了 dependencies
- trans_time 秒後，值已被 commit 到所有的資料中心後
- 清理該值的 dependencies
- 標記 never-depend (COPS 和 COPS-GT 都有)
- 需要同步到所有叢集
- 遠端資料中心 commit 後，經過 trans_time，告知原始資料中心
- 所有資料中心確認後，原始資料中心清除 dependencies，並通知其他資料中心
- 減少溝通佔據的頻寬
- 副本只在該版 key 是 trans_time 秒後的最新版時才通知原始資料中心
- 否則不需要，因為整個版本會被清除

#### Client Metadata Garbage Collection. (COPS + COPS-GT)

- 用 ctx_id 追蹤 client session 期間（單一執行緒）的所有操作
- dependencies 只須保存到每個地方都滿足的時候
- 當 put_after 成功 commit 到所有資料中心，將該版本的 key 標記成 never-depend 並告知用戶端（get_by_version 的回傳值包含這個 flag），在 context 中刪除
- 從 put_after 移除不再需要的 dependencies
- 節點收到 put_after 時，檢查依賴列表並移除比 global checkpoint time 舊的項目
- global checkpoint time
- 主節點找到 pending 中的 put_after 最舊的 Lamport timestamp
- 聯繫其他的等價節點，一對一交換拿到最舊的 Lamport timestamp
- 資料中心內的節點 gossip 自己負責 key range 中最小的 Lamport timestamp，找到最小的

### 5.2 Fault Tolerance

#### Client Failures

代表用戶端停止發出請求，不需要任何處理。

#### Key-Value Node Failures

COPS 可以使用任何底層容錯的線性化鍵值儲存。系統參考 FAWN-KV，在叢集內做 chain replication 來容錯。

- 本地叢集
- put_after: 寫入適當的鏈的 head，在鏈上傳播，在 tail 做 commit
- get_by_version: 讀 tail
- 跨叢集
- put_after: 本地叢集 commit 後，由 tail 傳播到遠端叢集的 head
- dep_check: 遠端叢集向原始叢集的 tail 讀取，逾時則重新請求。遠端叢集從 head 傳播到 tail，再 commit 及 ack 回原始叢集。

Dependency garbage collection 也是類似的模式。版本回收在節點本地完成，global checkpoint time 的計算則在鏈的 tail。

#### Datacenter Failures

資料中心出錯或是發生分區時，COPS 仍然正常運行，但可能有幾個 key 不一致。

- 寫入時本地叢集出錯
- 故障：遺失發起且尚未複製出去的 put_after
- 分區未故障：不會遺失寫入的操作，推遲到恢復正常
- 寫入時遠端叢集出錯，或是發生分區
- 無法複製資料、進行回收清理，複製佇列變長
- 管理員有兩個選擇：
- 等待恢復
- 重新配置 COPS，不使用故障的資料中心

### 5.3 Conflict Detection

在不同執行緒同時寫入一個 key 時，衝突發生。

COPS 預設使用 last-writer-wins，last 由比較版本號決定。

也可以自定義衝突的偵測和解決策略，需考慮：
- 所有 put 操作須帶有先前版本的 metadata（寫入時，本地叢集可見的最後一個版本）
- 所有 put 操作都隱含的依賴先前版本，需要額外的 dep_check 操作（開銷很小且在本地操作）
- 需定義偵測到衝突後用來解決衝突的 convergent conflict handler

偵測衝突的流程：
- 假設目前寫入為 $new$，帶有先前版本 $prev$，而當前可見的版本為 $curr$
- $prev\not=curr$$\iff$$new$ and $curr$ are conflict

> 證明略，論文有

## 6. Evaluation

### 6.1 Implementation and Experimental Setup

### 6.2 Microbenchmarks

### 6.3 DynamicWorkloads

### 6.4 Scalability

## 7. Related Work

## 8. Conclusion

當今的大規模、廣域系統為用戶端提供「始終可用」、低延遲的操作，但代價是較弱的一致性保證和複雜的應用程式邏輯。本文介紹了一種可擴展的分散式儲存系統 COPS，可在不犧牲 ALPS 特性的情況下提供 causal+一致性。COPS 透過在每個叢集中的寫入之前追蹤並明確檢查因果相依性是否得到滿足來實現 causal+一致性。COPS-GT 在 COPS 的基礎上引入了 get transaction，讓用戶端能夠獲得多個 key 的 consistent view；COPS-GT 結合了最佳化來減少 state、最小化多輪協定並減少複製開銷。我們的評估表明 COPS 和 COPS-GT 提供低延遲、高吞吐量和可擴展性。

## Reference

https://www.cs.cmu.edu/~dga/papers/cops-sosp2011.pdf

https://keys961.github.io/2020/04/29/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB-COPS/

https://www.lucienxian.top/2021/01/18/Don%E2%80%99t-Settle-for-Eventual-Scalable-Causal-Consistency-for-Wide-Area-Storage-with-COPS%E2%80%94%E2%80%94MIT6-824/