在上一篇《从架构特点到功能缺陷，重新认识分析型分布式数据库》中，我们完成了对不同“分布式数据库”的横向剖析。在这篇文章中，我将对拆解的第二部分进行描述，将结合NoSQL和NewSQL的区别，从纵向的角度来谈谈“分布式数据库”在OLTP场景下的实现方案的技术要点。这种思路是对上一篇文章的延伸，也是分布式数据库专题文章的一个大概概括。我将单独写一篇文章来详细说明要点。一、NewSQL&NoSQLNewSQL是本期的重点，也是上一篇文章特指的“分布式数据库”。适用于OLTP场景，具有高并发、低延迟的特点，其特性接近Oracle/DB2等传统数据库，依托通用的X86服务器实现性能水平扩展，可承受海量的性能压力交易。目前流行度较高的NewSQL有Google的Spanner/F1、阿里的OceanBase、CockroachDB、TiDB等。后两者是成长中的开源项目，2018年发布了2.0版本。NewSQL和NoSQL有着很深的渊源，所以NewSQL的介绍中会穿插一些NoSQL对应的实现技术。1.存储引擎B+TreeB+树是关系型数据库常用的索引存储模型。可以支持高效的范围扫描，叶节点相关链接按主键排序，扫描时避免了耗时的树遍历操作。B+树的局限性在于不适合大量随机写的场景，会出现“写放大”和“存储碎片”。下面用蒋承尧老师书上的例子[1]来说明，在B+树的运行过程中有一个高度为2的B+树，存储在5个页表中，每页可以存储4条记录，扇出为5。下图是B+树的结构，省略了叶子节点的数据指针和叶子节点之间的序列指针：B+树由两类节点组成：内部节点（InterNode）和叶节点（LeafNode）。携带一个指向数据的指针，而前者只包含索引信息。当插入一条索引值为70的记录时，由于对应页表的记录已满，需要重新排列B+树，更改其父节点所在页表的记录，调整相邻的页表。重分配后的效果如下：变更过程中存在两个问题：写放大本例中逻辑上只需要一条写记录（黄色标记），但实际上变更了3个页表中的7条索引记录。这6条记录（绿色标记）是为了维护B+树结构而生成的写入放大。注：WriteAmplification：写放大是写入存储的数据量与应用程序写入的数据量的比值，也就是说实际写入磁盘的数据大小与数据大小的比值应用程序编写的存储不连续性新加入的叶子节点会加入到原来叶子节点组成的有序链表中，整体逻辑上是连续的；但是，在磁盘存储上，新页表申请的存储空间很可能与不相邻的原页表相同。这样，在后续包含新增叶子节点的查询中，会出现多次连续读，磁盘寻道时间会增加。再者，B+Tree大量的随机写入会造成存储碎片。B+Tree数据库产品（如MySQL）在实际应用中，通常会提供填充因子（FactorFill）进行针对性优化。如果填充因子设置得太小，页表的数量会膨胀，增加磁盘的扫描范围，降低查询性能；不连续性还会降低查询性能。LSM-TreeLSM-Tree（LogStructured-MergeTree）最早由PatrickO'Neil提出，他在论文[2]中系统地解释了与B+树的区别。然后Google在Bigtable中引入了这种模型，如下图所示：LSM-Tree的主要思想是利用内存将随机写入转化为顺序写入，从而提高写入性能；同时大大降低了写操作的磁盘占用，使读操作获得更多的磁盘控制权，读操作性能也不会受到太大影响。写操作简化流程如下：当一个写请求到来时，首先写入内存中的Memtable，处理增量数据变化，同时记录WAL预写日志；当内存增量数据达到一定的阈值时，当前的Memtable会被冻结，并创建一个新的Memtable，被冻结的Memtable中的数据会依次写入磁盘，形成有序文件SSTable（SortedStringTable），这个操作称为MinorCompaction（在HBase中这个操作叫做Flush操作，MinorCompaction还有其他含义）；这些SSTables在满足一定规则后进行合并，即MajorCompaction。每个ColumnFamily下的所有SSTables被合并成一个大的SSTables。该模型避免了随机写入的IO效率问题，有效缓解了B树索引的写入放大问题，大大提高了写入效率。NoSQL广泛使用LSM-Tree模型，包括HBase、Cassandra、LevelDB、RocksDB等K/V存储。当然，LSM-Tree也有自身的缺陷：首先，其主要的compaction操作严重影响在线读写，还会产生写放大。为此，使用HBase通常会禁止系统自动执行MajorCompaction。注意：MajorCompaction操作的意义在于降低读操作的时间复杂度。假设系统包含多个SSTable文件，共有N条数据，SSTable平均包含m条数据。在执行读操作时，对单个SSTable文件使用半查找方式的时间复杂度为O(log2m)，整体时间复杂度为O(N/m*log2m)；合并成一个SSTable后，时间复杂度可以降低到O(log2N)二是对读取效率的影响，因为SSTable的文件都是同级的，按照执行的时机组成几个文件batchwrite，所以不同文件中的Keys（记录主键）会重叠重叠，所以在进行读操作的时候，必须对每个文件进行查找，造成不必要的I/O开销。最后是空间放大（SpaceAmplification）。在最坏的情况下，LSMTree需要与数据大小相等的空闲空间来完成压缩动作，即空间放大100%，而B+树的空间放大约为1/3。LeveledLSMTreeLeveledLSMTree的变化是将SSTable进一步分层，减少写放大的情况，缩小读文件的范围。最早在LevelDB中使用，后来Cassandra1.0也引入了这种策略[3]。SSTable的分层设计策略是：单个SSTable文件的大小是固定的，在Cassandra中默认设置为5M；level从Level0开始增加，存储的数据量随着level的增加而增加，level之间有一个一致的增长因子（GrowthFactor）。Cassandra中的GrowthFactor设置为10，Level1文件为1-10M，Level2文件为10-100M，这样10TB的数据量就会达到Level7；Level0的SSTable比较特殊，固定为4个文件，文件之间存在Key交叉重叠的情况。从Level1开始，SSTables将不再有Keycrossing。当Level0的SSTable超出容量时，会压缩到Level1。由于Key交叉，必须读取Level0的所有SSTable；当Level1的文件大小超过阈值时，将创建一个Level2SSTable，并删除原来的Level1SSTable；当Level1的Keyrange对应多个Level2的SSTable时，需要重写多个SSTable，但是由于SSTable的大小是固定的，所以通常只涉及到少量的SSTable。Compactbetweenlevels操作多个有序的SSTables，避免重写MajorCompaction等重量级文件，每次只更新部分内容，降低写放大率。对于读取元数据锁定相关的SSTables，效率明显高于对所有SSTables的halfsearch和BloomFilter。因此，读取效率得到了显着提高。根据某种评估方法[3]，当每行的数据大小基本相同时，90%的读操作只会访问一个SSTable。在这种策略下，compaction操作更加频繁，带来了更多的I/O开销。对于写密集型的操作，最终的结果能否达到足够的效率提升存在不确定性，需要在应用中权衡。NewSQL策略NewSQL数据库的存储层一般采用K/V存储，所以基本采用LSMTree模型。其中，CockroachDB和TiDB在KV层都使用了RocksDB。OceanBase采用不同的方式来避免majorcompaction的影响。通常，它使用空闲的副本（跟随者）来执行压缩操作，以避免阻塞读取操作。compaction完成后，replicas的作用就被替换掉了。同时，K/V存储引擎还在开发中，还有一些其他的改进比如分形树（FractalTree）等，限于篇幅我们这里就不展开了。2.Sharding分片的概念类似于RDBMS的分区。它是分布式数据库或分布式存储系统最关键的特性，也是横向扩展的基础。它也被广泛用于NoSQL系统。分片的目标是将数据尽可能均匀地分布在多个节点上，利用多个节点的数据存储和处理能力来提高数据库的整体性能。Range&Hash虽然在不同的系统中分片策略有很多细分，但大致可以归纳为两种方法，Range和Hash。Rangesharding有利于范围查询，而Hashsharding更容易实现数据的均衡分布。在实际应用中，Rangesharding似乎用得比较多，但也有很多应用混合使用这两种sharding方式。HBase采用Range方式，按照Rowkey的字典序排列。当超过单个Region的上限时，会分裂成两个新的Region。Range的优点是数据位置较近，访问数据时范围搜索成本低；缺点也很明显，容易出现热点集中的问题。比如在HBase中，一般不建议使用业务流水号作为RowKey，因为不断增加的流水号大部分时间会分配给同一个RegionServer，导致并发访问争抢RegionServer资源同一时间。为了避免这个问题，建议对RowKey进行编码，反序列号或者加盐。这种方式本质上是利用了应用层的设计策略，将Rangesharding转化为类似Hashsharding的方式。Spanner的底层存储沿用了BigTable的很多设计思想，只是在分片上做了一些调整。Tablet中增加Directory的动态部署，避免Range分片与操作热点不匹配，后面事务管理部分会详细介绍。.Staticsharding&dynamicsharding根据分片的生成策略可以分为静态分片和动态分片。静态分片在系统建设之初就已经确定了分片的数量，后期改变成本非常高；动态分片是指根据数据情况指定分片策略，其变更成本低，可以根据需要进行调整。在传统的DB+Proxy方案中，水平分库和分表是一种常见的静态分库。我们熟悉的几家主要的互联网公司都在大型交易系统中进行过类似的设计。默认情况下，数据被做成固定数量的分片，比如100、255、1024，或者其他你喜欢的数字。分片的数量可以根据系统预期目标的整体服务能力、数据量和单节点容量来评估。当然，100个分片合适还是1024个分片合适，就是脑洞大开的问题了。在NoSQL中，Redis集群也采用了同样的静态分片方式，默认为16384个哈希槽（相当于sharding）。静态分片的缺点是分片数量已经确定，根据单点处理能力形成容量上限；灵活性较差，后期调整分片数量时，数据迁移实施困难复杂。优势也很明显。静态分片的策略几乎是固化的，因此对分区键、分区策略等元数据管理的依赖性很低，而且这些元数据在分布式数据库中往往形成一个单点，成为可靠的改进源泉。性能和可用性的障碍。相比之下，动态分片更加灵活，适用于更丰富的应用场景，所以NewSQL也主要采用动态分片，代价是增加了元数据管理的复杂度。在分片方面，NoSQL非常接近NewSQL面临的问题。3、拷贝首先是由于通用设备单机可靠性低，所以必须多机拷贝。本文主要关注两个问题：一是副本一致性；另一个是副本可靠性和副本可用性之间的区别。数据副本一致性多副本必然会引入副本的数据一致性问题。之前有一个很有名的CAP理论，相信大家都不陌生，但是这里换个说法，CAP中的一致性和事务管理中的一致性不是一回事。我遇到过很多同学的误解，以CAP为依据证明分布式架构不能实现事务的强一致性，只能实现最终一致性。事务的一致性是指不同的数据实体在同一个事务中一起发生变化，要么全部成功，要么全部失败；而CAP中的一致性是指如何保证原子粒度数据副本的一致性，多个副本在逻辑上是同一个数据实体。副本同步大致可以分为以下三种模式：强同步：即数据更新必须在多个副本中完成，数据更新才能成功。这种模式的问题是高延迟和低可用性。一个操作要等待所有副本更新完毕，增加了大量的网络通信开销，增加了延迟。整个系统只有在多个副本节点正常运行时才可用，任何一个单点不可用都会导致整个系统不可用。假设单点可用性为95%，那么三个节点组成的多副本的可靠性为95%*95%*95%=85.7%。因此，虽然Oracle/MySQL等主流数据库提供了强大的同步方式，但在企业的实际生产环境中却很少使用。半同步：MySQL提供了一种半同步的方式。多个从节点从主节点同步数据。当任何一个从节点同步成功时，主节点就认为同步成功。这种逻辑模型有效避免了强同步的问题，多节点可用性的影响由“和”变为“或”，保证了整体的可用性。但遗憾的是，技术实现存在缺陷，会出现退化为异步的问题。Paxos/Raft：这种方式将参与节点划分为Leader/Follower等角色，主节点向多个备节点写入数据。当超过一半的节点写入数据成功时，将写入成功返回给客户端。这种方式可以避免网络抖动和备节点服务异常对集群整体的影响。其他像Zookeeper的ZAB协议和Kafka的ISR机制虽然和Paxos/Raft不同，但大体上是大同小异。副本可靠性和副本可用性数据副本只保证数据的持久性，即数据不丢失。我们还面临副本可用性的问题，即是否持续提供数据。以HBASE-10070为例说明这个问题：HBase通过分布式文件系统HDFS实现数据的多副本存储，但是在提供服务时，客户端连接到RegionServer，然后访问HDFS上的数据。因为一个Region会由唯一的RegionServer来管理，RegionServer仍然是一个单点。当RegionServer宕机时，需要经过一定的时间间隔后被HMaster检测到，后者调度新的RegionServer并加载对应的Region。整个过程可能需要几十秒。在大型集群中，单点故障频繁发生，每个单点都会导致本地服务中断几十秒，大大降低了HBase的可用性。为了解决这个问题，HBase引入了从RegionServer节点的概念。当主节点宕机时，从节点继续提供服务。但是，RegionServer不是无状态服务。它在内存中存储数据，存在主从RegionServer之间数据同步的问题。HBase实现了数据的可靠性，但仍然不能完全实现数据的可用性。CockroachDB和TiDB的思路是实现一个支持Raft的分布式KV存储，从而完全忽略单节点内存数据和磁盘数据的差异，保证数据的可用性。4.事务管理分布式事务处理由于其复杂性是NoSQL发展中第一个被抛弃的特性。但由于大规模互联网应用的广泛出现，其实际意义逐渐凸显，再次成为NewSQL无法回避的问题。随着NewSQL对事务处理的改进，过去十年的数据库技术演进终于实现了近乎完全的螺旋式上升。鉴于分布式事务管理的复杂性，本文只作简要说明，后续文章会进一步展开。NewSQL事务管理在控制方式上分为lock-base和lock-free。其中，无锁模式通常是根据时间戳来协调事务冲突。从资源占用上分为乐观协议和悲观协议。两者的区别在于对资源冲突的期望不同：悲观协议认为冲突频繁，因此会尽快抢占资源，保证交易的顺利完成；乐观协议认为冲突是零星的，资源只会在最近的可容忍时间被抢占。下面通过最经典的“两阶段提交协议”和两个具体的应用实践详细介绍其实现方法：两阶段提交协议（2PC）两阶段提交协议（Towphasecommitprotocol，2PC）是一种经典的分布式事务处理模型，处理过程分为两个阶段：请求阶段：事务查询。协调器向所有参与者发送交易内容，询问是否可以进行交易提交操作，并开始等待各参与者的响应；执行交易。每个参与节点执行事务操作，并在事务日志中记录Undo和Redo信息；每个参与者将交易查询的响应反馈给协调者。如果参与者成功执行交易操作，会反馈给协调者Yes，表示交易可以执行；如果参与者未能成功执行交易，则反馈No，表示交易无法执行。提交阶段：提交事务。发送提交请求。协调器向所有参与节点发送Commit请求；事务已提交。参与者收到Commit后，将正式执行事务提交操作，并在提交完成后释放整个事务执行期间占用的事务资源；反馈事务提交结果。参与者完成交易提交后，向协调者发送Ack消息；交易完成。协调者收到所有参与者的Ack消息后，交易完成；交易中断。发送回滚请求。协调者向所有参与者发出回滚请求；事务回滚。参与者收到Rollback请求后，将使用Phase1记录的Undo信息进行事务回滚操作，并在回滚完成后释放整个事务执行期间所占用的事务资源；反馈事务回滚结果。参与者完成事务回滚后，向协调者发送Ack消息；交易中断。协调器收到所有参与者反馈的Ack消息后，事务中断完成。该模型的主要优点是原理简单，易于实现。缺点也很明显。第一个是同步阻塞。整个交易过程中所有参与者都处于锁定状态，这必然会极大地影响并发性能。二是单点问题。协调器是一个单点。如果在第二阶段崩溃，则参与或将保持锁定状态。根据Spanner的论文[4]介绍，Spanner的分布式事务管理仍然采用2PC的方式，但创新的设计是改变了Tablet的数据分布策略。Tablet不再是单一连续的Key数据结构，新的Directory是最小的可调度数据组织单元。通过动态部署，降低了事务内数据跨节点分布的概率。我对这种事务处理的设计思路理解为：“最好的分布式事务处理方式不是做分布式事务处理，而是把它变成本地事务”。在OceanBase的早期版本中，也使用了一个独立的服务器UpdateServer来集中事务操作，概念类似。PercolatorPercolator[5]是谷歌开发的增量处理网页索引系统。在它诞生之前，Google使用MapReduce进行全网页索引处理。这样的处理时间取决于现有网页的数量，需要很长时间；并且即使某一天只有少量的网页变化，也必须进行全量的索引处理，浪费了大量的资源和时间。采用Percolator的增量处理方式后，处理时间大大减少。本文给出了一种分布式事务模型，它是“两阶段提交协议”的一种变形，将第二阶段的工作简化到极致，大大提高了处理效率。具体实现上，Percolator基于BigTable实现了分布式事务管理。通过MVCC和锁两种机制的结合，事务中所有要操作的记录都是新版本，不更新已有版本。这样做的好处是读操作在整个事务过程中不会被阻塞。事务中的锁分为主锁和副锁。主锁是加在事务中最先操作的记录上，然后随着操作的过程逐步加到事务中的其他记录上，并指向主锁记录。一旦遇到锁冲突，低优先级事务释放锁，事务回滚；交易中的所有记录更新后，交易进入第二阶段。此时只需要更新主锁的状态，交易就可以结束；从锁锁的状态依赖于异步进程和相关的读操作来协助完成。由于指向主锁记录的指针保留在从锁记录上，异步进程和读取操作可以很容易地确定从锁的正确状态并更新它。分布式事务管理的其他内容，包括无锁事务控制、全局时钟的必要性等，将在后续文章中讨论。2.结语这篇文章和上一篇文章的初衷是为几个典型技术背景的同学从不同方向解读“分布式数据库”，并对其中的一些技术点进行讲解，让不同技术领域的同学都能理解相关的我对技术略有了解，为有兴趣深入研究的同学做铺垫。随着分析的深入，感觉文章框架太大，难以把控，所以对关键技术的解读也不尽相同。对于本文没有展开的部分，我会在后续的系列文章中尽量补充。文章水平有限，难免有错漏之处。欢迎大家讨论指正。参考资料：[1]蒋成耀，MySQL技术内幕：InnoDB存储引擎机器，机械工业出版社，2011[2]PatrickO'NeilTheLog-StructuredMerge-Tree[3]LeveledCompactioninApacheCassandrahttps://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra[4]JamesC.Corbett、JeffreyDean、MichaelEpstein等人。Spanner：Google的全球分布式数据库[5]DanielPeng和FrankDabek，使用分布式事务和通知进行大规模增量处理
