从零开始深入理解存储引擎

作者：zhengweiwu

很多应用都属于数据密集型应用，而非计算密集型；对于这类应用，CPU往往不是第一限制性因素，关键在于数据量、数据复杂度和数据的快速多变性；因此数据库的选型在应用系统设计中就显得比较重要。数据库（数据引擎）最核心的任务就是"读到写入的值"，我们尝试从"最简单的脚本文件数据读写"一步一步扩展讨论到"分布式键值数据库"，在这个过程中我们会遇到很多"挑战"，并尝试逐步解决。

1.单机存储引擎

从两行代码的shell脚本

读写文件开始，我们通过逐步解决如下问题得到了一个单机可用的存储引擎(LSMTree

)：

1.读取慢

2.磁盘耗尽

3.文件压缩合并

4.重新组织数据文件格式提高压缩合并效率

5.内存排序数据以实现预期的数据文件格式

6.有序数据文件的压缩合并

7.引入预写日志解决重启内存数据丢失

不使用已有的任何数据引擎，我们重新来思考一个问题：如何从零构建一个可存储/读取数据的"数据库"?

我们先看如下这个最简单的"数据引擎"。

使用上述shell

脚本写入两条数据（key

分别为123456

和42

）之后，本地文件中的两行记录如下所示（用,

区分key

和value

）

123456,{"name":"London","attracions":["BigBen","LondonEye"]}

42,{"name":"sanFrancisco","attractions":["GoldenFateBridge"]}

上面这个"数据引擎"写操作性能足够好，因为只需要数据文件追加写入一条记录即可；

但它的读性能较差，因为需要全文件检索

(grep

|sed

)，同一个key

若有过多次写操作，在数据文件中会存在多行记录，查询时只取最后一条(tail-n1

)即可。

因数据文件格式固定，当前还不支持删除操作，以及key

中不能存在逗号,value

中不能存在

符等问题

1.2引入索引提高读性能

当前的第一个任务就是提高读性能

。我们可以引入单独维护的索引

(内存中维护的HashMap

)提升查询性能；因此写入时除了写数据文件，还需要写索引，这会降低写入的速度；这也是存储系统中很重要的权衡设计；到底关注读性能还是写性能，在技术选型的时候需要开发人员决定。

哈希索引

添加索引之后，如下所示:

添加了内存中的HashMap

来快速定位Key

所在的位置，hashvalue

是文件字节偏移量(byteoffset

)；读取时直接从文件指定偏移位置读取到

符即是Value

值。

此时可以提供高性能的读写，但需要所有的Key

可以全部放在内存中供索引即可；写操作仍是一次追加写，读操作只需要一次磁盘寻址即可。

引入了内存索引之后，很自然的一个问题就是机器重启，内存索引丢失怎么办？可以重新遍历文件构建索引

，后面再讨论其他更合理的方案。

另外，相同的key

若有多次写操作，则本地数据文件中也会存在多条记录；因此就有磁盘耗尽的风险；极端情况下，对同一个key

持续不断的写入，直到磁盘写满，实际上只有最后一条记录是有效的。磁盘空间放大特别显著；

同时，hashmap

需要全部存在于内存中，若key

的数量超过内存限制，也会有问题

1.3如何避免磁盘耗尽？

文件分段，分段压缩

假定数据文件写满1GB

之后就可以关闭，创建新的数据文件供后续的写入。如下segment1

写满之后就创建了segment2

；每个segment

就是一个独立的文件；

分段合并之后的新段中仅保留每个键最新的值；通过段合并，减少段日志文件数量和总体的大小；

如上图，purr

在segment1

和segment2

中存在多次，经过压缩合并之后，仅保留最新的值(2114

)即可；

同时要注意，上述segment

中的key

是无序的，是按照写入顺序来存储的

；

这个"数据引擎"也还是不完善的，比如对：

删除记录

如何处理？

崩溃恢复

如何进行？区间查询是否支持？等等

用这几个问题引出我们接下来的讨论

为实现区间查询和快速文件合并，对上面的日志段文件添加一个要求：Key有序

。则该文件就可称之为有序字符串表

(SSTable

-sortedstringtable

)；SSTable

相比上述无序的哈希索引的日志段，有如下优点：

1.4如何构建和维护SSTables

持续的数据写入排序不可能在文件中完成，因此我们使用内存来解决这个问题；基于内存的有序数据结构还是很多的，出于简单高效的原则，我们选择跳表

作为有序数据的内存实现：

数据写入时直接写入到内存中的跳表即可，当跳表数据量达到阈值时(如1GB

)就可以持久化写入(dump

)到磁盘文件中，因为跳表是有序的，因此生成的文件也就是有序的，符合SSTable

的要求；

此时还有一个问题：若跳表dump

到一半的时候（如上图中顺序遍历并持久化到71），此时写入20，待dump

结束之后，跳表重建，20这个值也就丢了

因此正在dump

的跳表是不能够再接收写入的，但是系统还是要接收来自客户端的写请求，因此还需要一个能够接受写请求的跳表；如下图所示：

在活跃跳表需要持久化的时候会变为不可写跳表，同时创建一个新的活跃跳表接收写请求。我们将活跃跳表称之为memtable

，不可写跳表称之为immutable

。只有跳表写入到磁盘SSTable

的过程中内存中才存在两个跳表，除此之外，内存中只存在一个活跃的跳表接收写请求。

是时候讨论一下SSTable

的文件结构了，因为只有清楚了SSTable

是如何存储数据的才能理解读请求是如何处理的

1.5详解SSTable的文件格式

首先，需要思考一个问题：一对kv

如何在文件中存储？

比如name

:zhengwei

，如果在文件中直接拼接编码成namezhengwei

,我们不知道key

是name

，还是namezheng

；若使用特殊字符区分，则kv

对中也就不允许存在特殊字符；最合理的办法还是存储key

的长度；读取指定长度的字节序列作为目标值。

在写入到文件的时候，在keyvalue

前面分别追加key

的长度就能通过偏移量的方式直接获取到key

的内容；如上图中的4和8，这样的一条记录，我们先称它为Entry

。

这里有一个小问题就是：key_length和value_length分别用几个字节来存储呢？1字节太少，只能存储256长度的字节序列，若有超长字符串就存不下；若字节太多，如4字节，又存在了很大的空间浪费；

可以参照UTF-8变长字节编码的方式来实现，根据前几个比特位是否为0来表示使用几个字节表示字节长

我们已经有了一条记录，那么这条记录如何组织进SSTable

中呢？也为了利用磁盘的页缓存特性，我们将多条记录组织成块(Block

)

在字典序上，Entry1

Level1

...直到每一层的SSTable

都读完；若在其中的一步读到了数据，则不再往下读取，适时终止。

如何删除数据

：需要删除的数据,Value

中存入特殊值，若读取到特定值则返回不存在；在Compaction

过程中也会跳过这些有特殊值的键（也称标记删除或“墓碑”）

此时架构如下:

此时还有一个问题就是：数据初始是写入到：memtable中的，若还没来得及dump到文件中，发生了机器故障，重启之后内存丢失，memtable中写入的值也会丢失。

要想保证不丢失数据必须要落盘，为了保证写入性能不受影响，以及磁盘顺序读写性能是最高的，我们可以引入预写日志(WAL-writeaheadlog）。

数据首先顺序追加到预写日志中，待数据落盘落盘之后再写入到memtable

中，待memtable

中的数据持久化到磁盘时，该memtable

对应的预写日志也就可以删除了。

1.7LSMTree

我们上面已经详细讨论了sstable

的文件格式，不再详细讨论WAL

的文件格式，有很多开源的实现；我们可以简单理解为每个memtable

和immutable

都对应一个WAL

文件，待immutable

写入到SSTable

之后，对应的WAL

也就可以删除了，因为该部分数据已经持久化到磁盘了。

若发生机器重启，则需要顺序重放WAL

中的请求以将内存中的跳表恢复到宕机之前的状态

讨论到此，我们已经有了一个单机存储数据的数据库，即使发生重启，数据也不会丢失。实际上这就是一个LSMTree

存储引擎。也是是LevelDB

/RocksDB

所采用的方案；在Cassandra

/HBase

中也有该方案的身影；基于合并和压缩排序文件原理的存储引擎通常称为LSM

存储引擎；

1.8和B 树的对比

除了上面提到的基于LSM

的存储引擎之外，还有基于B

树的存储引擎，它也几乎是关系数据库的标准实现，3-4层的B

树就可存储大量数据，不需要遍历太深（分支因子为500的4KB

页的四级树可存储256TB

如下图所示，对B

树讨论的资料很多，可以自行参考一下；不再展开

我们来对比一下B Tree和LSM-Tree

因此，LSM

经常应用在数据分析或其他离线场景，对读取的延迟容忍略高一些，但是需要接收比较多的写请求；B

树更多应用到在线或需要加锁的场景中。

1.9OLAP与OLTP

我们详细的讨论了LSM树

，并简单对比了B 树

，它们是OLAP

(onlineanalyticprocessing

)和OLTP

中日志结构流派

和原地更新流派

的代表；

还有融合了OLAP&OLTP的HTAP，代表数据库如下图所示:

我们可以简单认为OLTP

服务与在线业务，直接和C

端用户交互；在线数据经过ETL

之后存储到OLAP

中一份用于商业分析或离线特征计算后再反哺到在线业务（比如TDW

/用户画像特征等）

如下是ETL

(Extract

-Transform

-Load

,提取/转换/加载

)的过程：

将不同业务系统的数据库经过提取之后转换为分析需要的数据结构，加载到OLAP

等数据仓库中，供分析师使用；

一般情况下供分析师使用的表通常很宽

(有几百上千个字段/列，经过聚合多个数据源和业务数据得到)，但是每次分析时可能只会使用其中很少的列（比如用户画像表，会有很多字段，但是一次sql

可能只是涉及到很少的字段-selectmax(age)fromtablewheregender='male'

）；在OLTP

数据库中，存储以面向行的方式来布局；为提高查询性能，面向列存储可优化分析场景下的查询性能；列存如下图所示：

左下角是表结构，有a

/b

/c

三列，当前有a1

到a5

共5行数据；若查询只涉及b

列，行存储

情况下(Rowlayout

)需要间隔性的从磁盘中读取有效数据，每次从磁盘load

4KB的页到内存中，页中包含了a

三列的数据；想要获取的b

列数据只占用1/3页空间；该场景下所有存储页都需要读一遍，执行一次完整的表遍历才能拿到所有的b

列；

列存储

情况下，会将一列单独存储，因此列存数据库下会有三个数据文件，分别存储a

列，b

列和c

列。需要分析b

列，只需要把对应的文件加载到内存即可。查询没有涉及的a

列对应的文件不需要读取。

为进一步描述列存储，再看下面这个示例：

表共有8列，在列存储情况下，每一列作为一个文件存储

，如product_sk

列，就会作为一个独立文件，存储内容为：69,69,69,74,31,31,31；

列存储，因为相同列数据类型相同，且distinct

后数量较少，更方便压缩

;如上述product_sk

文件，连续的69和31是可以压缩存储的；不再讨论。

上面简单讨论了两类数据库，但实际上数据库的种类繁多，即使一个LSM

也会存在很多的变形。DBEnginesRanking

中对数据库排名如下(共有418种数据库参与排名):

如上排名中包含Relation

、Document

、Key-value

、SearchEngine

、Graph

等多种数据库类型。

可用的数据库系统如此之多，我们可以拿来就用；但因为选择太多，以及需求和设计目标的差异，个中精妙又不尽相同，我们总要清楚哪些适合自己，又该如何使用；

1.10数据库的可靠性、可扩展性和可维护性

系统总是不可靠的，我们应该构建什么样的系统？我们进行如下的讨论，也顺便引出下一部分的讨论：单机故障了怎么办？单机数据存不下了怎么办？

1.10.1可靠性

可靠性的定义为:即使发生了某些错误，系统仍可以正常工作

容错一定是有范围的，业务系统容错主要考虑到单机房故障维度就可以了，更大范围容错成本太高了；因此，单容器故障、错误输入、非法访问、流量洪峰等都应该囊括在可靠性考虑范围内；

硬件故障

以硬盘为例，平均无故障时间为10-50年，因此一个包含1万个磁盘的存储集群中，每天都会有磁盘故障；硬件故障是无法避免的；

软件故障

bug

总是持续存在的；需要进行全面的测试；同时在部署运行时，也需要进程隔离，允许进程崩溃并自动重启；

人为失误

人比机器更不可靠；比如出现配置错误导致系统异常；如下的可能方案来减少人为失误：

1.10.2可扩展性

定义：主要指负载增加时，有效保持系统性能的扩展性；

通常使用如请求QPS

、聊天室同时活动用户数量、缓存命中率等具体量化的数字描述负载

举个例子，以Twitter

查看推文流和发布推文而言:发布推文

：平均4.6K-12KQPS

推文流浏览

：300KQPS

因此消息存储有两种方式：1)拉模式2）推模式

拉模式

，所有消息放在全局tweet

表中；用户浏览推文流时，首先查找所有关注对象，再关联到推文，以时间序展示；发布推文只是生成一条记录；压力在查看时的关联查询；

推模式

，对每个用户维护一个序列“邮箱”，发推文时，先查询其关注者，再将推文存储到每个关注者的时间线缓存中；查看时只需要遍历自己的“邮箱”即可；压力在发推文时候的“信件投递”

twitter

开始时使用方案一，但读压力与日俱增；转而采用第二种方案；第二种方案最大的问题是当明星博主拥有超过3000万粉丝时，扇出巨大，需要写巨量的“邮箱”；最终方案融合，大多数博主因为粉丝较少，持续采用第二种方案；少量粉丝巨大的明星博主采用方案一，推文被单独存储，推文展示时合并渲染；因此，每个用户粉丝的分布情况就是可扩展的关键负载参数；

对于如何描述性能，一般采用响应时间、吞吐量及延迟等描述；如下图对请求的耗时分布的展示：

亚马逊以P99.9定义内部服务响应时间，即使只是1000个请求中的一个请求失败了，但考虑到请求最慢往往购买了更多的商品，反而是最有价值客户

；除此之外，SLO

/SLA

也用于描述服务质量；

1.10.3可维护性

对系统而言，开发阶段成本不是最大的，后续维护、缺陷修复、适配新功能、偿还技术债务等等成本更高；

可运维性：

运维更轻松

简单性：

简化复杂度；做好抽象，隐藏细节，对外提供干净/易懂的接口；如高级语言屏蔽此层寄存器/系统调用的复杂度；

可演变性：

易于改变

2.数据复制

经过第一部分的讨论，我们在单容器上得到了一个可高效读写的存储引擎，但机器总会故障，如何保证在机器故障的情况下，服务对外提供的读写能力不受到影响？

自然就是数据在多个容器上存储多份，待机器故障后，使用其他机器的数据对外提供服务。那如何保证不同机器上有多份数据，且它们是一致的就成为接下来要解决的问题。

如果数据一成不变，数据复制就很容易；挑战就在于处理那些持续更改的数据

，即如何确保多副本之间的数据是一致的。

同步的方式主要有三种:1.主从复制;2.多主复制;3.无主复制

各有优缺点，我们首先看主从复制，这也是最常见的

2.1主从复制

写请求发送到主节点（北京)，主节点按序将数据更改作为复制日志或更改流发送给所有从节点；从节点将变更数据流应用到自身的存储引擎中，也就拥有了和主节点一致的数据；读请求也就可以请求从节点获取数据；

若客户端等待主节点将数据同步到所有从节点再响应客户端，这个耗时会比较久；而且强同步策略也会在任一从节点故障不能响应主节点的时候堵塞所有客户端的写操作

2.1.1同步复制与异步复制

如上图，从节点1

的复制是同步的，主节点等待从节点1完成写入变更之后才会响应客户端；从节点2的复制是异步的，主节点不等待

从节点2的返回就会给用户响应；

同步复制的优点是，一旦向用户确认，则所有的从节点与主节点都是强一致的。即使主节点发生故障，仍可以在任一从节点中访问最新数据；缺点则是：任一从节点堵塞（崩溃/网络超时）则用户的写请求都将堵塞；

主从复制模式还经常配置为全异步模式。此时如果主节点故障，则所有尚未复制同步到从节点的写请求都将丢失。优点则是吞吐性能较高，因为不管从节点落后多少日志数据，主节点总是可以响应写请求；

我们折中一下，不管集群规模多大，我们配置一个同步的从节点，其他从节点为异步复制

。若主节点故障，则将同步的从节点提升为主节点；若同步的从节点故障，则从异步节点中挑选一个作为同步节点；该模式也被称为半同步

当需要新增加一个从节点提升容错能力，或者替换失败的节点，就需要增加从节点

。但如何确保新添加的从节点与主节点数据一致呢？也就是从节点如何从“一无所知”追赶到拥有主节点的所有数据

如上图所示，当从节点向主节点请求数据同步的时候，主节点做两件事情，一个是产生一个数据快照

（拥有所有的存量数据）；另一个是记录此刻开始发生的数据更改日志

(同步开始后的增量数据)；从节点首先将数据快照应用到自身节点，然后将发起同步请求开始的主节点的数据更改日志（即快照时候的数据变更,上图中的红色部分）应用到自身；日志同步流中的节点通常称之为LSN

(日志序列号/LogSequenceNumber

举个例子：在时间点t5从节点请求数据同步，此时主节点生成一个快照，包含t0-t5的数据；同时，此时该从节点的写命令日志序列LSN=100；从节点将快照数据加载之后，会从LSN:100处开始重放写命令日志序列；待重放完也就拥有了t5到此刻的增量数据，后面就是保持实时数据同步了。

不管主节点还是从节点都可能宕机，故障重启或者网络中断，在此情况下如何故障恢复也是一个挑战

从节点故障：追赶式恢复

若从节点重启或者网络中断后恢复，因为有本地副本的复制日志，从节点知道故障前最后一次写入的LSN

，则使用该LSN

从主节点继续同步追赶

主节点失效：切换

若主节点故障，则需要挑选某个从节点提升为主节点；客户端也需要更新，这样之后的写请求才会写到新的主节点；其他从节点也需要接受来自新主节点的数据变更。

自动切换的步骤通常如下:

确认主节点失效。一般都基于超时心跳来检测主节点是否还存活，可能是控制节点检测心跳，也可能是集群内部根据流言协议Gossip

决定主节点是否存活；

选举新的主节点。可以通过控制节点决定谁当选为新的主节点，也可以通过集群内选举的方式；这是典型的共识算法

重新配置系统使新主节点生效。

主从节点切换也会有很多需要考虑的挑战

：

1）若使用异步复制，且主从切换前，新的主节点没有收到原主节点的所有数据；则会发生数据丢失。若切换之后原主节点又加入到集群，又该如何做呢？

2）若发生脑裂，有两个节点都认为自己是主节点，怎么办呢？

3）如何设置合适的超时来检测主节点失效呢？太长会导致恢复时间过久；太短可能会导致不必要的切换

我们继续讨论主从复制的技术细节到底是如何工作的？也就是主节点的数据如何序列化成网络数据传输到从节点

复制和存储引擎可以使用不同的日志格式，这样复制日志就能从存储引擎内部分离。这种复制日志称为逻辑日志，以区分存储引擎的数据表示。比如行插入/更新/删除，复制日志中包含所有相关列的新值，从节点解析这些逻辑日志后应用到自身即可；

Mysql

的二进制日志binlog

就使用该方式；这种方式称为基于行的逻辑日志复制

对外部应用程序来说，逻辑日志格式更容易解析；因此通过接出复制日志，可是方便的将数据库数据同步到离线数仓中除了基于逻辑日志

的复制外，还有基于语句的复制

和基于WAL日志的复制

基于语句的复制

主节点记录执行的所有写请求，并将该操作语句作为日志发送给从节点；类同于每个从节点都在执行来自客户端的请求；非首选方案；会存在不适用的场景:1）非确定性函数的语句，如Now()

Rand()

，不同副本会产生不同的值；2）有副作用的语句，如触发器/用户自定义函数，会在不同副本有不同副作用

基于预写日志(WAL

)传输

主节点除了将WAL

日志写入磁盘之外，还会通过网络将其发送给主节点；缺点是日志描述的数据非常底层，如哪些磁盘块的哪些字节发生改变；不同版本的存储可能会有差异，无法进行滚动升级，只能停机升级；

2.1.2复制滞后问题

使用数据多副本部署除了能够解决节点故障之外，还期待能解决扩展性

（多节点处理更多请求）和低延迟

（副本部署在离用户更近的位置）。一个很现实的问题就是从节点读取到的信息不是最新的，也就是复制滞后问题

。复制滞后可能带来以下问题:

读不到自己的写

如上图，用户查询时可能会请求到复制滞后的从节点2

上；用户会觉得自己的写操作丢失了，实际上并没有；

这种情况下，我们需要实现“读写一致性”，方法有:1）有必要则读主节点，比如：网络社交首页只有所有者能编辑，因此从主节点读取自己的首页配置，从节点读取其他人的配置；能够保证作者更新信息后及时看到。2）客户端记录最近更新的时间戳，附带在请求中，如果从节点不够新，则将请求转发到另一个符合要求的节点来处理

单调读（不可重复读）

如上图，用户2345首次访问了从节点1看到了最新的内容，但是第二次访问了从节点2，但此时会读到旧数据；

单调读是一个比强一致性弱，但比最终一致性强的保证，单调读保证，如果某个用户依次进行多次读取，绝不会看到回滚现象

实现单调读的一种方式是：确保每个用户总是从固定的同一副本执行读取，如使用用户ID的哈希方法来决定副本读取；

分区数据时序错误

在观察者看来，答案（通常约10s,poons先生）发生在问题（Cake夫人，您能看到多远的未来？)之前。

分区数据经常会遇到这个问题，问题和答案会保存在不同的分区中，不同分区的复制进度是不同的

需要确保任何具有因果关系的写入都交给同一个分区来解决。

2.2多主节点复制

上面介绍的主从复制最为常见，但是在不考虑分片的情况下也有一个明显的缺点：系统只有一个主节点，所有的写入都要经由主节点。主节点的延迟会影响所有的写入操作。

因此扩展引申出多主节点的复制。

2.2.1多主节点复制的应用场景

1.多数据中心

：在每个数据中心都配置主节点，数据中心内部仍是主从复制，跨数据中心则由主节点负责数据中心间的数据交换和更新。写请求不再需要跨地域执行，并且也能容忍整个数据中心失效的故障；

多主节点复制最大的问题就是冲突解决

：不同的数据中心可能会同时修改相同的数据

2.离线客户端操作

：比如日历或者印象笔记等应用，无论设备是否联网都是允许工作的，且同一个账户在多设备都可以登录。因此需要在下次联网的时候完成数据同步；从结构层面来讲，也等同于数据中心之间的多主复制，每个设备就是一个数据中心。

3.协作编辑

：腾讯文档/GoogleDocs

等允许多人同时编辑，每一行/单元格可以看作一个key

，和多主复制也有类似之处。

2.2.2处理写冲突

多主复制最大的挑战就是解决写冲突

，如上图，跨地域的用户1和用户2同时修改了title

，主节点1收到主节点2同步过来的请求时发现是冲突的，必需有一种冲突解决方案决定title

最终是改为B

还是改为C

避免冲突

你可能想不到，处理冲突最理想的策略就是：避免发生冲突

。应用层保证对特定记录的写请求总是路由到同一个主节点，就不会发生写冲突。比如我们的服务部署了天津/深圳两个地域，两个地域是多主节点复制，则每一个用户只会路由到天津或者深圳其中一个地域，不会存在写冲突；从用户的角度开看，基本等价于主从复制模型

所有副本数据收敛于一致状态

上述示例中，因为title

从A->B

和A->C

是并发的，不存在hapen-before

关系，因此不管最终主节点1和主节点2的title

是变成B

还是变成C

都是可以的，重要的是两个主节点对title

存储的值要一致

实现收敛于一致的可能方式:

每个写请求分配唯一的ID

(时间戳/随机数/UUID

)，每个副本仅保留最高ID

作为胜利者写入，其他写入请求则丢弃；

为每个副本分配一个序号，序号大的副本写入优先级高于低序号的副本；

将冲突的结果都记录下来，依靠应用层（或用户）来决策。如上例中，将B/C

都记录下来，让用户决策最终使用哪个标题；

方案1/方案2都可能造成写入数据丢失，方案1中若是基于时间戳，也被称为最后写入者获胜

，后面再讨论

2.2.3多主复制的拓扑结构

若存在多主节点，对其中一个节点的写入如何扩散到所有的主节点，通常有三种方式：

环形拓扑和星形拓扑中因为要避免无限循环写入，因此复制日志中需要记录已通过的节点标识，若节点收到了包含自身标识的数据更改请求，说明已经处理过，忽略即可；同时这两种拓扑类型若有节点故障也会导致同步中断；全链路拓扑（上图C

）存在的最大问题是部分网络链路比其他链路更快的情况，如下图:

客户端B在主节点2上的操作早于客户端A在主节点2上的操作，就导致了更新操作早于插入操作；可以使用版本向量

的技术来解决；

使用多主节点复制的数据库时，上述提到的问题都值得关注，看该数据库是如何解决这些问题的，方便我们技术评估和调研

2.3无主节点复制

除了2.1和2.2中讨论的主从复制

和多主复制

，还有一种副本同步的方式是无主复制

该模式下不再区分主节点和从节点

，允许任何副本直接接受来自客户端的写请求。

用户1234作为客户端写入时，将写请求发送到所有的副本，即使副本3

宕机，客户端仍认为写入成功（多数节点返回成功），用户2345读取的时候也会将读请求发送给所有节点，每个节点都会返回当前值和版本，客户端可以获取到最新的值(version=7

)，并修复副本3

的值（这一步也称为读修复

）；

除了读修复之外，还有另一种方案，后台进程不断查找副本之间的数据差异，将缺少的数据完成修复，称之为反熵过程

2.3.1读写quorum

客户端写入/读取都需要跟所有副本交互，那写入/读取多少多少个副本就认为是成功呢？

假定有n

个副本，w

表示写成功的副本数量，r

表示读取成功的副本数量，只要满足w r>n

，则读取的副本节点中一定包含新值，因为此时参与读写的副本之间一定是有交集的

此限制也不能完全保证结果正确，假定一种场景：1）写操作和读操作同时发生，写操作已经在一部分副本上完成，此时读请求仍有可能返回旧值；2）某些副本写入成功，部分写入失败，则成功的副本并不会回滚；读请求可能返回新值，也可能返回旧值

2.3.2并发写的一致性

如果每个节点接收到请求就直接执行，从零开始深入理解存储引擎所有节点最终很难达成一致；如上图，因为每个节点执行命令的时序不同，最终结果也是错误的；

最后写入者获胜

只要我们有办法判定哪个写入是最新的，那所有副本最终都会收敛到相同的值；我们可以针对每个写请求附加一个时间戳（客户端的本地时间），节点仅存储最新/最大时间戳的请求保存即可；这是cassandra

仅有的冲突解决方案；

更多LWW-lastwritewins

最终写入者获胜的信息可参考：

版本矢量

每个副本和每个主键均定义一个版本号，每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本看到的版本号。通过这些信息来决定要覆盖/保留哪些并发值。

3.数据分片

通过第二部分的讨论，我们已经能够在多个容器通过复制技术保存数据的多份副本，在宕机/降低读延迟和读QPS

扩展性上有了提升；但现在仍面临一个问题就是：数据在一台机器上存不下怎么办？

面对海量数据和非常高的查询压力，只是复制技术还不够，我们还需要将数据拆分成分片，用每个分片去承载部分数据和部分请求；对分片不同系统有不同的称呼，Shard

、Region

、Tablet

、vnode

、vBuciet

、Partition

等都是对分片

的领域特定称呼

3.1键-值数据的分片

如上图，数据被分成了4个分片，每个分片有3个副本，共12副本，其中每个机器存储3副本，共存储在4台机器上；

这里就会引出第一个问题：全量数据如何均分到4个分片上？

3.1.1基于关键字区间分片

如上图，我们按照“键”的区间来分区，字典序介于Bayey

-Ceanothus

的存储到分片2，介于Trudeau

-Zywiec

的存储在12号分片；为避免数据倾斜

，关键字分区并不要求均匀分布，根据各首字母记录条数可以动态调配分区管理；

但有一个问题就是热点数据会导致某一分片承载的读写请求特别多，其中一种方案就是在分区键前追加其他信息让数据分散到多个分片，查询时也需要并发查询；

3.1.2基于键的哈希值分片

如上图，将时间戳计算哈希值（此处使用MD5

）取膜后映射到不同分片管理的分区中（分片0管理结果位于0-8192的键)。

3.2分片再平衡

随着业务发展，数据量可能会越来越多，即使数据量不增多，查询压力也能越来越大；因此需要扩容更多的机器承载请求，即如何将数据从一个机器的分片移动到另一个机器的其他分片

针对分片的再平衡，一般要满足:

再平衡一定伴随着数据在不同分片之间的迁移，需要迁移到的目标分片是新增的分片还是已有分片就有比较大的区别；

3.2.1固定数量的分片

最简单的方案：创建远超实际节点数的分片数量，为每个节点分配多个分片；需要迁移时就从现有机器上挑选分片移动到新机器上即可；

如上图新增节点4之后，将p4

、p9

、p14

、p19

这4个分片迁移到新节点中；

我们可以将机器硬件配置

/热点分区

考虑进来，硬件配置高的机器多分配一些分片，热点访问量比较高的分区所在机器少分配一些分片；

分片的大小应该“恰到好处”：若数据量非常大，则在数据迁移时候成本很高，数据量太少就会产生太多的开销；

RiakESCouchbaseRedis等都使用该方案

3.2.2动态分片

初始仅创建少量分片，当分片的数据增长超过一定阈值时（如10GB

），就会拆分成2个分片，每个分片承担一半的数据；反之，分片也会合并；每个分片只会分配给一个机器，但是一个机器可以承载多个分片数据；

MongoDBHBase等使用该方案

3.2.3按节点比例分区

动态分片的分片数量和整体数据集的大小成正相关；固定分片的每个分片大小和整体数据集大小成正相关；他们都与节点数没有关系；Cassandra

则采用了第三种方式，使分片数和集群节点数成正相关；即每个机器有固定数量的分片；

现在我们解决了数据分片和分片再平衡的问题，每个分片都会有主从节点；分片数量和每个分片内主从节点的数量和角色都会变化，这里就有了一个新的问题：客户端如何知晓该把请求发往哪个分片的哪个节点呢？

3.3请求路由

分片数据已经就绪，客户端应该把请求发送到哪个机器上呢？尤其是若发生了分片动态再平衡，分片与节点的关系也会随之变化；这本质上是一个服务发现

问题；

如上所示，通常有三种方式：1）节点转发；2）代理层转发；3)客户端缓存分区关系。

3.3.1节点转发

客户端连接任意节点，若节点恰好该数据则直接返回，若节点没有数据，则将请求转发到合适的节点，并将结果返回给客户端

3.3.2代理转发(proxy)

在客户端和数据库之间增加一个代理层（Proxy

）,Proxy

记录分片和节点机器的映射关系，负责请求的转发和响应；Proxy

本身不处理请求，只是一个感知分片的负载均衡器。

该方案采用较多，一来客户端不需要有复杂的逻辑，Proxy

可屏蔽分片/节点的动态变化；再者，处理类似于Redis

中的MGet

等涉及多个键的命令时，Proxy

可以完成分发&合并结果的工作；最后，Proxy

还可以处理"迁移中"的数据，如一个分片正在从一台机器迁移到另一台机器，命中该分片的请求该如何处理？

3.3.3客户端缓存分区关系

客户端感知分区和节点的分配关系，客户端可直接联系到目标节点，不需要任何Proxy

3.3.4分片和节点的映射关系如何维护？

在使用代理转发的选择下，需要去存储并感知分片和节点IP

的映射关系：

一般采用独立的协调服务(zookeeper

/ETCD

)跟踪集群范围内的元数据变化。如上图，节点分片的动态再平衡（可能是人工通过控制节点触发，也可能是自动再平衡）会同步写到Zookeeper

中，Proxy

通过watch

感知到节点变化之后会将后续请求转发到正确的节点；

关键字区间会映射到不同的分区，多个分区会映射到同一个节点中，图例中仅展示了主节点；

经过上面所有的讨论，我们可以得到如下这个相对通用的分布式存储架构：

当然，还有事物、一致性保证、共识算法，异常处理等等很多问题我们并没有讨论；也会有遗漏和错误，烦请指正～

参考资料:

《数据密集型应用系统设计》

《数据库系统内幕》