---
# System prepended metadata

title: 2-2 Don't Settle for eventaul
tags: [Consistency Protocol]

---

# 2-2 Don't Settle for eventaul
## Introduction
在分散式系統中，因為CAP，普遍選擇P、A，且強C不容於ALPS，因為在過往C較不重要，但現如今社群軟體興盛，C也成為重要的因素

論文中則提出一個中間方案與運用的系統
* 命名與定義Causal+ consistency
* COPS: 一個具可擴展性、低延遲、高吞吐量、運用Causal+ consistency的系統
* COPS-GT: 建立在COPS的基礎上，擁有no block/lcok(最多演算法進行2輪)
* 處理transcation的能力，但長時間會有P或故障問題

Causal+ consistency
* 有收斂衝突: 永遠不會分歧
* 因果一致性: 所有都有序

COPS由少數大型datacenter組成
* front-end: client
* back-end: key-value store

## ALPS Systems and Trade-offs
![image](https://hackmd.io/_uploads/SkCYRc8A6.png)
wide-area deployments across a few to tens of datacenters通常需要達成以下目標
* Availability: 所有操作都能成功完成，操作不會因數據不可用而阻塞或返回錯誤
* Low Latency: 客戶端操作能快速完成，以確保流暢性
* Partition Tolerance: data store能在網絡分區的情況下繼續運行
* High Scalability: data store能夠線性擴展，增加資源可以對應增加系統的吞吐量和儲存能力
* Stronger Consistency: linearizability(strong consistency)，一旦寫入，接續的讀取動作應該要能獲取最新版本，好處為簡化程式設計、提供期待的system behavior


:::info
但因為CAP理論，所以C(linearizability)無法和A、P共存，C也不能和L共存，為了達成 ALPS系統的需求和易程式設計的平衡，paper設計出intermediate consistency model
:::
## CAUSAL+ CONSISTENCY
### abstract model
* operations
    * write: put(key,val)
    * read: get(key)=val    
* logical replicas
    * 存取value的地方
    * in COPS則為local cluster 
* potential causality
    * ```~>```
    1. Execution Thread: 在單一thread上，```a~>b```代表a發生在b之前
    2. Gets From: a為put，b為get且return value是由a寫入，```a~>b```
    3. Transitivity: ```a~>b```，```b~>a```，則```a~>c```
### causal+ consistency Definition
*  causal consistency
    *  get的return value要和~>操作所獲得的結果一致
    * ```a~\>b```，```b~\>a```則代表a和b為concurrent。但如果a和b皆為put同一key，則會發生conflict
    * conflict會有的問題
        1. 因為為無序，所以允許conflict永遠分歧，例如a為put(x,1)、b為put(x,2)，一份replica get(x) = 1、另一份replica get(x) = 2
        2. 會有特殊情況會需要特殊處理
* Convergent conflict handling
    * 要求所有conflict在所有replica中以相同的handler function h解決
    * 需具備結合律和交換律，例如h(a,h(b,c))=h(c,h(b,a))，才能保證收斂
    * h的策略有很多，包括最後寫者贏或是透過額外的procedure處理
### Causal+ vs. Other Consistency Models
* linearizability(strong consistency): 維護global、real time一致性
* sequential consistency: 維護global一致性
* causal consistency: 只保證為有序依賴那部分的一致性
* FIFO (PRAM) consistency: 只保證執行中的thread的有序依賴那部分的一致性
* per-key sequential consistency: 每個獨立的key上有global一致性，但彼此不相干
* eventual consistency: catch-all，最後才達成一致性  

++linearizability和sequential consistency不能實現於ALPS++
![image](https://hackmd.io/_uploads/HkcHplv0p.png =600x)


### Causal+ in COPS
#### COPS中有2個概念
* version: key具有不同value的時期，![image alt](https://hackmd.io/_uploads/HycxJ-PCT.png =70x)
    * 為了保障因果關係，只有在保證```xi~>yj，then i < j```時才會分派version，所以擁有progressing property
    * progressing property: version一定為遞增 
* dependencies: 如果```xi~>yj```，則xi必須寫在yj之前，也就是```yj depends on xi <=> put(xi)~>put(yj)```，xi稱為yj的dependencies
    * COPS為了確保causal+ consistency，所以在複製到別的cluster過程中，只在所有dependencies寫入後才能寫入version
### Scalable Causality in COPS
之前的許多系統使用log，會限制scalability  

COPS達成scalability
* 每個datacenter中的每個node負責不同keyspace中的區域，但系統可追蹤在不同node中的dependencies
* 藉由key version建立dependencies的編碼metadata，在remote複製key，接收的cluster的datacenter可在提交的前檢查
## SYSTEM DESIGN OF COPS
### Overview of COPS
==COPS = causal+ consistency + ALPS==

++key-value storage system with small number of datacenters++
* local COPS cluster
    * 組成datacenter且配備完整data複製
    * linearizability，因為local沒有分區且低延遲
    * scalability
* client
    * 為application使用client library進入COPS
    * 只能和所在的local COPS cluster進行溝通
* Client library
    * 實際與datacenter溝通的角色
    * 維護client的state dependencies
    
![image](https://hackmd.io/_uploads/Sy37ofvC6.png)

++Goal++
* 提供causal+ consistency
* 最小化複製到其他datacenter的一致性維護的overhead 
* (COPS-GT) Minimize space requirements
* COPS-GT) Ensure fast ```get_trans```operations
### The COPS Key-Value Store
* store
    * 每個key-value有對應的metadata
        * COPS: ```<key, val>```
        * COPS-GT: ```<version, value, deps>```，```deps```為```<key, version>```的list(COPS-GT會保留old version)
* 在datacenters間複製為非同步，確保client的低延遲及分區可用性
* scalability
    * 利用consistent hashing對 keyspace 分區
* fault tolerance
    * 每個key在small number的node中以chain複製
* primary node
    * 每個key在每個cluster中都有一個primary node
    * 每個cluster中的primary node集合成該key的equivalent nodes
    * 一個給定node需要通信的equivalent nodes總數與datacenters的數量成正比
:::success
在loacl cluster寫入完成後，primary node將其放入replication queue，隨後非同步傳送至遠端equivalent nodes。這些節點依序等待直到該值的dependencies在其local cluster中得到滿足後，才在那個local cluster commit
這種dependencies檢查機制確保了寫入操作按照因果一致的順序發生，並且讀取操作永不阻塞
:::
### Client Library and Interface
Client Library提供的client API
:::info
![image](https://hackmd.io/_uploads/ry5uBmwRp.png)
:::
不同於傳統key-value interface:
* COPS-GT的```get_trans```，一次可以return多個key-vaule的consistent view 
* 所有function接受context參數，context提供了因果關係來追蹤不同client之間的因果關係

#### COPS-GT Client Library

context argument為一個表格由<version, value, deps>組成
* 讀取key，Client Library將key和causal dependencies加到context中
* 寫入value
    * Client Library將當前context中每個鍵的最新版本加到put的dependencies中
    * 成功寫入後，將新的條目添加到context中

![image](https://hackmd.io/_uploads/SkQ4T7wAa.png)

問題:
1. 狀態存儲space需求
    * 解決: 垃圾收集，一旦dependencies在所有COPS副本中提交，便會被移除
2. 複製過程中的dependencies檢查
    * 解決: nearest dependencies，因為transitivity所以可以只檢查最近依賴
    
#### COPS Client Library
context argument為一個表格由<key, version>組成，就代表最近依賴
* 讀取key，Client Library將key和version加到context中
* 寫入value，使用當前的context作為最近依賴，清空context，將此次put的<key, version>放入context
### Writing Values in COPS and COPS-GT
:::info
![image](https://hackmd.io/_uploads/ryRFiEPRa.png)
:::
#### Writes to the local cluster
1. ``` put(key,val,ctx_id)```，client library計算出一個完整的依賴集合deps，找出最近依賴nearest
2. ```put_after```without版本參數(vers = 0)
    * COPS-GT: deps、key、val、nearest
    * COPS: key、val、nearest
3. local cluster的primary node分配version然後return給client library
*  ```put_after```操作的確保性
    *  確保val只有在其依賴列表中的所有條目都被寫入後才提交到每個集群。
    *  在客戶端的本地集群中，由於本地存儲提供線性一致性，這一屬性自動成立。然而，在遠端集群中這不一定成立。
*  版本號的唯一性
    *  primary node使用Lamport timestamp來為每次更新分配一個唯一的版本號。
    *  node將版本號的high order bit設置為其Lamport時鐘，low order bits設置為其唯一節點識別符
    *  Lamport時間戳為last-writer-wins
     
#### Write replication between clusters
1. 在local write commit後，primary node通過一系列```put_after```非同步將該寫入複製到不同集群中的equivalent nodes(```put_after```現在有版本號了)
2. 另一cluster接收到```put_after```請求的節點必須確定值的最近依賴是否已在本地得到滿足
:::info
![image](https://hackmd.io/_uploads/H1y5yHPRa.png)
:::
3. ```dep_check```檢查依賴
    * yes: 立即回應操作
    * no: block直到需求的版本被寫入
    * 只檢查最近依賴
    * 如果檢查超時，處理```put_after```的節點將重新發起它，如果發生故障，可能會發給新的節點。
### Reading Values in COPS
1. client library```get_by_version```給負責key的節點
:::info
![image](https://hackmd.io/_uploads/BkTReSPC6.png)
:::
* LATEST為請求鍵的最新版本，給COPS，舊版本給COPS-GT
* 收到回應後，client library會將回傳放入context
### Get Transactions in COPS-GT??
COPS-GT client library提供```get_trans```
![image](https://hackmd.io/_uploads/S1xifVHP0a.png)
## GARBAGE, FAULTS, AND CONFLICTS
### Garbage Collection Subsystem
刪除不必要的狀態
1. Version Garbage Collection(COPS-GT)
    * why: ```get_trans```限制了完成一次get交易所需的版本數量，且第二輪僅針對第一輪返回的版本之後的版本發出請求
    * COPS-GT限制```get_trans```的總運行時間，超時則利用新版本號重啟
2. Dependency Garbage Collection(COPS-GT)
    * why: 一旦與舊依賴關聯的版本不再為get交易操作所需，它們或某個更後版本將始終被get返回(x1, y1在z1前寫入在z1之後的get都會返還x1, y1)
    * 在所有數據中commit後，COPS-GT可以清理，並通知其他數據中心做同樣的事情
    * 在分區期間，無法回收最新版本key的依賴
3. Client Metadata Garbage Collection(COPS + COPS-GT)
    * client library會儲存metadata(用來追踪client操作)到context中
    * why和上一個相同
    * ``put_after``所有cluster commit後，會標記never-depend到key的version，並通知client library
    * node從```put_after```移除不必要的依賴。當節點收到一個```put_after```時，它會檢查依賴列表中的每一項，並移除版本號小於全局檢查點時間的項目(但放在這個章節超怪)
### Fault Tolerance
1. Client Failures
    * 單純停止發出新的請求，不需要恢復
2. Key-Value Node Failures
    * COPS為基於FAWN-KV建構而成，提供chain複製來掩蓋節點故障
    * local cluster
        * ```put_after```被發送到chain的頭部，一路走到尾巴，然後在尾部提交
        * ```get_by_version```操作直接被發送到尾部進行操作
    * 跨cluster
        * local的尾巴將```put_after```發到其他cluster
        * remote的head收到```put_after```後發出```dep_check```到尾巴(因為屬於read)
        * remote的head檢查完後，一路走到尾巴，然後在尾部提交
3. Datacenter Failures
    * 分區datacenter
        * 內部提交後```put_after```到外部會延遲到連接上之後
        * 活躍replication queue可能會長，可相信分區很快就會恢復，讓他長
        * 垃圾收集要等到恢復
    * 失效datacenter
        * 內部提交後```put_after```到外部會直接丟失
        * 活躍replication queue可能會長，可以重新配置COPS不再用失效的datacenter
        * 垃圾收集要等到排除
### Conflict Detection
default衝突檢測與處理策略是版本號和最後寫入者勝出，但可以自定義
具有衝突檢測的COPS為COPS-CD，有增加幾個的compontent
* 所有```put```都會帶有之前的版本資訊(metadata)，可以在寫入時得知先前的版本
* 所有```put```都需要對先前版本具有依賴，確保了新版本只有在其先前版本之後才被寫入
* COPS-CD有一個收斂衝突handler，在檢測到衝突時被調用

衝突檢測: 
:::info
![image](https://hackmd.io/_uploads/SkgE8DO0T.png =500x)
:::
* new為最新要寫入的版本，前一個則為prev，衝突版本為curr
1. curr > prev 因為progressing property
2. ```curr~/>prev```，因為new的前一個為prev
3. ```prev~/>curr```，因為curr在new前寫入
## EVALUATION
這張主要在測試COPS、COPS-GT、LOG(沒有依賴更新)

* 測試：
    * 透過基準(Microbenchmarks)測試來確立系統的延遲和吞吐量
    * 動態工作負載特性，通過改變伺服器每個datacenter的數量和調整工作負載特性（如put:get比例）來測試系統性能。

* 性能結果：
    * 當操作間延遲較低時，COPS顯著優於COPS-GT
    * 隨著操作間延遲增加，COPS和COPS-GT的最大吞吐量趨於一致
    * 隨著操作間延遲的增加，每個操作的依賴數量減少(因為持續的垃圾收集)