最新消息:比度技术-是关注互联网技术的个人博客,大部分内容来自互联网,以作为笔记查阅。

LSM Tree和B树

编程开发 bidu 79浏览

LSM Tree(Log Structured Merge Trees)

讲LSM树之前,需要提下三种基本的存储引擎,这样才能清楚LSM树的由来:

 

哈希存储引擎  是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的复杂度都是O(1),明显比树的操作O(n)快,如果不需要有序的遍历数据,哈希表就是your Mr.Right

B树存储引擎是B树(关于B树的由来,数据结构以及应用场景可以看之前一篇博文)的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。

LSM树(Log-Structured Merge Tree)存储引擎和B树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

通过以上的分析,应该知道LSM树的由来了,LSM树的设计思想非常朴素:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,不过读取的时候稍微麻烦,需要合并磁盘中历史数据和内存中最近修改操作,所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。极端的说,基于LSM树实现的HBase的写性能比Mysql高了一个数量级,读性能低了一个数量级。

 

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

LSM数据组织方式被应用于多种数据库,如LevelDB、HBase、Cassandra等

顺序操作磁盘的性能,较随机读写磁盘的性能高很多,我们实现数据库时,也是围绕磁盘的这点特性进行设计与优化。如果让写性能最优,最佳的实现方式就是日志型(Log/Journal)数据库,其以追加(Append)的方式写磁盘文件。有得即有舍,万事万物存在权衡,带来最优写性能的同时,单纯的日志数据库读性能很差,为找到一条数据,不得不遍历数据记录,要实现范围查询(range)几乎不可能。为优化日志型数据库的读性能,实际应用中通常结合以下几种优化措施:

二分查找(Binary Search): 在一个数据文件中使用二分查找加速数据查找

哈希(Hash): 写入时通过哈希函数将数据放入不同的桶中,读取时通过哈希索引直接读取

B+树: 使用B+树作为数据组织存储形式,保持数据稳定有序

外部索引文件: 除数据本身按日志形式存储外,另对其单独建立索引加速读取

以上措施都很大程度提升了读性能(如二分查找将时间复杂度提升至O(log(N))),但相应写性能也有折损,第一写数据时需要维护索引,这视索引的实现方式,最差情况下可能涉及随机的IO操作;第二如果用B+树等结构组织数据,写入涉及两次IO操作,先要将数据读出来再写入。

LSM Tree存储结构

LSM tree存储实现思路与以上四种措施不太相同,其将随机写转化为顺序写,尽量保持日志型数据库的写性能优势,并提供相对较好的读性能。具体实现方式如下:

  1. 当有写操作(或update操作)时,写入位于内存的buffer,内存中通过某种数据结构(如skiplist)保持key有序
  2. 一般的实现也会将数据追加写到磁盘Log文件,以备必要时恢复
  3. 内存中的数据定时或按固定大小地刷到磁盘,更新操作只不断地写到内存,并不更新磁盘上已有文件
  4. 随着越来越多写操作,磁盘上积累的文件也越来越多,这些文件不可写且有序
  5. 定时对文件进行合并操作(compaction),消除冗余数据,减少文件数量。

LSM-Tree模型是全序模型(ordered key-value storage),换句话说里面的数据是按照key有序排列的;这么做的好处在于能采用类似于二分查找的方式快速定位,可以采用前缀压缩等手段进行有效数据管理;更重要的是支持前缀scan数据。这些技术特点能很好地为存储系统所扩展成更高级的应用模式(例如,表格存储系统,图存储系统等等)。但是,为了做到全序,在LSM-Tree引擎中,除了通常对外暴露的Put/Get/Scan操作外,还有一个非常重要的内部操作:Compact。Compact操作的目的是整理内部的数据,将随机写入的乱序数据整理成有序的数据排布到磁盘上。为了充分利用SATA磁道特点,在LSM-Tree引擎中,Compact会采用多路归并的方式,顺序读取多个数据文件,并归并排序顺序写入磁盘。这个多路归并过程需要额外读取的数据量和额外写入的数据量,处于用户实际读取和写入的数据量,就是读放大率和写放大率。

B+树与LSM树的区别与联系

k-v存储的核心之一—树

为什么在磁盘中要使用b+树来进行文件存储呢?原因还是因为树的高度低得缘故,磁盘本身是一个顺序读写快,随机读写慢的系统,那么如果想高效的从磁盘中找到数据,势必需要满足一个最重要的条件:减少寻道次数。

1、平衡树,可以看到基本上一个元素下只有两个子叶节点,抽象的来看,树想要达成有效查找,势必需要维持如下一种结构:树的子叶节点中,左子树一定小于等于当前节点,而当前节点的右子树则一定大于当前节点。只有这样,才能够维持全局有序,才能够进行查询。这也就决定了只有取得某一个子叶节点后,才能够根据这个节点知道他的子树的具体的值情况。这点非常之重要,因为二叉平衡树,只有两个子叶节点,所以如果想找到某个数据,他必须重复更多次“拿到一个节点的两个子节点,判断大小,再从其中一个子节点取出他的两个子节点,判断大小。”这一过程。这个过程重复的次数,就是树的高度。那么既然每个子树只有两个节点,那么N个数据的树的高度也就很容易可以算出了。平衡二叉树这种结构的好处是,没有空间浪费,不会存在空余的空间,但坏处是需要取出多个节点,且无法预测下一个节点的位置。这种取出的操作,在内存内进行的时候,速度很快,但如果到磁盘,那么就意味着大量随机寻道。基本磁盘就被查死了。而b树,因为其构建过程中引入了有序数组,从而有效的降低了树的高度,一次取出一个连续的数组,这个操作在磁盘上比取出与数组相同数量的离散数据,要便宜的多。因此磁盘上基本都是b树结构。B树在插入的时候,如果是最后一个node,那么速度非常快,因为是顺序写。但如果有更新插入删除等综合写入,最后因为需要循环利用磁盘块,所以会出现较多的随机io.大量时间消耗在磁盘寻道时间上。如果是一个运行时间很长的b树,那么几乎所有的请求,都是随机io。因为磁盘块本身已经不再连续,很难保证可以顺序读取。以上就是b树在磁盘结构中最大的问题了。那么如何能够解决这个问题呢?

目前主流的思路有以下几种:(1)放弃部分读性能,使用更加面向顺序写的树的结构来提升写性能.(2)使用SSD

2、LSM Tree采取了什么样的方式来优化这个问题呢?简单来说,就是放弃磁盘读性能来换取写的顺序性。

LSM Tree优化方式:

a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你,某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找,而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升,但付出的是空间代价。

b、compact:小树合并为大树:因为小树他性能有问题,所以要有个进程不断地将小树合并到大树上,这样大部分的老数据查询也可以直接使用log2N的方式找到,不需要再进行(N/m)*log2n的查询了

转载请注明:比度技术-关注互联网技术的个人博客 » LSM Tree和B树