从NoSQL到NewSQL,谈交易型分布式数据库建设要点数据库

来源:互联网 / 作者:SKY / 2018-05-07 15:15 / 点击:
在上一篇文章《从架构特点到功能缺陷,重新认识分析型分布式数据库》中,我们完成了对不同“分布式数据库”的横向分析,本文我将讲述拆解的第二部分,会结合NoSQ

在上一篇文章《从架构特点到功能缺陷,重新认识分析型分布式数据库》中,我们完成了对不同“分布式数据库”的横向分析,本文我将讲述拆解的第二部分,会结合NoSQLNewSQL的差异,从纵向来谈谈OLTP场景“分布式数据库”实现方案的关键技术要点。这样的思考是前文的延伸,也是分布式数据库专题文章的一个总纲,其中的要点我之后也会单独撰文阐述。

一、NewSQL & NoSQL

NewSQL是本专题关注的重点,也是前文中特指的“分布式数据库”,其适用于OLTP场景,具有高并发低延迟的特点,特性接近Oracle/DB2等传统数据库,依赖通用X86服务器实现性能上的水平拓展,能够扛住海量交易的性能压力。

目前具有较高知名度的NewSQL有Google的Spanner / F1、阿里的OceanBase、CockroachDB、TiDB。其中后两者是正在成长中的开源项目,2018年相继发布了2.0版本。

NewSQL与NoSQL有很深的渊源,所以下文在对NewSQL的介绍中会穿插一些NoSQL对应的实现技术方式。

1、存储引擎

B+ Tree

B+树是关系型数据库常用的索引存储模型,能够支持高效的范围扫描,叶节点相关链接并且按主键有序,扫描时避免了耗时的遍历树操作。B+树的局限在于不适合大量随机写场景,会出现“写放大”和“存储碎片”。

以下借用姜承尧老师书中的例子[1]来说明B+树的操作过程

存在高度为2的B+树,存储在5个页表中,每页可存放4条记录,扇出为5。下图展示了该B+ Tree的构造,其中略去了叶子节点指向数据的指针以及叶子节点之间的顺序指针:

从NoSQL到NewSQL,谈交易型分布式数据库建设要点

B+树由内节点(InterNode)和叶节点(LeafNode)两类节点构成,后者携带指向数据的指针,而前者仅包含索引信息。

当插入一个索引值为70的记录,由于对应页表的记录已满,需要对B+树重新排列,变更其父节点所在页表的记录,并调整相邻页表的记录。完成重新分布后的效果如下:

从NoSQL到NewSQL,谈交易型分布式数据库建设要点

变更过程中存在两个问题:

写放大

本例中,逻辑上仅需要一条写入记录(黄色标注),实际变动了3个页表中的7条索引记录,额外的6条记录(绿色标注)是为了维护B+树结构产生的写放大。

注:写放大(Write Amplification):Write amplification is the amount of data written to storage compared to the amount of data that the application wrote,也就是说实际写入磁盘的数据大小和应用程序要求写入数据大小之比

存储不连续

新增叶节点会加入到原有叶节点构成的有序链表中,整体在逻辑上是连续的;但磁盘存储上,新增页表申请的存储空间与原有页表很可能是不相邻的。这样,在后续包含新增叶节点的查询中,将会出现多段连续读取,磁盘寻址的时间将会增加。进一步来说,在B+Tree上进行大量随机写会造成存储的碎片化。

在实际应用B+Tree的数据库产品(如MySQL)中,通常提供了填充因子(Factor Fill)进行针对性的优化。填充因子设置过小会造成页表数量膨胀,增大对磁盘的扫描范围,降低查询性能;设置过大则会在数据插入时出现写扩大,产生大量的分页,降低插入性能,同时由于数据存储不连续,也降低了查询性能。

LSM-Tree

LSM-Tree(Log Structured-Merge Tree)由Patrick O'Neil首先提出,其在论文[2]中系统阐述了与B+树的差异。而后Google在Bigtable中引入了该模型,如下图所示:

从NoSQL到NewSQL,谈交易型分布式数据库建设要点

LSM-Tree的主要思想是借助内存将随机写转换为顺序写,提升了写入性能;同时由于大幅度降低了写操作对磁盘的占用,使读操作获得更多的磁盘控制权,读操作性能也并未受到过多的影响。

写操作简化过程如下:

从NoSQL到NewSQL,谈交易型分布式数据库建设要点

当写入请求到达时,首先写入内存中Memtable,处理增量数据变化,同时记录WAL预写日志;

内存增量数据达到一定阈值后,当前Memtable会被冻结,并创建一个新的Memtable,已冻结的Memtable中的数据会被顺序写入磁盘,形成有序文件SSTable(Sorted String Table),这个操作被称为Minor Compaction(在HBase中该操作称为Flush操作,而Minor Compaction有其他含义);

这些SSTable满足一定的规则后进行合并,即Major Compaction。每个Column Family下的所有SSTable被合并为一个大的SSTable。

该模型规避了随机写的IO效率问题,有效缓解了B树索引的写放大问题,极大的提升了写入效率。

NoSQL广泛使用了LSM-Tree模型,包括HBase、Cassandra、LevelDB、RocksDB等K/V存储。

当然LSM-Tree也存在自身的缺陷:

首先,其Major Compaction的操作非常重影响联机读写,同时也会产生写放大。因为这个原因,HBase的使用中通常会禁止系统自动执行Major Compaction。

注释:

Major Compaction操作的意义是降低读操作的时间复杂度。设系统包含多个SSTable文件,共有N数据,SSTable平均包含m数据。

执行读操作时,对单一SSTable文件采用折半查找方法的时间复杂度为O(log2m),则整体时间复杂度为O(N/m* log2m);合并为一个SSTable后,时间复杂度可降低到O(log2N)

其次是对读效率的影响,因为SSTable文件均处于同一层次,根据批量写的执行时序形成若干文件,所以不同文件中的Key(记录主键)会出现交叉重叠,这样在执行读操作时每个文件都要查找,产生非必要的I/O开销。

最后是空间上的放大(Space Amplification),最坏情况下LSM Tree需要与数据大小等同的自由空间以完成Compact动作,即空间放大了100%,而B+树的空间放大约为1/3。

Leveled LSM Tree

Leveled LSM Tree 的变化在于将SSTable做了进一步的分层,降低写放大的情况,缩小了读取的文件范围,在LevelDB 中率先使用,随后Cassandra 1.0也引入了该策略[3]。

SSTable的层次化设计策略是:

单个SSTable文件大小是固定的,在Cassandra中默认设置为5M;

阅读延展

1
3