这本书既不是关于关系型数据库的书，也不是关于NoSQL的书，而是关于在各种数据库系统中使用的算法和概念的书，重点是存储引擎和负责数据分布的组件。第一部分讨论节点本地的进程，并着重于存储引擎这个数据库系统的核心组件以及最重要的一个特有元素。第二部分讨论负责数据分布的子系统和组件，介绍如何将多个节点组织到一个数据库集群中。
无
分布式数据库系统是大多数企业和绝大多数应用程序不可或缺的一部分。这些应用程序提供业务逻辑和用户界面，而数据库系统则负责确保数据的完整性、一致性和冗余性。
回到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。这一路走来的每一步，她们都一直在支持我。
计算机\人工智能
“ 为了在工作中选择正确的工具，我们需要理解它们背后的设计思路和算法。这本书对初学者很友好，它由业界的实践者撰写，介绍了一些与分布式数据库系统相关的主题。”
——Michael Klishin
RabbitMQ资深贡献者
“ 这本书对于和任何数据库系统技术打交道的人来说都是必读之书，尤其是那些需要决定使用什么系统的人。”
——Nate McCall
Apache Cassandra 提交者
PMC主席
当我们选择、使用并维护一个数据库系统时，理解它的原理至关重要。但是现今有太多的分布式数据库和工具可供使用，要想弄明白每一种工具的作用以及它们之间的区别往往并不容易。在这本实用指南中，作者讲解了现代数据库和存储引擎背后的概念。
通过本书，你将领略到从众多书籍、论文、博客和多个开源数据库源代码中精心选取的相关材料，并且了解到众多现代数据库之间最重要的区别在于决定存储结构和数据分布的子系统。
你将深入了解如下内容：
? 存储引擎：学习存储的种类、分类依据，理解基于B树和不可变日志存储结构的存储引擎。
? 存储构建块：理解数据库文件如何使用诸如页缓存、缓冲池等辅助数据结构来组织构建高效的存储。
? 分布式系统：逐步学习节点和进程间如何连接并构建复杂的通信模式。
? 数据库集群：深入探究现在数据库中常用的一致性模型，并了解分布式存储系统是如何实现一致性的。
Alex Petrov是一位数据基础架构工程师，数据库和存储系统的狂热爱好者，Apache Cassandra 提交者和PMC成员，精通存储、分布式系统和算法。
[美]亚历克斯·彼得罗夫（Alex Petrov） 著：Alex Petrov是一位数据基础架构工程师，数据库和存储系统的狂热爱好者，Apache Cassandra 提交者和PMC成员，精通存储、分布式系统和算法。
作为数据库行业的从业者，我们常常自嘲本行业为夕阳行业。为何这么说呢？众所周知，Oracle在数据库行业被公认坐“头把交椅”，它诞生于20世纪70年代，而与之匹敌的DB2、SQL Server等产品也大多起步于同一时期。数据库系统中诸如关系代数、SQL、事务等基本概念也都存在了半个世纪之久，很多初入行的新人都是从一篇篇油墨印刷的论文开始学习的。也难怪大家会产生一种“夕阳”的感觉吧！
自嘲归自嘲，真实情况是怎样的呢？打开著名的DB-Engines Ranking（https://db-engines.com/en/ranking），虽然Oracle之辈霸榜依旧，但也涌现出了种类繁多的新秀。大家耳熟能详的“世界上最流行的开源数据库”MySQL，借着互联网的东风和开源运动的兴起，已经冲上榜眼的位置。除此之外，还有各种新兴的文档数据库、KV数据库等，它们往往在性能或数据规模方面远远甩开了先辈，在一些关键场景中大放异彩。
另一方面，商业领域的成功案例也屡见不鲜。2017年年底上市的MongoDB至今为很多技术创业者津津乐道，上市两年多以来市值已经翻了7倍。再比如Splunk也是一个全文索引数据库，2012年成为“全球第一家上市的大数据分析公司”，而其开源竞品ElasticSearch所属的Elastic公司亦于2018年年底登陆纳斯达克。更不用说AWS、阿里云这样的云计算厂商，它们先是从开源数据库的云服务化中享受到红利，然后又投入人力研发了诸如DynamoDB、PolarDB等各种“云原生”的数据库即服务（Database-as-a-Service）产品。
不经意间，“数据库”这个词的含义已经与20世纪大大不同了—尽管人们还在使用这一称呼。随着互联网的触角伸向社会的每个角落，互联网服务背后的数据库常常需要处理PB级别的数据，这远远超出了单机的容量上限，动辄就要使用成百上千台机器组成的分布式集群。另一方面，随着数据量的爆炸性增长，不同种类的数据往往以不同的格式和介质存放：有些需要超高的并发性和实时性，有些需要严格的ACID事务保证，另一些则需要极度的压缩以节省磁盘资源。
如果你是一名开发者，如此多的数据库系统难免让你感到眼花缭乱。它们间往往并没有严格的边界和限制，似乎每个产品都能拿出适合业务场景的“最佳实践”案例。迷茫之中，你可能会想起曾在大学学习过的数据库系统课程。然而遗憾的是，教科书上的信息大多还停留在20世纪—那个关系型数据库为王的年代。你可能失望地发现，当今日新月异的数据库技术在教科书上或许无法窥其全貌。
这也正是我们的感受。对于某一种数据库系统，你的确能找到许多关于它的文档和书籍。但一直以来，我们都期望着有人能站在现代视角重新审视整个数据库领域，对各种数据库系统的共通点进行梳理，为读者建立一个“Big Picture”。而本书正是这样一本书。
本书完全不拘泥于任何一款数据库系统，也不偏袒任何一种数据库的类型或特性。（它甚至几乎没有提到SQL！但SQL的确已经没那么普遍了，不是吗？）本书只会讨论现代数据库必不可少的那些东西，例如存储格式、索引数据结构、数据一致性等。每个话题又能引出许多选项与权衡，比如：是否应该为了可用性牺牲一些一致性？是否应该牺牲读取性能以换取更高的写入性能？正是这些权衡最终造就了许许多多数据库系统之间的差异。
今天，任何单点的系统架构设计都是令人难以容忍的，数据库系统更是不例外。本书使用了一半的篇幅讲述分布式系统与分布式数据库，通过这些章节，你将会了解分布式系统带来了哪些技术挑战，以及它是如何解决扩展性和高可用问题的。
整个翻译过程历时近半年，而我们三人分别位于北京、杭州和东京，在整个翻译过程中一直未曾谋面，然而彼此高效协作（感谢Google Docs和Asana），共同讨论了诸多技术与文字细节，力求每一句话精准达意、简练易懂。每个章节均经过数轮的审阅和修改，在这个过程中改进了上千处翻译细节，甚至还指出了原书的部分笔误。虽然尽力审慎细致，不过由于水平所限，难免仍有部分细节值得商榷并有待改进。抱着向业界各位好朋友求教的心态，我们真诚地希望得到每位读者对本书内容的建议，也欢迎与我们分享阅读本书后的感受。
我们要感谢机械工业出版社的王春华编辑为我们协调资源、答疑解惑。也要特别感谢参与第二轮审校的来自五湖四海的朋友—黄东旭（PingCAP）、王欢明（阿里云）、黄光星（新加坡Sea Group）、江嘉诚（晶泰科技），他们以读者的视角为译稿提出了许多宝贵的修改建议，令我们受益匪浅。
最后，真诚地希望本书能帮到你！
黄鹏程 傅宇 张晨
2020年4月4日
推荐序一
数据库是一个历史悠久的计算机学科。1970年，E. F. Codd在IBM提出了现代关系型数据库的标准—关系模型，而事务型数据库最常用的持久化数据结构B+树则来源于Bayer在1972年发表的论文，当时Bayer在波音公司工作，因此B+树的B有说法是取自平衡（Balance），也有说法是取自作者的姓名（Bayer），还有说法是取自波音（Boeing）。1974年IBM开发了最早的关系型数据库原型System R，现代数据库的故障恢复机制ARIES以及基于代价的优化器都源自System R。1979年，Oracle发布了最早的商业关系型数据库。Oracle最早的订单来自CIA的情报数据分析需求。在NSA的资助下，最早的开源数据库Ingres在20世纪70年代的同时期诞生，一度对Oracle构成了严重威胁。Oracle通过兼容SQL标准并在早期引入C语言以使自身能更快地移植到各种小型机硬件打败了Ingres。在Ingres的基础上又衍生出Sybase和SQL Server，以及流行的开源数据库PostgreSQL。当代另一个流行的关系型数据库MySQL的第一版则在1995年发布，其作者Monty和Linux的作者Linus都毕业于赫尔辛基大学。
近二十年来，随着互联网经济的兴起，企业对数据库的需求转向了如何以更低的成本处理、存储与分析海量数据。LAMP（Linux、Apache、MySQL、PHP）架构是在1998年提出的，它通过一套开源的解决方案，满足了中小型互联网公司的建站需求。LAMP架构影响了谷歌、Facebook、阿里巴巴、百度、腾讯等一众互联网巨头，它们都是基于MySQL起步，逐步发展出可扩展的在线事务型数据库服务。从2006年到2012年，固态硬盘的普及大大缩小了开源数据库与商业数据库的性能差距。也是在这个时期，阿里巴巴在国内喊出“去IOE”的口号。2013年，阿里巴巴将核心业务数据库全部切换到 AliSQL（阿里巴巴定制和优化的MySQL分支），也培养出一批数据库内核方面的优秀人才，译者之一傅宇就来自阿里巴巴数据库事业部。
近些年，云成为数据库发展的新动力，数据库厂商的版图正在发生巨大的变化。根据Gartner 2019年的报告，全球前三的云厂商（AWS、微软、谷歌）都跻身数据库领导者象限，与Oracle、SAP等老牌厂商并列。而传统企业数据库强者如IBM DB2则跌出了领导者象限。值得自豪的是，阿里云作为中国领先的云厂商，通过推出PolarDB、OceanBase等技术领先的自研数据库，在数据库系统（DBMS）领域进入了挑战者象限。Gartner预测到2022年，3/4的数据库都将使用云数据库。可见对数据库市场份额而言，云是一个很大的变量，云市场的兴起为国内数据库厂商带来了达到国际顶尖水平的机会。
技术的发展总是螺旋式上升的。近年来，RDMA网络设备开始商业化和普及。由于RDMA支持数据中心内部极低延迟和高吞吐的通信，因此对分布式数据库的设计范式有很大的冲击。过去几十年来，系统设计都是基于网络开销远高于单机内通信的假设，而在新硬件下这个假设被突破，比如访问其他机器的内存（~10s）比读本地的SSD（~100s）要快一个数量级，访问远程数据和访问本地磁盘数据的性能变得接近。近年来，另一个新兴的存储技术是NVM，它像SSD一样能将数据持久化，但读写延迟接近于内存DRAM。目前的SSD都是建议按4K来寻址，NVM却可以按字节寻址。NVM的出现对传统的数据库并发控制和故障恢复机制提出了新的挑战。
在这个背景下，云原生数据库成为数据库系统进一步演进的热点。云原生的本质是资源池化，多台服务器上的CPU、内存和磁盘资源通过分布式技术组成一个多租户、容量更大、容错能力更强且可弹性伸缩的计算池、内存池和存储池。云原生数据库的本质是基于池化的资源构建出的数据库服务，这与采用软件分发模式的传统数据库有着质的区别。在云原生数据库技术下，资源的分配和调度算法乃至供应链管理都得到了极大的简化，数据库的持久性和一致性也有了更高的保证。新硬件（例如RDMA、NVM）的使用也被隐藏在云服务接口下，透明地提供加速能力，减少用户使用新硬件的学习成本。
近几年，云原生数据库蓬勃发展，从全球来看，AWS的Aurora、微软Azure的HyperScale、阿里云的PolarDB等产品都基于云资源池基础设施构建，并且对传统Oracle等巨头产生了巨大的冲击。Oracle在全球技术大会上已经把云数据库当成最大的竞争对手。越来越多的企业上云开始直接选择云原生数据库，几乎所有的云厂商都在基于云原生理念构建下一代云数据库体系。可以说对于IT基础设施行业，得数据库者得云，得云者得天下。深入了解数据库的核心技术、把握新时代技术演进方向的重要性不言而喻。
本书是对当今各种数据库系统的概述。第一部分站在单机的角度，介绍了磁盘存储格式、索引数据结构、事务处理等；第二部分则以分布式系统为切入点，讲解了分布式数据库的多副本、分布式事务、一致性等问题。本书选材紧跟业内前沿发展，不仅涉及各种新兴的数据库产品，还涉及许多学术界前沿研究成果。不论你是有志于从事云计算领域、深入研究数据库系统的设计与实现，还是即将使用云数据库以及云原生数据库，都应当阅读本书。数据库是在线系统中最关键的支撑组件，开发者应该对数据库系统的原理有所了解，而深入理解数据库以及分布式系统内部的工作原理能帮助读者在工作中更好地提升在线系统的性能。
曹伟
中国计算机协会数据库专委委员
阿里巴巴数据库研究员
阿里云智能数据库事业部总经理
推荐序二
作为一名从事数据库研发的专业工程师，我想起在刚入门的时候，我对这样一个庞大又神秘的领域是充满好奇的。但是当时在大学里接触到的有关数据库系统理论的书几乎都是大部头，而且都充满了浓浓的学术气息。直到毕业以后真正开始从事这个行业、开始动手创建自己的数据库，我才真正意识到：“哦，原来书里写的是这个意思！”“哦，原来这也没那么困难！”“哦，书里的知识太老了，这个地方现在应该这么实现。”随着工作经验的逐渐丰富，我开始想：如果有一本书能给初入这一行的工程师介绍“现代数据库的全景”，揭开那层神秘的面纱，那将是一件多么棒的事情啊！
数据库开发者的圈子其实很小，我和本书的作者Alex也是在网上经常沟通的朋友（Alex是Cassandra的PMC成员），记得在2019年年初，我就得知他在写一本关于现代数据库设计的书，在出版后也第一时间入手了英文版。刚读到目录我就觉得这是一本符合我心意的书，它几乎不需要理论背景，深入浅出地介绍了现代数据库技术的全景（更欣慰的是，TiDB也作为例子出现在书中）。我在读完后，甚至从美国带回了很多本，放在公司里作为新工程师入职的学习材料，可见我对其甚是喜爱。更巧的是，本书中文版的译者之一黄鹏程也是我的老相识，得知我极力推崇本书，也邀请我作为一部分章节的审校者。非常荣幸能为本书的中文版贡献一点微薄的力量。
本书的行文和章节设计非常务实，从存储引擎到分布式算法，几乎涵盖了数据库开发的所有常见组件和常用算法。更有意思的是，本书很实际，舍弃了很多古老晦涩的理论，直奔主题，这很有工程师的风格。即使从一个应用开发者的角度来看，能更加理解现代数据库的设计，对于写出更好的程序、做出更好的架构也颇有裨益。简单来说这是一本高效修炼“内功”的好书。
最后，书中丰富的例子、良好的设计、简洁的代码都来自开源社区和开源软件，这些都源自你我这样的开发者和贡献者，大家在一步一步地推动技术的发展，让这一切变为可能。
黄东旭
PingCAP CTO
2020年4月26日于北京
推荐序三
非常开心能提前看到本书中文版部分样章。中文版能在英文原版发行之后的第二年即与读者见面，是译者和编辑辛勤工作的成果，也是我们这些读者的幸运。
作为DBA，多数时候我们只会和一两种数据库产品打交道，日常阅读的材料往往也就局限在了这一两种的范围内。我们常说“隔行如隔山”。根据我的观察，不同数据库产品DBA之间的隔膜程度可能不比产品经理和后端开发两个工种之间小多少。本书的内容不特定于某种数据库产品，适合所有DBA同行和对数据库实现技术有兴趣的工程师阅读。它深入讲解了数据库存储引擎和分布式数据存储的关键技术要素和基础概念，并提供了丰富的延伸阅读材料。它在传统的数据库理论书籍和具体的数据库产品使用指南之间为读者提供了一个坚实的落脚点。不论是数据库新手，还是经验丰富的DBA，都能通过阅读本书夯实基础，找到通往具体数据库产品的扶手和阶梯。
近年来，云计算、大数据和人工智能等领域的诸多工程技术进步正持续影响着传统数据库领域，各种新兴技术和产品一时之间纷至沓来。我们这一代DBA很可能无法指望十数年坚守一两种技术和产品过活了。唯有因应形势、修炼内功才是应对变数和挑战的不二法门。祝愿本书的读者朋友们都能保持好奇心，勤学不辍，积极主动地为组织的业务发展和个人的职业生涯长青积蓄力量，待时而飞。
刘春辉
Shopee DBA Manager，TiDB User Group 2019年度MVA
前言 1
第一部分 存储引擎
第1章 简介与概述 13
1.1 数据库架构 14
1.2 内存数据库与磁盘数据库 16
1.3 面向列与面向行的数据库 17
1.3.1 面向行的数据布局 18
1.3.2 面向列的数据布局 19
1.3.3 区别与优化 20
1.3.4 宽列式存储 20
1.4 数据文件和索引文件 21
1.4.1 数据文件 22
1.4.2 索引文件 23
1.4.3 间接的主索引 24
1.5 缓冲、不可变性和有序性 25
1.6 本章小结 26
第2章 B树基础知识 28
2.1 二分搜索树 28
2.1.1 树的平衡 29
2.1.2 基于磁盘存储的树 31
2.2 基于磁盘的结构 32
2.2.1 机械硬盘 32
2.2.2 固态硬盘 32
2.2.3 磁盘存储结构 34
2.3 无处不在的B树 35
2.3.1 B树的层次结构 36
2.3.2 分隔键 38
2.3.3 B树查找复杂度 39
2.3.4 B树查找算法 39
2.3.5 键的数目 40
2.3.6 B树的节点分裂 40
2.3.7 B树的节点合并 42
2.4 本章小结 43
第3章 文件格式 45
3.1 动机 45
3.2 二进制编码 46
3.2.1 原始类型 46
3.2.2 字符串和变长数据 48
3.2.3 按位打包的数据：布尔值、枚举值和标志 48
3.3 通用原理 49
3.4 页的结构 51
3.5 分槽页 51
3.6 单元格布局 53
3.7 将单元格放进分槽页 54
3.8 管理变长数据 55
3.9 版本 56
3.10 校验和 57
3.11 本章小结 58
第4章 B树的实现 59
4.1 页头 59
4.1.1 魔数 59
4.1.2 同级指针 60
4.1.3 最右指针 60
4.1.4 节点的高键 61
4.1.5 溢出页 62
4.2 二分搜索 64
4.3 传播分裂与合并 65
4.4 再平衡 67
4.5 仅在右侧追加 68
4.6 压缩 69
4.7 清扫与维护 70
4.7.1 更新和删除导致的碎片 70
4.7.2 页的碎片整理 71
4.8 本章小结 72
第5章 事务处理与恢复 74
5.1 缓冲区管理 75
5.1.1 缓存语义 77
5.1.2 缓存回收 77
5.1.3 在缓存中锁定页 78
5.1.4 页置换 79
5.2 恢复 82
5.2.1 日志语义 83
5.2.2 操作日志与数据日志 84
5.2.3 steal和force策略 84
5.2.4 ARIES 85
5.3 并发控制 86
5.3.1 可串行化 86
5.3.2 事务隔离 87
5.3.3 读异常和写异常 88
5.3.4 隔离级别 88
5.3.5 乐观并发控制 90
5.3.6 多版本并发控制 91
5.3.7 悲观并发控制 91
5.3.8 基于锁的并发控制 91
5.4 本章小结 98
第6章 B树的变体 101
6.1 写时复制 101
6.2 抽象节点更新 103
6.3 惰性B树 103
6.3.1 WiredTiger 104
6.3.2 惰性自适应树 105
6.4 FD树 106
6.4.1 分段级联 106
6.4.2 对数级的有序段 108
6.5 Bw树 108
6.5.1 更新链 109
6.5.2 用CAS控制并发 109
6.5.3 结构修改操作 110
6.5.4 合并和垃圾收集 111
6.6 缓存无关B树 112
6.7 本章小结 114
第7章 日志结构存储 116
7.1 LSM树 117
7.1.1 LSM树的结构 118
7.1.2 更新与删除 122
7.1.3 LSM树的查找 123
7.1.4 合并迭代 124
7.1.5 协调 126
7.1.6 LSM树的维护 126
7.2 读写放大与空间放大 129
7.3 实现细节 130
7.3.1 有序字符串表 130
7.3.2 布隆过滤器 132
7.3.3 跳表 133
7.3.4 磁盘访问 135
7.3.5 压缩 136
7.4 无序LSM存储 136
7.4.1 Bitcask 137
7.4.2 WiscKey 138
7.5 LSM树中的并发 139
7.6 日志堆叠 140
7.6.1 闪存转换层 141
7.6.2 文件系统日志记录 142
7.7 LLAMA与精心堆叠 144
7.8 本章小结 145
第一部分总结 147
第二部分 分布式系统
第8章 简介与概述 151
8.1 并发执行 151
8.2 分布式计算的误区 153
8.2.1 处理 154
8.2.2 时钟和时间 155
8.2.3 状态一致性 156
8.2.4 本地和远程执行 157
8.2.5 处理故障的需要 157
8.2.6 网络分区和部分故障 157
8.2.7 级联故障 158
8.3 分布式系统抽象 160
8.4 两将军问题 165
8.5 FLP不可能定理 166
8.6 系统同步性 167
8.7 故障模型 167
8.7.1 崩溃故障 168
8.7.2 遗漏故障 168
8.7.3 任意故障 169
8.7.4 故障处理 169
8.8 本章小结 169
第9章 故障检测 171
9.1 心跳和ping 172
9.1.1 无超时的故障检测器 173
9.1.2 外包心跳 174
9.2 phi增量故障检测器 175
9.3 Gossip和故障检测 175
9.4 反向故障检测 176
9.5 本章小结 177
第10章 领导者选举 179
10.1 霸道选举算法 180
10.2 依次故障转移 181
10.3 候选节点/普通节点优化 182
10.4 邀请算法 183
10.5 环算法 184
10.6 本章小结 185
第11章 复制和一致性 187
11.1 实现可用性 188
11.2 臭名昭著的CAP理论 188
11.2.1 小心使用CAP 189
11.2.2 收成与产量 190
11.3 共享内存 191
11.4 顺序 192
11.5 一致性模型 193
11.5.1 严格一致性 194
11.5.2 可线性化 194
11.5.3 顺序一致性 198
11.5.4 因果一致性 199
11.6 会话模型 202
11.7 最终一致性 204
11.8 可调一致性 204
11.9 见证者副本 206
11.10 强最终一致性和CRDT 207
11.11 本章小结 209
第12章 反熵和传播 212
12.1 读修复 213
12.2 摘要读 214
12.3 提示移交 215
12.4 Merkle树 215
12.5 位图版本向量 216
12.6 Gossip传播 218
12.6.1 Gossip技术细节 219
12.6.2 覆盖网络 219
12.6.3 混合Gossip 220
12.6.4 局部视图 221
12.7 本章小结 222
第13章 分布式事务 224
13.1 多个操作的原子性 225
13.2 两阶段提交 226
13.2.1 2PC中的参与者故障 227
13.2.2 2PC中的协调者故障 228
13.3 三阶段提交 229
13.4 Calvin分布式事务 231
13.5 Spanner分布式事务 233
13.6 数据库分区 235
13.7 Percolator分布式事务 236
13.8 协调避免 238
13.9 本章小结 240
第14章 共识 243
14.1 广播 244
14.2 原子广播 245
14.2.1 虚同步 245
14.2.2 Zookeeper原子广播 246
14.3 Paxos 248
14.3.1 Paxos算法 249
14.3.2 Paxos的Quorum 250
14.3.3 故障场景 251
14.3.4 Multi-Paxos 253
14.3.5 快速Paxos 254
14.3.6 平等Paxos 255
14.3.7 柔性Paxos 257
14.3.8 共识的推广解法 259
14.4 Raft 261
14.4.1 Raft中的领导者角色 263
14.4.2 故障场景 264
14.5 拜占庭共识 266
14.5.1 PBFT算法 266
14.5.2 恢复和检查点 268
14.6 本章小结 269
第二部分总结 272
参考文献 275
