tags: database

並行管理

確保

  • C (consistency)
    • 資料庫的資料符合 integrity constraints,也就是一些限制
    • 資料庫與使用者共同維護
  • I (isolation)
    • 對每筆交易都像是只有那個使用者在使用系統一樣

對於一次交易,其生命週期為:

  • Begin
  • Statement ends (如果有多個 statement)
  • End
    • Commit
    • Rollback

交易排程

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

並行交易希望能達到

  • Serializable schedule: 同時有
    n
    次交易,最終結果為該
    n
    次交易的某個排列組合
  • Recoverable schedule: 當一筆交易 abort 不影響其他筆交易;一筆交易 committed 後不應該被牽連而失去該筆交易

Anomalies

  • 發生資料衝突 (Conflict) (R: read, W: write)
  • WR conflict 一個先寫另一個後讀
    • Dirty reads: 讀還沒 committed 的資料
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →
    • Unrecoverable schedule 或 Cascading aborts
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →
  • RW conflict 一個先讀另一個後寫
    • Unrepeatable reads: 讀兩次讀的東西不同
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →
  • WW conflict 一個先寫另一個後寫
    • Lost update: 先寫的會失去
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →

解決資料衝突: Locking protocol

Two-phase locking (2PL)

  • 鎖種類
    • shared lock (R lock)
    • exclusive lock (W lock)
  • 階段
    1. Growing phase: 只取鎖
    2. Shrinking phase: 只放鎖

鎖以 Lock table (像是 hash table) 的方式管理。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

2PL 解決序列化問題,但可能發生

  • Cascading rollback
  • Deadlock
  • Starvation (根據不良的 waiting 隊列規則可能發生)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

S2PL (S: strict)

與 2PL 唯一差別: 等到一個交易結束時一次將所有鎖放掉,其他時候不放鎖,等同於 shrinking phase 只有一瞬間。

Strict 保證不會發生 cascading abort。

死結處理

  • Detection: timeout + rollback
  • Prevention: Wait die,放棄執行時間較短者
  • Conservative lock: S2PL 之上,連 growing phase 也只有一瞬間
    • 需知道 r/w working set
    • 適合 stored procedure
    • 不適合 ad-hoc (隨當前資料情況決定交易內容)

鎖的顆粒度 (Granularity) 與 Multiple-granularity locking (MGL)

可以鎖的物件有階層關係。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

以此為基礎的鎖: MGL,基於 2PL 鎖的種類做出調整 (多了 intention lock 意向鎖): 鎖某物件時,連同其上層的所有親代物件都使用對應的意向鎖鎖起來。

SIX 的白話文: 為 Share ( R ) 鎖,不過讀的下層存在 X 鎖。

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

上解鎖的順序有講究:

  • 上鎖由根往葉
    • 若改為由葉往根,上鎖時如果上層被鎖就無法繼續往下鎖了。
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →
  • 解鎖由葉往根
    • 若給為由根往葉,根一解鎖馬上被鎖,可能在葉的鎖還沒釋放的情況下就被拿上層的鎖。
      Image Not Showing Possible Reasons
      • The image was uploaded to a note which you don't have access to
      • The note which the image was originally uploaded to has been deleted
      Learn More →

實時動態資料庫的 Phantoms

資料可能實時 insert, update 和 delete,有機會發生讀兩次資料不同的情況。

兩招解法:

  • EOF lock 或 MGL
    • 如果使用 MGL 實作 phantom 避免,要去 X lock 目標上層 (高一層 Granularity) 的物件,比如要寫 block 的話去鎖 file
    • 常拿去避免 insert phantom
    • 但不會想去避免 update phantom,因為太損效能
  • Index/predicate lock

另外,Conservative lock 依然可能遇到 phantom,要看鎖了什麼東西。

Isolation model

  • Access model: 告知 read only/rw
  • Isolation level: 可放棄 serializable 的部分性質換取效能
    上表為使用者角度,下表為實作角度。
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

實務上考慮 Meta structure

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

由於 insert 和 delete 都需要先調整 meta structure 後調整 file,如果直接把 meta structure 鎖起來,insert 和 delete 就沒有並行性了。

要避免此瓶頸,可以不用完全遵照 S2PL,而是先 lock meta 後 lock file,在 lock 到 file 後可以放掉 meta 的 lock。

對 insert/delete 來說,資料不會錯誤是因為改 meta file 完對其他交易而言,相當於已經完成 insert/delete (只是還沒真的寫上去,但看起來是)。