深圳亿天联网站建设,企企网官网,p2p网站建设广州,新媒体如何运营推广LSM Tree
LSM Tree#xff1a;Log-Structured Merge Tree#xff0c;日志结构合并树。是一种频繁写性能很高的数据结构。
LSM Tree将写入操作与合并操作分离#xff0c;数据首先写入磁盘中的日志文件#xff08;WAL#xff09;#xff0c;随后写入内存缓存#xff0c;…LSM Tree
LSM TreeLog-Structured Merge Tree日志结构合并树。是一种频繁写性能很高的数据结构。
LSM Tree将写入操作与合并操作分离数据首先写入磁盘中的日志文件WAL随后写入内存缓存内存中的数据是有序的通常使用的方式如跳表、红黑树等。内存中的数据按照策略刷新至磁盘由于内存中的数据有序存储至磁盘中的数据也是有序的相较于随机写顺序写提高了性能。磁盘中的数据根据策略进行合并删除旧的数据避免数据持续增长同时提高了查询性能。
存储结构 WAL当有新的 key-value需要写入时首先将其追加到顺序写的日志文件WAL中因为WAL中的数据与当前内存中的KV数据一致可以利用WAL文件恢复上一次程序的运行状态。当immutable memtable中的内容写入SSTable后删除WAL文件重新创建一个空的WAL文件此处根据实际情况实现memtable内存中的数据结构保证存储数据有序通常使用跳表、红黑树等leveldb中使用的跳表immutable memtable内存中的数据结构不可修改的表memtable中的key数据达到一定的阈值时memtable变为immutable memtable然后创建一个新的memtable。引入immutable memtable可以有效避免 memtable 的读写冲突竞争从而避免阻塞提高系统性能Minor Compact 将immutable memtable的数据写入磁盘的流程在Level 0生成一个新的SSTable当某个 Level 中的 SSTable 文件数量或容量达到阈值时会触发该 Level 文件和下一个 Level 文件的合并操作这个过程会生成新的SSTable文件删除旧的SSTable文件 SSTable数据持久化到磁盘后的数据结构保存的是排序后的数据。每个SSTable包含多个存储数据的文件成为segment每个segment内部是有序的由于是追加写不用的SSTable可能存在相同的key 数据写入
数据写入的流程如下
写入日志文件Write-Ahead Log, WAL
当有新的 key-value需要写入时首先将其追加到顺序写的日志文件中。这个操作称为预写日志Write-Ahead Logging用于系统崩溃时数据的还原保证了数据的一致性和可靠性。写入Memtable
将新的key-value写入内存中的数据结构数据结构通常为跳表或红黑树保证了数据的有序性。数据读取时有限读取Memtable如Memtable中存在可以迅速响应提高了读取性能。Memtable to SSTable
当内存中写入的数量达到一定的阈值时将内存中的数据写入到磁盘的SStable的segmnet中此过程写入的数据是有序的。SSTable的合并
SSTable可以根据一定的策略进行合并如时间、文件大小或其他条件合并操作过程中消除重复的key和已经删除的key生成新的SSTable文件。数据读取
查询memtable如查询不到查询mmutable memtable查询mmutable memtable如查询不到查询SSTable查询SSTable
查询SSTable时通常从最新的segment扫描扫描全部segment直至查询到对应数据。当扫描某个特定的segment时由于该segment内部的数据是有序的因此可以使用二分查找的方式在O(logn)的时间内得到查询结果。但对于二分查找来说要么一次性把数据全部读入内存要么在每次二分时都消耗一次磁盘 IO当 segment 非常大时这两种情况的代价都非常高。通常使用稀疏索引的方式优化查询策略。稀疏索引 上图为kafka利用稀疏索引查询的机制。
稀疏索引的原理是将数据切分成多个小块以多个小块作为一个单位由于数据有序性仅需将每个单位开头的数据作为索引即可。
有了稀疏索引我们可以现在索引表中利用二分法快速定位要查询的key在哪个数据块中仅从磁盘中读取这一小块数据即可获取查询结果IO代价较小。
稀疏索引虽然提高了查询性能但是当查询结果不在SSTable中时我们不得不扫描完所有的segment针对这种情况通常使用布隆过滤器解决该问题。
布隆过滤器是一种空间效率极高的算法能够快速地检测一条数据是否在数据集中存在。我们只需要在写入每条数据之前先在布隆过滤器中登记一下在查询时即可断定某条数据是否缺失。
布隆过滤器的内部依赖于哈希算法当检测某一条数据是否见过时有一定概率出现假阳性False Positive但一定不会出现假阴性False Negative。也就是说当布隆过滤器认为一条数据出现过那么该条数据很可能出现过但如果布隆过滤器认为一条数据没出现过那么该条数据一定没出现过。这种特性刚好与此处的需求相契合即检验某条数据是否缺失。文件合并
文件合并的目的主要是控制存储数据大小LSM Tree可以按照一定的策略执行文件合并合并后的旧数据会被删除合并后的新数据是有序的合并过程中会消除重复键、删除键以及更新过期键。 数据删除
LSM tree设计一个特殊的标志位称为 tombstone墓碑删除一条数据就是把它的 value 置为tombstone如上图所示在执行文件合并时被删除的数据在合并过程中被清除掉。
合并过程中如存在重复的key通常根据key的时间戳或其他合并策略决定保留哪个版本的数据。
优缺点
具有较高的写入性能和压缩存储适用于写多读少或写入速度较快的场景。通过将写入操作集中在内存和顺序写的日志文件中可以获得较高的写入吞吐量。查询性能也较好通过内存缓存和有序的SSTable文件可以快速定位和检索键值对。合并操作可能会引起较长的停顿时间对于实时性要求较高的系统可能会有影响。
总结
LSM Tree具有较高的写入性能主要通过写入内存和磁盘顺序写实现写入数据时先将数据写入内存当内存达到一定大小时将内存中的数据一次性顺序写入(flush)磁盘生成SSTable中一个segmentsegment内部数据也是有序的读取数据时先查找布隆过滤器如查询不到直接返回key不存在如存在继续查询稀疏索引表查找稀疏索引表根据查询到的范围从磁盘读取数据进而利用二分法读取获取最终结果Segment过多的情况下会导致写性能下降通过文件合并操作消除重复键、删除键以及更新过期键避免产生大量的segment文件达到了数据压缩的目的同时也提高了查询效率
参考
https://zhuanlan.zhihu.com/p/640477369
https://hzhu212.github.io/posts/2d7c5edb
https://cloud.tencent.com/developer/article/2011084
