# 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
* 若```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呼叫結束
* 具有原子性，要嘛全部成功，要嘛什麼都沒更新
* 一旦commit，表示一定成功，必須要能夠在背後解決可能隱藏的HW問題
* 若transaction中有未return的```File.Read```，仍可commit; 未return的```File.Write```，則不能commit
* 系統或使用者可拋棄transaction，但必須取消所有write
* 提供serial consistency(上面提過)，但只在有順利commit的情況下
### Interface
* file suite
* 一個抽象的概念，為一個檔案由copy(這裡的copy我不知道是指個別data的copy(應該)，還是特別的一份file copy來實現file suite??) 的集合實現，copy稱為representatives
* 有一份配置，包含r、w、representative的數量、container、擁有的票數
* 由```File.CreateSuite```建立與儲存
* 每個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

* 每次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
1. 收集read quorum
* After a file suite is first accessed, collecting a quorum never encounters any delays，因為同一transcation不用再做詢問
2. 讀取速度最快的file
* Write to file suite
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時就會被擋下來

1. 利用fork對每個representative詢問版本(因為每個representative中的資訊都不同，所以才要每個都找)
2. 取得representative中prefix的資訊並如果為最版本則更新FileSuite中的資訊
3. 釋放lock
* collector
* 使用場景: 收集quorum，且會回傳回應速度最快的quorum
* read quorum collect
1. 等待lock(representative respond for inquirie)，則擁有voting rule(可能是依據回應速度成為seed)不用等待全部查找完畢是因為unknown不會加入quorum，若未尋找完畢就找到quorum則代表剩下的representative用不到
2. 對於每個representative若version number已知則不論是不是最新版本都加入quorum
* write quorum collect
1. 若不是current version加入read vote; 若是current write vote
2. 若找不齊write quorum，表示有可能read中有過多舊版本，會先啟動背景程序更新representative重新來過
* abort
* 拋棄transcation
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