Berkeley DB設計經驗

原文鏈接：http://www.aosabook.org/en/bdb.html

作者：Margo Seltzer 和 Keith Bostic

康威法則（Conway’s law）說明了設計反映了產生它的組織的結構。展開來說，我們也許會預見一款由兩個人設計和完成最初制作的軟件不僅會在一定程度上反映組織的結構，還會反映每一位帶來的內在偏見和哲學理念。我們中的一位（Seltzer）在文件系統和數據庫管理系統的世界中度過她的職業生涯。如果被問及于此，她會辯解說此二者基本上是等同物，進一步地，操作系統和數據庫管理系統實質上都既是資源管理器又是便利抽象層的提供者。它們的區別“僅僅”在于實現的細節。另一位（Bostic）則信仰軟件工程中基于工具的方法和基于簡單構造塊的組件構建方法，因為這樣的系統在各種重要“能力”方面總是優于單體式體系結構：可理解性、可擴展性、可維護性、可測試性和靈活性。

當把這兩種理念結合起來，你就不會奇怪我們花了過去二十年間的大部分時光共事于Berkeley DB（一個提供高速、靈活、可靠和可擴展的數據管理的軟件庫）了。Berkeley DB提供了人們所期待的傳統系統（例如關系型數據庫）中的大多數的同樣功能，但是打包方式不同。例如，Berkeley DB提供了按鍵值的和按順序的兩種快速數據訪問，同時還有事務支持和故障恢復。但是，它以庫的形式提供這些特性，與需要這些服務的應用程序鏈接到一起，而不是作為一個獨立的服務器應用提供服務。

在本章中，我們將要更深入地觀察Berkeley DB，看到它由一組模塊組成，每個模塊都體現了Unix的“把一件事做好”的哲學。嵌入了Berkeley DB的應用程序能夠直接使用這些模塊或者通過更加熟悉的操作獲取、存放和刪除數據項來間接使用它們。我們將集中關注體系結構——我們是如何開始的，我們設計了什么，我們在哪結束了以及為什么。設計能夠（而且一定將要）被強迫去適應和改變——重要的是隨時間的推移而維護原則和一致的愿景。我們也將簡要的談及長期軟件項目的代碼演進。Berkeley DB有超過20年的持續開發，這難免會給好的設計造成負面影響。

4.1 開端

Berkeley DB起源于Unix操作系統還專屬于AT&T的時代。那時有幾百種實用工具和函數庫的血統還帶有嚴格的許可限制。Margo Seltzer那時是加州大學伯克利分校的研究生，Keith Bostic是伯克利計算機系統研究組的一員。當時Keith正在從伯克利軟件發行版（BSD）中刪除AT&T的專屬軟件。

Berkeley DB項目開始于一個適度的目標——用一個新的、改進的、可同時支持內存和磁盤操作的哈希實現來替代內存哈希軟件包hsearch和磁盤哈希軟件包dbm/ndbm，以及允許不帶專有許可的自由分發。Margo Seltzer寫的哈希庫 SY91 基于Litwin的可擴展線性哈希研究成果。它宣稱采用了一種聰明的方法來達到哈希值和頁面地址之間的常量時間映射，以及處理較大數據的能力——大于底層的哈希桶或文件系統頁大小的項，通常是4到8KB。

如果哈希表很好，那么B樹加上哈希表將會更好。Mike Olson，也是加州大學伯克利分校的研究生，曾寫過一些B樹的實現，同意再寫一個。我們三個人把Margo的哈希軟件和Mike的B樹軟件轉換成了一套和存取方法無關的API，應用程序通過數據庫句柄來引用哈希表或B樹，句柄帶有讀取或修改數據的處理方法。

基于這兩種存取方法，Mike Olson和Marge Seltzer寫了一篇關于LIBTP（一個運行于應用程序地址空間的可編程事務函數庫）的研究論文 SO92 。

這套哈希和B樹函數庫以Berkeley DB 1.85的名稱被集成到了最終的4BSD發行版中。從技術上看，該B樹存取方法實現的是B+ link樹，不過在本章的后續部分我們將采用B樹一詞，因為它是存取方法的名稱。Berkeley DB 1.85的結構和API對用過Linux或BSD衍生系統的人而言很可能比較熟悉。

Berkeley DB 1.85沉寂了一些年，直到1996年Netscape與Margo Seltzer和Keith Bostic簽約來實現LIBTP論文中描述的全部事務設計并且實現一個生產質量級的版本。這項工作產生了Berkeley DB的第一個事務性版本，版本2.0。

Berkeley DB的后續歷史就是一個更簡單、傳統的大事年表了：Berkeley DB 2.0（1997）引入了事務；Berkeley DB 3.0 （1999）是一個重新設計的版本，增加了更多級別的抽象和間接性以支持不斷增長的功能；Berkeley DB 4.0 （2001）引入了復制和高可用；Oracle Berkeley DB 5.0 （2010）增加了SQL支持。

在寫作本文的時候，Berkeley DB 是世界上使用最廣泛的數據庫工具集，有幾億份部署的拷貝運行在從路由器、瀏覽器、郵件系統到操作系統的各種系統中。雖然已經有超過20年的歷史了，Berkeley DB 基于工具和面向對象的設計方法使得它可以增量改進和重構以滿足使用它的軟件的需求。

設計教訓1

對任何復雜的軟件包的測試和維護來說，將其設計和構建成帶有良好定義的API邊界的、一組互相協作的模塊至關重要。在有需求時，這些邊界能夠（而且必須！）移動，但是邊界總得存在。這些邊界的存在可以防止軟件變成一堆不可維護的意大利面條。Butler Lampson曾說過，計算機科學中的所有問題都可以通過添加一個間接層來解決。更確切的是，當被問及面向對象的東西是什么意思時，Lampson說這意味著能夠在一套API之后有多種實現。Berkeley DB的設計和實現體現了這種同一套接口之后允許多種實現的方法，提供了面向對象的觀感，雖然函數庫是用C實現的。

4.2 體系結構概述

本節我們將從LIBTP開始回顧Berkeley DB的體系結構，強調它演進中的關鍵問題。

圖4.1摘自Seltzer和Olson的原始論文，說明了原先的LIBTP體系結構；而圖4.2則展現了Berkeley DB 2.0設計時的體系結構。

 圖4.1：LIBTP原型系統的體系結構

 圖4.2：Berkeley DB 2.0預期的體系結構

LIBTP實現和Berkeley DB 2.0設計之間唯一顯著的區別是刪除了進程管理器（process manager）。LIBTP要求每個線程注冊到庫中，然后同步各個線程/進程，而不是提供子系統級的同步。正如4.4節中討論的那樣，原先的設計可能更好。

 圖4.3：實際的Berkeley DB 2.0.6體系結構

設計和實際發布的Berkeley DB 2.0.6（見圖4.3）在體系結構上的區別體現在后者實現了一個強壯的恢復管理器（recovery manager）。恢復子系統在圖中用灰色表示。恢復既包括用recovery框表示的驅動結構，也包括用于恢復存取方法所執行操作的重做（redo）和撤銷（undo）例程的集合。這些在圖中用“access method recovery routines”標注的橢圓形表示。與LIBTP中針對特定存取方法編寫日志和恢復例程不同，Berkeley DB 2.0中對恢復的處理是一種一致的設計。這個通用的設計也產生了不同模塊間更豐富的接口。

圖4.4展現了Berkeley DB 5.0.21的體系結構。圖中的數字表示表4.1中列出的API。雖然仍可以看出原始的體系結構的樣子，當前的體系結構體現了新模塊的增加，舊模塊的分解（例如log變成了log和dbreg），以及模塊間API的顯著增加。

經過十年多的演進，幾十個商業發布，以及幾百個新特性的增加之后，我們看到體系結構明顯比以前更復雜了。值得注意的關鍵點是：首先，復制（replication）在系統中增加了全新的一層，不過做得很清晰，就像前期的代碼一樣通過同樣的API與系統的其他部分交互。其次，log模塊被分成了log和dbreg（database registration）。在4.8節對此有更詳細的描述。第三，我們把所有模塊間的調用放到了一個以下劃線打頭的命名空間內，這樣應用軟件就不會與我們的函數名沖突了。我們在設計教訓6中對此進一步討論。

第四，日志子系統的API現在是基于游標的了（API logget不復存在，代之以API logcursor）。過去，Berkeley DB中在同一時刻讀寫日志的線程從來就沒有多于一個，因此函數庫中只有一個日志的當前掃描指針。這從來都不是一個好的抽象（但還可以工作），但有了復制之后它變得不可用了。就像應用層API用游標實現循環一樣，日志現在也通過游標來支持循環了。第五，存取方法中的fileop模塊提供了事務保護的數據庫創建、刪除和重命名操作。我們嘗試了多次以使得實現使人滿意（它仍然不是我們期望的那樣清晰），在許多次改造之后，我們把它抽成一個獨立的模塊。

設計教訓2

軟件設計絕對是迫使你自己在試圖解決問題前通盤考慮整個問題的幾種方法之一。有經驗的程序員采用不同的技術來達到這個目的：有些先寫第一版然后扔掉，有些寫出大量的手冊或設計文檔，其他的則設計出代碼模板并識別出每個需求，分派到一個具體的函數或一段注釋。例如，在Berkeley DB中，我們在寫代碼之前為存取方法和底層模塊創建了一份完整的Unix風格的手冊。不管采用的具體技術如何，在代碼調試開始后都很難想清楚程序的體系結構，更不要說大的體系結構變化通常會浪費前期的調試努力。軟件體系結構設計需要一種與代碼調試不同的思維方式，當你開始調試時的軟件體系結構通常就是你在該版本中將會交付的結構。

 圖4.4：Berkeley DB 5.0.21的體系結構

為什么把事務函數庫設計成多個模塊而不是為單一用途優化？針對這個問題有三個答案。首先，它促使一個更嚴謹的設計。其次，代碼中若沒有明顯的邊界，復雜的軟件包必然會惡化成為一堆不可維護的東西。第三，你不可能預見用戶使用你的軟件的所有方式，如果你授權用戶訪問軟件的內部模塊，他們將會用你從未想到過的方式來使用這些模塊。

在隨后的章節中，我們會討論Berkeley DB中的每個組件，理解它做了什么以及它在整個系統中的位置。

4.3 存取方法：B樹、哈希、記錄號和隊列

Berkeley DB的存取方法同時提供了基于變長和定長字節串的按鍵值查找和循環。B樹和哈希支持變長的鍵/值對。記錄號和隊列支持記錄號/值對（其中記錄號支持變長值而隊列僅支持定長值）。

Notes：Btree、Hash、Recno、Queue在這里屬于專用名詞，保留英文似乎更好。

B樹和哈希存取方法之間的主要區別在于B樹提供了鍵值引用的局部性，而哈希則沒有。這意味著對幾乎所有的數據集B樹都是合適的存取方法，而哈希存取方法則適合于大到連B樹索引都在內存中放不下的數據集。此時，把內存用來存放數據比存放索引要更好。1990年那時的內存比今天要小很多，這種權衡顯得更有道理。

記錄號和隊列之間的差別在于隊列以只支持定長值為代價來支持記錄級鎖定；記錄號支持變長對象，但和B樹以及哈希一樣，僅支持頁級鎖定。

我們最初把Berkeley DB設計成CRUD功能（創建、讀取、更新和刪除）是基于鍵的，而且是給應用的主要接口。后來我們增加了游標以支持循環。這個需求導致了函數庫中大量的重復代碼，造成了混亂和資源浪費。隨著時間的推移，這變得不可維護，我們把所有基于鍵的操作都轉換成了游標操作（現在，基于鍵的操作會分配一個緩存的游標，執行操作，然后將游標返回到游標池）。這是軟件開發中不斷重復的規則之一的應用：在你知道必須去做之前，不要以任何方式優化一條減少清晰度和簡潔性的代碼路徑。

設計教訓3

軟件體系結構不會優雅地老化。軟件體系結構的退化與軟件本身的改動數量成正比：缺陷修復會腐蝕軟件的層次，新特性會使設計產生應力。確定什么時候軟件體系結構退化到該重新設計或重寫一個模塊是一個很難的決定。一方面，在設計退化時，維護和開發變得更困難，最終變成一個老化的軟件。它的每次發布只能靠一群暴力測試者來維持。因為沒有人知道該軟件內部是怎么工作的。另一方面，用戶會強烈抱怨根本性改動帶來的不穩定和不兼容。作為一個軟件架構師，你唯一的保證是無論選擇那條路，總有人對你不滿。

我們略去了對Berkeley DB存取方法內部的詳細討論。他們實現了眾所周知的B樹和哈希算法（記錄號是B樹代碼之上的一層；隊列是一個文件塊查找功能，盡管它被記錄級鎖定弄復雜了。）

4.4 函數庫的接口層

隨著時間的推移，我們增加了更多的功能，發現應用程序和內部代碼都需要相同的上層功能（例如內部的表連接操作要用到多個游標來遍歷行，應用程序也會用游標來遍歷同樣這些行。）

設計教訓4

你怎么命名變量、方法和函數，采用什么注釋或代碼風格并不重要；也就是說有大量的格式和風格“足夠好”。重要和非常重要的是命名和風格保持一致。有經驗的程序員從代碼格式和對象命名中得到大量信息。你應當將命名和風格的不一致視為某些程序員將時間和精力花費來欺騙另外的程序員，反之亦然。不能遵循內部編碼規范是一種該被解雇的行為。

正因如此，我們把存取方法的API分拆為準確定義的層次。這些接口例程層處理所有必要的通用錯誤檢查，函數特有的錯誤檢查，接口追蹤以及其他如自動事務管理等任務。當應用程序調用進Berkeley DB時，它們調用的是基于對象句柄內的方法的第一層接口例程（例如Berkeley DB游標的“put”方法就是調用_dbcputpp接口來更新數據項的）。我們用后綴“pp”來標識所有可以被應用程序調用的函數。

Berkeley DB的接口層處理的任務之一是追蹤哪些線程正在Berkeley DB庫內運行。這是必要的，因為有些內部的Berkeley DB操作只可以在庫內沒有線程運行時被執行。Berkeley DB通過在每個庫API開始時標記線程在庫內運行，在API調用返回時清除標記來追蹤線程。這些進入/退出檢查總是在接口層進行檢查，與此類似的是檢查調用是否在復制環境中執行。

很明顯的一個問題是“為什么不傳遞一個線程標識符到函數庫，這難道不是更簡單嗎？”答案是肯定的，那將容易很多，我們當然希望已經那么做了。可是，這種變化將導致每個Berkeley DB應用程序，以及每個應用程序中對Berkeley DB的大部分調用，這在大部分情況下需要應用程序的重構。

設計教訓5

軟件架構師必須慎重選擇升級路徑：用戶會接受小的改動來升級到新的版本（如果你保證升級期間只出現編譯時錯誤也就是明顯的錯誤；升級的變化絕不應該導致難以理解的失敗。）但是要做出真正根本性的變化，你必須承認這是一個新的基礎代碼，所以需要現有用戶的移植。顯然，新的基礎代碼和應用移植在時間或資源上算都不便宜，但是二者都不會像告訴他們一個大改動實際是一次小升級那樣惹惱你的用戶群。

接口層負責的另一個任務是事務的產生。Berkeley DB支持一種每個操作都隱含一個事務的模式（這可以省去應用程序顯式創建和提交事務的麻煩）。支持這種模式需要在應用程序未指定自己的事務調用API時，自動為其創建一個事務。

最后，所有的Berkeley DB API都需要參數檢查。在Berkeley DB中有兩種類型的錯誤檢查——判斷數據庫是否在前一個操作中被破壞了的通用性檢查，以及我們是否正在一個復制狀態變化的中間（例如，改變哪個副本以允許寫入）。也有針對具體API的檢查：標記的正確使用，參數的正確使用，選項的正確組合，以及其他可以在真正執行請求的操作前檢查的錯誤。

API相關的檢查都被封裝在以“arg”為后綴的函數中。因此，與游標的put方法相關的錯誤檢查就位于dbcputarg中，它被函數dbcput_pp調用。

最后，當所有參數檢驗和事務產生完成時，我們調用真正執行操作的輔助方法（在上述例子中是_dbcput），這也是我們內部調用游標put功能時用的函數。

這種模塊拆分在一段開發密集期間逐漸形成，那時我們正在決策需要采取哪些行動以支持復制環境。在基礎代碼中迭代開發不少次后，我們把前面所說的所有檢查都抽出來以使得以后發現問題時更容易修改。

4.5 底層模塊

在存取方法之下有四個模塊：緩沖區管理器、鎖管理器、日志管理器和事務管理器。我們將分別討論每個模塊，不過它們有一些共同的體系結構特性。

首先，所有的這些子系統都有自己的API，而且最初每個子系統都有自己的對象句柄，子系統的所有方法都基于該句柄。例如，你可以用Berkeley DB的鎖管理器來處理你自己的鎖或者寫自己的遠程鎖管理器。你也可以用Berkeley DB的內存管理器來處理自己的共享內存中的文件頁。隨著時間的推移，這些子系統特性的句柄被從API中刪除了以簡化Berkeley DB應用程序。雖然這些子系統仍然是可以被獨立于其他子系統使用的獨立模塊，它們現在共享一個通用的對象句柄，也就是DB_ENV“環境”句柄。這個體系結構的特性強化了分層和通用性。雖然層不時在移動，而且還有些地方一個子系統跨越到另一個子系統，讓程序員把系統的不同部分理解為各自獨立的軟件產品是一個不錯的原則。

其次，所有的這些子系統（實際上，所有的Berkeley DB函數）都給上層返回錯誤碼。作為一個函數庫，Berkeley DB不能通過定義全局變量侵入應用程序的名字空間。更何況強制錯誤從調用棧通過單一路徑返回強化了好的程序員紀律。

設計經驗6

在函數庫的設計中，重視名字空間是至關重要的。用你的函數庫的程序員應該不需要去記住幾十個函數、常量、結構、全局變量的保留名字以避免應用和函數庫的命名沖突。

最后，所有這些子系統都支持共享內存。因為Berkeley DB支持在多個運行的進程之間共享數據庫，所有共享數據結構都必須放在共享內存中。這個選擇的最明顯的結果是內存數據結構都必須采用一對基地址和偏移量而不是指針，以使得基于指針的數據結構都可以在多進程的環境下工作。換句話說，不通過指針做間接轉換，Berkeley DB函數庫必須通過基地址（共享內存段被映射到進程中的內存地址）加上一個偏移量（給定數據結構在映射的內存段中的偏移位置）來創建指針。為了支持這個特性，我們寫了一個BSD版本的queue軟件包，它實現了各種各樣的鏈表。

設計教訓7

在我們寫共享內存的鏈表軟件包之前，Berkeley DB的工程師們手工編寫了共享內存中的各式不同的數據結構，而且這些實現容易出錯和很難調試。共享內存鏈表軟件包，仿照BSD鏈表軟件包（queue.h）實現，代替了所有這些努力。在它一旦調試通過后，我們再也不需要去調試共享內存鏈表問題了。這體現了三個重要的設計原則：第一，如果一個功能出現了多次，那就寫出共享的函數并使用它們，因為對于任何特定功能而言，兩份拷貝的存在一定說明其中一份實現得不正確。其次，當你開發一系列通用的例程時，給這些例程寫一個測試集，這樣你就可以分開調試它們。第三，代碼越難以書寫，單獨書寫并維護它就越重要。因為基本上不可能防止外圍代碼感染和侵蝕一份代碼。

4.6 緩沖區管理器：Mpool

Berkeley DB的Mpool子系統是文件頁面的內存緩沖池，它隱藏了這樣一個事實：內存是一種有限資源，當處理超過內存大小的數據庫時，需要函數庫在磁盤和內存間來回移動數據庫頁。將數據庫頁緩存在內存中使得原先的哈希庫大大優于先前的hsearch和hdbm實現。

雖然Berkeley DB的B樹存取方法是一個相當傳統的B+樹實現，樹節點之間的指針用頁面號而不是內存指針表示，因為函數也把磁盤頁格式用作內存頁格式。這種表示的優勢在于頁面可以不需要格式轉換就能被從緩存刷出到磁盤，劣勢在于遍歷索引結構時需要（代價稍高的）重復的緩沖池查找而不是（代價稍低的）內存操作。

底層假設Berkeley DB索引的內存表示實際上是磁盤上持久數據的緩存，這還有其他的一些對性能的影響。例如，每當Berkeley DB訪問一個緩存的頁面時，首先要pin住內存中的頁面。Pin操作防止任何其他的線程或進程將該頁從內存池中換出。即便整個索引結構都可以在緩沖中放下，并且從不需要被刷新到磁盤，Berkeley DB仍然在每個操作時要獲取和釋放這些pin，因為Mpool底層的模型是一個緩存而不是一個持久存儲。

4.6.1 Mpool的文件抽象

Mpool假設它位于文件系統之上，通過其API暴露文件抽象。例如，DBMPOOLFILE句柄表示一個磁盤文件，提供了從文件中獲取頁面和寫頁面到文件的方法。雖然Berkeley DB也支持臨時的和純粹的內存數據庫，這二者也是通過DBMPOOLFILE 句柄引用的，因為底層都是Mpool抽象層。Get和put方法是主要的Mpool API：get確保頁面在緩存中，獲得頁面上的一個pin并返回指向頁面的指針。當函數庫用完頁面時，put調用unpin頁面并允許頁面被換出。 Berkeley DB的早期版本不區分讀訪問的pin頁面和寫訪問的pin頁面。然而，為了增加并發性，我們擴展了Mpool的API以允許調用者指示更新頁面的意圖。區分讀訪問和寫訪問的能力對多版本并發控制的實現至為重要。為讀訪問pin住的臟頁面是可以被寫入磁盤的，而為寫訪問pin住的臟頁面就不能，因為后者可能在任何時刻都處于不一致的狀態。

4.6.2 先寫日志

Berkeley DB采用先寫日志（WAL）實現故障恢復的事務機制。術語先寫日志定義了一個策略，要求任何修改所對應的日志記錄都要先于它實際的數據更新被寫到磁盤。 Berkeley DB采用WAL作為其事務機制對Mpool有重要的影響，Mpool必須在通用的緩存機制以及支持WAL協議的需要之間找到設計的平衡點。

Berkeley DB將日志順序號（LSN）寫到所有數據頁上，以記錄每個特定頁的最近更新所對應的日志記錄。實施WAL需要Mpool在寫頁面到磁盤前驗證頁面上的 LSN對應的日志記錄已經安全地記錄到磁盤了。設計的挑戰在于提供該功能而不要求所有Mpool的客戶采用和Berkeley DB完全一致的頁面格式。Mpool通過提供一系列的set（和get）方法指引其行為來解決這個挑戰。DBMPOOLFILE的方法setlsnoffset提供了頁面內的字節偏移，告訴Mpool到哪兒去找LSN以實現WAL。如果這個方法從未被調過，Mpool就不實現WAL。類似的，setclearlen方法告訴Mpool頁內有多少字節表示元數據，在緩存中創建一個頁面前需要顯式的清除掉這些字節。這些API允許Mpool提供了支持Berkeley DB事務所必要的功能，而不是迫使Mpool的所有用戶去自己實現。

設計教訓8

先寫日志是另一個提供封裝和分層的例子，即使是這個特性不會對其他的軟件有用：畢竟有多少程序會關心緩存中的LSN？不管怎樣，這個原則是有用的，而且使得軟件容易維護、測試、調試和擴展。

4.7 鎖管理器：Lock

像Mpool一樣，鎖管理器也被設計成一個通用模塊：它被設計成支持對象層次的封鎖（例如獨立的數據項、數據項所在的頁面、甚至是一組文件）的一個層次式鎖管理器（參看GLPT76）。在描述鎖管理器的特性時，也將同時解釋Berkeley DB是怎么用它的。然而，就像Mpool一樣，其他的應用程序可以用完全不同的方式使用鎖管理器，不過那沒問題——它被設計得很靈活并支持很多不同的用法。

鎖管理器有三個關鍵的抽象：“封鎖者”標識鎖是代表誰獲取的，“封鎖對象”標識被鎖定的項，以及一個“沖突矩陣”。

封鎖者是32位無符號整數。Berkeley DB把這個32位的名字空間劃分為事務性封鎖者和非事務性封鎖者（雖然這種區分對鎖管理器而言是透明的）。當Berkeley DB使用鎖管理器時，它把范圍從0到0x7fffffff之間的ID分給非事務性封鎖者，把從0x80000000到0xffffffff的分給事務性封鎖者。例如，當應用程序打開數據庫時，Berkeley DB獲取該數據庫上的一個長的讀鎖以保證它在被使用時沒有其他的線程刪除或重命名它。因為這是一個長鎖，所以它不屬于任何一個事務，持有該鎖的封鎖者就是非事務性的。

任何使用鎖管理器的應用程序都需要分配封鎖者ID，所以鎖管理器的API同時提供了DBENV->lockid和DBENV->lockid_free調用用以分配和釋放封鎖者。因此應用程序不需要實現自己的封鎖者ID分配器，雖然他們也可以這么做。

4.7.1 鎖對象

鎖對象是表示被封鎖對象的任意長度的不透明（opaque）字節串。當兩個不同的封鎖者試圖鎖住一個特定對象時，他們采用同樣的不透明字節串來引用該對象。也就是說，應用程序負責定義描述對象的不透明字節串的約定。

例如，Berkeley DB采用一個DBLOCKILOCK結構來描述其數據庫鎖。這個結構包含三個字段：文件標識符、頁號和類型。

在幾乎所有情況下，Berkeley DB都只需要描述它想鎖定的特定文件和頁面。Berkeley DB在數據庫創建時給每個庫分配一個唯一的32位數字，并把它寫到數據庫的元數據頁中。以后就在Mpool、封鎖、日志子系統中將它用作數據庫的唯一標識符。這就是我們在DBLOCKILOCK結構中引用的fileid字段。不出所料，頁面號表示我們想要鎖定的特定數據庫中的某個頁。當我們引用頁面鎖時，我們將結構中的type字段設置為DBPAGELOCK。然而，我們我們也可以在需要時鎖定其他類型的對象。正如前面提到的，我們有時會鎖住數據庫句柄，它就需要DBHANDLELOCK類型。DBRECORDLOCK類型使我們可以處理隊列存取方法中的記錄級鎖定，而DBDATABASELOCK類型則讓我們鎖定整個數據庫。

設計教訓9

Berkeley DB選擇采用頁面級別的鎖定是有足夠理由的，但是我們發現該選擇有時也是有問題的。當一個線程在修改數據庫頁面中的一條記錄時，頁級鎖定將不允許其他線程修改同一頁面中的其他記錄，這限制了應用程序的并發性。而只要兩個線程不在修改同一個記錄，記錄級鎖定就允許這樣的并發。頁級鎖定增強了穩定性，因為它限制了可能的恢復路徑（在恢復過程中，頁面總是在幾個狀態之一，而不是在允許多個記錄被同時在頁內增加或刪除時導致的無數的可能狀態）。因為 Berkeley DB是為嵌入式系統使用的，一旦有破壞，不會有數據庫系統管理員來修復問題，我們選擇了穩定性而不是更好的并發。

4.7.2 沖突矩陣

我們將討論的封鎖子系統的最后一個抽象是沖突矩陣。沖突矩陣定義了系統中不同類型的鎖以及它們之間的交互。讓我們將持有鎖的實體稱為持有者，請求鎖的稱為請求者，并且假設持有者和請求者具有不同的封鎖者ID。沖突矩陣就是一個以[請求者][持有者]為下標的數組，其中如果沒有沖突的格子為0，表明請求的鎖可以被授予，如果有沖突則為1，表明請求不能被授予。

鎖管理器含有一個缺省的沖突矩陣，它碰巧正是Berkeley DB所需要的。然而，應用程序可以自由定義自己的封鎖模式和沖突矩陣以滿足它自己的需求。對沖突矩陣的唯一要求是它必須是方的（它有相同的行數和列數）并且應用程序用從0開始的整數描述其封鎖模式（例如讀、寫等）。表4.2列出了Berkeley DB的沖突矩陣。

4.7.3 對層次封鎖的支持

在解釋Berkeley DB沖突矩陣中不同的封鎖模式之前，讓我們談談封鎖子系統是怎么支持層次封鎖的。層次封鎖指的是一種鎖定同一層次結構中不同項的能力。例如文件包含頁面，而頁面包含不同的元素。當在一個層次封鎖系統中修改一個頁面元素時，我們僅想鎖住該元素；如果我們要更新頁面中的每個元素，僅鎖定頁面將更有效，而如果我們要修改文件中的每個頁面，最好的就是鎖定整個文件。此外，層次封鎖必須理解容器的層次，因為鎖定一個頁面也意味著在某種程度上鎖定了文件，文件中有頁面在被修改時，你不能修改頁面所在的文件。

那么問題在于怎么允許不同的封鎖者在不同層級進行封鎖又不引起混亂。答案是一種叫做意向鎖的結構。封鎖者獲取容器上的一個意向鎖以說明將要鎖定容器內的東西的意向。于是，獲取頁面上的讀鎖隱含著獲取文件上的一個意向讀鎖。類似的，要寫頁面中的一個元素，你必須同時獲取頁面和文件上的意向寫鎖。在上面的沖突矩陣中，iRead、iWrite和iWR鎖都是意向鎖，它們分別表示讀的意向、寫的意向和同時讀寫的意向。

因此，在處理層次封鎖時，不是在某個東西上請求單一的一個鎖，可能有必要請求很多鎖：最終要操作的實體上的鎖以及所有包含該實體的實體的意向鎖。這個需求引入了Berkeley DB中的DBENV->lockvec接口，它接受一個鎖請求的數組然后原子性的授予（或拒絕）。

雖然Berkeley DB內部沒有采用層次封鎖，它利用了這個能力來指定不同的沖突矩陣，以及一次性指定多個鎖請求。在提供事務支持時，我們采用缺省的沖突矩陣；但采用另一個沖突矩陣以支持不帶事務的簡單的并發存取和恢復支持。我們采用DBENV->lockvec來處理鎖的耦合，這是一種增強B樹遍歷的并發性的技術Com79。在鎖耦合中，你只用持有鎖足夠的時間以獲取下一個鎖。也就是說，你只需要鎖住一個內部的B樹頁面足夠長的時間以讀到選擇和鎖定下一級頁面的信息。

設計教訓10

Berkeley DB的通用設計在我們增加并發數據存儲功能時獲得了很好的回報。最初Berkeley DB只提供了兩種操作模式：要么沒有寫并發性的運行，要么支持全部事務支持。事務支持給開發人員帶來了一定程度的復雜性，我們發現有些應用程序想提高并發性又不想要全事務支持的額外代價。為了提供這個特性，我們增加了API級別的封鎖以允許并發性，同時保證沒有死鎖。這需要一個新的和不同的封鎖模式以支持游標。與其在鎖管理器中增加特殊目的的代碼，我們能夠創建另外一種鎖矩陣以支持API級鎖定只需要的封鎖模式。于是，僅僅通過將鎖管理器配置得不同，我們就能提供我們需要的封鎖支持。（不幸的是，修改存取方法就不那么容易了，存取方法中還有相當大的一部分代碼要處理這種并發存取的特殊模式）

4.8 日志管理器：Log

日志管理器提供了一個結構化的、僅限追加的文件的抽象。與其他模塊一樣，我們試圖設計出一個通用的日志設施，然而日志子系統可能是我們做的最不成功的一個模塊。

設計教訓11

當你發現一個體系結構上的問題而又不想立即修復時，你其實傾向于放過它。請記住被蠶食而死和被大象踩住都一定會要你的命。別太猶豫而不去修改整個框架來改進軟件結構，而且當你做出修改時，不要以為你以后會清理它而做出不完全的修改——一次做完并繼續向前進。就像經常說的，“如果你現在沒有時間去做，以后也不會有時間去做”。此外，在你修改框架時，同時也要寫測試結構。

日志在概念上很簡單：它拿到不透明的字節串并將它們順序地寫到文件中，給每筆日志一個稱作日志順序號（LSN）的唯一標識。此外，日志必須提供通過LSN 的高效的正向和反向遍歷和檢索。這里有兩個需要慎重處理的地方：第一，日志必須要保證在任何可能的故障后處于一個一致的狀態（這里“一致”指的是未損壞的日志記錄的連續序列）；其次，因為日志記錄被寫到穩定存儲中以支持事務的提交，日志的性能通常會限定事務性應用的性能。

因為日志是一個僅限追加的數據結構，它可能會無限制增長。我們把日志實現為一組順序編號的文件，因此，日志空間可以通過簡單的刪除舊日志文件來回收。在這種多文件的日志結構下，我們把LSN定義為文件號和文件內偏移組成的對。于是，給定一個LSN，日志管理器定位日志記錄就很簡單了：它移動到給定日志文件的給定偏移，并返回該位置的日志記錄。但是日志管理器怎么知道從該位置返回多少字節呢？

4.8.1 日志記錄格式

日志必須保留每個日志記錄的元數據以保證給定一個LSN，日志管理器可以判斷待返回的記錄的大小。至少，它需要知道日志記錄的長度。我們假定每個日志記錄都有一個包含記錄長度的日志記錄頭、前一個日志記錄的偏移位置（以支持反向遍歷），以及一個日志記錄的校驗和（以標識日志的損壞和日志文件的結束）。這些元數據足夠讓日志管理器維護日志記錄的順序了，但是這還不足以支持恢復的實現；該功能要靠日志記錄中的內容以及Berkeley DB怎么用這些日志記錄來實現。

Berkeley DB通過日志管理器在數據庫中更新數據項前寫下數據的前像和后像 HR83 。這些日志記錄包含了重做或撤銷數據庫中操作的足夠信息。Berkeley DB利用這些信息處理事務撤銷（即，在事務撤銷時撤銷該事務的所有影響）和應用故障或系統故障后的恢復。

除了讀寫日志記錄的API之外，日志管理器還提供了一個強制將日志記錄刷出到磁盤的API（DBENV->logflush）。該API允許Berkeley DB實現WAL——在Mpool中回收頁面前，Berkeley DB檢查頁面的LSN并且要求日志管理器保證該LSN已經在穩定存儲上了。只有這樣，Mpool才會將頁面寫到磁盤。

設計教訓12

Mpool和Log用內部的處理方法來處理WAL，在某些情況下，方法的聲明比本身的代碼還要長，因為代碼除了比較兩個整數之外什么也不做。為什么弄這些不太重要的方法僅僅去維護一致的層次呢？因為如果你的代碼不是面向對象到了讓你牙疼的話，它還不夠面向對象。每段代碼應該做少量的事情并且應該有個鼓勵程序員在小的功能塊之上構建新功能的上層設計。如果說我們在過去的幾十年中學到了什么軟件開發的東西的話，那就是我們構建和維護大量軟件的能力是很弱的。構建和維護大量軟件是困難和容易出錯的，作為軟件架構師，你必須盡你所能、盡早、盡量頻繁的最大化軟件結構表達的信息。

Berkeley DB在日志記錄上施以結構以減少恢復的難度。大部分Berkeley DB的日志記錄描述的是事務性更新。也就是說，大部分日志記錄對應于以事務身份所做的數據庫頁面更新。這個描述有助于我們識別哪些是Berkeley DB必須附加到每條日志記錄的元數據：數據庫、事務和記錄類型。事務標識和記錄類型字段在每個記錄的同一位置出現。這使得恢復系統可以抽取出日志類型并且將記錄分發到可以解釋和執行相關動作的合適的處理者。事務標識讓恢復過程識別日志記錄屬于哪個事務，使得在恢復的不同階段中，它知道該記錄是否可以被忽略還是必須被處理。

4.8.2 打破抽象層

還有一些“特殊的”日志記錄。檢查點記錄可能是這些特殊記錄中最熟悉的。做檢查點是使數據庫的磁盤狀態在某個時間點一致的過程。換句話說，Berkeley DB為了性能盡量將數據庫頁緩存在Mpool中。然而，這些頁面最終必須被寫到磁盤，而我們越早做這個，在應用或系統故障時我們就能更快得恢復。這意味著需要在做檢查點的頻率和恢復時間長短之間權衡：系統做檢查點越頻繁，它就能更快得恢復。做檢查點是一個事務性功能，因為我們將在下一節介紹它的細節。就本節而言，我們將談談檢查點記錄以及日志管理器如何在成為一個獨立的模塊和一個專用的Berkeley DB組件之間掙扎的。

總之，日志管理器本身沒有記錄類型的概念，因此在理論上，它不需要區分檢查點記錄和其他的記錄——它們都僅僅是需要日志管理器寫到磁盤的不透明字節串。實際上，日志管理器維護了元數據，說明了它確實理解一些記錄的內容。例如，在日志啟動過程中，日志管理器檢查所有它能找到的日志文件并且識別出最近寫過的日志文件。它假定所有該文件之前的所有日志文件都是完整無缺的，然后開始檢查最近的日志文件并確定它含有哪些有效的記錄。它從日志文件的開頭開始讀，直到遇到一個不能正確校驗的日志記錄頭才停下來，這意味著到了日志尾或日志文件損壞了。這兩種情況都確定了日志的邏輯結尾。

在讀取日志以找到當前日志尾的過程中，日志管理器抽取Berkeley DB的記錄類型以尋找檢查點記錄。作為對事務系統的“幫忙”，它把找到的最后一個檢查地點記錄的位置保留在日志管理器的元數據中。也就是說，事務系統需要找到最后的檢查點，但是與其讓日志管理器和事務管理器都去讀取整個日志來干這件事，事務管理器把該任務代理給了日志管理器。這是一個違背抽象邊界而換來性能的典型例子。

這個權衡意味著什么呢？假設Berkeley DB之外有個系統在使用日志管理器。如果它碰巧寫了一個檢查點日志類型對應的值到了Berkeley DB放置自己的記錄類型的同一個位置，那么日志管理器將把該記錄識別為一個檢查點記錄。然而，除非應用程序找日志管理要這些信息（通過直接讀取日志元數據中的cachedckplsn字段），這些信息不會影響任何事情。簡而言之，這既不是一個有害的對分層的違背，也不是一個精明的性能優化。

文件管理部分是日志管理器與Berkeley DB其他模塊間的分離比較模糊的另一個例子。就像前面提到的一樣，大部分Berkeley DB的日志記錄需要標識一個數據庫。每條日志記錄都可能包含數據庫的全名，但這樣在日志空間的角度看將是很昂貴的，也比較難看，因為恢復將需要把這個名字映射到某種形式的句柄以便能夠訪問數據庫（要么是一個文件描述符要么是一個數據庫句柄）。實際上，Berkeley DB在日志中用一個整數標識數據庫，稱為一個日志文件ID，并實現了一系列的函數，統稱為dbreg（database registration的簡稱），來維護文件名和日志文件ID的映射。當數據庫被打開時，這個映射的持久化版本（記錄類型為 DBREG_REGISTER）被寫到日志記錄中。然而，我們也需要這個映射的內存表示以支持事務的撤銷和恢復。哪個子系統應該負責維護這個映射呢？

理論上，文件到日志文件ID的映射是一個高層的Berkeley DB函數；它不屬于任何一個子系統，子系統不應有全局概念。在最初的設計中，這些信息被留在日志子系統的數據結構中，因為日志系統看起來是最好的選擇。然而，在不斷地發現和修復實現中的缺陷時，這個映射支持被從日志子系統代碼中抽取出來形成了它自己小子系統，有了自己的面向對象的接口和私有的數據結構。（回過來看，這些信息邏輯上本應該被放在Berkeley DB環境信息本身中，在所有子系統之外。）

設計教訓13

極少存在“不重要的Bug”這樣的事情。確實，不時會有一些筆誤，但通常一個Bug意味著有人沒有完全理解他們在做的事情并實現錯了。當你修復Bug時，不要僅看現象，要看底層的原因。如果你愿意的話，還應該看看產生誤解的原因，因為這樣可以更好的理解程序的體系結構并發現設計本身更本質的缺陷。

4.9 事務管理器：Txn

我們的最后一個模塊是事務管理器，它把各個獨立的模塊聯系在一起以提供事務的ACID屬性（原子性、一致性、隔離性和持久性）。事務管理器負責事務的開始和結束（要么提交，要么撤銷），協調日志管理器和緩沖區管理器做事務檢查點并組織恢復。我們將按順序逐一討論這些領域。

Jim Gray發明了ACID這個縮寫詞來描述事務提供的關鍵屬性 Gra81 。原子性的意思是一個事務中執行的所有操作在數據庫中表現為一個單一的單元——它們要么都在數據庫中，要么都不在。一致性的意思是事務把數據庫從一個邏輯一致的狀態轉移到另一個。例如，如果應用程序要求每個員工都必須被安排到一個已在數據庫中定義了的部門，那么一致性屬性將會確保它（在事務正確書寫時）。隔離性的意思是從每個事務的角度看，它就像是在沒有任何其他并發事務在運行時順序執行的。最后，持久性的意思是一旦事務被提交，它就保持提交狀態——沒有故障可以使得已經提交的事務消失掉。

事務子系統在其他子系統的協助下確保ACID屬性。它采用傳統的事務開始、提交和撤銷操作來分隔事務的開始點和結束點。它也提供了一個prepare調用以實現兩階段提交，兩階段提交是在分布事務之間提供事務屬性的技術，本章對此沒有描述。事務開始要分配一個新的事務標識符并返回一個事務句柄DB_TXN 給應用程序。事務提交要寫一個提交日志記錄然后強制刷出日志到磁盤（除非應用程序表明它愿意放棄持久性以換取更快的提交處理），保證即使在出現故障時，事務也會被提交。事務撤銷會反向讀取屬于對應事務的日志記錄，撤銷該事務已經做的每個操作，將數據庫退回到該事務開始前的狀態。

4.9.1 檢查點處理

事務管理器也負責做檢查點。在學術界有很多不同的技術來做檢查點 HR83 。 Berkeley DB采用了模糊檢查點的一個變種。從根本上看，做檢查點需要需要將緩沖區從Mpool中寫到磁盤。這是一個很可能代價昂貴的操作，重要的是系統同時能繼續處理新的事務以避免長時間的服務中斷。在檢查點開始時，Berkeley DB檢查當前活動的事務集合以找到它們當中任何一個所寫的最小的LSN。該LSN就是檢查點LSN。事務管理器然后要求Mpool去刷新緩存中的臟頁到磁盤，寫這些緩沖可能會觸發日志的刷出操作。在所有這些緩沖都被安全寫到磁盤后，事務管理器會寫一個包含檢查點LSN的檢查點記錄。該記錄表明在檢查點 LSN之前的日志記錄描述的所有操作現在都安全的存在磁盤上了。因此，在檢查點LSN之前的日志記錄就不再需要用來恢復了。這有兩重意思：第一，系統可以回收檢查點LSN之前的任意日志文件。第二，恢復只需要處理檢查點LSN之后的日志記錄。因為檢查點LSN之前的日志記錄所描述的更新已經被反映在磁盤狀態中了。

注意在檢查點LSN和實際的檢查點記錄之間可能存在很多的日志記錄。這沒什么問題，因為那些記錄描述的操作邏輯上發生在檢查點之后，因此如果系統故障了還是需要做恢復的。

4.9.2 恢復

事務性難題的最后一個部分是恢復。恢復的目標是將磁盤數據庫從一個可能不一致的狀態轉到一個一致的狀態。Berkeley DB采用一個相當傳統的兩遍模式，大致對應于“相對于最后的檢查點LSN，撤銷所有沒有提交的事務并重做所有已經提交的事務”。后面將介紹更多的細節。

Berkeley DB需要重新構造從日志文件ID到實際的數據庫之間的映射以便它可以重做和撤銷數據庫中的操作。日志中包含了DBREGREGISTER日志記錄的完整歷史，但是數據庫會長時間處于打開狀態，我們不想保留整個數據庫打開期間的日志文件，而需要一個更有效的方法來訪問這個映射。在寫檢查點記錄前，事務管理器寫下一組DBREGREGISTER記錄來描述當前的從日志文件ID到數據庫的映射。在恢復期間，Berkeley DB使用這些日志記錄去重新構造文件映射。

當恢復開始時，事務管理器檢查日志管理器的cachedckplsn值來判斷最后一個檢查點記錄的位置。該記錄包含檢查點的LSN。 Berkeley DB需要從該檢查點LSN開始恢復，但是為了做這件事，它需要重新構造在該檢查點LSN處的日志文件ID映射；這些信息在該檢查點LSN之前的檢查點記錄中。因此，Berkeley DB必須查找在該檢查點LSN之前的最近一個檢查點記錄。檢查點記錄不僅包含了檢查點LSN，還有前一個檢查點的LSN（以支持這個查找過程）。恢復從最近的檢查點開始，采用每個檢查點記錄中的prev_lsn字段去反向遍歷日志直到它找到了一個出現在檢查點LSN之前的檢查點記錄。算法如下：

ckp_record = read (cached_ckp_lsn) ckp_lsn = ckp_record.checkpoint_lsn
cur_lsn = ckp_record.my_lsnwhile (cur_lsn > ckp_lsn) {     ckp_record = read (ckp_record.prev_ckp)     cur_lsn = ckp_record.my_lsn}

從前面的算法找到的檢查點開始，恢復算法順序讀取到日志尾以重新構造日志文件ID映射。當它到達日志尾時，映射應該準確的對應系統停止時存在的映射。也是在這個階段中，恢復算法跟蹤遇到的每個事務提交記錄，記錄它們的事務標識。所有有日志記錄但是其日志標識未在事務提交記錄中出現的事務要么是被回滾了，要么是從未完成從而也應被視為回滾了。當恢復到日志尾時，它調轉方向并開始反向讀取日志。對于遇到的每個事務日志記錄，它抽取出事務標識并構造出已經提交事務的列表，以決定該記錄是否該被回滾。如果它找到事務標識不屬于提交的事務，就抽取出記錄類型并且調用一個該日志記錄的恢復例程，指導它去撤銷對應的操作。如果該記錄屬于一個已提交的事務，恢復在反向掃描時忽略它。反向掃描一直進行到檢查點LSN（Notes：這里有個腳注）。最終，恢復再以正向方式最后讀一遍日志，這次重做所有屬于已提交事務的日志記錄。當這最后一個階段完成時，恢復做一個檢查點。此時，數據庫完全一致了，可以開始運行應用程序了。

總之，恢復可以被總結為：

1. 找到最近檢查點記錄中檢查點LSN之前的那個檢查點
2. 正向讀取日志以恢復日志文件ID映射并構造出已提交事務的列表
3. 反向讀取日志到檢查點LSN，撤銷未提交事務的所有操作
4. 正向讀取日志，重做已提交事務的所有操作
5. 做檢查點

理論上，最后一個檢查點是不必要的。實際上，它減少了未來的恢復的時間并使得數據庫處于一個一致的狀態。

設計教訓14

數據庫恢復是一個復雜的主題，很難寫，更難調試，因為恢復根本不會頻繁的發生。在他的圖靈獎演講中，Edsger Dijkstra認為編程天生很難，承認我們不擅此道是智慧的開端。我們作為架構師和程序員的目的是使用我們所掌握的工具：設計、問題分解、評審、測試、命名和風格規范以及其它好的習慣來限制編程問題為我們能解決的問題。

4.10 結束語

Berkeley DB現在已經年滿20歲了。它可以說是第一個通用的事務性鍵/值存儲，也是NoSQL運動的鼻祖。Berkeley DB繼續作為幾百個商業產品和幾千個開源應用軟件（包括SQL、XML和NoSQL引擎）的底層存儲系統，并在全球有幾百萬個部署。我們在它的開發和維護過程中所學到的經驗教訓都體現在代碼和上面總結的設計提示中了。我們分享并希望其他的軟件設計者和架構師發現它們有用。

腳注

請注意我們只需要返回到檢查點LSN，而不是它前面的檢查點記錄。

轉自：http://blog.csdn.net/zedware/article/details/7870754