当前位置： 首页 > article >正文

mini-lsm通关笔记Week2Day7

article 2025/2/6 12:19:25

项目地址：https://github.com/skyzh/mini-lsm

个人实现地址：https://gitee.com/cnyuyang/mini-lsm

在上一章中，您已经构建了一个完整的基于LSM的存储引擎。在本周末，我们将实现存储引擎的一些简单但重要的优化。欢迎来到Mini-LSM的第2周零食时间！

在本章中，您将：

  • 实现批量写入接口。
  • 添加checksum到块、SST元数据、manifest和WAL。

注意：本章没有单元测试。只要你通过了之前的所有测试，并确保校验和在你的文件格式中正确编码，就可以了。

Task 1-Write Batch Interface

在本任务中，我们将通过添加写入批处理API来为本教程的第3周做好准备。您需要修改：

src/lsm_storage.rs

用户向write_batch提供一批要写入数据库的记录。这些记录是WriteBatchRecord<T:AsRef<[u8]>>，因此它可以是Bytes、&[u8]或Vec<u8>。有两种类型的记录：delete和put。您可以以与您的put和delete函数相同的方式处理它们。

之后，你可以重构你原来的put和delete函数来调用write_batch。

在实现此功能之后，您应该通过前面章节中的所有测试用例。

该任务就是实现write_batch函数，其实就是把之前写在put、delete中的函数，放在一起循环遍历：

pub fn write_batch<T: AsRef<[u8]>>(&self, _batch: &[WriteBatchRecord<T>]) -> Result<()> {
    for record in _batch {
        match record {
            WriteBatchRecord::Del(key) => {
                // 原来delete中的逻辑
                ...
            }
            WriteBatchRecord::Put(key, value) => {
                // 原来put中的逻辑
                ...
            }
        }
    }
    Ok(())
}

再修改put、delete的实现，调用该函数：

pub fn put(&self, _key: &[u8], _value: &[u8]) -> Result<()> {
    self.write_batch(&[WriteBatchRecord::Put(_key, _value)])
}

pub fn delete(&self, _key: &[u8]) -> Result<()> {
    self.write_batch(&[WriteBatchRecord::Del(_key)])
}

Task 2-Block Checksum

在此任务中，当编码SST时，您需要在每个块的末尾添加块校验和。您需要修改：

src/table/builder.rs
src/table.rs

SST的格式将更改为：

---------------------------------------------------------------------------------------------------------------------------
|                   Block Section                     |                            Meta Section                           |
---------------------------------------------------------------------------------------------------------------------------
| data block | checksum | ... | data block | checksum | metadata | meta block offset | bloom filter | bloom filter offset |
|   varlen   |    u32   |     |   varlen   |    u32   |  varlen  |         u32       |    varlen    |        u32          |
---------------------------------------------------------------------------------------------------------------------------

我们使用crc32作为我们的校验和算法。您可以在构建block块后使用crc32fast::hash生成block块的校验和。

通常，当用户在存储选项中指定目标block块大小时，大小应包括块内容和校验和。例如，如果目标block块大小为4096，校验和占用4字节，则实际block块内容目标大小应为4092。但是，为了避免破坏之前的测试用例，并且为了简单起见，在我们的教程中，我们仍然将使用目标block块大小作为目标内容大小，并简单地在块的末尾附加校验和。

当你读取块时，你应该在read_block函数中校验校验和，以保证读取到正确的存储内容。在实现此功能之后，您应该通过前面章节中的所有测试用例。

如题目要求需要修改SST的格式，在block块数据后存储校验和。读取的时候通过校验和校验数据是否正确。

计算校验和，并存储(src/table/builder.rs)：

fn finish_block(&mut self) {
    ...
    // 计算校验和
    let checksum = crc32fast::hash(&encoded_block);
    // 存储数据
    self.data.append(&mut encoded_block.to_vec());
    // 尾部附加校验和
    self.data.put_u32(checksum);
}

读取校验和，并校验(table.rs)：

pub fn read_block(&self, block_idx: usize) -> Result<Arc<Block>> {
    let offset = self.block_meta[block_idx].offset;
    let offset_end = self
        .block_meta
        .get(block_idx + 1)
        .map_or(self.block_meta_offset, |x| x.offset);
    // block块的长度
    let block_len = offset_end - offset - 4;
    // 读取block块以及校验和
    let block_data_with_chksum: Vec<u8> = self
        .file
        .read(offset as u64, (offset_end - offset) as u64)?;
    // 数据块数据
    let block_data = &block_data_with_chksum[..block_len];
    // 校验和
    let checksum = (&block_data_with_chksum[block_len..]).get_u32();
    // 校验数据是否正确
    if checksum != crc32fast::hash(block_data) {
        bail!("block checksum mismatched");
    }
    Ok(Arc::new(Block::decode(block_data)))
}

Task 3-SST Meta Checksum

在此任务中，您需要为布隆过滤器和块元数据添加块校验和：

src/table/builder.rs
src/table.rs
src/bloom.rs

----------------------------------------------------------------------------------------------------------
|                                                Meta Section                                            |
----------------------------------------------------------------------------------------------------------
| no. of block | metadata | checksum | meta block offset | bloom filter | checksum | bloom filter offset |
|     u32      |  varlen  |    u32   |        u32        |    varlen    |    u32   |        u32          |
----------------------------------------------------------------------------------------------------------

您需要在Bloom::coding和Bloom::decode中的Bloom过滤器的末尾添加校验和。请注意，我们的大多数API采用一个现有的缓冲区，实现将写入该缓冲区，例如，Bloom::code。因此，在写入编码内容之前，应该记录bloom filter开始的偏移量，并且只对bloom filter本身进行校验和，而不是对整个缓冲区进行校验和。

之后，您可以在块元数据的末尾添加校验和。您可能会发现在小节的开头添加一段元数据会很有帮助，这样在解码块元数据时更容易知道在哪里停止。

元数据校验和

编码(table.rs)：

pub fn encode_block_meta(
    block_meta: &[BlockMeta],
    #[allow(clippy::ptr_arg)] // remove this allow after you finish
    buf: &mut Vec<u8>,
) {
    let original_len = buf.len();
    buf.put_u32(block_meta.len() as u32);
    for meta in block_meta {
       ...
       // 填充Meta数据
    }
    // 计算并写入校验和，只计算Meta数据部分
    buf.put_u32(crc32fast::hash(&buf[original_len + 4..]));
}

解码(table.rs)：

pub fn decode_block_meta(mut buf: &[u8]) -> Result<Vec<BlockMeta>> {
    let num = buf.get_u32();
    // 计算校验和
    let checksum = crc32fast::hash(&buf[..buf.remaining() - 4]);
    let mut block_meta: Vec<BlockMeta> = Vec::with_capacity(num as usize);
    for i in 0..num {
        ...
        // 读取Meta数据
    }
    // 读取校验和 并 校验读取的和计算的是否相同
    if buf.get_u32() != checksum {
        bail!("meta checksum mismatched");
    }

    Ok(block_meta)
}

布隆过滤器校验和

编码(bloom.rs)：

pub fn encode(&self, buf: &mut Vec<u8>) {
    let offset = buf.len();
    
    ... // 编码布隆过滤器

    // 计算并写入布隆过滤器
    let checksum = crc32fast::hash(&buf[offset..]);
    buf.put_u32(checksum);
}

解码(bloom.rs)：

pub fn decode(buf: &[u8]) -> Result<Self> {
    // 读取校验和并校验
    let checksum = (&buf[buf.len() - 4..buf.len()]).get_u32();
    if checksum != crc32fast::hash(&buf[..buf.len() - 4]) {
        bail!("checksum mismatched for bloom filters");
    }
    ...
}

Task 4-WAL Checksum

在此任务中，您需要修改：

src/wal.rs

我们将在预写日志中执行每个记录的校验和。为此，您有两个选择：

  • 生成key-value记录的缓冲区，并使用crc32fast::hash一次性计算校验和。
  • 一次写入一个字段（例如，密钥长度，密钥切片），并使用crc32fast：哈希器对每个字段增量计算校验和。

这取决于您的选择，您将需要选择您自己的冒险。只要正确处理大/小端差异，这两种方法都应该产生完全相同的结果。新的WAL编码应该如下所示：

| key_len | key | value_len | value | checksum |

编码(wal.rs)，一次写入一个字段（例如，密钥长度，密钥切片），并使用crc32fast：哈希器对每个字段增量计算校验和：

pub fn put(&self, _key: &[u8], _value: &[u8]) -> Result<()> {
    ...
    let mut hasher = crc32fast::Hasher::new();
    hasher.write_u16(key_len as u16);
    ...
    hasher.write(_key);
    ...
    hasher.write_u16(value_len as u16);
    ...
    hasher.write(_value);
    buf.put_u32(hasher.finalize());
    ...
}

解码(wal.rs)，就是逆过程：

let mut hasher = crc32fast::Hasher::new();
...
hasher.write_u16(key_len as u16);
...
hasher.write(&key);
...
hasher.write_u16(value_len as u16);
...
hasher.write(&value);
...

// 读取并校验
let checksum = rbuf.get_u32();
if hasher.finalize() != checksum {
    bail!("checksum mismatch");
}

Task 5-Manifest Checksum

最后，让我们在Manifest文件中添加校验和。Manifest类似于WAL，不同的是，我们不存储每条记录的长度。为了使实现更简单，我们现在在记录的开头添加记录长度的标头，并在记录的末尾添加校验和。

新的Manifest格式如下：

| len | JSON record | checksum | len | JSON record | checksum | len | JSON record | checksum |

在实现所有内容之后，您应该通过之前的所有测试用例。本章不提供新的测试用例。

编码(manifest.rs)：

pub fn add_record_when_init(&self, record: ManifestRecord) -> Result<()> {
    ...
    // 序列化数据
    let mut buf = serde_json::to_vec(&record)?;
    // 计算校验和
    let hash = crc32fast::hash(&buf);
    // 写入数据段长度
    file.write_all(&(buf.len() as u64).to_be_bytes())?;
    // 在数据末尾添加校验和
    buf.put_u32(hash);
    // 将数据、校验和写入文件
    file.write_all(&buf)?;
    file.sync_all()?;
    Ok(())
}

解码(manifest.rs)，就是逆过程：

while buf_ptr.has_remaining() {
    // 读取长度
    let len = buf_ptr.get_u64();
    let slice = &buf_ptr[..len as usize];
    // 反序列化
    let json = serde_json::from_slice::<ManifestRecord>(slice)?;
    buf_ptr.advance(len as usize);
    // 读取并校验校验和
    let checksum = buf_ptr.get_u32();
    if checksum != crc32fast::hash(slice) {
        bail!("checksum mismatched!");
    }
    records.push(json);
}

http://www.kler.cn/a/533665.html

相关文章：

  • 每日Attention学习19——Convolutional Multi-Focal Attention
  • 司库建设-融资需求分析与计划制定
  • redis教程
  • 全栈开发：使用.NET Core WebAPI构建前后端分离的核心技巧（二）
  • 蓝桥杯更小的数（区间DP）
  • 机器学习--1.KNN机器学习入门
  • 将OneDrive上的文件定期备份到移动硬盘
  • 闲聊邵雍的“象数”与古诗有感
  • 从51到STM32：PWM平滑迁移方案
  • make -j$(nproc)——多核加速编译
  • 《Java核心技术 卷II》本地日期
  • 01vue3实战-----前言
  • VSCode中使用EmmyLua插件对Unity的tolua断点调试
  • Go语言并发之美：构建高性能键值存储系统
  • 动静态库的学习
  • golang命令大全11--命令的常见问题与解决方案
  • pandas获取指定日期的行
  • 网络爬虫会对服务器造成哪些影响？
  • 每日Attention学习19——Convolutional Multi-Focal Attention
  • Java学习进阶路线
  • 标准库发送数据深入理解USART
  • Windows下安装mkcert
  • 9. k8s二进制集群之kube-controller-manager部署
  • TensorFlow深度学习实战（6）——回归分析详解
  • Deepseek技术浅析（四）：专家选择与推理机制
  • AI开发模式：ideal或vscode + 插件continue+DeepSeek R1