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的编码如下：
-------------------------------------------------------------------------------------------
| Block Section | Meta Section | Extra |
-------------------------------------------------------------------------------------------
| data block | ... | data block | metadata | meta block offset (u32) |
-------------------------------------------------------------------------------------------timate_size函数
你还需要实现SsTableBuilder的es，如许调用者就可以知道什么时候可以开始一个新的SST来写入数据。函数不需要非常精确。假设数据块数据量远远大于元数据块，我们可以简单地返回数据块的大小为estimate_size。
除了SST构建器，你还需要完成块元数据的编码/解码，以便SsTableBuilder::build可以生成有效的SST文件。
BlockMeta的编码与解码
先实现元信息的编码与解码。
https://img2023.cnblogs.com/blog/3373136/202408/3373136-20240821225936033-20606423.png
如图所示就是将内存中的BlockMeta数组写入到磁盘中，同时能将磁盘中的二进制信息还原回来。
编码
先添加BlockMeta的个数，在写入每个BlockMeta，由于first_key和last_key是可变长的字符串类型，所有需要添加长度信息保证正常解码。
pub fn encode_block_meta(
block_meta: &,
# // remove this allow after you finish
buf: &mut Vec<u8>,
) {
buf.put_u32(block_meta.len() as u32);
for meta in block_meta {
buf.put_u32(meta.offset as u32);
buf.put_u16(meta.first_key.len() as u16);
buf.put(meta.first_key.raw_ref());
buf.put_u16(meta.last_key.len() as u16);
buf.put(meta.last_key.raw_ref());
}
}解码
解码就是编码的逆过程
pub fn decode_block_meta(mut buf: &) -> Vec<BlockMeta> {
let num = buf.get_u32();
let mut block_meta: Vec<BlockMeta> = Vec::with_capacity(num as usize);
for i in 0..num {
let offset: usize = buf.get_u32() as usize;
let first_key_len = buf.get_u16();
let first_key = KeyBytes::from_bytes(buf.copy_to_bytes(first_key_len as usize));
let last_key_len = buf.get_u16();
let last_key = KeyBytes::from_bytes(buf.copy_to_bytes(last_key_len as usize));
block_meta.push(BlockMeta {
offset,
first_key,
last_key,
})
}
block_meta
}SsTableBuilder建造者
成员变量&构造函数
[*]builder:BlockBuilder
[*]first_key:存储的第一个key，用于加快查找
[*]last_key:存储的末了一个key，用于加快查找
[*]data:Block编码后的数据
[*]meta:元信息
[*]block_size:每个Block的大小
构造函数：
pub fn new(block_size: usize) -> Self {
SsTableBuilder {
builder: BlockBuilder::new(block_size),
first_key: Vec::new(),
last_key: Vec::new(),
data: Vec::new(),
meta: Vec::new(),
block_size,
}
}finish_block
存在两种情况大概，大概会新生成一个Block用于存储数据：
[*]Block存不数据
[*]SsTableBuilder调用build生成SsTable，不再新增数据
fn finish_block(&mut self) {
let builder = std::mem::replace(&mut self.builder, BlockBuilder::new(self.block_size));
let encoded_block = builder.build().encode();
self.meta.push(BlockMeta {
offset: self.data.len(),
first_key: KeyBytes::from_bytes(self.first_key.clone().into()),
last_key: KeyBytes::from_bytes(self.last_key.clone().into()),
});
self.data.append(&mut encoded_block.to_vec())
}先利用std::mem::replace将self.builder中的数据替换成空的对象，将存满数据的对象返回赋值给builder。
调用builder的build()函数生成Block对象，再调用encode()编码出二进制数据encoded_block。
将元信息添加进meta中，将编码后的二进制数据添加进data。
add操作
pub fn add(&mut self, key: KeySlice, value: &) {
if self.first_key.is_empty() {
self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
}
self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();
if !self.builder.add(key, value) {
self.finish_block();
self.builder.add(key, value);
}
}判断当前Block块可否添加进当前Block，如果不能则调用上述finish_block函数，再进行添加。同时保存用于每个Block的first_key、last_key。
pub fn add(&mut self, key: KeySlice, value: &) {
if self.first_key.is_empty() {
self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
}
if !self.builder.add(key, value) {
self.finish_block();
self.builder.add(key, value);
self.first_key = Bytes::copy_from_slice(key.raw_ref()).into();
}
self.last_key = Bytes::copy_from_slice(key.raw_ref()).into();
}build操作
就是将SsTableBuilder建造者中保存的数据，写入磁盘：
pub fn build(
mut self,
id: usize,
block_cache: Option<Arc<BlockCache>>,
path: impl AsRef<Path>,
) -> Result<SsTable> {
self.finish_block();
let mut buf = self.data;
let meta_offset = buf.len();
BlockMeta::encode_block_meta(&self.meta, &mut buf);
buf.put_u32(meta_offset as u32);
let file = FileObject::create(path.as_ref(), buf)?;
Ok(SsTable {
id,
file,
first_key: self.meta.first().unwrap().first_key.clone(),
last_key: self.meta.last().unwrap().last_key.clone(),
block_meta: self.meta,
block_meta_offset: meta_offset,
block_cache,
bloom: None,
max_ts: 0,
})
}按照文档说明先写入数据部门，再写入元数据部门，末了写入元数据的偏移距离。
SsTable读取
就是编码的逆过程，即SsTable对象的open方法：
pub fn open(id: usize, block_cache: Option<Arc<BlockCache>>, file: FileObject) -> Result<Self> {
let len = file.1;
let meta_block_offset = (&file.read(len - 4, 4)?[..]).get_u32();
let len = len - meta_block_offset as u64 - 4;
let meta_block = &file.read(meta_block_offset as u64, len)?[..];
let block_meta = BlockMeta::decode_block_meta(meta_block);
Ok(SsTable {
file,
block_meta_offset: meta_block_offset as usize,
id,
block_cache,
first_key: block_meta.first().unwrap().first_key.clone(),
last_key: block_meta.last().unwrap().last_key.clone(),
bloom: None,
block_meta: block_meta,
max_ts: 0,
})
}Task 2-SST Iterator
<blockquote>在此任务中，您需要修改：
src/table/iterator.rs
src/table.rs与BlockIterator类似，您需要在SST上实现一个迭代器。请注意，您应该按需加载数据。比方，如果您的迭代器位于块1，则在到达下一个块之前，不应该在内存中保存任何其他块内容。
SsTableIterator应该实现StorageIterator特性，以便未来可以与其他迭代器组合利用。
有一点需要注意的是find_to_key函数。基本上，您需要对块元数据执行二进制搜索，以找到大概包罗键的块。有大概key在LSM树中不存在，所以块迭代器在一次查找后立即失效。比方：
--------------------------------------
| block 1 | block 2 | block meta |
--------------------------------------
| a, b, c | e, f, g | 1: a/c, 2: e/g |
--------------------------------------
我们发起只利用每个块的第一个键来执行二分查找，以低沉实现的复杂性。如果我们在这个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(())}find_block_idx
在刚刚的函数实现中，需要为SsTable对象实现find_block_idx方法。找到末了一个first_keyusize { 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); }}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]