[轉]Berkeley DB實作分析

計劃實作一個開源的KV資料庫——Simple DB

實作一個開源KV資料庫的想法來源于對目前項目中所使用的K-V資料庫使用情況的不滿意。

先介紹一下我們的目前項目，作為本文的背景：

較為底層的分布式運作平台，使用C/C++實作的Actor模型（異步消息傳遞系統）

資料schema簡單靈活，使用key-value能夠很好表示。

資料庫有大量的讀寫請求，有事務需求，資料丢失容忍度很低。

目前，從衆多的KV和NOSQL存儲産品中，我們使用了Berkeley DB作為底層的存儲引擎。

為什麼選擇BDB呢？

1.與傳統的RDBMS相比，簡單K-V存儲的Berkeley DB（再加入“嵌入式”直接庫連結的特性）有着優越的性能，容易滿足我們大量讀寫（尤其是大量寫）的需求。

2.作為一個嵌入式的K-V資料庫，Berkeley DB曆史悠久（目前由Oracle所有），穩定且久經考驗，文檔豐富，輔助工具全面。這是我們之是以在衆多的開源K-V(Nosql)資料庫中選擇BDB的首要原因：靠譜。

3.第三個選擇BDB的原因是事務支援：作為為數不多的能夠提供ACID事務支援的K-V資料庫，BDB對事務支援提供了豐富的支援：從不同的隔離級别、不同的持久化保證以及分布式事務2PC的prepare模型等，可配置程度很高。

BDB哪些方面不能達到我們的需求？

1.仍然是性能。作為K-V資料庫，BDB的性能依然達不到我們的目标：由于有足夠大的記憶體作為緩存，讀操作的性能基本沒問題，但寫操作（尤其是大量應用的事務寫）的性能堪憂。

使用Auto-commit（每條寫作為一個獨立的事務），一條記錄的寫延時接近于1~10ms。

顯示開啟事務後，寫操作有了極大改善：10~100us（因為不需要即時sync到硬碟），但事務送出操作依然極為耗時。

有人可能會說，你可以調節BDB事務的持久化保證的程度，比如在送出時設定：

DB_TXN_WRITE_NO_SYNC，在送出時隻寫log到硬碟，不sync（隻有OS Crash才會丢資料）

或者更快一些，使用DB_TXN_NOSYNC，連同步調syscall write的開銷都省下來（但App crash可能會丢資料）

我們目前的項目是一個底層的運作時平台，對資料丢失的敏感程度是很高的，不像一些常見的網際網路應用。我們既需要事務的Durability支援，也需要高的寫性能。

2.我們的資料模型相對簡單：Key-Value存儲，需要事務的Atomicity支援批量修改，需要事務的Durability保證，可能需要Prepare語義支援分布式事務。

不需要對資料庫通路的并發支援。目前核心系統是一個基于線程池的異步系統，資料庫的寫操作和送出操作應該由獨立線程來完成，不應阻塞有限的池中線程。是以我們可以不需要并發支援而使用單獨線程操作資料庫。

至于事務的Consistency和Isolation以及各種複雜的鎖協定（尤其是BDB中惱人的page級别的鎖粒度），在不需要并發通路的資料庫中也不需要。

這樣的需求，或許通過詳細的配置和tuning也能在BDB上實作，但BDB畢竟太大太複雜（一方面BDB為了通用的需求，實作複雜，難以了解内部機理；一方面是配置複雜），以至于步履蹒跚。

與其繼續鑽研BDB的各種配置來适配目前特殊的需求，不如輕裝上陣，自己實作一個項目特定的底端存儲，由于目标和需求少兒明确，實作起來要簡單很多，預期能夠獲得比BDB更高的性能。

這個資料庫暫時取名為Simple DB，其主要需求和大緻實作如下：

1.Key-Value存儲，使用Hash實作（可能需要使用linear hash)，不采用實作較為複雜的B+樹

2.嵌入式，通過連結方式直接使用，不适用其他IPC。隻考慮Linux 2.6平台，暫不考慮其他平台。

3.主要支援get/set/traverse操作

（如果支援delete操作，也不會釋放或重新利用檔案空間：重利用釋放的空間向來是一個複雜的問題，既要保證效率，又要避免碎片。最多提供一個database compress工具進行檔案的壓縮處理。）

4.每個資料庫包括：資料檔案，索引檔案和日志檔案，不支援并發通路。

5.支援事務，但隻提供Atomicity和Durability語義。（使用write-ahead logging）

支援跨同一目錄下多個資料庫的事務，可能會提供事務的prepare語義。

6.暫不考慮replication支援，不支援shading（由應用層自行完成）

希望資料庫如其名，簡單高效。

Keep it simple, stupid!

Berkeley DB實作分析(1) ——多程序下資料庫環境的恢複：DB_REGISTER

一個程序在打開Berkeley DB環境時（DbEnv::open），通常需要恢複環境（DB_RECOVER）以確定資料的完整性。

但DB_RECOVER的語義是強制恢複，即任何情況下都會删除舊環境并建立新環境，以確定環境的正确性。

1.每次程式啟動時都進行recovery是沒有必要的：

1. 環境很有可能是正常的，每個通路程序退出時都正确地使用了DbEnv::close()。

2. 很多時候，Environment的重建是一個比較耗時的行為，增加了恢複服務的等待時間，影響了系統的可用性。

恢複環境時，會在BDB環境的描述區域（dbinc/region.h中的REGENV結構，該結構映射到__db.001檔案的最開始N個位元組）設定panic标記，并删除所有的區域檔案（__db.001 ~ __db.006），而BDB庫中的幾乎所有操作都會檢測panic标記（傳回錯誤或抛出DbRunRecoveryException異常）。

3. 是以，目前仍然在正常環境下工作的程序将會由于一個指定了DB_RECOVER程序的加入而被迫退出。

2.怎樣設定某一個環境為“需要時才進行recovery”？

所有打開同一個環境的程序，如果指定了DB_RECOVER，需要同時指定DB_REGISTER。

DB_REGISTER保證隻在檢測到data corruption時進行資料庫環境的恢複。

對于成百上千兆的環境檔案，顯然不可能對内容進行逐位元組驗證。那麼BDB怎樣檢測到環境檔案的data corruption呢？

3.Process Registry實作原理:

既然沒法逐位元組驗證環境檔案内容，不妨換個思路：

如果可以確定之前所有的程序都是正常退出（正确調用DbEnv::close），則可以確定環境檔案的内容是一緻的。

于是register檔案粉墨登場，每個程序打開/關閉環境時都會在此留下自己的記錄：

程序打開環境時：在register檔案的某一行記錄自己的process id，并使用檔案鎖(fcntl)鎖住該行的第一個byte

正常退出環境時：将其記錄“擦除”，并解鎖。

register檔案所有的行都是等寬的，每一行不是一個process ID slot，就是一個空記錄（empty slot），格式如下：

__db.register :

|<--- 25 bytes --->|

                    12345 # prcess ID slot 1

X                            # empty slot

                     12346 # process ID slot 2

                     12347 # process ID slot 3

X                             # empty slot

X

這樣每個程序打開環境時，都會周遊register檔案所有的行：

1. 該行符合empty slot的格式（X後面跟24個空格），則跳過

2. 該行是一個process ID slot，且該pocess ID不等于該程序本身的pid，則檢查是否可以鎖住該行的第一個byte：

lock失敗：說明該行對應的process依然在環境中，正常并跳過該行

lock成功：說明該行對應的process已經crash（而沒有來得及更新register檔案），但程序退出時由OS回收了所擁有的檔案鎖，需要進行recover

3. 該行不夠寬度（隻可能發生在最後一行）：說明程序在更新register檔案時被interrupt，需要進行recover。

如果不需要進行recovery，則再次周遊register檔案所有行：

1. 找到一個empty slot并且可以lock該行的第一個byte，寫入自己的process id

2. 直到讀到register檔案末尾。

等寬行的優勢在此展現：結合檔案鎖，很好地保證了多個程序不會同時寫一個檔案的同一個位置。

4.其他實作方案：

使用flock也可以在某個檔案上加上建議鎖。這個方法要求每個程序都需要建立并鎖住自己的register檔案，退出環境時解鎖并删除該register檔案。這樣程序打開環境時隻需周遊所有其他程序的register檔案，并確定是否已上鎖即可。

但這種方式可能會産生大量的檔案（程序數量*打開的DbEnv數量），按作者的話說：

"but flock would require a separate file for each process of control (and probably each DbEnv handle) in the database environment, which is fairly ugly."

5.多程序下恢複環境依然有風險：

當一個程序檢查register檔案并決定要恢複資料庫環境時，會将整個環境設定panic标志，此時所有正在該環境上操作的程序都會檢測到錯誤并退出。

但是仍然會有一個corruption的時間視窗：當一個程序進行了panic檢測并将要進行寫操作時，另一個程序決定恢複環境。（這個時間視窗是BDB本身就存在的，與是否進行register檢測無關。）

按作者的話說，"That's very, very unlikely to happen."，并且有一個可能的解決辦法，在一個程序決定要recover時，向環境内的已有程序發送SIGKILL以強制其退出，缺點在于該程序不一定有這樣的權限，而且不能準确地判斷該程序是否已死。是以該方法預設是不采用的。

/* in file env/env_register.c */
#define DB_ENVREG_KILL_ALL 0      

小議同步IO ：fsync與fdatasync

對于提供事務支援的資料庫，在事務送出時，都要確定事務日志（包含該事務所有的修改操作以及一個送出記錄）完全寫到硬碟上，才認定事務送出成功并傳回給應用層。

一個簡單的問題：在*nix作業系統上，怎樣保證對檔案的更新内容成功持久化到硬碟？

1.  write不夠，需要fsync

一般情況下，對硬碟（或者其他持久儲存設備）檔案的write操作，更新的隻是記憶體中的頁緩存（page cache），而髒頁面不會立即更新到硬碟中，而是由作業系統統一排程，如由專門的flusher核心線程在滿足一定條件時（如一定時間間隔、記憶體中的髒頁達到一定比例）内将髒頁面同步到硬碟上（放入裝置的IO請求隊列）。 因為write調用不會等到硬碟IO完成之後才傳回，是以如果OS在write調用之後、硬碟同步之前崩潰，則資料可能丢失。雖然這樣的時間視窗很小，但是對于需要保證事務的持久化（durability）和一緻性（consistency）的資料庫程式來說，write()所提供的“松散的異步語義”是不夠的，通常需要OS提供的同步IO（synchronized-IO）原語來保證：

1 #include <unistd.h>
2 int fsync(int fd);      

fsync的功能是確定檔案fd所有已修改的内容已經正确同步到硬碟上，該調用會阻塞等待直到裝置報告IO完成。     PS：如果采用記憶體映射檔案的方式進行檔案IO（使用mmap，将檔案的page cache直接映射到程序的位址空間，通過寫記憶體的方式修改檔案），也有類似的系統調用來確定修改的内容完全同步到硬碟之上：

1 #incude <sys/mman.h>
2 int msync(void *addr, size_t length, int flags)      

msync需要指定同步的位址區間，如此細粒度的控制似乎比fsync更加高效（因為應用程式通常知道自己的髒頁位置），但實際上（Linux）kernel中有着十分高效的資料結構，能夠很快地找出檔案的髒頁，使得fsync隻會同步檔案的修改内容。

2. fsync的性能問題，與fdatasync

除了同步檔案的修改内容（髒頁），fsync還會同步檔案的描述資訊（metadata，包括size、通路時間st_atime & st_mtime等等），因為檔案的資料和metadata通常存在硬碟的不同地方，是以fsync至少需要兩次IO寫操作，fsync的man page這樣說：

"Unfortunately fsync() will always initialize two write operations : one for the newly written data and another one in order to update the modification time stored in the inode. If the modification time is not a part of the transaction concept fdatasync() can be used to avoid unnecessary inode disk write operations."

多餘的一次IO操作，有多麼昂貴呢？根據Wikipedia的資料，目前硬碟驅動的平均尋道時間（Average seek time）大約是3~15ms，7200RPM硬碟的平均旋轉延遲（Average rotational latency）大約為4ms，是以一次IO操作的耗時大約為10ms左右。這個數字意味着什麼？下文還會提到。

Posix同樣定義了fdatasync，放寬了同步的語義以提高性能：

1 #include <unistd.h>
2 int fdatasync(int fd);      

fdatasync的功能與fsync類似，但是僅僅在必要的情況下才會同步metadata，是以可以減少一次IO寫操作。那麼，什麼是“必要的情況”呢？根據man page中的解釋：

"fdatasync does not flush modified metadata unless that metadata is needed in order to allow a subsequent data retrieval to be corretly handled."

舉例來說，檔案的尺寸（st_size）如果變化，是需要立即同步的，否則OS一旦崩潰，即使檔案的資料部分已同步，由于metadata沒有同步，依然讀不到修改的内容。而最後通路時間(atime)/修改時間(mtime)是不需要每次都同步的，隻要應用程式對這兩個時間戳沒有苛刻的要求，基本無傷大雅。     PS：open時的參數O_SYNC/O_DSYNC有着和fsync/fdatasync類似的語義：使每次write都會阻塞等待硬碟IO完成。（實際上，Linux對O_SYNC/O_DSYNC做了相同處理，沒有滿足Posix的要求，而是都實作了fdatasync的語義）相對于fsync/fdatasync，這樣的設定不夠靈活，應該很少使用。    

3. 使用fdatasync優化日志同步

文章開頭時已提到，為了滿足事務要求，資料庫的日志檔案是常常需要同步IO的。由于需要同步等待硬碟IO完成，是以事務的送出操作常常十分耗時，成為性能的瓶頸。

在Berkeley DB下，如果開啟了AUTO_COMMIT（所有獨立的寫操作自動具有事務語義）并使用預設的同步級别（日志完全同步到硬碟才傳回），寫一條記錄的耗時大約為5~10ms級别，基本和一次IO操作（10ms）的耗時相同。

 我們已經知道，在同步上fsync是低效的。但是如果需要使用fdatasync減少對metadata的更新，則需要確定檔案的尺寸在write前後沒有發生變化。日志檔案天生是追加型（append-only）的，總是在不斷增大，似乎很難利用好fdatasync。   且看Berkeley DB是怎樣處理日志檔案的：

1.每個log檔案固定為10MB大小，從1開始編号，名稱格式為“log.%010d" 2.每次log檔案建立時，先寫檔案的最後1個page，将log檔案擴充為10MB大小 3.向log檔案中追加記錄時，由于檔案的尺寸不發生變化，使用fdatasync可以大大優化寫log的效率 4.如果一個log檔案寫滿了，則建立一個log檔案，也隻有一次同步metadata的開銷

參考資料：

1. linux man pages for fsync/msync/open 2. 《Unix環境進階程式設計》 3. Berkeley DB Source Code

深入了解Berkeley DB的鎖：理論與實踐篇

本文僅僅從應用的角度來談一談Berkeley DB中鎖相關的理論與實踐經驗，接下來還會有一篇部落格來介紹BDB鎖的内部實作。

鎖粒度

除了Queue Access Method，其他所有的Access Pattern都是頁級鎖（page-level locking），而Page大小預設為作業系統filesystem的block size（Linux下預設為4K）。

（可以通過減少Page大小，使一個Page上容納更少的記錄來減少頁級鎖粒度，但是減小Page會影響資料庫的IO效率，在缺乏足夠性能資料支撐的情況下，很少會這樣做。）

　　BDB的頁級别的鎖粒度一向是比較惱人的問題，由于Queue并不常用（key為邏輯記錄号，value為定長），而一般使用BDB的都需要較為松散自由的key-value存取，來滿足靈活（Schema-Free)的資料，注定了使用BDB大部分情況下都要和頁級鎖打交道。

　　頁級鎖的存在大大增加了鎖沖突的可能，減少了高并發情況下的吞吐量。對于讀-寫沖突，可以根據業務邏輯的需要選擇“髒讀"（uncommited read）或者使用快照事務（snapshot）來避免，但是對于寫-寫沖突，鎖争用無法避免，應用程式需要随時做好應付死鎖的準備。關于這兩點，下文會詳細說明。

鎖協定與隔離級别

　　預設情況下，BDB的事務采用的是嚴格的二階段鎖協定(strong strict 2-phase locking, SS2PL)，即随着事務的進行不斷擷取鎖（讀鎖/寫鎖），直到事務結束（commit/abort）時才會釋放所有的鎖。

　　實際上，SS2PL的限制過于強烈，如果在某些情況下不需要如此之高的隔離程度，可以配置BDB不同的隔離級别（Isolation level）以放寬SS2PL的限制，減少鎖争用以提高整個系統的吞吐。

Berkeley DB有4種隔離級别以供選擇：

（注意：所有的隔離級别都不允許”髒寫“，即一個事務更改另一個事務未經送出的資料，這是事務隔離的最基本保證）

1. Read-Uncommitted ：允許”髒讀“（一個事務可以讀取另一個事務修改中但未送出的資料）。這是能夠配置的最低的隔離級别，讀寫沖突最小。

2. Read-Committed ：不允許”髒讀“，基本上和預設級别一樣，除了事務遊标（Cursor）在移動時會釋放之前的持有的鎖。

3. Serializable：（預設級别）可序列化，遵守SS2PL。相對于Read-Committed級别，遊标的鎖在其關閉之前不會釋放，保證了遊标的”可重複讀“（repeatable reads）。

4. Snapshot：快照隔離，能夠保證和Serializable一樣的隔離效果。snapshot事務讀DB時不會請求讀鎖，大大減少讀-寫沖突。

談談隔離級别的選擇：

Berkeley DB對隔離級别的配置是很靈活的，允許統一資料庫環境下的不同的事務采用不同的隔離級别，隻要顯示在資料層開啟了該級别的支援。

1. 對于資料一緻性要求不高的場景（如大部分的Web應用），對大部分non-critical資料的讀寫可以采用Read-Uncommitted級别。該級别下，由于允許”髒讀“，讀寫幾乎沒有沖突（為什麼是”幾乎“，下文還會說明），但讀到的資料不一定正确。

2. Read-Committed和預設級别幾乎沒有差別，除了Cursor的鎖協定。

　　在預設級别下，如果使用事務遊标周遊資料庫，遊标會逐漸擷取所有的讀鎖，極大阻塞其他事務的進行，使用Read-Committed級别會使遊标使用鎖耦合（lock-coupling）協定，在擷取到下一頁的鎖的同時釋放上一頁的鎖，減少了鎖的占用。

3. 預設級别不多說，适合大部分對資料一緻性要求高的場景，如處理關鍵/敏感資料的應用

4. Snapshot在保證預設級别隔離程度的同時減少了讀寫沖突，适用于多個讀事務/單個寫事務的應用場景。

　　快照隔離的原理是多版本并發控制（Multi-version Concurrency Control），所有事務都會采用Copy-on-write的協定，即需要寫資料時，先将原頁面的内容拷貝到一個新的頁面上，在新的頁面上進行修改，送出時再合并到資料庫中：由于寫事務沒有在原頁面上修改，保證了快照事務可以安全地讀取該頁面——實際上，快照事務讀資料時不需要加讀鎖。

　　快照隔離不是萬能的。1.耗記憶體：由于需要寫前複制，資料庫需要的Cache數量大約是不開啟MVCC支援前的2倍（可以使用db_stat -m檢視目前資料庫使用cache的情況）2.依然不能解決寫-寫沖突。

鎖類型

除了常見的讀/寫鎖，為了減少鎖沖突、提高吞吐量，Berkeley DB提供了多種粒度的意向鎖（multi-granularity intention lock）。

BDB的鎖相容矩陣（conflict matrix）如下圖所示：（橫欄表示目前持有的鎖類型，豎欄表示加鎖請求，勾表示鎖沖突）

圖1：BDB的鎖相容矩陣

iRead/iWrite/iRW都是意向鎖，意向鎖是為了支援階層化鎖（hierarchical locking），舉例說明：

如果我們需要寫某資料某頁的某一條記錄，我們将會發出一連串原子的鎖請求：給DB加iWrite鎖，給page加iWrite鎖，給record加Write鎖。在每個鎖請求都被允許的條件下，加鎖才算成功，否則放棄之前步驟已經擷取的鎖。

我們可以看出，對單條記錄的讀寫操作在DB和Page層加的都是意向鎖，意向鎖比讀/寫鎖弱的多，與之沖突的鎖類型大大減少。隻有DB級的全局操作（如周遊全記錄、修改）才會在DB加上标準的讀/寫鎖。

在這種階層化場景下，意向鎖使得鎖的粒度被減少了，同時加鎖時檢查的效率被提高了。

uRead/iwasWrite不是意向鎖，而是BDB為了支援”髒讀“（Read-Uncommitted）而使用的特殊的鎖類型。

iwasWrite：在Read-Uncommitted級别下，所有事務的寫操作先擷取寫鎖，在Page上完成具體的修改後，寫鎖降級（downgrade）為iwasWrite——”已寫鎖“：iwasWrite的鎖相容清單和普通的寫鎖基本相同：除了允許uRead。

uRead：在Read-Uncommitted級别下，允許”髒讀“的事務在讀資料時，會嘗試擷取該資料的”髒讀鎖“（uRead），在Page上完成一次完整的讀取後，釋放該uRead鎖（注意是完成讀取後即釋放，"髒讀鎖“是一種臨時鎖，不會被長期持有，想一想為什麼）

死鎖與死鎖檢測

決定使用事務的一刻起，我們注定要與鎖沖突進行無休止的戰争。正如前文所述：

1. 盡管我們可以設定各種隔離級别來減少讀-寫沖突，寫-寫沖突總是不可避免的。

2. 即使應用層能夠保證不會同時寫同一個邏輯記錄，頁級鎖的存在常常使這樣的努力成為徒勞：）

除了影響并發性能，鎖沖突帶來的另一個嚴重問題是死鎖。有兩種情形可能造成BDB的死鎖：

1. 資源的循環依賴：如線程1中的事務A持有Page1的鎖，想要擷取Page2的鎖；線程2的事務B持有Page2的鎖，想要擷取Page1的鎖：誰也不撒手。

2. ”自死鎖“：同一個線程中開啟了兩個事務，一個事務等待另一個事務的鎖，其實上是自己等待自己。

對于第一種死鎖，Berkeley DB提供了兩種死鎖檢測接口：

1. 自動檢測：env->set_lk_detect(reject policy)，每當一個加鎖請求即将被阻塞時，BDB都會周遊内部的鎖表（lock table）以檢測是否有死鎖發生。

如果有死鎖發生，一部分擁有鎖的事務将會被強制abort以解除死鎖（abort時會釋放所有已獲得的鎖）。可以指定BDB選擇abort事務的政策，預設情況下是随機，為了系統的吞吐量考慮，一般選擇abort掉擁有寫鎖數量最少的事務（DB_LOCK_MINWRITE），因為持有寫鎖多的事務一般是已經執行了更多工作的事務。

2. 手工檢測，如直接使用db_deadlock工具來檢測并解決目前的死鎖，在調試時極為有用。

然而對于第二種的“自死鎖”，BDB的死鎖檢測無能為力。根據我們項目中使用BDB的經驗來看，由于程式不慎而導緻的“自死鎖”還是比較常見的。

可以使用如下的方法判斷是死鎖還是“自死鎖”：

1. 使用db_stat -Co工具來列印目前資料庫的鎖表，檢視是否有鎖的循環依賴：

圖2：一個典型的死鎖：

圖3：一個典型的“自死鎖”：

2. 使用db_deadlock工具，如果是正常的死鎖，則一定可以被檢測并解除。

應用層政策

Design for failure:

在支援事務的資料庫中，死鎖是常态。一定要在系統設計中考慮到死鎖的可能，盡可能防止死鎖，并提供相應的容錯、重試的政策。

盡可能地防止死鎖：

1. 所有事務使用一緻地順序來擷取鎖

如按照固定的順序通路多個資料庫、按Key的順序重排（reorder）記錄寫入資料庫的次序

2. 在事務的最後通路熱點資源（hot spot），使其鎖持有時間盡可能短

容錯與重試：

在事務進行的任意一點，都有可能因為出現死鎖而被BDB終止。如果需要重試，必須回到原事務起點，開啟一個新事物并重新執行。

（這也是不鼓勵長事務的原因：除了長時間持有鎖影響了并發的其他事務，在發現死鎖時，長事務也相對較難找到一個起點，将之前的操作重演一遍）

參考資料

《Oracle Berkeley DB Programmer's Reference Guide》

《Oracle Berkeley DB API Reference for C++》

《Oracle Berkeley DB Getting Started with Transaction Processing for C++》

《Berkeley DB 死鎖的調試》  http://www.chenyajun.com/2008/06/29/21

文章來源：http://www.cnblogs.com/promise6522/tag/Berkeley%20DB/