# 1-4 Weighted Voting for Replicated Data
## Introduction
- Replication data 可以讓資料就近存取，也增加了資料的可用性 (availability)，也增加可靠度 (reliability)，如何有效管理副本顯得特別重要
- 本篇論文所提出的演算法概念如下
- 對於每個副本給與一些票數
- 對於每筆 transaction，他會一個一個累加 representative (副本)的票數，並收集這些副本，直到能超過 r/w 票數門檻，而這些副本便是我們 read/write quorum (候選人)
- r 跟 w 有一個限制， r+w > v，v也就是所有 representative 的票數總和
- 運用鴿籠原理可知， read quorum 跟 write quorum 一定至少有一個是重複的
- 收集的 read quorum 一定有一個是最新版本的
- 一定會有一群票數總和加起來為 w 的 representative 是最新版本的
- 簡單說明如下
- 假如有3個副本，每個副本各1票
- r+w > v => r 和 w 設為 2
- 要讀必須讀兩個副本，要寫也要寫兩個副本
- 必定會有一個是重複的，而該重複的也會是最新版本
- 本演算法帶來的優點
- 就算有 node 壞掉，r/w 門檻有過還是可以進行
- 不需要複雜的檔案通訊機制? (It consists of a small amount of extra machinery that nlllS on top of a transactional file system. Although "voting" occurs as will become evident later in the paper, no complicated 11lessage based coordination mechanisms are needed.)
- 符合 serial consistency，多個 transaction 看起來就像 sequential 進行，每次都能夠有最新版本給使用者
- r, w 和 每個 representative 的票數可以依據系統 / node 需求 (performance / reliability)客製設定
- 任何的副本都可以應用此演算法，包含本地暫存副本(快取)也是
- 演算法介紹是使用 Mesa 程式語言盡進行

## Other Works
- 在當時，分散式系統被歸納為兩類
- 有一個 primary site 進行版本更新，其餘 node 為儲存副本用
- 將所有 node 的版本都更新，如 SDD-1 是透過一個複雜的通訊機制來維護各副本的版本

:::info
- 在進入演算法介紹前，簡單化假設 (其實好像也沒很重要)
- 即使在不同機器上，任意物件(包含後面介紹的 class )被初始化後都有獨立的名字
- 所有機器上的 file system 底層運作方式一樣
:::
## 基本物件 & 環境認識
- Files
- bytes of array

- Containers
- files 的存放處
- 例如: 硬碟 磁碟

- Transactions
- 一系列的 Files 操作
- 由 begin 和 commit 包起來，commit 後，transaction 的行為才成立
- ACID (沒有C):
- 論文本身並沒有直接點名就是 DB 的 ACID 概念，有可能只是剛好符合
- 保證所有的寫行為都有成功，不然就是沒有任何一個成功，二選一 (Atomicity)
- Serial Consistency (Isolation)
- 一個完成的 transactions ，不會被硬體損壞受影響 (Durability)
- 假如要對多個副本進行讀/寫行為，可以平行處理 (fork process 做事情)，而 Forked process 可以透過這個回歸 parent process。
- 使用者手動放棄、電腦壞掉、通訊錯誤或是 lock conflict，可以進行 abort (放棄)，如此，所有的 write 行為不會計數

- <b>Serial Consistency</b>
- 多個 transaction 可能是 concurrent 進行，但是系統/演算法會決定出一個 order，讓其看起來 sequential 進行。
- 就像隱藏了 concurrency

- 其餘規則
- 假如讀取的檔案是不可用的，`File.Read` 不會回傳;反之，`File.Write` 也一樣
- 未完成的 read 不影響 transaction 做 commit
- 未完成的 write ，transaction 必須完成所有的 write 才能 commit

- File Suite
- 是一種 abstraction interface
- 一個 file 的多個副本集合體。其中副本又被稱作 `representatives`，因為後續演算法是透過投票的方式進行
- 可以想成
- A檔案是一個抽象的檔案介面(File Suite)，他本身有很多副本，散落於不同機器或目錄，A_1, A_2...
- 但統一都對A檔案操作，而`representatives`有可能是A_1, A_2...
- 被創建時要提供以下參數
- r: 判定讀行為成功的最少票數
- w: 判定寫行為成功的最少票數
- v: 存放每個`representatives`的陣列，會記錄每個`representatives`放在哪個 container，以及其所擁有的票數
- 就如同操作一個 file(read, write, update, delete)。但是多了兩個 file 沒有的特徵
1. performance: 延遲性相關
2. reliability: 系統穩定性相關
- 可以針對著重哪個特徵，而對不同`representatives`有票數分配
- high performance -> heavily weighting high performance representatives
- very reliable -> heavily weighting reliable representatives, or equally weighted representatives
- 當時年代把分散式系統分類為 centralized 以及 decentralized，此篇論文表示此演算法兩者皆通 (呼應前面 related work 說的)
- <b>decentralized structure</b> -> equally weighting representatives
- <b>centralized structure</b> -> assigning of all of the votes to one representative
- 可以針對應用的特性，像是 讀寫比、行為的成本 或是 期望的 reliability 以及 performance，設定不同的 r, w。
- r/w 低，(operation的)讀/寫 reliability 以及 performance 增加
- 不是指 data，是指 operation
- 門檻低，很快就決定出 quorum (performance)
- 門檻低，不會因為到不了門檻導致 operation 失敗 (reliability)

## 核心演算法
### FileSuite
- 初始化
- FileSuite 是透過 Monitor (OS 教過 Monitor) 實作出來的
- 對於 shared data 的操作會上 lock
- FileSuite 會記錄以下資訊
1. suite: SuiteEntry 的陣列
- SuiteEntry紀錄每個`representatives`的名字、版本和票數
2. r 和 w 的設定

- Read
- 首先聚集特定數量的 <u>讀候選人</u>
- 從這些 <u>讀候選人</u>中，通常是選擇可以反應最快的(延遲低)

- Write
- 首先聚集特定數量的 <u>寫候選人</u>
- 在寫之前，每個<u>寫候選人</u>的版本必須是最新的，確保不會寫到過時的候選人
- 可平行地寫入每個候選人 (演算法用fork)
:::info
- 於演算法中
- quorum 是 Set，在上面 FileSuite 資料結構裡有寫到是 boolean array
- suite 是多個 `representative` 的陣列
- for 迴圈整個 suite，並查看該 index 的 quorum 是不是 true，來得知是不是候選人
:::

### 版本查詢
- 在上述 read / write 可以發現，在收集候選人的時候，演算法一定會確定有正確的版本在這些候選人中。也就是在對 file suite 操作前，會先做各個 representative 的 version 查詢。
- <b>針對每個 representative ，做 version 查詢</b>
:::info
- Inquiry
- 針對每個 representative 開始查詢
:::
:::info
- ReadPrefixInformation
- 從 stable file system 讀取各 representative 的 version 還有投票規則 (Paper Figure 1)
- 回傳的值作為參數傳給 `NewRepresentative`
:::
:::info
- NewRepresentative
- 更新 representative 的 version
- 同時如果發現有 representative 的 version 是最新的，將其 voting rule 更新給 file suite
:::

### 候選人收集
- 剛剛的 version 查詢，在確定 voting rule 是最新的之後，便會進入收集環節
- CrowdLarger 是一個 Condition variable (詳見 Monitor 介紹)，是 lock 的一種。在剛剛的更新完成後，便會 unlock
- Read
- 除非有任一個 representative 更新了投票規則，否則持續等待 CrowdLarger
- 對應演算法裡註解`-- until the first representative responds we don't have a seedfor the voting rules`
- 對應內文的第一個 potential problem: `it is possible that a read quorum of the suite's representatives have not reported their version numbers.`
- Collector 會選擇延遲低的 representative 當作 quorum，增進 performance
- 對應演算法裡 function `SortRepresentativesBySpeed[];`
- 開始累加票數，值至超過最新 voting rule 裡的 r quorum 門檻
- 回傳 quorum (boolean array)，代表哪幾個 representative 是候選人
- Write
- 同前面 read 操作，會選擇延遲低的當作　quorum，並且持續累積票數，值至超過最新 voting rule 裡的 w quorum 門檻
- 特別注意的是，多了一個 condition <u>`IF suite[j].versionNumber = current`</u>，呼應前面說的寫候選人版本要是最新的
- 假如 r < w，可以相信 read quorum 已經比 write quorum 早收集完成，假如 write quorum 因為沒有夠多的 current version representative 可以加入，那就可以透過 read quorum 得知 current version，並先行更新過時的 representative，如此 loop 回去找 write quorum 時，便可收集足夠多的 write quorum
- r >= w 呢? 就只能一直 loop 直到足夠多的 write quorum
:::warning
- 處理 r < w 的狀況如下
:::

### 中斷行為
- 使用者中斷或是遭遇系統中斷，file suite的狀態就不完整，包含投票規則、各 representative 的狀態都應該被放棄不再被使用，就是直接設為空值(第一個紅框)，並且等待下次版本查詢再重新替換狀態(第二個紅框)

## 改進
### 1. Weak Representatives (弱代表)
- replicate 也可以存為 temporary data 於使用者本地電腦上，並給與 0 票
- 此種 replicate 不是為了 reliability，而是為了 performance，加快反應速度
- 透過上面的收集候選人演算法，temporary data 通常是反應最快的(因為存於使用者電腦上)，而且因為 0 票，也會被納入候選人列表
- 以下例子為例:
- 高讀寫比環境，一個 server(75ms 延遲)，多使用者(使用者本地電腦 65ms 延遲)
- representative 1 是 server 上的副本，2跟3是兩個使用者暫存在各自電腦的副本
- 前面有說累積票數要大於等於r/w，因此 quorum 便會有本地副本以及 server 上的副本
- 讀的話會選擇延遲低的，因此本地副本先行存取，因此底下延遲標示 65ms
- 寫的話因為每個每個 write quorum 都要寫，因此取延遲最大的 representative 1

### 2. Lock compatibility
- 修改原有 lock 的規則，增進系統的 concurrency
- 原有的 lock 規則
- No lock 就任何行為都可以做
- Read lock 只允許不做事或讀而已
- Write lock 只允許不做是
- 雖然 read 可以很多人同時讀，但 writer 只能有一個
- 給 write lock 一個 time out，讓 writer不能霸佔太久，是一個暫時性解法。後續會提到此解法不合適
- 改過的 lock 規則
- 一個 transaction 中，所有的 write 是在 commit time 才發生的，commit time 之前其實只是處理在 buffer 中而已
- 透過這個特性，將 write lock 拆成兩個: I-Write, Commit
- 當使用者正在新增資料時(原文使用 datum，不知跟 data 差在哪)，I-Write 會上鎖，代表有意圖寫入
- 有意圖寫入，但還沒真的寫進去，reader 還是可以先讀舊資料
- 確定寫入後，轉為 Commit，直到 commit 結束並解鎖
- commit時，資料正在更新，不能讓使用者繼續讀舊資料

### 3. Lower Degrees of Consistency
- Degrees of Consistency，於 `Granularity of Locks and Degrees of Consistency in a Shared Data Base` 有說明各 degree 的標準
- 簡單思考可以想成，degree 越高，consistency 越強
- 假如有一個應用，只是單純提高 performance，或是他有額外的版本檢查機制，可以單純的把 r 設成 0，就可以利馬回傳任何一個結果，而不管他的版本對不對

### 4. 最小可複製物件的種類
- 根據應用需求，可能會有不同種的物件做成副本
- 例如 DB ，可能會想複製 relation 或 index
- 本演算法要求物件的版本號碼在 transaction 進行時不能被更動，因此最小的種類只能被限定為檔案
- 當一個檔案修改完後，版本後才會變動

### 5. 打破 read lock
- 假如允許強行破壞 read lock，帶來兩個優點
- 可以減少被放棄的 transactions ，如需 commit 的 write transaction

### 6. 重新給與票數
<b>TODO</b>

### 7. 複製 container
- 假如使用者A使用 c d 容器，使用者B使用 d e 容器，當d容器下線時，使用者A B 的 transaction 有可能持續進行，也有可能都不能進行，給系統帶來一個不確定性
- 可以複製容器 d 出來，使用者可以把這個複製的容器當作一般容器操作
- 但如果是再複製的容器裡 create file ， 他會建立一個 file suite。可以想成複製容器 d 的 d_1, d_2, d_3 .... 也都需要 create file，因此是建立一個這些在複製容器內副本的 file suite
- 被複製的容器叫做 base container
- 複製容器的幾個優點
- 增加了系統的 avalibility，同時系統也可以知道說 base container 下線後，可以改用 replicate container 進行
- 做到備份的功能
- 這些複製的 container 就算下線了，整體影響也不大

### 8. 釋放 read lock
- 針對版本查詢，因為版本查詢會去查所有 representative 的 version，每查一個，那個就會被上 read lock
- 假如確定已經不會在 quorum 裡的 representative，可以先行釋放 read lock，而那些 representative 就可以被 commit 的操作改變

### 9. Updating Representatives in Background
- 可以在 replicated container 上更新舊的 representative，加強 replicated container 的作用

## 實作
### Violet
:::spoiler 網路架構
:::
:::spoiler Violet 介面
:::

- Violet 是一個分散式的日曆系統
- 其背後用的檔案系統叫做 `DFS`，是一種 transactional file system
- Transactional File System 代表他是用 transaction (前面有提到)的方式在操作 data
- 其餘實作皆依照本篇演算法說明
- 他沒有說明 file suite 是對應到系統的甚麼東西，我猜是行程表

### lock 問題
- 假如使用的是未改進的鎖規則。B使用者原先正在讀，A使用者要寫東西進去，導致B使用者不能讀，且A使用者一直不 commit (write 上 lock)
- 如果用 time out 的方法解
- A使用者寫太久了，導致 time out
- A使用者沒寫成功，B使用者也過了很久才看到東西，且兩者的資料都是舊的
- 使用改進的鎖規則
- A使用者有意圖寫，I-Write 上 lock，但這並不阻止B使用者讀
- 直到A使用者寫完了，雖然commit 的短暫時間讓B暫時不能讀，但commit 完後，兩使用者皆呈現新資料

### 效能
- 展示兩組數據
- 讀/寫次數
- DFS 本身封包來回次數和 delay
- DFS 是採用 `three phase commit protocol`，因此針對一個操作，基本上會有 3 次 message 的來回
- 效能圖
- Begin Transaction: 整個 transaction 初始化
- Add Server: 將其餘 server 加入此 transaction 的過程，想成新增其他副本所在伺服器的成本。不太確定為什麼這邊是5
- Inquiries: 演算法的版本查詢，因為每個 representative 都查，因此讀 m 次，並有 3m 次的訊息傳遞
- Read (第一個 read): 因為前面已經做完版本查詢和候選人收集，因此直接讀取回傳最快的 representative，花費讀取一次
- Subsequent Read: 都花費一次讀取
- Subsequent Write: 前面有提到，要寫就要寫給每個最新版本的 quorum，因此每次寫都寫 m 次
- Coordinator: 結束 transaction 的初始化?
- Workers: 感覺是把原本操作在 buffer 的東西完整的寫進 file system，對每個 quorum 做一讀一寫，因此 3m+3m