# 資料庫 Transaction & Lock 筆記

###### tags: `DB`

DB 四大重要特性(ACID)

- Atomicity: transaction 不可分割性，transaction 內所有操作全部完成或全部不完成，中間錯誤會被 rollback
- Consistency: 保持資料完整一致性
- Isolation: 允許多筆 transaction 同時對資料讀寫跟修改能力，且避免多筆 transaction 執行時由於交叉執行而導致數據的不一致(race condition)。
- Durability: 對資料的修改是永久的，即便系統故障也不會丟失

基本要求

- transaction 執行過程有 error 將會自動 rollback，不必自行實作。
- transaction 執行成功完成 commit 即存入資料庫，除非儲存空間受損，否則資料不會流失。
- 完善的 lock 管理機制，避免 race condition 情形，有 deadlock resolution。

## Race condition

多筆 transaction 同時對同一筆資料讀寫跟修改時可能會出現的狀況

- Dirty Read: 讀取到其他 transaction 尚未 commit 的資料

| Transaction 1 | Transaction 2 |
| ------ | ----------- |
| 修改商品價格(100元 -> 0元) | |
| | 取得商品價格(0元) |
| Rollback ||
| | 新增訂單(0元) |
| | Commit |

**Transaction 2 不該讀取到 Transaction 1 尚未 commit 的資料**

- Non-repeatable reads: 同一個 transaction 中，執行多次相同的 query 條件，讀取欄位的資料不同

| Transaction 1 | Transaction 2 |
| ------ | ----------- |
| 取得 A 商品價格(3000元) | |
| (其他指令...) | 修改 A 商品價格(4000元) |
| (其他指令...) | Commit|
| 取得 A 商品價格(4000元) ||
| 新增訂單(4000元)||
| Commit||

**Transaction 1 中取得 A 商品的價格應該要一致**

- Phantom reads: 同一個 transaction 中，執行多次相同的 query 條件，取出的資料數目不同

| Transaction 1 | Transaction 2 |
| ------ | ----------- |
| 取得 A 商品的積木數(30個) ||
| (其他指令...) | 新增 A 商品積木 |
| (其他指令...) | Commit|
| 取得 A 商品的積木數(31個) ||
| 新增訂單(31個)||
| Commit||

**Transaction 1 中取得 A 商品的積木數應該要一致**

- Write Skew: 不同的 transactions 執行某樣 query 條件操作驗證，然後再去做新增/修改動作，卻造成資料衝突

EX: 同一張票造成多人訂票
| Transaction 1 | Transaction 2 |
| ------ | ----------- |
| 取得票剩餘數(1 張) ||
| (其他指令...) | 取得票剩餘數(1 張) |
| (其他指令...) | (其他指令...) |
| 寫入訂票資料 | (其他指令...) |
| Commit | 寫入訂票資料 |
| | Commit |

EX: 點數超支
| Transaction 1 | Transaction 2 | Transaction 3 | Transaction 4 |
| ------ | ------ | ------ | ------ |
| 取得商品資料(10000點)||
| 取得剩餘點數(11000點) | 取得商品資料(10000點)|
| (其他指令...) | 取得剩餘點數(11000點) | 取得商品資料(10000點)|
| (其他指令...) | (其他指令...) | 取得剩餘點數(11000點) | 取得商品資料(10000點)|
| (其他指令...) | (其他指令...) | (其他指令...) |取得剩餘點數(11000點) |
| 新增訂單(10000點) | (其他指令...) | (其他指令...) | (其他指令...) |
| Commit | 新增訂單(10000點) | (其他指令...) | (其他指令...) |
| | Commit | 新增訂單(10000點) | (其他指令...) |
| | | Commit | 新增訂單(10000點) |
| | | | Commit |

## Isolation Level
Isolation Levels 有四種等級，各家資料庫皆會宣稱支援到何種等級，一般需要 transaction 情境至少會要求到 Repeatable Read 的等級。選擇 DB System 要考量其支援 Isolation Levels，否則要自行處理 race condition 問題。

1. Read Uncommitted: 代表 transaction 可以讀到別的 transaction 尚未 commit 的資料，在這個等級中 race condition 三個問題都沒有解決。
2. Read Committed: 代表 transaction 只能讀到別的 transaction 已經 commit 的資料，沒有 commit 的話就不會讀到，在這個等級解決了 Dirty Read 的問題。
3. Repeatable Read: 代表每次 transaction 要讀取特定欄位的資料時，只要 query 條件相同，讀取到的資料內容就會相同。在這個等級解決了 Non-repeatable reads 的問題。
4. Serializable: 代表在多個 transaction 同時執行時，只要 transaction 的順序相同時，得到的結果一定相同。比如說 Transaction A 先執行了接下來再執行 Transaction B，在同樣的條件下，每次執行都會得到一樣的結果。在這個等級下連同 Phantom reads 也會一併被解決。

## 如何解決 race condition 問題

### MYSQL InnoDB

- InnoDB 預設 Isolation Level 為 Repeatable Read

#### Record-level locks

- 分成 shared (S) locks 和 exclusive (X) locks，該筆資料(index records) 被讀取時發行 S lock，修改/刪除時發行 X lock
- S lock 可以發給多個 trancaction，所以多個 trancactions 可以讀取同一筆資料。
- X lock 只會發給一個 trancaction，且如果該筆資料已發行 S locks 給其他 trancaction 時，將不會發行 X lock。
- SX locks 機制即 transaction 讀取時其他 transactions 都可以讀，但 transaction 修改時其他 transactions 將無法讀取。
- InnoDB SX locks 提供不同粒度的 lock 種類:
- Record lock: This is a lock on an index record.
- Gap lock: This is a lock on a gap between index records, or a lock on the gap before the first or after the last index record
- Next-key lock: This is a combination of a record lock on the index record and a gap lock on the gap before the index record.

- 遇到 conflict 時 trancaction 會等待以取得相應 locks，lock 種類越多或 lock 範圍越大，越容易引起 Lock wait timeout。
- 提升到 Serializable 才會加入 Gap lock & Next-key lock，但容易引起 Lock wait timeout or Deadlock 及大大降低使用效能。

#### Intention Locks

- 分成 Intention shared (IS) 和 Intention exclusive (IX)，是自行上鎖的概念
- 加上 IS 會使其他 insert/update 會被檔下來，但取值不會被擋下

SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 LOCK IN SHARE MODE

#此時其他 transation 如果想在10~20內 insert/update 會被檔下來
#此時其他 transation 如果想在10~20內取值不會被擋下

- 加上 XS 會使其他 insert/update 會被檔下來，但取值也會被擋下，
可防止 Phantom reads 及 Write Skew

SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 FOR UPDATE

#此時其他 transation 如果想在10~20內 insert/update 會被檔下來
#此時其他 transation 如果想在10~20內取值會被檔下來

- lock type compatibility

|| X | IX | S | IS |
| ------ | ------ | ------ | ------ | ------ |
| X |Conflict | Conflict | Conflict | Conflict |
| IX |Conflict | Compatible | Conflict | Compatible |
| S |Conflict | Conflict | Compatible | Compatible |
| IS |Conflict | Compatible | Compatible | Compatible |

#### Undo log

當對資料做變更時 innoDB 會寫入 Undo log，紀錄每個 transaction 變更內容，可依此作為 rollback 依據，並宣稱有 MVCC 功能，其實資料沒有多版本並存，如果 A transaction 出錯要 rollback 時，還原的資料會加上排他鎖(其他 transaction 無法讀取跟寫入)，仍會出現無法讀取。

### PostgreSQL

- PostgreSQL 預設是 Read Committed 的 isolation level

#### MVCC (Multiversion Concurrency Control)
- 每一筆資料的變動都會增加額外 snapshot 並標記 version，太舊的版本會自動刪除，讀取時會取最新的 commit version
- 資料只有 X lock，如同 SX lock 架構，更新資料必須沒有其他 X lock 存在。
- 資料帶有 snapshot 版本，讀取不需關注是否有 X lock，即使修改時也能讀取
- lock 種類較少，降低 deadlock 發生機率。
- 因為加入 version 管理機制，就單一 transaction 而言，效能會比 SX locks 差。

#### Predicate locking

- transaction 讀取時會加入 predicate lock，若有其他 transaction 執行 predicate lock 修改並成功 commit (有新版的 commit version)，則這次 transaction 將會回傳錯誤並 rollback
- 可達到 Serializable isolation level
- 不會讓任何 transaction 等待
- 降低效能

#### Table and row locks

- PostgreSQL 提供多樣可自行加入的 table and row locks，可參考 [Explicit Locking](https://www.postgresql.org/docs/9.5/explicit-locking.html)，以下舉 Row-level Lock Modes 為例
- `FOR UPDATE`: 類似 MYSQL InnoDB 的 IX， row 在 `FOR UPDATE` mode 將不能執行 `UPDATE`、`DELETE`、其他 Row-level Lock Modes 操作
- `FOR NO KEY UPDATE`: 除了允許 `SELECT FOR KEY SHARE` 與 `FOR UPDATE` 相同
- `FOR SHARE`: row 在 `FOR SHARE` mode 不能執行 `UPDATE`, `DELETE`, `SELECT FOR UPDATE` or `SELECT FOR NO KEY UPDATE`
- `FOR KEY SHARE`: row 在 `FOR KEY SHARE` mode 不能執行 `UPDATE`, `DELETE`, `SELECT FOR UPDATE`

### DynamoDB

- 遇 race condition 情形會 throw TransactionConflictException, 可能要視情況自行實作 auto-retries 機制

#### Isolation Level
DynamoDB 提供 TransactWriteItems & TransactGetItems 來執行 transaction, 其宣稱的 Isolation Level 可參考 [DynamoDB transaction-isolation](https://docs.aws.amazon.com/en_us/amazondynamodb/latest/developerguide/transaction-apis.html#transaction-isolation)

| Operation | Isolation Level |
| ------ | ----------- |
| DeleteItem | Serializable |
| PutItem | Serializable |
| UpdateItem | Serializable |
| GetItem | Serializable |
| BatchGetItem | Read-committed |
| BatchWriteItem | NOT Serializable |
| Query | Read-committed |
| Scan | Read-committed |
| Other transactional operation | Serializable |

#### failed 情境

TransactWriteItems 失敗情境
1. 其中一個 condition expressions 沒有吻合
2. 同一 item 正在被其他 request 更新時( 其他的 PutItem, UpdateItem, or DeleteItem or TransactWriteItems)
3. Table 在不同的 account or region 時
4. 單一 item 超過 400 KB, local secondary index too large 時
5. Items 總量大於 4MB
6. data format 錯誤

TransactGetItems 失敗情境
1. 同一 item 當有其他 PutItem, UpdateItem, DeleteItem or TransactWriteItems request 在處理時
2. Table 在不同的 account or region 時
3. Items 總量大於 4MB
4. 超過 25 個 unique item
5. data format 錯誤

## 參考資料
- [Transaction Isolation Levels for MySQL](https://dev.mysql.com/doc/refman/8.0/en/innodb-transaction-isolation-levels.html)
- [Transaction Isolation for PostgreSQL](https://www.postgresql.org/docs/9.5/transaction-iso.html)
- [InnoDB Locking](https://dev.mysql.com/doc/refman/8.0/en/innodb-locking.html#innodb-intention-locks)
- [PostgreSQL Explicit Locking](https://www.postgresql.org/docs/9.5/explicit-locking.html)
- [Amazon DynamoDB Transactions](https://docs.aws.amazon.com/en_us/amazondynamodb/latest/developerguide/transaction-apis.html)
- [DynamoDB Transactions Limits](https://docs.aws.amazon.com/en_us/amazondynamodb/latest/developerguide/Limits.html#limits-dynamodb-transactions)
- [TritonHo RDBMS Course](https://github.com/TritonHo/slides/blob/master/Taipei%202019-04%20course/lesson1.pdf)