# 2-3: Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System

## 名詞定義

* Bayou(系統)是指這篇論文提出的輕量級分散式檔案儲存系統。
* Application(應用程式)是使用Bayou這個系統來存儲資料的程式，也是會直接與Bayou系統互動的client。
* User(使用者)是使用application提供的功能的人。
* 三者的關係大概是這樣，箭頭代表使用的意思:
$$User \rightarrow Appication \rightarrow Bayou$$
* Server是指Bayou系統中存儲資料與做運算的node。

## Abstract

Bayou是一個強調高可用性的輕量級分散式檔案儲存系統。

特點:
* 可以運行在運算能力較為不足的硬體上(例如: laptop、PDAs)、或運行在網路較差的環境。
* 使用write log (update operation) 作為修改的依據，**如果每個server的log都一致，那就可以保證每個server在檔案系統上的檔案會一致**。
* 當網路不通時，Bayou可以**直接寫在client上**。當網路恢復時再與server同步各自擁有的log。這保證了**Bayou的高可用性**。
* Bayou有能力去偵測各個server log的conflict，並利用**使用者自訂的mergeproc去解決conflict**，使各個server的log保持一致。
* 當使用者自訂的mergeproc失敗時，可以將該conflict mark起來，將來系統管理員可以手動的解決該conflict。
* Bayou只保證**eventual consistency**。
* 為了保持server間的log一致，Bayou針對log提供兩個操作。
* undo某條log上的operation。
* redo某條log上的operation。
* 當server A傳遞write operations給server B時，server B會先undo write log直到該write operations的第一個write operation，再redo整個writer operations，這樣就可以保證一致性。

## 1. Introduction

* Bayou設計的運行環境
* client有時可能會與server斷聯。
* client的頻寬很小。
* 所有server可能永遠不會同時連接。
* 為了保證高可用性，Bayou系統有以下幾個特點:
* 不使用quorum or lock去保證consistency。
* 資料隨時都可以讀，包含在資料因為自動merge失敗而在等待管理員解決時與系統正在解決conflict時，但系統會回傳該資料當下的狀態。
* 系統有可能會回傳過時或與其他node不同步的資料給使用者。
* 系統將處理過時資料的責任delegate給應用程式，且應用程式必須提供偵測conflict與mergeproc的方式，讓應用程式可以根據應用情境去設計這兩個function。
* Contributions:
* 提供一個general的框架給使用者自定義conflict detection與mergeproc。
* 提供一個方法去管理log。使其符合eventual consistency。
* 對於每條log定義了兩個state，分別是tentative與committed，前者代表可能因為conflict被覆蓋的log，後者則相反。
* 證明各個replica一定最終一定會相同(eventual consistency)
* 探討系統的security。

## 2. Bayou Applications
:::info
***這邊只是在說明應用情境，應該可以跳過***
:::
:::spoiler
說明Bayou適合運用在多人協作且非即時性的系統，以下提出了兩個例子。
* Meeting room scheduler
* 使用者可以在Bayou中的某一台機器上針對同一個meet預訂多個會議時間，這個操作會被本地機器當成一個tentative update operation，之後會與其他機器交流並決定該條update operation是要被commit還是取消。
* 使用者可以在Bayou中的某一台機器讀到目前全部會議的schedule，但其中過時的資料會被mark起來，代表其是有可能會變動的，而已經commit的預訂則是不會再被改變的。
* Bibliographic database
* 使用者可以在Bayou中的某一台機器上針對論文查詢，查詢到的論文可能不是最新的版本。
* 使用者可以在Bayou中的某一台機器增加新的論文或修改原有的論文，這個操作會被當成一個tentative update operation。
* 每篇論文會被assign一個unique id，但因為concurrent write的關係，有可能不同的兩篇論文擁有同一個unique id，系統會再產生另一個unique id賦予給其中一篇論文，令這兩篇論文都有unique id。
* 因為concurrent write，也有可能發生同樣的論文在兩個不同的機器被寫入，而有了兩個不同的unique id，則系統會將重複的論文自動刪除。
:::

## 3. Bayou’s Basic System Model
在Bayou系統裡，有兩種角色:
* server:
* 負責**儲存資料與處理client請求**的角色
* 本身含有兩個API，**Read與Write**，開放給client使用。
* **與client通信的API以RPC的方式為主**。
* 與其他server交換資訊時是採用anti-entropy的方式通訊。
:::info
anti-entropy其實就是點對點的通訊，而不是像傳統網路中使用broadcast來通訊。作者有說明根據某一個理論，就算是使用anti-entropy通訊，最終system上的所有server也會趨於同步。但使用anti-entropy通訊最後達到convergence的速度被很多個因素所影響，例如發送request的頻率、選擇要發送給哪個server的演算法，但作者說因為這些主要取決於使用Bayou的應用程式的scenario，所以這篇論文不討論。
:::
* client:
* 負責發送請求的角色。
* client會將server提供的API包裝成stub程式，利用stub程式傳送API request。
* 在傳送write reqeust時會夾帶額外的資訊，像是conflict detection的方式與mergeproc。且會有一個unique的write id。
* client可以任意更換與自己連接的server(手機漫遊可能有這個需求)，Bayou會使用session去確保使用者看到inconsistent data的機率降低。

## 4. Conflict Detection and Resolution

### 4.1 Accommodating application semantics

* 為何需要應用程式自己去定義conflict detection與mergeproc?
* 答: 因為對於不同的應用程式對於conflict的粒度有所不同。
* 以Bayou Applications中的第一個例子 Meeting room scheduler來解釋的話:
* 粒度過大: 規定在file層面會conflict，那會很常conflict，這代表兩個不同的operation對於同一個檔案的replica修改就算conflict。
* 粒度過小: 規定在record層面會conflict，也就是兩個不同的operation永遠不會conflict，因為他們必定屬於兩個不同的record。
* 因此粒度的選擇應該由應用程式自訂，以這個例子來說，conflict的定義應該是現在系統中有沒有兩個不同的meeting預定在同個時間且同一個會議室。

* 系統讓應用程式可以自訂兩個操作，***dependency checks(conflict detection) and merge procedures(mergeproc)***。write operation的流程如下
* 

### 4.2 Dependency checks

* 系統透過conflict detection的function可以去偵測讀寫衝突與寫寫衝突。

### 4.3 Merge procedures

* 在發生衝突時，server會call mergeproc來自動解決衝突。
* 當mergeproc失敗時，server會將失敗的merge儲存進log，並等待人工解決conflict。

## 5. Replica Consistency

* 要確保server會符合eventual consistency，需要滿足以下兩個條件:
* server上的log最終會一樣。
* 所有write operation的操作必須是deterministic，也就是write operation不具有隨機性。
* server上的write operation的格式，包含timestamp(由系統的real time clock與logical clock產生)，以及一個unique的write ID。
$$<timestamp, ID\ of\ server\ that\ assigned\ it>$$
* server上的log最頂層會是committed的write，再來則是tentative的write，兩者皆按照timestamp排序。
* 所有server必須要被指定相同大小的CPU運算資源與相同大小的Memory，因為如果硬體資源不同的話，可能會造成有些write operation在某些server成功，在某些server卻失敗。

## 6. Write Stability and Commitment
* 對於一個write operation在某一個server上何時能被稱作穩定?
在該server上，timestamp小於該write operation的操作都被寫入了，那這個write operation本身就能被稱作穩定。
* Bayou提交方式:
* 選出一個primary server去提交它。
* 對於負責提交該data的primary server，所有針對該data的write operation一旦經由anti-entropy傳到該server，經過排序後就會被提交，也就是從tentaive轉換成committed。提交後再經由anti-entropy傳到與之相連的其他server。
* 並不能保證write operation的提交順序和時間順序一致，舉例來說:

> * A更新<-,10,A>W1，B更新<-,20,B>W2，主节点为C，正常下应该：W1,W2
> * A由于一直断线，C先看到B，W2=<5,20,B>，并将其提交
> * A终于上限，C看到A，W1=<6,10,A>，并将其提交
> * 此时顺序变为W2,W1

* 這個方式的優勢是就算primary server暫時不可用，也不影響讀寫操作。因為在這期間的操作會變成tentative並存在其他server上，等到primary server恢復時，還是可以將那些操作轉變為committed。

## 7. Storage System Implementation Issues

* Bayou使用的存儲系統應該要提供以下幾種操作:
* 有效率的寫入log。
* 有效率的undo/redo write operation。
* 要可以有效率的展現log中的full view(包含tentative與committed的操作)、committed view(只包含committed的操作)。
* 支援server之間的anti-entropy通訊。
* 系統架構圖:
* 在這圖中:
* Memory
* Tuple Store可以當成是一個SQL的資料庫，裡面存儲著實際上被寫入的那些資料，每個data有額外附加2個bit，代表該資料目前在哪個view中。
* 01：只存在full view中。
* 10：存在于commit view，也存在于full view中。
* 11：存在于Stable Storage中（被checkpoint了）。
:::info
Tuple Store有分為在memory裡的部分與在stable storage裡的部分，前者是有被apply tentative write operation的狀態，後者則是作為checkpoint的作用，用來在server故障時恢復資料。
:::
* Undo Log裡面紀錄了tentative write operation如果要撤銷的話需要執行的操作。
* 在記憶體中的write log保存了所有的tentative write operation與部分的committed write operation。
* C向量紀錄在Write Log中執行最後一個commited write operation後的timestamp，F向量紀錄在Write Log中執行最後一個tentative write operation後的timestamp，這兩個向量的作用是在進行anti-entropy通訊時保證相同的write operation不會被重複執行。
* Stable Storage
* 在Stable Storage中的write log保存了已經穩定的committed write operation。
* O向量紀錄了server最近被丟棄的write operation的timestamp，這裡的丟棄是指在Memory的write log中被轉移到Stable Storage的操作。這個向量的功能與上面兩個向量一致。
* 當server接收到write operation的pseudo code

## 8. Access Control

> 以一个data collection为粒度，并通过非对称加密，实现访问控制和相互认证。
Bayou使用3种认证来授予、委托和收回data collection的访问权：
> * AC[PU,P,D]：授予用户权限P（如read, write, server）于data collectionD，PU为用户的公钥
> * D[PU,C,PY]：将公钥为PY的用户下的证书C委托给另一个公钥为PU的用户
> * R[C,PY]：收回公钥为PY的用户下的证书C

* 在一個client發出一個write operation給某一個server時，該server會驗證client的證書且確認該client是否有權限去更改該data。在該write operation被傳送給該data所屬的primary server時，primary server在要commit該write operation時會在檢查一次該client是否有權限做這件事。

## 9. Status and Experience


## 10. Conclusions

Bayou是一個針對移動應用程序的存儲基礎設施，僅依賴於弱連接性的假設。為了應對任意的網絡分區，該系統建立在點對點的客戶端-服務器和服務器-服務器通信基礎上。為了提供高可用性，Bayou採用弱一致性複製，使客戶能夠連接到任何可用的服務器進行讀取和寫入操作。支持自動衝突檢測和解決使應用程序能夠有效處理並發更新。該系統通過確保所有更新最終傳播到所有服務器，使服務器按照全局順序執行更新，並確保所有服務器以一致的方式解決任何更新衝突，從而保證最終一致性。

## Reference:
https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p172-terry.pdf
https://keys961.github.io/2019/04/30/%E8%AE%BA%E6%96%87%E9%98%85%E8%AF%BB-Bayou/