BigTable底层数据结构实现及C++原型设计正确性咨询

我正在学习SSTABLE和MVCC，决定阅读BigTable论文。但BigTable的数据模型较为抽象，因此我计划用C++实现一个小型原型。我设计了如下数据结构，但似乎存在冗余，请问该设计是否正确？

// 表示BigTable中单元格的结构体
struct Cell {
    string value; // 单元格的值
    int64_t timestamp; // 单元格的时间戳
};

// 表示BigTable中列族的结构体
struct ColumnFamily {
    string name; // 列族的名称
    map<string, Cell> cells; // 从列键到单元格的映射
};

// 表示BigTable中行的结构体
struct Row {
    string RowKey; // 行键
    vector<ColumnFamily> column_families; // 行中的列族集合
};

class table {
    string table_name;
    vector<Row> rows_;
};

核心问题分析 #

你的设计方向贴合BigTable的层级逻辑，但存在3个关键的冗余和模型偏差：

1. 缺失MVCC多版本支持 #

BigTable的核心特性是MVCC，每个列键允许存储多个时间戳版本的单元格（默认按时间戳降序返回最新版本）。但你的ColumnFamily::cells是map<string, Cell>，只能存储单个版本，直接违背了MVCC设计，这是最核心的问题。

2. 列族存储冗余 #

BigTable中列族是表级元数据，不是行级数据。每个行不需要重复存储列族名称——你的Row::column_families会让每一行都存储列族名，造成大量冗余。正确的做法是表级别维护列族信息，行只存储该列族下的列数据。

3. 行存储结构低效 #

BigTable的行是按行键字典序排序的，支持范围查询。用vector<Row>存储行无法高效实现按行键查找、范围遍历，必须用有序结构替代。

改进后的结构示例 #

// 单元格：存储值与时间戳，建议用uint64_t避免负数问题（BigTable用微秒级时间戳）
struct Cell {
    string value;
    uint64_t timestamp;
};

// 行数据：列族名 -> 列键 -> 多版本单元格列表（按时间戳降序排列）
struct RowData {
    map<string, map<string, vector<Cell>>> cf_columns;
};

class BigTable {
private:
    string table_name;
    // 表级列族元数据：存储列族的存在性与属性（简化版仅存存在性）
    unordered_set<string> column_families;
    // 有序存储行：按行键字典序排列，支持高效查找与范围遍历
    map<string, RowData> sorted_rows;

public:
    // 预先创建列族（BigTable要求列族需提前创建）
    bool create_column_family(const string& cf_name) {
        return column_families.insert(cf_name).second;
    }

    // 写入单元格：支持指定时间戳
    void put(const string& row_key, const string& cf_name, const string& column, const string& value, uint64_t timestamp) {
        if (!column_families.count(cf_name)) return; // 列族不存在则拒绝写入

        auto& cell_list = sorted_rows[row_key].cf_columns[cf_name][column];
        cell_list.emplace_back(value, timestamp);
        // 保持单元格按时间戳降序，方便快速获取最新版本
        sort(cell_list.begin(), cell_list.end(),
             [](const Cell& a, const Cell& b) { return a.timestamp > b.timestamp; });
    }

    // 获取最新版本的单元格值
    optional<string> get_latest(const string& row_key, const string& cf_name, const string& column) {
        auto row_it = sorted_rows.find(row_key);
        if (row_it == sorted_rows.end()) return nullopt;

        auto cf_it = row_it->second.cf_columns.find(cf_name);
        if (cf_it == row_it->second.cf_columns.end()) return nullopt;

        auto col_it = cf_it->second.find(column);
        if (col_it == cf_it->second.end() || col_it->second.empty()) return nullopt;

        return col_it->second.front().value;
    }
};

额外注意事项 #

• SSTable是持久化层结构，内存层通常用MemTable（有序结构，比如跳表），上述示例用map是简化实现，实际可以用更高效的有序容器
• BigTable的时间戳可由客户端指定或服务器分配，建议优先用uint64_t
• 列族的属性还可包括TTL（自动过期时间）、存储类型等，可根据原型需求扩展

内容的提问来源于stack exchange，提问作者hpd