第三章：交易處理 學習要點

[adrian-lin-1-0-0]

事務處理

手段

• Atomic
• Isolation
• Durability

結果

• Consistency

Consistency

• 內部一致性
• 外部一致性

Local Transaction

ARIES(Algorithms for Recovery and Isolation Exploiting Semantics)

• Oracle
• MS SQL Server
• MySQL/InnoDB
• IBM DB2
• PostgreSQL

實現原子性和持久性

Crash Recovery (Failure Recovery /Transaction Recovery)

Commit Logging

1. Commit Record
2. End Record

Shadow Paging

1. 複製副本
2. 修改副本
3. 修改指針指向副本

Commit Logging vs Write-Ahead Logging

Commit Logging

• Force/No-Force
• No-Steal

Write-Ahead Logging

• Force/No-Force
• Steal/No-Steal

Undo Log

1. Analysis
2. Redo
3. Undo

實現隔離性

• Write Lock
• Read Lock
• Range Lock

  SELECT * FROM books WHERE price < 100 FOR UPDATE;

Isolation level

• Dirty Read isolation The Dirty Read isolation (or ANSI Read Uncommitted) level does not place any locks on any rows fetched during a SELECT statement. Dirty Read isolation is appropriate for static tables that are used for queries.
• Committed Read isolation A reader with the Committed Read isolation (or ANSI Read Committed) isolation level checks for locks before returning a row. By checking for locks, the reader cannot return any uncommitted rows.
• Cursor Stability isolation A reader with Cursor Stability isolation acquires a shared lock on the row that is currently fetched. This action assures that no other user can update the row until the user fetches a new row.
• Repeatable Read isolation Repeatable Read isolation (ANSI Serializable and ANSI Repeatable Read) is the strictest isolation level. With Repeatable Read, the database server locks all rows examined (not just fetched) for the duration of the transaction.

Global Transaction

事務提交

2PC(2 Phase Commit)

前提 必須假設網路在提交階段的短時間內是可靠的，即提交階段不會遺失訊息。同時也假設網路通訊在整個過程中都不會出現誤差，也就是可以遺失訊息，但不會傳遞錯誤的訊息，XA 的設計目標並不是解決諸如拜占庭將軍一類的問題。兩段式提交中投票階段失敗了可以補救（回滾），而提交階段失敗了無法補救（不再改變提交或回滾的結果，只能等崩潰的節點重新恢復），因而此階段耗時應盡可能短，這也是為了盡量控製網路風險的考量。 必須假設因為網路分區、機器崩潰或其他原因而導致失聯的節點最終能夠恢復，不會永久地處於失聯狀態。由於在準備階段已經寫入了完整的重做日誌，所以當失聯機器一旦恢復，就能夠從日誌中找出已準備妥當但並未提交的事務數據，並向協調者查詢該事務的狀態，確定下一步應該進行提交還是回滾操作。

• 準備階段
• 提交階段

缺點

• 單點問題
• 效能問題
• 一致性風險

3PC(3 Phase Commit)

Share Transaction

Distributed Transaction

CAP x ACID

• Consistency
• Availability
• Partition Tolerance

可靠事件隊列

TCC (Try-Confirm-Cancel)

• Try
• Confirm
• Cancel

SAGA

補充

• Blocking Retry
• Using Queues to Process Asynchronously in the Background
• Local Message Table (Asynchronously Ensured/Outbox Pattern)
• MQ Transaction
• Event Sourcing
• CQRS(Command Query Responsibility Segregation)
• Atomic Commitment
• Parallel Commits
• Transactional Replication
• Consensus Algorithms
• Timestamp Ordering
• Optimistic Concurrency Control
• BFT(Byzantine Fault Tolerance)
• Distributed Locking
• Sharding
• MVCC(Multi-Version Concurrency Control)
• Distributed Snapshots
• Leader-Follower Replication

[emily40830]

這週細節有夠多，WAL 那段可能還需要額外的內容，覺得光書中的內容還少了一些上下文跟 context ＠＠ Ch3. 交易處理 Transaction(TX)

[HuaYuan-Tseng]

筆記 Link: Link 這週真滴猛烈 0.0

[shihgangliu]

• 事務是為了保證數據的 ACID：
  1. A(Atomic)：同一項業務的多個數據處理要同時成功或同時撤銷。
  2. C(Consistency)：數據的一致性。
  3. I(Isolation)：保證各個業務間處理的數據彼此獨立互不影響。
  4. D(Dutability)：保證被提交的數據都能正確的持久化不遺失。
• 外部一致性很難用 ACID 解決，而必須將 consistency 依不同代價去劃分不同強度。
• 本地事務：單個服務使用單個數據源的場景，依賴數據源本身的事務處理。其中原理可追朔到 ARIES。
  • 實現原子性與持久性：由於崩潰是無法避免的，所以後續的補救措施叫「崩潰恢復」，目前有 Commit Logging、Shadow Paging 兩種常見方式。
  • 未提交事務，寫入後崩潰：某些數據已經寫入硬碟但此時崩潰，重啟後必須將以修改的數據恢復成原本的樣子，以保證原子性。
  • 已提交事務，寫入前崩潰：變動的數據都已提交但尚未寫入永久性硬碟前崩潰， 重啟後必須將這些已提交的數據寫入硬碟，以確保一致性。
  • 因為 Commit Logging 需要等提交才會一次寫入磁碟，性能不佳才有 WAL 的解決方案。
  • Write Ahead Logging 分為 FORCE、STEAL。Commit Logging is NO-FORCE but is not STEAL。WAL 允許 NO-FORCE 也允許 STEAL，解法是 Undo Log（回滾日誌）和 Redo Log（重做日誌），且都必須確保幂等性。
  • WAL 根據 Undo Log 在崩潰重啟後會執行三階段操作：
    1. Analysis：從 Checkpoint 找出所有沒有 End Record 的事務。
    2. Redo：根據分析完後待恢復的數據中重演歷史，找出所有 Commit Record 數據寫入磁盤。
    3. Undo：前兩階段完剩餘的恢復數據改寫回去。
  • 實現隔離性：加鎖可以快速達成目的，且串行化(Serializable)是最高的隔離層級。
  • 三種鎖類別：
    1. 寫鎖(X-Lock)：只有拿到鎖的人可以操作資源。
    2. 讀所(S-Lock)：其他沒有拿到鎖的不能寫入可以讀取。
    3. 範圍鎖(Range Lock)：對某個範圍下排他鎖。
  • 四種隔離級別：
    1. Serializable：最高級別，但是效能不好。
    2. Repeatable Read：不加上範圍鎖，所以有幻讀的可能。
    3. Read Committed：讀鎖不再等到事務結束釋放，而是查詢完馬上釋放，所以有可能造成兩次相同查詢結果不一樣。
    4. Read Uncommited：不加讀鎖，會有髒讀問題。
  • MVCC：利用 CREATE/DELETE_VERSION 加入事務 ID，但隔離級別為可重複讀，只讀取 <= 現在版本，若為讀已提交，總是讀取最新版本。
• 全局事務：也稱為外部事務，是ㄧ個服務（強調強一致性）多個數據源的解決方案。
  • XA：能在一個事務管理器和多個資源管理器形成溝通橋樑。且分成兩個階段去完成事務：準備（投票）階段和提交階段，提交階段是根據上一階段是否都已 Prepared 來決定要發送 Commit or Abort，以上稱為 2 Phase Commit。
  • 2PC 缺點：
    1. 單點問題：協調者如果掛掉參與者必須一直等待。
    2. 性能問題：會因為最慢的節點造成 bottleneck。
    3. 一致性風險：如果在協調者提交持久化狀態時網路崩潰，還是有不一致存在的可能。
  • 3PC：為了解決 2PC 缺點而發明。分為 CanCommit(詢問階段)、PreCommit(Redo Log階段)、DoCommit。
• 分布式事務：在分布式服務環境下的事務處理機制。
  • CAP 定理：Consistency、Availability、Partition Tolerance 最多只能滿足兩個。
  • BASE：Basically Available、Soft State、Eventually Consistent。
  • Base-Effort Delivery：靠著不斷重試來保證可靠性。
  • TCC：強調強隔離性，相較於 2PC 是著重在用戶代碼層面，所以可以根據需要設計資源鎖定的粒度，靈活性較高。
  • SAGA：將一個大事務切割成一個個的子事務，也會有日誌來保證系統恢復後可以追蹤到子事務的執行情況。

[linxinemily]

吃瓜 Link

[helloworldsmart]

吃瓜參戰 Link

[kehao-chen]

學習要點

吃 🍉 為主，隨筆撰寫

本週改用 Heptabase，本週閱讀範圍很容易會花時間去研究延伸內容，筆記整理不多，且戰且走。

[tuhacrt]

事務處理 (Transaction)

目的: 一致性 C (consistency): 數據狀態完全一致。 手段:

1. 原子性 A (Atomic): 單項業務處理只有成功或失敗，沒有中間態。
2. 隔離性 I (Isolation): 不同業務處理間互不影響。

3. 持久性 D (Durability): 提交的數據穩定持久化不丟失。

   本地事務

   泛指: 不需要經由全局事務管理器協調的事務。

   原子性和持久性

   由於在單項業務中進行操作可能會有各種不同的狀況(服務崩潰)，會用以下兩種方式來保證。

4. Commit Logging
   • 提交成功時產生 commit record
   • 修改成功時產生 end record
5. Shadow Paging - 實現簡單，但併發能力有限。
   • 複製原數據
   • 修改副本
   • 將指針移至副本 Commit Logging 會導致在 commit record 之後，不允許任何其他操作修改數據，導致性能下滑。

     ARIES

     ARIES 提出了“Write-Ahead Logging”的日志改进方案 Write-Ahead Logging 依照事務提交的時間點分為兩種情況

6. FORCE: 事務提交後，需要同時完成寫入
7. STEAL: 事務提交前，允許提前寫入。 為了允許這兩種操作 Write-Ahead Logging 新增了 Undo Log 來提前記錄哪個部分會被修改。

隔離性

鎖分為三種:

1. Write Lock(X-Lock): 數據被上 X-Lock 不可被寫，也不可被上讀鎖
2. Read Lock(S-Lock): 數據被上 R-Lock 不可被寫，也不可被上寫鎖，只有一個事務有讀鎖則可升級為寫鎖
3. Range Lock: 對於一個範圍實施排他鎖，不可被寫(含新增和刪除) 隔離性可以分為四個層級:
4. 可串行化(Serializable): 要用時全部鎖起來
5. 可重複讀(Repeatable Read): 不加上範圍鎖 => 可能導致 幻讀問題(Phantom Read)
6. 讀已提交(Read Committed): 讀鎖在查詢完成後馬上釋放 => 可能導致 不可重複讀問題(Non-Repeatable Read)
7. 讀未提交(Read Uncommitted): 只加寫鎖 => 可能導致 髒讀問題(Dirty Read)

[outshaker]

事務處理

• 為了數據狀態的一致性 C
• A原子性 I隔離性 D持久性 是手段，C是目的。
• 不限於資料庫、事務記憶體、緩存、消息佇列、分散式存儲

內部一致性 => 單一數據源，採用 AID 古典解法。 外部一致性 => 多個數據源，問題變復雜。

拆分為四種情境討論

• 單一服務，單一數據源
• 單一服務，多個數據源
• 多個服務，單一數據源
• 多個服務，多個數據源

本地事務 Local Transaction

最基礎的解法，透過數據源本身達成。 實現原理可追溯至 Algorithms for Recovery and Isolation Exploiting Semantics，ARIES

A原子性 D持久性 => 寫入磁碟無法保證原子性，有可能發生崩潰Crash

實現原子性和持久性

• 未提交，寫入後崩潰。 => 需要還原回之前的的樣子
• 已提交，寫入前崩潰。 => 需要將改動寫入

崩潰復原 Crash Recovery, Failure Recovery, Transaction Recovery

提交日誌 Commit Logging 影子分頁 Shadow Paging => SQLite v3 的實作。原理更簡單，但性能不太足

Commit Logging 先天弱勢：沒辦法事務提交前修改磁碟內的數據 改進方式：提前寫入 Write-Ahead Logging，在事務提交前，提前寫入變更

• FORCE 提交後同時變更數據，不強制為 NO-FORCE
• STEAL 事務提交前提前寫入，不允許為 NO-STEAL

Commit Logging => NO-FORCE, NO-STEAL。 Write-Ahead Logging => NO-FORCE, STEAL。搭配 Undo Log，Redo Log

恢復過程

• 分析 => 掃描日誌，找出沒有 end record 的事務 => transaction table, dirty page table
• 重做
• 回滾

NO-FORCE, STEAL => 性能最高，複雜度最高 FORCE, NO-STEAL => 性能最差，最低複雜度

實現隔離性

• 寫鎖 Write Lock => 其他事務無法讀取和寫入
• 讀鎖 Read Lock => 其他事務無法寫入，可讀取。讀鎖可以升級成寫鎖
• 範圍鎖 Range Lock => 在範圍內無法讀取和寫入，比寫鎖更嚴苛

Concurrency Control => 隔離和併發是互相牴觸的

Serializable => 最高等級的隔離 Repeatable Read => 次一級，沒有範圍鎖，可能會有幻讀問題 Read Committed => ... Read Uncommitted => ...

多版本併發控制 Multi-Version Concurrency Control，MVCC 無鎖優化方案 => 只針對 讀+寫 方案優化 樂觀併發控制 Optimistic Concurrency Control，OCC

全域事務 Global Transaction

也有外部事務的說法，適用［單一服務，多個數據源］的情境，強一致性

1991 X/Open 提出 XA (XA eXtended Architecture) 的處理事務架構

XA 將事務提交拆分成為兩階段過程

1. 準備階段
2. 提交階段

還需要其他前提：網路是可靠的。

缺點：單點問題、性能問題、一致性風險

為了改善問題，於是提出三段式提交

改善了單點問題和回滾時的性能問題

共用事務 Share Transaction

數據源是指提供數據的邏輯設備，不必與物理設備一一對應

一種理論可行的方案是直接讓各個服務共用資料庫連接 ProxySQL

分散事務

CAP 定理說明了 CAP 三者之中僅能達成兩項。現今的分散式系統大多選擇放棄C一致性達成A可用性和P分區容忍性，而對於一致性的需求變成了接受弱一致性/最終一致性。

最終一致性的說法出自於 BASE 理論 (Basically Available, Soft State, Eventually Consistent)

TCC 事務

全名 Try-Confirm-Cancel，類似 2PC，但導入既有專案還是需要一定的成本，而且也有現實狀況無法執行的困難 (下文提到 try 階段無法完成的狀況)

SAGA 事務

把大事務拆解成一系列子事務完成，在失敗時採用兩種恢復策略。

[Carisa-Li]

學習要點

事務處理

目標：維持一致性(Consistency)

• 一致性為程度
• 原子性(Atomic)
• 隔離性(Isolation)
• 持久性(Durability)

CAP定理

• 一致性(Consistency)
• 可用性(Availability)
• 分區容忍性(Partition tolerance)

類型：

• 內部一致性 - 單一數據源內
• 外部一致性 - 多數據源間
• 強一致性
• 最終一致性
• 弱一致性

crash無法避免，在考慮crash的情況下保證原子性及持久性

常用方法：

• commit logging
  • 使用log紀錄狀態
  • 可使用undo log及redo log優化
• shadow paging
  • 操作前備份數據
• 兩/三段式提交
  • 維持外部一致性

ARIES理論(Algorithms for Recovery and Isolation Exploiting Semantics)

隔離性

方法：

• lock

等級：

• serializable
• repeatable read
  • 無範圍鎖
• read committed
  • 在完成SELECT完成後(而非事務完成後)就釋放讀鎖
• read uncommitted
  • 無讀鎖

分布式事務的一致性 多服務多資料源

• TCC
  • try confirm cancel
• SEGA

[alxtz]

link: https://app.heptabase.com/w/98f3311b812edc1184a454213ec35e583c543a3b35fb510d04dea723c9b6831c

---

Summary：Transaction，本質上是從想在分散式系統上，實作出各式一致性需求而發展出的模型

---

Summary：ACID/ARIES 是基於 RDBMS 在單一硬體上設計所發展出來的理論與實現，深度影響了後世對於 transaction 和一致性的理解

---

Summary：描述了 DB journaling 最經典的實作之一，WAL

---

當要處理多硬體（分散式系統時），ACID 及「可以有真正時間次序」的諸多框架會變得不用夠，需要開始了解弱一致性以及 quorum 類的設計

---

Summary：筆者試著用「不同的鎖法」來介紹 ANSI SQL isolation 及 phenomenon，值得一提的是各資料庫實現 isolation level 的實作與哲學都有諸多差異，使用上也經常會被工具搞的混亂（serializable vs. FOR UPDATE vs. atomic check and set vs. MVCC)

建議試著用不同資源來交叉理解 phenomenon 及 MVCC，才比較能達成理解

---

Note：後續的筆記整理不完

Summary：在後續的幾章節，「distributed transaction」的定義由於作者的劃分變得有些模糊；以下簡單描述我的理解

想解決分散式系統的一致性問題，可以把哲學主要劃分為兩類

1. 試著在分散式系統上能達成 RDBMS 同等級的（強）一致性，以此基礎 2PC (XA), Paxos, Raft, TCC 類實作都屬於此。專屬名詞為維基上所定義的 Distributed Transaction/Distributed Consensus
2. 試著定義出更細致的一致性變體

前者是 XA 組織、上個 decade 許多研究的方向，但後來還是發覺 distributed consensus 終究是效能差的，導致爾後的 NoSQL/NewSQL 都往 2. 方向努力 distributed consensus 還是有他實用的價值，包含用來設計第三方服務間的交互、節點數量可控時。但後來就較少被當成分散式系統一致性的最佳解