分布式数据库设计参考
2022-11-20 21:34:47 
阿炯
一、存储引擎原理
摘要
数据库的一个首要目标是可靠并高效地管理数据，以供人们使用。进而不同的应用可以使用相同的数据库来共享它们的数据。数据库的出现使人们放弃了为每个独立的应用开发数据存储的想法，同时，随着数据库广泛的使用，其处理能力飞速发展，演进出如现代的分布式数据库这般惊人的能力。为了支撑抽象的多种场景。一般的数据库都会采用多模块或多子系统的架构来构建数据库，从而方便数据库项目团队依据现实的场景来组合不同的子模块，进而构造出一众丰富的数据库产品。而存储引擎就是这一众模块中极为重要的一环。
分布式数据库就是为了解决存储可扩展性的一类数据库。多认为除了最初的分库分表方案，分布式数据库经历了三个主要发展阶段。第一代是分布式中间件的形式，大多数是基于MySQL数据库做Data Sharding和水平扩展；第二代是以Cassandra、MongoDB为代表的NoSQL；第三代是以AWS Aurora和Google Spanner为代表的云数据库，或者称作NewSQL。这三个阶段在分布式这个概念上没有本质上的区别，但是在具体的实现上有不同的侧重点，比如NoSQL就不支持跨分片的ACID事务。大家要注意并不是越新的概念的就越先进，实际上，现在市面上主流的分布式数据库，大多是分布式中间件的形式。
目前主流的数据库文件系统有两类，一类是关系型数据库（如MySQL）使用的B+Tree，另一类是多用于键值存储数据库（如NoSQL）的LSM-Tree数据结构。分布式数据库建立在分布式文件系统之上，在底层实现上也是依赖于这两类数据结构的。
1、存储引擎的定位
这个世界上，没有针对数据库设计的一定之规。每个数据库都是根据它所要解决的问题，并结合其他因素慢慢发展成如今的模样的。所以数据库子模块的分化也没有一个广泛接受的标准，且有些模块之间的边界也是很模糊的。特别是需要优化数据库性能时，原有被设计为独立存在的模块很可能会融合以提高数据库整体性能。比较典型的分布式数据库的架构和模块组合标准，因为这是大部分分布式数据库的架构模式。
传输层：它是接受客户端请求的一层。用来处理网络协议。同时，在分布式数据库中，它还承担着节点间互相通信的职责。
查询层：请求从传输层被发送到查询层。在查询层，协议被进行解析，如 SQL 解析；后进行验证与分析；最后结合访问控制来决定该请求是否要被执行。解析完成后，请求被发送到查询优化器，在这里根据预制的规则，数据分布并结合数据库内部的统计，会生成该请求的执行计划。执行计划一般是树状的，包含一系列相关的操作，用于从数据库中查询到请求希望获取的数据。
执行层（存储引擎层）：执行计划被发送到执行层去运行。执行层一般包含本地运行单元与远程运行单元。根据执行计划，调用不同的单元，而后将结果合并返回到传输层。
细心的读者可能会注意到，这里只有查询层，那么数据是怎么写入的？这对于不同的数据库，答案会非常不同。有的数据库会放在传输层，由于协议简单，就不需要额外处理，直接发送到执行层；而有些写入很复杂，会交给查询层进行处理。
以上就是数据库领域中比较常见的模块划分方式。你可能有这样的疑问：那么存储引擎在哪里呢？
执行层本地运行单元其实就是存储引擎。它一般包含如下一些功能：
事务管理器：用来调度事务并保证数据库的内部一致性（这与模块一中讨论的分布式一致性是不同的）；
锁管理：保证操作共享对象时候的一致性，包括事务、修改数据库参数都会使用到它；
存储结构：包含各种物理存储层，描述了数据与索引是如何组织在磁盘上的；
内存结构：主要包含缓存与缓冲管理，数据一般是批量输入磁盘的，写入之前会使用内存去缓存数据；
提交日志：当数据库崩溃后，可以使用提交日志恢复系统的一致性状态。
以上就是存储引擎比较重要的几个功能，其核心就是提供数据读写功能，故一般设计存储引擎时，会提供对其写入路径与读取路径的描述。
2、内存与磁盘
存储引擎中最重要的部分就是磁盘与内存两个结构。而根据数据在它们之中挑选一种作为主要的存储，数据库可以被分为内存型数据库与磁盘型数据库。由此可见存储引擎的一个功能，就是可以被作为数据库类型划分的依据，可见引擎的重要性。
2.1内存型存储
内存型存储是把数据主要存储在内存里，其目的很明显，就是加快数据读写性能。分布式数据库一个重要的门类就是内存型数据库，包括 Redis、NuoDB 和 MySQL Cluster 等。当然其缺点也很明显，那就是内存的成本较高，且容量有限。而分布式的架构能有效地扩充该类数据库的容量，这也是内存数据库主要是分布式数据库的原因。
2.2磁盘型存储
磁盘存储相对传统，它存储主要数据，而内存主要作为缓冲来使写入批量化。磁盘存储的好处是，存储性价比较高，这主要得益于磁盘甚至是磁带的单位存储价格相比内存非常低廉。但是与内存型数据库相比，磁盘型数据库的性能比较低。不过，随着近年 SSD 磁盘的普及，这种趋势得到了有效的改善。
这两种存储引擎的差别还体现在功能实现的难度上。内存型数据库相对简单，因为写入和释放随机的内存空间是相对比较容易的；而磁盘型数据库需要处理诸如数据引用、文件序列化、碎片整理等复杂的操作，实现难度很高。
3、行式存储与列式存储
数据一般是以表格的形式存储在数据库中的，所以所有数据都有行与列的概念。但这只是一个逻辑概念，我们将要介绍的所谓“行式”和“列式”体现的其实是物理概念。
3.1 行式存储
行式存储会把每行的所有列存储在一起，从而形成数据文件。当需要把整行数据读取出来时，这种数据组织形式是比较合理且高效的。但是如果要读取多行中的某个列，这种模式的代价就很昂贵了，因为一些不需要的数据也会被读取出来。
3.2 列式存储
而列式存储与之相反，不同行的同一列数据会被就近存储在一个数据文件中。同时除了存储数据本身外，还需要存储该数据属于哪行。而行式存储由于列的顺序是固定的，不需要存储额外的信息来关联列与值之间的关系。
列式存储非常适合处理分析聚合类型的任务，如计算数据趋势、平均值，等等。因为这些数据一般需要加载一列的所有行，而不关心的列数据不会被读取，从而获得了更高的性能。
会发现 OLTP 数据库倾向于使用行式存储，而 OLAP 数据库更倾向于列式存储，正是这两种存储的物理特性导致了这种倾向性。而 HATP 数据库也是融合了两种存储模式的一种产物。
当然这里要区分 HBase 和 BigTable 所说的宽列存储与列存储在本质上是不同的。宽列存储放在其中的数据的列首先被聚合到了列簇上，列簇被放在不同的文件中；而列簇中的数据其实是按行进行组织的。
当然，选择这两种存储模式最重要的因素还是访问模式。如果数据主要是按照行进行读取，比如交易场景、资料管理场景等，那么行式存储应是首选。如果需要经常查询所有数据做聚合，或者进行范围扫描，那么列式存储就很值得一试。
4、数据文件与索引文件
上文介绍了内存与磁盘之间的取舍，从中可看到磁盘其实更为重要的，因为数据库是提供数据持久化存储的服务。故我们开始介绍磁盘上最为重要的两类文件：数据文件和索引文件。
数据文件和索引文件如名字所示，分别保存原始数据与检索数据用的索引数据。但是随着时间的推移，两者的区分也不是那么泾渭分明了。其中以 IOT（索引组织表）模式为代表的数据文件在数据库，特别是分布式数据库中占据越来越重的位置。一种将两者进行融合的趋势已经变得势不可挡。
数据文件最传统的形式为堆组织表（Heap-Organized Table），数据的放置没有一个特别的顺序，一般是按照写入的先后顺序排布。这种数据文件需要一定额外的索引帮助来查找数据。
另外有两种数据表形式自带了一定的索引数据能力，即哈希组织表（Hash-Organized Table）和索引组织表（Index-Organized Table）。前者是将数据通过哈希函数分散到一组数据桶内，桶内的数据一般是按照一定规则进行排序，以提高查询效率；而后者一般采用索引文件的形式来存储数据，以 B+树为例，数据被存储在叶子节点上，这样做的目的是减少检索数据时读取磁盘的次数，同时对范围扫描支持友好。
索引文件的分类模式一般为主键索引与二级索引两类。前者是建立在主键上的，它可能是一个字段或多个字段组成。而其他类型的索引都被称为二级索引。主键索引与数据是一对一关系，而二级索引很有可能是一对多的关系，即多个索引条目指向一条数据。
这里按照索引与数据之间结合的程度，我们又可以把索引分为聚簇索引和非聚簇索引。前者如哈希组织表和索引组织表那样，数据的分布与索引分布是有关联的，它们被“聚”在一起，这样的查询效率很好。而后者最常见的例子就是针对这两种数据文件的二级索引，因为二级索引要索引的列不是主键，故索引与数据是分割的，查询时需要进行多次磁盘读取。但是对于写入，聚簇索引可能需要进行唯一判断，性能会比简单构建的非聚簇索引低效。
最后一点需要说明的是，二级索引需要保存指向最终数据的“引用”。从实现层面上，这个引用可以是数据的实际位置，也可以是数据的主键。前者的好处是查询效率高，而写入需要更新所有索引，故性能相对较低。而后者就恰好相反，查询需要通过主键索引进行映射，效率稍低，但写入性能很稳定，如 MySQL 就是选用后者作为其索引模式。
5、面向分布式的存储引擎
5.1 内存型数据库会倾向于选择分布式模式来进行构建
原因也是显而易见的，由于单机内存容量相比磁盘来说是很小的，故需要构建分布式数据库来满足业务所需要的容量。
5.2 列式存储也与分布式数据库存在天然的联系。
可以去研究一下，很多列式相关的开源项目都与 Hadoop 等平台有关系的。原因是针对 OLAP 的分析数据库，一个非常大的应用场景就是要分析所有数据。
而列式存储可以被认为是这种模式的一种优化，实现该模式的必要条件是要有分布式系统，因为一台机器的处理能力是有瓶颈的。如果希望处理超大规模数据，那么将数据分散到多个节点就成为必要的方式。所以说，列模式是由分析性分布式的优化需求所流行起来的。
至于宽列存储更是分布式数据库场景下才会采用的模式。数据文件的组织形式，分布式数据库几乎不会使用堆组织表。因为该形式过于随意，无法有效地分散数据。不知道学习过数据分片那一讲的时候你有没有注意到，另外两种组织表的名字与两种分片算法是有着天然联系的。哈希组织表数据经过哈希函数散列到不同的桶，这些桶可以被分散到不同节点。而索引组织表一般叶子节点是按一定顺序排列的，这与范围分片又有着某种契合的关系。所以分布式数据库一般都会采用这两种模式作为其存储引擎，甚至一些分布式数据库直接将数据文件当作索引使用。
6、LSM树存储引擎
典型的面向分布式数据库所使用的存储引擎。从其特点可以看到，它高速写入的特性对分布式数据库而言是有非常大吸引力的，同时其KV 结构更是分片所喜欢的一种数据格式，非常适合基于此构建分布式数据库。所以诸如 Apache Cassandra、ClickHouse 和 TiDB 等分布式数据库都选用 LSM 树或类似结构的存储引擎来构建分布式数据库。
LSM-Tree，全称Log Structured Merge Tree，是一种写入操作不做原地更新，而是以追加的方式写入内存，每次写到一定程度，即冻结为一层，然后写入持久化存储的数据结构。可以简单描述一下一条数据在LSM-Tree中的写入过程：写入Log -> 写入memtable -> flush入持久化存储 -> 经compaction操作进入持久化存储的更新层 -> 同一key的新数据到来时丢弃。下面是一张LSM-Tree的结构图：
LSM 树存储引擎的结构暗含在它的名字内。LS 代表日志结构，说明它是以日志形式来存储数据的，那么日志有什么特点呢？如果你对财务记账有些了解的话，会知道会计在删除一笔记录时，是不会直接拿着橡皮擦去擦掉这个记录的，而是会写一笔与原金额相等的冲抵操作。这就是典型的日志型存储的模式。
日志型存储的特点是对写入非常友好，不像 B 树等结构需要进行随机写，日志存储可以进行顺序性写。因为我们常用的 HDD 磁盘是有旋转机构的，写入延迟主要发生在磁盘旋转与读写臂的移动上。如果数据可以顺序写入，可以大大加快这种磁盘机构的写入速度。
而 M 则暗含这个结构会存在合并操作，形成最终的可读取结构。这样读取操作就不用去查找对于该记录的所有更改了，从而加快了读取速度。同时将多个记录合并为一个最终结果，也节省了存储空间。虽然合并操作有诸多优点，但是它也不是没有代价的，那就是会消耗一定的计算量和存储空间。
6.1 LSM树的内存结构
LSM 树包含内存驻留单元和磁盘驻留单元。首先数据会写入内存的一个缓冲中，而后再写到磁盘上的不可变文件中。
内存驻留单元一般被称为 MemTable（内存表），是一个可变结构。它被作为一个数据暂存的缓冲使用，同时对外提供读取服务。当其中的数据量到达一个阈值后，数据会被批量写入磁盘中的不可变文件内。
磁盘驻留单元，也就是数据文件，是在内存缓冲刷盘时生成的。且这些数据文件是不可变的，只能提供读取服务。而相对的，内存表同时提供读写两个服务。
关于 LSM 树的结构，一般有双树结构和多树结构两种。前者一般是一个理论说明，目前没有一个实际的存储引擎是使用这种结构的。所以我简单说一下双树概念，它有助于你去理解多树结构。
双树中的两棵树分别指：内存驻留单元和磁盘驻留单元中分别有一棵树，你可以想象它们都是 B 树结构的。刷盘的时候，内存数据与磁盘上部分数据进行合并，而后写到磁盘这棵大树中的某个节点下面。成功后，合并前的内存数据与磁盘数据会被移除。
可以看到双树操作是比较简单明了的，而且可以作为一种 B 树类的索引结构而存在。但实际上几乎没有存储引擎去使用它，主要原因是它的合并操作是同步的，也就是刷盘的时候要同步进行合并。而刷盘本身是个相对频繁的操作，这样会造成写放大，也就是会影响写入效率且会占用非常大的磁盘空间。
多树结构是在双树的基础上提出的，内存数据刷盘时不进行合并操作，而是完全把内存数据写入到单独的文件中。那这个时候另外的问题就出现了：随着刷盘的持续进行，磁盘上的文件会快速增加。这时，读取操作就需要在很多文件中去寻找记录，这样读取数据的效率会直线下降。
为了解决这个问题，此种结构会引入合并操作（Compaction）。该操作是异步执行的，它从这众多文件中选择一部分出来，读取里面的内容而后进行合并，最后写入一个新文件中，而后老文件就被删除掉了。如下图所示，这就是典型的多树结构合并操作。而这种结构也是本节介绍的主要结构。
6.2 刷盘的流程
数据首先写入当前内存表，当数据量到达阈值后，当前数据表把自身状态转换为刷盘中，并停止接受写入请求。此时会新建另一个内存表来接受写请求。刷盘完成后，由于数据在磁盘上，除了废弃内存表的数据外，还对提交日志进行截取操作。而后将新数据表设置为可以读取状态。
在合并操作开始时，将被合并的表设置为合并中状态，此时它们还可以接受读取操作。完成合并后，原表作废，新表开始启用提供读取服务。
6.3 查询、更新与删除、合并操作
查询操作本身并没有 LSM 树的特色操作。由于目标数据可能在内存表或多个数据表中，故需要对多个数据源的结果数据进行归并操作。其中使用了排序归并操作，原因也非常简单，因为不论是内存表还是数据表，其中的数据都已经完成了排序。排序归并算法广泛应用在多种数据库中，如 Oracle、MySQL，等等。另外数据库中间 Apache ShardingShpere 在处理多数据源 order by 时，也使用了这个方法。
而查询另外一个问题是处理同一份数据不同版本的情况，虽然合并操作可以解决部分问题，但合并前的数据还需要通过查询机制来解决。我刚介绍过 LSM 树中对数据的修改和删除本质上都是增加一条记录，因此数据表和内存表中，一份数据会有多条记录，这个时候查询就需要进行冲突处理。一般一份数据的概念是它们具有相同的 key，而往往不同的版本会有时间戳，根据这个时间戳可以建立写入顺序，这类似于向量时钟的概念。故查询中我们很容易判断哪条数据是最新数据。
更新和删除操作本质上是插入数据，然后根据上面提到的冲突处理机制和合并操作来获取最终数据。更新操作是比较简明的，插入新数据就好了。但是删除操作时插入的是什么呢？
一般插入的是特殊的值，被称作墓碑（Tombstone）。它是一个特殊的值，用来表示记录被删除。如果要产出一个范围内数据呢？Apache Cassandra 的处理方法是引入范围墓碑（Range Tombstone）。
比如有从 k0 到 k9 的 9 条数据，在 k3 处设置开始删除点（包含 k3），在 k7 处设置结束删除点（不包含 k7），那么 k3 到 k6 这四条数据就被删除了。此时查询就会查不到 k4 到 k6，即使它们上面没有设置墓碑。
合并操作是用来维护 LSM 树的结构的，以保证其可以正常运行。需要强调的一点是，我们这里说的合并操作针对的是 LSM 树的结构里面提到的多树结构。在多树结构中，磁盘中表的数量随着刷盘动作的持续进行，而变得越来越多。合并操作正是让它们减少的一种手段。
合并操作会根据一定规则，从磁盘的数据文件中选择若干文件进行合并，而后将新文件写入磁盘，成功后会删除老数据。在整个操作的过程中，对内存的消耗是完全可控的。这是由于每个数据文件都是经过排序的，如上一讲提到的查询规则一样，我们依然可以通过排序归并来合并多个文件中的数据。这种合并每次只会加载部分数据，也就是每个文件头部的数据，进入内存进行合并操作。从而很好地控制了合并操作对内存资源的消耗。
在整个合并的过程中，老的数据表依然可以对外提供读取服务，这说明老数据依然在磁盘中。这就要求磁盘要留有一定的额外空间来容纳生成中的新数据表。同时合并操作可以并行执行，但是一般情况下它们操作的数据不会重合，以免引发竞争问题。合并操作既可以将多个数据文件合并成一个，也可以将一个数据文件拆分成多个。
常见的合并策略有 Size-Tiered Compaction 和 Leveled Compaction。
6.3.1 Size-Tiered Compaction合并算法
其中，数据表按照大小进行合并，较小的数据表逐步合并为较大的数据表。第一层保存的是系统内最小的数据表，它们是刚刚从内存表中刷新出来的。合并过程就是将低层较小的数据表合并为高层较大的数据表的过程，Apache Cassandra 使用过这种合并策略。该策略的优点是比较简单，容易实现。但是它的空间放大性很差，合并时层级越高该问题越严重。比如有两个 5GB 的文件需要合并，那么磁盘至少要保留 10GB 的空间来完成这次操作，可想而知此种容量压力是巨大的，必然会造成系统不稳定。
6.3.2 Leveled Compaction
如名称所示，该策略是将数据表进行分层，按照编号排成 L0 到 Ln 这样的多层结构。L0 层是从内存表刷盘产生的数据表，该层数据表中间的 key 是可以相交的；L1 层及以上的数据，将 Size-Tiered Compaction 中原本的大数据表拆开，成为多个 key 互不相交的小数据表，每层都有一个最大数据量阈值，当到达该值时，就出发合并操作。每层的阈值是按照指数排布的，例如 RocksDB 文档中介绍了一种排布：L1 是 300MB、L2 是 3GB、L3 是 30GB、L4 为 300GB。
上图概要性地展示了从 L1 层开始，每个小数据表的容量都是相同的，且数据量阈值是按 10 倍增长。即 L1 最多可以有 10 个数据表，L2 最多可以有 100 个，以此类推。随着数据表不断写入，L1 的数据量会超过阈值。这时就会选择 L1 中的至少一个数据表，将其数据合并到 L2 层与其 key 有交集的那些文件中，并从 L1 中删除这些数据。
仍然以上图为例，一个 L1 层数据表的 key 区间大致能够对应到 10 个 L2 层的数据表，所以一次合并会影响 11 个文件。该次合并完成后，L2 的数据量又有可能超过阈值，进而触发 L2 到 L3 的合并，如此往复。可见，Leveled Compaction 与 Size-Tiered Compaction 相比，每次合并时不必再选取一层内所有的数据，并且每层中数据表的 key 区间都是不相交的，重复 key 减少了，所以很大程度上缓解了空间放大的问题。
当然在实际应用中会组合两种策略，比如经典的 RocksDB 会在 L0 合并到 L1 时，使用 Size-Tiered Compaction；而从 L1 开始，则是采用经典的 Leveled Compaction。这其中原因是 L0 的数据表之间肯定会存在相同的 key。
6.3.3 RUM 假说
开始介绍这个假说之前，你要先明确几个“放大”概念。
读放大：它来源于在读取时需要在多个文件中获取数据并解决数据冲突问题，如查询操作中所示的，读取的目标越多，对读取操作的影响越大，而合并操作可以有效缓解读放大问题。
写放大：对于 LSM 树来说，写放大来源于持续的合并操作，特别是 Leveled Compaction，可以造成多层连续进行合并操作，这样会让写放大问题呈几何倍增长。
空间放大：这是我在说合并的时候提到过的概念，是指相同 key 的数据被放置了多份，这是在合并操作中所产生的。尤其是 Size-Tiered Compaction 会有严重的空间放大问题。
那么可以同时解决以上三种问题吗？根据 RUM 的假说，答案是不能。
该假说总结了数据库系统优化的三个关键参数：读取开销（Read）、更新开销（Update）和内存开销（Memory），也就是 RUM。对应到上面三种放大，可以理解为 R 对应读放大、U 对应写放大，而 M 对应空间放大（Memory 可以理解为广义的存储，而不仅仅指代内存）。
该假说表明，为了优化上述两项的开销必然带来第三项开销的上涨，可谓鱼与熊掌不可兼得。而 LSM 树是用牺牲读取性能来尽可能换取写入性能和空间利用率。
而有的人会发现，合并操作会带来空间放大的问题，理论上应该会浪费空间。但是 LSM 树由于其不可变性，可以引入块压缩，来优化空间占用使用，且内存不需要做预留（B 树需要额外预留内存来进行树更新操作），从而使其可以很好地优化空间。
应该知道，RUM 所描述的内容过于简单，一些重要指标如延迟、维护性等没有涵盖其中，但是它可以作为我们工具箱里面的一个短小精干的扳手，来快速分析和掌握一个存储引擎的特点。
B+Tree VS LSM-Tree
来比较一下这两类数据结构，明确它们的特性和适用场景。
B+Tree将数据拆分为固定大小的Block或Page，Page是读写的最小单位。B+Tree可以做到原地更新和删除，因此对数据库事务的支持更加友好，因为一个key只会出现一个Page页里面。而LSM-Tree的设计思路是将数据拆分为几百M大小的Segment，并顺序写入。LSM-Tree只能追加写，并且在L0层key的range会重叠，所以对事务支持较弱，只能在Segment Compaction的时候真正地更新和删除。
B+Tree的优点是支持高效的读（稳定的O(logN)的复杂度），但对大规模的写请求的效率就比较低（O(logN)复杂度），这是因为在大规模写的情况下，为了维护B+Tree的结构，B+Tree的节点就会不断分裂，操作磁盘的随机读写概率会变大，从而导致写性能降低。LSM-Tree则相反，支持高吞吐量的写（O(1)），但普通LSM-Tree读取的复杂度是O(n)，在使用索引或者缓存优化后可以达到O(logN)。
可以粗略的认为未优化的LSM-Tree的写比B+Tree快一个数量级，未优化的LSM-Tree的读比B+Tree慢一个数量级。
第一代分布式数据库：分库分表及分布式中间件
最初面对存储扩展问题，一个比较直接的思路就是分库分表——一个库装不下，我就用多个库装。
假设一开始有一个单点的MySQL数据库，随着业务增长，达到了单库的存储性能瓶颈，准备使用三到五个MySQL来重新安排存储。在最理想的情况下，我们可以在拥有原来三到五倍存储空间的情况下，也能有三到五倍的并发来提升存储性能。
但这有两个很明显的问题：第一个是我要对业务进行大量的改造，找到一个合适的维度打散业务进入多个库（而且这种完美的方案还不一定存在），而且跨库的业务也要重新写业务逻辑。第二个是一旦库又满了，我想再做一次扩容的工作，我就又要把这部分的工作再做一次——包括重写业务。
上面两个问题的代价显然是不可承受的，这时候就有分布式数据库厂家来说了：我们来做整合并管理多个库的工作，你们应用只要把多个数据库当作原来的一个库使用即可。
这就诞生了分布式中间件的概念，或者称作分布式关系型数据库。分布式中间件，是从关系型数据库出发，加入分布式技术，实现分布式的高可用性和高扩展性等特性。本文把此类数据库称为分布式中间件，不代表它们就没有对底层数据库（通常是MySQL）做任何改动。实际上，目前市面上的分布式关系型数据库几乎都对底层数据库有自己的修改，甚至有阿里的OceanBase那样自己实现一个关系型底层的情况。
但分布式中间件有根本解决上面的两个问题吗？显然并没有。分布式中间件没有把数据自动分片的能力，应用也不能真真正正的把分布式数据库当作一个单库来使用——除非你完全不在乎跨片的性能损耗。
但分布式中间件也确确实实有很大的作用，它极大的减少了业务的改造量，也保证了了分布式事务的ACID特性。在各类分布式中间件迭代发展的过程中，这一技术路线也在逐渐进步：厂家开始探索对底层数据库的改造，以使其更适应分布式特性；中间件层也吸收了后面NewSQL的一些技术思路，在全局事务管理、数据增量写入等方面做了很多优化。
普通分布式中间件
大部分分布式中间件的架构一般有以下三个部分：
客户端：通常为MySQL5.7或8.0版本的客户端，支持JDBC访问。
存储层：由多个MySQL实例组成，引擎为InnoDB。
计算层（中间件层）：组织并管理存储层的MySQL实例，接受并解析客户端传来的SQL请求。计算层通常用片的概念把存储层的MySQL分割，然后以片为单位进行多副本来实现高可用。计算层显式或隐式的有一个事务管理组件，负责给事务赋一个全局唯一的ID，这个组件是实现分布式事务一致性的一种重要的解决方案。计算层对客户端屏蔽多副本和事务ID，会对客户端发来的普通SQL进行拆分和改造，并生成分布式的执行计划，然后下发到存储层的MySQL实例执行。
第二代分布式数据库：NoSQL
在早期分库分表方案发展过程中，好多公司都面临了因扩容而无限次改造业务的痛苦。他们再次观察业务，发现业务并不复杂——至少没复杂到需要使用高级SQL的地步。这样NoSQL干脆就抛弃了高级SQL（分布式ACID特性），从而换来对业务透明的特性和强水平扩展的能力。这样做的好处显而易见——只要你能忍受不用高级SQL这一点，那么你只要进行一次到NoSQL的改造，后面就可以近乎无限的扩容，无需任何业务的适配。
各种NoSQL，如HBase,Cassandra,Leveldb,RocksDB底层的数据结构，都是LSM-Tree。因为NoSQL不支持分布式ACID特性，和其他分布式数据库差别较大，所以不列入后面对事务的讨论。
第三代分布式数据库：NewSQL
上面的分库分表、分布式中间件和NoSQL都不可避免的由一个业务侵入性的问题，有些前沿厂家就产生了把二者结合起来，设计一个兼具分布式事务一致性和强可扩展性的数据库的想法——这就是NewSQL的诞生。在NewSQL领域，有两个流派，分别是Amazon的Aurora和Google的Spanner。
Aurora流派也被称作Shared Everything，目前这个流派，多是被部署到虚拟计算环境中的云数据库，本文涉及的云数据库有阿里的PolarDB，Amazon的Aurora以及华为云数据库Taurus。该流派最重要的一个概念就是Log is Database。这个概念是把log写到存储层，由存储层负责重放log、回写page并尽量减少写放大。
基于LSM-Tree分层存储能够做到写的高吞吐，带来的副作用是整个系统必须频繁的进行compaction，写入量越大，Compaction操作越频繁。而Compaction操作非常消耗CPU和IO，在高吞吐的情况下，大量的Compaction操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响。
Spanner流派也称作Shared Nothing。与分布式中间件不同的是，它是从分布式系统出发，再来做存储，做查询，利用天然的扩展能力和列存的性能优势，实现基于KV存储的支持关系型查询的数据库。如TiDB就是一个NewSQL的商业化的实现。
对Spanner的所有了解都来自Google于2012年发表的论文《Spanner: Google's Globally-Distributed Database》。该论文中有两个十分重的论点：一个是TrueTime API的实现，给Spanner提供了全局的时钟接口，在此基础上Spanner才能实现强的全局一致性保证；另一个是论文中对Spanner的分布式事务实现细节进行了详细的描述。
摘要
数据库的一个首要目标是可靠并高效地管理数据，以供人们使用。进而不同的应用可以使用相同的数据库来共享它们的数据。数据库的出现使人们放弃了为每个独立的应用开发数据存储的想法，同时，随着数据库广泛的使用，其处理能力飞速发展，演进出如现代的分布式数据库这般惊人的能力。为了支撑抽象的多种场景。一般的数据库都会采用多模块或多子系统的架构来构建数据库，从而方便数据库项目团队依据现实的场景来组合不同的子模块，进而构造出一众丰富的数据库产品。而存储引擎就是这一众模块中极为重要的一环。
分布式数据库就是为了解决存储可扩展性的一类数据库。多认为除了最初的分库分表方案，分布式数据库经历了三个主要发展阶段。第一代是分布式中间件的形式，大多数是基于MySQL数据库做Data Sharding和水平扩展；第二代是以Cassandra、MongoDB为代表的NoSQL；第三代是以AWS Aurora和Google Spanner为代表的云数据库，或者称作NewSQL。这三个阶段在分布式这个概念上没有本质上的区别，但是在具体的实现上有不同的侧重点，比如NoSQL就不支持跨分片的ACID事务。大家要注意并不是越新的概念的就越先进，实际上，现在市面上主流的分布式数据库，大多是分布式中间件的形式。
目前主流的数据库文件系统有两类，一类是关系型数据库（如MySQL）使用的B+Tree，另一类是多用于键值存储数据库（如NoSQL）的LSM-Tree数据结构。分布式数据库建立在分布式文件系统之上，在底层实现上也是依赖于这两类数据结构的。
1、存储引擎的定位
这个世界上，没有针对数据库设计的一定之规。每个数据库都是根据它所要解决的问题，并结合其他因素慢慢发展成如今的模样的。所以数据库子模块的分化也没有一个广泛接受的标准，且有些模块之间的边界也是很模糊的。特别是需要优化数据库性能时，原有被设计为独立存在的模块很可能会融合以提高数据库整体性能。比较典型的分布式数据库的架构和模块组合标准，因为这是大部分分布式数据库的架构模式。
传输层：它是接受客户端请求的一层。用来处理网络协议。同时，在分布式数据库中，它还承担着节点间互相通信的职责。
查询层：请求从传输层被发送到查询层。在查询层，协议被进行解析，如 SQL 解析；后进行验证与分析；最后结合访问控制来决定该请求是否要被执行。解析完成后，请求被发送到查询优化器，在这里根据预制的规则，数据分布并结合数据库内部的统计，会生成该请求的执行计划。执行计划一般是树状的，包含一系列相关的操作，用于从数据库中查询到请求希望获取的数据。
执行层（存储引擎层）：执行计划被发送到执行层去运行。执行层一般包含本地运行单元与远程运行单元。根据执行计划，调用不同的单元，而后将结果合并返回到传输层。
细心的读者可能会注意到，这里只有查询层，那么数据是怎么写入的？这对于不同的数据库，答案会非常不同。有的数据库会放在传输层，由于协议简单，就不需要额外处理，直接发送到执行层；而有些写入很复杂，会交给查询层进行处理。
以上就是数据库领域中比较常见的模块划分方式。你可能有这样的疑问：那么存储引擎在哪里呢？
执行层本地运行单元其实就是存储引擎。它一般包含如下一些功能：
事务管理器：用来调度事务并保证数据库的内部一致性（这与模块一中讨论的分布式一致性是不同的）；
锁管理：保证操作共享对象时候的一致性，包括事务、修改数据库参数都会使用到它；
存储结构：包含各种物理存储层，描述了数据与索引是如何组织在磁盘上的；
内存结构：主要包含缓存与缓冲管理，数据一般是批量输入磁盘的，写入之前会使用内存去缓存数据；
提交日志：当数据库崩溃后，可以使用提交日志恢复系统的一致性状态。
以上就是存储引擎比较重要的几个功能，其核心就是提供数据读写功能，故一般设计存储引擎时，会提供对其写入路径与读取路径的描述。
2、内存与磁盘
存储引擎中最重要的部分就是磁盘与内存两个结构。而根据数据在它们之中挑选一种作为主要的存储，数据库可以被分为内存型数据库与磁盘型数据库。由此可见存储引擎的一个功能，就是可以被作为数据库类型划分的依据，可见引擎的重要性。
2.1内存型存储
内存型存储是把数据主要存储在内存里，其目的很明显，就是加快数据读写性能。分布式数据库一个重要的门类就是内存型数据库，包括 Redis、NuoDB 和 MySQL Cluster 等。当然其缺点也很明显，那就是内存的成本较高，且容量有限。而分布式的架构能有效地扩充该类数据库的容量，这也是内存数据库主要是分布式数据库的原因。
2.2磁盘型存储
磁盘存储相对传统，它存储主要数据，而内存主要作为缓冲来使写入批量化。磁盘存储的好处是，存储性价比较高，这主要得益于磁盘甚至是磁带的单位存储价格相比内存非常低廉。但是与内存型数据库相比，磁盘型数据库的性能比较低。不过，随着近年 SSD 磁盘的普及，这种趋势得到了有效的改善。
这两种存储引擎的差别还体现在功能实现的难度上。内存型数据库相对简单，因为写入和释放随机的内存空间是相对比较容易的；而磁盘型数据库需要处理诸如数据引用、文件序列化、碎片整理等复杂的操作，实现难度很高。
3、行式存储与列式存储
数据一般是以表格的形式存储在数据库中的，所以所有数据都有行与列的概念。但这只是一个逻辑概念，我们将要介绍的所谓“行式”和“列式”体现的其实是物理概念。
3.1 行式存储
行式存储会把每行的所有列存储在一起，从而形成数据文件。当需要把整行数据读取出来时，这种数据组织形式是比较合理且高效的。但是如果要读取多行中的某个列，这种模式的代价就很昂贵了，因为一些不需要的数据也会被读取出来。
3.2 列式存储
而列式存储与之相反，不同行的同一列数据会被就近存储在一个数据文件中。同时除了存储数据本身外，还需要存储该数据属于哪行。而行式存储由于列的顺序是固定的，不需要存储额外的信息来关联列与值之间的关系。
列式存储非常适合处理分析聚合类型的任务，如计算数据趋势、平均值，等等。因为这些数据一般需要加载一列的所有行，而不关心的列数据不会被读取，从而获得了更高的性能。
会发现 OLTP 数据库倾向于使用行式存储，而 OLAP 数据库更倾向于列式存储，正是这两种存储的物理特性导致了这种倾向性。而 HATP 数据库也是融合了两种存储模式的一种产物。
当然这里要区分 HBase 和 BigTable 所说的宽列存储与列存储在本质上是不同的。宽列存储放在其中的数据的列首先被聚合到了列簇上，列簇被放在不同的文件中；而列簇中的数据其实是按行进行组织的。
当然，选择这两种存储模式最重要的因素还是访问模式。如果数据主要是按照行进行读取，比如交易场景、资料管理场景等，那么行式存储应是首选。如果需要经常查询所有数据做聚合，或者进行范围扫描，那么列式存储就很值得一试。
4、数据文件与索引文件
上文介绍了内存与磁盘之间的取舍，从中可看到磁盘其实更为重要的，因为数据库是提供数据持久化存储的服务。故我们开始介绍磁盘上最为重要的两类文件：数据文件和索引文件。
数据文件和索引文件如名字所示，分别保存原始数据与检索数据用的索引数据。但是随着时间的推移，两者的区分也不是那么泾渭分明了。其中以 IOT（索引组织表）模式为代表的数据文件在数据库，特别是分布式数据库中占据越来越重的位置。一种将两者进行融合的趋势已经变得势不可挡。
数据文件最传统的形式为堆组织表（Heap-Organized Table），数据的放置没有一个特别的顺序，一般是按照写入的先后顺序排布。这种数据文件需要一定额外的索引帮助来查找数据。
另外有两种数据表形式自带了一定的索引数据能力，即哈希组织表（Hash-Organized Table）和索引组织表（Index-Organized Table）。前者是将数据通过哈希函数分散到一组数据桶内，桶内的数据一般是按照一定规则进行排序，以提高查询效率；而后者一般采用索引文件的形式来存储数据，以 B+树为例，数据被存储在叶子节点上，这样做的目的是减少检索数据时读取磁盘的次数，同时对范围扫描支持友好。
索引文件的分类模式一般为主键索引与二级索引两类。前者是建立在主键上的，它可能是一个字段或多个字段组成。而其他类型的索引都被称为二级索引。主键索引与数据是一对一关系，而二级索引很有可能是一对多的关系，即多个索引条目指向一条数据。
这里按照索引与数据之间结合的程度，我们又可以把索引分为聚簇索引和非聚簇索引。前者如哈希组织表和索引组织表那样，数据的分布与索引分布是有关联的，它们被“聚”在一起，这样的查询效率很好。而后者最常见的例子就是针对这两种数据文件的二级索引，因为二级索引要索引的列不是主键，故索引与数据是分割的，查询时需要进行多次磁盘读取。但是对于写入，聚簇索引可能需要进行唯一判断，性能会比简单构建的非聚簇索引低效。
最后一点需要说明的是，二级索引需要保存指向最终数据的“引用”。从实现层面上，这个引用可以是数据的实际位置，也可以是数据的主键。前者的好处是查询效率高，而写入需要更新所有索引，故性能相对较低。而后者就恰好相反，查询需要通过主键索引进行映射，效率稍低，但写入性能很稳定，如 MySQL 就是选用后者作为其索引模式。
5、面向分布式的存储引擎
5.1 内存型数据库会倾向于选择分布式模式来进行构建
原因也是显而易见的，由于单机内存容量相比磁盘来说是很小的，故需要构建分布式数据库来满足业务所需要的容量。
5.2 列式存储也与分布式数据库存在天然的联系。
可以去研究一下，很多列式相关的开源项目都与 Hadoop 等平台有关系的。原因是针对 OLAP 的分析数据库，一个非常大的应用场景就是要分析所有数据。
而列式存储可以被认为是这种模式的一种优化，实现该模式的必要条件是要有分布式系统，因为一台机器的处理能力是有瓶颈的。如果希望处理超大规模数据，那么将数据分散到多个节点就成为必要的方式。所以说，列模式是由分析性分布式的优化需求所流行起来的。
至于宽列存储更是分布式数据库场景下才会采用的模式。数据文件的组织形式，分布式数据库几乎不会使用堆组织表。因为该形式过于随意，无法有效地分散数据。不知道学习过数据分片那一讲的时候你有没有注意到，另外两种组织表的名字与两种分片算法是有着天然联系的。哈希组织表数据经过哈希函数散列到不同的桶，这些桶可以被分散到不同节点。而索引组织表一般叶子节点是按一定顺序排列的，这与范围分片又有着某种契合的关系。所以分布式数据库一般都会采用这两种模式作为其存储引擎，甚至一些分布式数据库直接将数据文件当作索引使用。
6、LSM树存储引擎
典型的面向分布式数据库所使用的存储引擎。从其特点可以看到，它高速写入的特性对分布式数据库而言是有非常大吸引力的，同时其KV 结构更是分片所喜欢的一种数据格式，非常适合基于此构建分布式数据库。所以诸如 Apache Cassandra、ClickHouse 和 TiDB 等分布式数据库都选用 LSM 树或类似结构的存储引擎来构建分布式数据库。
LSM-Tree，全称Log Structured Merge Tree，是一种写入操作不做原地更新，而是以追加的方式写入内存，每次写到一定程度，即冻结为一层，然后写入持久化存储的数据结构。可以简单描述一下一条数据在LSM-Tree中的写入过程：写入Log -> 写入memtable -> flush入持久化存储 -> 经compaction操作进入持久化存储的更新层 -> 同一key的新数据到来时丢弃。下面是一张LSM-Tree的结构图：
LSM 树存储引擎的结构暗含在它的名字内。LS 代表日志结构，说明它是以日志形式来存储数据的，那么日志有什么特点呢？如果你对财务记账有些了解的话，会知道会计在删除一笔记录时，是不会直接拿着橡皮擦去擦掉这个记录的，而是会写一笔与原金额相等的冲抵操作。这就是典型的日志型存储的模式。
日志型存储的特点是对写入非常友好，不像 B 树等结构需要进行随机写，日志存储可以进行顺序性写。因为我们常用的 HDD 磁盘是有旋转机构的，写入延迟主要发生在磁盘旋转与读写臂的移动上。如果数据可以顺序写入，可以大大加快这种磁盘机构的写入速度。
而 M 则暗含这个结构会存在合并操作，形成最终的可读取结构。这样读取操作就不用去查找对于该记录的所有更改了，从而加快了读取速度。同时将多个记录合并为一个最终结果，也节省了存储空间。虽然合并操作有诸多优点，但是它也不是没有代价的，那就是会消耗一定的计算量和存储空间。
6.1 LSM树的内存结构
LSM 树包含内存驻留单元和磁盘驻留单元。首先数据会写入内存的一个缓冲中，而后再写到磁盘上的不可变文件中。
内存驻留单元一般被称为 MemTable（内存表），是一个可变结构。它被作为一个数据暂存的缓冲使用，同时对外提供读取服务。当其中的数据量到达一个阈值后，数据会被批量写入磁盘中的不可变文件内。
磁盘驻留单元，也就是数据文件，是在内存缓冲刷盘时生成的。且这些数据文件是不可变的，只能提供读取服务。而相对的，内存表同时提供读写两个服务。
关于 LSM 树的结构，一般有双树结构和多树结构两种。前者一般是一个理论说明，目前没有一个实际的存储引擎是使用这种结构的。所以我简单说一下双树概念，它有助于你去理解多树结构。
双树中的两棵树分别指：内存驻留单元和磁盘驻留单元中分别有一棵树，你可以想象它们都是 B 树结构的。刷盘的时候，内存数据与磁盘上部分数据进行合并，而后写到磁盘这棵大树中的某个节点下面。成功后，合并前的内存数据与磁盘数据会被移除。
可以看到双树操作是比较简单明了的，而且可以作为一种 B 树类的索引结构而存在。但实际上几乎没有存储引擎去使用它，主要原因是它的合并操作是同步的，也就是刷盘的时候要同步进行合并。而刷盘本身是个相对频繁的操作，这样会造成写放大，也就是会影响写入效率且会占用非常大的磁盘空间。
多树结构是在双树的基础上提出的，内存数据刷盘时不进行合并操作，而是完全把内存数据写入到单独的文件中。那这个时候另外的问题就出现了：随着刷盘的持续进行，磁盘上的文件会快速增加。这时，读取操作就需要在很多文件中去寻找记录，这样读取数据的效率会直线下降。
为了解决这个问题，此种结构会引入合并操作（Compaction）。该操作是异步执行的，它从这众多文件中选择一部分出来，读取里面的内容而后进行合并，最后写入一个新文件中，而后老文件就被删除掉了。如下图所示，这就是典型的多树结构合并操作。而这种结构也是本节介绍的主要结构。
6.2 刷盘的流程
数据首先写入当前内存表，当数据量到达阈值后，当前数据表把自身状态转换为刷盘中，并停止接受写入请求。此时会新建另一个内存表来接受写请求。刷盘完成后，由于数据在磁盘上，除了废弃内存表的数据外，还对提交日志进行截取操作。而后将新数据表设置为可以读取状态。
在合并操作开始时，将被合并的表设置为合并中状态，此时它们还可以接受读取操作。完成合并后，原表作废，新表开始启用提供读取服务。
6.3 查询、更新与删除、合并操作
查询操作本身并没有 LSM 树的特色操作。由于目标数据可能在内存表或多个数据表中，故需要对多个数据源的结果数据进行归并操作。其中使用了排序归并操作，原因也非常简单，因为不论是内存表还是数据表，其中的数据都已经完成了排序。排序归并算法广泛应用在多种数据库中，如 Oracle、MySQL，等等。另外数据库中间 Apache ShardingShpere 在处理多数据源 order by 时，也使用了这个方法。
而查询另外一个问题是处理同一份数据不同版本的情况，虽然合并操作可以解决部分问题，但合并前的数据还需要通过查询机制来解决。我刚介绍过 LSM 树中对数据的修改和删除本质上都是增加一条记录，因此数据表和内存表中，一份数据会有多条记录，这个时候查询就需要进行冲突处理。一般一份数据的概念是它们具有相同的 key，而往往不同的版本会有时间戳，根据这个时间戳可以建立写入顺序，这类似于向量时钟的概念。故查询中我们很容易判断哪条数据是最新数据。
更新和删除操作本质上是插入数据，然后根据上面提到的冲突处理机制和合并操作来获取最终数据。更新操作是比较简明的，插入新数据就好了。但是删除操作时插入的是什么呢？
一般插入的是特殊的值，被称作墓碑（Tombstone）。它是一个特殊的值，用来表示记录被删除。如果要产出一个范围内数据呢？Apache Cassandra 的处理方法是引入范围墓碑（Range Tombstone）。
比如有从 k0 到 k9 的 9 条数据，在 k3 处设置开始删除点（包含 k3），在 k7 处设置结束删除点（不包含 k7），那么 k3 到 k6 这四条数据就被删除了。此时查询就会查不到 k4 到 k6，即使它们上面没有设置墓碑。
合并操作是用来维护 LSM 树的结构的，以保证其可以正常运行。需要强调的一点是，我们这里说的合并操作针对的是 LSM 树的结构里面提到的多树结构。在多树结构中，磁盘中表的数量随着刷盘动作的持续进行，而变得越来越多。合并操作正是让它们减少的一种手段。
合并操作会根据一定规则，从磁盘的数据文件中选择若干文件进行合并，而后将新文件写入磁盘，成功后会删除老数据。在整个操作的过程中，对内存的消耗是完全可控的。这是由于每个数据文件都是经过排序的，如上一讲提到的查询规则一样，我们依然可以通过排序归并来合并多个文件中的数据。这种合并每次只会加载部分数据，也就是每个文件头部的数据，进入内存进行合并操作。从而很好地控制了合并操作对内存资源的消耗。
在整个合并的过程中，老的数据表依然可以对外提供读取服务，这说明老数据依然在磁盘中。这就要求磁盘要留有一定的额外空间来容纳生成中的新数据表。同时合并操作可以并行执行，但是一般情况下它们操作的数据不会重合，以免引发竞争问题。合并操作既可以将多个数据文件合并成一个，也可以将一个数据文件拆分成多个。
常见的合并策略有 Size-Tiered Compaction 和 Leveled Compaction。
6.3.1 Size-Tiered Compaction合并算法
其中，数据表按照大小进行合并，较小的数据表逐步合并为较大的数据表。第一层保存的是系统内最小的数据表，它们是刚刚从内存表中刷新出来的。合并过程就是将低层较小的数据表合并为高层较大的数据表的过程，Apache Cassandra 使用过这种合并策略。该策略的优点是比较简单，容易实现。但是它的空间放大性很差，合并时层级越高该问题越严重。比如有两个 5GB 的文件需要合并，那么磁盘至少要保留 10GB 的空间来完成这次操作，可想而知此种容量压力是巨大的，必然会造成系统不稳定。
6.3.2 Leveled Compaction
如名称所示，该策略是将数据表进行分层，按照编号排成 L0 到 Ln 这样的多层结构。L0 层是从内存表刷盘产生的数据表，该层数据表中间的 key 是可以相交的；L1 层及以上的数据，将 Size-Tiered Compaction 中原本的大数据表拆开，成为多个 key 互不相交的小数据表，每层都有一个最大数据量阈值，当到达该值时，就出发合并操作。每层的阈值是按照指数排布的，例如 RocksDB 文档中介绍了一种排布：L1 是 300MB、L2 是 3GB、L3 是 30GB、L4 为 300GB。
上图概要性地展示了从 L1 层开始，每个小数据表的容量都是相同的，且数据量阈值是按 10 倍增长。即 L1 最多可以有 10 个数据表，L2 最多可以有 100 个，以此类推。随着数据表不断写入，L1 的数据量会超过阈值。这时就会选择 L1 中的至少一个数据表，将其数据合并到 L2 层与其 key 有交集的那些文件中，并从 L1 中删除这些数据。
仍然以上图为例，一个 L1 层数据表的 key 区间大致能够对应到 10 个 L2 层的数据表，所以一次合并会影响 11 个文件。该次合并完成后，L2 的数据量又有可能超过阈值，进而触发 L2 到 L3 的合并，如此往复。可见，Leveled Compaction 与 Size-Tiered Compaction 相比，每次合并时不必再选取一层内所有的数据，并且每层中数据表的 key 区间都是不相交的，重复 key 减少了，所以很大程度上缓解了空间放大的问题。
当然在实际应用中会组合两种策略，比如经典的 RocksDB 会在 L0 合并到 L1 时，使用 Size-Tiered Compaction；而从 L1 开始，则是采用经典的 Leveled Compaction。这其中原因是 L0 的数据表之间肯定会存在相同的 key。
6.3.3 RUM 假说
开始介绍这个假说之前，你要先明确几个“放大”概念。
读放大：它来源于在读取时需要在多个文件中获取数据并解决数据冲突问题，如查询操作中所示的，读取的目标越多，对读取操作的影响越大，而合并操作可以有效缓解读放大问题。
写放大：对于 LSM 树来说，写放大来源于持续的合并操作，特别是 Leveled Compaction，可以造成多层连续进行合并操作，这样会让写放大问题呈几何倍增长。
空间放大：这是我在说合并的时候提到过的概念，是指相同 key 的数据被放置了多份，这是在合并操作中所产生的。尤其是 Size-Tiered Compaction 会有严重的空间放大问题。
那么可以同时解决以上三种问题吗？根据 RUM 的假说，答案是不能。
该假说总结了数据库系统优化的三个关键参数：读取开销（Read）、更新开销（Update）和内存开销（Memory），也就是 RUM。对应到上面三种放大，可以理解为 R 对应读放大、U 对应写放大，而 M 对应空间放大（Memory 可以理解为广义的存储，而不仅仅指代内存）。
该假说表明，为了优化上述两项的开销必然带来第三项开销的上涨，可谓鱼与熊掌不可兼得。而 LSM 树是用牺牲读取性能来尽可能换取写入性能和空间利用率。
而有的人会发现，合并操作会带来空间放大的问题，理论上应该会浪费空间。但是 LSM 树由于其不可变性，可以引入块压缩，来优化空间占用使用，且内存不需要做预留（B 树需要额外预留内存来进行树更新操作），从而使其可以很好地优化空间。
应该知道，RUM 所描述的内容过于简单，一些重要指标如延迟、维护性等没有涵盖其中，但是它可以作为我们工具箱里面的一个短小精干的扳手，来快速分析和掌握一个存储引擎的特点。
B+Tree VS LSM-Tree
来比较一下这两类数据结构，明确它们的特性和适用场景。
B+Tree将数据拆分为固定大小的Block或Page，Page是读写的最小单位。B+Tree可以做到原地更新和删除，因此对数据库事务的支持更加友好，因为一个key只会出现一个Page页里面。而LSM-Tree的设计思路是将数据拆分为几百M大小的Segment，并顺序写入。LSM-Tree只能追加写，并且在L0层key的range会重叠，所以对事务支持较弱，只能在Segment Compaction的时候真正地更新和删除。
B+Tree的优点是支持高效的读（稳定的O(logN)的复杂度），但对大规模的写请求的效率就比较低（O(logN)复杂度），这是因为在大规模写的情况下，为了维护B+Tree的结构，B+Tree的节点就会不断分裂，操作磁盘的随机读写概率会变大，从而导致写性能降低。LSM-Tree则相反，支持高吞吐量的写（O(1)），但普通LSM-Tree读取的复杂度是O(n)，在使用索引或者缓存优化后可以达到O(logN)。
可以粗略的认为未优化的LSM-Tree的写比B+Tree快一个数量级，未优化的LSM-Tree的读比B+Tree慢一个数量级。
第一代分布式数据库：分库分表及分布式中间件
最初面对存储扩展问题，一个比较直接的思路就是分库分表——一个库装不下，我就用多个库装。
假设一开始有一个单点的MySQL数据库，随着业务增长，达到了单库的存储性能瓶颈，准备使用三到五个MySQL来重新安排存储。在最理想的情况下，我们可以在拥有原来三到五倍存储空间的情况下，也能有三到五倍的并发来提升存储性能。
但这有两个很明显的问题：第一个是我要对业务进行大量的改造，找到一个合适的维度打散业务进入多个库（而且这种完美的方案还不一定存在），而且跨库的业务也要重新写业务逻辑。第二个是一旦库又满了，我想再做一次扩容的工作，我就又要把这部分的工作再做一次——包括重写业务。
上面两个问题的代价显然是不可承受的，这时候就有分布式数据库厂家来说了：我们来做整合并管理多个库的工作，你们应用只要把多个数据库当作原来的一个库使用即可。
这就诞生了分布式中间件的概念，或者称作分布式关系型数据库。分布式中间件，是从关系型数据库出发，加入分布式技术，实现分布式的高可用性和高扩展性等特性。本文把此类数据库称为分布式中间件，不代表它们就没有对底层数据库（通常是MySQL）做任何改动。实际上，目前市面上的分布式关系型数据库几乎都对底层数据库有自己的修改，甚至有阿里的OceanBase那样自己实现一个关系型底层的情况。
但分布式中间件有根本解决上面的两个问题吗？显然并没有。分布式中间件没有把数据自动分片的能力，应用也不能真真正正的把分布式数据库当作一个单库来使用——除非你完全不在乎跨片的性能损耗。
但分布式中间件也确确实实有很大的作用，它极大的减少了业务的改造量，也保证了了分布式事务的ACID特性。在各类分布式中间件迭代发展的过程中，这一技术路线也在逐渐进步：厂家开始探索对底层数据库的改造，以使其更适应分布式特性；中间件层也吸收了后面NewSQL的一些技术思路，在全局事务管理、数据增量写入等方面做了很多优化。
普通分布式中间件
大部分分布式中间件的架构一般有以下三个部分：
客户端：通常为MySQL5.7或8.0版本的客户端，支持JDBC访问。
存储层：由多个MySQL实例组成，引擎为InnoDB。
计算层（中间件层）：组织并管理存储层的MySQL实例，接受并解析客户端传来的SQL请求。计算层通常用片的概念把存储层的MySQL分割，然后以片为单位进行多副本来实现高可用。计算层显式或隐式的有一个事务管理组件，负责给事务赋一个全局唯一的ID，这个组件是实现分布式事务一致性的一种重要的解决方案。计算层对客户端屏蔽多副本和事务ID，会对客户端发来的普通SQL进行拆分和改造，并生成分布式的执行计划，然后下发到存储层的MySQL实例执行。
第二代分布式数据库：NoSQL
在早期分库分表方案发展过程中，好多公司都面临了因扩容而无限次改造业务的痛苦。他们再次观察业务，发现业务并不复杂——至少没复杂到需要使用高级SQL的地步。这样NoSQL干脆就抛弃了高级SQL（分布式ACID特性），从而换来对业务透明的特性和强水平扩展的能力。这样做的好处显而易见——只要你能忍受不用高级SQL这一点，那么你只要进行一次到NoSQL的改造，后面就可以近乎无限的扩容，无需任何业务的适配。
各种NoSQL，如HBase,Cassandra,Leveldb,RocksDB底层的数据结构，都是LSM-Tree。因为NoSQL不支持分布式ACID特性，和其他分布式数据库差别较大，所以不列入后面对事务的讨论。
第三代分布式数据库：NewSQL
上面的分库分表、分布式中间件和NoSQL都不可避免的由一个业务侵入性的问题，有些前沿厂家就产生了把二者结合起来，设计一个兼具分布式事务一致性和强可扩展性的数据库的想法——这就是NewSQL的诞生。在NewSQL领域，有两个流派，分别是Amazon的Aurora和Google的Spanner。
Aurora流派也被称作Shared Everything，目前这个流派，多是被部署到虚拟计算环境中的云数据库，本文涉及的云数据库有阿里的PolarDB，Amazon的Aurora以及华为云数据库Taurus。该流派最重要的一个概念就是Log is Database。这个概念是把log写到存储层，由存储层负责重放log、回写page并尽量减少写放大。
基于LSM-Tree分层存储能够做到写的高吞吐，带来的副作用是整个系统必须频繁的进行compaction，写入量越大，Compaction操作越频繁。而Compaction操作非常消耗CPU和IO，在高吞吐的情况下，大量的Compaction操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响。
Spanner流派也称作Shared Nothing。与分布式中间件不同的是，它是从分布式系统出发，再来做存储，做查询，利用天然的扩展能力和列存的性能优势，实现基于KV存储的支持关系型查询的数据库。如TiDB就是一个NewSQL的商业化的实现。
对Spanner的所有了解都来自Google于2012年发表的论文《Spanner: Google's Globally-Distributed Database》。该论文中有两个十分重的论点：一个是TrueTime API的实现，给Spanner提供了全局的时钟接口，在此基础上Spanner才能实现强的全局一致性保证；另一个是论文中对Spanner的分布式事务实现细节进行了详细的描述。