LSM 树把前台写入成本转移到后续归并
LSM 树把一部分分散更新的成本转移到内存缓冲与后续归并。这是一种设计取舍,不是“所有磁盘操作从此完全顺序”的承诺,也不保证随机写一定胜过 B 树。真正需要回答的问题,是前台写入、后台压实、读取和保留版本,能否同时放进同一份资源预算。不能用一个没有提供数据生成器的精确耗时,替代对实际工作负载的解释。 缓冲改变工作的发生时机 RocksDB 通常把新写入放入内存表,并可同时写入预写日志。是否启用 WAL、是否同步日志,是另外的持久性选择;仅仅采用 LSM 布局,不保证每个已应答写入都能抵御断电。内存表填满后刷成不可变有序表,产生零层文件,应用则通过其他可用缓冲继续写入。日志追加、刷盘和压实也不是同一个动作。 采用分层压实时,零层文件的键范围可以重叠。更深的层通常各自组成一个有序段,但一个段可以按键范围拆为多个不重叠 SST 文件,不能理解为每层只有一个文件。查找先利用文件范围选择候选,压实则把重叠区间归并成替代文件。动态层大小配置还可能让某些中间层为空,因此不能把所有层永远填满的示意图当作运行事实。 读取仍然需要处理多个版本 同一个键的旧值可能存在于多个段中。读取要选择可见版本,而删除标记必须阻止更老的值重新出现。布隆过滤器可以排除肯定不含目标键的候选文件;返回可能存在后,仍需进一步检查。一次最终成功的查找,也能通过过滤器跳过不相关文件,再到真正包含答案的文件中读取。因此,“过滤器只帮助未命中,对命中毫无作用”并不准确。 压实通过重写数据,降低这种搜索和空间负担。分层策略与通用策略通常在写放大、读放大、空间放大之间作不同选择,但真实结果仍取决于负载、压缩、缓存和配置。统计时必须统一口径:SST 写入字节、WAL 字节、设备写入字节与应用逻辑字节不是同一种量。不写清分子分母的倍率,不能直接用来规划存储吞吐。 坏掉的样子 刷盘或压实跟不上时,不可变缓冲和零层文件可能积累,读取成本上升,引擎还可能减速或暂停前台写入。历史阻塞计数非零,不足以诊断今天的瓶颈。应同时查看最近的阻塞时间、待处理工作、文件数量、存储延迟与应用吞吐。提高阈值可能暂时推迟压力,却把更多工作留到后面,并扩大恢复时需要处理的积压。 删除不会立刻回收所有旧值。只要更低的段仍可能暴露被遮住的值,或保留快照需要相关历史,墓碑就不能随意消失。回收空间取决于压实覆盖了哪些历史,以及版本保留规则是否允许丢弃。若数据已经全部删除,活跃字节数为零,就不能再报告一个有限的“物理字节除以活跃字节”空间放大率;此时应直接报告残留字节与回收条件。 快速验证 把程序保存为 lsm_model.py,用 Python 3 执行。它明确只是标准库内存模型,展示三个刷出段和覆盖全部历史的压实。程序不会执行 RocksDB,不会创建真正 SST,不做磁盘输入输出,不模拟引擎调度,也不测延迟。打印的计数不能被重新包装成生产性能结果;示例的作用是把版本选择与墓碑删除条件具体化。 from pprint import pprint # A semantic model: sorted in-memory runs, not RocksDB or a disk benchmark. runs = [] # newest run first writes = 0 sequence = 0 def flush(operations): global writes, sequence memtable = {} for key, value in operations: sequence += 1 memtable[key] = (sequence, value) run = dict(sorted(memtable.items())) runs.insert(0, run) writes += len(run) def get(key, tables): for run in tables: if key in run: return run[key][1] # None is a tombstone: stop searching. return None flush([("a", "one"), ("b", "old")]) flush([("a", "two"), ("c", "three")]) flush([("b", None)]) assert [get(k, runs) for k in "abc"] == ["two", None, "three"] assert writes == 5 and sequence == 5 # Dropping a tombstone from only the newest run resurrects old b. unsafe = [{k: v for k, v in runs[0].items() if v[1] is not None}] + runs[1:] assert get("b", unsafe) == "old" # Merge ALL history, with no retained snapshots, before dropping tombstones. latest = {} for run in reversed(runs): latest.update(run) merged = {k: v for k, v in sorted(latest.items()) if v[1] is not None} writes += len(merged) assert [get(k, [merged]) for k in "abc"] == ["two", None, "three"] assert (len(merged), writes, sequence) == (2, 7, 5) pprint({"live_keys": list(merged), "logical_operations": sequence, "table_records_written": writes, "record_write_ratio": writes / sequence, "unsafe_partial_merge_resurrects": get("b", unsafe)}) 第一次刷出保存 a 和 b;第二次替换 a 并新增 c;第三次删除 b。跨所有段读取时得到新的 a、缺失的 b 和 c。反例刻意只从最新段移除墓碑,结果旧段中的 b 重新出现。这说明一条表面上没有业务值的删除记录,仍可能承担遮住历史版本的职责,不能因为它“看起来没用了”就局部删除。 ...