# 3/22 SRE 讀書會共筆
---

場地提供：PIXNET
- 誠徵 [SRE 服務可靠度工程師](https://gist.github.com/jnlin/8329bea1c1ed92a1924da7e032304261)，有興趣的朋友可聯繫 [e-mail]

# 第23章管理關鍵狀態：利用分佈式共識來提高可靠性 by Jui-Nan Lin (PIXNET)

## 為何需要分散式系統？
- 服務可能會當機，或是需要維護而重開
- 資料中心可能遇到災害而離線
- 一個不夠就蓋兩個

## CAP 理論
- 三種特性不可能在分散式系統同時共存，只能滿足兩個
- 一致性 Constistency
- 可用性 Availability
- 分區容錯性 Partition tolerance
- Partition 發生時，資料會不一致
- Eventually consistency 通常在分散式系統的作法，在某一段時間之後資料就會一致
- 例如 FB 貼文的讚，每個人看到的讚數不會剛好相同
- CP 或 AP

## 分散式系統中需要釐清的問題
- 系統中，哪個行程是 Leader ?
- 系統中目前有哪些行程？
- 有哪些資訊已經被插入待處理的佇列中 => 一致性問題
- ..

## 分散式系統案例圖
- 每個 Process 只跟附近兩個鄰居節點連結
- 沒有相連的要傳遞資料只能透過鄰居轉送
- 當兩條路線掛掉時就會出問題，造成資料不一致

## ACID & BASE
- 傳統的 RDBMS 提供 ACID
- Atomicity 不可分割性
- Consistency 一致性
- Isolation 獨立性
- Durability 持久性
- 分散式資料庫提供 BASE
- BA (basically availibility) 基本可用 = 不保證你一定拿到最新的東西
- S, Soft state 軟狀態
- E, Eeventual consistency 最終一致性
- 受到 clock drift 或 network partition 影響，導致資料不正確
- 使用只支援 BASE 的資料庫寫程式是很困難的
- 資料一性的問題應該在資料庫層解決

## 常見的分散式系統協調失敗：叢集分裂 (腦裂)
- 常見的 Active-Standby 架構
- heartbeat 網路緩慢時會發生什麼事情？
- 發生兩個 Node 自認自己是 Active 的狀態
- PIXNET case study: DRBD 把兩邊資料串起來，就發生 split brain
-

- 不能使用簡單逾時的機制來實行領頭者選舉

## 常見的分散式系統協調失敗：需要人為介入
- 如果有問題就把 Standby 提升為 active
- 如果 standby 資料無法一致，就需要人工介入
- 若網路緩慢，會發生什麼事情？

## 常見的分散式系統協調失敗：有問題的演算法
- 每個節點啟動時，透過 discovery 方式，找到附近的 cluster 並加入
- 每個 cluster 選舉出一個 leader node
- 出現 partition 時，每個各自選出新的 leader node
- 造成 split brain 的資料損壞
- 需要一個演算法，實作「在訊息傳遞可能無線延遲的環境下實現非同步分散式一致化」
- 當機無法恢復與當機可以復原
- 拜占庭式問題 vs 非拜占庭式問題
- 電腦系統裡分散式問題
- 以前拜占庭的城邦，訊息需要傳令兵溝通，但可能中途會被殺掉或俘虜、收買，帶的訊息會遺失或被竄改，將軍們需要演算法確認大家對事情的看法
- 例如幾月幾號出兵攻打某地點，如果訊息被竄改或部分到達，演算法要能找出來真正的大家共識是什麼
- 比較難
- 非拜占庭式問題：保證中間訊息不被竄改，但可能會被延遲
- 比較簡單
- Paxos 協定
- Latex 作者發明的
- Paxos 協定
- 以「提案」為基礎
- 可能被接受或拒絕
- 提案有順序性（序號）
- 被大多數的行程接受的提案就成功， 即 2n+1 的 node 同意就成功
- 有些節點的權重可能比較高
- Proposer 發送提案給 acceptor
- 序號必須是唯一的，可以用 hostname 或 IP, MAC addr, etc.
- 如果 acceptor 已經接受更高序號的提案，就不能接受較低序號的提案
- 假設 R > J，C 接受了 R 的提案，就不能接受 J 的提案
- 解決的問題
- 順序性：解決系統中訊息排序問題
- 大多數同意：解決一個 Proposal 不能有兩個值
- e.g. 兩個行程同時提案
- e.g. 一個行程提了兩個一樣的案子，值不同
- 缺點：沒有一個節點可以完整檢視已經被接收的所有值

- 基於 Paxos 實作的分散式系統
- Google Chubby
- Zookeeper (使用衍生型，而非直接用 Paxos)

## Replicated State Machine 複製狀態機 RSM
- 架構在一致化演算法 (e.g. Paxos) 上
- 有限狀態機：在現行的電腦系統，所有的狀態都是有限的，每個狀態都是工程師定義出來，什麼樣的值會滿足此狀態而進入下一個狀態
- 電腦的所有控制邏輯都是用有限狀態機在執行的

## 領頭者選舉
- 寫一個程式，幫你選出 leader
- server 需要選 leader 的時候，就呼叫該程式，得到 leader ID
- server A 告訴程式自己是 leader，分散式系統就會紀錄 server A 是 ID

## Locking (以 Map-Reduce 為例)
- Map 做完才往 Reduce 丟
- 可以寫一個有限狀態機檢查所有的 Job 都完成才會進入下一個 Reduce 狀態，可以應用在撰寫 Locking 機制

## Message Queeue
- Worker 可以去使用有限狀態機達成 MQ 功能

## 分散式一致化系統的效能問題
- 實作比較慢，但還是有方法可以提高效能
- 系統負載的評估基準
- 單位時間提出 Proposal 的數量
- 請求類型
- 讀取資料的一致性要求
- 請求資料大小
- 提升效能的策略
- 局部佈署或是廣域佈署，例如靠近 client 端比較多
- 仲裁（同意）的過程，以及大部分行程分布的地理區域？
- 是否使用 sharing, pipeline 或 batching 方式處理？

## 複合式 Paxos (Multi-Paxos)
- 使用 strong leader 概念
- 系統只有一個提案者
- 避免多個提案者，造成提案成功率下降的問題
- 交替提案者時，很可能所有的提案都無法達到「大多數」
- 先選出 leader 提案者，接下來交給他
- 更換 leader 提案者的成本很高
- 可能出現 dueling proposers 狀況
- 衍生：raft

## 改善讀取的效能
- 如果不需要強一致性，資料就可以從「任意」的副本讀取
- 例如 Google Photon 系統，過期資料只會造成「額外工作」，而非錯誤結果
- 如果要保障讀取的資料是最新的
- 進行一致的唯讀操作
- 不給寫入，那當然是最新的！
- 從一個保證有最新資料的副本讀取，例如 leader node
- 使用法定租約 (quorem lease) 協定，用寫入效能換取效能
- 在有效期間內，對資料的修改操作，必須得到租約內所有行程的成功回應
- 租約通常很短，一秒, 兩秒, 十秒等等
- 租約的時間內，寫入效率會降低
- 如果資料大量集中在某些地理區域，法定租約很有用
- 使用者都在台灣，資料放在台灣，可是備份放到日本，可以把租約限制在台灣 node，寫入就會很快，就可以保證在台灣讀取的資料都是新的

## 分散式系統網路延遲問題
- RTT, Round-Trip Time ; 理想上越低越好
- TCP/IP 的三項握手問題
- 使用 Proxy 來降低連線成本
- 只需要一兩個連線

## Fast Paxos
- 希望最佳化 Paxos 在 WAN 的效能
- 不要有提案者架構，直接讓 client 發訊息給 acceptor
- 少了提案者這個中間人
- 少一個節點自然整個效率提升
- 反例：原本是 proxy，現在變成直接連，連線變多有可能導致效能變差

## Stable Leaders
- Raft 演算法
- 優點：leader 有最新的資料，可以優化讀取效率
- 缺點：Leader 是效能瓶頸
- 距離比較遠的使用者會有網路延遲問題
- 對外頻寬也會影響處理能力

## 批次處理
- 一個提案者處理好幾個請求
- 中間沒有相依性的提案者可以多個同時進行

## 磁碟存取
- 延遲的操作行為
- Proposer 寫入硬碟的操作
- Proposer 傳輸到 acceptors 的延遲
- acceptors 寫入硬碟
- 回復訊息的操作
- 可以算出每秒鐘的吞吐量
- 若一次 Random Write 10ms，則每秒鐘最多就 100 次操作
- RSM 的日誌可以和分散式演算法的日誌一起寫入

## 佈署：副本數量
- 通常採取 2N + 1 佈署
當 N 個副本 lose，需要介入處理

## 佈署：副本數量的選擇策略
- 愈多不一定越可靠
- 對可考性的要求
- 計畫內維護操作的頻率
...

## 佈署：地理位置
- 系統需要處理的故障區域數量
- 故障的時候還要保證系統可以正常存取
- 系統的延遲性要求

## 地理位置：故障域
- 案例：颱風橫掃美東，讓 AWS 機房掛掉
- 可能故障的範圍
- 實體機器
一個機櫃內實體機器共用的設施，例如電力

- 不一定要增加更多的故障域

## 地理位置： 延遲性要求＆災難回復
- 光速是固定的，沒有任何傳輸方法更快
- 使用者的地理位置很重要，決定故障域放哪
- 不是所有服務都需要低延遲或高流量，例如 IoT log
- 真的需要加一個節點在靠近使用者的地方嗎？不一定
- 選擇地理位置時，也要考慮災難回復的處理
- 災難可能是因為軟體 bug 或人為疏失

## 容量規劃
- 增加副本可以增加系統可承載數量
- 反例：五個副本一定要有三個可以用，最多可達到 40% rate，六個副本降低到 33% fail rate
- 採用法定仲裁的系統在
- 副本所在的資料中心，也會影響可用性
- 例如六個副本，五個資料中心

## 負載平衡
- 如果用戶集中在某個區域，把副本放在離用戶近的地方
- 但不能總是找最近的，因為過載時可能發生連鎖反應
- 解法可能需要切區域，一部分使用者導到稍微遠的區域
- leader 放在同一個地區可能造成頻寬瓶頸
- leader 故障時，可能造成資料中心頻寬不足
- 地理位置分布，對效能會有影響，主要是 RTT 造成
- 故障時 RTT 大幅增加
- 層級副本可以減少對中央的依賴

## 監控分散式一致化系統
- 每個群組裡面的節點數量與健康狀態
- 持續落後的副本
- leader note 是否存在以及他改變的次數
- 交易的次數，可以算出吞吐量
- 提案者的數量，如果提出多接受少表示有效能問題
- 流量與延遲

## 小結
- 標準的分而治之解決方案
- 大問題切小塊，解掉後再架一層上去

# 第24章分佈式週期性任務系統 by Luke Liu

## introduction
- 定期週期被執行的指令
- 指令被存在 crontab 檔案
- crond daemon 分鐘檢查是否有預定的作業需要執行

## 可靠度
- anacron
- 檢測相關的排程有沒有被執行，如果超過期限的工作在，就執行該排程任務

## Cron jobs and idempotency
- 是否可以多次執行？
- 跳過一次是否可以？
- Google 傾向最差狀況跳過一次，而不執行多次任務
- 對資料敏感度高不高，例如漏掉一天的資料對伺服器有無影響，如果沒有可能可以接受，如果不能接受怎麼處理？
- 例如手動回補資料
- 會跳過一次一定是有些問題，去看 log 找問題，而盡量不要執行多次
- 擁有者需監控任務的執行結果

## Cron at large scale at Google
- 擴充基礎建設
- job 從機器中隔離出來
- 執行任務，只需要指定需要的系統資源即可
- 分發系統會決定任務在哪些機器跑，例如不會分配到忙碌的機器
- 擴充需求
- 系統資源隔離，每個任務執行不會影響到其他任務
- 建立副本，避免單台機器故障，導致任務無法執行

## Building Cron at Google
- Tracking the state of cron jobs
- cron 任務訊息，存在外部裝置，比較舊的存在別的地方像是 Hadoop
- 本地端只存小量的任務訊息，Google 選擇的作法

## the leader
- 負責管理任務
- 紀錄任務的時間戳記
- 同步任務訊息 (副本) 給 follower
- leader 掛了 follower 就可以馬上接手

## the follower
- 與 header 同步任務與系統狀態
- header 故障，follow 必須在一分鐘內選出新的 leader
- 當新的 header 被選出來，所有還沒完成的任務都不需結束
- 同步的時間點：任務執行之前與之後

## Resolving partial failures
- 任務的執行多次結果都必須一樣，以便新的 header 選出後，可以重新執行
- 外部查詢，任務是否外部查詢，任務是否成功

## Storing the state
- Google 藉由寫 log 來同步任務狀態，衍生出兩個問題
1. log 必須定期壓縮，避免無限成長
只存最後一筆的狀態

2. log 必須存在某個地方

## Running large cron
- 避免同一時間大家同時跑，會搶資源，導致系統資源不足
- 在 cron 中使用問號「？」來增加系統彈性，今天跑無論是幾點跑都沒差，增加系統彈性