存储引擎简介

| No Comments

存储的访问速度是根据业务场景来看,即要读取效率高,又要写入效率高,那肯定是内存的操作。但内存非常昂贵,如图1各种介质的性能和成本对比:

DiskCompareAnalyzer.jpg表1 存储介质对比

相对磁盘来说,内存非常昂贵,所以大量研究人员对存储的优化做了大量工作,并构建了很多数据结构,使得数据更快的访问。对于大数据的场景,一般常使用下面几种存储引擎方式组织数据。

1 哈希(hash)索引

Hash索引是存储常见的一种索引方式。因Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。

对于随机读取,哈希索引应该是最快的获取数据的方式,但哈希的随机写受很大的限制,对于机械磁盘,随机写会造成磁头寻道的时间更长,而对于固态硬盘,因为写放大的问题,往往写比读慢。哈希索引不适合连续读取和写入的场景,仅仅能满足"=","IN"和"<=>"查询,不能使用范围查询。

像DBM、redis等使用哈希索引加快查询、写入速度。

2 B树(B-Tree)索引

说到B树,一般会先了解一下平衡二叉树。

平衡二叉树具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。因为每个节点下最多只有两个子节点,所以想找到某个数据,必须从其中一个子节点取出他的两个子节点来判断大小,这个过程重复的次数,就是树的高度。检索时,高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

平衡二叉树结构的好处是没有空间浪费,但坏处是需要取出多个节点,且无法预测下一个节点的位置。这种取出的操作,在内存中速度很快,但若到磁盘,那么就意味着大量随机寻道,访问速度就慢死了。

B树则在其构建过程中引入了有序数组,从而有效的降低了树的高度,且一次能取出一个连续的数组,因此检索数据时,在磁盘上比取出与数组相同数量的离散数据,要快得多。因此磁盘上基本都是B树索引结构。

但B树结构与二叉树相比,会耗费更多的空间。在最恶劣的情况下,要有几乎是元数据两倍的格子才能装得下整个数据集(当B树的所有节点都进行了分裂后)。

B+树则是B树的增强版本,满足下列特征:

(1)有n棵子树的结点中含有n个关键字。

(2)所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身关键字的大小自小而大顺序链接。

(3)所有的非终端节点可以看成是索引部分,结点 中仅含有其子树(根结点)中的最大(小)关键字。

B+树通常有两个指针,一个指向根结点,另一个指向关键字最小的叶子结点。因些,对于B+树进行查找两种运算:一种是从最小关键字起顺序查找,另一种是从根结点开始,进行随机查找。如图2-1所示:

BTREE.PNG图2-1 B+树示意图

常见的是B+树索引,也是数据库技术领域常用到的加速数据查询的方式,对顺序读取和顺序写入有优势,对随机读取和随机写入的支持性也很好,机械磁盘则靠磁头寻道,故B+树索引随机读取、随机写入想对较差,而固态硬盘的随机读取想对较好,而随机写入随写入放大受到影响。

像MongoDB、mysql等,都使用B+树索引加快存储读取写入速度。

3 LSM树索引

上述提到B+树索引在随机写入的时候相对较差,怎么从数据结构上解决这个问题呢?当今使用面向顺序写的树的结构来提升写性能。一般比较流行的有COLA(Cache-Oblivious Look ahead Array)和LSM(Log-structured merge Tree)两类数据结构。这里主要说日志结构的合并(LSM)树索引。

LSM树索引其核心思想就是放弃部分读能力,换取写入的最大化能力,即若机器内存足够大,不需要一旦有数据更新就须将数据写入到磁盘中,先可以将更新的数据驻留在内存中,等到积累足够多之后,再使用归并排序的方式将内存内的数据合并追加到磁盘中。读取时需要合并磁盘中历史数据和内存中最近修改操作。

LSM树原理把一棵大树拆分成N棵小树,它首先写入内存中,随着小树越来越大,内存中的小树会flush到磁盘中,磁盘中的树定期可以做merge操作,合并成一棵大树,以优化读性能,如下图3-1:

LSM.JPG图3-1 内存和磁盘中的LSM树

另外,可以通过Bloom filter在一个小的有序结构里判断是否有那个数据,避免了二分查找。

常见的LSM树索引存储有leveldb、hbase等。

4 Bitcask

Bitcask是一种日志型键值模型。所谓日志型,指它不直接支持随机写入,是将随机写入转化为顺序写入,像日志一样支持追加操作。Bitcask有两个好处:

(1)提高随机写入的吞吐量,因为写操作不需要查找,直接追加即可。

(2)若使用固态硬盘,写入放大的问题能够有效的避免。

Bitcask中存在3种文件,包括数据文件,索引文件和线索文件(hint file, 姑且就叫线索文件吧)。

数据文件存储于磁盘上,包含了原始的数据的键值信息;数据文件以日志型只增不减的写入文件,而文件有一定的大小限制,当文件大小增加到相应的限制时,就会产生一个新的文件,老的文件将只读不写。在任意时间点,只有一个文件是可写的,在Bitcask模型中称其为active data file,而其他的已经达到限制大小的文件,称为older data file,如下图4-1:

bitcask-1.jpg图4-1 Bitcask的数据文件

文件中的数据结构非常简单,是一条一条的数据写入操作,每一条数据的结构如图4-2所示:

bitcask-2.jpg图4-2 Bitcask的数据文件结构

索引文件存在于内存,用于记录记录的位置信息,启动Bitcask时,它会将所有数据的位置信息全部读入一个内存中的哈希表,也就是索引文件;其作用是通过key值快速的定位到value的位置,如图4-3所示:

bitcask.jpg图4-3 Bitcask的数据结构

线索文件(hint file)并不是Bitcask的必需文件,如果我们不做额外的工作,那么在初始化时重建hash表时,就需要整个扫描一遍全部的数据文件,若数据文件很大,这将是一个非常耗时的过程,因此在生成一份数据文件的同时,Bitcask鼓励生成一份线索文件,这样在重建hash表时,就不需要再扫描所有数据文件,而仅仅需要将线索文件中的数据一行行读取并重建即可。极大的提高了利用数据文件重启数据库的速度。

像riak、beansdb就属于Bitcask索引结构类型。

5 跳表(Skiplist)

跳跃表是一种随机化数据结构,基于并联的链表,其效率可以比拟平衡二叉树,查找、删除、插入等操作都可以在对数期望时间内完成,对比平衡树,跳跃表的实现要简单直观很多,如下图5-1:

SKIPLIST.PNG图5-1 Skiplist数据结构

像redis中有一种数据结构叫zset,就是属于跳表。

6 总结

总在来说,存储访问是根据不同的场景去制定不同的数据结构索引,利用本身存储硬件的特性达到最优的结果。每种索引可以根据业务特点做特定的优化,形成各种各样的存储引擎。

Leave a comment

Archives

Pages

Powered by Movable Type 6.2.4

June 2016

Sun Mon Tue Wed Thu Fri Sat
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30    

Recent Assets

  • ClusterNodeAndManager.jpg
  • SampleNode.jpg
  • ClusterNode.jpg
  • SM.jpg
  • SKIPLIST.PNG
  • bitcask.jpg
  • bitcask-2.jpg
  • bitcask-1.jpg
  • LSM.JPG
  • BTREE.PNG
Creative Commons License
This blog is licensed under a Creative Commons License.

About this Entry

This page contains a single entry by Cnangel published on May 14, 2016 8:25 PM.

vim的几个问题 was the previous entry in this blog.

分布式存储的几种架构 is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.