专栏名称: 狗厂
目录
相关文章推荐
51好读  ›  专栏  ›  狗厂

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

狗厂  · 掘金  ·  · 2018-05-29 02:33

正文

数据库从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在文件中的Offest,假如我们知道了每个Key的Offest,我们就可以直接Seek到Key对应的Offest,直接读取Key对应的Value。而Key到Offest的映射我们自然会想起到我们熟悉的数据结构HashMap,我们可以在内存中维护一个HashMap,HashMap的Key就是Key-Value DB的每一条记录的Key,HashMap的Value就是每一条记录在文件中的Offest。

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

有了HashMap后,我们每次写数据后就必须要更新HashMap,查询数据时先从HashMap获取特定Key的Offest,再直接Seek到文件对应Offest的位置,读取数据。 事实上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







请到「今天看啥」查看全文