前　　言
為什么要寫這本書
在互聯(lián)網(wǎng)行業(yè)中，存儲(chǔ)是一個(gè)非常重要的領(lǐng)域。所有的互聯(lián)網(wǎng)應(yīng)用都離不開數(shù)據(jù)的存儲(chǔ)和檢索。然而，存儲(chǔ)系統(tǒng)是計(jì)算機(jī)中非常復(fù)雜的一類系統(tǒng)。想掌握它，不僅需要掌握數(shù)據(jù)結(jié)構(gòu)、算法、操作系統(tǒng)等知識(shí)，還要掌握分布式系統(tǒng)相關(guān)知識(shí)。因此，存儲(chǔ)領(lǐng)域的入門門檻較高，對(duì)于初學(xué)者或者存儲(chǔ)愛好者而言并不友好。不幸的是，我也屬于存儲(chǔ)愛好者這個(gè)行列。此外，在日常工作和求職時(shí)，存儲(chǔ)相關(guān)知識(shí)的運(yùn)用和考察占比非常大。如果對(duì)存儲(chǔ)系統(tǒng)的原理有深入的理解，在工作時(shí)能夠更好地編寫高效的軟件，在求職時(shí)也將是明顯的優(yōu)勢(shì)和加分項(xiàng)。
目前業(yè)界的存儲(chǔ)系統(tǒng)主要包括關(guān)系數(shù)據(jù)庫(kù)（如MySQL、Oracle等）、NoSQL數(shù)據(jù)庫(kù)（如Redis、MongoDB、InfluxDB、OrientDB等）、NewSQL數(shù)據(jù)庫(kù)（如TiDB、OceanBase、CockroachDB等），以及消息隊(duì)列中間件（如Kafka、RocketMQ、Pulsar等）。這些存儲(chǔ)系統(tǒng)絕大部分都是分布式系統(tǒng)，它們將多個(gè)單機(jī)節(jié)點(diǎn)有序地組織在一起來(lái)提供服務(wù)。如果按照模塊化的思路進(jìn)行拆解，這類系統(tǒng)可以分為單機(jī)存儲(chǔ)組件和分布式組件。單機(jī)存儲(chǔ)組件主要針對(duì)單個(gè)實(shí)例，關(guān)注數(shù)據(jù)如何高效地存儲(chǔ)和檢索，主要考慮數(shù)據(jù)如何組織、索引如何維護(hù)、數(shù)據(jù)如何在磁盤上布局、單機(jī)事務(wù)如何支持等問(wèn)題。而分布式組件則更多關(guān)注多個(gè)實(shí)例之間的數(shù)據(jù)同步、故障發(fā)生后的故障自動(dòng)遷移、數(shù)據(jù)一致性的保證、數(shù)據(jù)分片等問(wèn)題。
雖然不同類型的存儲(chǔ)系統(tǒng)有很多差異，但在本質(zhì)上它們之間存在一些通用的技術(shù)點(diǎn)。市場(chǎng)上有幾本相關(guān)的書籍介紹這些內(nèi)容，比如Martin Kleppmann所著的《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計(jì)》和Alex Petrov所著的《數(shù)據(jù)庫(kù)系統(tǒng)內(nèi)幕》等。此外，還有一些主要介紹關(guān)系數(shù)據(jù)庫(kù)的書籍，比如Hector Garcia-Molina等人所著的《數(shù)據(jù)庫(kù)系統(tǒng)實(shí)現(xiàn)》、Abraham Silberschatz等人所著的《數(shù)據(jù)庫(kù)系統(tǒng)概念》和Baron Schwartz等人所著的《高性能MySQL》等。對(duì)于第一類書籍，我閱讀完后發(fā)現(xiàn)其廣度非常大，每個(gè)技術(shù)點(diǎn)都介紹到了，但在具體的技術(shù)專題上缺乏深度，需要搜羅其他資料進(jìn)行深入學(xué)習(xí)；而第二類書籍更多的是從理論上介紹，讀者閱讀完以后很難直接上手去剖析任何一款數(shù)據(jù)庫(kù)的源碼。
2020年年底，由于工作需要，我有幸負(fù)責(zé)了單機(jī)嵌入式的KV（鍵值對(duì)）存儲(chǔ)引擎的調(diào)研工作，隨后接觸并研究了BoltDB、LevelDB、RocksDB、PebblesDB、Bitcask等項(xiàng)目。在調(diào)研過(guò)程中我花費(fèi)了很多的時(shí)間和精力，也走了很多彎路。當(dāng)時(shí)在網(wǎng)上搜索了很多資料，但沒(méi)有解開我內(nèi)心的困惑。當(dāng)時(shí)想，如果市面上有一本系統(tǒng)地介紹存儲(chǔ)引擎的書就好了（比如存儲(chǔ)引擎的分類、適用場(chǎng)景、設(shè)計(jì)上的共通之處及工程實(shí)現(xiàn)等），這樣的書可以幫助我少走很多探索的彎路。后來(lái)偶然的機(jī)會(huì)接觸到了《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計(jì)》這本書，一讀就被這本書的內(nèi)容深深地吸引了。我反復(fù)讀了第3章，每次讀完書中對(duì)存儲(chǔ)引擎簡(jiǎn)明扼要的介紹時(shí)，都有一種豁然開朗的感覺(jué)。在后來(lái)不斷研究的過(guò)程中，我對(duì)單機(jī)的KV存儲(chǔ)引擎有了深入的認(rèn)識(shí)和個(gè)人理解。其間，我將其作為一個(gè)專題在團(tuán)隊(duì)內(nèi)部和外部社區(qū)進(jìn)行了分享，收到了不錯(cuò)的反饋，也有幸?guī)椭�到了一些技術(shù)小伙伴。
后來(lái)我想，像我當(dāng)初一樣，在入門存儲(chǔ)時(shí)存在各種疑惑的初學(xué)者可能有很多。于是我決定嘗試動(dòng)手寫一本解開上述疑惑的書，記錄研究過(guò)程中的一些經(jīng)驗(yàn)和感悟。于是，有了這本書。本書將給讀者一個(gè)全新的視角，秉承大道至簡(jiǎn)的主導(dǎo)思想，聚焦于單機(jī)存儲(chǔ)引擎本身，重點(diǎn)分析存儲(chǔ)引擎如何處理存儲(chǔ)和檢索，編寫上采用理論結(jié)合實(shí)踐的方式，并給出項(xiàng)目源碼分析。本書不僅僅是某種技能的分享，更致力于建立方法論，分享個(gè)人的一些想法和見解，希望能夠拋磚引玉，為讀者拓展出更深入、更全面的思路，幫助存儲(chǔ)初學(xué)者和愛好者知其然并知其所以然。最后，希望本書能夠填補(bǔ)存儲(chǔ)領(lǐng)域的一些空白。
本書特色
本書主要有三個(gè)目標(biāo)。首先，分析存儲(chǔ)引擎和各種存儲(chǔ)系統(tǒng)之間的關(guān)系，使讀者明確存儲(chǔ)引擎在存儲(chǔ)系統(tǒng)中的位置和角色。其次，給出存儲(chǔ)引擎的整體框架和分類，使讀者對(duì)存儲(chǔ)引擎有全面的了解。最后，對(duì)于每種存儲(chǔ)引擎，主要關(guān)注數(shù)據(jù)的存儲(chǔ)和檢索過(guò)程，解釋每類存儲(chǔ)引擎背后的設(shè)計(jì)思想和方案選擇，使讀者既知其然又知其所以然。
本書在寫作上采用了理論結(jié)合實(shí)踐的方式。每一類存儲(chǔ)引擎的介紹，分為理論部分和實(shí)踐部分。理論部分重點(diǎn)介紹設(shè)計(jì)方案和思想，不僅告訴讀者每一類存儲(chǔ)引擎能解決什么問(wèn)題、適用于什么場(chǎng)景，還告訴讀者為什么它們能解決這些問(wèn)題。在介紹設(shè)計(jì)原理的基礎(chǔ)上，配套一個(gè)開源項(xiàng)目進(jìn)行核心源碼的分析，幫助讀者更深入地理解存儲(chǔ)引擎的原理。
本書的目的不是介紹某個(gè)項(xiàng)目或技術(shù)，而是闡述存儲(chǔ)引擎背后通用的設(shè)計(jì)思想和方法論。我在前人的基礎(chǔ)上抽象和整理出來(lái)的方法論可以幫助讀者更好、更快、更輕松地理解存儲(chǔ)引擎，解決存儲(chǔ)領(lǐng)域門檻較高的問(wèn)題。此外，這些設(shè)計(jì)思想不局限于存儲(chǔ)系統(tǒng)，讀者在深刻理解后可以在計(jì)算機(jī)的其他系統(tǒng)中復(fù)用。因此，處于不同工作階段的不同人群可能有不同的閱讀感受，讀者可以根據(jù)需要在不同階段多次閱讀本書。
讀者對(duì)象
在閱讀本書之前，希望讀者對(duì)計(jì)算機(jī)基本知識(shí)有一個(gè)大致的了解，同時(shí)具備一定的編程基礎(chǔ)，至少熟悉一種編程語(yǔ)言（如C++或Go）等。如果有一些關(guān)系數(shù)據(jù)庫(kù)或者其他數(shù)據(jù)庫(kù)的經(jīng)驗(yàn)會(huì)更好，否則閱讀起來(lái)可能有些許困難。本書的讀者對(duì)象主要包括：
數(shù)據(jù)庫(kù)架構(gòu)師。
開發(fā)應(yīng)用架構(gòu)師。
數(shù)據(jù)庫(kù)開發(fā)人員。
后端開發(fā)人員。
存儲(chǔ)、數(shù)據(jù)庫(kù)愛好者。
其他計(jì)算機(jī)從業(yè)人員。
如何閱讀本書
本書共9章內(nèi)容，從邏輯上分為三部分。
第一部分為存儲(chǔ)引擎基礎(chǔ)，一方面對(duì)存儲(chǔ)引擎進(jìn)行概述，另一方面介紹存儲(chǔ)引擎中高頻使用的數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)介質(zhì)。這部分包括以下3章內(nèi)容。
第1章首先對(duì)互聯(lián)網(wǎng)上的各種存儲(chǔ)系統(tǒng)進(jìn)行不同維度的分類，并在此基礎(chǔ)上分析其內(nèi)部數(shù)據(jù)存儲(chǔ)的核心—存儲(chǔ)引擎。接著對(duì)存儲(chǔ)引擎進(jìn)行分類。本章是提綱挈領(lǐng)的一章。
第2章按照讀/寫的時(shí)間復(fù)雜度從低到高的順序介紹存儲(chǔ)引擎中索引高頻使用的數(shù)據(jù)結(jié)構(gòu)。涉及的數(shù)據(jù)結(jié)構(gòu)包括數(shù)組、鏈表、Hash（哈希）表、位圖、布隆過(guò)濾器、二叉搜索樹、紅黑樹、跳表、B樹、B+樹等。
第3章對(duì)存儲(chǔ)引擎中的存儲(chǔ)介質(zhì)進(jìn)行介紹，主要包括內(nèi)存、持久化內(nèi)存、磁盤等介質(zhì)。本章內(nèi)容涉及了大量的操作系統(tǒng)知識(shí)，例如虛擬內(nèi)存、文件系統(tǒng)等。
第二部分為基于B+樹的存儲(chǔ)引擎，重點(diǎn)討論處理讀多寫少場(chǎng)景的B+樹存儲(chǔ)引擎的相關(guān)內(nèi)容。這部分包括以下3章內(nèi)容。
第4章從宏觀角度分析B+樹存儲(chǔ)引擎的原理。這一章采用了逐步推導(dǎo)的思路來(lái)展開介紹，告訴讀者B+樹存儲(chǔ)引擎背后的方案選型和取舍。
第5章從微觀角度介紹B+樹存儲(chǔ)引擎中的細(xì)節(jié)。一方面介紹了B+樹存儲(chǔ)引擎的正常處理流程、邊界條件的處理過(guò)程、異常情況的應(yīng)對(duì)方案；另一方面介紹了存儲(chǔ)引擎中事務(wù)的實(shí)現(xiàn)方案和多版本并發(fā)控制等內(nèi)容。
第6章以BoltDB存儲(chǔ)引擎為例，分析其核心源碼實(shí)現(xiàn)邏輯。本章是實(shí)踐內(nèi)容，通過(guò)對(duì)BoltDB核心源碼的分析，使讀者更好地理解B+樹存儲(chǔ)引擎的內(nèi)部工作原理。
第三部分為基于LSM派系的存儲(chǔ)引擎，主要介紹處理寫多讀少場(chǎng)景的LSM派系存儲(chǔ)引擎的相關(guān)內(nèi)容。這部分包括以下3章內(nèi)容。
第7章也采用了逐步推導(dǎo)的方式，首先介紹LSM Tree（LSM樹）存儲(chǔ)引擎的內(nèi)部原理和演變過(guò)程，其次對(duì)LSM Tree的幾個(gè)核心問(wèn)題（如數(shù)據(jù)合并、數(shù)據(jù)分區(qū)、放大問(wèn)題、寫放大優(yōu)化等）進(jìn)行詳細(xì)的介紹。
第8章對(duì)LSM派系的各類存儲(chǔ)引擎（如LSM Tree、LSM Hash、LSM Array、消息隊(duì)列Kafka等）進(jìn)行闡述。其中，在介紹LSM Tree時(shí)重點(diǎn)對(duì)KV分離存儲(chǔ)技術(shù)WiscKey進(jìn)行了詳細(xì)的講解。
第9章以LevelDB為例，對(duì)其核心源碼進(jìn)行剖析。通過(guò)前面兩章的理論介紹和本章的源碼分析，讀者可以深入理解LSM Tree存儲(chǔ)引擎的原理。
其中，第1章、第4章、第5章、第7章、第8章為本書的重點(diǎn)。如果你沒(méi)有充足的時(shí)間閱讀全書，可以選擇性地閱讀重點(diǎn)章節(jié)。
勘誤和支持
由于我的水平有限且編寫時(shí)間緊張，書中難免會(huì)出現(xiàn)一些錯(cuò)誤或者不準(zhǔn)確的地方，懇請(qǐng)讀者批評(píng)指正。讀者可以通過(guò)郵箱2282186474@qq.com反饋寶貴的意見和建議，期待與大家在技術(shù)交流中互勉共進(jìn)。
致謝
感謝那些為開源項(xiàng)目做過(guò)分享的技術(shù)大咖和發(fā)表過(guò)學(xué)術(shù)論文的學(xué)者，以及各社區(qū)和平臺(tái)上的技術(shù)愛好者，尤其是《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計(jì)》的作譯者。他們的開源和分享對(duì)本書的編寫起到了至關(guān)重要的作用。在編寫本書的過(guò)程中，我一方面參考了大量相關(guān)論文、項(xiàng)目源碼和資料，另一方面也參考了一些非常優(yōu)秀的博客文章。這些資料對(duì)我的研究和探索也起到了非常重要的作用。
感謝我的妻子王淑明女士，為寫作這本書，我犧牲了很多陪伴她的時(shí)間。也感謝我的其他家人，他們的關(guān)懷給了我堅(jiān)持寫作的動(dòng)力。
特別感謝我職業(yè)生涯中的導(dǎo)師楊天琳先生，在本書寫作之前的方案調(diào)研和準(zhǔn)備過(guò)程中，他給了我很多建議。此外，在日常工作中我們進(jìn)行過(guò)很多次技術(shù)討論和交流，他給了我很多幫助。沒(méi)有他在技術(shù)上的指導(dǎo)，我估計(jì)不會(huì)有寫作本書的計(jì)劃。
謹(jǐn)以此書獻(xiàn)給我最親愛的家人、朋友，以及為計(jì)算機(jī)行業(yè)做出巨大貢獻(xiàn)的大師們。

文小飛