or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
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.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
tags:
database
段考速記
架構
請求層 (Query Interface)
存儲層 (Storage Interface)
RecordFile 和存儲單位
Metadata
伺服器與執行緒
Thread or Process
伺服器管理的最小可執行單元可能為 thread 或 process,各有優缺,考量兩者的差異:
通常使用 Thread,這是因為管理 global/share resource (open file, heap mem) 交由 DBMS 來處理較方便、高效,且 thread 的建置較 Process 快。
Kernel & user thread
Thread mapping 模型的選擇
處理的請求步驟
收到 SQL query 時…
Parsing (syntax-based)
Verification (semantic-based)
根據語意,語意是否合理
Plan
Scan
存儲層
三種資料
資料庫的 ACID 分別由 concurrency manager 和 recovery manager 實現。
硬碟三時間
OS 提供的資料訪問方法
Block level
File level
File v.s. block
記憶體管理
記憶體的使用有
對於 DBMS,不應該依賴 VM,swap 與否應自行管理。其好在
另外,Log 不需用 buffer pool,因為其只會恆定的使用一個 buffer,且永遠只有 append 和反向讀取兩種操作。
使用 Buffer pool 減少 I/O…
使用 Block 時透過 pin 一個 page buffer,pin 有以下幾種可能:
注意到 buffer 和 page 都應該是 thread safe 的。
Replacement algo
常見算法
也可採用混合算法,比如 Oracle DBMS 使用 cold 時 LRU、hot 時 FIFO。
Deadlock
資料管理
Table records 於 file 中的存法
Spanned v.s. unspanned records
Field 索引方法
text
這種肥大且不定長的資料Column/row oriented store
要以 column 還是 row 為基礎存資料?
綜合判斷
並行管理
確保
對於一次交易,其生命週期為:
交易排程
並行交易希望能達到
Anomalies
解決資料衝突: Locking protocol
Two-phase locking (2PL)
鎖以 Lock table (像是 hash table) 的方式管理。
2PL 解決序列化問題,但可能發生
S2PL (S: strict)
與 2PL 唯一差別: 等到一個交易結束時一次將所有鎖放掉,其他時候不放鎖,等同於 shrinking phase 只有一瞬間。
Strict 保證不會發生 cascading abort。
死結處理
鎖的顆粒度 (Granularity) 與 Multiple-granularity locking (MGL)
可以鎖的物件有階層關係。
以此為基礎的鎖: MGL,基於 2PL 鎖的種類做出調整… (多了 intention lock 意向鎖): 鎖某物件時,連同其上層的所有親代物件都使用對應的意向鎖鎖起來。
上解鎖的順序有講究:
實時動態資料庫的 Phantoms
資料可能實時 insert, update 和 delete,有機會發生讀兩次資料不同的情況。
兩招解法:
另外,Conservative lock 依然可能遇到 phantom,要看鎖了什麼東西。
Isolation model
上表為使用者角度,下表為實作角度。
實務上考慮 Meta structure
由於 insert 和 delete 都需要先調整 meta structure 後調整 file,如果直接把 meta structure 鎖起來,insert 和 delete 就沒有並行性了。
要避免此瓶頸,可以不用完全遵照 S2PL,而是先 lock meta 後 lock file,在 lock 到 file 後可以放掉 meta 的 lock。
對 insert/delete 來說,資料不會錯誤是因為改 meta file 完對其他交易而言,相當於已經完成 insert/delete (只是還沒真的寫上去,但看起來是)。
資料復原
可能需要復原的時機:
Rollback 成功的依據:Write-Ahead-Logging (WAL),在所有寫資料操作前先寫一 log,commit/abort 操作完成後再寫一個 log。
Physical logging (段考範圍末)
Log 內容有以下幾種:
Rollback 操作從 log 末尾開始蒐集…
且需確保在 flushing 的 buffer 不會被修改,修改中的 buffer 也不該被 flush,可由 latch 保證。
至此我們有 rollback undo 的演算法如下。
一個例子:
Undo-redo recovery
每完成一筆交易都需要 flush dirty buffer 至 disk 的效率實在不怎麼樣。透過紀錄修改新舊值訊息的 log,我們可以延緩 flush 的時機,如果在還沒 flush 之前系統出事,可透過 log 把還沒 flush 進 disk 的資料都 redo 一遍。
概念澄清
有趣的想法: Force + No steal
Redo 本身是因為採用 no force 導致 commit 後寫的資料不會即時 flush 回 disk,如果 force 的話就規避了 redo 操作。
那麼 undo 本身會存在即因為 steal: flush 了中間結果而非最終結果,若採用 no steal,是否就規避了 undo 操作?
也就是 Force + no steal 就使 log 沒有必要存在了 (no redo & no undo)?
答案是錯的,此法有兩點問題。
Force undo-redo recovery
特別注意到這些 log rollback 操作都是 idempotent (每次做都得到一樣的結果) 的。
No-force undo-redo recovery
更進一步的,no-force 版的更激進,在 rollback 時不需要將 dirty pages flush 掉,更不需要寫入
<ROLLBACK>
進 log,因為重啟後重新 rollback 的結果都是 idempotent 的!這帶來了另一版本的 rollback 演算法:
此時 undo journaling 一定要先於 redo! 不然 undo 的部分可能蓋掉 redo 的。
比較
undo-only 的
明顯 undo-redo 版的對服務時期比較友好,更佳適合採用。
Checkpoint
降低每次 rollback undo/redo 的成本,適合在離峰時進行。
Quiescent 版
但第二步不知道要等多久…
Nonquiescent 版
<NOQCKPT, T1, T2, ..., Tk>
至 log 並將其 flush 回 disk但由於 checkpointing 時仍有交易在進行,他們可能也要寫 log,故在上述 3~4 步時需要 latch log file + all blocks (始於 3 前,終於 4 後)。