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

mini-lsm通关笔记Week2Day7

news 2025/7/3 8:36:17

项目地址：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 finishbuf: &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);
}