並行管理
確保
- C (consistency)
- 資料庫的資料符合 integrity constraints,也就是一些限制
- 資料庫與使用者共同維護
- I (isolation)
對於一次交易,其生命週期為:
- Begin
- Statement ends (如果有多個 statement)
- End
交易排程
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: 同時有 次交易,最終結果為該 次交易的某個排列組合
- 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)
- 階段
- Growing phase: 只取鎖
- 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 →
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 (只是還沒真的寫上去,但看起來是)。