RocksDB SST文件 #

SST文件特点：
├── 有序存储 - 键按字典序排列
├── 不可变 - 一旦写入不再修改
├── 压缩存储 - 支持多种压缩算法
└── 索引结构 - 支持高效查找

文件命名格式：<number>.sst

示例：
000001.sst
000002.sst
000003.sst

文件编号全局唯一，递增分配

┌────────────────────────────────────────────────────┐
│                  Data Block 1                       │
├────────────────────────────────────────────────────┤
│                  Data Block 2                       │
├────────────────────────────────────────────────────┤
│                     ...                             │
├────────────────────────────────────────────────────┤
│                  Data Block N                       │
├────────────────────────────────────────────────────┤
│               Meta Block (Filter)                   │
├────────────────────────────────────────────────────┤
│               Meta Block (Index)                    │
├────────────────────────────────────────────────────┤
│               Meta Index Block                      │
├────────────────────────────────────────────────────┤
│                  Index Block                        │
├────────────────────────────────────────────────────┤
│                   Footer                            │
└────────────────────────────────────────────────────┘

┌────────────────────────────────────────────────────┐
│                   Block Header                      │
│  ┌──────────────────────────────────────────────┐ │
│  │ Block Type (1B) │ Size (2B) │ CRC (4B)       │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│                  KV Entries                         │
│  ┌──────────────────────────────────────────────┐ │
│  │ Entry 1: Shared | Unshared | Value Length    │ │
│  │          Shared Key | Unshared Key | Value   │ │
│  ├──────────────────────────────────────────────┤ │
│  │ Entry 2: ...                                  │ │
│  ├──────────────────────────────────────────────┤ │
│  │ ...                                           │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│                  Restart Points                     │
│  ┌──────────────────────────────────────────────┐ │
│  │ Restart Point 1 | Restart Point 2 | ...      │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│              Restart Points Count (4B)             │
└────────────────────────────────────────────────────┘

前缀压缩原理：

原始数据：
key1: "user:1001:name"
key2: "user:1001:age"
key3: "user:1001:email"

压缩后存储：
Entry 1: shared=0,  key="user:1001:name",  value="Alice"
Entry 2: shared=11, key="age",             value="25"
Entry 3: shared=11, key="email",           value="alice@example.com"

Restart Points:
- 每16个Entry设置一个Restart Point
- Restart Point处不使用前缀压缩
- 支持二分查找

#include <rocksdb/table.h>

rocksdb::BlockBasedTableOptions GetBlockOptions() {
    rocksdb::BlockBasedTableOptions options;
    
    // Block大小
    options.block_size = 4 * 1024;  // 4KB
    
    // Block大小偏差
    options.block_size_deviation = 10;  // 10%
    
    // Restart Point间隔
    options.block_restart_interval = 16;
    
    // 索引类型
    options.index_type = rocksdb::BlockBasedTableOptions::kBinarySearch;
    
    return options;
}

Index Block存储Data Block的索引信息：

┌────────────────────────────────────────────────────┐
│ Index Entry 1                                      │
│  ┌──────────────────────────────────────────────┐ │
│  │ Max Key in Block 1 | Block 1 Offset | Size   │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│ Index Entry 2                                      │
│  ┌──────────────────────────────────────────────┐ │
│  │ Max Key in Block 2 | Block 2 Offset | Size   │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│                    ...                             │
└────────────────────────────────────────────────────┘

查找过程：
1. 二分查找Index Block
2. 定位到目标Data Block
3. 在Data Block内查找

#include <rocksdb/table.h>

// 1. 二分查找索引（默认）
options.index_type = rocksdb::BlockBasedTableOptions::kBinarySearch;

// 2. 哈希索引（适合点查询）
options.index_type = rocksdb::BlockBasedTableOptions::kHashSearch;
options.prefix_extractor.reset(rocksdb::NewFixedPrefixTransform(5));

// 3. 二路搜索索引
options.index_type = rocksdb::BlockBasedTableOptions::kTwoLevelIndexSearch;

#include <rocksdb/table.h>
#include <rocksdb/filter_policy.h>

rocksdb::BlockBasedTableOptions GetFilterOptions() {
    rocksdb::BlockBasedTableOptions options;
    
    // 创建布隆过滤器
    options.filter_policy.reset(
        rocksdb::NewBloomFilterPolicy(10)  // 10 bits per key
    );
    
    // 过滤器位置
    options.optimize_filters_for_memory = false;
    
    // 全键过滤
    options.whole_key_filtering = true;
    
    return options;
}

Filter Block结构：

┌────────────────────────────────────────────────────┐
│                  Filter Data                        │
│  ┌──────────────────────────────────────────────┐ │
│  │ Bloom Filter Bits Array                      │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│                  Filter Offsets                    │
│  ┌──────────────────────────────────────────────┐ │
│  │ Offset 1 | Offset 2 | ...                    │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│             Filter Offset Array Offset             │
├────────────────────────────────────────────────────┤
│                  Base Log Value                    │
└────────────────────────────────────────────────────┘

布隆过滤器工作原理：

插入：
key → hash1(key), hash2(key), ... → 设置对应bit位

查询：
key → hash1(key), hash2(key), ... → 检查对应bit位

结果：
- 所有bit为1 → 可能存在（需进一步确认）
- 有bit为0   → 一定不存在（直接跳过）

参数：
- bits_per_key: 每个key分配的bit数
- 假阳性率 ≈ (1 - e^(-kn/m))^k
  - k: hash函数数量
  - n: key数量
  - m: bit数组大小

Footer结构（48字节）：

┌────────────────────────────────────────────────────┐
│             Meta Index Block Handle                 │
│  ┌──────────────────────────────────────────────┐ │
│  │ Offset (8B) | Size (8B)                      │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│              Index Block Handle                    │
│  ┌──────────────────────────────────────────────┐ │
│  │ Offset (8B) | Size (8B)                      │ │
│  └──────────────────────────────────────────────┘ │
├────────────────────────────────────────────────────┤
│                Padding (4B)                        │
├────────────────────────────────────────────────────┤
│             Checksum Type (1B)                     │
├────────────────────────────────────────────────────┤
│             Magic Number (8B)                      │
│           0x88e241b785f4cff7                       │
└────────────────────────────────────────────────────┘

Footer的作用：
1. 定位Index Block
2. 定位Meta Index Block
3. 文件完整性校验
4. 版本识别

读取一个key的流程：

1. 读取Footer
   ↓
2. 获取Index Block位置
   ↓
3. 读取Index Block
   ↓
4. 二分查找定位Data Block
   ↓
5. 检查Filter Block（布隆过滤器）
   ↓
6. 读取Data Block
   ↓
7. 在Data Block内查找key

#include <rocksdb/table.h>
#include <rocksdb/cache.h>

// 配置Block Cache
rocksdb::BlockBasedTableOptions table_options;

// LRU缓存
table_options.block_cache = rocksdb::NewLRUCache(
    1024 * 1024 * 1024,  // 1GB容量
    8                      // 分片数
);

// 压缩块缓存
table_options.block_cache_compressed = rocksdb::NewLRUCache(
    256 * 1024 * 1024  // 256MB
);

options.table_factory.reset(
    rocksdb::NewBlockBasedTableFactory(table_options)
);

# 查看SST文件信息
sst_dump --file=/path/to/file.sst --command=scan

# 查看文件属性
sst_dump --file=/path/to/file.sst --command=stats

# 导出数据
sst_dump --file=/path/to/file.sst --command=scan --output_format=escaped

# 验证文件
sst_dump --file=/path/to/file.sst --command=verify

# 查看SST文件内容
ldb dump --file=/path/to/file.sst

# 查看数据库所有SST文件
ldb list_file_nums /path/to/db

# 导出整个数据库
ldb dump /path/to/db > dump.txt

SST文件生命周期：

1. 创建
   - MemTable Flush
   - Compaction
   - 外部导入

2. 使用
   - 读取数据
   - Compaction输入

3. 删除
   - Compaction完成后
   - 手动清理

#include <rocksdb/db.h>
#include <iostream>

void PrintSSTStats(rocksdb::DB* db) {
    // 各层文件数量
    for (int level = 0; level < 7; level++) {
        uint64_t num_files = 0;
        std::string prop = "rocksdb.num-files-at-level" + std::to_string(level);
        db->GetIntProperty(prop, &num_files);
        std::cout << "Level " << level << ": " << num_files << " files" << std::endl;
    }
    
    // 总SST文件大小
    uint64_t total_size = 0;
    db->GetIntProperty("rocksdb.total-sst-files-size", &total_size);
    std::cout << "Total SST size: " << total_size / 1024 / 1024 << " MB" << std::endl;
}