tiny-lsm

前置

英文术语	常见中文译名	含义说明
LSM Tree	日志结构合并树 / 日志结构合并型树	一种为写入优化的分层有序存储结构，将随机写转为顺序写。
MemTable	内存表 / 内存有序表	保存在内存中的有序键值集合，用于接收写入请求。
Immutable MemTable	不可变内存表	已经写满、只读等待刷盘的内存表。
SSTable (Sorted String Table)	有序字符串表 / 有序表文件	存储在磁盘上的不可变、有序的数据文件，是 LSM 的核心持久层。
WAL (Write-Ahead Log)	预写日志 / 写前日志	确保数据落盘前的可靠性，防止断电丢失数据。
Flush	刷盘 / 刷新	将内存表（MemTable）写入磁盘形成 SSTable 的过程。
Compaction	压实 / 合并压缩 / 层级合并	将多个 SSTable 合并成新的 SSTable，删除过期或重复键。
Leveling	层级压实策略	控制每一层容量上限的合并策略（RocksDB 默认）。
Tiering	分层压实策略 / 批量合并策略	多个文件合并为更大文件后再下放到下一层。
Bloom Filter	布隆过滤器	判断 key 是否可能存在于某个 SSTable，用于加速查询。
Manifest	元数据文件 / 清单文件	记录各层 SSTable 的组织与状态，类似文件目录结构。
Write Amplification	写放大	同一数据被多次写入磁盘的效应。
Read Amplification	读放大	一次查询需访问多个文件的效应。
Space Amplification	空间放大	由于多版本与未清理数据导致的额外磁盘占用。
Key-Value Pair	键值对	存储的基本单元。
Delete Marker (Tombstone)	删除标记 / 墓碑标记	用于延迟删除数据的逻辑标记，在合并时真正清除。
Level 0, Level 1, …	第0层、第1层…	磁盘层次，每层存储不同大小的 SSTable。
Compaction Filter	压实过滤器	压实时用于决定保留或丢弃键值的逻辑。
Seek / Point Lookup	查找 / 精确查找	查找单个 key 的过程。
Range Query / Scan	范围查询 / 扫描	按顺序遍历多个键的操作。

LSM Tree（Log-Structured Merge-Tree） 用于磁盘存储的数据结构

LSM 存储结构：从原理到应用，简单聊聊

• 存储数据结构

  • B树，单节点可以包含多个键，从而降低树的高度，降低从磁盘读取数据的次数。（写入为页内更新和随机写， 不适合写密集型负载）
  • LSM Tree，写入先入内存（MemTable），再批量写磁盘；合并压缩读优化

• 一般数据结构：AVL Tree、Red-Black Tree、Heap、Graph、Hash Table

LSM优化：

• Bloom Filter：快速判断某 key 是否存在于某个 SSTable，减少不必要的磁盘查找。
• Index Block / Block Cache：缓存热点数据页，加速读请求。
• Tiered / Leveled Compaction：通过分层或分阶段合并，平衡写放大与读放大。

clangd：一个C/C++语言服务器, 其可以提供代码补全、代码跳转、代码高亮等功能。

skiplist

shared_mutex 读写锁

允许多线程同时读取数据，但只有一个线程可以写入数据。

std::shared_mutex rwMutex;
rwMutex.lock_shared();  // 获取共享锁
rwMutex.unlock_shared();  // 释放共享锁
rwMutex.lock();  // 获取独占锁
rwMutex.unlock();  // 释放独占锁

利用 shared_lock 进行优化。类似于使用 std::lock_gurad 或者 unique_lock 来锁定 std::mutex ，shared_lock 析构时可以自动进行锁的释放。shared_lock可以自动管理读锁的获取以及释放，

std::shared_lock<std::shared_mutex> lock(rwMutex);  // 自动获取和释放共享锁

代码中的一种写法是：std::shared_ptr<std::shared_lock<std::shared_mutex>> lock，通过共享指针封装shared_lock，但共享指针引用计数归零时，shared_lock 也会被析构，进而导致其中的shared_mutex 被析构。

谓词查询

因为skiplist本身是单调的，所以他也支持上层进行单调的查询。比如范围查询，单调的谓词查询。

谓词：返回 “真（true）” 或 “假（false）” 的逻辑表达式，用来描述数据必须满足的条件。

函数的返回值通常是 某一个具体的类型，比如 指针， 数，那么如果该指针、数不存在应该如何表示呢，这时可以将一个特殊的值比如 0 设定为表示空值，假如返回该值则代表值为0。

• 这样做有个缺陷是 0 本质上是一个有效的值，但用来表示空值，语义上不完整。
• 而且如果程序员不小心，可能将 0 当作非空值处理了。

可以通过cpp17引入的std::optional来改进，这可以显示区分究竟是有值还是没有：

std::optional<int> find_first_even(const std::vector<int>& nums) {
    if (num % 2 == 0) {
        return num; // 返回有值的 optional
    }
    return std::nullopt; // 未找到，返回无值
}
int main() {
    std::vector<int> vec1 = {1, 3, 5, 4};
    auto res1 = find_first_even(vec1);
    if (res1) { // 直接判断是否有值（等价于 res1.has_value()）
        std::cout << "第一个偶数：" << *res1 << std::endl; // 输出：4（可通过 * 解引用获取值）
    }
}

memtable

memtable 分为currenttable以及frozentable，这样可以通常查询多个表，以便提升并发度。

LSM的写入是追加写入，新的数据会覆盖旧的数据，因此查询时也需要按照从新到旧的顺序查询，一旦成功即可返回。

std::unique_lock 会调用模板参数类型的 lock以及unlock，

std::shared_lock会调用模板参数类型的 lock_shared 以及unlock_shared。

基类有一个方法, 派生类重写后，返回值是使用基类的返回值类型还是派生类的返回值类型。两种方法都是可行的，第二种方法涉及到返回类型协变。

class BaseIterator {
    virtual BaseIterator &operator++() = 0;
}
class HeapIterator : public BaseIterator {
    BaseIterator &operator++() override;
    //HeapIterator &operator++() override;
}

移动构造函数，传统的：

HeapIterator(std::vector<SearchItem> &&item_vec, uint64_t max_tranc_id);
//为了避免二义性，拷贝构造函数应该是如下所示。假如没有 const 以及 &，那么如果传入一个右值，可以同时匹配上下两个函数
HeapIterator(const std::vector<SearchItem> & item_vec, uint64_t max_tranc_id);

现代的：Pass-by-value and move”（按值传参并移动）

class Foo {
public:
    Foo(std::string name) : name_(std::move(name)) {}   // 👈 就这一版
private:
    std::string name_;
};

假如实际传递给Foo的参数是 右值，那么会触发string的移动构造函数，内部只需要修改指针，开销很小。

假如传递的是左值，需要触发拷贝构造函数。

在函数内部，都需要触发一次移动构造函数。

在性能上，两者几乎一样，但略有差别：

情况	双重重载（const& + &&）	Pass-by-value-and-move
传入右值（临时对象）	✅ 最快（一次移动）	✅ 一样快（一次移动）
传入左值（已有变量）	✅ 最快（一次拷贝）	⚠️ 略慢（一次拷贝 + 一次移动）
代码复杂度	❌ 需要写两份函数	✅ 简洁，易维护
可读性	中	✅ 高

for (int frist = 0, last = offsets.size(), idx = (offsets.size()) / 2;
     frist <= last; idx = (frist + last) / 2) {
}
//https://github.com/tjzhang-src/lsm/blob/main/src/block/block.cpp：get_monotony_predicate_iters

针对上述的二分查找，失败的情况下first，end指向哪里，可以分析一下，end，begin都是

最靠近目标值的位置，并分别位于目标值其前后。因为可以发现每次退出前，都会经历一次first==last的情况(可以归纳一下，所有原始的list最后都换变成 lsit为 3 或者 2 的list，而这两者都会经过first == last的一次判断才会退出)，这就导致了first 变为了 idx + 1，（或者last变为了idx -1），而另外一者不变。

小tip：下面的调试结果很奇怪：因为它不是连续内存, 而调试器必须根据指针 map 去渲染，而假设block map 尚未加载，就会导致下面的情况。

p kv.second.size()
(std::deque<long unsigned int, std::allocator<long unsigned int> >::size_type) 1
p kv.second
(std::deque<long unsigned int, std::allocator<long unsigned int> >) size=0 {}

LSM Engine

LSM Tree 的优化

BlockCache

LRU-K（Least Recently Used with K accesses）是一种基于访问频率和时间的缓存淘汰策略。相比于传统的LRU（最近最少使用），LRU-K考虑了更复杂的访问模式，能够更好地适应实际应用场景中的数据访问特性。

使用boost库时，cplusincludepath不要直接设置为boost的include文件夹，要设置为boost的include的上一层文件夹，然后这样使用#include <boost/asio.hpp>，避免boost头文件与系统库头文件冲突。

/usr/include这个路径以及默认处于搜索路径之中了，不需要再次include这个路径，否则如果遇到 include_next时，可能导致找不到对应的头文件。

compact

本项目的compact机制采用了一种混合方法，主要在第0层使用基于大小的分层压缩，而在更高层则转向分层压缩。

当磁盘中写入了大量的日志，就涉及到压缩了，如果不压缩，会导致查询效率低下，如果压缩过快，会消耗大量计算资源，在什么时候压缩就成为了一个关键问题。两种基础的压缩策略：level vs size/tier。（参考LSM Tree的Leveling 和 Tiering Compaction ）

Level compaction

每层level维护唯一一个run，每层中的所有sstable是有序的，并且每层中的sstable保存不重叠的key 区间。

Tier/Size Compaction

每一层的sstable足够了之后，将这一层的sstable 压缩后放到下一层，它能够保证每个sstable是sorted，但是不能保证每一层只有一个Run。（只能在最大的一层保证run）

如下图，leveling 中 level1 变为 level2时，会维持level2的有序并且不重叠关系。

使用Tier/Size Compaction：简单，写入高效，导致读放大。

使用leveled Compaction: 减少读放大，合并导致了写放大（Li-1层可能和Li层的 10 个 sstable都重复了，导致在写入数据时花费大量资源）

将两者结合可以实现更高效。

代码写的越简单越好，一个if 语句 假如有很多个 与、或表达式，记得将他们拆成多个 if语句（3个 判断就意味着有16种情况了，太难判断了）

布隆过滤器

用于检索一个元素是否在一个集合中。它的优点是

• 时间复杂度低，增加和查询元素的时间复杂为O(N)
• 布隆过滤器不存储元素本身

布隆过滤器的缺点：

• 有点一定的误判率

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在

布隆过滤器由一个很长的二进制向量和一系列随机映射函数组成。

Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。

增加元素

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 将计算得到的数组索引下标位置数据修改为1

查询元素

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

事务

事务（Transaction）是指一组原子性操作的执行单元，需要满足 ACID 性质。

特性	定义	技术实现	KV存储中的特殊表现
原子性 (Atomicity)	事务内的操作要么全部成功，要么全部失败，不存在中间状态。	- WAL（Write-Ahead Logging） - 两阶段提交（2PC） - 操作回滚日志	- 单键操作天然原子 - 跨键原子性需显式事务（如批量提交） - LSM-Tree依赖WAL保证崩溃恢复
一致性 (Consistency)	事务执行后数据库必须保持预设的业务规则（如唯一性、完整性约束）。即执行前后都必须是有效的。	- 关系型：外键、触发器 - 声明式约束（DDL） - 事务回滚机制	- 业务逻辑一致性需应用层实现
隔离性 (Isolation)	并发事务相互隔离，避免脏读、不可重复读、幻读。	- 锁机制（悲观锁） - MVCC（多版本并发控制） - 快照隔离（Snapshot Isolation）	- 通常采用乐观锁（版本号校验） - 全局时间戳实现快照隔离 - 弱隔离级别常见（如Read Committed）
持久性 (Durability)	事务提交后，数据永久存储，即使系统崩溃也不丢失。	- 同步刷盘（fsync） - 副本复制（Replication） - 冗余存储（如RAID）	- LSM-Tree依赖SSTable落盘 - 内存数据需通过WAL持久化 - 异步刷盘可能牺牲部分持久性（如Redis AOF）

针对写的话：

• 写操作：必须保证 “同一数据不会被两个事务同时修改并提交”（避免脏写，这是所有隔离级别都必须遵守的底线 —— 哪怕是最低的 “读未提交”，也不允许脏写）。

隔离性：

• 脏读，事务 A 读取了事务 B “未提交” 的修改。
• 不可重复读，事务过程中，当一行数据被检索两次，而两次检索的行内值不同。
• 幻读，当执行了两个相同的查询，而第二个查询返回的行集合与第一个不同时。

隔离级别	脏读(Dirty Read)	不可重复读(Non-Repeatable Read)	幻读(Phantom Read)	典型实现方案
读未提交（允许读取未提交的数据）	允许	允许	允许	- 无版本控制 - 直接读取内存最新值
读已提交（只允许读取已经提交的数据）	禁止	允许	允许	- 单版本快照 - 每次读获取最新提交版本
可重复读	禁止	禁止	允许	- 多版本快照 - 事务级版本锚定（如MySQL InnoDB的MVCC，查询一定trancid之前的信息，这样就算有新的值提交了，也不会显示），或者使用行锁。
可串行化	禁止	禁止	禁止	- 严格锁机制 - 冲突范围检测（如FoundationDB）

另一种隔离级别，Snapshot Isolation

• 事务的读操作从Committed快照中读取数据，快照时间可以是事务的第一次读操作之前的任意时间，记为StartTimestamp
• 事务准备提交时，获取一个CommitTimestamp，它需要比现存的StartTimestamp和CommitTimestamp都大
• 事务提交时进行冲突检查，如果没有其他事务在[StartTS, CommitTS]区间内提交了与自己的WriteSet有交集的数据，则本事务可以提交；这里阻止了Lost Update异常

不会出现脏读、不可重复度和幻读三种读异常。缺点是可能导致读写冲突。

Serializable Snapshot Isolation

在Multi-Version的串行图中，增加一种称之为RW依赖的边，即事务T1先写了一个版本，事务T2读了这个版本，则产生RW依赖。当这个图产生环时，则违背了Serializable。需要abort某个事务。

Write-Snapshot Isolation

提出：SI中的LostUpdate异常，不一定需要阻止WW冲突；换成RW检测，允许WW冲突，既能够阻止LostUpdate异常，同时能够实现Serializable。

如何检测RW冲突：事务读写过程中维护ReadSet，提交时检查自己的ReadSet是否被其他事务修改过

W检测会带来很多好处：

• 只读事务不需要检测冲突，它的StartTS和CommitTS一样
• 只写事务不需要检测冲突，它的ReadSet为空

其他

如果是传统的数据库（可以随意读取内存，而非lsm这种增量式的数据形式），实现 si，ssi，wsi 并不需要给相关的事务加锁以便来检测事务冲突。

si ——检测写写冲突，只需要给每一行添加一个最新的版本号。当某一行提交时，检测该版本号与当前事务开启时的版本号是否一致即可。

wsi——检测读写冲突，我读过的版本是否被某个并发事务覆盖了。读数据时，将事务A的信息记录下来，后续有事务B要往改行写入数据时，可以判断A的写集是否有效。

ssi——一个事务是否同时具有inbound RW conflict，outbound RW conflict，且事务存活时间满足条件

两种合并方式

• 大小阶梯合并（Size-Tiered），当某个桶里的文件数量达到阈值（默认 4 个），就把这个桶的所有文件合并成一个更大的文件，推到下一个大小桶。（注意限制的是文件数量，因为这种压缩方式本来写放大很小了，读放大与每层的文件数量有关，所以限制文件数量降低一点读放大）

• 层级合并（Leveled），当某层总大小超过阈值（total size > level_size_target），就触发合并，把部分数据推到下一层。（注意这种方式限制的是每层的总容量，每层容量按比例增长，这能让层级更加平衡，避免写放大失控）