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

Select a repo