Tasks

Task 1: Bloom Filters

布隆过滤器是维护一组键的概率数据结构。布隆过滤器的工作原理：插入的时候对键用不同的哈希函数求哈希值，并且将布隆过滤器的对应比特位置为 1；在查找的时候检查布隆过滤器的对应位，如果对应位为 0 则一定不在集合中。首先是从键的哈希值创建布隆过滤器：依次对每个键求哈希值，一个键设置 k 个位，将对应位设置成 true。

/// Build bloom filter from key hashes
pub fn build_from_key_hashes(keys: &[u32], bits_per_key: usize) -> Self {
    ...
    // TODO: build the bloom filter
    for h in keys {
        let mut h = *h;
        let delta = h.rotate_left(15);
        for _ in 0..k {
            let bit_pos = (h as usize) % nbits;
            filter.set_bit(bit_pos, true);
            h = h.wrapping_add(delta);
        }
    }
    ...
}

在判断是否包含的时候也是同样的步骤，判断对应位是否为 true，如果不为则一定不在集合中：

/// Check if a bloom filter may contain some data
pub fn may_contain(&self, mut h: u32) -> bool {
    if self.k > 30 {
        // potential new encoding for short bloom filters
        true
    } else {
        let nbits = self.filter.bit_len();
        let delta = h.rotate_left(15);

        // TODO: probe the bloom filter
        for _ in 0..self.k {
            let bit_pos = h % (nbits as u32);
            if !self.filter.get_bit(bit_pos as usize) {
                return false;
            }
            h = h.wrapping_add(delta);
        }

        true
    }
}

Task 2: Integrate Bloom Filter on the Read Path

在 SST 文件后，需要添加布隆过滤器的长度，和相应的偏移量。向 SST 添加数据时要加上键的哈希值：

pub fn add(&mut self, key: KeySlice, value: &[u8]) {
    ...
    self.key_hashes.push(farmhash::fingerprint32(key.raw_ref()));
    ...
}

在构建的时候要添加布隆过滤器的元数据值：先从键的哈希值构建布隆过滤器，再将布隆过滤器编码，最后加上偏移量。

pub fn build(
    mut self,
    id: usize,
    block_cache: Option<Arc<BlockCache>>,
    path: impl AsRef<Path>,
) -> Result<SsTable> {
    ...
    let bloom = Bloom::build_from_key_hashes(
        &self.key_hashes,
        Bloom::bloom_bits_per_key(self.key_hashes.len(), 0.01),
    );
    let bloom_offset = buf.len();
    bloom.encode(&mut buf);
    buf.put_u32(bloom_offset as u32);

    ...
    Ok(SsTable {
        ...
        bloom: Some(bloom),
        ...
    })
}

相应的，在打开 SST 时就要先解码读出布隆过滤器：先读出其偏移量，再根据偏移量解码出布隆过滤器

pub fn open(id: usize, block_cache: Option<Arc<BlockCache>>, file: FileObject) -> Result<Self> {
    let raw_bloom_offset = file.read(len - 4, 4)?;
    let bloom_offset = (&raw_bloom_offset[..]).get_u32() as u64;
    let raw_bloom = file.read(bloom_offset, len - bloom_offset - 4)?;
    let bloom_filter = Bloom::decode(&raw_bloom[..])?;

    let raw_meta_offset = file.read(bloom_offset - 4, 4)?;
    ...

    Ok(Self {
        ...
        bloom: Some(bloom_filter),
        ...
    })
}

Task 3: Key Prefix Encoding + Decoding

这里实现的是一种编码手段，因为 SST 文件是顺序存储键的，所以用户存储的可能是前缀相同的键。所以可以用 前缀长度 | 后缀长度 | 后缀 来表示。

首先要有一个计算前缀长度，也就是从第一个字符起共同的部分：

fn compute_overlap(first_key: KeySlice, key: KeySlice) -> usize {
    let mut i = 0;
    while i < first_key.len() && i < key.len() {
        if first_key.raw_ref()[i] != key.raw_ref()[i] {
            break;
        }
        i += 1;
    }
    i
}

添加元素的时候就要进行编码。先调用函数计算前缀长度，然后将其写入数据，再写入剩余部分的程度以及剩余的部分。

#[must_use]
pub fn add(&mut self, key: KeySlice, value: &[u8]) -> bool {
    ...
    let overlap = compute_overlap(self.first_key.as_key_slice(), key);
    self.data.put_u16(overlap as u16);
    self.data.put_u16((key.len() - overlap) as u16);
    self.data.put(&key.raw_ref()[overlap..]);
    ...
}

在扫描的时候先读取前缀的长度和剩余长度，再读出剩余部分，根据前缀和剩余部分组成完整的键。

fn seek_to(&mut self, idx: usize) {
    ...
    let overlap_len = entry.get_u16() as usize;
    let key_len = entry.get_u16() as usize;
    let key = &entry[..key_len];
    self.key.clear();
    self.key.append(&self.first_key.raw_ref()[..overlap_len]);
    self.key.append(key);
    ...
    let value_begin = offset + SIZEOF_U16 + SIZEOF_U16 + SIZEOF_U16 + key_len;  // FIX
    ...
}

还要注意第一个键是没有比较对象的，所以相似的长度为 0：

impl Block {
    fn get_first_key(&self) -> KeyVec {
        let mut buf = &self.data[..];
        buf.get_u16();
        let key_len = buf.get_u16() as usize;
        let key = &buf[..key_len];
        KeyVec::from_vec(key.to_vec())
    }
}

Result

Test Your Understanding

How does the bloom filter help with the SST filtering process? What kind of information can it tell you about a key? (may not exist/may exist/must exist/must not exist) 检查所有对应的比特位，如果有一个是 false 那么就一定不存在，反之则是有可能存在。
Consider the case that we need a backward iterator. Does our key compression affect backward iterators?
这种压缩方案只依赖第一个键，因此对后序遍历影响不大。
Can you use bloom filters on scan? 可以的，通过布隆过滤器排除不可能的值。
What might be the pros/cons of doing key-prefix encoding over adjacent keys instead of with the first key in the block?
优势：在一个 block 中如果大量键有相同的前缀，可以减少时间
劣势：如果没啥相同的前缀，就会导致空间的浪费

Prince's Blog

Day7: SST Optimizations