tags: Data Base

第十二章: Transactions

Transaction Processing

• Single-User System:

  • 在同一時間最多一個 user 可以使用 system

• Multiuser System:

  • 在同一時間可有很多 user 進入 system concurrently

• Concurrency

  • Interleaved processing
    • processes 競爭一個 CPU
  • Parallel processing
    • processes 競爭數個 CPUs

Transactions

• 一連串的 operations
• Transaction boundaries
  • Begin and End transaction

Read and Write Operations

• read_item(X)

  • 找到 address of the disk block item X
  • Copy disk bkock into a buffer in main memory
  • Copy item X 給 program variable named X

• write_item(X)

  • 找到 address of the disk block contain X
  • Copy disk block into a buffer in main memory
  • Copy item X from program variable named X 到正確的 location in the buffer
  • 儲存 updated block from buffer 給 disk

Why Concurrency Control

• Lost Update Problem
  
  (T1 的 X = X - N 白做)

• Temporary Update Problem
  
  (T1 失敗需要轉回原本的 X，但T2先讀取 temporary 的值)

• Incorrect Summary Problem
  
  (T3 在 X -N 後讀取 X, 在 Y + N 之前讀取 Y, 造成 X + Y 錯誤)

Why Recovery?

• 系統崩潰
• 系統錯誤或 transaction error
• Local errors 或 exception conditions
• Concurrency control
• Disk failure
• Physical problem and catastrophes

Transaction Concepts

• 為了達到 recovery 必須時時刻刻盯著 transaction
• Transaction states:
  • Active state
  • Partially commited stated
  • Failed state
  • Terminated State

• begin_transaction: 標記 transaction 執行開始

• read or write: 定義 read and write operation on the database items

• end_transaction: 標記 transaction 執行結束

• commit_transaction: 表示 transaction 執行安全，可以放心確認 database 不會被 undone

• rollback(or abort): 表示 transaction 執行不成功，要將之前被 transation 改變的 effects undone

• Recovery techniques 用下列 operators:

  • undo:撤回之前的動作
  • redo:某些 transation operations 要重做確保成功應用於 database

System Log

• Log or Journal: log 會追蹤 transaction operations 影響了那些 database items
  • log 會用在 recovery 時
  • log 會存在 disk 所以不會受到 transcation 失敗影響
  • 定期備份到暫存 storage 確保不會有物理傷害

Log Records

• T 是 transaction-id
• Type of log record:

  • [start_transation, T]: transaction 開始標記

  • [Write_item, T, X, old_value, new_value]: 更改 log

  • [read_item, T, X]: 讀取 log

  • [commit, T]: transaction 執行成功 log

  • [abort, T]: transaction 失敗 log

Transaction Redo

• Redoing transactions:
  • 當 commit entry 已經在 log 時， 其他 write operators 也已經在 Log, 除此之外可以從 log entries 啟動 redone
  • 當系統 crash 時，只有 log entries 被寫回 disk，可以用於 recovery process，因為 main memory 可能丟失資料

Force Write

• 有任何 transaction log 沒有被寫入 disk 時，必須在 committing transaction 之前啟動 force write process 來寫入 log。

ACID Properties

• Atomicity:
  • 全完成或全不完成(不可分割性)
• Consistency preservation:
  • transaction 正確執行會將 db state 轉移到另一個
• Isolation:
  • transaction 在 commit 前都不會看到其他 transaction，解決 temporary update problem
• Durability or permanency:
  • 一旦 commit ，這些改變不會因為後面的失敗而被刪除

Schedules

• Transaction 所組成，解決 concurrency ，排順序決定 transaction 執行

Characterizing Schedules

• Recoverable schedule:

  • 當 T' 有對 item A 做 write 時，必須在 item A 被其他 transaction read 之前先做 commit，這樣符合 recovery schedule

• Cascadeless schedule:

  • 所有 transaction 只有 read the 被 committed 的 item ，稱作 Cascadeless schedule

• Schedules requiromg cascaded rollback:

  • 當讀 failed transaction 改動的值時，必須一起 rollback

• Strict Schedules:

  • 每個 transaction 都只讀寫已 commited 的 item

Serializability

• Serial schedule:

  • 每個 transacion 出現的順序等於執行的順序

• Serializable schedule:

  • 如果 schedule S 等價於其他有 n 個 transaction 的serial schedule, 稱為 serializable scheudule

Result Equivalent

• Result equivalent:
  • 兩個 schedules 結果一樣稱為等價

Conflict Serializability

• 衝突:

  • 定義:
    • 屬於不同 transactions
    • access 一樣的 item
    • 至少一個是 write

• Conflict equivalent:

  • 兩個排程間有 order 一樣的任兩個 conflicting operations，稱 Conflict equvalent

• Conflict serializable:

  • 若發生 conflict equivalent，則兩 schedules 稱為 conflict serializable

Serializability

• 定義: schedule 是 correct schedule
  • 執行過後 database 是 consistent state
  • 適當交錯且 result 是 serially executed，並且有效率執行 concurrent execution
• 使用 locks with two phase locking(2PL)

Testing Conflict Serializability

1. 只看 read_item and write_item operations
2. 建構 precedence graph(serialization graph)
3. 當 Ti 跟 Tj 有 conflitct operator 時，畫箭頭
   • 只往下對應
   • 當 read(x) 時，對應其他 transaction 的 write(x) 畫箭頭
   • 當 write(x) 時，對應其他 transaction 的 write(x) 與 read(x)
4. 當 precedence graph 沒有 cycles 時，則 schedule is serializable

Transaction Support in SQL2

SQL 有一個 SET TRANSACTION statement in SQL2

• Isolation level <isolation>
  • 可以做到:
    • READ UNCOMMITTED
    • READ COMMITTED
    • REPEATABLE READ
    • SERIALIZABLE

Potential problems with lower isolation levels:

• Dirty Read:

  • 讀到 failed transaction 寫入的值

• Nonrepeatable Read:

  • T1 裡有 read_item(x) ,之後 T2 wrrite_item(x)完，T1 再 read_item(x) 一次，得到兩個不一樣的值

• Phantoms:

  • A transaction T1 may read a set of rows from a table,perhaps based on some condition specified in the SQL WHERE clause.
  • Now suppose that a transaction T2 inserts a new row that also satisfies the WHERE clause condition of T1, into the table used by T1.
  • If T1 is repeated, then T1 will see a row that previously did not exist, called a phantom .

Possible Violation of Serializability

Reference

http://debussy.im.nuu.edu.tw/sjchen/Database/Final/Ch09.pdf