---
# System prepended metadata

title: 1-4 Weighted Voting for Replicated Data
tags: [CAP Theorem]

---

# 1-4 Weighted Voting for Replicated Data
## Introduction
* 在分散式系統中，Replication of data且放置在每個node中，則可增加效能與可靠性，包括能平行使用data、提高data的就近訪問能力、可抵消複製維護成本、可使用其他copy。因為replicated files會有版本更新問題，此篇論文的目的就是介紹了一種演算法來維護replicated files。
* 演算法特色
    * 每份copy都被分配了一個數量的票數(vote)，可以不同
    * 每次執行transaction會收集共有r票的read quorum(為copy file的集合，其中票數相加為r)和共有w票的write quorum，r+w>v(分配給所有copy的票數)
    * r+w>v，根據鴿籠原理，因此read quorum和write quorum中至少一個相同
        * copys中一定有總票數為w的set是最新的版本，此為最近一次的write quorum
        * read quorum中一定會至少有一個是最新版本的copy
    * 維護Version number來判斷哪個copy是最新版本
* 演算法好處
    * 能處理copy unavailable，因為只要票數超過就行，不一定要特定的copy
    * 不需要複雜的訊息傳遞溝通，因為是建立在transaction機制上
    * 提供serial consistency(??)，因為是transaction會感覺像是獨立運作，且可隱藏不在預期內的操作，例如故障恢復
    * 始終提供最新版本data
    * 調整r、w、投票結構可改變file的性能或可靠性
    * 可整合所有額外創建的copy到framework
## The Basic Algorithm
### Environment
* 需要配備stable file system
* object
    * file: array of bytes
    * container: file的儲存倉庫，像是disk
    * 每個object有unique name
* file可以Create、Delete、Read、Write
![image](https://hackmd.io/_uploads/B1Ajq3CTa.png)  
    * 若```File.Read``` unavailale file，則不會回傳
    * Outstanding uncompleted reads, because
they never occurred, do not affect the ability of a transaction to commit??
    * 若```File.Write``` unavailale file，則不會回傳
* transaction 
    * file對於同步控制和故障恢復的操作，一個transaction一組file操作
    * one process, one transaction
    * 由 begin transaction呼叫開始，由commit transaction呼叫結束
    ![image](https://hackmd.io/_uploads/BJ6EphCT6.png)
    * 具有原子性，要嘛全部成功，要嘛什麼都沒更新
        * 一旦commit，表示一定成功，必須要能夠在背後解決可能隱藏的HW問題
        * 若transaction中有未return的```File.Read```，仍可commit; 未return的```File.Write```，則不能commit
        * 系統或使用者可拋棄transaction，但必須取消所有write
        ![image](https://hackmd.io/_uploads/HJfbZ6Rpp.png)
    * 提供serial consistency(上面提過)，但只在有順利commit的情況下  
### Interface
* file suite
    * 一個抽象的概念，為一個檔案由copy(這裡的copy我不知道是指個別data的copy(應該)，還是特別的一份file copy來實現file suite??) 的集合實現，copy稱為representatives
    * 有一份配置，包含r、w、representative的數量、container、擁有的票數   
    ![image](https://hackmd.io/_uploads/BktISpR66.png)
    * 由```File.CreateSuite```建立與儲存
    ![image](https://hackmd.io/_uploads/Sy03IaATa.png)
    * 每個representative的prefix紀錄其他representatives及其的票數(??)
    * 可視為file，使用```File.Read```、```File.Write``` 、```File.Delete```操作
    * 可操作file(file suite)的performance和reliability
        * 修改不同representative的票數，例如可加權到高效率的file增加高效率
        * 修改r、w控制read或write，為反比，因為收集越少票數表示越快
### The Algorithm
* FileSuite
    * monitor，entry procedure有lock
    ![image](https://hackmd.io/_uploads/HyEx7ACpa.png)

    * 每次transaction都需要創建新的```FileSuite```，創建時monitor內部的基本資訊是從一些representatives的prefix中得到的
:::success
step for each transcation: 
1. inquiries確認file suite版本是否跟每個representative一樣
2. collector收集quorum
3. 執行Read/Write
:::
* Read/Write file suite
    * Read from file suite
        ![image](https://hackmd.io/_uploads/S1cZiR0aT.png)
        1. 收集read quorum
            * After a file suite is first accessed, collecting a quorum never encounters any delays，因為同一transcation不用再做詢問
        2. 讀取速度最快的file
    * Write to file suite
        ![image](https://hackmd.io/_uploads/BkthhARaT.png)
        1. 收集write quorum，成員必須全部為最新的版本
        2. 寫入為平行執行，利用fork對所有quorum中的成員進行寫入
        4. 增加file prefix中和FileSuite entry的version number
        3. 若是寫入相同部分則undefined(會發生嗎??)
    * 當執行時間超過規定時間則判斷crash，拋棄transaction
* inquiries
    * 使用場景: a file suite第一次被trancation使用，需要詢問共有資訊以及representative的訊息，因為目前保存在FileSuite的不一定會是正確的，有可能在此trancation不知道的情況下有其他trancation有更新過
    * read quorum需要在file suite可以處理request(包含寫嗎??)前建立；voting rules(FileSuite中的資訊)需要在read quorum前建立
    * 若a representative不可存取，則在讀取prefix時就會被擋下來
    
    ![image](https://hackmd.io/_uploads/BkexLykRa.png)
    1. 利用fork對每個representative詢問版本(因為每個representative中的資訊都不同，所以才要每個都找)
    2. 取得representative中prefix的資訊並如果為最版本則更新FileSuite中的資訊
    3. 釋放lock
* collector
    * 使用場景: 收集quorum，且會回傳回應速度最快的quorum
    * read quorum collect
    ![image](https://hackmd.io/_uploads/H1T6vgkAa.png)
        1. 等待lock(representative respond for inquirie)，則擁有voting rule(可能是依據回應速度成為seed)不用等待全部查找完畢是因為unknown不會加入quorum，若未尋找完畢就找到quorum則代表剩下的representative用不到
        2. 對於每個representative若version number已知則不論是不是最新版本都加入quorum
    * write quorum collect
    ![image](https://hackmd.io/_uploads/Bkj-_g1CT.png)
        1. 若不是current version加入read vote; 若是current write vote
        2. 若找不齊write quorum，表示有可能read中有過多舊版本，會先啟動背景程序更新representative重新來過
* abort
    * 拋棄transcation
    ![image](https://hackmd.io/_uploads/rJ_Bw4JRa.png)
    1. reset FileSuite
    2. transcation重新開始
    3. inquires


## Refinements
* Weak Representatives 
    * 一個票數為0的representatives，可以加入到任何quorum中且不會影響，放在high performance或local container可提高performamce
    * 特性
        * 不負責保管data，因為vote為0
        * 錯誤可單純設version number成unknown
        * lock避免共享(我覺得Weak Representative有點像單一node所有的且不可共享，否則本末倒置)
* Lock Compatibility
    * 在原本的lock中，Read、Write、No Lock3種狀態，但只要一碰到Write就會被lock。但實際寫入只在transcation commit的時候，所以原本的lock非常沒有效率，通過引入I-Write(再提交時才鎖住)讓等待時間減少
    * I-Write遇到I-Write時會鎖住，因為總會有人要commit
* Lower Degrees of Consistency
    * 雖然系統保證serial consistency，但對於不需要最新版本的使用來說被限制，所以給予較低的一致性，(可恢復??)
* Size of Replicated Objects
    * 有些應用中可能會需要更小的object，例如database需要tuples。但在此論文中最小object為file
* Broken Read Locks
    * 在衝突時break read lock而不是丟棄transaction
        * 則丟棄數量下降
       * 可利用告知version number更新，最小lock object則不會是file
* Reassigning Votes
    * 可以更新票數配置以提高效能，但會發生衝突
    * 證明??
* Replicating Containers
    * 複製container可解決當container fail的情況
    * 在replicated container創造檔案則為建立file suite??
    * 特性:
        * 可靠性上升，實際擁有備份功能
        * replicated container可以輕鬆執行安裝及卸載
* Releasing Read Locks
    * 查詢representative的狀態內容時所有representative會獲得read lock，但可以釋放一些不在quorum中的read lock
* Updating Representatives in Background 
    * 結合replicated container，可以更新舊版本的representative以及利用多餘的通訊容量傳輸
## Implementation
* The Violet System
    * 分散式日歷
    * file suite name為list包含representatives
    * lock problem
        * user A和B長时间查看相同的日歷，超做系统保證查看data的任何最短时间
        * 當user A write，User B's transaction會被取消。這時，用户B被拒絕使用data，且user B的node會不斷request以重新整理畫面
        * user A 可能因為思考等待輸入，最终超時了，user A的transaction會被取消。user A和B的畫面最終都是重新產生舊訊息
        * 可利用I-Write來解決
    * performance
    ![image](https://hackmd.io/_uploads/BybHdEk0T.png)

