从零实现一个MVCC事务引擎：版本链、快照隔离与写冲突检测
在上一篇文章中，我们从零实现了一个协程调度器，覆盖了栈式协程、无栈协程与M:N调度。那篇文章聚焦的是并发执行模型。这一次我们把视角转向数据库的并发控制，目标是一个完整的MVCC事务引擎。
数据库的并发控制经历了三个阶段。第一阶段是锁，读写互斥，性能极差。第二阶段是读写锁，读读并发，但读写仍然互斥，写操作会阻塞所有读操作。第三阶段是MVCC（多版本并发控制），读不阻塞写，写不阻塞读，读写完全并发。MVCC是现代数据库的标配——PostgreSQL、MySQL InnoDB、Oracle、SQL Server都基于MVCC或其变体实现事务隔离。
MVCC的核心思想是：每次写入不覆盖旧数据，而是创建一个新版本。读操作根据事务开始时的快照，选择可见的版本。这样读操作永远不会被写操作阻塞，因为读的是旧版本；写操作也不会被读操作阻塞，因为写的是新版本。代价是旧版本需要保留一段时间，直到确定不再有事务需要它们。
本文用纯前端JavaScript从零实现一个完整的MVCC事务引擎，不依赖任何库。完整链路是：行版本结构 → 事务ID分配 → 快照创建 → 版本链遍历 → 可见性判断 → 写冲突检测 → 垃圾回收。最后会讨论快照隔离与可串行化隔离的差异，以及MVCC的经典异常（写偏斜）。
一、行版本结构：每条记录携带版本信息
MVCC的最小存储单元是"行版本"。与普通行不同，行版本除了数据本身，还携带两组关键的元数据：创建该版本的事务ID和删除该版本的事务ID。
class RowVersion { constructor(data, createdBy, deletedBy = null) { this.data = data; // 行数据 { col: value } this.createdBy = createdBy; // 创建此版本的事务ID this.deletedBy = deletedBy; // 删除此版本的事务ID（null表示未被删除） this.next = null; // 指向更旧的版本（版本链） } isVisible(snapshot) { // 创建事务必须已提交且不在当前快照的活跃事务集合中 if (!snapshot.isCommitted(this.createdBy)) return false; if (snapshot.isActive(this.createdBy)) return false; // 如果已被删除，删除事务必须未提交或在活跃集合中 if (this.deletedBy !== null) { if (snapshot.isCommitted(this.deletedBy) && !snapshot.isActive(this.deletedBy)) { return false; // 已被已提交的事务删除 } } return true; } }
版本链是MVCC的核心数据结构。当一行被多次修改时，旧版本不会被覆盖，而是通过next指针链接成一个链表。链表头是最新版本，链表尾是最旧版本。读取时从链表头开始遍历，找到第一个对当前快照可见的版本。
class VersionedRow { constructor() { this.head = null; // 最新版本 this.tail = null; // 最旧版本 } // 追加一个新版本到链表头 prepend(version) { version.next = this.head; this.head = version; if (this.tail === null) { this.tail = version; } } // 查找对当前快照可见的版本 findVisible(snapshot) { let current = this.head; while (current !== null) { if (current.isVisible(snapshot)) { return current; } current = current.next; } return null; // 没有可见版本（该行在快照创建时不存在） } }
这里有一个细节需要注意：版本链遍历的顺序是从新到旧。为什么？因为最新的版本最可能是可见的，从新到旧遍历可以尽早返回。如果从旧到新遍历，每次都要走到链表末尾才能确定哪个版本可见。
二、事务管理：ID分配与状态机
事务是MVCC的基本单位。每个事务有一个全局唯一的ID，以及一个状态（活跃、已提交、已回滚）。
class TransactionManager { constructor() { this.nextTxId = 1; this.transactions = new Map(); // txId -> { status, startTime, commitTime } this.activeTransactions = new Set(); } begin() { const txId = this.nextTxId++; this.transactions.set(txId, { id: txId, status: 'active', startTime: Date.now(), commitTime: null }); this.activeTransactions.add(txId); return txId; } commit(txId) { const tx = this.transactions.get(txId); if (!tx || tx.status !== 'active') { throw new Error(`事务 ${txId} 不存在或已结束`); } tx.status = 'committed'; tx.commitTime = Date.now(); this.activeTransactions.delete(txId); } rollback(txId) { const tx = this.transactions.get(txId); if (!tx || tx.status !== 'active') { throw new Error(`事务 ${txId} 不存在或已结束`); } tx.status = 'rolledback'; this.activeTransactions.delete(txId); } getStatus(txId) { const tx = this.transactions.get(txId); return tx ? tx.status : 'unknown'; } isActive(txId) { return this.activeTransactions.has(txId); } }
事务ID的分配是单调递增的。这个顺序很重要——它定义了事务之间的"先后关系"。一个事务ID更大的事务，如果它的快照包含了更小ID的事务的提交，那么它可以看到那个事务的修改。
三、快照隔离：读操作的可见性规则
快照隔离（Snapshot Isolation，SI）是MVCC最常用的隔离级别。每个事务在开始时创建一个快照，快照记录了"哪些事务已提交"和"哪些事务还在活跃"。读操作只看到快照创建时已提交的数据，看不到快照创建后提交的任何修改。
class Snapshot { constructor(txId, manager) { this.txId = txId; // 创建此快照的事务ID this.manager = manager; this.activeAtStart = new Set(manager.activeTransactions); // 快照创建时的活跃事务 this.activeAtStart.delete(txId); // 自己不算活跃 } isCommitted(txId) { const status = this.manager.getStatus(txId); return status === 'committed'; } isActive(txId) { return this.activeAtStart.has(txId); } // 判断某个事务对此快照是否可见 isVisible(txId) { // 自己创建的数据对自己可见 if (txId === this.txId) return true; // 快照创建时活跃的事务，其提交对快照不可见 if (this.activeAtStart.has(txId)) return false; // 其他已提交事务可见 return this.isCommitted(txId); } }
这个可见性判断规则是MVCC的精髓。核心逻辑是：快照创建时活跃的事务，无论它们后来是否提交，对当前快照都不可见。这是因为快照创建时这些事务还没完成，它们的结果不属于快照的"时间点"。
考虑一个场景：事务A（ID=1）和事务B（ID=2）同时开始。事务A先提交，事务B后提交。事务C（ID=3）在A提交后、B提交前开始。
-
事务C的快照：activeAtStart = {B}（因为B还在活跃）
-
事务C读A的数据：A已提交且不在activeAtStart中，可见
-
事务C读B的数据：B在activeAtStart中，不可见（即使B后来提交了）
这就是快照隔离的语义——每个事务看到的是一个一致的快照，快照之间是隔离的。
四、版本可见性判断的完整实现
将行版本的可见性判断和事务的快照结合起来，就得到了完整的读取路径：
class MVCCEngine { constructor() { this.txManager = new TransactionManager(); this.tables = new Map(); // tableName -> Map<primaryKey, VersionedRow> this.indexes = new Map(); // tableName -> Map<indexName, Map<key, Set<primaryKey>>> } beginTransaction() { const txId = this.txManager.begin(); const snapshot = new Snapshot(txId, this.txManager); return { txId, snapshot }; } read(tx, tableName, primaryKey) { const table = this.tables.get(tableName); if (!table) return null; const versionedRow = table.get(primaryKey); if (!versionedRow) return null; const visible = versionedRow.findVisible(tx.snapshot); if (!visible) return null; return { ...visible.data }; } // 范围扫描 scan(tx, tableName, predicate) { const table = this.tables.get(tableName); if (!table) return []; const results = []; for (const [key, versionedRow] of table.entries()) { const visible = versionedRow.findVisible(tx.snapshot); if (visible && predicate(visible.data)) { results.push({ key, ...visible.data }); } } return results; } }
read方法的逻辑是：找到主键对应的版本链，从新到旧遍历，返回第一个对当前快照可见的版本。如果没有可见版本，说明该行在快照创建时不存在（或已被删除）。
scan方法对每一行执行相同的可见性判断，然后应用谓词过滤。这个实现是O(N)的——遍历所有行。生产级实现会用B+树索引加速范围扫描，但核心的可见性判断逻辑是一样的。
五、写操作：新版本创建与写冲突检测
写操作比读操作复杂得多，因为需要处理并发写的冲突。MVCC使用写冲突检测来保证一致性——如果两个并发事务修改了同一行，后提交的事务必须回滚。
class MVCCEngine { // ... 之前的代码 write(tx, tableName, primaryKey, data) { if (!this.tables.has(tableName)) { this.tables.set(tableName, new Map()); } const table = this.tables.get(tableName); let versionedRow = table.get(primaryKey); if (versionedRow === null || versionedRow === undefined) { // 插入新行：创建第一个版本 versionedRow = new VersionedRow(); versionedRow.prepend(new RowVersion(data, tx.txId, null)); table.set(primaryKey, versionedRow); } else { // 更新已有行：检查写冲突 const latest = versionedRow.head; // 如果最新版本已经被另一个活跃事务修改，产生写冲突 if (this._hasWriteConflict(tx, versionedRow)) { throw new Error(`写冲突: 行 ${primaryKey} 已被并发事务修改`); } // 标记旧版本为已删除 latest.deletedBy = tx.txId; // 创建新版本 versionedRow.prepend(new RowVersion(data, tx.txId, null)); } // 记录本事务修改过的行，用于提交时验证 tx.writeSet.add(`${tableName}:${primaryKey}`); } _hasWriteConflict(tx, versionedRow) { let current = versionedRow.head; while (current !== null) { // 如果最新版本的创建者是另一个活跃事务，冲突 if (current.createdBy !== tx.txId && this.txManager.isActive(current.createdBy)) { return true; } // 只检查最新版本，不检查更旧的版本 break; } return false; } delete(tx, tableName, primaryKey) { const table = this.tables.get(tableName); if (!table) return; const versionedRow = table.get(primaryKey); if (!versionedRow) return; const visible = versionedRow.findVisible(tx.snapshot); if (!visible) return; if (this._hasWriteConflict(tx, versionedRow)) { throw new Error(`写冲突: 行 ${primaryKey} 已被并发事务修改`); } // 标记为已删除（不创建新版本） visible.deletedBy = tx.txId; tx.writeSet.add(`${tableName}:${primaryKey}`); } }
写冲突检测的逻辑是：检查版本链的最新版本是否由另一个活跃事务创建。如果是，说明两个事务在并发修改同一行，产生冲突。后写入的事务需要回滚或重试。
这种"首次写入者获胜"的策略被称为First-Writer-Wins。它的优点是实现简单、无死锁（不需要等待锁）。缺点是并发冲突时事务会失败，应用层需要重试。
写操作的另一个关键点是：修改已有行时，旧版本的deletedBy被设置为当前事务ID，新版本被插入链表头。这意味着旧版本并没有被真正删除，只是被标记为"被当前事务删除"。如果当前事务回滚，这个标记需要被撤销。
class MVCCEngine { // ... 之前的代码 commit(tx) { // 提交前再次检查写冲突（乐观并发控制） for (const key of tx.writeSet) { const [tableName, primaryKey] = key.split(':'); const versionedRow = this.tables.get(tableName)?.get(primaryKey); if (versionedRow && this._hasWriteConflict(tx, versionedRow)) { throw new Error(`提交冲突: ${key} 已被并发事务修改`); } } this.txManager.commit(tx.txId); } rollback(tx) { // 回滚：撤销本事务的所有修改 for (const key of tx.writeSet) { const [tableName, primaryKey] = key.split(':'); const versionedRow = this.tables.get(tableName)?.get(primaryKey); if (!versionedRow) continue; // 如果最新版本是本事务创建的，移除它 if (versionedRow.head.createdBy === tx.txId) { versionedRow.head = versionedRow.head.next; if (versionedRow.head === null) { this.tables.get(tableName).delete(primaryKey); } } // 如果旧版本被本事务标记为删除，撤销标记 let current = versionedRow.head; while (current !== null) { if (current.deletedBy === tx.txId) { current.deletedBy = null; } current = current.next; } } this.txManager.rollback(tx.txId); } }
回滚操作比提交复杂，因为需要同时处理两种情况：本事务创建的新版本需要被移除，本事务标记的删除需要被撤销。
六、垃圾回收：旧版本清理策略
MVCC的代价是旧版本会持续累积，占用存储空间。如果没有垃圾回收机制，数据库会不断膨胀。垃圾回收的目标是：删除那些"不再可能被任何活跃事务看到"的旧版本。
判断一个旧版本是否可以回收的标准是：所有活跃事务的快照中，该版本都不可见。换句话说，如果该版本的创建事务ID小于所有活跃事务的最小快照，且该版本的删除事务ID也小于最小快照，那么它就可以被安全回收。
class GarbageCollector { constructor(engine) { this.engine = engine; } collect() { const manager = this.engine.txManager; // 找到最小的活跃事务ID let minActiveTxId = Infinity; for (const txId of manager.activeTransactions) { if (txId < minActiveTxId) minActiveTxId = txId; } if (minActiveTxId === Infinity) { // 没有活跃事务，可以回收所有已提交事务的旧版本 minActiveTxId = manager.nextTxId; } let collected = 0; for (const [tableName, table] of this.engine.tables) { for (const [primaryKey, versionedRow] of table) { // 从链表头开始，保留第一个对最小快照可见的版本 // 之后的所有版本都可以回收 // 找到需要保留的版本 let keep = versionedRow.head; let current = versionedRow.head; // 跳过所有已提交事务创建的版本，找到最旧的"仍然可能可见"的版本 while (current !== null) { if (current.createdBy >= minActiveTxId) { // 这个版本可能被某些活跃事务看到 keep = current; break; } current = current.next; } // 回收 keep 之后的所有版本 if (keep !== null) { let toDelete = keep.next; keep.next = null; versionedRow.tail = keep; while (toDelete !== null) { const next = toDelete.next; toDelete.next = null; toDelete = next; collected++; } } } } return collected; } }
垃圾回收的时机很关键。太频繁会浪费CPU，太稀疏会占用大量存储。生产级实现通常由后台进程周期性执行，或在前台事务提交时触发增量回收。
七、隔离级别的差异：快照隔离 vs 可串行化
快照隔离解决了脏读、不可重复读和幻读，但它不是可串行化的。快照隔离有一个著名的异常：写偏斜（Write Skew）。
考虑一个场景：一个会议室预订系统，规则是"同一时间段至少留一个空闲会议室"。有两个会议室A和B。初始状态是两个都空闲。
事务T1：读A和B，发现都空闲。决定预订A。
事务T2：读A和B，发现都空闲。决定预订B。
两个事务的快照都看到A和B空闲。T1修改A，T2修改B。两者修改的是不同的行，没有写冲突。两个事务都提交成功。
结果：A和B都被预订了，违反了"至少留一个空闲"的约束。
写偏斜的本质是：两个事务读取了重叠的数据集，但写入了不重叠的数据集。快照隔离只检测写写冲突，不检测读写冲突（读到的数据是否被其他事务修改）。
可串行化隔离（Serializable Isolation）解决了这个问题。实现可串行化的方式主要有两种：
严格两阶段锁（Strict 2PL） ：读操作加读锁，写操作加写锁，事务结束时才释放锁。这保证了可串行化，但并发度低。
可串行化快照隔离（SSI） ：在快照隔离的基础上，检测读写冲突（一个事务读了另一个事务修改的数据）。如果发现冲突，回滚其中一个事务。
SSI的核心是跟踪每个事务的读集和写集，在提交时检查是否存在"危险结构"——即一个事务读了旧版本，而另一个事务写了新版本。如果存在，则其中一个事务必须回滚。
八、完整测试：并发场景验证
把所有部分串联起来，测试几个关键场景：
function testMVCC() { const engine = new MVCCEngine(); // 场景1：基本读写 console.log('=== 场景1：基本读写 ==='); const tx1 = engine.beginTransaction(); engine.write(tx1, 'users', 1, { name: 'Alice', age: 30 }); engine.commit(tx1); const tx2 = engine.beginTransaction(); console.log(engine.read(tx2, 'users', 1)); // { name: 'Alice', age: 30 } engine.commit(tx2); // 场景2：快照隔离 console.log('\n=== 场景2：快照隔离 ==='); const tx3 = engine.beginTransaction(); console.log('tx3 初始读:', engine.read(tx3, 'users', 1)); // Alice, 30 const tx4 = engine.beginTransaction(); engine.write(tx4, 'users', 1, { name: 'Alice', age: 31 }); engine.commit(tx4); console.log('tx3 再次读:', engine.read(tx3, 'users', 1)); // 仍然是 Alice, 30 console.log('tx4 提交后新事务读:', engine.read(engine.beginTransaction(), 'users', 1)); // Alice, 31 engine.commit(tx3); // 场景3：写冲突 console.log('\n=== 场景3：写冲突 ==='); const tx5 = engine.beginTransaction(); const tx6 = engine.beginTransaction(); engine.write(tx5, 'users', 2, { name: 'Bob', age: 25 }); try { engine.write(tx6, 'users', 2, { name: 'Bob', age: 26 }); } catch (e) { console.log('捕获写冲突:', e.message); } engine.commit(tx5); engine.rollback(tx6); // 场景4：垃圾回收 console.log('\n=== 场景4：垃圾回收 ==='); const gc = new GarbageCollector(engine); const collected = gc.collect(); console.log(`回收了 ${collected} 个旧版本`); } testMVCC();
九、性能分析与优化方向
MVCC的性能瓶颈主要有三个：
版本链遍历。如果一行被修改了N次，读取时需要遍历版本链找到可见版本。最坏情况是O(N)。优化方向是在版本链上维护索引，或者使用时间戳排序的数组代替链表。
垃圾回收的停顿。全量垃圾回收需要遍历所有表的所有行，可能造成长时间停顿。优化方向是增量回收——每次事务提交时回收一部分旧版本，把停顿分散到多个小周期中。
写冲突检测的开销。每次写入都需要检查版本链的最新版本。优化方向是维护一个活跃事务的写集，在冲突检测时直接比对写集，而不是遍历版本链。
在PostgreSQL中，MVCC的实现与我们这里的模型有重要差异。PostgreSQL将旧版本存储在同一个表中（通过xmin和xmax系统列标记），而不是维护独立的版本链。这被称为"原地更新"（in-place update）模型。读取时通过xmin和xmax判断可见性，不需要遍历链表。代价是表会膨胀，需要VACUUM进程定期清理。
十、总结
从行版本结构到事务管理，从快照创建到可见性判断，从写冲突检测到垃圾回收——这个MVCC事务引擎的核心代码不到400行，但覆盖了现代数据库并发控制的全部关键机制。
快照隔离的核心是"读不阻塞写，写不阻塞读"：读操作访问旧版本，写操作创建新版本，两者通过版本链和快照解耦。写冲突检测采用First-Writer-Wins策略，避免了锁等待和死锁。垃圾回收通过最小活跃事务ID判断旧版本的可回收性。
理解了这套最小内核，再去看PostgreSQL的HeapTupleHeader、InnoDB的ReadView、Oracle的SCN机制，会发现它们在设计上遵循的是同一套思路——用多版本换取并发度，用垃圾回收换取空间。差异只在工程细节：PostgreSQL用原地更新减少链表遍历，InnoDB用undo log实现回滚，Oracle用回滚段支持闪回查询。MVCC是这一切的起点。
- 点赞
- 收藏
- 关注作者
评论（0）