LSM Tree是一种对高并发写数据非常友好的键值存储模型.同时兼顾了查询效率.LSM Tree是NoSQL数据库所依赖的核心数据结构.例如BigTable HBase Cassandra TiDB等.
LSM Tree原理:
LSM Tree的有效性基于一个结论:磁盘或内存的顺序读写数据性能远高于随机读写数据性能.这个结论不仅对传统的机械硬盘成立.对SSD磁盘同样成立.
顺序读写的意思是按照文件中数据的顺序有序的进行读写操作.例如.向磁盘文件的末尾追加数据就是一种典型的顺序写操作.而随机读写则相反.它不遵循文件数据的先后顺序进行数据的读取写入.LSM Tree模型的思想就是在磁盘上用顺序读写代替随机读写.充分发挥磁盘的读写性能优势.LSM Tree模型主要包括如下几个组成部分.
1.MemTable:
MemTable是一种内存中的结构.用于保存SSTable最近更新数据.并且按照数据Key的字典序将数据有序的组织起来.LSM Tree模型并不限定MemTable的具体实现方式.只要保证数据有序 读写效率高即可.红黑树 跳跃表等数据结构都是实现MemTable的适当选择.
LSM Tree模型接收到写数据的请求后会直接在MemTable中处理.针对新增修改删除类型的写请求分别会执行不同的逻辑.
新增数据:
直接将数据插入MemTable中.
修改数据:
如果在MemTable中存在此数据Key.则直接修改.否则.将数据插入MemTable中.
删除数据:
LSM Tree模型不删除数据.而是将数据状态标记为tombstone(墓碑).表示此数据已被删除.可见.删除数据的流程与修改数据的流程类似.如果在MemTable中存在此数据Key.则将数据状态修改为tombstone.否则.将携带tombstone状态的数据插入MemTable中.
由于最近更新的数据都被保存在内存中.而内存是易失性存储.所以通常使用预写日志的方式保证数据的可靠性--在数据修改命令被提交到MemTable之前.先追加记录到磁盘上的WAL文件中.
2.Immutable MemTable:
当MemTable中存储的数据达到一定大小(默认为32MB)时.MemTable会变成只读的Immutable MemTable.后台线程将它持久化为基于磁盘的SSTable文件.为了不影响写数据请求的处理.LSM Tree会新建一个空白的Mem Table接管工作.
3.SSTable:
LSM Tree将数据持久化到磁盘后的结构称为SSTable.顾名思义.SSTable保存了基于数据Key按照字典排序后的数据集合.踏实一种持久化的 有序且不可变的键值对存储结构.数据Key Value连续的存储在SSTable文件中.同时在文件的尾部存储数据Key在文件中位置的偏移量并将其作为稀疏索引.用于提高在SSTable中查找某数据Key的速度.
当MemTable达到一定的大小后.它最终会被刷写到磁盘中变成SSTable文件.所以在不同的SSTable中可能存在相同的数据Key.对于某个特定的数据.在最新的SSTable中存储的对应记录才是它的最新值.其他SSLTable中的对应记录都是冗余数据.这会浪费存储空间.所以.LSM Tree会周期性的对SSL Table进行合并操作.通过将多个SSLTable合并为更大的SSTable来消除冗余记录.
LSM Tree使用Level划分SSTable文件.Level N的SSTable文件会经过合并操作下沉到Level N+1.Immutable MemTable被持久化成的SSTable文件处于Level0.合并操作的主要策略是Leveled Compaction Strategy(LCS).此策略保证.
1.所有Level的SSTable文件大小均一致.默认为160MB.
2.每个Level会限制此层内所有SSTable文件的总大小.层级越高.限制的阈值越大.如Level1的文件总大小为10GB.Level2的文件总大小为10GB等.
3.不仅单个SSTable的内部数据有序.而且同一Level内的SSLable之间也是有序的.
当LevelN的文件总大小达到阈值时.会触发LCS合并操作.在LevelN中选择一个SSTable和Level N+1与其数据Key有交集的SSTable进行合并.合并结果是生成若干新的SSTable.且它们各自的大小都不超过160MB.这些SSTable文件下沉到Level N+1.如果Level N+1的总文件大小也达到阈值.则继续执行同样的合并操作.直到某一层的文件总大小在限制阈值内.或者达到最后一层.
如图简单描述了合并操作过程.假设Level1的SSTable文件总大小超过阈值.那么Level1中的1个SSTable选择Level2中与它有交集的2个SSTable进行合并.生成了3个新的SSTable.
这3个SSTable被归入Level2.发现Level2的文件总和也超过阈值.于是Level2中的某个SSTable与Level3中有交集的3个SSTable继续合并操作.生成一个新的SSTable被归入Level3.如图所示.
由于Level0的SSTable文件来自Immutable MemTable.所以这些SSTable之间可能有数据Key重叠.但是经过合并操作.Level1~N每一层的SSTable之间不会有数据Key重叠了.一个数据Key在某一层至多存一次.
可以发现.层级越低.数据越新.如果某数据存在于Leve1 Level3 Level5.那么Level1是最新的.
读写数据流程:
1.将写数据信息记录到WAL文件中.
2.在MemTable中写入数据.此时就可以将响应数据返回给客户端.
3.当MemTable中存储的数据大小达到阈值时.将其变为Immutable MemTable.新的MemTable继续对外提供服务.
4.Immutable MemTable被持久化为SSTable文件.处于Level0.
5.如果Level0的SSTable文件大小达到阈值.则执行合并操作.Level0的SSTable文件逐渐下沉到Level1.
6.以此类推.如果LevelN的SSTable文件大小达到阈值.则继续通过合并操作将SSTable文件下沉到Level N+1.
在LSM Tree中查找数据时.按照数据值的新旧程度.查找顺序为MemTable Immutable MemTable Level0 SSTable.直到LevelN SSTable.LSM Tree处理客户端的读数据请求.当然也要保证读取到数据的最新值.流程如下.
1.在MemTable中查找数据.
2.如果未找到数据.则在Level0最新的SSTable文件中查找.
4.如果在Level0的所有SSTable文件中都找不到数据.则继续在Level1查找.
5.以此类推.直到在某一层找到数据.或者在最后一层也未找到数据.
语雀地址https://www.yuque.com/itbosunmianyi/xg8vfe?
《Go.》 密码：xbkk 欢迎大家访问.提意见.
