Please enable JavaScript.
Coggle requires JavaScript to display documents.
DDIA - Coggle Diagram
DDIA
Replication
Single-leader
Multi-leader
併發修改
後寫者贏 (Last write wins): 容易丟失資料
避免衝突 (目前所有實作效果都不好)
自訂解決衝突邏輯
寫入時執行: Bucardo 支援,必須快速執行完
讀取時執行: 把所有寫入存起來,讀取時傳給應用層自己解決
只適用於單筆資料
定義並發性
同時發生 != 並發,因為 clock skew
並發 = 兩個操作沒有因果關係
拓樸
環狀
星狀
All-to-all
Leaderless
Aka Dynamo-style (不是 DynamoDB),為了最終一致性而設計
不存在 failover
寫入/讀取都並發傳給所有副本,只要大部分成功就視為成功
寫入失敗
讀取時檢測並修復
反熵程序: 在背景不斷查找跟其他副本的差異,找到差異時可能過一陣子了
以上兩者都沒有,就失去了 Durability 保證
法定票數演算 Quorums
w + r > n: 讀取的資料至少有一份是最新的,因為讀跟寫必定有一個重複
w 跟 r 只是用來調整讀到舊值的機率
Sloppy quorum
Hinted handoff
Synchronous
在等待副本完成同步之前,leader 會阻塞所有的寫入請求
Asynchronous
最終一致性 Eventually consistency
被廣泛採用
Replication log
必須是 Deterministic
Log sequence number: 用來建立新的 Follower
Write-ahead log
Row-based logical log (跟底層細節脫鉤,有利相容性,便於CDC分析)
Trigger-based
Leader-based replication
Leader failover
重新設定系統以讓 leader 生效
可能遇到腦分裂 (Brain split)
如果跟其他儲存系統協作,可能丟失資料,產生不一致
判斷 leader 失效
選出新 leader
會遇到單點失效
複製落後
先讀到後發生的資料,才讀到先發生的資料 (單分區)
單調讀取 (Monotonic reads): 確保每個使用者從相同副本讀取資料
同步未完成,使用者以為剛提交的資料遺失
讀己所寫 (Read your writes): 從 leader 讀取最新資料,但可能會抵消擴展性的好處
先讀到後發生的資料,才讀到先發生的資料 (多分區)
一致性前綴讀取 (consistent prefix reads)
主因: 各分區獨立運行,寫入沒有全域的順序
版本向量 (Version vectors)
Partition / Sharding
分區不均勻 (skewed)
hotspot
Hash-based partition
一致性雜湊 Consistent hasing
範圍查詢效率差
Range-based partition
範圍查詢效率佳
可能產生 hotspot,可以同其他欄位決定分區
Cassandra 的折衷方案: 複合主鍵 (compund primary key),第一部分做 hash-based,第二部分做 range-based
次索引 (Secondary index)
Local index
查詢得發送到所有分區
Aka Document-partitioned index
Global index
Aka Term-partitioned index
只需向包含 term 的分區查詢
非同步更新
寫入效率慢
再平衡策略
mod N
再平衡時要移動一堆 keys
固定分區數量
再平衡時只需移動一些分區
更強的節點可以負擔更多分區
難選擇適當的分區數量
動態分區
按節點比例進行分區
自動再平衡搭配自動故障檢測有風險
請求路由
追蹤節點變化
依賴於協調服務
Apache ZooKeeper / MongoDB Config Server
Gossip protocol
Cassandra
路由層
Couchbase moxi
做出路由決策的元件,可能是節點之一、路由層或客戶端
分散式系統的問題
網路不可靠
檢測故障
網路的不確定性導致很難判斷一個節點是否正常運作
過早宣布節點失效會帶來問題
網路壅塞
交換器佇列
OS佇列
TCP 壅塞控制 / back pressure
時間不可靠
生活時鐘
單調時鐘
總是向前移動,檢測差值可知道時間過了多久
每個電腦/CPU的設計不一樣
NTP可以做時鐘調速
不準確,會產生飄移 drift
導致 LWW 搞錯資料寫入順序
信賴區間
NTP 可以根據 round-trip time 計算
Google spanner True time API
程序中斷
垃圾回收導致 Stop the world
虛擬機器可以被 suspend
執行緒因硬碟存取而暫停
網路磁碟如 Amazon EBS 會加劇這種情況
OS 開啟分業機制時時可能花很多時間做 Swap
UNIX SIGSTOP/SIGCONT
回應時間保證? RTOS
節點不一定相信自己的判斷,真相由多數說了算
Quorum
Fencing token
是有租期的鎖,通常是遞增的值
用來防止過期的 leader 寫入
範例: zookeeper zxid
拜占庭故障: 節點說謊
拜占庭將軍問題: 在不信任的環境達成一致性
系統模型
timing
部分同步
非同步
同步
節點失效
崩潰後恢復
拜占庭任意故障
崩潰即停止
活躍性: 請求終究會被完成
安全性: 違反安全性,會造成破壞,但能指出誰造成破壞
Transaction
ACID
A
在交易時發生失敗,回滾所有寫入
C
資料正確性,不是資料庫要保證的
I
每一個交易都能假設自己是唯一一個執行中的交易,就像是一次執行一個交易,因此也被稱為可序列化
D
交易完成後,資料就不會流失
沒有任何技術能提供絕對的保證,但有很多降低風險的手段
單物件交易
A 實作: 支援從崩潰恢復的日誌
I 實作: 對每個物件加鎖
交易中止是為了安全重試而存在的
隔離級別
讀已提交 Read Commited
無髒讀
實作: Row-level locks
不會讀取到其他交易寫到一半的資料
無髒寫
不能覆蓋進行中交易的寫入
資料庫會記住舊值,交易提交後,其他交易才會讀到新值
快照隔離 Snapshot isloation
處理什麼
讀取偏斜 Read skew
只是暫時問題,再次讀取就好了
無法接受的情況:備份、分析查詢
Aka 不可重複讀取 non-repeatable read
讀方不會阻塞寫方,寫方不會阻塞讀方
實作: MVCC
每一列都有 created_by、deleted_by 紀錄 txid
一致快照:忽略進行中、已中止、後到的 txid
可序列化 Serializable
處理什麼
更新丟失 (lost update)
兩個交易同時讀取某個值、修改、寫入(read-modify-write cycle),其中一邊會遺失
解法1: 部分資料庫提供原子操作,有得用就該用
解法2: 顯式加鎖 (SELECT FOR UPDATE)
解法3: 自動檢測更新丟失
解法4: atomic compare-and-set,但如果從舊快照讀取資料,就沒辦法防止
解法5: (for multi-leader or lederless): 同時寫入多個兄弟值(siblings)再合併,但只適用於某些操作
寫入偏斜 (Write skew): 並發交易
解法1: 顯式加鎖 (SELECT FOR UPDATE)
案例
值班醫生同時點休假鈕
會議室預約系統避免重複預約
查詢沒有傳回任何列,SELECT FOR UPDATE 沒有任何東西可以加鎖
解法1: 實體化衝突 (materializing conflicts): 手動建立每一個可預約時段,對他們做 SELECT FOR UPDATE
解法2: 述詞鎖 (Predicate lock),但性能很差
幻讀: 在一個交易中,兩次查詢的結果不一樣,因為有資料被新增或刪除了
實作
嚴格循序執行交易
單執行序執行
案例: Redis
預存程序 (Stored procedure): 事先把交易程式碼提交給資料庫,以避免任何網路、磁碟 I/O,但不好管理
跨分區交易比單分區交易慢很多
兩階段加鎖 2PL
先持有鎖、完成交易、放掉鎖
讀取之前需要取得共享鎖 (Shared lock)
寫入之前需要取得互斥鎖 (Exclusive lock)
會發生 deadlock,但資料庫大多會檢測死鎖並中止被影響的交易
延遲很不穩定
會使用簡化版述詞鎖,稱為索引範圍鎖定 (index-range locking / next-key locking)
悲觀鎖
可序列化快照隔離 (SSI)
樂觀鎖
假設: 基於過時的前提並採取行動的交易
檢測在讀取之前發生未提交的寫入
檢測讀取之後,又發生了新的寫入
唯獨查詢不需要任何鎖,效率很好
一致性與共識
一致性保證
可線性化
場景
加鎖、領導者選舉
唯一性約束
可線性化儲存服務
實作
共識演算法 (可線性化)
Single-leader (有潛力)
Leaderless (不可線性化,除非執行讀取修復)
Multi-leader (不可線性化)
可線性化一定會拖慢速度
全序,不存在並發操作,但總是正確的保持因果關係
因果一致
偏序
效能比較好
序號(邏輯時鐘),提供全序
比如 Single-leader replication 的 log sequence
Lamport timestamp
(counter, node ID)
每個節點和客戶端都跟蹤自己看到的最大計數值,並在每個請求都附上
無法判斷兩個操作是並發還是因果依賴
全序廣播 (total order broadcast)
訊息會被傳到所有節點
總是以相同的順序傳遞
可以藉此實現可序列化交易、可線性化儲存
可視為建立日誌的方式
共識
兩階段提交 2PC
單節點交易的成功與否取決於是否成功把提交紀錄寫入硬碟
Coordinator 向參與者發送 prepare,若所有參與者回傳 yes,coordinator 在自己硬碟紀錄交易成功,並向所有參與者發送 commit。
參與者崩潰的話,重開後可以自己查詢,或者收到來自 coordinator 的重試訊息
Coordinator 崩潰的話,所有參與者進入 in doubt 狀態,值到 coordinator 恢復
效能差
可能導致 server 變成 stateful,或必須手動處理交易
支援容錯的共識
完整性 Integrity
有終性 Termination
合法性 Validity
共識演算法
相比 2PC,只要大部分節點投票通過就行
網路分裂時,具有大部分節點的那部分可繼續運行
對網路特別敏感