第八章：分散式系統的麻煩：學習要點

[Jay0328]

The Trouble with Distributed Systems

沒有什麼可以相信的，這世界沒救了，人生好難

Unreliable Networks

• 如果你想確保一個 request 是成功的，你需要應用程式本身的正確 response
• Timeout 等待時間
  • 長
    • cons
      • 等待時間較長
  • 短
    • props
      • 快速地檢測到故障
    • cons
      • 更高的風險誤將一個 node 宣告死亡
      • 可能導致由另一個 node 接管而使動作被執行多次
      • 如果系統已處於高負荷狀態，可能導致 cascading failure (級聯失效)
  • 更好的一種做法是，系統不是使用配置好的常量 timeout，而是連續測量 response time 及其變化，並根據分佈結果自動調整 timeout

Unreliable Clocks

每臺機器都有自己的時間概念，可能比其他機器稍快或更慢

NTP (網路時間協議)，根據一組伺服器報告的時間來調整計算機時鐘

Clock Type

• time-of-day clock (日曆時鐘)
  • Unix Timestamp
  • Linux，clock_gettime(CLOCK_REALTIME)
  • Java，System.currentTimeMillis()
  • 需要根據 NTP server 或其他外部時間源來設定才能有用
  • 如果 local clock 跟 NTP server 差太多則會被強制重置，這些跳躍以及他們經常忽略閏秒的事實，使日曆時鐘不能用於測量經過時間 (elapsed time)
• monotonic clock (單調鐘)
  • Linux，clock_gettime(CLOCK_MONOTONIC)
  • Java，System.nanoTime()
  • 總是往前走
  • 絕對值是毫無意義的，它可能是計算機啟動以來的納秒數，或類似的任意值
  • 不需要 synchronize
• logic clock (邏輯時鐘)
  • 基於 increment counter 而不是振盪石英晶體

Synchronize Clock

• Clock 存在信賴區間
• 必須仔細監控所有機器之間的 clock 偏移。偏離其他太遠的 node 應當被宣告死亡，並從 cluster 中移除。這樣的監控可以確保你在損失發生之前注意到

System Pause

Distributed system 中的 node，必須假定其執行可能在任意時刻暫停相當長的時間，即使是在一個 function 的中間。在暫停期間，世界的其它部分在繼續運轉，甚至可能因為該 node 沒有響應，而宣告其死亡。最終被暫停的 node 可能會繼續執行，在再次檢查自己的 clock 之前，甚至可能不會意識到自己進入了睡眠。

Knowledge, Truth, and Lies

在 distributed system 中，我們可以陳述關於行為（系統模型）的假設，並以滿足這些假設的方式設計實際系統

許多 distributed algorithm 都依賴於法定人數，即在 nodes 之間進行投票：決策需要來自多個 nodes 的最小投票數，以減少對於某個特定 node 的依賴。這也包括關於宣告 node 死亡的決定。如果法定數量的 nodes 宣告另一個 node已經死亡，那麼即使該 node 仍感覺自己活著，它也必須被認為是死的，必須遵守法定決定並下臺。

Truth Defined by Most

Leader and Lock

即使一個 node 認為它是 "天選者（the choosen one）"，ex. lock 的持有者，但這並不一定意味著有法定人數的 nodes 同意！一個 node 可能以前是領導者，但是如果其他 nodes 在此期間宣佈它死亡（例如，由於網路中斷或 GC 暫停），則它可能已被降級，且另一個領導者可能已經當選

client 1 get lock
-> client1 get into gc
-> client 1 lock expired
-> client 2 get lock
-> client 2 write data
-> client 1 wake up and write (will break the system)

Fencing

我們假設每次鎖定 server 授予 lock 或租約時，它還會返回一個 fencing token，這個數字在每次授予鎖定時都會增加（例如，由鎖定服務增加）。然後，我們可以要求 client 每次向 storage service 傳送 write request 時，都必須包含當前的 token。

client 1 get lock ( token 33 )
-> client1 get into gc
-> client 1 lock expired
-> client 2 get lock ( token 34 )
-> client 2 write data
-> client 1 wake up and write but fail since 33 < 34

Byzantine Fault

如果存在 node 可能 “撒謊”（傳送任意錯誤或損壞的響應）的風險，則 distributed system 的問題變得更困難了，例如，如果節點可能聲稱其實際上沒有收到特定的訊息

Byzantine fault-tolerant (拜占庭容錯)，當一個系統在部分 nodes 發生故障、不遵守協議、甚至惡意攻擊、擾亂網路時仍然能繼續正確工作

在 web service 中通常可以安全地假設沒有拜占庭式的錯誤

System Model

Time

• synchronous model
  • 假設 network latency、system pause 和 clock error 都是受限的
  • 做夢
• partial synchronous
  • 意味著一個系統在大多數情況下像一個 synchronous model 一樣執行，但有時候會超出界限
  • 較符合現實
• asynchronous model
  • 在這個模型中，一個演算法不允許對時序做任何假設

Node Failure

• crash-stop
  • node 可能在任意時刻突然停止響應，此後永遠消失
• crash-recovery
  • node 具有穩定的儲存(非易失性磁碟儲存)且會在崩潰中保留，而 memory 中的狀態會丟失
• byzantine fault

[AK4codee]

不可靠的網路

如果你傳送請求並期待響應，則很多事情可能會出錯:

• 請求可能已經丟失（可能有人拔掉了網線）。
• 請求可能正在排隊，稍後將交付（也許網路或接收方過載）。
• 遠端節點可能已經失效（可能是崩潰或關機）。
• 遠端節點可能暫時停止了響應（可能會遇到長時間的垃圾回收暫停。
• 遠端節點可能已經處理了請求，但是網路上的響應已經丟失（可能是網路交換機配置錯誤）。
• 遠端節點可能已經處理了請求，但是響應已經被延遲，並且稍後將被傳遞（可能是網路或者你自己的機器過載）。

處理這個問題的通常方法是 超時（Timeout）：在一段時間之後放棄等待，並且認為響應不會到達。但是，當發生超時時，你仍然不知道遠端節點是否收到了請求。

檢測故障

何時需要自動檢測故障節點

• 負載平衡器需要停止向已死亡的節點轉發請求
• 在單主複製功能的分散式資料庫中，如果主庫失效，則需要將從庫之一升級為新主庫

不可靠的時鐘

日曆時鐘

• 日曆時鐘通常與 NTP 同步，這意味著來自一臺機器的時間戳（理想情況下）與另一臺機器上的時間戳相同。
• 根據某個日曆（也稱為 掛鐘時間，即 wall-clock time）返回當前日期和時間。

單調鍾

• 單調鍾適用於測量持續時間（時間間隔）
• 可以在某個時間點檢查單調鐘的值，做一些事情，且稍後再次檢查它。這兩個值之間的差異告訴你兩次檢查之間經過了多長時間。

有序事件的時間戳

邏輯時鐘（logic clock）是基於遞增計數器而不是振盪石英晶體，對於排序事件來說是更安全的選擇。邏輯時鐘不測量一天中的時間或經過的秒數，而僅測量事件的相對順序（無論一個事件發生在另一個事件之前還是之後）。

不可靠的知識與真相

領導者和鎖

• 資料庫分割槽的領導者只能有一個節點，以避免 腦裂
• 特定資源的鎖或物件只允許一個事務 / 客戶端持有，以防同時寫入和損壞。
• 一個特定的使用者名稱只能被一個使用者所註冊，因為使用者名稱必須唯一標識一個使用者。

[jxiu0129]

不可靠的網路

• 超時與無窮延遲

不可靠的時鐘

• 單調鐘 與 日曆時鐘
• 同步時鐘

拜占庭故障

• 當一個系統在部分節點發生故障、不遵守協議、甚至惡意攻擊、擾亂網路時仍然能繼續正確工作，稱之為 拜占庭容錯

[at7211]

• 如何確保可靠的網路狀態→ 幾乎不可行
  Currently deployed technology does not allow us to make any guarantees about delays or reliability of the network
  第八章：Makes Network More Reliable - Jay Chou #92
• 確保不同 node 的時間要趨於一致的方式
  →每隔一個時間去做跟主要的 node 同步
• 不同 node 可能欺騙/故障等可能性，但再一定容忍範圍和投票機制下，依然可以驅使系統繼續運行 → 拜占庭容錯

[0x171-0]

故障與部分失效

• 單體機、超級電腦 處理錯誤的方式會將部分失效升級成完全失效
  • 原因：
  • 因為不像 Cloud Computing 需要一直保持 online
  • 因為不能接受錯誤的回傳結果，所以寧願完全失效
• 分散式系統之所以難以實現的原因就在於 因為 nondeterministic、unpredictably fail，所以我們需要容錯機制：基於不可靠的組件，構建可靠的系統

Unreliable Networks

Asynchronous packet networks 的網路錯誤

• 無回應的可能
  • the request was lost or delay (queue 排太長)
  • The remote node is down
  • the respose was lost or delay
• 無回應的應對：timeout
  • reasonable timeout = 2d + r
  • 只係系統暫時變慢但是判斷 timeout 會造成什麼影響
    • 某些任務重複執行
    • 其他節點職責加重
    • TCP 可以自動監測 response time 動態調整 timeout 時間
• 建立自動檢測故障機制
• delay 的原因：在 switch、虛擬機、作業系統排隊太長，或 受限 TCP 流量控制

電路交換 circuit switching VS 封包交換 packet switching

• 電路交換
  • 固定分配頻寬，有浪費的問題
  • 不會有排隊過長的問題
  • 最大延遲固定 bounded delay
• 封包交換
• 不固定分配頻寬，可以極大化使用頻寬，沒有浪費的問題
• 有排隊過長的問題
• 延遲時間不固定

Unreliable Clocks

兩種時間

• durations
• point in time

兩種時間

• Time-of-days clocks
  • 單純回傳現在的日期、時間（wall-clock time)
  • 通常與 NTP 同步
  • 存在時間回跳的問題
• Monotonic clocks
  • 適用於量側時間
  • 沒有時間回跳問題
  • 不需要與 NTP 同步時間，但是 NTP 可以調整之前走的頻率

依賴同步時間

• 有序事件的時間戳

• 物理時鐘 vs 邏輯時鐘

• 時間置信區間：與 NTP 同步的精度飄移

• LWW 的問題

  • 每台機器的物理時間不同，導致時間較新的也可能是較舊發生的，時間無法反映先後順序、違背因果關係
  • 解法：使用邏輯時鐘，ex: 利用計數器額外追蹤因果關係
  • 如何處理時間戳相同？
  • 解法：使用 決勝值 tiebreaker 可能是簡單的隨機數，所以這方法可能違背因果關係

• 全局快照的同步時鐘

  • 利用置信區間實現快照
  • 提交前等待置信區間的長度

求真的方法

• 節點故障： 半斷開（semi-disconnected）

  • reponse 被惡意攔截
  • 因為 GC 造成所有線程被強佔、回應遲緩

• 退休的領導這：

  • 重複鎖：退休的領導者跟新的領導者可能同時拿到主控鎖
  • 解法：防護令牌 fencing token，每次授予鎖都會遞增，像 client 得請求都包含令牌， client 只接受後令牌的請求

• 拜占庭將軍問題

• 拜占庭故障：節點存在撒謊風險

• 拜占庭容錯：面對部分失效依然可以正常運作

• 安全性和活性

  • 安全性
    • 唯一性、單調序列
    • 沒有壞事發生
    • 需要始終保持
  • 活性
    • 可用性
    • 最終好事發生
    • 最終達成即可

[JimmyFUFU]

• 不可靠的網路
  • 真實世界網路故障 : application 需要知道如何解決網路斷線問題
  • 檢測故障 : 判斷某個節點是否還有在正常工作，如果是故障的狀態需要做什麼處理
  • 超時與無窮的延遲 : 通常會設定一個 timeout 的時間，但訂定一個合理的 timeout 也是課題之一，過短可能會造成系統部必要的負擔，故障檢測延遲 與 過早超時風險 之間的適當折衷
• 不可靠的時鐘
  • 單調鐘與日曆時鐘 :
    • 單調鐘 : 相對，測量經過時間 elapsed time
    • 日曆時鐘 : 絕對
  • 時鐘同步與準確性 : 分散式系統中各台機器的日曆時鐘是需要透過 NTP 同步的，可能因為drifts or smearing 或是 NTP 通訊不正常造成時間不正確
  • 依賴同步時鐘 : 因為 Last write win 這個解決衝突的策略，而且保留最近寫入的值是取決於當台機器本地的日曆時鐘，所以我們必須同步多台機器的時間戳
• 拜占庭故障 : 節點存在說謊的風險
• 拜占庭容錯 : 在部分節點失效時仍然可以正常工作

[samwu4166]

• 我們很難知道丟失的網路封包到底是因為哪種原因 (過去不見, 沒有回應, 回來不見)
• 我們沒辦法阻止節點延宕或意外掛掉，只能盡量做自動檢測跟失效處理
• 拜占庭故障 - 節點存在預期之外的事情 (允許說謊, 被駭)
• 拜占庭容錯 - 允許某些節點自己做自己的事情 (失效容錯)
• RTOS - 允許在指定時間內保證 CPU 分配時間，且函示庫必須註明最壞情況的執行時間

實時系統在 Embedded system & Web 有完全不同的解釋，前者是在精心設計和測試下對全系統的保證，後者比較沒有嚴格的響應時間 (也沒辦法)

描述分布式系統時序假設的系統模型:

• 同步模型 - 假設可以知道所有網路延遲, 進程暫停 & 時鐘誤差的範圍跟上限
• 部分同步模型 - 大部分像一個同步系統一樣, 但必須承認會有無限延遲的問題存在
• 異步模型 - 沒有時鐘也不需要假設時序

[taco0929]

不可靠的網路

• 需要假設網路會出錯
  • 自動檢測故障節點
  • 轉發請求
  • 超時與延遲
• 不能太快宣告節點死亡
  • 若節點還活著則同樣動作可能會執行兩次
  • 高負荷系統下轉移節點任務給其他節點容易使系統失衡
• 同步網路與異步網路
  • 固定延遲vs不固定延遲
  • TCP為了有效利用資源，將產生不可預期（可變的）的延遲

  不可靠的時鐘

  • 單調鐘：計算間隔時間
  • NTP可以偏移單調鐘，使時鐘變快或變慢
• 有序時間戳
  • LWW策略被混淆
  • 時鐘讀數存在置信區間
• 進程暫停
  • 租約：領導者向其他節點申請有限時間的租約
    • 暫停
    • GC
    • 虛擬機掛起與恢復
    • 線程切換
• 多數決
• 拜占庭將軍問題