分布式數據庫繫統是大多數企業和絕大多數應用程序不可或缺的一部分。這些應用程序提供業務邏輯和用戶界面,而數據庫繫統則負責確保數據的完整性、一致性和冗餘性。
回到2000年,那時如果你要選擇一個數據庫,則隻有少數幾個選項,而且其中大部分都屬於關繫型數據庫,因此它們之間的差異相對較小。當然,這並不是說所有數據庫都是完全相同的,隻是它們的功能和使用場景都非常相似。
其中一些數據庫專注於水平擴展(scale out),即通過運行多個數據庫實例(表現得像是一個單一)來提高性能並增加容量,例如:Gamma數據庫機器項目、Teradata、Greenplum、Parallel DB2等。如今,水平擴展仍然是客戶期望的重要的數據庫特性之一,雲服務的日益普及詮釋了這一點。相較於將數據庫遷移至更大型、功能更強大的計算機進行垂直擴展(scale up),啟動一個新實例並將其添加到集群中通常要容易得多。因為遷移可能會耗時冗長且令人痛苦不堪,還可能會導致停機。
在2010年左右,一類新型的終一致性數據庫開始逐步湧現,並且一些諸如NoSQL、大數據等術語也日益流行。在過去的15年間,開源社區、大型互聯網公司和數據庫供應商構建了眾多的數據庫和工具,以至於當人們在試圖理解它們的使用場景、細節和規範時很容易迷失方向。
Amazon團隊於2007年發布的Dynamo論文[DECANDIA07]對數據庫社區產生了相當巨大的影響,在短時間內它便激發出了許多變體和實現。其中突出的是誕生於Facebook的Apache Cassandra、LinkedIn研發的Voldemort,以及由前Akamai工程師研發的Riak。
如今,該領域再次發生了變化:在鍵值存儲、NoSQL和終一致性數據庫之後,我們開始看到一些可擴展性更強、性能更高的數據庫,它們能夠在保證具有更強一致性的同時執行復雜的查詢。
本書的受眾
在技術會議的交流中,我經常聽到同樣的問題:“如何更多地了解有關數據庫內部的原理?我甚至不知道從哪裡開始。”關於數據庫繫統的大多數書籍都沒有詳細介紹存儲引擎的實現,並且隻是在較高的層次上介紹了訪問方法,例如B樹。很少有書籍涵蓋較新的概念,例如不同的B樹變體和日志結構存儲(log-structured storage),因此我通常建議直接閱讀論文。
但是每個讀過論文的人都知道這並不容易:時常缺乏上下文,措辭可能含糊不清,論文之間甚至幾乎根本沒有聯繫,論文本身也不容易找到。本書簡要總結了重要的數據庫繫統概念,並可以為希望深入研究的人們提供指南,也可以為已經熟悉這些概念的人們提供備忘單。
並非每個人都希望成為數據庫開發者,但是本書也將為使用數據庫繫統構建軟件的人員提供幫助,如:軟件開發者、運維工程師、架構師和工程技術經理。
如果你的公司依賴於任何基礎架構組件,無論是數據庫、消息隊列、容器平臺還是任務調度器,你都必須通過閱讀項目變更日志(change-log)和郵件列表來與社區保持聯繫、同步項目的進展。理解術語並了解其中的工作原理將使你能夠從這些信息來源中獲取更多信息,並可以更高效地使用工具來進行故障診斷,識別和避免潛在的風險與瓶頸。如果繫統出現了某些問題,那麼對數據庫繫統的工作原理有一個全面和基本的了解將會對你有所幫助。利用這些知識,在面對問題時,你將有能力提出假設、進行驗證、找到根本原因,並將其講解給其他項目成員。
本書也適合那些具備好奇心的人:喜歡學習一些不急用的知識的人,將空閑時間花在搗鼓一些有趣事情上的人。他們有的自己編寫編譯器,有的編寫自用的操作繫統、文本編輯器、電腦遊戲,有的學習編程語言—他們樂於獲取新知識。
本書假設讀者具有一些開發後端繫統和以用戶身份使用數據庫繫統的經驗。同時,具備一些不同種類數據結構的知識將有助於更快地吸收書中的知識。
為什麼應該閱讀本書
我們經常聽到人們用他們實現的概念和算法來描述數據庫繫統:“該數據庫使用Gossip來進行成員資格的傳播”(參見第12章)、“他們已經實現了Dynamo”或“這就像他們在Spanner論文中描述的一樣”(參見第13章)。抑或,如果你正在討論算法和數據結構,那麼你會聽到類似於“ZAB和Raft有很多共同點”(參見第14章)、“Bw樹就像是在日志結構化存儲上實現的B樹一樣”(參見第6章)或“它們使用的是類似於Blink樹中的同級指針”(參見第5章)的描述。
我們需要使用抽像來討論復雜的概念,但是我們不能在每次開啟一場對話時都討論抽像術語。以白話的形式來掌握這些抽像概念是一個捷徑,這能幫助我們將注意力轉移到其他更高層次的問題上。
學習基本概念、證明和算法的一個優點是它們永不過時。當然,總會有新的東西出現,但是新算法往往是在發現經典算法的缺陷或改進空間之後纔被創造出來的。了解歷史有助於更好地理解這些算法之間的差異和它們的發明動機。
學習這些內容是鼓舞人心的。你將看到各種各樣的算法,了解我們的工業界是如何一個接一個地解決問題的,並開始欣賞數據繫統。同時,學習這些是有回報的:你幾乎可以感覺到多個拼圖碎片在腦海中移動到一起,終形成一幅完整的圖畫,並且你將總是能夠與他人分享這幅圖畫。
本書的範疇
本書既不是關於關繫型數據庫的書,也不是關於NoSQL的書,而是關於在各種數據庫繫統中使用的算法和概念的書,且重點是存儲引擎和負責數據分布的組件。
諸如查詢計劃、查詢優化、調度、關繫模型等概念,在一些優秀的數據庫繫統教科書中已均有涉及。這些概念中的一部分通常是從用戶的角度進行描述的,而本書則著重於內部結構。你可以在第二部分的總結和每章的小結中找到一些有用文獻的推薦。這些文獻應該能回答很多與數據庫相關的問題。
由於本書中提到的數據庫繫統之間沒有一種通用的查詢語言,所以本書將不討論查詢語言。
為了收集本書的材料,我研究了15本書、300多篇論文、無數的博客文章、源代碼以及幾個開源數據庫的文檔。對於是否要在書中包含某個特定概念的原則,我常常會問自己這樣一個問題:“數據庫工業界和學術界的人都在談論這個概念嗎?”如果答案是“是”,我便會將該概念添加到一個長長的討論清單裡。
本書的結構
市面上有一些支持可插撥組件的可擴展數據庫的例子(例如[SCHWARZ86]),但它們較為少見。與此同時,數據庫使用可插撥存儲的例子卻頗多。類似地,我們很少聽到數據庫供應商談論查詢的執行,但他們卻非常熱衷於討論其數據庫是如何保證一致性的。
數據庫繫統之間顯著的區別集中在兩個方面:如何存儲和分布數據(其他子繫統有時也很重要,但這裡不作介紹)。本書分為兩部分,討論了負責數據存儲(部分)和數據分布(第二部分)的子繫統和組件。
部分討論節點本地的進程,並關注存儲引擎,它是數據庫繫統的核心組件以及重要的一素。首先,我們從數據庫管理繫統的架構開始介紹,並提出幾種基於主存介質和布局來對數據庫繫統進行分類的方法。隨後,我們將介紹存儲結構,並學習基於磁盤的存儲結構與基於內存的存儲結構之間的區別。然後介紹B樹以及在磁盤上高效維護B樹結構的算法,包括序列化、頁布局以及磁盤存儲形式。再之後,我們會討論B樹的一些變體,以說明上述概念的作用以及受B樹所影響和啟發的數據結構的多樣性。後,我們將討論日志結構存儲的幾種變體(它們通常用於實現文件和存儲繫統),並介紹日志結構存儲的起源以及使用它們的原因。
第二部分介紹如何將多個節點組織到一個數據庫集群中。我們從構建具備容錯性的分布式繫統理論開始,進而討論分布式繫統與單節點應用程序有何不同,以及我們在分布式環境中面臨的問題、約束和復雜性。之後,我們將深入研究分布式算法。其中,我們從故障檢測算法入手,這些算法通過檢測和報告故障並排除故障節點的方式來提高繫統整體的性能和穩定性。由於本書稍後討論的許多算法都依賴於集群領導權這個概念,所以我們將介紹幾種領導者選舉算法,並討論它們的使用範圍。分布式繫統中困難的事情之一就是要保證數據一致性,因此我們將討論復制的概念,緊接著討論一致性模型、副本之間可能存在的差異以及終一致性。由於終一致性繫統有時會依賴於反熵進行收斂,並依靠Gossip來進行數據分發,所以我們會討論幾種反熵和Gossip方法。後,我們討論數據庫事務上下文中的邏輯一致性,並以共識算法結尾。
如果沒有書中提到的這些研究和出版物,我是不可能完成本書的。在本書中,方括號代表參考文獻的索引,例如[DECANDIA07]。你可以使用這些參考資料來更詳細地了解有關概念。
在每章後的小結中都包含與該章內容相關的進一步研究的材料。
本書約定
本書使用了下述約定。
楷體
表示新術語。
斜體(Italic)
表示URL、電子郵件地址、文件名和文件擴展名。
等寬字體(Constant width)
用於程序清單,以及段落中引用素,例如變量或函數名、數據庫、數據類型、環境變量、語句和關鍵詞。
這個圖標表示提示或建議。
這個圖標表示一般性說明。
這個圖標表示警告或提醒。
示例代碼
寫作本書的目的是幫助你完成工作,而書中的示例代碼則是為了幫助你更好地理解本書的內容。通常,可以在程序或文檔中使用本書中的代碼,而不需要聯繫O扲eilly獲得許可,除非需要大段地復制代碼。例如,使用本書中所提供的幾個代碼片段來編寫一個程序不需要得到我們的許可,但銷售或發布O扲eilly的配套CD-ROM則需要獲得許可。引用本書的示例代碼來回答一個問題也不需要許可,將本書中的示例代碼的很大一部分放到自己的產品文檔中則需要獲得許可。
我們希望(但不強制)讀者在使用本書代碼時注明出處。出處的形式包含標題、作者、出版社和ISBN,例如:
Database Internals,作者Alex Petrov,由O扲eilly出版,書號978-1-492-04034-7
如果讀者覺得對示例代碼的使用超出了上面所給出的許可範圍,歡迎通過permission@oreilly.com聯繫我們。
O'Reilly在線學習平臺(O'Reilly Online Learning)
近40年來,O'Reilly Media致力於提供技術和商業培訓、知識和卓越見解,來幫助眾多公司取得成功。
我們擁有獨一無二的專家和革新者組成的龐大網絡,他們通過圖書、文章、會議和我們的在線學習平臺分享他們的知識和經驗。O扲eilly的在線學習平臺允許你按需訪問現場培訓課程、深入的學習路徑、交互式編程環境,以及O扲eilly和200多家其他出版商提供的大量文本和視頻資源。有關的更多信息,請訪問http://oreilly.com。
聯繫方式
對於本書,如果有任何意見或疑問,請按照以下地址聯繫本書出版商。
美國:
O'Reilly Media,Inc.
1005 Gravenstein Highway North
Sebastopol,CA 95472
中國:
北京市西城區西直門南大街2號成銘大廈C座807室(100035)
奧萊利技術咨詢(北京)有限公司
本書配套網站(http://bit.ly/database-internals)列出了勘誤表、示例以及其他信息。
要詢問技術問題或對本書提出建議,請發送電子郵件至bookquestions@oreilly.com。
關於書籍、課程、會議和新聞的更多信息,請訪問我們的網站:
http://www.oreilly.com
http://www.oreilly.com.cn
我們在Facebook上的地址:http://facebook.com/oreilly
我們在Twitter上的地址:http://twitter.com/oreillymedia
我們在YouTube上的地址:http://www.youtube.com/oreillymedia
致謝
如果沒有數以百計的人辛勤撰寫相關研究論文和書籍,本書就不可能出版。這些論文和書籍是分布式數據繫統思想的源泉,亦是這些思想的參考物,更是本書的參考來源。
我想對所有審閱本書手稿並提供反饋的人表示謝意,是你們確保了書中內容與措辭的正確性: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。
當然,如果沒有家人的支持,本書是不可能完成的,感謝我的妻子Marina和我的女兒Alexandra。這一路走來的每一步,她們都一直在支持我。