LSM-Tree

LSM-Tree是针对kv存储设计的，而MergeTree是针对列式存储设计的，虽然两者均通过后台合并操作优化存储结构，但目的不同：

• LSM-Tree的合并主要解决写入产生的碎片化问题
• MergeTree的合并则侧重优化列存压缩和查询性能
  • Clickhouse中的主键对于表中的每一行来说不是唯一的。ORDER BY和PRIMARY KEY的定义是等效的。

KV存储的简单模型（键映射到值）天然契合LSM-Tree的分层有序结构：

• 键的唯一性：LSM-Tree通过键的排序实现高效合并（Compaction）和查询，而KV存储中键的唯一性避免了复杂冲突处理。
• 值无关性：LSM-Tree对值的内容无特殊要求（可以是任意字节流），仅依赖键的顺序，这与KV存储的灵活性一致。

LSM-Tree的理论由Patrick O’Neil等人在1996年提出，但最早的工业级开源实现是LevelDB，由Google的Jeff Dean和Sanjay Ghemawat开发，并于2011年开源。

Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth (Betty) O’Neil, “The Log-Structured Merge-Tree,” patent granted to Digital Equipment Corporation, December 1993; appeared in ActaInformatica 33, pp. 351-385, June 1996.

LevelDB是由google在2011年开源的一款轻量级、持久化的键值存储库，它是基于LSM-Tree算法实现的，旨在提供高速写入、顺序读取以及高效的空间利用率。

RocksDB起源于LevelDB，它是facebook在2012年从LevelDB项目分支出去并进行深度优化和扩展后开源的。RocksDB最初是为了解决Facebook内部特定工作负载下的性能瓶颈而开发的，尤其是在处理大量数据和高度并发写入的场景中。

下图展示了LevelDB中基于LSM Tree的存储结构。LevelDB的存储包括内存数据库（MemTable）和磁盘数据库（SSTable）两部分。新增、修改、删除数据时首先会生成一条日志，追加在磁盘WAL文件（Write Ahead LOG）中，用于系统崩溃时进行数据还原，随后将操作（增删改）与数据信息编码成一条记录插入内存中的MemTable中 ，并对插入数据进行排序。MemTable是一个跳表结构（支持多步查询的有序链表），其插入时间复杂度为O(log n)，当MemTable容量达到阈值时转化为Imutable MemTable，并创建一个新的MemTable用于后续数据写入，同时后台线程将Immutable MemTable中的数据Flush到磁盘文件SSTable中。由于MemTable中数据是有序的因此SSTable文件中数据也具有有序性。

MemTable数据生成SSTable文件的过程称为Minor Compact，磁盘数据库由分层的SSTable文件存储，Level级别越高该层级的SSTable文件越旧，数据容量越大，Minor Compact过程就是将Immutable MemTable数据写入磁盘，在Level 0生成一个新的SSTable文件。

LevelDB中数据可能会存储于MemTable、Immutable MemTable、SSTable（Level 0 ~ Level n）中，并且由于是追加写的操作，同一个key可能同时存储在上述多个结构中（也就是数据重叠），只是这些Key对应的Value以及操作（增删改）不同。为了加快读取最新数据，每次数据查询时总是从新文件往旧文件查询，因此每次读取操作先查询内存数据MemTable和Immutable MemTable，若没查到则继续查找磁盘中的SSTable文件。

内存中MemTable和Immutable MemTable是跳表结构，查找时间复杂度为O(log n)，而磁盘中第0层的SSTable文件之间可能存在数据重叠的情况，因此在数据查询时需要遍历Level 0的所有SSTable文件。为了避免0层文件越来越庞大冗余影响数据读取效率以及磁盘空间利用率，当0层文件容量或数量达到一定阈值后，将通过多路归并的方式将第0层的文件合并为若干个没有重叠且有序的1层文件（因为有merge所以有抖动）。以此类推，当某个Level中的SSTable文件数量或容量达到阈值时，会触发该Level文件和下一个Level文件的合并操作，这个过程会生成新的SSTable文件删除旧的SSTable文件，这个合并操作叫做Major Compact。由于合并后Level 1 ~ Level n中文件总是不重叠且有序的，因此对于这几层可以采用二分查找的方式提升文件查询效率。

LSM-Tree适合分布式，是因为它是基于KV存储的，分片方便。

s3天然和LSM-Tree契合

可以把SSTable的数据存放到s3对象存储中

对象存储是实现存算分离的关键

LSM-Tree写数据和读数据

一般来说，数据更新写入有两种策略，即本地更新（in-place update）、异地更新（out-of-place update）。

B-Tree 是本地更新（in-place），即更新数据时直接修改原记录。比如把 <k1,v1> 改成 <k1,v4>，是在原来位置把v1直接改为v4，这样查询 k1 的值会直接返回 v4，这种方式具有很高的查询效率。由于更新没有开辟新的空间，因此具有很高的空间利用率，但代价是写放大，每一次写要先找到那个 k1的位置，再更新其v1的值，这会出现一次随机 I/O，就会导致写性能变慢。

LSM-Tree 是异地更新（out-of-place update），即更新数据时不直接修改原记录。比如把 <k1,v1> 改成 <k1,v4>，实际上并不真改，而是把<k1,v4> 另外存储在新的空间，查询时查新空间的<k1, v4>。这样写 k1 时，就不需要事先找到 k1 再更新，而是直接利用顺序 I/O 将新记录追加上去。这相比于本地更新（in-place updates）具有更好的写效率。同时，由于没有覆盖旧记录，也提高了回滚效率。但代价是具有读放大与空间放大。

LSM-tree 查找一条数据的访问顺序依次是：Memtable、Immemtable、SSTable Level 0 —> Level N，这样保证了只要找到这条数据，它一定是最新的数据，就可以立即返回给应用。

LSM-Tree 本身不直接解决分布式事务，需依赖上层协议

B树通过结构设计和锁机制原生支持事务，而LSM-Tree需依赖外部补偿方案

1. 预写日志（WAL）保证持久性

LSM-Tree在写入内存（MemTable）前，会先将操作记录到WAL（Write-Ahead Log）中。即使系统崩溃，也能通过重放WAL恢复未持久化的数据，确保事务的原子性（Atomicity）和持久性（Durability）

2. 多版本并发控制（MVCC）

   • 版本管理：LSM-Tree通过时间戳或序列号标记数据版本，读操作根据事务开始的版本号访问对应快照，避免脏读和不可重复读，实现隔离性（Isolation）
   • 内存与磁盘协同：活跃事务的数据可能存在于MemTable或未合并的SSTable中，MVCC确保读取时忽略未提交的版本

3. 两阶段提交（2PC）与分布式事务 在分布式场景（如OceanBase），LSM-Tree结合Paxos协议和优化后的2PC：

   • 协调者简化：参与者直接持久化Prepare日志，省去协调者日志写入，降低延迟
   • Paxos同步：事务日志通过多数副本确认后提交，确保跨节点事务的一致性（Consistency）

4. 合并（Compaction）中的事务处理

   • 延迟清理：删除和更新通过墓碑标记（Tombstone）和版本合并实现，Compaction时才会物理清除旧数据，避免事务执行期间的数据冲突
   • 全局有序性：合并后的SSTable按key有序组织，减少范围查询的版本检查开销

5. 锁与并发控制

   • 行级锁：写入MemTable时对key加锁，避免并发修改冲突
   • 无锁优化：部分实现（如基于PM的LSM-Tree）利用持久化内存的原子操作避免锁开销，同时通过ROR算法保证无日志的ACID

B+树不支持多线程多核执行同一个查询，LSM天然支持多核

B+树在传统实现中确实难以支持多核并行执行​​同一个查询​​，主要原因包括：

• 锁粒度问题​​：B+树的查询通常需要从根节点向下遍历，若采用锁机制（如页级锁或节点锁），多线程访问同一路径时会因锁竞争导致串行化。例如，InnoDB的B+树索引通过锁存器（latch）保护节点访问，但同一查询的线程仍需等待前一个线程释放锁
• 结构依赖​​：B+树的平衡性依赖于严格的节点分裂/合并规则，并发修改可能导致结构调整冲突。例如，插入操作可能触发从叶子节点到根节点的递归分裂，此时其他线程的查询会被阻塞
• 内存访问瓶颈​​：即使缓存了非叶子节点（如InnoDB的缓冲池），高频的共享数据访问（如根节点）仍可能成为多核争用的热点

LSM树的设计特性使其更适合多核并发查询：

• 分层存储与无锁读​​：LSM树将数据分为内存（MemTable）和磁盘（SSTable）两部分。读取时，各线程可并行查询内存中的跳表（无锁或乐观锁）和磁盘中的有序文件（只读访问），无需全局锁
• 数据分片​​：SSTable文件按层级组织且内部有序，不同线程可并行处理不同层或不同范围的数据文件。例如，LevelDB的Major Compaction可将大范围数据拆分为多个子任务并行处理
• 写入与查询分离​​：LSM树通过WAL（预写日志）和MemTable/Immutable MemTable分离写入与查询负载，减少线程竞争。查询线程只需读取静态的Immutable MemTable或SSTable，而写入由后台线程异步处理

kv模型的LSM树，根据key找value的时间复杂度是多少

单层查找的时间复杂度​:

• 内存查找（MemTable/Immutable MemTable）​
  • 数据首先在内存中的有序结构（如跳表或红黑树）中查找，时间复杂度为 ​​O(log n)​​（n为当前内存中的数据量）
• 磁盘查找（SSTable）​
  • 每个SSTable内部数据按Key有序存储，通过二分查找定位Key，时间复杂度为 ​​O(log m)​​（m为单个SSTable的条目数）
  • 若需遍历多个SSTable（如LevelDB中的分层设计），时间复杂度为：O(k × log m)​
    • ​​k​​：需要检查的SSTable数量
    • m​​：单个SSTable的平均数据量。

多层查找的时间复杂度​: ​​O(L × k × log m)​​

• L: 需要查找的层数

优化措施对复杂度的影响​

• Bloom Filter
  • 通过布隆过滤器快速判断Key是否存在于某个SSTable中，将无效SSTable的查找时间降为 ​​O(1)​​，显著减少k值
• ​​分层合并（Compaction）​
  • 定期合并SSTable以减少文件数量（尤其是Level 0的重复Key），降低k值
• 稀疏索引​
  • 在SSTable中维护索引块，减少二分查找的范围，进一步优化log m项

SSTable文件由多个逻辑块（Block）组成，每个块存储不同类型的数据，并通过索引机制实现高效查询

• Data Block​​：存储实际的键值对数据，按键有序排列。
• Filter Block​​：存储布隆过滤器（Bloom Filter）数据，用于快速判断键是否存在，避免无效磁盘IO。
• Meta Index Block​​：记录Filter Block的元信息（如偏移量和大小）。
• Index Block​​：存储所有Data Block的索引信息（如最大键、偏移量、大小）。
• Footer​​：位于文件末尾，固定48字节，存储Meta Index Block和Index Block的位置信息，以及校验魔数（Magic Number）。

上一篇 « pg常用查询 下一篇 » 问题