Quotient Filterを書く

「大規模データセットのアルゴリズムとデータ構造」という本があります。 以前、この本の第３章で紹介される「ブルームフィルタ」をRustで実装しました。

今回は同じ章で紹介される「Quotient Filter（商フィルタ）」をRustで実装してみました。

Quotient FilterはBloom Filterと同様の確率的データ構造ですが、削除操作に対応し、よりメモリ効率的な設計になっています。

Rustでの実装

#[derive(Clone, Copy)]
struct Slot<const RBYTE: usize> {
    /// Metadata bits packed into a single byte
    /// - Bit 0: is_occupied
    /// - Bit 1: is_continuation
    /// - Bit 2: is_shifted
    /// 
    /// Rust's bool takes 1 byte, so we use bit packing to save space
    metadata_bits: u8,

    /// Rust's bool takes 1 bytes, so we use u8 array to store bits
    reminder: [u8; RBYTE],
}

impl <const RBYTE: usize> Slot<RBYTE> {
    const IS_OCCUPIED_MASK: u8 = 0b0000_0001;
    const IS_CONTINUATION_MASK: u8 = 0b0000_0010;
    const IS_SHIFTED_MASK: u8 = 0b0000_0100;

    fn new(bucket_occupied: bool, is_continuation: bool, is_shifted: bool, reminder: [u8; RBYTE]) -> Self {
        let mut metadata_bits = 0;
        if bucket_occupied {
            metadata_bits |= Self::IS_OCCUPIED_MASK;
        }
        if is_continuation {
            metadata_bits |= Self::IS_CONTINUATION_MASK;
        }
        if is_shifted {
            metadata_bits |= Self::IS_SHIFTED_MASK;
        }
        Slot {
            metadata_bits,
            reminder,
        }
    }

    fn is_empty(&self) -> bool {
        self.metadata_bits == 0
    }

    /// true if quotient index is occupied
    fn is_occupied(&self) -> bool {
        (self.metadata_bits & Self::IS_OCCUPIED_MASK) != 0
    }

    fn set_occupied(&mut self, value: bool) {
        if value {
            self.metadata_bits |= Self::IS_OCCUPIED_MASK;
        } else {
            self.metadata_bits &= !Self::IS_OCCUPIED_MASK;
        }
    }

    fn is_continuation(&self) -> bool {
        (self.metadata_bits & Self::IS_CONTINUATION_MASK) != 0
    }

    fn set_continuation(&mut self, value: bool) {
        if value {
            self.metadata_bits |= Self::IS_CONTINUATION_MASK;
        } else {
            self.metadata_bits &= !Self::IS_CONTINUATION_MASK;
        }
    }

    fn is_shifted(&self) -> bool {
        (self.metadata_bits & Self::IS_SHIFTED_MASK) != 0
    }

    fn set_shifted(&mut self, value: bool) {
        if value {
            self.metadata_bits |= Self::IS_SHIFTED_MASK;
        } else {
            self.metadata_bits &= !Self::IS_SHIFTED_MASK;
        }
    }
}

impl <const RBYTE: usize> Default for Slot<RBYTE> {
    fn default() -> Self {
        Slot {
            metadata_bits: 0,
            reminder: [0; RBYTE],
        }
    }
}

struct QuotientFilter<const R_BYTES: usize, const SLOT_SIZE: usize, T>
 {
    q_bits: usize,
    r_bits: usize,
    slots: [Slot<R_BYTES>; SLOT_SIZE],
    _phantom: std::marker::PhantomData<T>,

 }

impl  <const R_BYTES: usize, const SLOT_SIZE: usize, T> QuotientFilter<R_BYTES, SLOT_SIZE, T>
where T: AsRef<[u8]> + Clone
 {

    pub fn new(size: usize, r_bits:usize) -> Self{
        let q = size.ilog2() as usize;
        if r_bits * 8 < R_BYTES{
            panic!("r_bits is smaller than R_BYTES");
        }

        let m = SLOT_SIZE.ilog2() as usize;
        let r = m - q;

        QuotientFilter {
            q_bits: q,
            r_bits: r,
            slots: [Slot::default(); SLOT_SIZE],
            _phantom: std::marker::PhantomData,
        }

    }

    /// Returns the index of the start of the cluster for the given quotient index
    fn find_start_of_cluster(&self, index: usize) -> usize {
        // 簡単な実装：クラスターの開始を見つける
        let mut pos = index;
        
        // 後方に向かってクラスターの開始を探す
        while pos > 0 {
            let prev_pos = pos - 1;
            if !self.slots[prev_pos].is_occupied() && !self.slots[prev_pos].is_shifted() {
                break;
            }
            pos = prev_pos;
        }
        
        // wrap around の場合の処理（簡単な実装のため今は省略）
        pos
    }

    /// 簡単な挿入位置検索
    fn find_insert_position(&mut self, target_index: usize) -> (usize, bool) {
        // 目標インデックスが空いているかチェック
        if self.slots[target_index].is_empty() {
            self.slots[target_index].set_occupied(true);
            return (target_index, true); // head of run
        }
        
        // 空いているスロットを前方に向かって探す
        let mut pos = target_index;
        for _ in 0..SLOT_SIZE {
            pos = (pos + 1) % SLOT_SIZE;
            if self.slots[pos].is_empty() {
                self.slots[target_index].set_occupied(true);
                return (pos, false); // not head of run
            }
        }
        
        // 全てのスロットが埋まっている場合（エラー）
        panic!("Quotient filter is full");
    }

    /// Insert data into the quotient filter
    /// 
    /// Algorithm:
    /// 1. Hash the data to get a fingerprint
    /// 2. Split the fingerprint into quotient and remainder
    /// 3. Find the start of the cluseter
    /// 4. Insert the remainder into the appropriate slot

    pub fn insert(&mut self, data: &T) {
        let fingerprint = hash_64(data.clone());
        let index = ((fingerprint >> self.r_bits) as usize) % SLOT_SIZE;
        let remainder = fingerprint & ((1u64 << self.r_bits) - 1);
        let remainder_bytes = downcast_usize_to_u8_array::<R_BYTES>(remainder as usize);  

        let (insert_pos, head_of_run) = self.find_insert_position(index);

        // 挿入位置に新しいデータを設定
        self.slots[insert_pos].reminder.copy_from_slice(&remainder_bytes);
        self.slots[insert_pos].set_continuation(!head_of_run);
        self.slots[insert_pos].set_shifted(index != insert_pos);
    }

    pub fn lookup(&self, data: &T) -> bool {
        let fingerprint = hash_64(data.clone());
        let index = ((fingerprint >> self.r_bits) as usize) % SLOT_SIZE;
        let remainder = fingerprint & ((1u64 << self.r_bits) - 1);
        let remainder_bytes = downcast_usize_to_u8_array::<R_BYTES>(remainder as usize);  

        if !self.slots[index].is_occupied() {
            return false;
        }

        // 簡単な実装：目標インデックスから前方に検索
        let mut pos = index;
        for _ in 0..SLOT_SIZE {
            if !self.slots[pos].is_empty() && self.slots[pos].reminder == remainder_bytes {
                return true;
            }
            pos = (pos + 1) % SLOT_SIZE;
            
            // 空のスロットに到達したら終了
            if self.slots[pos].is_empty() {
                break;
            }
        }
        
        false
    }
}

fn hash_64<T>(data: T) -> u64
where T: AsRef<[u8]> + Clone
{
    let mut cursor = std::io::Cursor::new(data.clone());
    let hash_128 = murmur3::murmur3_x64_128(&mut cursor, 0 as u32).unwrap();
    // 128bitハッシュの上位64bitを取得
    (hash_128 >> 64) as u64
}

fn downcast_usize_to_u8_array<const R: usize>(value: usize) -> [u8; R] {
    let mut arr = [0u8; R];
    for i in 0..R {
        arr[R - 1 - i] = ((value >> (i * 8)) & 0xFF) as u8;
    }
    arr
}

fn bit_crash(original: usize, bits: usize) -> usize{
    original >> bits
}

実装のポイント：

• スロット構造: メタデータビット（occupied, continuation, shifted）をパッキングしてメモリ効率を向上
• ハッシュ値の分割: quotient（スロットインデックス）とremainder（格納値）に分離
• クラスター管理: ハッシュ衝突時の効率的な処理

Bloom Filterとの比較

特徴	Bloom Filter	Quotient Filter
削除操作	不可	可能
偽陽性率	あり	あり
偽陰性率	なし	なし
メモリ効率	良い	より良い
実装複雑度	簡単	複雑
クラスター処理	なし	あり

Quotient Filterは削除操作が必要で、メモリ効率を重視するアプリケーションに適しています。

ダミーデータでのテスト

ブルームフィルター記事と同じダミーデータ生成スクリプトが使用できます：

#!/usr/bin/env python3
"""Generate 10**6 random integers in [0, 10**12] and write to dummy_data.txt."""

import random
from pathlib import Path

COUNT = 10 ** 6
LOWER = 0
UPPER = 10 ** 12
OUTPUT = Path("dummy_data.txt")
CHUNK_SIZE = 10_000


def main() -> None:
    rng = random.Random()
    with OUTPUT.open("w", encoding="utf-8") as file:
        buffer: list[str] = []
        for _ in range(COUNT):
            buffer.append(str(rng.randint(LOWER, UPPER)))
            if len(buffer) >= CHUNK_SIZE:
                file.write("\n".join(buffer))
                file.write("\n")
                buffer.clear()
        if buffer:
            file.write("\n".join(buffer))
            file.write("\n")


if __name__ == "__main__":
    main()

まとめ

Quotient Filterは、Bloom Filterに削除機能とメモリ効率の改善を加えた確率的データ構造です。実装は複雑になりますが、柔軟性と効率性を求める場合に有用です。