cmu15445源码解析

发表于 | 分类于 | 次

Bustub重点解析

mvcc解析

主流程

task1: watermark

Watermark::AddTxn 事务开启的时候，记录读时间戳
Watermark::RemoveTxn 事件提交或者回滚的时候，更新watermark

task2: 重建元组 和 扫描算子

  1. 重建元组

示例 1：正常更新链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
初始版本 (t=0): {id:1, name:"Alice", age:25}
更新 (t=1): 修改 name → "Bob"    (undo_log[1])
更新 (t=2): 修改 age → 30        (undo_log[0])
当前版本: {id:1, name:"Bob", age:30}

执行 ReconstructTuple 回退到 t=0:

values = {1, "Bob", 30}, is_deleted = false

应用 undo_log[0] (age 修改):
  modified_fields_: [false, false, true]
  tuple_: [30]
  → values = {1, "Bob", 30}  (age 改回 30？不对！)

等等，这里要注意顺序：undo_logs 是从新到旧
undo_logs[0] 是 t=2 的修改 (age: 25 → 30)
undo_logs[1] 是 t=1 的修改 (name: Alice → Bob)

应用 undo_log[0] (回退 age):
  values = {1, "Bob", 25}
应用 undo_log[1] (回退 name):
  values = {1, "Alice", 25}
结果: {id:1, name:"Alice", age:25} ✅

示例 2：删除与恢复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
t=0: 插入 {id:1, name:"Alice", age:25}
t=1: 删除该行															(undo_log[1])
t=2: 重新插入 {id:1, name:"Alice", age:25}(undo_log[0])
当前版本: {id:1, name:"Alice", age:25}

执行 ReconstructTuple 回退到 t=1 (已删除):

values = {1, "Alice", 25}, is_deleted = false

应用 undo_log[0] (t=2 的插入):
  undo_log.is_deleted_ = false
  modified_fields_: [true, true, true] (完整元组)
  → 不做特殊处理，因为 values 非空
  → values = {1, "Alice", 25}

应用 undo_log[1] (t=1 的删除):
  undo_log.is_deleted_ = true
  → is_deleted = true
  → values.clear()

循环结束，is_deleted = true
返回 std::nullopt ✅

UndoLink结构体解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
当前元组 (最新版本)
    │
    │  UndoLink
    ↓
Txn 100, undo_logs_[3]  ← 上一个版本
    │
    │  UndoLink (在 UndoLog 内部)
    ↓
Txn 99, undo_logs_[7]   ← 更早版本
    │
    │  UndoLink
    ↓
Txn 98, undo_logs_[1]   ← 最老版本
    │
    │  UndoLink (IsValid() == false)
    ↓
  NULL (没有更早版本)
  1. 扫描算子
1
2
3
4
1、获取 tuple
2、获取当前行的undo log版本链
3、根据版本链获取应该显示的tuple
4、扫描的谓词过滤

task3: 增删改算子

insert
路径 1: UPDATE 路径 (rid_opt.has_value() == true)

当检测到主键冲突且需要更新时，执行以下步骤：

  1. 获取旧元组信息
1
2
3
4
auto tuple_link_info = GetTupleAndUndoLink(txn_mgr, table_info->table_.get(), rid_opt.value());
auto &tuple_meta = std::get<0>(tuple_link_info);  // 元组元数据
auto &old_tuple = std::get<1>(tuple_link_info);   // 旧元组数据
auto cur_ts = tuple_meta.ts_;                     // 当前版本的时间戳
  1. 写-写冲突检测
1
2
3
4
if (IsWriteWriteConflict(txn, cur_ts)) {
    txn->SetTainted();
    throw ExecutionException("w-w conflict");
}
  • 检查当前事务是否与持有该元组的事务存在写-写冲突
  • 如果冲突，标记事务为脏并抛出异常
  1. 处理已删除元组
1
2
3
4
auto tuple_ptr = &old_tuple;
if (tuple_meta.is_deleted_) {
    tuple_ptr = nullptr;  // 元组已被删除，视为空
}
  1. 生成或查找 Undo Link
1
2
3
4
5
6
7
auto target_undo_link = GenerateOrFindUndoLink(
    &table_info->schema_, txn_mgr, txn, 
    tuple_ptr,           // 旧元组（可能为空）
    tuple_meta.ts_,      // 旧时间戳
    new_tuple,           // 新元组
    std::get<2>(tuple_link_info)  // 原来的 undo link
);
  • 这是 MVCC 的核心：创建 undo 记录以便回滚
  • 保存旧版本信息，允许事务回滚时恢复
  1. 更新元组
1
2
3
4
5
6
7
8
9
10
11
12
auto check = [cur_ts](const TupleMeta &meta, const Tuple &tuple, RID rid, std::optional<UndoLink> undo_link) {
    return meta.ts_ == cur_ts;  // 乐观锁检查：确保元组未被其他事务修改
};
tuple_meta.is_deleted_ = false;  // 标记为未删除
tuple_meta.ts_ = txn->GetTransactionTempTs();  // 更新时间戳为当前事务的临时时间戳
auto updated = UpdateTupleAndUndoLink(txn_mgr, rid_opt.value(), target_undo_link, 
                                       table_info->table_.get(), txn,
                                       tuple_meta, *new_tuple, check);
if (!updated) {
    txn->SetTainted();
    throw ExecutionException("Update failed");
}
  • 使用乐观锁检查，确保更新是原子的
  • 如果更新失败（元组被其他事务修改），抛出异常
路径 2: INSERT 路径 (rid_opt.has_value() == false)

纯插入操作：

  1. 插入元组到表
1
2
auto tuple_meta = TupleMeta{txn->GetTransactionTempTs(), false};
rid_opt = table_info->table_->InsertTuple(tuple_meta, *new_tuple, lock_mgr, txn, table_info->oid_);
  • 创建新的元组元数据（时间戳 = 事务临时时间戳，未删除）
  • 调用表的 InsertTuple 方法分配新的 RID
  • 使用锁管理器确保并发安全
  1. 更新索引（只更新主键索引）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (const auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;  // 只处理主键索引
    }
    auto inserted = index->index_->InsertEntry(
        new_tuple->KeyFromTuple(table_info->schema_, index->key_schema_, index->index_->GetKeyAttrs()),
        rid_opt.value(), 
        txn
    );
    if (!inserted) {
        txn->SetTainted();
        throw ExecutionException("Duplicate key");
    }
}
  • 提取元组的主键值
  • 插入到 B+ 树索引中
  • 如果插入失败（重复键），抛出异常
GenerateNewUndoLog and GenerateUpdatedUndoLog
GenerateNewUndoLog
  1. INSERT 操作：base_tuple == nullptr
1
2
3
if (base_tuple == nullptr) {
    return UndoLog{true, {}, {}, ts, prev_version};
}

场景：插入新元组

  • base_tuple 为空 → 修改前没有数据
  • 返回的Undo日志：is_deleted_ = true（回滚时删除该元组）
  • modified_fields_ 和 tuple_ 为空（不需要保存旧值）

示例：

1
INSERT INTO users (id, name) VALUES (1, 'Alice');

Undo Log：{is_deleted: true, modified: [], tuple: []}
回滚时：删除RID对应的元组

  1. DELETE 操作：target_tuple == nullptr
1
2
3
4
5
6
if (target_tuple == nullptr) {
    std::vector<bool> modified_fields;
    modified_fields.resize(schema->GetColumnCount(), true);  // 所有字段都修改
    auto original_tuple = *base_tuple;  // 保存完整的旧元组
    return UndoLog{false, modified_fields, original_tuple, ts, prev_version};
}

场景：删除已有元组

  • target_tuple 为空 → 修改后数据消失
  • 标记所有字段为已修改（modified_fields 全为true）
  • 保存完整的原始元组（original_tuple）
  • is_deleted_ = false（回滚时恢复元组，不是删除）

示例：

1
DELETE FROM users WHERE id = 1;

Undo Log：{is_deleted: false, modified: [true,true,…], tuple: (1, ‘Alice’, 25)}
回滚时：在RID位置插入保存的完整元组

  1. UPDATE 操作：两者都不为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::vector<bool> modified_fields;
modified_fields.resize(schema->GetColumnCount(), false);
std::vector<Column> modified_columns;
std::vector<Value> modified_values;

for (uint32_t i = 0; i < schema->GetColumnCount(); i++) {
    // 比较每个字段的值是否变化
    if (base_tuple->GetValue(schema, i).CompareExactlyEquals(target_tuple->GetValue(schema, i))) {
        continue;  // 字段未变化，跳过
    }
    modified_fields[i] = true;
    modified_columns.push_back(schema->GetColumn(i));
    modified_values.push_back(base_tuple->GetValue(schema, i));  // 保存旧值
}

场景：更新已有元组的部分字段

  • 逐字段比较 base_tuple 和 target_tuple
  • 只记录发生变化的字段
  • 节省存储空间（只保存修改字段的旧值）

示例：

1
2
-- 假设原数据: (1, 'Alice', 25)
UPDATE users SET name = 'Bob', age = 26 WHERE id = 1;

比较结果：

  • id: 1 vs 1 → 未变化，跳过
  • name: ‘Alice’ vs ‘Bob’ → 变化，记录旧值 ‘Alice’
  • age: 25 vs 26 → 变化，记录旧值 25

Undo Log：{is_deleted: false, modified: [false, true, true], tuple: (1, ‘Alice’, 25)}

创建部分Schema

1
2
3
Schema modified_schema(modified_columns);  // 只包含被修改的列
Tuple tuple(modified_values, &modified_schema);  // 只保存被修改字段的值
return UndoLog{false, modified_fields, std::move(tuple), ts, prev_version};

4.执行流程图

1
2
3
4
5
6
7
8
9
10
11
GenerateNewUndoLog()
    ↓
base_tuple == nullptr? → 是 → INSERT: {is_deleted: true}
    ↓ 否
target_tuple == nullptr? → 是 → DELETE: {modified: 全true, tuple: 完整旧值}
    ↓ 否
UPDATE: 逐字段比较
    ↓
记录变化的字段和旧值
    ↓
返回: {modified: 仅变化字段, tuple: 仅旧值}
GenerateUpdatedUndoLog

第一部分：核心逻辑

  1. 处理已删除的元组
1
2
3
if (log.is_deleted_) {
    return log;  // 如果元组已被删除，不需要合并，直接返回
}
  1. 没有base_tuple的情况
1
2
3
if (base_tuple == nullptr) {
    return GenerateNewUndoLog(schema, &log.tuple_, target_tuple, log.ts_, log.prev_version_);
}
  • 场景：元组之前不存在，这是第一次插入
  • 行为：生成新的Undo日志，记录从”空”到”新元组”的变化
  • 回滚时，将元组删除即可
  1. 有base_tuple的情况（完整合并）

Step 1: 重建原始元组

1
2
auto original_tuple = ReconstructTuple(schema, *base_tuple, {0, false}, {log});
BUSTUB_ASSERT(original_tuple.has_value(), "Reconstructed tuple should have a value");
  • 使用当前的base_tuple和Undo log，重建修改前的原始元组
  • 这是通过应用Undo log中的修改字段来实现的

Step 2: 生成当前的变更日志

1
auto cur_log = GenerateNewUndoLog(schema, base_tuple, target_tuple, log.ts_, log.prev_version_);
  • 记录从base_tuple到target_tuple的变更
  • 即当前事务这次修改了哪些字段

Step 3: 合并两个Undo日志

1
2
3
4
5
UndoLog combined_log;
combined_log.is_deleted_ = log.is_deleted_;
combined_log.modified_fields_.resize(schema->GetColumnCount(), false);
combined_log.ts_ = log.ts_;
combined_log.prev_version_ = log.prev_version_;
  • 创建合并后的日志
  • 继承旧日志的元数据（时间戳、上一版本等）

Step 4: 合并修改字段

1
2
3
4
5
6
7
std::vector<Value> values;
for (size_t i = 0; i < schema->GetColumnCount(); i++) {
    if (cur_log.modified_fields_[i] || log.modified_fields_[i]) {
        combined_log.modified_fields_[i] = true;  // 标记该字段被修改
        values.push_back(original_tuple->GetValue(schema, i));  // 保存原始值
    }
}
  • 如果该字段在当前修改或历史修改中被修改过，标记为已修改
  • 保存该字段的原始值（用于回滚）

Step 5: 构造合并后的元组

1
2
auto temp_schema = GetUndoLogSchema(schema, combined_log);
combined_log.tuple_ = Tuple(values, &temp_schema);
  • 创建一个只包含修改字段的临时schema
  • 用保存的原始值构造元组

第二部分：可视化示例

假设表有3个字段：(id, name, age)

场景：事务T1连续修改同一个元组

1
2
3
4
5
6
7
8
9
初始状态: (1, "Alice", 25)

操作1: UPDATE SET name = "Bob"
  → 修改字段: [name]
  → Undo Log 1: {modified: [name], tuple: (Alice)}

操作2: UPDATE SET age = 30  
  → 修改字段: [age]
  → Undo Log 2: {modified: [age], tuple: (25)}

合并过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
base_tuple = 当前数据库值 (1, "Bob", 30)
target_tuple = (1, "Bob", 30)  // 已经是最终状态
log = Undo Log 2

Step 1: 重建原始元组
  original_tuple = (1, "Alice", 25)  // 从base_tuple应用Undo Log 2回退

Step 2: 生成cur_log
  cur_log = 从base_tuple到target_tuple的变更
  由于已经是相同值，cur_log.modified_fields = [所有字段为false]

Step 3: 合并
  检查字段:
  - id: 未修改 → 不标记
  - name: log.modified_fields[name]=true → 标记，保存原始值 "Alice"
  - age: log.modified_fields[age]=true → 标记，保存原始值 25

合并后的Undo Log:
  {modified: [name, age], tuple: (1, "Alice", 25)}
update and detelte
delete_executor
  1. 执行删除

阶段一：收集待删除元组并检测冲突

1
2
3
4
5
6
7
8
9
std::vector<Tuple> tuples;
while (child_executor_->Next(tuple, rid)) {
    auto tuple_meta = table_info_->table_->GetTupleMeta(*rid);
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other committed txn");
    }
    tuples.emplace_back(*tuple);
}

关键点：

  • 从子执行器（通常是 SeqScan/IndexScan）逐行读取要删除的元组
  • 对每个元组检查 写-写冲突（Write-Write Conflict）
  • 将所有待删除元组暂存到 tuples 向量中

为什么要暂存？ 为了符合 MVCC 的”先收集后操作”模式，避免在遍历过程中因为删除操作影响扫描结果。

阶段二：逐个执行删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
for (auto &tuple : tuples) {
    // 1. 获取元组的 UndoLink 信息
    auto tuple_link_info = GetTupleAndUndoLink(exec_ctx_->GetTransactionManager(), 
                                                table_info_->table_.get(), 
                                                tuple.GetRid());
    auto tuple_meta = std::get<0>(tuple_link_info);
    
    // 2. 再次检查冲突
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other committed txn");
    }
    
    // 3. 生成或查找 Undo Link
    auto target_undo_link = GenerateOrFindUndoLink(
        &table_info_->schema_, 
        exec_ctx_->GetTransactionManager(), 
        exec_ctx_->GetTransaction(),
        &tuple,           // base_tuple（旧版本）
        tuple_meta.ts_,   // 当前版本时间戳
        nullptr,          // target_tuple = nullptr 表示删除操作
        std::get<2>(tuple_link_info)  // prev_version
    );
    
    // 4. 更新元数据（标记为已删除）
    tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
    tuple_meta.is_deleted_ = true;
    
    // 5. 更新元组和 Undo Link
    auto updated = UpdateTupleAndUndoLink(exec_ctx_->GetTransactionManager(), 
                                          tuple.GetRid(), 
                                          target_undo_link,
                                          table_info_->table_.get(), 
                                          exec_ctx_->GetTransaction(), 
                                          tuple_meta, 
                                          tuple, 
                                          check);
    
    // 6. 记录写集（用于提交时验证）
    exec_ctx_->GetTransaction()->AppendWriteSet(table_info_->oid_, tuple.GetRid());
}
  1. 流程图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
开始
  │
  ├─ 初始化子执行器
  │
  ├─ 循环扫描待删除元组
  │   ├─ 检查写-写冲突
  │   └─ 暂存到 vector
  │
  ├─ 遍历每个待删除元组
  │   ├─ 获取 UndoLink 信息
  │   ├─ 生成 Undo Log（保存完整元组）
  │   ├─ 更新元数据（is_deleted_ = true, ts = temp_ts）
  │   ├─ 乐观锁更新
  │   └─ 记录事务写集
  │
  ├─ 返回删除行数
  │
  └─ 结束

  1. 删除示例

    事务 T1（txn_id = 200）执行删除：

    1
    DELETE FROM users WHERE id = 1;

    执行流程：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    1. 扫描找到 RID=101 的元组
       ├─ tuple_meta.ts_ = 100, is_deleted_ = false
       ├─ 检查写-写冲突（无冲突）
       └─ 暂存到 tuples 列表

    2. 生成 Undo Log
       ├─ base_tuple = {id:1, name:"Alice", age:25}
       ├─ target_tuple = nullptr (删除操作)
       └─ UndoLog {is_deleted_: false, modified_fields: [true,true,true], 
                   tuple: {id:1, name:"Alice", age:25}, 
                   ts: 100, prev_version: null}

    3. 更新元组元数据
       ├─ tuple_meta.ts_ = 200 (临时时间戳)
       └─ tuple_meta.is_deleted_ = true

    4. 写入写集
       └─ AppendWriteSet(table_oid, RID=101)
update_executor
  1. 核心设计思想

更新操作分为两种类型：

更新类型 处理方式 说明
主键不变 原地更新（In-place Update） 直接修改元组数据，生成 Undo Log 保存旧版本
主键变更 删除 + 插入（Delete + Insert） 先逻辑删除旧元组，再插入新元组

阶段一：收集待更新的元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<RID> tuple_rids;
std::vector<Tuple> new_tuples;

while (child_executor_->Next(tuple, rid)) {
    // 1. 检查写-写冲突
    auto tuple_meta = table_info_->table_->GetTupleMeta(*rid);
    if (IsWriteWriteConflict(exec_ctx_->GetTransaction(), tuple_meta.ts_)) {
        exec_ctx_->GetTransaction()->SetTainted();
        throw ExecutionException("w-w conflict with other txn");
    }
    
    // 2. 保存旧元组的 RID
    tuple_rids.emplace_back(*rid);
    
    // 3. 计算新元组的值（通过目标表达式）
    std::vector<Value> values;
    for (auto &expr : plan_->target_expressions_) {
        values.emplace_back(expr->Evaluate(tuple, table_info_->schema_));
    }
    new_tuples.emplace_back(Tuple(values, &table_info_->schema_));
}

关键点：

  • 先扫描所有待更新元组，暂存到 vector 中（避免遍历时数据变化影响结果）
  • 对每个元组计算新值（target_expressions_ 对应 SET 子句）
  • 检查写-写冲突

阶段二：判断主键是否变更

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool primary_key_equal = true;
for (auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;  // 只考虑主键索引
    }
    auto old_key = old_tuple.KeyFromTuple(table_info_->schema_, index->key_schema_, index->index_->GetKeyAttrs());
    auto new_key = new_tuple.KeyFromTuple(table_info_->schema_, index->key_schema_, index->index_->GetKeyAttrs());
    
    // 逐个字段比较
    for (size_t i = 0; i < index->key_schema_.GetColumnCount(); i++) {
        if (!old_key.GetValue(&index->key_schema_, i).CompareExactlyEquals(new_key.GetValue(&index->key_schema_, i))) {
            primary_key_equal = false;
            break;
        }
    }
}

示例：

sql

1
2
3
4
5
-- 主键不变（原地更新）
UPDATE users SET age = 26 WHERE id = 1;   -- id=1 不变 ✅

-- 主键变更（删除+插入）
UPDATE users SET id = 10 WHERE id = 1;    -- id 从 1 变为 10 ❌

分支一：主键不变 → 原地更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
if (primary_key_equal) {
    // 生成 Undo Log（保存旧版本数据）
    auto new_undo_link = GenerateOrFindUndoLink(
        &table_info_->schema_, 
        exec_ctx_->GetTransactionManager(), 
        exec_ctx_->GetTransaction(),
        &old_tuple,      // base_tuple = 旧元组
        tuple_meta.ts_,  // 旧版本时间戳
        &new_tuple,      // target_tuple = 新元组（更新操作）
        std::get<2>(tuple_link_info)  // prev_version
    );
    
    // 更新元组数据
    tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
    auto is_updated = UpdateTupleAndUndoLink(
        exec_ctx_->GetTransactionManager(), 
        old_tuple.GetRid(), 
        new_undo_link,
        table_info_->table_.get(), 
        exec_ctx_->GetTransaction(), 
        tuple_meta, 
        new_tuple,  // 新数据写入
        check
    );
    
    // 记录写集
    exec_ctx_->GetTransaction()->AppendWriteSet(table_info_->oid_, tuple_rids[i]);
    updated[i] = true;
    continue;
}

Undo Log 生成：

1
2
3
4
5
6
7
8
9
10
11
12
13
// GenerateNewUndoLog 中的更新路径
if (base_tuple != nullptr && target_tuple != nullptr) {
    // 只记录修改的字段
    for (uint32_t i = 0; i < schema->GetColumnCount(); i++) {
        if (base_tuple->GetValue(schema, i).CompareExactlyEquals(target_tuple->GetValue(schema, i))) {
            continue;  // 未修改的字段不记录
        }
        modified_fields[i] = true;
        modified_columns.push_back(schema->GetColumn(i));
        modified_values.push_back(base_tuple->GetValue(schema, i));  // 保存旧值
    }
    return UndoLog{false, modified_fields, modified_tuple, ts, prev_version};
}

示例数据：

操作前 操作后 Undo Log 内容
{id:1, name:"Alice", age:25} {id:1, name:"Alice", age:26} modified_fields: [F,F,T], {age:25}

分支二：主键变更 → 删除 + 插入

步骤 1：逻辑删除旧元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 生成 Undo Log（删除操作，保存完整旧元组）
auto new_undo_link = GenerateOrFindUndoLink(
    &table_info_->schema_, 
    exec_ctx_->GetTransactionManager(), 
    exec_ctx_->GetTransaction(),
    &old_tuple,      // base_tuple = 旧元组
    tuple_meta.ts_,  
    nullptr,         // target_tuple = nullptr（删除操作）
    std::get<2>(tuple_link_info)
);

// 标记为已删除
tuple_meta.ts_ = exec_ctx_->GetTransaction()->GetTransactionTempTs();
tuple_meta.is_deleted_ = true;
auto is_deleted = UpdateTupleAndUndoLink(..., tuple_meta, old_tuple, check);

步骤 2：检查新主键是否冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool key_exist = false;
std::optional<RID> rid_opt = std::nullopt;

for (auto &index : indexes) {
    if (!index->is_primary_key_) {
        continue;
    }
    auto ret = CheckKeyIfExistInIndex(&table_info_->schema_, &new_tuples[i], index.get(), 
                                       exec_ctx_->GetTransaction(), table_info_);
    if (ret.first) {
        key_exist = true;  // 新主键已被其他事务占用
        break;
    }
    if (ret.second.GetPageId() != INVALID_PAGE_ID) {
        rid_opt = ret.second;  // 找到可复用的 RID（被删除标记的元组）
    }
}

if (key_exist) {
    continue;  // 冲突则跳过，稍后重试
}

CheckKeyIfExistInIndex 的返回值：

  • ret.first = true：键冲突（已被其他事务使用）
  • ret.second：可复用的 RID（被删除标记的旧元组位置）

步骤 3：插入新元组

1
2
3
4
5
6
7
InsertTupleAndIndexKey(&new_tuples[i], 
                       exec_ctx_->GetTransactionManager(), 
                       exec_ctx_->GetTransaction(), 
                       table_info_,
                       rid_opt,  // 如果有可复用的 RID，直接使用
                       exec_ctx_->GetLockManager(), 
                       indexes);

InsertTupleAndIndexKey 的逻辑（你之前看过的）：

  • 如果 rid_opt.has_value() == true：复用被删除标记的位置（更新模式）
  • 如果 rid_opt.has_value() == false：插入到新位置（插入模式）

阶段三：处理第一次失败的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 4. try to insert for previous not updated
for (size_t i = 0; i < tuple_rids.size(); i++) {
    if (!updated[i]) {
        // 重新检查键冲突
        auto ret = CheckKeyIfExistInIndex(...);
        if (ret.first) {
            exec_ctx_->GetTransaction()->SetTainted();
            throw ExecutionException("key conflict");  // 真的冲突了
        }
        if (ret.second.GetPageId() != INVALID_PAGE_ID) {
            rid_opt = ret.second;
        }
        
        // 执行插入
        InsertTupleAndIndexKey(&new_tuples[i], ..., rid_opt, ...);
        updated[i] = true;
    }
}

为什么需要重试？

  • 第一次循环中可能遇到键冲突（key_exist = true），跳过该元组
  • 第二次循环时，其他元组的插入可能已经完成，冲突可能已解决
  • 如果仍然冲突，则抛出异常
  1. 完整执行流程图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
开始
  │
  ├─ 阶段一：收集待更新元组
  │   ├─ 扫描子执行器
  │   ├─ 检查写-写冲突
  │   └─ 计算新元组值
  │
  ├─ 阶段二：逐个处理
  │   ├─ 判断主键是否变更？
  │   │
  │   ├─ 【主键不变】原地更新
  │   │   ├─ 生成 Undo Log（保存修改的字段）
  │   │   ├─ 更新元组数据
  │   │   └─ 记录写集
  │   │
  │   └─ 【主键变更】删除 + 插入
  │       ├─ 逻辑删除旧元组
  │       │   ├─ 生成 Undo Log（保存完整元组）
  │       │   └─ is_deleted_ = true
  │       ├─ 检查新主键是否冲突
  │       ├─ 如果冲突 → 跳过，稍后重试
  │       └─ 如果不冲突 → 插入新元组
  │
  ├─ 阶段三：重试失败的插入
  │   ├─ 重新检查键冲突
  │   ├─ 如果仍然冲突 → 抛出异常
  │   └─ 否则执行插入
  │
  └─ 返回更新行数
  1. 示例数据演示
1
2
3
4
5
6
7
8
9
10
11
12
-- 初始数据
INSERT INTO users VALUES (1, 'Alice', 25);
INSERT INTO users VALUES (2, 'Bob', 30);

-- 场景1：主键不变
UPDATE users SET age = 26 WHERE id = 1;
→ 原地更新，Undo Log 记录 {age: 25}

-- 场景2：主键变更
UPDATE users SET id = 3 WHERE id = 2;
→ 删除 id=2（is_deleted_=true），插入 id=3
→ 删除的 Undo Log 保存完整 {id:2, name:'Bob', age:30}

这种设计完美地平衡了性能（原地更新）和灵活性（主键变更），同时通过 MVCC 保证了读一致性和事务回滚能力。

垃圾回收
  1. 整体架构
1
2
3
4
5
GarbageCollection()
    ├── 阶段一：收集所有事务的写集（RID 列表）
    ├── 阶段二：标记不可见的页面版本（Page Versions）
    ├── 阶段三：统计不可见的 Undo Log
    └── 阶段四：清理已完成的事务

阶段一：收集所有事务的写集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
auto water_mark = running_txns_.GetWatermark();
std::unordered_map<txn_id_t, size_t> invisible_undo_logs_cnt;
std::vector<std::pair<table_oid_t, RID>> tuple_infos;
std::unordered_set<RID> invisible_page_versions;

{
    std::unique_lock<std::shared_mutex> lck(txn_map_mutex_);
    for (auto &it : txn_map_) {
        auto &txn = it.second;
        std::unique_lock<std::mutex> txn_lck(txn->latch_);
        for (auto &w : txn->write_set_) {
            for (auto &rid : w.second) {
                tuple_infos.emplace_back(w.first, rid);
            }
        }
    }
}

关键点：

变量 含义
water_mark 水位线：当前所有活跃事务中最小的读时间戳。任何 ts <= water_mark 的版本都对所有活跃事务不可见。
tuple_infos 所有已提交/中止事务修改过的 RID 列表（从写集中收集）
txn_map_ 存储所有事务（包括活跃和已完成的）

为什么需要停止世界（Stop-the-World）？

  • 需要获取所有事务的快照（water_mark）
  • 在 GC 期间，不能有新事务开始或旧事务提交，否则水位线会变化
  • 这就是为什么注释说 “Will be called only when all transactions are not accessing the table heap”

阶段二：标记不可见的页面版本

1
2
3
4
5
6
7
8
9
10
11
12
{
    for (auto &info : tuple_infos) {
        auto table = catalog_->GetTable(info.first);
        auto page_read_guard = table->table_->AcquireTablePageReadLock(info.second);
        auto page = page_read_guard.As<TablePage>();
        auto [meta, tuple] = page->GetTuple(info.second);
        
        if (meta.ts_ <= water_mark) {
            invisible_page_versions.insert(info.second);  // 标记为不可见
        }
    }
}

判断逻辑：

1
2
3
如果 meta.ts_ <= water_mark
    → 该元组的最新版本对所有活跃事务都不可见
    → 可以安全回收其旧版本（Undo Log）

示例：

时间戳场景 water_mark meta.ts_ 是否不可见
活跃事务最小 ts=100 100 50 ✅ 不可见（旧版本）
活跃事务最小 ts=100 100 150 ❌ 仍可见（新版本）
活跃事务最小 ts=100 100 100 ✅ 不可见（边界值）

阶段三：统计不可见的 Undo Log

这是最复杂的部分，需要遍历每个 RID 的 Undo Log 链：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
{
    std::unique_lock<std::shared_mutex> lck(version_info_mutex_);
    for (auto &it : version_info_) {
        auto &page_version_info = it.second;
        std::unique_lock<std::shared_mutex> page_lck(page_version_info->mutex_);
        
        for (auto &vit : page_version_info->prev_link_) {
            RID rid{it.first, static_cast<uint32_t>(vit.first)};
            auto meet_first = invisible_page_versions.find(rid) != invisible_page_versions.end();
            auto link = vit.second;
            std::optional<UndoLog> log = std::nullopt;
            
            for (; link.IsValid(); link = log.value().prev_version_) {
                log = GetUndoLogOptional(link);
                if (!log.has_value()) {
                    break;
                }
                
                if (meet_first) {
                    // 已经遇到第一个不可见的版本，后续都不可见
                    invisible_undo_logs_cnt[link.prev_txn_]++;
                    continue;
                }
                
                if (log.value().ts_ <= water_mark) {
                    meet_first = true;  // 找到第一个不可见的版本
                    continue;
                }
            }
        }
    }
}

核心算法解析

数据结构：

  • version_info_[page_id]：每个页面的版本信息
  • prev_link_[slot_num]：每个槽位的 Undo Log 链表头
  • Undo Log 通过 prev_version_ 链接成链表（从新到旧）

遍历逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
Undo Log 链表示例（从新到旧）：
  [版本5: ts=200] → [版本4: ts=180] → [版本3: ts=150] → [版本2: ts=120] → [版本1: ts=80]
                                                                              ↑
                                                                         water_mark = 100

遍历过程：
1. 版本5 ts=200 > 100 → 可见，继续
2. 版本4 ts=180 > 100 → 可见，继续
3. 版本3 ts=150 > 100 → 可见，继续
4. 版本2 ts=120 > 100 → 可见，继续
5. 版本1 ts=80 <= 100 → 不可见，标记 meet_first = true

结果：只有版本1被标记为不可见（版本2-5仍可能被某些事务看到）

两种情况：

情况 meet_first 初始值 行为
最新版本已被删除 true（RID 在 invisible_page_versions 中） 所有 Undo Log 都标记为不可见
最新版本仍可见 false 只标记 ts <= water_mark 的旧版本

阶段四：清理已完成的事务

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::unique_lock<std::shared_mutex> lck(txn_map_mutex_);
for (auto it = txn_map_.begin(); it != txn_map_.end();) {
    auto &txn = it->second;
    std::unique_lock<std::mutex> txn_lck(txn->latch_);
    auto state = txn->state_.load();
    auto is_complete = state == TransactionState::COMMITTED || state == TransactionState::ABORTED;
    
    if (!is_complete) {
        it++;  // 活跃事务，保留
        continue;
    }
    
    // 检查该事务的所有 Undo Log 是否都已被回收
    if (txn->undo_logs_.empty() || invisible_undo_logs_cnt[txn->GetTransactionId()] == txn->undo_logs_.size()) {
        it = txn_map_.erase(it);  // 所有 Undo Log 已回收，删除事务对象
    } else {
        it++;  // 仍有 Undo Log 被其他事务引用，保留
    }
}

清理条件：

1
2
3
4
5
6
条件1：事务已完成（COMMITTED 或 ABORTED）
条件2：该事务的所有 Undo Log 都已不可见
    → txn->undo_logs_.empty()（没有 Undo Log）
    → 或 invisible_undo_logs_cnt[txn_id] == txn->undo_logs_.size()（全部不可见）

满足以上条件 → 从 txn_map_ 中删除事务对象
  1. 完整执行示例

场景设置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
时间线：
  ts=100: T1 插入 Alice (id=1, name='Alice', age=25)
  ts=200: T2 将 Alice 更新为 Alice2（生成 UndoLog1）(name='Alice2', age=26)
  ts=300: T3 将 Alice2 更新为 Alice3（生成 UndoLog2）(name='Alice3', age=27)
  ts=400: T4 删除 Alice3（生成 UndoLog3）
  
Undo Log 链结构
text
数据页中的最新版本（已删除）
    ts = 400
    is_deleted_ = true
    roll_ptr ↓
         ↓
    UndoLog3 (T4 的删除操作)
    ├── is_deleted_: false
    ├── modified_fields: [T, T, T]
    ├── tuple: {id:1, name:'Alice3', age:27}
    ├── ts_: 300
    └── prev_version_ ↓
              ↓
    UndoLog2 (T3 的更新操作)
    ├── is_deleted_: false
    ├── modified_fields: [F, T, T]
    ├── tuple: {name:'Alice2', age:26}
    ├── ts_: 200
    └── prev_version_ ↓
              ↓
    UndoLog1 (T2 的更新操作)
    ├── is_deleted_: false
    ├── modified_fields: [F, T, T]
    ├── tuple: {name:'Alice', age:25}
    ├── ts_: 100
    └── prev_version_: null

当前活跃事务：T5（ts=250）
water_mark = 250（最小活跃事务时间戳）

数据状态

版本 内容 ts prev_version
最新（元组） 已删除 400 → UndoLog3
UndoLog3 Alice3 300 → UndoLog2
UndoLog2 Alice2 200 → UndoLog1
UndoLog1 Alice 100 null

GC 执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 阶段一：收集 RID
tuple_infos = [RID_Alice]

// 阶段二：检查最新版本
meta.ts_ = 400 > water_mark(250)
→ invisible_page_versions = {} (空，因为最新版本仍可见)

// 阶段三：遍历 Undo Log 链
meet_first = false

遍历 UndoLog3: ts=300 > 250 → 可见，继续
遍历 UndoLog2: ts=200 <= 250 → 不可见，标记 meet_first = true
遍历 UndoLog1: meet_first = true → 标记为不可见

结果：
  invisible_undo_logs_cnt[T2] = 1  (UndoLog1)
  invisible_undo_logs_cnt[T3] = 1  (UndoLog2)
  invisible_undo_logs_cnt[T4] = 0  (UndoLog3 仍可见)

// 阶段四：清理事务
T1: 无 Undo Log → 可清理
T2: 所有 Undo Log (1个) 已不可见 → 可清理
T3: 所有 Undo Log (1个) 已不可见 → 可清理
T4: UndoLog3 仍被 T5 需要 → 保留

清理结果

事务 Undo Log 是否可见 是否清理
T1 无 N/A ✅ 清理
T2 UndoLog1 ❌ 不可见 ✅ 清理
T3 UndoLog2 ❌ 不可见 ✅ 清理
T4 UndoLog3 ✅ 可见（T5需要） ❌ 保留
T5 无 N/A ❌ 活跃事务