HBase 篇（八）：LSM Tree
source link: https://mp.weixin.qq.com/s/oxFpCezAzxjsah3Py4bbGA?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Google的BigTable论文提到了一个很重要的东西：它所使用的文件组织方式（LSM-Tree），这个东东出自1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》。
对HBase有一定了解的同学对这个LSM一定不陌生。我们先来回忆下HBase的读写
写流程
-
向zookeeper发起请求，从ROOT表中获得META所在的region，再根据table，namespace，rowkey，去meta表中找到目标数据对应的region信息以及regionserver
-
把数据分别写到HLog和MemStore上一份，若MemStore中的数据有丢失，则可在HLog上恢复
-
当memstore数据达到阈值（默认是64M），将数据刷到硬盘，将内存中的数据删除同时删除Hlog中的历史数据。
-
当多个StoreFile文件达到一定的大小后，会触发Compact合并操作，合并为一个StoreFile，这里同时进行版本的合并和数据删除。
-
当Compact后，逐步形成越来越大的StoreFIle后，会触发Split操作，把当前的StoreFile分成两个，这里相当于把一个大的region分割成两个region
-
当hregionser宕机后，将hregionserver上的hlog拆分，然后分配给不同的hregionserver加载，修改.META.
读流程
-
首先用MemStoreScanner搜索MemStore里是否有所查的rowKey（这一步在内存中，很快），
-
同时也会用Bloom Block通过一定算法过滤掉大部分一定不包含所查rowKey的HFile，
-
上面提到在RegionServer启动的时候就会把Trailer，和Load-on-open-section里的block先后加载到内存，所以接下来会查Trailer，因为它记录了每个HFile的偏移量，可以快速排除掉剩下的部分HFile。
-
经过上面两步，剩下的就是很少一部分的HFile了，就需要根据Index Block索引数据（这部分的Block已经在内存）快速查找rowkey所在的block的位置；
-
找到block的位置后，检查这个block是否在blockCache中，在则直接去取，如果不在的话把这个block加载到blockCache进行缓存，
-
最后扫描这些读到内存中的Block（可能有多个，因为有多版本），找到对应rowKey返回需要的版本。
熟悉了HBase的读写流程后（尤其是写流程），了解lsm tree就会变得容易很多了。Log-Structured Merge-Tree中文翻译是日志结构合并树。那我们就从日志结构与合并树这两个方面来讲。
日志结构
我们知道磁盘随机读写性能是比顺序读写慢至少3个数量级的，日志的特点是 它是顺序追加写 的，可以保证非常好的写操作性能，但是从 日志文件中读一些数据将会比写操作需要更多的时间 ，需要倒序扫描，直接找到所需的内容。
因此日志适用的场景非常有限：
-
数据是被整体访问，像大部分数据库的WAL(write-ahead log)、HDFS
-
记录了文件明确的偏移量，比如Kafka
为了为更复杂的读场景（比如按key或者range）提供高效的性能，人们发明了几种方式：
二分查找: 将文件数据有序保存，使用二分查找来完成特定key的查找。
哈希：用哈希将数据分割为不同的bucket
B+树：使用B+树 或者 ISAM 等方法，可以减少外部文件的读取
外部文件： 将数据保存为日志，并创建一个hash或者查找树映射相应的文件。
所有的方法都可以有效的提高了读操作的性能（最少提供了O(log(n)) )，但是，却丢失了日志文件超好的写性能。上面这些方法，都 强加了总体的结构信息在数据上，数据被按照特定的方式放置，所以可以很快的找到特定的数据 ，但是却对写操作不友善，让写操作性能下降。更糟糕的是，当我们需要更新hash或者B+树的结构时，需要同时更新文件系统中特定的部分，这就是上面说的比较慢的随机读写操作。这种随机的操作要尽量减少。
此时，LSM 被发明了， LSM 使用一种不同于上述四种的方法，保持了日志文件写性能，以及微小的读操作性能损失。本质上就是 通过把随机写的数据写到内存，然后定期flush到磁盘，对于磁盘来说，让所有的操作顺序化，而不是随机读写。
合并树
LSM树原理把一棵大树拆分成N棵小树， 它首先写入内存中即是小树，随着小树越来越大，会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能 。
lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。
hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。
觉得有价值请关注 ▼
Recommend
-
30
-
30
06年，Google发表了BigTable论文，从此推开了大数据时代的大门。 为什么又提及BigTable，是因为这篇论文中使用了LSM这种数据结构。 LSM: Log Structured-Merge Tree(日志结构合并树)，是一种先于BigTable出现的文件组织...
-
57
-
30
LSM树(Log Structured Merged Tree)的名字往往给人一个错误的印象, 实际上LSM树并没有严格的树状结构。 LSM 树的思想是使用顺序写代替随机写来提高写性能，与此同时会略微降低读性能。 LSM 的高速写入能力与读缓存技术...
-
17
引言： 随着数据量的与日俱增，目前mysql计算能力逐渐成为了数据页面的性能瓶颈。TIDB作为一个具有分布式特征的关系型数据...
-
3
[TOC] 一、大幅度制约存储介质吞吐量的原因 首先抛出结论。无论任何存储介质（不管是机械硬盘还是SSD，抑或是内存）的顺序访问速度都远远高出随机访问的速度。
-
25
论文翻译：LSM-based storage techniques: a survey （下）本文是论文翻译的下篇，关注LSM-Tree的改进方案和代表性系统，背景基础介绍在上篇：3 LSM-tree improvements在本节中，我们提出了一种分类法，用于对改进LSM树的现有研究成果...
-
0
从 RocksDB 看 LSM-Tree 算法设计原创不易，转载请注明出处目前笔者本人正在基于 Pulsar 搭建公司内部的消息平台，自然也对其底层存储做了一些研究。Puls...
-
4
1.The Log-Structured Merge-Tree 2.一文带你看透基于LSM-tree的NoSQL系统优化方向 3.
-
3
作者：金长龙爱可生测试工程师，负责DMP产品的测试工作先前在做OB存储引擎这块学习的时候，对 OceanBase 的分层转储和 SSTable 这块有些细节就懵懵的，比如L0层的 mini SSTable 的每次生成是否就计入转储次数，L0层到L...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK