注：Condolination array 的 slot 部分理解有問題
Abstract
4個缺陷限制了 logging-related 的數(shù)據(jù)庫系統(tǒng)的可擴展性:
- 大量小 I/O 請求可能過載 disk
- 事務(wù)在等待 log flush 期間持有鎖
- 外延的而上下文切換，帶來的線程執(zhí)行 log I/O 給操作系統(tǒng)調(diào)度器帶來的壓力
- 事務(wù)順序訪問內(nèi)從中的 log 數(shù)據(jù)結(jié)構(gòu)帶來的競爭
本文介紹了這些問題，并用一種全面的、可擴展的 log 方式來解決這些問題，展示出了可觀的性能。
Introduction
以前的 DBMS 的硬件環(huán)境是：單核、高 I/O 延遲，現(xiàn)在這一情況已經(jīng)改變。新的 DBMS 盡可能利用并發(fā)性來交織大量事務(wù)的執(zhí)行。雖然理論上硬件提升后，并發(fā)性也就更高，但是 DBMS 內(nèi)部的很多瓶頸限制了這一提升。這些瓶頸如 Abstract 里所列舉的，目前的研究都只是分段或部分地解決這些問題，沒有提出一個充分適應(yīng)當前多核環(huán)境下的，可擴展的 log manager。
Write-ahead Logging and Log Bottlenecks
幾乎所有數(shù)據(jù)庫系統(tǒng)都使用中心化的 write-ahead logging (WAL) 技術(shù)。WAL 技術(shù)的目的和好處這里就不另外說明了，文中給出了四種存在的 delay，如下所示。
- I/O-related delays
這個好理解，就是每次日志要寫到非易失性存儲上，一般是磁盤，I/O 有延遲。 - Log-induced lock contetention
寫操作需要持有日志的寫鎖，在 flush 期間一直持有寫鎖，會導(dǎo)致其它線程無法并發(fā)。 - Excessive context switching
CPU 可能將正在執(zhí)行事務(wù)的線程給切換出去了，因為時間片到了。 - Log buffer contention
中心化的設(shè)計導(dǎo)致只有一個中央日志，大量線程同時嘗試往日志里寫的時候，因為日志是先寫到緩沖區(qū)的，這樣就算沒有邏輯鎖，也會產(chǎn)生“競爭”。
async logging 異步日志可以有效解決上述問題的前三個，并且很多數(shù)據(jù)庫系統(tǒng)，如 Oracle 和 PostgreSQL 都提供，但是可能會產(chǎn)生數(shù)據(jù)丟失的問題。這里不展開闡述。目前為止，還沒有方法全部解決上述四個問題。
A Holistic Approach to Scalable Logging
- Early Lock Release (ELR)
ELR 用來解決寫鎖競爭。ELR 在研究工作中多次被提到，但是目前沒有實現(xiàn)到任何數(shù)據(jù)庫引擎中。（注：這個 ELR 可能存在設(shè)計問題） - Flush Pipelining
用來解決上寫問切換的問題。 - Log Buffer Redesign
重新設(shè)計了 log buffer, 來實現(xiàn)線程數(shù)量、日志大小與日志競爭之間無關(guān)。但可能導(dǎo)致內(nèi)存帶寬成為新的瓶頸。
Related Work
ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) 技術(shù)在 DBMS 中廣泛被應(yīng)用，來實現(xiàn)并發(fā)控制、事務(wù)回滾和錯誤恢復(fù)。ARIES 技術(shù)下的 log 被實現(xiàn)為一個所有事務(wù)共享的全局數(shù)據(jù)結(jié)構(gòu)，從而造成了性能瓶頸。
固態(tài)硬盤能極大地減少 I/O 帶來的開銷，但是因為同步 flush 操作還是會造成線程阻塞，從而觸發(fā)線程調(diào)度，還是不能消除所有開銷。
Log 組提交策略將多個 flush 操作合并為單個 I/O 操作，從而減少了上面提到的開銷。
TODO 沒看懂 Unfortunately, group commit does not eliminate unwanted context switches because transactions merely block pending notification from the log rather than blocking on I/O requests directly.
異步提交繼承了組提交的思想，但還包括異步。異步就可能造成數(shù)據(jù)丟失。
一個研究結(jié)論：事務(wù)可以安全地在 flush 日志到磁盤上之前就釋放鎖。ELR 基于這個結(jié)論做了實現(xiàn)。
內(nèi)存數(shù)據(jù)庫面臨的挑戰(zhàn)就是，log I/O 相比之下成為很大的性能瓶頸，因為這是唯一需要訪問磁盤的操作，體現(xiàn)在磁盤 I/O 本身的延遲和對 log buffer 的競爭。
Moving Log I/O Latency off the Critical Path
Early Lock Release
事務(wù)的鎖可以在日志提交到磁盤之前被釋放，只要它不會在持久化之前返回給客戶端任何結(jié)果。但是如果有預(yù)提交事務(wù)要讀這個結(jié)果，那么就存在一個依賴關(guān)系，DBMS 保證在它所依賴的事務(wù)被完成之前，即寫到磁盤上之前，不會返回任何結(jié)果。順序日志實現(xiàn)天生保證了這一特點，因為日志只能順序?qū)憽?br> ELR 系統(tǒng)必須包含兩個條件來保證可恢復(fù)性：
- 每一個事務(wù)的日志必須在它所依賴的事務(wù)完成預(yù)提交階段后，才能提交。
這里涉及到一個數(shù)據(jù)庫事務(wù)的三階段提交的概念。詳細可以查閱博客。與本文相關(guān)的，pre-commit 后，所有操作已經(jīng)計入日志，而 do-commit 只是根據(jù)日志去寫入磁盤。所以只要 pre-commit 完成，實際上就可以釋放日志的寫鎖了。
- 當一個 pre-commit 事務(wù)被 abort 掉后，依賴該事務(wù)的所有事務(wù)也要被 abort。這個很好理解，需要注意的是實現(xiàn)上。
一篇博客中 關(guān)于 WAL 的工作流程的解釋。
1.在SQL Server的緩沖區(qū)的日志中寫入”Begin Tran”記錄
2.在SQL Server的緩沖區(qū)的日志頁寫入要修改的信息
3.在SQL Server的緩沖區(qū)將要修改的數(shù)據(jù)寫入數(shù)據(jù)頁
4.在SQL Server的緩沖區(qū)的日志中寫入”Commit”記錄
5.將緩沖區(qū)的日志寫入日志文件
6.發(fā)送確認信息到客戶端(SMSS,ODBC等）
7.將緩沖區(qū)內(nèi)的頁寫入到磁盤
一篇博客中 關(guān)于事務(wù)提交的工作流程解釋。
0.begin transaction;
1.search & lock tuple for update;
2.update tuple & generate log;
3.write commit log;
4.flush logs;
5.unlock tuples;
6.commit & notify user;
容易發(fā)現(xiàn)，事務(wù)在寫出并且持久化日志的時候會帶來 IO，而 IO 通常而言比較耗時。如果事務(wù)中此前的操作都是內(nèi)存操作的話（在內(nèi)存數(shù)據(jù)庫或 LSM 結(jié)構(gòu)的系統(tǒng)中更明顯），這些 IO 的相對耗時就會顯得更大。IO 雖然可以做成異步的，但是在 IO 結(jié)束之前鎖都仍然會被持有，從而會阻塞其他的并發(fā)事務(wù)。如果可以把第 5 步釋放鎖的操作提前，放到第 4 步刷出日志之前，則可以讓并發(fā)操作同一記錄（試圖獲得鎖）的事務(wù) t2 提前開始執(zhí)行，從而可以增加系統(tǒng)的吞吐量。顯然，第 6 步的 commit 操作不能提前，仍然必須等到日志持久化完成之后才能通知用戶提交成功，因此用戶事務(wù)的響應(yīng)時間不會縮短。
現(xiàn)有 DBMS 沒有采用 ELR 的，作者文中認為是因為異步更高效，但根據(jù)前面的博客，MySQL 是做過嘗試的，但失敗了，同時也有臟讀的問題。
Evaluation of ELR
鎖競爭越激烈，ELR 帶來的性能提升越大；I/O 耗時越長（持有鎖的時間越長），ELR 帶來的性能提升越大。
Decoupling OS Scheduling from Log Flush Operations
log flush 造成的延遲來自兩個方面：
- I/O 造成的等待
- I/O 導(dǎo)致阻塞一個線程和解阻塞一個線程帶來的上下文切換
I/O 的時候 CPU 可以做其它的工作，但是調(diào)度的時候，CPU 是被占用了幾毫秒的時間的。
調(diào)度和上下文切換越來越重要的原因：
- 固態(tài)硬盤的速度越來越快，調(diào)度和上下文切換帶來的耗時占比越來越大。
- 指數(shù)增長的核數(shù)讓 OS 調(diào)度線程的時候考慮的更多，更復(fù)雜。
測試發(fā)現(xiàn)，隨著 client 線程的增加，系統(tǒng)耗時線性增長，所以單獨使用組提交并不能完全解決擴展性的問題，異步提交很快但是可能不安全。
Flush Pipelining
Flush Pipelining 的思想主要是將線程在事務(wù)提交后，與等待 flush 操作完成進行分離。分為以下步驟：
- 線程異步提交事務(wù)后，不等待 flush 操作完成，但是也不是直接就返回了，而是退出當前事務(wù)，將狀態(tài)寫入 log 里，然后繼續(xù)執(zhí)行其它事務(wù)。
- 一個守護線程按時、按次、按大小等策略自動觸發(fā) flush。
- flush 完成后，守護線程通知執(zhí)行線程 newly-hardened transactions，which eventually reattach to each transaction, finish the commit process and return results to the client.
這里具體的事務(wù)操作沒看懂，猜測是執(zhí)行線程重新執(zhí)行上次的事務(wù)，完成事務(wù)提交后面要做的工作，然后返回值給 caller 函數(shù)。hardened 的意思貌似是指日志寫到磁盤上，而不是緩沖區(qū)中。
產(chǎn)生日志記錄后 abort 掉的事務(wù)也必須 hardened 才能回滾。
TODO 有點沒看懂
Evaluation of Flush Pipelining
略
Scalable Log Buffer Design
大部分數(shù)據(jù)庫引擎使用 ARIES 的一個變體，給每個 log 記錄一個唯一的 Log Sequential Number (LSN)。LSN 編碼了記錄的磁盤位置，同時作為數(shù)據(jù)頁寫到磁盤的時間戳，還作為指向內(nèi)存和磁盤中的 log 記錄的指針。LSN 也可以用來做 log buffer 中的地址，這樣一來生成一個 LSN 的同時也就預(yù)留了 buffer 中的空間。
為了保證數(shù)據(jù)庫的一致性，ARIES 對 LSN 有嚴格排序要求。技術(shù)上并不需要全局排序來保證正確性，正確的偏序又可能太復(fù)雜且互相依賴，不值得作為性能優(yōu)化的備選項。
插入一條記錄到 log buffer 中包括如下三個階段：
- LSN generation and log buffer acquire.
線程必須先申請打算寫 log 進去的空間。雖然 LSN 是個線性操作，但是很快且可預(yù)測，除非一些異常情況，比如 buffer wraparound 和 buffer 滿。 - Log record insertion.
線程把 log 寫進之前申請的空間。 - Log buffer release.
事務(wù)釋放 buffer，從而允許 log manager 把 log 中的記錄寫到磁盤上。
最簡單的方法，log insert 之前獲取到 log 的鎖，這個鎖只有一個，然后做完 2，3操作后，釋放 buffer 的同時釋放這個鎖。但很明顯，這樣做就把 insert log 線性化了，并發(fā)高的時候就成了性能瓶頸；同時，如果 log record 大小不同，那么這部分工作的性能損耗就不可預(yù)測。
解決這個問題的思路：使得 insert log 操作和并發(fā)數(shù)、log record 的大小無關(guān)。
Consolidating Buffer Allocation
log record 由一個標準的 header 和任意數(shù)據(jù)載荷組成。log buffer 分配申請由兩個連續(xù)的請求組成，內(nèi)容也是一樣的形式。利用這一點，通過類似組提交的思想，把多個 buffer 分配申請進行合并，從而擴大吞吐量。
TODO 看不懂。擴展了 elimination-based backoff 的思想，同時利用 elimination trees 和 backoff。。。
TODO 看不懂。When elimination is successful threads satisfy their requests without returning to the shared resource at all, making the backoff very effective. For example, stacks are amenable to elimination because push and pop requests which encounter each other while backing off can cancel each other directly via the elimination array
and leave.
遇到 log insert 競爭的線程，回退到一個叫 consolidation array 的地方，合并它們的寫操作，再嘗試對 log buffer 進行寫操作。這里叫 consolidation 而不是 elimination 是因為，線程在合并請求后，還要進行協(xié)調(diào)：最后一個執(zhí)行 insert 的線程得釋放自己組的 log buffer。
這樣一來，log buffer 支持的最大并發(fā)數(shù)就變成了數(shù)組的容量，而不是系統(tǒng)內(nèi)的線程數(shù)。
這里的 allocation 首先揭示了一個思想，后面也用到了 insert 上：一個線程嘗試去鎖 buffer 的時候，如果沒有鎖，這個線程就拿到鎖，執(zhí)行自己的操作，再釋放鎖；如果這個時候鎖被占用著的，那么這個線程就回退到一個 consolidation array，在里面繼續(xù)嘗試拿鎖。不同的是，這個時候如果再來一個請求，這個請求也進入 consolidation array，然后兩個整合、協(xié)調(diào)一下，計算一共要分配多大的空間，誰去申請這個空間，可能是根據(jù)自己寫的 record 大小來決定誰釋放這個空間（不過我感覺這種簡單的機制不靠譜，因為萬一來個調(diào)度，record 小的可能后做完，所以并不靠譜）。做完之后，繼續(xù)嘗試獲取鎖。這個時候再來個請求的話，如上。
但是作者并沒有講一個 consolidation array 內(nèi)是怎么并發(fā)執(zhí)行對 buffer 的寫操作的，看圖的話應(yīng)該是并發(fā)執(zhí)行的，但是 buffer 的執(zhí)行應(yīng)該是線性的。感覺圖畫的有問題。個人理解是將多個寫操作合并成一個寫操作了。
總之，只有第一個線程需要請求分配 buffer ，只有最后一個線程需要等待釋放 buffer。但是也存在一個問題，如果兩組線程先后嘗試寫 log，第一組的第一個線程鎖了 buffer 后，寫很大一個 record，這時候第二組還是得等。并發(fā)性只是被保證在了同一組內(nèi)。
Decoupling Buffer Fill
因為 buffer fill 操作不是必須順序的 (records 不會重疊)，并且有不同的耗時，可以考慮把這些操作從關(guān)鍵路徑上移出來。只要線程以 LSN 順序釋放它們寫入的區(qū)域，線程可以安全地以任意順序?qū)戇@些區(qū)域。
作者修改了原來的算法，線程一旦分配到 buffer 之后就釋放鎖。這樣做了之后，就要解決 buffer 釋放的問題。Buffer 釋放的操作必須以 LSN 順序來避免在 record 之間產(chǎn)生 gap；Recovery 必須在遇到第一個 gap 的時候就停下來，在一個 crash 中，gap 之后的操作都會丟失掉。雖然無鎖，但是每一個線程都必須等它前面的 region 被釋放之后才能釋放自己的 region。
這里的思想有點類似于樂觀鎖。所有線程都先樂觀地寫，只有在需要同步的時候才同步，這里“同步”即是前面的 region 必須先寫完。為什么要保證這個順序要求，可能是為了 crash failover 的考慮：如果用一個類似 CountDownLatch 的實現(xiàn)，一旦 crash，因為不知道哪些寫完了，所以這個 CountDownLatch 上對應(yīng)的操作都得被作廢了。如果保證以 LSN 順序來寫，哪里 crash 掉是知道的。
這樣一來，就解決了第二組遇上一個寫大 record 的另一組線程，必須一直等別人寫完才能自己開始寫的情況。并發(fā)性得到了提高。
但是因為釋放操作有依賴關(guān)系，整體上還是會被寫大 log 的拖累，可能會導(dǎo)致大量線程等著前序線程釋放。（這誰頂?shù)米“?jpg）
Putting it all Together: Hybrid Log Buffer
前面提到的包括兩個工作：
- 一個基于整合隊列的方法來減少進入臨界區(qū)的線程數(shù)
- 一種分離策略使得線程能在臨界區(qū)外寫 log buffer
組合起來，就能使得整體性能相對來說，不對并發(fā)數(shù)和 log record 大小敏感。
下面解釋一下這個圖：
幾種優(yōu)化措施的原理和對耗時的影響
- (B) 是基準對照，箭頭入口表明操作被提交的時間，可見短時間內(nèi)來了三個操作，第一個操作拿到鎖后，往 buffer 里寫，然后釋放；然后第二、第三個操作順序執(zhí)行。
- (C) 是采用了整合隊列后的示例。這里第一個操作是第一組線程，因為這里只有它一個線程，申請分配 log space 是它，申請完了后寫 record 也是它，釋放鎖的還是它。
第二組操作等到第一組操作釋放鎖后，第二組操作所有的線程被組合成一個整合隊列，由其中第一個線程去申請鎖，申請 log space，然后隊列里的線程以不知道的某種并發(fā)方式都開始往 buffer 里寫 record，然后最后一個寫完的釋放鎖。 - (D) 是采用了分離 buffer insert 之后的示例。來一個請求，除了在申請分配 buffer 空間的時候經(jīng)歷短暫的串行執(zhí)行，就執(zhí)行一個請求。各自寫各自的區(qū)域，寫完了，檢查一下前面的區(qū)域?qū)懲隂]有，沒寫完了就等，寫完了就釋放自己寫的 region，這樣下一個寫完的線程才能釋放自己的 region。
- (CD) 組合兩種策略。與 D 類似，但是現(xiàn)在后面的兩個線程被劃分到同一個 consolidating array 里，所以這兩個線程可以并發(fā)執(zhí)行寫 log 操作。
Performance Evaluation
略
Appendix
Details of the Log Buffer Algorithms
baseline
一個最簡單、最直接的 log insert實現(xiàn)由以下幾個步驟組成:
- 獲取到一個全局鎖
- 進入臨界區(qū)
2.1 一個線程申請分配 log buffer 空間
2.2 寫 record 到 buffer 里
2.3 釋放 buffer，增加一個專用指針的指，讓這次寫入操作對負責 flush 的守護線程可見。 - 釋放鎖
這個算法有兩個問題：
- 競爭程度與工作線程數(shù)量線性相關(guān)
- 臨界區(qū)的（時間）長度與持有鎖的工作現(xiàn)場的工作量線性相關(guān)
Consolidation array
Consolidation-based backoff 目的是為了減少競爭，同時更重要的是，讓性能與訪問 log 的線程數(shù)無關(guān)。
主要的數(shù)據(jù)結(jié)構(gòu)是一個固定大小的數(shù)組，用來讓線程合并請求。線程首先以非阻塞的方式請求鎖，而不是無條件地等。什么意思呢？如果成功了，那就直接執(zhí)行 log insert，與上面提到的算法一樣。如果失敗了，那么線程就回退到 consolidation array ，位置 index 用一個 offset 變量來表示。
第一個進入 consolidation array 的線程是這個 array 的擁有者，下面稱為 leader。所有在 array 里等待獲取鎖的線程是一個組，leader 繼續(xù)嘗試獲取鎖并一直阻塞。一旦進入臨界區(qū)，leader 讀取 group 的 size，通過一條原子寫操作標記這個 array 已經(jīng)關(guān)閉了。
leader 然后請求分配 buffer 空間，在開始寫 buffer 之前通知其它組員。同時，組內(nèi)的線程通過組大小來推測自己在 meta-request （TODO 沒看懂）中的相對位置。leader 匯報 LSN 和 buffer 的位置，其余線程就可以計算自己的 LSN 和 buffer 的位置。每一個線程寫完自己的 record，就對 group 的 size 減1，返回。最后一個返回的，即檢測到 size = 0 的，釋放掉 buffer 上的鎖（即全局鎖）。
關(guān)閉后的 array 仍然不可被后續(xù)的線程訪問，因為要等 array 里的線程完成寫 record 操作。為了避免新到的線程一直等著，在 array 關(guān)閉的時候，每個 slot 上的線程釋放掉 array 里的數(shù)據(jù)結(jié)構(gòu)，相當于清空 array，讓后續(xù)的線程可以進入。
Decoupled buffer fill
分離 buffer 寫操作可以減少臨界區(qū)的（時間）長度，競爭的程度就不會隨著 log record 的大小的增長而加劇。具體實現(xiàn)如下：
- 一個線程獲取到 log 的鎖，生成 LSN，分配 buffer 空間。
- 釋放鎖
- 所有線程各自往自己的 region 里寫 log record。每個線程都自旋等待自己的前序 region 寫完后再釋放自己的 region。釋放操作就是將當前寫完的 offset 增加，其它線程通過對比 offset 來判斷前面的是否寫完了。
Consolidation-based Backoff
Slot Join Operation
slot_join 函數(shù)包括以下幾個步驟：
- 線程獲取到一個隨機的 offset，得到 array 里對應(yīng)的 slot 的數(shù)據(jù)結(jié)構(gòu)
- 查看 slot 是否 open，如果否的話，返回步驟 1 里，重新申請一個 slot。
這里引入了不確定性，因為隨機到的 slot 開沒開完全取決于隨機到的 offset。
- open 后通過 CAS 來更新當前 slot 的狀態(tài)，表明被占用。如果失敗的話，需要回退到步驟 2。
- 返回 <slot, offset> pair。
Slot close operation
在 leader 獲取到 buffer 的鎖后，關(guān)閉 group 來計算需要申請多大的 buffer，同時防止后續(xù)線程在已經(jīng)提交分配申請后又加入到 group 里。
這個操作是通過使用一個原子交換，返回當前狀態(tài)，并賦一個 PENDING 的新值。這個狀態(tài)改變，會讓后續(xù)調(diào)用 slot_join 方法的線程都失敗，但是大部分的線程不會遇到失敗的情況，因為一個 slot 關(guān)閉的時候，這個 slot 經(jīng)過短暫的操作，前面已經(jīng)提到，就把 slot 給空出來了。線程會試探整個 array，直到找到一個空 slot。因為 array 很大，所以基本上都能一發(fā)入魂。TODO 沒看懂The pool allocation need not be atomic because the caller already holds the log mutex. 一個 slot 關(guān)閉后，函數(shù)返回整個組的大小，用來讓調(diào)用者知道申請多少空間。
Slot notify and wait operations
Slot release and free operations
Delegated Log Buffer Release and Skew
對線程釋放 buffer region 的順序要求，造成了一個潛在的性能問題。許多很小的寫操作可以跟很大的寫操作并發(fā)執(zhí)行，但是需要等大的寫完了才能釋放自己的 region。TODO 沒看懂 Buffer and log file wraparounds complicate matters further, because they prevent threads from consolidating buffer releases. 而這些 wrapping buffer 的釋放必須被識別出來并單獨處理，因為它們會在 log flush 的時候產(chǎn)生額外的工作。
TODO 沒看懂
CDME 算法比 CD 更健壯，但是沒必要。幾乎所有 records 都很小且大 record 出現(xiàn)的頻率很低，在一般情況下，因為復(fù)雜的實現(xiàn)，反而會導(dǎo)致系統(tǒng)吞吐率的降低。但是，對于一些奇奇怪怪的場景，這個算法還是提供穩(wěn)定的保證的。
Sensitivity to consolidation array size
線程數(shù)與 consolidation array 的大小的關(guān)系。理想情況下，性能應(yīng)該只跟硬件有關(guān)，而與線程數(shù)無關(guān)。線程很多的時候，實驗表明，3-4 個 slots 最好，文中用的 4 個；線程很少的時候，這個時候無所謂。
原因：TODO 沒看懂 The optimal slot number corresponds closely with the number of threads required to saturate the baseline log which the consolidation array protects
A Case Against Distributed Logging
分布式的日志不適合用在數(shù)據(jù)庫中，因為依賴太多，幾乎無法有效地跟蹤。所以作者認為，為了解決 log buffer 上的競爭，這個思路是 unattractive 和 unfeasible的。
