3/22 SRE 讀書會共筆

場地提供：PIXNET

• 誠徵 SRE 服務可靠度工程師，有興趣的朋友可聯繫 applyjob@pixnet.tw

第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 中使用問號「？」來增加系統彈性，今天跑無論是幾點跑都沒差，增加系統彈性