企业官网建设流程全解析

ScyllaDB MVCC 设计解析：mutation_partition_v2、连续性不变量与范围墓碑表示

【免费下载链接】scylladbNoSQL data store using the Seastar framework, compatible with Apache Cassandra and Amazon DynamoDB项目地址: https://gitcode.com/GitHub_Trending/sc/scylladb

在 ScyllaDB 中，内存里的分区数据（memtable 与 row cache）需要同时支持并发读、并发写和增量驱逐（eviction），其核心机制就是 MVCC（多版本并发控制）。本文基于仓库中的设计文档 docs/dev/mvcc.md 展开，结合mutation/目录下的实际实现（partition_version.hh、mutation_partition_v2.hh、mutation_partition.hh）以及 mvcc_test.cc 中的测试用例，系统讲解mutation_partition_v2的版本链模型、驱逐规则、连续性不变量和范围墓碑（range tombstone）的紧凑表示法。读完本文，你将能够理解 ScyllaDB 如何在不阻塞读请求的前提下安全地从缓存中逐出数据、合并版本，并保证任何时刻的逻辑分区值都是正确的。

基础概念与两个分区模型

MVCC 的三个基本概念是：

• snapshot（快照）：一个只读句柄，指向某个分区版本，生命周期内其看到的分区数据不变；
• partition entry（分区条目）：对某个分区的读写主句柄；
• partition version（分区版本）：条目内部按时间从新到旧排列的版本链中的一个元素。

在 ScyllaDB 中，MVCC 的分区版本由mutation_partition_v2模型表示（见 mutation/mutation_partition_v2.hh）。它与瞬时 mutation 对象使用的mutation_partition模型不同，源于两者的设计诉求差异。mutation_partition_v2类注释中明确写道：

Like mutation_partition, but intended to be used in cache/memtable so the tradeoffs are different. This representation must be memory-efficient and must support incremental eviction of its contents.（mutation_partition_v2.hh 类头部注释）

即它：

• 针对低内存占用优化；
• 需要支持高效的增量驱逐。

两者最本质的区别在于范围墓碑（range tombstone）的表示方式：

源码印证：mutation_partition.hh 中的rows_entry类带有一个tombstone _range_tombstone成员（第 943 行附近），其注释解释了语义：“Given p is the preceding rows_entry&, this tombstone applies to the range (p.position(), position()] if continuous() and to [position(), position()] if !continuous()”，即该墓碑只作用于左侧的连续区间；若区间不连续，则仅作用于条目本身。这正是“墓碑挂在行条目上”的实现形态。

此外，当mutation_partition_v2处于 MVCC 快照内部时，其内容还必须满足一些不变量，以保证拥有该版本的快照始终一致——本文后面的章节将逐一说明。

两类快照：evictable 与 non-evictable

MVCC 快照分为两种，二者的规则在若干关键点上分叉：

• evictable 快照：其分区条目存在于cache（row cache）中，内容可以被驱逐；
• non-evictable 快照：其分区条目存在于memtable中，所有元素不可驱逐且全部区间都标记为 continuous。

分区条目的可驱逐性在创建时确定，条目只会产生相应类型的快照。这一点在 partition_version.hh 的partition_entry类注释中有对应描述：“We distinguish evictable and non-evictable partition entries. Entries which are non-evictable have all their elements non-evictable and fully continuous. Partition snapshots inherit evictability of the entry”。实现上，partition_entry提供evictable_tag标签构造器和make_evictable()静态工厂（partition_version.hh#L586-L607），mutation_partition_v2.hh中还有一个is_evictable = bool_class<class evictable_tag>标签类型贯穿apply_monotonically()等合并入口。

版本链的结构：partition_entry / partition_version / partition_snapshot

理解驱逐规则前，先明确三者的关系。partition_version.hh 文件头部用四个“场景”画出了版本链的典型形态：

Scene I. 只写： pv ── pe（单一版本，写入直接作用于 partition_entry 指向的版本） Scene II. 只读： pv ── pe ← ps（单一快照指向条目） Scene III. 读写并发： pv -- pv -- pv ^ ^ ^ pe ps ps Scene IV. 条目被逐出： pv ── pe，ps(u) 成为 unique owner

关键机制：当partition_entry指向的最新版本正被某个partition_snapshot读取时，新写入不会原地修改，而是在链表头部插入一个新版本（partition_entry::add_version()），条目指向新版本，旧快照继续指向它原来看到的版本。快照销毁时，版本被“squash”合并以压缩链长（对应partition_snapshot::merge_partition_versions()，partition_version.hh#L464-L474）。

从源码结构看，partition_version是侵入式链表节点（继承anchorless_list_base_hook<partition_version>），每个节点内嵌一个mutation_partition_v2 _partition和一个schema_ptr _schema（partition_version.hh#L195-L265）。类注释说明：“mutation_partition represents just a difference against the next one in the list. To get a single mutation_partition fully representing this version one needs to merge this one and all its successors in the list”，即逻辑分区值 = 从最新到最旧依次用apply()归约整个版本链。

Evictable 快照：驱逐时的一致性约束

独立连续性（independent-continuity）规则

驱逐一个rows_entry（记为 r1）时，需要把该行所在区间标记为“不连续”。若只有一个mutation_partition_v2，只需找到 r1 的后继 r2 并把其continuous标志置为false，表示 r1 前驱与 r2 之间的区间信息不完整。

但在多版本场景下，当rows_entry被选中驱逐时，我们只持有指向该对象的引用。为了在不定位、不更新其它版本条目的情况下完成驱逐（避免查找兄弟版本的开销），每条规则要求：每个partition_version拥有自己独立的、自包含的连续性信息，与其它版本的连续性无关；整个快照的行连续性 = 所有版本连续性集合的并集。这就是independent-continuity规则。

版本间的区间覆盖关系

不同版本中的连续区间可能重叠，evictable 与 non-evictable 快照的合并规则不同：

• evictable 快照：如果新版本中某区间被标记为 continuous，则它**覆盖（overwrite）**旧版本中该区间内的一切信息，包括范围墓碑信息；旧版本中的对应信息可以整体忽略。这样旧版本中的该区间内容可以被自由驱逐而不影响分区的逻辑值。此规则依赖information monotonicity（信息单调性，见下文）。
• non-evictable 快照：所有区间都是 continuous 的，新版本的信息不覆盖而是叠加旧版本的信息。memtable 中新版本的 range tombstone 会与所有旧版本中与之重叠的 range tombstone 合并。

“旧版本先被驱逐”（older versions are evicted first）

这条规则要求：对任一 clustering 区间 R，版本 V 中关于 R 的写信息，只能在比 V 更老的版本中 R 的信息全部被移除、且那些区间在老版本中被标记为不连续之后，才能被移除。否则会出现“看似丢失写”的现象——例如同一行存在于多个版本中，若新版本的行先被驱逐，使用最新快照的读者会读到老版本的行状态，结果就是错的。

另外，从区间 R 移除信息时，还必须把老版本中的相应区间标记为不连续；否则读者会认为该区间是完整的（快照连续性 = 各版本连续性的并集），从而返回“该行不存在”的错误结果。

实现方式：只有属于最新版本的行条目才会被移到 LRU 前端（标记为最近使用、最后驱逐），从而保证最新版本中的行在旧版本的行被驱逐之后才被驱逐。从最老版本（链尾）移除信息之所以安全，是因为有 information monotonicity 兜底。

源码印证这一 LRU 顺序约束：db/partition_snapshot_row_cursor.hh 中partition_snapshot_row_cursor::touch()的注释写道：

We cannot bring entries from non-latest versions to the front because that could result violate ordering invariant for the LRU, which states that older versions must be evicted first. Needed to keep the snapshot consistent.

并且touch()只在at_latest_version() && is_in_latest_version()时才把条目提到 LRU 前端——与设计文档的规则逐条对应。测试用例 test/boost/mvcc_test.cc 中的evict_with_consistency_check()（第 497 行）则通过“每次驱逐后验证 squashed 结果与游标视图一致”的方式，主动检验是否违反 “older versions are evicted first” 与 “information monotonicity” 规则。

Last dummy entry（末尾哑条目）

所有 evictable 快照中的分区版本，必须在position_in_partition::after_all_clustered_rows()位置持有一个 dummy entry。两个原因：

1. 让驱逐能正确地把区间标记为不连续。没有它，驱逐最后一个条目后，该键段之后的区间会被默认视为 continuous（行树中最后一个条目之后的区间默认 continuous），从而丢失“信息不完整”的语义。
2. 让版本即使没有任何行条目也能被 LRU 追踪——版本中可能只剩下墓碑和 static row，但仍有内存足迹需要参与 LRU 管理。

实现上，mutation_partition_v2::ensure_last_dummy()负责保证该哑条目存在（mutation_partition_v2.hh#L135-L137）；rows_entry的位域中专门有_last_dummy标志标记“位于 after_all_clustered_rows() 的哑条目”，注释解释其必要性：“Needed so that eviction, which can't use comparators, can check if it's dealing with it”（mutation_partition.hh#L951-L953）。测试 test/boost/mvcc_test.cc 中test_apply_to_incomplete_with_dummies也专门覆盖了哑条目场景。

Information monotonicity（信息单调性）

这是仅适用于 evictable 快照的不变量：对任意版本中给定的连续元素（行、键区间），它所反映的写集合必须包含更早版本中该元素包含的所有写。换句话说，新版本不丢写。

直接推论：

• compact（不含垃圾回收）保持信息单调性，且可以在版本内部本地完成，无需查看其它版本；
• 不允许只在某个版本中 GC 掉墓碑而不先将其应用到所有更老版本；
• 一个较新版本可以只含有一个覆盖旧版本该行所有存活单元的行墓碑——因为它取代了该行所有更早的写；但不允许较新版本对该行不含任何信息，只要存在包含该行写的更早版本。

这条规则让版本合并时可以丢弃中间版本的信息、用更晚版本的信息替代。它不适用于 non-evictable 快照，对后者执行这种操作会导致“复活”某个分区的更老元素。

Breaking continuity（打断连续性）

在任何版本打断连续性都是安全的，前提是该处没有挂任何写信息。例如，如果区间上挂着范围墓碑信息，则打断连续性并不安全。只有在它是最老版本（在所有快照中）时，才允许在携带写信息的情况下把区间标记为不连续；否则会违反 “older versions are evicted first”，把受影响区间中的旧信息暴露出来，造成写丢失的假象。

non-evictable 快照中所有版本的所有区间都标记为 continuous。

Population：版本的并发填充规则

文档给出了并发填充（population）的三条约束：

1. 版本可以被并发合并和填充；分区版本的合并不能假设没有外部修改者（mutator）存在。
2. 版本可以被并发填充和读取。
3. insertion only in latest（只向最新版本插入）规则：MVCC 版本的条目只能插入到最新版本中。读者刷新状态时依赖此规则——当迭代器未被失效时，它们假设在游标位置之前的老版本中没有新插入的条目。违反它会导致游标看到不一致的快照状态。

以及关于迭代器失效的两条：

• 插入条目不会失效迭代器；
• 修改已有条目的属性总是失效迭代器——这发生在驱逐时（可能清除游标的连续性），也发生在被抢占的版本合并重新完成后（插入 sentinel 条目）。

源码印证：合并操作mutation_partition_v2::apply_monotonically()返回stop_iteration，其注释描述了可抢占语义：“Returns stop_iteration::no if the operation was preempted before finished... some progress is always guaranteed (liveness)”（mutation_partition_v2.hh#L176-L202），并给出驱动完成的循环模板（apply_resume）。这正是“可抢占合并 + sentinel 条目 + 迭代器失效”机制的落点。

Range tombstone 表示法：记号与示例

设计文档用一套简单记号描述mutation_partition_v2中版本的内容。条目写作：

{key}

两个条目之间的键区间可标记为continuous（====）或discontinuous（----）：

{key1} ==== {key2} {key1} ---- {key2}

条目上可以挂 range tombstone 信息：

{key, range_tombstone}

挂在条目上的range_tombstone是一个tombstone对象，表示删除到该条目键（含）为止的所有写。如果前一个区间是 continuous 的，它作用于该区间；否则只作用于条目本身。

以下是各种键区间删除在mutation_partition_v2中的表示（x、y为 clustering key，t为时间戳）：

Deletion of (x, y] @ t: --- {x} === {y, t} [x, y] @ t: --- {before(x)} === {y, t} [x, y) @ t: --- {before(x)} === {before(y), t} [x] @ t: --- {x, t} [-inf, x] @ t: === {x, t} [x, +inf) @ t: --- {x, t} === {after_all_clustered_rows(), t} (x, y] @ t0 + (y, z] @ t1: --- {x} === {y, t0} === {z, t1}

注意[x, +inf)的例子用到了末尾哑条目{after_all_clustered_rows(), t}——这就是 “Last dummy entry” 规则在墓碑表示上的具体运用。

另一个重要性质：挂在“前区间为不连续”的哑条目上的 range tombstone 不携带任何删除信息（它作用于空区间，可以直接丢弃）。例如：

--- {before(x), t0} ==== {y, t1}

可以等价替换为：

--- {before(x)} ==== {y, t1}

测试用例test_range_tombstone_representation（test/boost/mvcc_test.cc 第 1490 行）正是对这一表示法的直接验证。

MVCC 下多版本 range tombstone 的合并

这一节描述如何把快照中各分区版本的信息组合成快照最终代表的单一版本。这些规则既适用于版本不再被引用后的实际合并过程（合并以减少版本数），也适用于读者的即时（on-the-fly）合并，即 partition_snapshot_row_cursor 边读边合并的路径。

non-evictable 快照：所有版本墓碑求和

对任意键区间，最终的 range tombstone 信息 = 该区间内所有版本的 range tombstone 信息之和。文档给出的例子：

v2: ============================= {5, t0} === v1: ----------- {2} === {3, t2} ============= v0: === {1, t1} =============================

产生的键区间为：

(-inf, 1), [1], (1, 2), [2], (2, 3), [3], (3, 5), [5], (5, +inf)

对区间 (2, 3)，各版本的 range tombstone 信息为：

v2: t0 v1: t2 v0: null

合并结果为 t0 + t2 + null =t2（墓碑合并取更“强”者）。所有区间合并后得到：

=== {1, t1} === {2, t0} === {3, t2} === {5, t0} ===

evictable 快照：放松规则——取最新连续区间

对 evictable 快照，同样的求和规则仍然成立，但由于有information monotonicity兜底，可以使用更放松的规则：对任意键区间，取“最新的那个 continuous 区间”的写信息即可——因为更新的连续区间已经包含了所有旧写。

information monotonicity 对填充路径的影响：为了维护该规则，当向最新版本插入一个空行条目、且它落入快照中的连续区间时，必须把该区间的 range tombstone 设置到新条目上，即使其左侧在最新版本中被标记为不连续。

源码中这条规则被逐行注释。db/partition_snapshot_row_cursor.hh 的ensure_entry_if_complete()（游标刷新时向最新版本插入“哨兵”条目）中有两处：

if (latest_i && latest_i->continuous()) { e->set_continuous(true); // See the "information monotonicity" rule. e->set_range_tombstone(latest_i->range_tombstone()); } else { // Even if the range in the latest version is not continuous, the row itself // is assumed to be complete, so it must inherit the current range tombstone. e->set_range_tombstone(range_tombstone()); }

即新条目继承最新版本条目的墓碑（注释明确写着 “See the 'information monotonicity' rule”）；即使最新版本区间不连续，行本身仍被视为完整，必须继承当前 range tombstone。测试test_ensure_in_latest_preserves_range_tombstones与test_ensure_in_latest_with_row_only_tombstone_in_older_version分别覆盖了这两条路径。

no singular tombstones（无单点墓碑）规则

最后一条规则禁止出现如下 MVCC 版本配置：较新版本中存在一个设置了 range tombstone、但区间不连续的条目，而该条目又落在某个较老版本的连续区间内，且该老区间带有更老的 range tombstone。

文档给出的反例：

v1: -------- {3, t2} -------------- v0: --- {1} ========= {7, t1} -----

此时把 v1 合并进 v0 会陷入两难：

• 不能简单地把{3, t2}移到{7, t1}之前并标记为 continuous，那样会错误地把 t2 向前扩展到{1}；
• 也不能在{3, t2}之前打断{7, t1}的连续性，因为这会丢失 t1 在键区间 (1, 3) 上的信息。若存在携带该区间信息的更老版本，这就违反了information monotonicity；对 non-evictable 快照则根本不允许打断连续性（即丢失信息）。

一种可能的解法是在{3, t2}前插入哑条目{before(3), t1}，但 ScyllaDB选择直接在更新路径上禁止这种配置，使分区版本合并代码更简单。该禁令在 mutation/mutation_partition_v2.cc 的合并逻辑中被显式检查（代码注释直接引用 “See the 'no singular tombstones' rule”）。

这条规则是自维持的：只要更新路径维护 no singular tombstones，且同时维护 older versions are evicted first，它就持续成立——因为连续性只会断在最老版本上，而那里不可能造成对 no singular tombstones 的破坏。

验证路径：如何用测试检验这些不变量

以上规则并非纯理论，仓库中的 test/boost/mvcc_test.cc 提供了成体系的回归测试，与文档各节一一对应：

其中test_eviction_with_active_reader（第 372 行）与test_apply_to_incomplete_respects_continuity（第 411 行）通过随机 mutation 生成器（random_mutation_generator）驱动，在“有活跃读快照”的前提下反复驱逐并断言逻辑值不变，是验证整套驱逐不变量最直接的入口。

小结

ScyllaDB 的 MVCC 实现是一组环环相扣的不变量体系：

1. 结构上：partition_entry持有版本链，partition_snapshot钉住某个版本，写入通过“头部新增版本”实现无锁并发（partition_version.hh）；
2. 表示上：mutation_partition_v2把范围墓碑挂在rows_entry上并与连续性标志（_continuous位域，mutation_partition.hh#L945-L955）绑定，使增量驱逐成为可能；
3. 规则上：independent-continuity、older versions are evicted first、information monotonicity、insertion only in latest、no singular tombstones 五条规则共同保证：无论驱逐、合并、并发填充以何种顺序发生，任何快照在任何时刻看到的逻辑分区值都等于“所有版本归约后的写集合”；
4. 验证上：test/boost/mvcc_test.cc中的驱逐一致性检查（每驱逐一项即校验一次）是这套不变量的自动化守门人。

理解这五条规则及其在 db/partition_snapshot_row_cursor.hh（游标刷新/填充）、mutation/mutation_partition_v2.cc（合并路径）中的落点，是深入 ScyllaDB 内存层（row cache 驱逐、memtable 应用、版本合并、schema upgrade）的必读前提——后者同样复用了这套 MVCC 机制，见 partition_version.hh 文件头部关于 schema upgrade 的完整说明。

【免费下载链接】scylladbNoSQL data store using the Seastar framework, compatible with Apache Cassandra and Amazon DynamoDB项目地址: https://gitcode.com/GitHub_Trending/sc/scylladb