`Undo Log`的`数据`结构：`undo`日志的`回滚`和`MVCC`（`多版本并发控制`）的`物理`实现。

好的，我们开始今天的讲座。今天的主题是Undo Log的数据结构，以及Undo Log在回滚和MVCC中物理实现的角色。

1. 事务与数据一致性

在深入Undo Log之前，我们先回顾一下事务的基本概念。事务是数据库管理系统（DBMS）执行过程中的一个逻辑单位，由一个有限的操作序列构成。事务必须具备ACID特性：

• 原子性（Atomicity）： 事务中的所有操作要么全部成功，要么全部失败。不存在部分成功的情况。
• 一致性（Consistency）： 事务执行前后，数据库的状态必须保持一致。一致性是由应用程序保证的，而原子性、隔离性和持久性是DBMS提供保障一致性的手段。
• 隔离性（Isolation）： 并发执行的事务之间应该相互隔离，一个事务不应该看到其他事务未提交的修改。
• 持久性（Durability）： 事务一旦提交，其修改就应该永久保存在数据库中，即使系统崩溃也不应该丢失。

Undo Log正是保障事务原子性和一致性的关键组件之一。

2. Undo Log 的概念与作用

Undo Log，顾名思义，是用于撤销（Undo）操作的日志。它记录了事务对数据进行修改之前的状态。当事务执行失败需要回滚时，DBMS可以利用Undo Log将数据恢复到修改前的状态，从而保证原子性。

Undo Log的主要作用：

• 事务回滚（Transaction Rollback）： 当事务因任何原因（例如系统崩溃、应用程序错误）需要回滚时，Undo Log提供必要的信息，将数据恢复到事务开始前的状态。
• MVCC（多版本并发控制）： 在MVCC机制中，Undo Log存储了数据的历史版本，允许并发事务读取不同版本的数据，从而提高并发性能。

3. Undo Log 的数据结构

Undo Log通常以链表的形式组织，每个链表节点对应一个事务对数据的修改操作。每个节点包含以下关键信息：

字段名称	字段类型	描述
Log Record Type	Enum	记录类型，例如：INSERT, UPDATE, DELETE, COMPENSATE(用于指示回滚时执行的操作)
Table ID	Integer	修改的表ID
Page ID	Integer	修改的页ID
Offset	Integer	修改的数据在页内的偏移量
Old Value	Byte Array	修改前的数据值
Next Undo Log	Pointer	指向同一个事务的下一个Undo Log记录的指针。用于将属于同一个事务的所有Undo Log记录链接起来。
Transaction ID	Integer	事务ID，用于标识属于哪个事务的undo log
Rollback Segment No	Integer	回滚段编号，用于标识该undo log属于哪个回滚段。这在一些实现中用于优化undo log的管理，比如将undo log分散存储在不同的回滚段中。

假设我们有一个简单的users表：

CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    age INT
);

现在假设有如下事务：

START TRANSACTION;
INSERT INTO users (id, name, age) VALUES (1, 'Alice', 30);
UPDATE users SET age = 31 WHERE id = 1;
DELETE FROM users WHERE id = 1;
COMMIT;

对应的Undo Log记录可能如下 (简化表示)：

1. INSERT Log Record:

   • Log Record Type: INSERT
   • Table ID: users 表的ID
   • Page ID: 数据页ID
   • Offset: 偏移量
   • Old Value: 空 (因为是插入操作)
   • Next Undo Log: 指向下一个Undo Log记录
   • Transaction ID: 当前事务ID

2. UPDATE Log Record:

   • Log Record Type: UPDATE
   • Table ID: users 表的ID
   • Page ID: 数据页ID
   • Offset: 偏移量
   • Old Value: age = 30 (修改前的值)
   • Next Undo Log: 指向下一个Undo Log记录
   • Transaction ID: 当前事务ID

3. DELETE Log Record:

   • Log Record Type: DELETE
   • Table ID: users 表的ID
   • Page ID: 数据页ID
   • Offset: 偏移量
   • Old Value: id = 1, name = 'Alice', age = 31 (被删除的整行数据)
   • Next Undo Log: NULL (最后一个Undo Log记录)
   • Transaction ID: 当前事务ID

代码示例 (C++ 模拟 Undo Log 结构):

#include <iostream>
#include <vector>
#include <string>

enum LogRecordType {
    INSERT,
    UPDATE,
    DELETE_RECORD,
    COMPENSATE
};

struct UndoLogRecord {
    LogRecordType record_type;
    int table_id;
    int page_id;
    int offset;
    std::vector<unsigned char> old_value; // 使用字节数组存储数据
    UndoLogRecord* next;
    int transaction_id;
    int rollback_segment_no;

    UndoLogRecord(LogRecordType type, int table, int page, int off, const std::vector<unsigned char>& old, int tx_id, int rollback_no)
        : record_type(type), table_id(table), page_id(page), offset(off), old_value(old), next(nullptr), transaction_id(tx_id), rollback_segment_no(rollback_no) {}
};

class UndoLog {
public:
    UndoLog() : head(nullptr), tail(nullptr) {}

    void add_record(LogRecordType type, int table, int page, int off, const std::vector<unsigned char>& old, int tx_id, int rollback_no) {
        UndoLogRecord* new_record = new UndoLogRecord(type, table, page, off, old, tx_id, rollback_no);
        if (!head) {
            head = new_record;
            tail = new_record;
        } else {
            tail->next = new_record;
            tail = new_record;
        }
    }

    UndoLogRecord* get_head() {
        return head;
    }

    ~UndoLog() {
        UndoLogRecord* current = head;
        while (current) {
            UndoLogRecord* next = current->next;
            delete current;
            current = next;
        }
    }

private:
    UndoLogRecord* head;
    UndoLogRecord* tail;
};

int main() {
    UndoLog undo_log;

    // 模拟插入操作
    std::vector<unsigned char> empty_value;
    undo_log.add_record(INSERT, 1, 100, 0, empty_value, 123, 1);

    // 模拟更新操作
    std::string old_age = "30";
    std::vector<unsigned char> old_age_bytes(old_age.begin(), old_age.end());
    undo_log.add_record(UPDATE, 1, 100, 4, old_age_bytes, 123, 1);

    // 模拟删除操作
    std::string deleted_row = "id=1, name='Alice', age=31";
    std::vector<unsigned char> deleted_row_bytes(deleted_row.begin(), deleted_row.end());
    undo_log.add_record(DELETE_RECORD, 1, 100, 0, deleted_row_bytes, 123, 1);

    // 打印 Undo Log 记录 (简单示例)
    UndoLogRecord* current = undo_log.get_head();
    while (current) {
        std::cout << "Record Type: " << current->record_type << std::endl;
        std::cout << "Table ID: " << current->table_id << std::endl;
        current = current->next;
    }

    return 0;
}

4. Undo Log 与事务回滚

当事务需要回滚时，DBMS会按照Undo Log记录的反向顺序执行补偿操作。 补偿操作的类型取决于Undo Log记录的类型：

• INSERT: 执行DELETE操作，删除插入的数据。
• UPDATE: 将数据恢复到Old Value。
• DELETE: 重新插入被删除的数据。

以上面的例子为例，如果事务需要回滚，则按照DELETE -> UPDATE -> INSERT的顺序执行补偿操作：

1. DELETE 补偿: 根据DELETE Log Record中的Old Value，重新插入id = 1, name = 'Alice', age = 31这条记录。
2. UPDATE 补偿: 根据UPDATE Log Record中的Old Value，将id = 1的记录的age字段更新为30。
3. INSERT 补偿: 根据INSERT Log Record，删除刚刚插入的id = 1的记录。

代码示例 (C++ 模拟回滚):

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  // for std::reverse

// (前面定义的 LogRecordType 和 UndoLogRecord 结构体保持不变)
// (前面定义的 UndoLog 类保持不变)

// 模拟数据库操作 (简化)
void insert_data(int table_id, int page_id, int offset, const std::vector<unsigned char>& data) {
    std::cout << "Simulating INSERT: table_id=" << table_id << ", page_id=" << page_id
              << ", offset=" << offset << ", data='" << std::string(data.begin(), data.end()) << "'" << std::endl;
}

void update_data(int table_id, int page_id, int offset, const std::vector<unsigned char>& data) {
    std::cout << "Simulating UPDATE: table_id=" << table_id << ", page_id=" << page_id
              << ", offset=" << offset << ", data='" << std::string(data.begin(), data.end()) << "'" << std::endl;
}

void delete_data(int table_id, int page_id, int offset) {
    std::cout << "Simulating DELETE: table_id=" << table_id << ", page_id=" << page_id
              << ", offset=" << offset << std::endl;
}

void rollback(UndoLog& undo_log) {
    std::vector<UndoLogRecord*> records;
    UndoLogRecord* current = undo_log.get_head();
    while (current) {
        records.push_back(current);
        current = current->next;
    }

    // 反向遍历 Undo Log 记录
    std::reverse(records.begin(), records.end());

    for (UndoLogRecord* record : records) {
        switch (record->record_type) {
            case INSERT:
                std::cout << "Performing INSERT Compensation (DELETE)" << std::endl;
                delete_data(record->table_id, record->page_id, record->offset);
                break;
            case UPDATE:
                std::cout << "Performing UPDATE Compensation (REVERT)" << std::endl;
                update_data(record->table_id, record->page_id, record->offset, record->old_value);
                break;
            case DELETE_RECORD:
                std::cout << "Performing DELETE Compensation (RE-INSERT)" << std::endl;
                insert_data(record->table_id, record->page_id, record->offset, record->old_value);
                break;
            default:
                std::cout << "Unknown Log Record Type" << std::endl;
                break;
        }
    }
}

int main() {
    UndoLog undo_log;

    // 模拟插入操作
    std::vector<unsigned char> empty_value;
    undo_log.add_record(INSERT, 1, 100, 0, empty_value, 123, 1);

    // 模拟更新操作
    std::string old_age = "30";
    std::vector<unsigned char> old_age_bytes(old_age.begin(), old_age.end());
    undo_log.add_record(UPDATE, 1, 100, 4, old_age_bytes, 123, 1);

    // 模拟删除操作
    std::string deleted_row = "id=1, name='Alice', age=31";
    std::vector<unsigned char> deleted_row_bytes(deleted_row.begin(), deleted_row.end());
    undo_log.add_record(DELETE_RECORD, 1, 100, 0, deleted_row_bytes, 123, 1);

    std::cout << "Initiating Rollback..." << std::endl;
    rollback(undo_log);

    return 0;
}

5. Undo Log 与 MVCC

MVCC 允许多个事务并发读取相同的数据，而无需互相阻塞。 实现MVCC的关键在于维护数据的多个版本。 Undo Log在MVCC中扮演着至关重要的角色，它存储了数据的历史版本。

在MVCC中，每个数据行通常包含以下元数据：

• 创建版本号（Creator Transaction ID）： 标识创建该数据行的事务ID。
• 删除版本号（Deleter Transaction ID）： 标识删除该数据行的事务ID。如果该数据行未被删除，则此字段为空。

当一个事务需要读取数据时，DBMS会根据事务的隔离级别和版本号来选择合适的版本。

• 读取未提交读 (Read Uncommitted): 读取最新的版本，可能读取到未提交的数据。
• 读取已提交读 (Read Committed): 读取已提交的最新版本。
• 可重复读 (Repeatable Read): 读取事务开始时存在的已提交版本。
• 串行化 (Serializable): 强制事务串行执行。

例如，如果一个事务T1正在读取数据，并且隔离级别为可重复读，那么T1只能看到在T1开始时已经提交的数据版本。如果某个数据行在T1开始之后被修改或删除，T1仍然可以从Undo Log中找到该数据行的旧版本。

MVCC 读取数据的流程 (简化):

1. 事务T发起读取请求。
2. DBMS检查数据行的创建版本号和删除版本号。
3. 如果数据行的创建版本号小于等于T的事务ID，并且删除版本号大于T的事务ID或者为空，则表示T可以看到该数据行。
4. 如果数据行的版本不符合条件，DBMS会根据Undo Log找到符合条件的旧版本。
5. 将找到的版本返回给事务T。

代码示例 (C++ 模拟 MVCC 读取):

#include <iostream>
#include <vector>
#include <string>
#include <map>

// 简化的数据行结构
struct DataRow {
    int id;
    std::string name;
    int age;
    int creator_tx_id;
    int deleter_tx_id;  // 0 表示未删除
};

// 存储数据行和 Undo Log
std::map<int, DataRow> database; // key 是 data row id
UndoLog undo_log;
int current_transaction_id = 1; // 简单递增事务 ID

// 模拟数据库操作
void insert_data_with_tx(int id, const std::string& name, int age, int tx_id) {
    DataRow new_row = {id, name, age, tx_id, 0}; // 0 表示未删除
    database[id] = new_row;
}

void update_data_with_tx(int id, const std::string& new_name, int new_age, int tx_id) {
    // 1. 保存旧值到 Undo Log
    DataRow& old_row = database[id];
    std::string old_data = std::to_string(old_row.id) + "," + old_row.name + "," + std::to_string(old_row.age);
    std::vector<unsigned char> old_data_bytes(old_data.begin(), old_data.end());
    undo_log.add_record(UPDATE, 1, 100, id, old_data_bytes, tx_id, 1);

    // 2. 更新数据
    old_row.name = new_name;
    old_row.age = new_age;
}

void delete_data_with_tx(int id, int tx_id) {
    // 1. 保存删除前的状态到 Undo Log
    DataRow& old_row = database[id];
    std::string old_data = std::to_string(old_row.id) + "," + old_row.name + "," + std::to_string(old_row.age);
    std::vector<unsigned char> old_data_bytes(old_data.begin(), old_data.end());
    undo_log.add_record(DELETE_RECORD, 1, 100, id, old_data_bytes, tx_id, 1);

    // 2. 标记为已删除
    database[id].deleter_tx_id = tx_id;
}

// MVCC 读取数据
DataRow read_data_with_mvcc(int id, int tx_id) {
    DataRow row = database[id];

    // 检查是否可见
    if (row.creator_tx_id <= tx_id && (row.deleter_tx_id > tx_id || row.deleter_tx_id == 0)) {
        return row; // 返回当前版本
    } else {
        // 从 Undo Log 查找旧版本 (简化，只查找最近的一个版本)
        UndoLogRecord* current = undo_log.get_head();
        DataRow old_row;

        while(current){
            if(current->table_id == 1 && current->page_id == 100 && current->offset == id && current->transaction_id < tx_id){
                std::string old_data(current->old_value.begin(), current->old_value.end());
                size_t pos1 = old_data.find(",");
                size_t pos2 = old_data.find(",", pos1 + 1);
                if (pos1 != std::string::npos && pos2 != std::string::npos) {
                    old_row.id = std::stoi(old_data.substr(0, pos1));
                    old_row.name = old_data.substr(pos1 + 1, pos2 - pos1 - 1);
                    old_row.age = std::stoi(old_data.substr(pos2 + 1));
                    old_row.creator_tx_id = 0; //未知
                    old_row.deleter_tx_id = 0; // 未知
                    return old_row;
                }
            }
            current = current->next;
        }

        // 没有找到符合条件的版本
        return {-1, "", -1, -1, -1}; // 返回一个无效的数据行
    }
}

int main() {
    // 初始化数据
    insert_data_with_tx(1, "Alice", 30, 1);

    // 事务 2 更新数据
    update_data_with_tx(1, "Alice Smith", 31, 2);

    // 事务 3 删除数据
    delete_data_with_tx(1, 3);

    // 事务 4 读取数据
    DataRow row4 = read_data_with_mvcc(1, 4);
    std::cout << "Transaction 4 reads: id=" << row4.id << ", name=" << row4.name << ", age=" << row4.age << ", creator_tx_id=" << row4.creator_tx_id << ", deleter_tx_id=" << row4.deleter_tx_id << std::endl; //输出id=-1，name=""，age=-1，creator_tx_id=-1，deleter_tx_id=-1。事务4读不到数据了

    // 事务 1 读取数据 (应该读取到最初的版本)
    DataRow row1 = read_data_with_mvcc(1, 1);
    std::cout << "Transaction 1 reads: id=" << row1.id << ", name=" << row1.name << ", age=" << row1.age << ", creator_tx_id=" << row1.creator_tx_id << ", deleter_tx_id=" << row1.deleter_tx_id << std::endl; //Transaction 1 reads: id=1, name=Alice, age=30, creator_tx_id=1, deleter_tx_id=0

    // 事务 2 读取数据 (应该读取到事务 2 更新后的版本)
    DataRow row2 = read_data_with_mvcc(1, 2);
    std::cout << "Transaction 2 reads: id=" << row2.id << ", name=" << row2.name << ", age=" << row2.age << ", creator_tx_id=" << row2.creator_tx_id << ", deleter_tx_id=" << row2.deleter_tx_id << std::endl;//Transaction 2 reads: id=1, name=Alice Smith, age=31, creator_tx_id=1, deleter_tx_id=0

    return 0;
}

6. Undo Log 的物理实现

Undo Log的物理实现涉及到如何将Undo Log记录存储在磁盘上，以及如何有效地管理和访问这些记录。 一些关键的考虑因素包括：

• 存储位置： Undo Log可以存储在单独的文件中，也可以与数据文件混合存储。 单独存储可以提高性能，但会增加管理的复杂性。
• 存储格式： Undo Log记录可以使用二进制格式或文本格式存储。 二进制格式更紧凑，但可读性较差。
• 空间管理： Undo Log的空间需要定期回收，以防止空间耗尽。 常见的回收策略包括：事务提交后立即删除Undo Log记录、定期清理不再需要的Undo Log记录。
• 并发访问： 需要采取适当的并发控制机制，以保证多个事务可以安全地访问Undo Log。

在实际的数据库系统中，Undo Log的管理通常由专门的模块负责。 这些模块负责Undo Log的写入、读取、回收和并发控制。 不同的数据库系统可能有不同的实现方式，但基本原理是相似的。

一些数据库系统使用的Undo Log相关技术

• 回滚段（Rollback Segments）： Oracle等数据库系统使用回滚段来管理Undo Log。回滚段是预先分配的一组存储空间，用于存储Undo Log记录。
• Undo Tablespace： MySQL的InnoDB存储引擎使用Undo Tablespace来存储Undo Log。Undo Tablespace是一个独立的表空间，专门用于存储Undo Log。
• Mini-Transactions: 某些数据库系统，特别是那些针对高并发场景优化的系统，会将大的事务分解成更小的"mini-transactions"。每个 mini-transaction 都有自己的 undo log，从而减少单个事务的锁持有时间，提高并发性。

对事务进行回滚和利用Undo Log实现MVCC至关重要

Undo Log是保障数据库事务ACID特性的重要组成部分。它不仅用于事务回滚，还为MVCC提供了必要的历史版本信息。理解Undo Log的数据结构和物理实现对于深入理解数据库系统的内部机制至关重要。

Undo Log 的管理和优化需要关注

Undo Log的管理涉及到存储位置、存储格式、空间管理和并发访问等多个方面。选择合适的策略可以有效地提高数据库系统的性能和可靠性。