浅谈存储引擎

343 阅读12分钟

最近一段时间在看一些数据库内部实现的相关知识,一直想找个时间总结下,感觉学习这些知识会觉得挺有意义的,作为一个开发人员你可能不会自己被要求去实现一个数据库,不过你应该要去理解数据库的实现原理,这样你才能根据你的场景更好的优化你的应用,然后也会在针对你的应用在进行数据库选型时提供帮助。

目前的话,市面上有各种各样的数据库,有sql,nosql,newsql具体可以看我前段时间总结的一篇文章形形色色的数据库,那么他们的实现到底是怎么的?或则都是用的什么存储引擎?再然后存储引擎各自的优势,应用场景是什么,我看了一些资料,这里简单总结一下,文末提供了相关资料。

最简单的数据库

用vim 定义db shell文件,输入下变的内容,就实现一个最简单的数据库,只有set, get方法

#/bin/bash

db_set() {
  echo "$1, $2" >> databases
}

db_get() {
  grep "^$1," databases | sed -e "s/^$1,//" | tail -n 1
}

[[ -z "${1-}" ]]
case $1 in
    db_set|db_get) "$1" "${@:2}" ;;
    *);;
esac

set数据

$ ./db db_set test_key test_value
$ cat databases

test_key, test_value

get数据

$./db db_get test_key
test_value


简要分析

简要的分析一下,上边的数据库通过set方法会一直append文件到databases文件中,只要数据存储充足,对于数据库来说是顺序写入,所以性能是很高的,这块相当于是log操作,只有append。然后是get方法,每次都需要grep整个数据库文件,相当于是全表扫描,从算法的角度来分析复杂度会是O(N),随着数据文件的增加,性能会越来越低,速度会很慢。

所以为了优化存储get方法结构,我们需要额外引入一个结构,索引结构(这个先不考虑并发控制,事务,范围查询等等常见的功能),索引的详情可以看链接,简单来说它的目的是保存key和value的对应关系,就是位置对应关系,所以可以帮助我们提升查询性能,同时也会带来一些弊端,这就要求在数据插入前同时更新索引数据,保持索引数据和内容数据的一致性,会影响写入性能。正式这样的原因,数据库默认是不会开启索引的,索引创建会是很影响数据库的性能的一个指标,需要根据不同情形创建合适的索引,索引太多,会影响写入性能,索引太少,影响查询性能,所以找到一个合适的平衡点,是非常重要的,大多数情况下,索引都是需要dba和开发一起评估。

HASH索引

先用最简单索引结构来分析,hash索引,hash是一个非常基本的算法,具体可以看链接。这里列举一个主要利用hash存储引擎的数据库Bitcask官方文档详细的介绍了其实现原理,简单来说就是这个该数据库在内存中是一种hash表结构,hash结构维护key到文件存储的position,数据仅支持追加操作,所有的操作都是append增加而不更改老数据,数据文件分为新数据文件和老数据文件,老的数据文件只读不写,只有一个数据更新,及活跃数据文件。

A Log-Structured Hash Table for Fast Key/Value Data

数据结构如下:

Bitcask在内存中保存了key,value的位置关系,索引关系,key对应数据key, value保存不是实际的数据值,而是保存对应文件的相关信息,从图中可以看到是 file_id, value_sz, value_ops, tstamp,由于内存实际不保存真实数据,所有存储容量就会大大提升。

内存结构


file_id 代表保存的具体文件id

value_sz 代表value大小

value_ops 代表在文件中具体位置

tstamp 保存时间

然后还有一个点是,该数据实现的高性能是依赖于文件追加的方式,相当于LSM的数据追加,数据增加,删除,更新都是追加操作,形成新的数据版本,老的数据还是会在磁盘上,所以操作对应的io都是顺序io,不会随机访问磁盘,所以写入性能得到了保证,然后对于过期的数据,脏数据,bitcask会定期在后台进行一个merge操作,将inactive的数据清除。对于读操作就不需要过多介绍了,通过key可以直接读取到values_文件位置,性能也能得到保证。

由于所有的数据都是保存在内存,所有服务或则主机挂掉,内存中的映射关系就会丢失,所以需要将内存中的hash结构数据数据持久化到磁盘,当数据服务重新启动,会从磁盘恢复对应关系。

下图是数据文件中保存的内容

实际文件中具体记录的数据如下,包含crc校验值,key, value等。


磁盘结构


试想一下,如果上边shell数据库,精简优化,利用hash索引保存key,value映射关系,那么就能提高数据的访问速度,避免全表扫描这种操作,这也是hash索引能带来的最大优势,但是试想一下,你的数据需要保证有序性,key有一定的顺序,那么hash索引就不能解决这类问题。

LSM

引入LSM算法可以保证写入性能的情况下支持还范围排序的。

首先说一下什么是LSM算法(Log Structured-Merge Tree), 最初LSM来自于Google分布式表格系统BigTable的论文,它是bigtables的文件组织方式。目前LSM已经应用到了多种数据库领域,最简单的是LevelDB,然后是facebook针对其更改的Roskdb,后来又产生了带上Hbase, cassandra数据库,在mongdb Wired Tiger也能看到,最近也出现在了MySQL领域,已经被广泛验证的存储引擎方式。

这里我简单介绍一下该类数据库的流程(这里以leveldb结构介绍)

leveldb


LSM会维护一个内存有序的Memtable,在内存中维护这样一个有序的数据结构会很容易,像红黑树,平衡树,当有数据插入是先写入到Memtable保持平衡,有序,当Memtable到达一定大小会触发Merge操作,首先将源Memtable指针赋值给一个不可变的MemTable, 这里叫Immutalbe Memtable,然后会重新生成一个Memtable,后续的操作会新的Memtable中操作,产生的Immutalbe Memtable会持久化为.sst文件,由于数据已经是有序的了,所以持久化也会很容易。

组织结构

然后sst文件会是一种层级文件,sstable中的文件也是根据主键顺序排序的,每个文件都会记录其中记录中的最小值和最大值(查询速度会有所保证)。leveldb中manifest文件保存了每个sstable中的范围信息,和层级信息,leveldb在运行中 sstable也会进行合并,老的数据也会被清除,manifest保存了相关过程,低level的文件会合并为高level的文件。

这里想谈一下log文件,这里的log会记录写操作,就是所以写操作前必须将数据有限顺序写入到log中,然后再写入到内存中,这里你会想起数据库的redo log实现类似的事情,这里很简单,和其他标准数据库一样,为了解决内存数持久化到磁盘中可能出现的故障,如机器异常,内存故障等问题,优先顺序写入磁盘,由于这里是顺序的磁盘io,所有性能也不会有很大的顺势,可以这么说,大多数数据库为了保证数据的可靠性都肯定会有预先写log操作,当然该log也不会无限增大,大多数数据库会采用checkpoint保存一定时间数据变化。

LSM的写操作和Bitcask一样,是通过append log的方式,只是会附加一点需要保持数据在内存中有序,不过插入,更新,删除都还是顺序io,性能会有一定保证。然后后台会定期合并各个sstable,清除不必要数据。这里可能引入的一个性能瓶颈是读取性能,如果是查询一个不存在的key,会先查找Memtable,然后会查询最新的sstable文件,这里会引入一个布隆过滤器来解决该问题,简单来说他能很快的判定某数据集中是否存在某个key。

最后简单来说,在保证一定写入和读取性能的条件下,比hash index的优势在于,提供了有序的数据集,支持了范围查询。

BTREE

上边介绍的hash和lsm都不是最应用广泛的索引,btree才是应用最广泛的数据结构。

B+索引是数据库中最常见,也是使用最频繁的索引结构,下面这里可以通过一些基础数据结构来解释会好一点。

相信大家都了解过一种基础的算法,二分查找法,以有序中点为间隔,使用跳跃式的方式,能快速将一组有序的数据结构中找到需要查找的值。如在下列数组中查找到48,使用3次就可以了。

二分查找

相对应的树数据结构是二叉查找树,二叉查找树定义是,二叉查找树左边的叶子节点总是小于父节点的节点的值,右节点总是大于父节点的值。该树可以通过前序,或则中序遍历获取到有序数组数据,然后通过二叉查找获取到数据。


二叉树


有序性能提高查询效率,有序性也能给数据库带来支持像范围查询提供条件。

其次为了更好的提升查询性能,我们应该减少树的层级结构,如平衡二叉树(符合二叉树的定义,增加条件: 任何两个节点的高度差不得超过1),我们需要尽可能保证一棵树的平衡,不过保证一棵树的平衡需要带来一定的开销(通过旋转维护平衡),所以设计数据结构需要考虑查询效率,也需要考虑维护一棵树的成本。

btree,二叉树,平衡二叉树一样都是经典的数据结构。是由B tree演进而来,关于B+ tree,可以看连接详情。简单来说就是 b+树的所有节点都是按照大小顺序的保存在同一层的叶子节点上,各个叶子节点通过子节点的指针进行连接,如下图。


btree+


这里简单说一种最常用的数据库Mysql Innodb,Innodb由btree实现索引,和hash索引相比,由于有序性,所以Innodb支持范围查询,在Innodb中,有一种叫聚集索引的特殊索引,他会保存将具体的数据行内容。

Innodb是按照page的方式来管理数据,每个page对应一个节点,叶子节点保存了具体的数据,非叶子节点保存了索引信息,数据节点在b tree+ 有序,查询来讲是从根节点二分查找,查找对应的数据,如果数据不存在,就从磁盘中读取,然后更新内存数据,修改数据和前边内容一样,都会先写入日志(防止异常情况数据丢失),这里对应redo log。对应插入操作会比较复杂,这里就不分析了,简单来说就是为了保持b tree+树的平衡,会带来树的旋转和分裂,分离过程都是内存操作是非常危险的,所以也会进行也需要先写入redo log。

从这里看出,为了保持内存中树的平衡,维护btree+这样一个数据结构,需要做很多工作,性能会有一定降低,主要是插入,更新,删除都不是上边两种方式,通过append 文件,这里的插入,更新,删除,会查找到具体的内存位置,然后是磁盘位置,进行磁盘数据的更新,这回产生大量的随机IO, 写入,更新,删除,这类型的随机IO会更多。

流程

LSM和Btree由于实现原理的不同,所以不过也都有各有优缺点,LSM由于顺序写,提供更快的写入性能,Btree由于更加平衡,读取性能会更强。

总结

虽然这些年层出不穷的出现了各种数据库,但是其实很多数据库底层的存储引擎还是有很多相似性,可以看到各类存储引擎实现方式应用的场景都有一定的不同,比如hash索引更适合简单的kv存储,适合做缓存,lsm适合高并发的数据写入,btree更适合大量查询的应用场景,所以在实际应用的时候,我们需要考虑我们的应用场景,如有大量查询的场景(OLTP),像电商,就更好使用btree引擎的数据库,如mysql, oracle。需要高并发写入的场景,如IOT设备写入,用户访问日志记录等,可以使用LSM为基础实现的分布式nosql hbase,cassandra等。再然后对于简单数据操作,页面缓存,热点数据缓存,可以使用hash结构的memcache,redis等。

最后,推荐看一下leveldbboltdb的源码,代码比较少,更容易数据库实现原理。

参考文献


designing data-intensive applications

大规模分布式存储系统

MySQL技术内幕:InnoDB存储引擎

bitcask-intro

https://github.com/google/leveldb