HackMD
  • Prime
    Prime  Full-text search on all paid plans
    Search anywhere and reach everything in a Workspace with Prime plan.
    Got it
      • Create new note
      • Create a note from template
    • Prime  Full-text search on all paid plans
      Prime  Full-text search on all paid plans
      Search anywhere and reach everything in a Workspace with Prime plan.
      Got it
      • Options
      • Versions and GitHub Sync
      • Transfer ownership
      • Delete this note
      • Template
      • Save as template
      • Insert from template
      • Export
      • Dropbox
      • Google Drive
      • Gist
      • Import
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
      • Download
      • Markdown
      • HTML
      • Raw HTML
      • Sharing Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Note Permission
      • Read
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Write
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • More (Comment, Invitee)
      • Publishing
        Everyone on the web can find and read all notes of this public team.
        After the note is published, everyone on the web can find and read this note.
        See all published notes on profile page.
      • Commenting Enable
        Disabled Forbidden Owners Signed-in users Everyone
      • Permission
        • Forbidden
        • Owners
        • Signed-in users
        • Everyone
      • Invitee
      • No invitee
    Menu Sharing Create Help
    Create Create new note Create a note from template
    Menu
    Options
    Versions and GitHub Sync Transfer ownership Delete this note
    Export
    Dropbox Google Drive Gist
    Import
    Dropbox Google Drive Gist Clipboard
    Download
    Markdown HTML Raw HTML
    Back
    Sharing
    Sharing Link copied
    /edit
    View mode
    • Edit mode
    • View mode
    • Book mode
    • Slide mode
    Edit mode View mode Book mode Slide mode
    Note Permission
    Read
    Owners
    • Owners
    • Signed-in users
    • Everyone
    Owners Signed-in users Everyone
    Write
    Owners
    • Owners
    • Signed-in users
    • Everyone
    Owners Signed-in users Everyone
    More (Comment, Invitee)
    Publishing
    Everyone on the web can find and read all notes of this public team.
    After the note is published, everyone on the web can find and read this note.
    See all published notes on profile page.
    More (Comment, Invitee)
    Commenting Enable
    Disabled Forbidden Owners Signed-in users Everyone
    Permission
    Owners
    • Forbidden
    • Owners
    • Signed-in users
    • Everyone
    Invitee
    No invitee
       owned this note    owned this note      
    Published Linked with GitHub
    Like BookmarkBookmarked
    Subscribed
    • Any changes
      Be notified of any changes
    • Mention me
      Be notified of mention me
    • Unsubscribe
    Subscribe
    ###### 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 ![](https://i.imgur.com/RBercNf.png) (T1 的 X = X - N 白做) - Temporary Update Problem ![](https://i.imgur.com/BBYJmKc.png) (T1 失敗需要轉回原本的 X,但T2先讀取 temporary 的值) - Incorrect Summary Problem ![](https://i.imgur.com/nR4iDba.png) (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 ![](https://i.imgur.com/g9ZXfT3.png) - 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 ![](https://i.imgur.com/El9nB5x.png) ## 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 ![](https://i.imgur.com/uZFXS1U.png) # Reference http://debussy.im.nuu.edu.tw/sjchen/Database/Final/Ch09.pdf

    Import from clipboard

    Advanced permission required

    Your current role can only read. Ask the system administrator to acquire write and comment permission.

    This team is disabled

    Sorry, this team is disabled. You can't edit this note.

    This note is locked

    Sorry, only owner can edit this note.

    Reach the limit

    Sorry, you've reached the max length this note can be.
    Please reduce the content or divide it to more notes, thank you!

    Import from Gist

    Import from Snippet

    or

    Export to Snippet

    Are you sure?

    Do you really want to delete this note?
    All users will lost their connection.

    Create a note from template

    Create a note from template

    Oops...
    This template is not available.


    Upgrade

    All
    • All
    • Team
    No template found.

    Create custom template


    Upgrade

    Delete template

    Do you really want to delete this template?

    This page need refresh

    You have an incompatible client version.
    Refresh to update.
    New version available!
    See releases notes here
    Refresh to enjoy new features.
    Your user state has changed.
    Refresh to load new user state.

    Sign in

    Forgot password

    or

    By clicking below, you agree to our terms of service.

    Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in via Google

    New to HackMD? Sign up

    Help

    • English
    • 中文
    • Français
    • Deutsch
    • 日本語
    • Español
    • Català
    • Ελληνικά
    • Português
    • italiano
    • Türkçe
    • Русский
    • Nederlands
    • hrvatski jezik
    • język polski
    • Українська
    • हिन्दी
    • svenska
    • Esperanto
    • dansk

    Documents

    Tutorials

    Book Mode Tutorial

    Slide Mode Tutorial

    YAML Metadata

    Contacts

    Facebook

    Twitter

    Feedback

    Send us email

    Resources

    Releases

    Pricing

    Blog

    Policy

    Terms

    Privacy

    Cheatsheet

    Syntax Example Reference
    # Header Header 基本排版
    - Unordered List
    • Unordered List
    1. Ordered List
    1. Ordered List
    - [ ] Todo List
    • Todo List
    > Blockquote
    Blockquote
    **Bold font** Bold font
    *Italics font* Italics font
    ~~Strikethrough~~ Strikethrough
    19^th^ 19th
    H~2~O H2O
    ++Inserted text++ Inserted text
    ==Marked text== Marked text
    [link text](https:// "title") Link
    ![image alt](https:// "title") Image
    `Code` Code 在筆記中貼入程式碼
    ```javascript
    var i = 0;
    ```
    var i = 0;
    :smile: :smile: Emoji list
    {%youtube youtube_id %} Externals
    $L^aT_eX$ LaTeX
    :::info
    This is a alert area.
    :::

    This is a alert area.

    Versions

    Versions and GitHub Sync

    Sign in to link this note to GitHub Learn more
    This note is not linked with GitHub Learn more
     
    Add badge Pull Push GitHub Link Settings
    Upgrade now

    Version named by    

    More Less
    • Edit
    • Delete

    Note content is identical to the latest version.
    Compare with
      Choose a version
      No search result
      Version not found

    Feedback

    Submission failed, please try again

    Thanks for your support.

    On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

    Please give us some advice and help us improve HackMD.

     

    Thanks for your feedback

    Remove version name

    Do you want to remove this version name and description?

    Transfer ownership

    Transfer to
      Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

        Link with GitHub

        Please authorize HackMD on GitHub

        Please sign in to GitHub and install the HackMD app on your GitHub repo. Learn more

         Sign in to GitHub

        HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.

        Push the note to GitHub Push to GitHub Pull a file from GitHub

          Authorize again
         

        Choose which file to push to

        Select repo
        Refresh Authorize more repos
        Select branch
        Select file
        Select branch
        Choose version(s) to push
        • Save a new version and push
        • Choose from existing versions
        Available push count

        Upgrade

        Pull from GitHub

         
        File from GitHub
        File from HackMD

        GitHub Link Settings

        File linked

        Linked by
        File path
        Last synced branch
        Available push count

        Upgrade

        Danger Zone

        Unlink
        You will no longer receive notification when GitHub file changes after unlink.

        Syncing

        Push failed

        Push successfully