数据库从0到0.1 (一): LSM-Tree VS B-Tree


作者: 康凯森

日期: 2018-05-26

分类: 数据库


数据库最基本两个功能:数据的存储和数据的查询当我们写入数据时,数据库可以存储数据;当我们需要访问数据时,数据库可以给我们想要的数据。 数据库会通过特定的数据模型和数据结构存储数据,并支持通过特定的查询语言访问数据。本文将从最简单的数据库开始,讨论数据库如何存储数据,如何查询数据。本文将讨论两种存储引擎:log-structured 存储引擎和以B+树为代表的page-oriented存储引擎。

1 最简单的数据库

#!/bin/bash

#key,value对追加写入文件的最后一行
db_set () {    
    echo "$1,$2" >> database
}

#查找指定key的最后一行的最新的value
db_get () {    
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

上面两个Shell函数实现了最简单的Key-Value数据库。 调用db_set可以写入数据,调用db_get可以查询数据,数据的物理存储格式是逗号分隔的普通文本文件。

bash-3.2$ db_set 1 kks
bash-3.2$ db_get 1
kks
bash-3.2$ db_set 2 kangkaisen
bash-3.2$ db_get 2
kangkaisen
bash-3.2$ db_set 1 KKS
bash-3.2$ db_get 1
KKS
bash-3.2$ cat database
1,kks
2,kangkaisen
1,KKS

其中db_set函数拥有很好的写入性能,因为是追加写;但是db_get函数的性能十分糟糕,其时间复杂度是O(n),我们每次必须全表Scan。

2 Index

为了能够快速找到特定Key对应的Value, 我们需要引入一个数据结构:Index。 所谓Index,就是我们在数据库中增加额外的元数据,然后Index像路标一样可以快速知道我们需要访问数据的位置和偏移量。 Index类似汉语字典中的索引和一般书籍中的目录。如果我们需要按照不同的方式访问相同的数据,我们有可能需要多种不同的索引,比如按照Key查询和按照Value查询,我们会分别需要针对Key的索引和针对Value的索引。

Index是基于原始数据衍生的附加的数据结构,增加索引必然意味着降低数据写入速度,增大存储空间,所以Index是以数据写入时的处理成本和存储的空间成本来换取查询的加速。这也是数据库设计的一个trade-off,不同索引的查询加速比,写入时的处理成本,存储的空间成本往往是不同的,所以在设计数据库时选择何种索引是一个很重要的点。

3 Hash Index

下面就让我们用Index加速之前最简单的Key-Value DB。之前我们db_get方法查询特定Key必须全表Scan的原因,是因为我们不知道特定Key在文件中的Offset,假如我们知道了每个Key的Offset,我们就可以直接Seek到Key对应的Offset,直接读取Key对应的Value。而Key到Offset的映射我们自然会想起到我们熟悉的数据结构HashMap,我们可以在内存中维护一个HashMap,HashMap的Key就是Key-Value DB的每一条记录的Key,HashMap的Value就是每一条记录在文件中的Offset。

屏幕快照 2018-05-01 下午5.56.01.png-298kB

有了HashMap后,我们每次写数据后就必须要更新HashMap,查询数据时先从HashMap获取特定Key的Offset,再直接Seek到文件对应Offset的位置,读取数据。 事实上Bitcask(Riak的默认存储引擎)就是这样做的。

不过显然Hash Index有两个缺陷:

  1. 内存的大小必须可以放下Hash Table
  2. Range Scan的效率十分低下

4 Segment

目前为止,我们都是把数据写到一个文件中,这显然是不合理的。 一个常见的做法就是将文件按照大小拆为为Segment,每个Segment是不可变的。 Segment的概念很常见,比如Kylin和Druid中都有Segment的概念,指一定大小或者一定时间内不可变的文件。

第1部分我们知道,我们同一个Key的Value的更新只是追加写入,并没有删除旧的Value。 当我们有了多个Segment后,我们自然就可以定期在后台执行Compaction操作,将同一个Key的旧Value删除,更进一步,如果我们数据库支持delete的话,我们可以在一开始只进行标记,并不实际删除,等到Compaction的时候,我们再进行实际删除。 总之一句话,基于log-structured的存储引擎,我们可以通过后台的Compaction来实现update和delete,Compaction时依然可以进行数据的写入和查询。

屏幕快照 2018-05-01 下午6.10.49.png-239.1kB

至此,每个Segment文件都在内存中有了对应的Hash table。 我们查询时为了找到特定Key对应的Value,我们依次查询每个Segment文件即可,查询每个Segment文件的过程和之前一样。

这种Append-only Log-structured的存储引擎的优点:

  1. 顺序写的效率远高于随机写
  2. 并发控制和故障恢复十分简单,因为Segment文件是不可变的,且是Append-only的,

为什么不再对Segment文件做索引呢?

这样我们就不需要顺序遍历每个Segment文件了,有了索引我们就只需要访问包含特定Key的Segment文件。

5 SSTables and LSM-Trees

现在对Segment文件的格式做个简单的改变:我们要求所有的 key-value对必须按照Key排序。 这种格式我们称之为Sorted String Table, 简称为SSTable。 我们也要求在每个已经Merged的Segment文件中1个Key只会出现一次,Compaction过程保证了这一点。

SSTable相比Log Segments + Hash Indexes 有以下几个明显的优势:

  1. Segment的Merge会更加简单和高效,即使合并的所有文件比内存还大。 因为每个Segment是有序的,Sort Merge的成本比较低。
  2. 为了查找特定Key,我们不再需要在内存中维护一个很大的Hash Map。因为所有的key-value对是按照Key排序的,所以我们可以维护一个Segment文件的稀疏索引,索引的Key是每个Segment文件的Start Key,Value就是每个Segment文件的位置。 其次,在Segment内部,由于Segment有序,我们不再需要针对每个key-value对都构建索引,我们可以针对Block(几百或者几千行数据)粒度做稀疏索引,Block内存则进行二次查询。
  3. 由于我们的读取的最小粒度是Block,我们也可以基于Blcok粒度做压缩,减小磁盘空间和IO。
  4. SSTable不仅可以较好的支持Point Query,也可以很好的支持Range Scan。

屏幕快照 2018-05-01 下午6.26.22.png-292.6kB

那么我们如何保证Segment文件有序呢? 因为数据写入一般都要经过内存,在内存中我们可以利用Red-black tree 或者AVL tree保证有序。

至此,我们基于SSTable的存储引擎可以这样Run起来:

  1. 当一条数据写入时,我们将其插入到基于内存的平衡树中(Red-black tree)。 内存中的树我们称之为Memtable
  2. 当Memtable的大小超过一定阈值时,我们将Memtable Flush到磁盘,转为SSTable
  3. 当我们查询时,需要同时查询内存中的Memtable和磁盘中的SSTable。
  4. 周期性的在后台进行异步的Merge和Compaction操作。
  5. 为了防止Memtable在Flush到磁盘前机器故障导致数据丢失,我们可以在磁盘上维护一个只追加写的log文件,称之为Write-Ahead-Log,当集群故障后可以从log中恢复出Memtable。 所以我们在每次写入Memtable,需要先写入WAL。当Memtable flush到磁盘后,对应的WAL文件就可以删除。

至此,LSM-Tree(Log-Structured Merge-Tree)的3个组件:SSTable,Memtable,Write-Ahead-Log终于全了。 从开始最简单的Key-Value 数据库 讲到现在,我相信你已经理解了LSM-Tree的核心思想。

LSM-Tree 已经被广泛使用,比如LevelDB,RocksDB,Cassandra,HBase等,其中的SSTable也是被广泛借鉴,比如ClickHouse,Palo等。

6 磁盘简介

磁盘结构

如图,一个磁盘由多个盘片组成。

磁盘结构

如图,1个盘片由一个个的同心圆组成,一个同心圆就是一个磁道,每个磁道由多个扇区组成,每个磁道的扇区数量是一个常量,每个扇区的大小一般是4KB,扇区是磁盘基本的物理单元

一次磁盘IO的耗时主要由三部分组成:寻道时间 + 旋转延迟 + 数据传输时间

  1. 寻道时间: 将读写磁头移动至正确的磁道上所需要的时间。 目前磁盘的平均寻道时间一般在3-15ms。
  2. 旋转延迟: 盘片旋转将请求数据所在的扇区移动到读写磁盘下方所需要的时间。旋转延迟取决于磁盘转速,转速为15000rpm的磁盘其平均旋转延迟为2ms。
  3. 数据传输时间:传输实际数据所需要的时间,它取决于数据传输率,其值等于数据大小除以数据传输率。目前IDE/ATA能达到133MB/s,SATA II可达到300MB/s的接口数据传输率,数据传输时间通常远小于前两部分消耗时间

提高磁盘读写速度方法就是尽量减小寻道时间和旋转延迟,而减少寻道时间和旋转延迟的方法就是减少磁盘的随机IO,这就是为什么磁盘顺序读写的性能远高于随机读写的原因。

7 B-Trees

前面我们从零开始了解了LSM-Tree的核心原理,但是在数据库领域使用最广泛的索引结构是B-tree及其变种。

其实之前我们为最简单的数据库增加索引的时候,如果我们同时希望提高查询性能,支持原地更新和删除,支持Point query和Scan query, 保持高效的插入性能,我们就会比较自然的想到二叉查找树, 平衡二叉查找树,红黑树,B-Tree 及其最常见的变种B+Tree等树结构, 如果再考虑到面向磁盘,以及更好地支持Scan query,我们就会选择B+Tree。B+Tree具有较低的深度,这样就减少了磁盘 Seek操作的次数。

类似LSM-Tree,B-Tree也可以提供高效地Point query和Scan query。 但是两者的设计哲学是完全不同的:LSM-Tree是将数据拆分为几百M大小的Segments,并是顺序写入;B-Tree则是面向磁盘,将数据拆分为固定大小的Block或Page, 一般是4KB大小,和磁盘一个扇区的大小对应,Page是读写的最小单位。

屏幕快照 2018-05-01 下午6.43.19.png-310kB

在数据的更新和删除方面,B-Tree可以做到原地更新和删除,但由于LSM-Tree只能追加写,所以只能在Segment Compaction的时候进行真正地更新和删除。

大家可以通过B+Tree 可视化理解B+Tree的插入,查找,更新和删除过程。

关于B+Tree更详细的原理可以参考此文MySQL索引背后的数据结构及算法原理

8 B-Tree VS LSM-Tree

一般而言, LSM-tree的写更加高效(追加顺序写),B-tree的读更加高效(LSM-tree需要访问几个不同的数据结构)。

LSM-Tree的优点:

  1. 高吞吐的写
  2. 可以高效的压缩,更节省磁盘(B-Tree一般会为Page的分裂预留一些空间)

LSM-Tree的缺点:

  1. Compaction会影响正常数据的读写。 阿里为了优化这个问题,X-DB的Compaction使用了FPGA来进行。
  2. 数据量越大,Compaction需要的磁盘带宽就越多。
  3. B-Tree中一个Key只会出现在一个Page,但是LSM-tree中一个key可能出现在多个Segment,所以B-Tree实现事务更加简单。

9 参考资料

1《Designing-Data-Intensive-Applications》第3章的第一部分《Data Structures That Power Your Database》

2 计算机底层知识拾遗(三)理解磁盘的机制 第6部分磁盘简介参考

3 磁盘I/O那些事 第6部分磁盘简介参考


DorisDB —— 新一代极速 MPP 分析型数据库

DorisDB 是由 Apache Doris 核心研发团队打造的新一代企业级 OLAP 数据库,继承了 Apache Doris 项目十多年研发成果,以及数千台服务器稳定运行经验,并在此基础上,对传统 MPP 数据库进行了开创性的革新。 DorisDB 重新定义了 MPP 分布式架构,集群可扩展至数百节点,支持 PB 级数据规模,是当前唯一可以在大数据规模下进行在线弹性扩展的企业级分析型数据库。

DorisDB 打造了全新的向量化执行引擎,查询性能相比 Apache Doris 整体有5到10倍的提升,导入性能相比 Apache Doris 整体有10到30倍的提升。

如果你想和我们一起打造一款世界第一的企业级 OLAP 数据库,欢迎发送简历到 kangkaisen#dorisdb.com

如果你希望了解 DorisDB 相关问题,欢迎添加下面的微信号:

评论