mini-lsm通关笔记Week1Day4

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

Task 1-SST Builder

在此任务中，您需要修改：
src/table/builder.rs
src/table.rs
SST由存储在磁盘上的数据块和索引块组成。通常，数据块都是懒加载的-直到用户发出哀求，它们才会被加载到内存中。索引块也可以按需加载，但在本教程中，我们简单假设所有SST索引块（元信息块）都可以放入内存（实际上我们没有索引块的实现）。通常，SST文件的大小为256MB。
SST构建器类似于之前实现的BlockBuilder——用户将在构建器上调用add。你应该在SST builder中维护一个BlockBuilder，并在须要时拆分块。此外，你还需要维护块元数据BlockMeta，其中包罗每个块中的第一个/末了一个键以及每个块的偏移量。build函数将对SST进行编码，利用FileObject::create将所有内容写入磁盘，并返回一个SsTable对象。
SST的编码如下：

1. -------------------------------------------------------------------------------------------
2. |         Block Section         |          Meta Section         |          Extra          |
3. -------------------------------------------------------------------------------------------
4. | data block | ... | data block |            metadata           | meta block offset (u32) |
5. -------------------------------------------------------------------------------------------

复制代码

timate_size函数
你还需要实现SsTableBuilder的es，如许调用者就可以知道什么时候可以开始一个新的SST来写入数据。函数不需要非常精确。假设数据块数据量远远大于元数据块，我们可以简单地返回数据块的大小为estimate_size。
除了SST构建器，你还需要完成块元数据的编码/解码，以便SsTableBuilder::build可以生成有效的SST文件。

BlockMeta的编码与解码

先实现元信息的编码与解码。

如图所示就是将内存中的BlockMeta数组写入到磁盘中，同时能将磁盘中的二进制信息还原回来。
编码

先添加BlockMeta的个数，在写入每个BlockMeta，由于first_key和last_key是可变长的字符串类型，所有需要添加长度信息保证正常解码。

1. pub fn encode_block_meta(
2.     block_meta: &[BlockMeta],
3.     #[allow(clippy::ptr_arg)] // remove this allow after you finish
4.     buf: &mut Vec<u8>,
5. ) {
6.     buf.put_u32(block_meta.len() as u32);
7.     for meta in block_meta {
8.         buf.put_u32(meta.offset as u32);
9.         buf.put_u16(meta.first_key.len() as u16);
10.         buf.put(meta.first_key.raw_ref());
11.         buf.put_u16(meta.last_key.len() as u16);
12.         buf.put(meta.last_key.raw_ref());
13.     }
14. }

复制代码

解码

解码就是编码的逆过程

1. pub fn decode_block_meta(mut buf: &[u8]) -> Vec<BlockMeta> {
2.     let num = buf.get_u32();
3.     let mut block_meta: Vec<BlockMeta> = Vec::with_capacity(num as usize);
4.     for i in 0..num {
5.         let offset: usize = buf.get_u32() as usize;
6.         let first_key_len = buf.get_u16();
7.         let first_key = KeyBytes::from_bytes(buf.copy_to_bytes(first_key_len as usize));
8.         let last_key_len = buf.get_u16();
9.         let last_key = KeyBytes::from_bytes(buf.copy_to_bytes(last_key_len as usize));
10.         block_meta.push(BlockMeta {
11.             offset,
12.             first_key,
13.             last_key,
14.         })
15.     }
16.     block_meta
17. }

复制代码

SsTableBuilder建造者

成员变量&构造函数

• builder:BlockBuilder
  
• first_key:存储的第一个key，用于加快查找
  
• last_key:存储的末了一个key，用于加快查找
  
• data:Block编码后的数据
  
• meta:元信息
  
• block_size:每个Block的大小
  

构造函数：

1. pub fn new(block_size: usize) -> Self {
2.     SsTableBuilder {
3.         builder: BlockBuilder::new(block_size),
4.         first_key: Vec::new(),
5.         last_key: Vec::new(),
6.         data: Vec::new(),
7.         meta: Vec::new(),
8.         block_size,
9.     }
10. }

复制代码

finish_block

存在两种情况大概，大概会新生成一个Block用于存储数据：

• Block存不数据
  
• SsTableBuilder调用build生成SsTable，不再新增数据
  

1. fn finish_block(&mut self) {
2.     let builder = std::mem::replace(&mut self.builder, BlockBuilder::new(self.block_size));
3.     let encoded_block = builder.build().encode();
4.     self.meta.push(BlockMeta {
5.         offset: self.data.len(),
6.         first_key: KeyBytes::from_bytes(self.first_key.clone().into()),
7.         last_key: KeyBytes::from_bytes(self.last_key.clone().into()),
8.     });
9.     self.data.append(&mut encoded_block.to_vec())
10. }

复制代码

先利用std::mem::replace将self.builder中的数据替换成空的对象，将存满数据的对象返回赋值给builder。
调用builder的build()函数生成Block对象，再调用encode()编码出二进制数据encoded_block。
将元信息添加进meta中，将编码后的二进制数据添加进data。
add操作

1. pub fn add(&mut self, key: KeySlice, value: &[u8]) {
2.     if self.first_key.is_empty() {
3.         self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
4.     }
6.     self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();
8.     if !self.builder.add(key, value) {
9.         self.finish_block();
10.         self.builder.add(key, value);
11.     }
12. }

复制代码

判断当前Block块可否添加进当前Block，如果不能则调用上述finish_block函数，再进行添加。同时保存用于每个Block的first_key、last_key。

1. pub fn add(&mut self, key: KeySlice, value: &[u8]) {
2.     if self.first_key.is_empty() {
3.         self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
4.     }
6.     if !self.builder.add(key, value) {
7.         self.finish_block();
8.         self.builder.add(key, value);
9.         self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
10.     }
12.     self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();
13. }

复制代码

build操作

就是将SsTableBuilder建造者中保存的数据，写入磁盘：

1. pub fn build(
2.     mut self,
3.     id: usize,
4.     block_cache: Option<Arc<BlockCache>>,
5.     path: impl AsRef<Path>,
6. ) -> Result<SsTable> {
7.     self.finish_block();
8.     let mut buf = self.data;
9.     let meta_offset = buf.len();
10.     BlockMeta::encode_block_meta(&self.meta, &mut buf);
11.     buf.put_u32(meta_offset as u32);
12.     let file = FileObject::create(path.as_ref(), buf)?;
13.     Ok(SsTable {
14.         id,
15.         file,
16.         first_key: self.meta.first().unwrap().first_key.clone(),
17.         last_key: self.meta.last().unwrap().last_key.clone(),
18.         block_meta: self.meta,
19.         block_meta_offset: meta_offset,
20.         block_cache,
21.         bloom: None,
22.         max_ts: 0,
23.     })
24. }

复制代码

按照文档说明先写入数据部门，再写入元数据部门，末了写入元数据的偏移距离。
SsTable读取

就是编码的逆过程，即SsTable对象的open方法：

1. pub fn open(id: usize, block_cache: Option<Arc<BlockCache>>, file: FileObject) -> Result<Self> {
2.     let len = file.1;
3.     let meta_block_offset = (&file.read(len - 4, 4)?[..]).get_u32();
4.     let len = len - meta_block_offset as u64 - 4;
5.     let meta_block = &file.read(meta_block_offset as u64, len)?[..];
6.     let block_meta = BlockMeta::decode_block_meta(meta_block);
7.     Ok(SsTable {
8.         file,
9.         block_meta_offset: meta_block_offset as usize,
10.         id,
11.         block_cache,
12.         first_key: block_meta.first().unwrap().first_key.clone(),
13.         last_key: block_meta.last().unwrap().last_key.clone(),
14.         bloom: None,
15.         block_meta: block_meta,
16.         max_ts: 0,
17.     })
18. }

复制代码

Task 2-SST Iterator

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

1. src/table/iterator.rs
2. src/table.rs

复制代码

与BlockIterator类似，您需要在SST上实现一个迭代器。请注意，您应该按需加载数据。比方，如果您的迭代器位于块1，则在到达下一个块之前，不应该在内存中保存任何其他块内容。
SsTableIterator应该实现StorageIterator特性，以便未来可以与其他迭代器组合利用。
有一点需要注意的是find_to_key函数。基本上，您需要对块元数据执行二进制搜索，以找到大概包罗键的块。有大概key在LSM树中不存在，所以块迭代器在一次查找后立即失效。比方：

1. --------------------------------------
2. | block 1 | block 2 |   block meta   |
3. --------------------------------------
4. | a, b, c | e, f, g | 1: a/c, 2: e/g |
5. --------------------------------------

复制代码

我们发起只利用每个块的第一个键来执行二分查找，以低沉实现的复杂性。如果我们在这个SST中查找b，则相当简单——利用二分查找，我们可以知道块1包罗键a Result {    let mut index = self.table.find_block_idx(key);    self.blk_iter = BlockIterator::create_and_seek_to_key(self.table.read_block(index)?, key);    if !self.blk_iter.is_valid() && index != self.table.num_of_blocks() - 1 {        index += 1;        self.blk_iter = BlockIterator::create_and_seek_to_first(self.table.read_block(index)?);    }    self.blk_idx = index;    Ok(())}[/code]find_block_idx


在刚刚的函数实现中，需要为SsTable对象实现find_block_idx方法。找到末了一个first_key  usize {    self.block_meta        .partition_point(|meta| meta.first_key.as_key_slice()  Result {    if let Some(ref block_cache) = self.block_cache {        let blk = block_cache            .try_get_with((self.id, block_idx), || self.read_block(block_idx))            .map_err(|e| anyhow!("{}", e))?;        Ok(blk)    } else {        return self.read_block(block_idx);    }}[/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。