# 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
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++
### Causal+ in COPS
#### COPS中有2個概念
* version: key具有不同value的時期，
* 為了保障因果關係，只有在保證```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
++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
:::
不同於傳統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中
問題:
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
:::
#### 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
:::
3. ```dep_check```檢查依賴
* yes: 立即回應操作
* no: block直到需求的版本被寫入
* 只檢查最近依賴
* 如果檢查超時，處理```put_after```的節點將重新發起它，如果發生故障，可能會發給新的節點。
### Reading Values in COPS
1. client library```get_by_version```給負責key的節點
:::info
:::
* LATEST為請求鍵的最新版本，給COPS，舊版本給COPS-GT
* 收到回應後，client library會將回傳放入context
### Get Transactions in COPS-GT??
COPS-GT client library提供```get_trans```
## 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
:::
* 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的最大吞吐量趨於一致
* 隨著操作間延遲的增加，每個操作的依賴數量減少(因為持續的垃圾收集)
Sign in with Wallet
Connect another wallet