分布式數(shù)據(jù)庫(kù)系統(tǒng)是大多數(shù)企業(yè)和絕大多數(shù)應(yīng)用程序不可或缺的一部分。這些應(yīng)用程序提供業(yè)務(wù)邏輯和用戶(hù)界面，而數(shù)據(jù)庫(kù)系統(tǒng)則負(fù)責(zé)確保數(shù)據(jù)的完整性、一致性和冗余性。

回到2000年，那時(shí)如果你要選擇一個(gè)數(shù)據(jù)庫(kù)，則只有少數(shù)幾個(gè)選項(xiàng)，而且其中大部分都屬于關(guān)系型數(shù)據(jù)庫(kù)，因此它們之間的差異相對(duì)較小。當(dāng)然，這并不是說(shuō)所有數(shù)據(jù)庫(kù)都是完全相同的，只是它們的功能和使用場(chǎng)景都非常相似。

其中一些數(shù)據(jù)庫(kù)專(zhuān)注于水平擴(kuò)展（scale out），即通過(guò)運(yùn)行多個(gè)數(shù)據(jù)庫(kù)實(shí)例（表現(xiàn)得像是一個(gè)單一邏輯單元）來(lái)提高性能并增加容量，例如：Gamma數(shù)據(jù)庫(kù)機(jī)器項(xiàng)目、Teradata、Greenplum、Parallel DB2等。如今，水平擴(kuò)展仍然是客戶(hù)期望的最重要的數(shù)據(jù)庫(kù)特性之一，云服務(wù)的日益普及詮釋了這一點(diǎn)。相較于將數(shù)據(jù)庫(kù)遷移至更大型、功能更強(qiáng)大的計(jì)算機(jī)進(jìn)行垂直擴(kuò)展（scale up），啟動(dòng)一個(gè)新實(shí)例并將其添加到集群中通常要容易得多。因?yàn)檫w移可能會(huì)耗時(shí)冗長(zhǎng)且令人痛苦不堪，還可能會(huì)導(dǎo)致停機(jī)。

在2010年左右，一類(lèi)新型的最終一致性數(shù)據(jù)庫(kù)開(kāi)始逐步涌現(xiàn)，并且一些諸如NoSQL、大數(shù)據(jù)等術(shù)語(yǔ)也日益流行。在過(guò)去的15年間，開(kāi)源社區(qū)、大型互聯(lián)網(wǎng)公司和數(shù)據(jù)庫(kù)供應(yīng)商構(gòu)建了眾多的數(shù)據(jù)庫(kù)和工具，以至于當(dāng)人們?cè)谠噲D理解它們的使用場(chǎng)景、細(xì)節(jié)和規(guī)范時(shí)很容易迷失方向。

Amazon團(tuán)隊(duì)于2007年發(fā)布的Dynamo論文[DECANDIA07]對(duì)數(shù)據(jù)庫(kù)社區(qū)產(chǎn)生了相當(dāng)巨大的影響，在短時(shí)間內(nèi)它便激發(fā)出了許多變體和實(shí)現(xiàn)。其中最突出的是誕生于Facebook的Apache Cassandra、LinkedIn研發(fā)的Voldemort，以及由前Akamai工程師研發(fā)的Riak。

如今，該領(lǐng)域再次發(fā)生了變化：在鍵值存儲(chǔ)、NoSQL和最終一致性數(shù)據(jù)庫(kù)之后，我們開(kāi)始看到一些可擴(kuò)展性更強(qiáng)、性能更高的數(shù)據(jù)庫(kù)，它們能夠在保證具有更強(qiáng)一致性的同時(shí)執(zhí)行復(fù)雜的查詢(xún)。

本書(shū)的受眾

在技術(shù)會(huì)議的交流中，我經(jīng)常聽(tīng)到同樣的問(wèn)題：“如何更多地了解有關(guān)數(shù)據(jù)庫(kù)內(nèi)部的原理？我甚至不知道從哪里開(kāi)始。”關(guān)于數(shù)據(jù)庫(kù)系統(tǒng)的大多數(shù)書(shū)籍都沒(méi)有詳細(xì)介紹存儲(chǔ)引擎的實(shí)現(xiàn)，并且只是在較高的層次上介紹了訪問(wèn)方法，例如B樹(shù)。很少有書(shū)籍涵蓋較新的概念，例如不同的B樹(shù)變體和日志結(jié)構(gòu)存儲(chǔ)（log-structured storage），因此我通常建議直接閱讀論文。

但是每個(gè)讀過(guò)論文的人都知道這并不容易：時(shí)常缺乏上下文，措辭可能含糊不清，論文之間甚至幾乎根本沒(méi)有聯(lián)系，論文本身也不容易找到。本書(shū)簡(jiǎn)要總結(jié)了重要的數(shù)據(jù)庫(kù)系統(tǒng)概念，并可以為希望深入研究的人們提供指南，也可以為已經(jīng)熟悉這些概念的人們提供備忘單。

并非每個(gè)人都希望成為數(shù)據(jù)庫(kù)開(kāi)發(fā)者，但是本書(shū)也將為使用數(shù)據(jù)庫(kù)系統(tǒng)構(gòu)建軟件的人員提供幫助，如：軟件開(kāi)發(fā)者、運(yùn)維工程師、架構(gòu)師和工程技術(shù)經(jīng)理。

如果你的公司依賴(lài)于任何基礎(chǔ)架構(gòu)組件，無(wú)論是數(shù)據(jù)庫(kù)、消息隊(duì)列、容器平臺(tái)還是任務(wù)調(diào)度器，你都必須通過(guò)閱讀項(xiàng)目變更日志（change-log）和郵件列表來(lái)與社區(qū)保持聯(lián)系、同步項(xiàng)目的最新進(jìn)展。理解術(shù)語(yǔ)并了解其中的工作原理將使你能夠從這些信息來(lái)源中獲取更多信息，并可以更高效地使用工具來(lái)進(jìn)行故障診斷，識(shí)別和避免潛在的風(fēng)險(xiǎn)與瓶頸。如果系統(tǒng)出現(xiàn)了某些問(wèn)題，那么對(duì)數(shù)據(jù)庫(kù)系統(tǒng)的工作原理有一個(gè)全面和基本的了解將會(huì)對(duì)你有所幫助。利用這些知識(shí)，在面對(duì)問(wèn)題時(shí)，你將有能力提出假設(shè)、進(jìn)行驗(yàn)證、找到根本原因，并將其講解給其他項(xiàng)目成員。

本書(shū)也適合那些具備好奇心的人：喜歡學(xué)習(xí)一些不急用的知識(shí)的人，將空閑時(shí)間花在搗鼓一些有趣事情上的人。他們有的自己編寫(xiě)編譯器，有的編寫(xiě)自用的操作系統(tǒng)、文本編輯器、電腦游戲，有的學(xué)習(xí)編程語(yǔ)言—他們樂(lè)于獲取新知識(shí)。

本書(shū)假設(shè)讀者具有一些開(kāi)發(fā)后端系統(tǒng)和以用戶(hù)身份使用數(shù)據(jù)庫(kù)系統(tǒng)的經(jīng)驗(yàn)。同時(shí)，具備一些不同種類(lèi)數(shù)據(jù)結(jié)構(gòu)的知識(shí)將有助于更快地吸收書(shū)中的知識(shí)。

為什么應(yīng)該閱讀本書(shū)

我們經(jīng)常聽(tīng)到人們用他們實(shí)現(xiàn)的概念和算法來(lái)描述數(shù)據(jù)庫(kù)系統(tǒng)：“該數(shù)據(jù)庫(kù)使用Gossip來(lái)進(jìn)行成員資格的傳播”（參見(jiàn)第12章）、“他們已經(jīng)實(shí)現(xiàn)了Dynamo”或“這就像他們?cè)赟panner論文中描述的一樣”（參見(jiàn)第13章）。抑或，如果你正在討論算法和數(shù)據(jù)結(jié)構(gòu)，那么你會(huì)聽(tīng)到類(lèi)似于“ZAB和Raft有很多共同點(diǎn)”（參見(jiàn)第14章）、“Bw樹(shù)就像是在日志結(jié)構(gòu)化存儲(chǔ)上實(shí)現(xiàn)的B樹(shù)一樣”（參見(jiàn)第6章）或“它們使用的是類(lèi)似于Blink樹(shù)中的同級(jí)指針”（參見(jiàn)第5章）的描述。

我們需要使用抽象來(lái)討論復(fù)雜的概念，但是我們不能在每次開(kāi)啟一場(chǎng)對(duì)話時(shí)都討論抽象術(shù)語(yǔ)。以白話的形式來(lái)掌握這些抽象概念是一個(gè)捷徑，這能幫助我們將注意力轉(zhuǎn)移到其他更高層次的問(wèn)題上。

學(xué)習(xí)基本概念、證明和算法的一個(gè)優(yōu)點(diǎn)是它們永不過(guò)時(shí)。當(dāng)然，總會(huì)有新的東西出現(xiàn)，但是新算法往往是在發(fā)現(xiàn)經(jīng)典算法的缺陷或改進(jìn)空間之后才被創(chuàng)造出來(lái)的。了解歷史有助于更好地理解這些算法之間的差異和它們的發(fā)明動(dòng)機(jī)。

學(xué)習(xí)這些內(nèi)容是鼓舞人心的。你將看到各種各樣的算法，了解我們的工業(yè)界是如何一個(gè)接一個(gè)地解決問(wèn)題的，并開(kāi)始欣賞數(shù)據(jù)系統(tǒng)。同時(shí)，學(xué)習(xí)這些是有回報(bào)的：你幾乎可以感覺(jué)到多個(gè)拼圖碎片在腦海中移動(dòng)到一起，最終形成一幅完整的圖畫(huà)，并且你將總是能夠與他人分享這幅圖畫(huà)。

本書(shū)的范疇

本書(shū)既不是關(guān)于關(guān)系型數(shù)據(jù)庫(kù)的書(shū)，也不是關(guān)于NoSQL的書(shū)，而是關(guān)于在各種數(shù)據(jù)庫(kù)系統(tǒng)中使用的算法和概念的書(shū)，且重點(diǎn)是存儲(chǔ)引擎和負(fù)責(zé)數(shù)據(jù)分布的組件。

諸如查詢(xún)計(jì)劃、查詢(xún)優(yōu)化、調(diào)度、關(guān)系模型等概念，在一些優(yōu)秀的數(shù)據(jù)庫(kù)系統(tǒng)教科書(shū)中已均有涉及。這些概念中的一部分通常是從用戶(hù)的角度進(jìn)行描述的，而本書(shū)則著重于內(nèi)部結(jié)構(gòu)。你可以在第二部分的總結(jié)和每章的小結(jié)中找到一些有用文獻(xiàn)的推薦。這些文獻(xiàn)應(yīng)該能回答很多與數(shù)據(jù)庫(kù)相關(guān)的問(wèn)題。

由于本書(shū)中提到的數(shù)據(jù)庫(kù)系統(tǒng)之間沒(méi)有一種通用的查詢(xún)語(yǔ)言，所以本書(shū)將不討論查詢(xún)語(yǔ)言。

為了收集本書(shū)的材料，我研究了15本書(shū)、300多篇論文、無(wú)數(shù)的博客文章、源代碼以及幾個(gè)開(kāi)源數(shù)據(jù)庫(kù)的文檔。對(duì)于是否要在書(shū)中包含某個(gè)特定概念的原則，我常常會(huì)問(wèn)自己這樣一個(gè)問(wèn)題：“數(shù)據(jù)庫(kù)工業(yè)界和學(xué)術(shù)界的人都在談?wù)撨@個(gè)概念嗎？”如果答案是“是”，我便會(huì)將該概念添加到一個(gè)長(zhǎng)長(zhǎng)的討論清單里。

本書(shū)的結(jié)構(gòu)

市面上有一些支持可插拔組件的可擴(kuò)展數(shù)據(jù)庫(kù)的例子（例如[SCHWARZ86]），但它們較為少見(jiàn)。與此同時(shí)，數(shù)據(jù)庫(kù)使用可插拔存儲(chǔ)的例子卻頗多。類(lèi)似地，我們很少聽(tīng)到數(shù)據(jù)庫(kù)供應(yīng)商談?wù)摬樵?xún)的執(zhí)行，但他們卻非常熱衷于討論其數(shù)據(jù)庫(kù)是如何保證一致性的。

數(shù)據(jù)庫(kù)系統(tǒng)之間最顯著的區(qū)別集中在兩個(gè)方面：如何存儲(chǔ)和分布數(shù)據(jù)（其他子系統(tǒng)有時(shí)也很重要，但這里不作介紹）。本書(shū)分為兩部分，討論了負(fù)責(zé)數(shù)據(jù)存儲(chǔ)（第一部分）和數(shù)據(jù)分布（第二部分）的子系統(tǒng)和組件。

第一部分討論節(jié)點(diǎn)本地的進(jìn)程，并關(guān)注存儲(chǔ)引擎，它是數(shù)據(jù)庫(kù)系統(tǒng)的核心組件以及最重要的一個(gè)特有元素。首先，我們從數(shù)據(jù)庫(kù)管理系統(tǒng)的架構(gòu)開(kāi)始介紹，并提出幾種基于主存介質(zhì)和布局來(lái)對(duì)數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行分類(lèi)的方法。隨后，我們將介紹存儲(chǔ)結(jié)構(gòu)，并學(xué)習(xí)基于磁盤(pán)的存儲(chǔ)結(jié)構(gòu)與基于內(nèi)存的存儲(chǔ)結(jié)構(gòu)之間的區(qū)別。然后介紹B樹(shù)以及在磁盤(pán)上高效維護(hù)B樹(shù)結(jié)構(gòu)的算法，包括序列化、頁(yè)布局以及磁盤(pán)存儲(chǔ)形式。再之后，我們會(huì)討論B樹(shù)的一些變體，以說(shuō)明上述概念的作用以及受B樹(shù)所影響和啟發(fā)的數(shù)據(jù)結(jié)構(gòu)的多樣性。最后，我們將討論日志結(jié)構(gòu)存儲(chǔ)的幾種變體（它們通常用于實(shí)現(xiàn)文件和存儲(chǔ)系統(tǒng)），并介紹日志結(jié)構(gòu)存儲(chǔ)的起源以及使用它們的原因。

第二部分介紹如何將多個(gè)節(jié)點(diǎn)組織到一個(gè)數(shù)據(jù)庫(kù)集群中。我們從構(gòu)建具備容錯(cuò)性的分布式系統(tǒng)理論開(kāi)始，進(jìn)而討論分布式系統(tǒng)與單節(jié)點(diǎn)應(yīng)用程序有何不同，以及我們?cè)诜植际江h(huán)境中面臨的問(wèn)題、約束和復(fù)雜性。之后，我們將深入研究分布式算法。其中，我們從故障檢測(cè)算法入手，這些算法通過(guò)檢測(cè)和報(bào)告故障并排除故障節(jié)點(diǎn)的方式來(lái)提高系統(tǒng)整體的性能和穩(wěn)定性。由于本書(shū)稍后討論的許多算法都依賴(lài)于集群領(lǐng)導(dǎo)權(quán)這個(gè)概念，所以我們將介紹幾種領(lǐng)導(dǎo)者選舉算法，并討論它們的使用范圍。分布式系統(tǒng)中最困難的事情之一就是要保證數(shù)據(jù)一致性，因此我們將討論復(fù)制的概念，緊接著討論一致性模型、副本之間可能存在的差異以及最終一致性。由于最終一致性系統(tǒng)有時(shí)會(huì)依賴(lài)于反熵進(jìn)行收斂，并依靠Gossip來(lái)進(jìn)行數(shù)據(jù)分發(fā)，所以我們會(huì)討論幾種反熵和Gossip方法。最后，我們討論數(shù)據(jù)庫(kù)事務(wù)上下文中的邏輯一致性，并以共識(shí)算法結(jié)尾。

如果沒(méi)有書(shū)中提到的這些研究和出版物，我是不可能完成本書(shū)的。在本書(shū)中，方括號(hào)代表參考文獻(xiàn)的索引，例如[DECANDIA07]。你可以使用這些參考資料來(lái)更詳細(xì)地了解有關(guān)概念。

在每章最后的小結(jié)中都包含與該章內(nèi)容相關(guān)的進(jìn)一步研究的材料。

本書(shū)約定

本書(shū)使用了下述約定。

楷體

表示新術(shù)語(yǔ)。

斜體（Italic）

表示URL、電子郵件地址、文件名和文件擴(kuò)展名。

等寬字體（Constant width）

用于程序清單，以及段落中引用的程序元素，例如變量或函數(shù)名、數(shù)據(jù)庫(kù)、數(shù)據(jù)類(lèi)型、環(huán)境變量、語(yǔ)句和關(guān)鍵詞。

這個(gè)圖標(biāo)表示提示或建議。

這個(gè)圖標(biāo)表示一般性說(shuō)明。

這個(gè)圖標(biāo)表示警告或提醒。

示例代碼

寫(xiě)作本書(shū)的目的是幫助你完成工作，而書(shū)中的示例代碼則是為了幫助你更好地理解本書(shū)的內(nèi)容。通常，可以在程序或文檔中使用本書(shū)中的代碼，而不需要聯(lián)系O扲eilly獲得許可，除非需要大段地復(fù)制代碼。例如，使用本書(shū)中所提供的幾個(gè)代碼片段來(lái)編寫(xiě)一個(gè)程序不需要得到我們的許可，但銷(xiāo)售或發(fā)布O扲eilly的配套CD-ROM則需要獲得許可。引用本書(shū)的示例代碼來(lái)回答一個(gè)問(wèn)題也不需要許可，將本書(shū)中的示例代碼的很大一部分放到自己的產(chǎn)品文檔中則需要獲得許可。

我們希望（但不強(qiáng)制）讀者在使用本書(shū)代碼時(shí)注明出處。出處的形式包含標(biāo)題、作者、出版社和ISBN，例如：

Database Internals，作者Alex Petrov，由O扲eilly出版，書(shū)號(hào)978-1-492-04034-7

如果讀者覺(jué)得對(duì)示例代碼的使用超出了上面所給出的許可范圍，歡迎通過(guò)permission@oreilly.com聯(lián)系我們。

O'Reilly在線學(xué)習(xí)平臺(tái)（O'Reilly Online Learning）

近40年來(lái)，O'Reilly Media致力于提供技術(shù)和商業(yè)培訓(xùn)、知識(shí)和卓越見(jiàn)解，來(lái)幫助眾多公司取得成功。

我們擁有獨(dú)一無(wú)二的專(zhuān)家和革新者組成的龐大網(wǎng)絡(luò)，他們通過(guò)圖書(shū)、文章、會(huì)議和我們的在線學(xué)習(xí)平臺(tái)分享他們的知識(shí)和經(jīng)驗(yàn)。O扲eilly的在線學(xué)習(xí)平臺(tái)允許你按需訪問(wèn)現(xiàn)場(chǎng)培訓(xùn)課程、深入的學(xué)習(xí)路徑、交互式編程環(huán)境，以及O扲eilly和200多家其他出版商提供的大量文本和視頻資源。有關(guān)的更多信息，請(qǐng)?jiān)L問(wèn)http://oreilly.com。

聯(lián)系方式

對(duì)于本書(shū)，如果有任何意見(jiàn)或疑問(wèn)，請(qǐng)按照以下地址聯(lián)系本書(shū)出版商。

美國(guó)：

O'Reilly Media，Inc.

1005 Gravenstein Highway North

Sebastopol，CA 95472

中國(guó)：

北京市西城區(qū)西直門(mén)南大街2號(hào)成銘大廈C座807室（100035）

奧萊利技術(shù)咨詢(xún)（北京）有限公司

本書(shū)配套網(wǎng)站（http://bit.ly/database-internals）列出了勘誤表、示例以及其他信息。

要詢(xún)問(wèn)技術(shù)問(wèn)題或?qū)Ρ緯?shū)提出建議，請(qǐng)發(fā)送電子郵件至bookquestions@oreilly.com。

關(guān)于書(shū)籍、課程、會(huì)議和新聞的更多信息，請(qǐng)?jiān)L問(wèn)我們的網(wǎng)站：

http://www.oreilly.com

http://www.oreilly.com.cn

我們?cè)贔acebook上的地址：http://facebook.com/oreilly

我們?cè)赥witter上的地址：http://twitter.com/oreillymedia

我們?cè)赮ouTube上的地址：http://www.youtube.com/oreillymedia

致謝

如果沒(méi)有數(shù)以百計(jì)的人辛勤撰寫(xiě)相關(guān)研究論文和書(shū)籍，本書(shū)就不可能出版。這些論文和書(shū)籍是分布式數(shù)據(jù)系統(tǒng)思想的源泉，亦是這些思想的參考物，更是本書(shū)的參考來(lái)源。

我想對(duì)所有審閱本書(shū)手稿并提供反饋的人表示謝意，是你們確保了書(shū)中內(nèi)容與措辭的正確性：Dmitry Alimov、Peter Alvaro、Carlos Baquero、Jason Brown、Blake Eggleston、Marcus Eriksson、Francisco Fernández Casta、Joel Knighton、Eugene Lazin、Nate McCall、Christopher Meiklejohn、Tyler Neely、Maxim Neverov、Marina Petrova、Stefan Podkowinski、Edward Ribiero、Denis Rytsov、Kir Shatrov、Alex Sorokoumov、Massimiliano Tomassi及Ariel Weisberg。

當(dāng)然，如果沒(méi)有家人的支持，本書(shū)是不可能完成的，感謝我的妻子Marina和我的女兒Alexandra。這一路走來(lái)的每一步，她們都一直在支持我。