Rustデータベースカーネル：LSM-Treeストレージエンジンをゼロから構築する6つのコアモジュール
编程语言
データベースカーネルの4つの課題、LSM-Treeはどう突破するか
B+Treeの書き込み増幅は深刻——ランダム書き込みのたびにページ全体をフラッシュ；LSM-Treeの概念は複雑——MemTable、SSTable、Compactionが入れ子になり混乱；Compaction戦略の選択が困難——Leveled、Tiered、FIFOそれぞれトレードオフ；WALの実装が難しい——シーケンシャル書き込みで永続性を保証するがクラッシュリカバリロジックが煩雑。2026年、Rust + LSM-Tree + tokioの組み合わせがデータベースストレージエンジンのベストプラクティスを提示：ロックフリー並発スキップリストMemTable、順序付きSSTableフラッシュ、WALクラッシュリカバリ、階層型Compaction領域回収——B+Treeより10倍の書き込み性能、読み取り増幅は制御可能。
本記事では6つのコアモジュールから、MemTable→SSTable→WAL→Compaction→Bloom Filter→Block Cacheの完全な実践を解説。
主要な学び
- crossbeamスキップリストによるMemTable並発読み書きの実装を習得
- SSTableディスクフォーマット設計とBlockインデックス機構を理解
- WAL先行書き込みログでクラッシュリカバリ一貫性を実現
- Leveled Compaction戦略で領域回収と読み取り増幅を低減
- Bloom FilterとBlock Cacheでポイントクエリパスを高速化
目次
- コア概念一覧
- 問題分析：5つの課題
- モジュール1：MemTableインメモリテーブル
- モジュール2：SSTableディスク永続化
- モジュール3：WAL先行書き込みログ
- モジュール4：Compactionマージ戦略
- モジュール5：Bloom Filter
- モジュール6：Block Cache
- 落とし穴ガイド：5つのよくある罠
- エラートラブルシューティング：10のよくあるエラー
- 高度な最適化のヒント
- 比較分析
- まとめと展望
- オンラインツール推奨
コア概念一覧
| 概念 | 説明 |
|---|---|
| LSM-Tree | Log-Structured Merge-Tree、追記書き込みの順序付き構造、B+Treeより書き込み性能が大幅に優位 |
| MemTable | メモリ上の順序付きキー値テーブル、通常スキップリストで実装、書き込み満了後にフリーズしてフラッシュ |
| SSTable | Sorted String Table、ディスク上の不変順序付きファイル、Block単位で構成 |
| Compaction | 複数SSTableをマージして重複と削除マーカーを排除、読み取り増幅を低減 |
| WAL | Write-Ahead Log、先行書き込みログでクラッシュ後のデータ損失を防止 |
| Bloom Filter | 確率的データ構造、KeyがSSTableに存在する可能性を高速に判定 |
| Block Cache | SSTableのData Blockをキャッシュ、ディスクIOを削減 |
| Sorted Run | Compaction後の重複なし順序付きSSTableグループ |
| Tombstone | 削除マーカー、Compaction時にのみ真に削除 |
アーキテクチャ概要
┌──────────────────────────────────────────────────────┐
│ LSM-Tree Storage Engine │
│ ┌────────────┐ ┌────────────┐ ┌──────────────────┐ │
│ │ Write │ │ Read │ │ Compaction │ │
│ │ Path │ │ Path │ │ Scheduler │ │
│ └─────┬──────┘ └─────┬──────┘ └────────┬─────────┘ │
│ │ │ │ │
│ ┌─────▼──────────────▼─────────────────▼─────────┐ │
│ │ Active MemTable (SkipList) │ WAL (Append) │ │
│ └──────────────┬──────────────────────────────────┘ │
│ │ freeze & flush │
│ ┌──────────────▼──────────────────────────────────┐ │
│ │ L0: [SST-0] [SST-1] [SST-2] (重複許可) │ │
│ │ L1: [SST-3] [SST-4] (Sorted Run) │ │
│ │ L2: [SST-5] [SST-6] [SST-7] (Sorted Run) │ │
│ │ L3: [SST-8] ... [SST-15] (Sorted Run) │ │
│ └─────────────────────────────────────────────────┘ │
│ ┌──────────────┐ ┌──────────────┐ │
│ │Bloom Filter │ │ Block Cache │ │
│ └──────────────┘ └──────────────┘ │
└──────────────────────────────────────────────────────┘
問題分析：5つの課題
| 課題 | ペインポイント | LSMソリューション |
|---|---|---|
| 書き込み増幅と読み取り増幅 | B+Treeランダム書き込み増幅10-30倍、LSM読み取り増幅は多層検索が必要 | MemTableバッチフラッシュ+Compactionマージで書き込み増幅低減、Bloom Filter+Cacheで読み取り増幅低減 |
| Compaction戦略選択 | Leveledは書き込み増幅高、Tieredは空間増幅高、FIFOは永続化に不適 | ハイブリッド戦略：L0はTieredで高速マージ、L1+はLeveledで空間制御 |
| 並発制御 | MemTable読み書き競合、Compactionと読み取り操作の衝突 | crossbeamロックフリースキップリスト+読み書き分離（Active/Immutable MemTable） |
| クラッシュリカバリ | フラッシュ未完了データの損失、WAL部分書き込み | WAL原子書き込み+checksum検証+再起動時リプレイ |
| メモリ管理 | MemTable使用量が制御不能、Block Cache退避戦略 | サイズ閾値でフリーズ+LRU Cacheでメモリ上限を制限 |
モジュール1：MemTableインメモリテーブル
MemTableはLSM-Tree書き込みの最初のステップ——すべての書き込み操作がまずMemTableに入り、書き込み満了後はImmutable MemTableにフリーズしてフラッシュを待機。crossbeam-skiplistはロックフリー並発スキップリストを提供し、RustエコシステムでMemTableに最適なデータ構造。
crossbeamスキップリストベースのMemTable
use crossbeam_skiplist::SkipMap;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;
pub struct MemTable {
table: Arc<SkipMap<Vec<u8>, Vec<u8>>>,
approximate_size: AtomicUsize,
capacity: usize,
}
impl MemTable {
pub fn new(capacity: usize) -> Self {
Self {
table: Arc::new(SkipMap::new()),
approximate_size: AtomicUsize::new(0),
capacity,
}
}
pub fn put(&self, key: Vec<u8>, value: Vec<u8>) {
let entry_size = key.len() + value.len();
self.table.insert(key, value);
self.approximate_size.fetch_add(entry_size, Ordering::Relaxed);
}
pub fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
self.table.get(key).map(|entry| entry.value().clone())
}
pub fn delete(&self, key: Vec<u8>) {
self.table.insert(key, Vec::new());
}
pub fn is_full(&self) -> bool {
self.approximate_size.load(Ordering::Relaxed) >= self.capacity
}
pub fn iter(&self) -> impl Iterator<Item = (Vec<u8>, Vec<u8>)> + '_ {
self.table.iter().map(|entry| {
(entry.key().clone(), entry.value().clone())
})
}
pub fn len(&self) -> usize {
self.table.len()
}
}
MemTableフリーズと切り替え
use tokio::sync::RwLock;
pub struct MemTableManager {
active: Arc<RwLock<MemTable>>,
immutable: Arc<RwLock<Option<MemTable>>>,
capacity: usize,
}
impl MemTableManager {
pub fn new(capacity: usize) -> Self {
Self {
active: Arc::new(RwLock::new(MemTable::new(capacity))),
immutable: Arc::new(RwLock::new(None)),
capacity,
}
}
pub async fn put(&self, key: Vec<u8>, value: Vec<u8>) -> Result<(), String> {
let active = self.active.read().await;
if active.is_full() {
drop(active);
self.freeze_and_switch().await?;
let active = self.active.read().await;
active.put(key, value);
} else {
active.put(key, value);
}
Ok(())
}
pub async fn get(&self, key: &[u8]) -> Option<Vec<u8>> {
if let Some(val) = self.active.read().await.get(key) {
return Some(val);
}
self.immutable.read().await.as_ref().and_then(|t| t.get(key))
}
async fn freeze_and_switch(&self) -> Result<(), String> {
let mut active = self.active.write().await;
let mut immutable = self.immutable.write().await;
if immutable.is_some() {
return Err("Immutable MemTable still flushing".into());
}
let frozen = std::mem::replace(&mut *active, MemTable::new(self.capacity));
*immutable = Some(frozen);
Ok(())
}
pub async fn take_immutable(&self) -> Option<MemTable> {
self.immutable.write().await.take()
}
}
モジュール2：SSTableディスク永続化
SSTableはLSM-Treeのディスク保存単位——不変、順序付き、Block単位で構成。各SSTableはData Block、Meta Block、Index Block、Footerで構成され、Index Blockは各Data Blockの開始Keyとオフセットを記録。
SSTableフォーマット設計
┌─────────────────────────────────────┐
│ Data Block 0 [key1, val1, ...] │
│ Data Block 1 [keyN, valN, ...] │
│ ... │
│ Meta Block (Bloom Filter) │
│ Index Block [block0_offset, ...] │
│ Footer [meta_offset, index_offset] │
└─────────────────────────────────────┘
SSTable Builder
use std::io::{BufWriter, Write};
use std::fs::File;
use crc32fast::Hasher;
const BLOCK_SIZE: usize = 4 * 1024;
pub struct SsTableBuilder {
data_blocks: Vec<Vec<u8>>,
current_block: Vec<u8>,
index_entries: Vec<IndexEntry>,
first_key_in_block: Option<Vec<u8>>,
block_count: usize,
}
#[derive(Clone)]
pub struct IndexEntry {
pub first_key: Vec<u8>,
pub offset: u64,
pub length: u32,
}
impl SsTableBuilder {
pub fn new() -> Self {
Self {
data_blocks: vec![],
current_block: vec![],
index_entries: vec![],
first_key_in_block: None,
block_count: 0,
}
}
pub fn add(&mut self, key: &[u8], value: &[u8]) {
if self.first_key_in_block.is_none() {
self.first_key_in_block = Some(key.to_vec());
}
let entry_len = 4 + key.len() + 4 + value.len();
if self.current_block.len() + entry_len > BLOCK_SIZE && !self.current_block.is_empty() {
self.finish_block();
}
if self.first_key_in_block.is_none() {
self.first_key_in_block = Some(key.to_vec());
}
self.current_block.extend_from_slice(&(key.len() as u32).to_le_bytes());
self.current_block.extend_from_slice(key);
self.current_block.extend_from_slice(&(value.len() as u32).to_le_bytes());
self.current_block.extend_from_slice(value);
}
fn finish_block(&mut self) {
if self.current_block.is_empty() {
return;
}
let offset = self.data_blocks.len() as u64 * BLOCK_SIZE as u64;
let length = self.current_block.len() as u32;
self.index_entries.push(IndexEntry {
first_key: self.first_key_in_block.take().unwrap_or_default(),
offset,
length,
});
let mut block = std::mem::take(&mut self.current_block);
block.resize(BLOCK_SIZE, 0);
self.data_blocks.push(block);
self.block_count += 1;
}
pub fn build(mut self, path: &std::path::Path) -> std::io::Result<()> {
self.finish_block();
let file = File::create(path)?;
let mut writer = BufWriter::new(file);
for block in &self.data_blocks {
writer.write_all(block)?;
}
let index_offset = self.data_blocks.len() as u64 * BLOCK_SIZE as u64;
for entry in &self.index_entries {
writer.write_all(&(entry.first_key.len() as u32).to_le_bytes())?;
writer.write_all(&entry.first_key)?;
writer.write_all(&entry.offset.to_le_bytes())?;
writer.write_all(&entry.length.to_le_bytes())?;
}
writer.write_all(&index_offset.to_le_bytes())?;
writer.flush()?;
Ok(())
}
}
モジュール3：WAL先行書き込みログ
WAL（Write-Ahead Log）はLSM-Treeのクラッシュリカバリの保障——毎回の書き込み操作がまずWALに追記され、その後MemTableに書き込まれる。クラッシュ後の再起動でWALをリプレイすればフラッシュ未完了のデータを復旧。
WAL実装
use std::io::{BufWriter, Write, BufReader, Read};
use std::fs::{File, OpenOptions};
use std::path::Path;
use crc32fast::Hasher;
const WAL_RECORD_HEADER_SIZE: usize = 4 + 4 + 4;
pub enum WalRecord {
Put { key: Vec<u8>, value: Vec<u8> },
Delete { key: Vec<u8> },
}
pub struct WalWriter {
writer: BufWriter<File>,
}
impl WalWriter {
pub fn create(path: &Path) -> std::io::Result<Self> {
let file = OpenOptions::new()
.create(true)
.append(true)
.open(path)?;
Ok(Self { writer: BufWriter::new(file) })
}
pub fn append(&mut self, record: &WalRecord) -> std::io::Result<()> {
let mut payload = Vec::new();
match record {
WalRecord::Put { key, value } => {
payload.push(0u8);
payload.extend_from_slice(&(key.len() as u32).to_le_bytes());
payload.extend_from_slice(key);
payload.extend_from_slice(&(value.len() as u32).to_le_bytes());
payload.extend_from_slice(value);
}
WalRecord::Delete { key } => {
payload.push(1u8);
payload.extend_from_slice(&(key.len() as u32).to_le_bytes());
payload.extend_from_slice(key);
}
}
let mut hasher = Hasher::new();
hasher.update(&payload);
let checksum = hasher.finalize();
self.writer.write_all(&checksum.to_le_bytes())?;
self.writer.write_all(&(payload.len() as u32).to_le_bytes())?;
self.writer.write_all(&payload)?;
self.writer.flush()?;
Ok(())
}
}
pub struct WalReplayer;
impl WalReplayer {
pub fn replay(path: &Path) -> std::io::Result<Vec<WalRecord>> {
let file = File::open(path)?;
let mut reader = BufReader::new(file);
let mut records = Vec::new();
loop {
let mut header = [0u8; WAL_RECORD_HEADER_SIZE];
match reader.read_exact(&mut header) {
Ok(()) => {}
Err(_) => break,
}
let checksum = u32::from_le_bytes(header[0..4].try_into().unwrap());
let len = u32::from_le_bytes(header[4..8].try_into().unwrap()) as usize;
let mut payload = vec![0u8; len];
reader.read_exact(&mut payload)?;
let mut hasher = Hasher::new();
hasher.update(&payload);
if hasher.finalize() != checksum {
tracing::warn!("WAL checksum mismatch, stopping replay");
break;
}
let record = match payload[0] {
0 => {
let key_len = u32::from_le_bytes(payload[1..5].try_into().unwrap()) as usize;
let key = payload[5..5 + key_len].to_vec();
let val_len = u32::from_le_bytes(
payload[5 + key_len..9 + key_len].try_into().unwrap()
) as usize;
let value = payload[9 + key_len..9 + key_len + val_len].to_vec();
WalRecord::Put { key, value }
}
1 => {
let key_len = u32::from_le_bytes(payload[1..5].try_into().unwrap()) as usize;
let key = payload[5..5 + key_len].to_vec();
WalRecord::Delete { key }
}
_ => break,
};
records.push(record);
}
Ok(records)
}
}
モジュール4：Compactionマージ戦略
CompactionはLSM-Treeの領域回収の中核——複数SSTableをマージして重複KeyとTombstoneを排除し、読み取り増幅を低減。Leveled Compactionは各レベルに1つのSorted Runのみを保証し、空間増幅を制御可能だが書き込み増幅は高め。
Leveled Compaction実装
use std::collections::BTreeMap;
use std::path::PathBuf;
pub struct CompactionScheduler {
base_dir: PathBuf,
level_size_multiplier: usize,
max_level: usize,
}
impl CompactionScheduler {
pub fn new(base_dir: PathBuf) -> Self {
Self {
base_dir,
level_size_multiplier: 10,
max_level: 6,
}
}
pub fn should_compact(&self, level: usize, sst_count: usize) -> bool {
let max_count = self.level_capacity(level);
sst_count > max_count
}
fn level_capacity(&self, level: usize) -> usize {
if level == 0 { 4 } else { self.level_size_multiplier.pow(level as u32) }
}
pub fn pick_compaction(
&self,
level: usize,
sstables: &[SsTableMeta],
) -> Option<CompactionTask> {
if sstables.is_empty() {
return None;
}
let input_ssts: Vec<SsTableMeta> = if level == 0 {
sstables.to_vec()
} else {
vec![sstables[0].clone()]
};
let smallest_key = input_ssts.iter()
.map(|s| s.smallest_key.clone())
.min()?;
let largest_key = input_ssts.iter()
.map(|s| s.largest_key.clone())
.max()?;
Some(CompactionTask {
level,
input_ssts,
smallest_key,
largest_key,
target_level: level + 1,
})
}
pub fn execute_compaction(
&self,
task: &CompactionTask,
) -> std::io::Result<Vec<SsTableMeta>> {
let mut merged: BTreeMap<Vec<u8>, Vec<u8>> = BTreeMap::new();
for sst in &task.input_ssts {
let reader = SsTableReader::open(&sst.path)?;
for (key, value) in reader.iter() {
if value.is_empty() {
merged.remove(&key);
} else {
merged.insert(key, value);
}
}
}
let mut new_ssts = Vec::new();
let mut builder = SsTableBuilder::new();
let mut count = 0;
for (key, value) in merged {
builder.add(&key, &value);
count += 1;
if count >= 1024 * 4 {
let sst_id = format!("L{}-{:06}", task.target_level, new_ssts.len());
let path = self.base_dir.join(&sst_id);
builder.build(&path)?;
new_ssts.push(SsTableMeta {
id: sst_id,
path,
smallest_key: Vec::new(),
largest_key: Vec::new(),
level: task.target_level,
});
builder = SsTableBuilder::new();
count = 0;
}
}
if count > 0 {
let sst_id = format!("L{}-{:06}", task.target_level, new_ssts.len());
let path = self.base_dir.join(&sst_id);
builder.build(&path)?;
new_ssts.push(SsTableMeta {
id: sst_id,
path,
smallest_key: Vec::new(),
largest_key: Vec::new(),
level: task.target_level,
});
}
Ok(new_ssts)
}
}
#[derive(Clone)]
pub struct SsTableMeta {
pub id: String,
pub path: PathBuf,
pub smallest_key: Vec<u8>,
pub largest_key: Vec<u8>,
pub level: usize,
}
pub struct CompactionTask {
pub level: usize,
pub input_ssts: Vec<SsTableMeta>,
pub smallest_key: Vec<u8>,
pub largest_key: Vec<u8>,
pub target_level: usize,
}
pub struct SsTableReader;
impl SsTableReader {
pub fn open(_path: &PathBuf) -> std::io::Result<Self> { Ok(Self) }
pub fn iter(&self) -> Vec<(Vec<u8>, Vec<u8>)> { vec![] }
}
モジュール5：Bloom Filter
Bloom FilterはLSM-Tree読み取りパスの重要な最適化——SSTableを開く前にKeyが存在する可能性を高速に判定し、無駄なディスクIOを回避。偽陽性率は制御可能、空間オーバーヘッドは極小。
Bloom Filter実装
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
pub struct BloomFilter {
bitmap: Vec<u64>,
num_bits: usize,
num_hashes: usize,
}
impl BloomFilter {
pub fn new(expected_items: usize, fp_rate: f64) -> Self {
let num_bits = Self::optimal_num_bits(expected_items, fp_rate);
let num_hashes = Self::optimal_num_hashes(num_bits, expected_items);
let bitmap_len = (num_bits + 63) / 64;
Self {
bitmap: vec![0u64; bitmap_len],
num_bits,
num_hashes,
}
}
pub fn insert(&mut self, key: &[u8]) {
let hashes = self.hash_key(key);
for i in 0..self.num_hashes {
let bit_pos = hashes[i] % self.num_bits;
let word_idx = bit_pos / 64;
let bit_idx = bit_pos % 64;
self.bitmap[word_idx] |= 1u64 << bit_idx;
}
}
pub fn may_contain(&self, key: &[u8]) -> bool {
let hashes = self.hash_key(key);
for i in 0..self.num_hashes {
let bit_pos = hashes[i] % self.num_bits;
let word_idx = bit_pos / 64;
let bit_idx = bit_pos % 64;
if self.bitmap[word_idx] & (1u64 << bit_idx) == 0 {
return false;
}
}
true
}
fn hash_key(&self, key: &[u8]) -> Vec<usize> {
let mut hasher1 = DefaultHasher::new();
key.hash(&mut hasher1);
let h1 = hasher1.finish() as usize;
let mut hasher2 = DefaultHasher::new();
key.hash(&mut hasher2);
let h2 = hasher2.finish() as usize;
(0..self.num_hashes)
.map(|i| h1.wrapping_add(i.wrapping_mul(h2)))
.collect()
}
fn optimal_num_bits(n: usize, p: f64) -> usize {
let ln2 = std::f64::consts::LN_2;
((-(n as f64) * p.ln()) / (ln2 * ln2)).ceil() as usize
}
fn optimal_num_hashes(m: usize, n: usize) -> usize {
((m as f64 / n as f64) * std::f64::consts::LN_2).ceil() as usize
}
}
モジュール6：Block Cache
Block CacheはホットなSSTable Data Blockをキャッシュし、ディスクIOを削減。LRU退避戦略はメモリ制限時にコールドデータを自動的に排除。
LRU Block Cache実装
use std::collections::HashMap;
use std::sync::Arc;
use tokio::sync::RwLock;
pub struct BlockCache {
cache: Arc<RwLock<LruCache<Vec<u8>, Vec<u8>>>>,
}
struct LruCache<K, V> {
entries: HashMap<K, V>,
order: Vec<K>,
capacity: usize,
}
impl<K: Clone + Eq + std::hash::Hash, V> LruCache<K, V> {
fn new(capacity: usize) -> Self {
Self {
entries: HashMap::new(),
order: Vec::new(),
capacity,
}
}
fn get(&mut self, key: &K) -> Option<&V> {
if self.entries.contains_key(key) {
self.order.retain(|k| k != key);
self.order.push(key.clone());
self.entries.get(key)
} else {
None
}
}
fn put(&mut self, key: K, value: V) {
if self.entries.contains_key(&key) {
self.order.retain(|k| k != &key);
self.order.push(key.clone());
self.entries.insert(key, value);
return;
}
if self.entries.len() >= self.capacity {
if let Some(evicted) = self.order.first().cloned() {
self.order.remove(0);
self.entries.remove(&evicted);
}
}
self.order.push(key.clone());
self.entries.insert(key, value);
}
}
impl BlockCache {
pub fn new(capacity: usize) -> Self {
Self {
cache: Arc::new(RwLock::new(LruCache::new(capacity))),
}
}
pub async fn get(&self, sst_id: &str, block_offset: u64) -> Option<Vec<u8>> {
let key = format!("{}:{}", sst_id, block_offset).into_bytes();
self.cache.write().await.get(&key).cloned()
}
pub async fn put(&self, sst_id: &str, block_offset: u64, data: Vec<u8>) {
let key = format!("{}:{}", sst_id, block_offset).into_bytes();
self.cache.write().await.put(key, data);
}
}
落とし穴ガイド：5つのよくある罠
罠1：MemTableの無制限増大でOOM
// ❌ 間違い：容量上限を設定しない
let memtable = MemTable::new(usize::MAX);
// ✅ 正しい：合理的な容量を設定、書き込み満了後にフリーズしてフラッシュ
let memtable = MemTable::new(64 * 1024 * 1024); // 64MB
if memtable.is_full() {
manager.freeze_and_switch().await?;
flush_to_sstable(immutable).await?;
}
罠2：WALのfsyncなしでクラッシュ時にデータ損失
// ❌ 間違い：flushのみでfsyncなし
writer.flush()?;
// ✅ 正しい：fsyncでデータのディスク書き込みを保証
writer.flush()?;
file.sync_all()?;
罠3：Compaction中のSSTable削除で読み取り失敗
// ❌ 間違い：Compaction完了後すぐに古いSSTableを削除
for sst in &old_sstables { std::fs::remove_file(&sst.path)?; }
// ✅ 正しい：参照カウントがゼロになってから削除（または遅延削除）
for sst in &old_sstables {
if sst.ref_count.load(Ordering::SeqCst) == 0 {
std::fs::remove_file(&sst.path)?;
} else {
pending_deletions.push(sst.clone());
}
}
罠4：Bloom Filter偽陽性率の設定が高すぎる
// ❌ 間違い：偽陽性率0.1、10%の無駄なIO
let filter = BloomFilter::new(100000, 0.1);
// ✅ 正しい：偽陽性率0.01、本番環境推奨
let filter = BloomFilter::new(100000, 0.01);
罠5：SSTable Blockサイズの設定が不適切
// ❌ 間違い：Blockが小さすぎ、インデックスが膨張
const BLOCK_SIZE: usize = 256;
// ✅ 正しい：4KB-64KB、圧縮率とインデックスサイズのバランス
const BLOCK_SIZE: usize = 4 * 1024;
エラートラブルシューティング：10のよくあるエラー
| # | エラーメッセージ | 原因 | 解決方法 |
|---|---|---|---|
| 1 | Cannot allocate memory |
MemTableに容量制限がなくOOM | MemTable容量上限を設定、書き込み満了後にフリーズしてフラッシュ |
| 2 | WAL checksum mismatch |
WAL部分書き込みまたはディスク障害 | 破損レコードを切り捨て、有効部分をリプレイ |
| 3 | SSTable not found: L0-000001 |
Compactionが読み取り中のSSTableを削除 | 参照カウントまたは遅延削除機構を実装 |
| 4 | Compaction stuck: level overflow |
L0ファイル数が閾値を超過、マージが遅延 | Compactionトリガー閾値を調整またはマージスレッドを追加 |
| 5 | Bloom filter false positive rate too high |
期待要素数と実際が不一致 | Bloom Filterパラメータを再計算、bitmapを拡大 |
| 6 | Block cache hit rate below 10% |
キャッシュ容量不足またはアクセスパターンが分散 | Cache容量を増加またはLRU戦略を調整 |
| 7 | crossbeam-skiplist: key already exists |
同じKeyの重複挿入 | insert_if_absentではなくinsertで上書き |
| 8 | IO error: Too many open files |
SSTableファイルハンドルが未解放 | ファイルハンドルプールを実装または同時オープン数を制限 |
| 9 | tokio: task panicked during Compaction |
Compactionマージ時のメモリオーバーフロー | バッチマージ、1回のCompactionメモリ使用量を制限 |
| 10 | data corruption after crash recovery |
WALとMemTableの状態が不整合 | WALをMemTableより先に書き込み、2相コミットを使用 |
高度な最適化のヒント
1. プレフィックス圧縮（Prefix Compression）
SSTable Block内の隣接Keyがプレフィックスを共有し、ストレージ容量を削減。例えばuser:1001とuser:1002はuser:プレフィックスを共有し、差分のみを保存。
2. パーティション化Compaction（Partitioned Compaction）
大きなSSTableをKey Rangeでパーティション分割し、Compactionは重複パーティションのみをマージ、全量書き直しを回避。RocksDBのPartitioned Index Filterがこの戦略を採用。
3. 動的レベル調整（Dynamic Level）
起動時に実際のデータ量に基づいて各レベルのサイズ倍数を動的に調整、空レベルでのCompactionリソース浪費を回避。LevelDBのdynamic_level_bytesオプションがこの最適化を実装。
4. Write Stall流量制御
L0ファイル数が多すぎる場合に書き込みレートを能動的に制限し、読み取りレイテンシの急増を防止。level0_slowdown_writes_triggerとlevel0_stop_writes_triggerの2段階閾値を設定。
5. 並列Compaction
複数スレッドで異なるレベルのCompactionタスクを並列実行し、マルチコアで領域回収を高速化。tokioのspawn_blockingはCPU集約的なマージ操作のラッピングに適している。
比較分析
| 次元 | LSM-Tree | B+Tree | LSM-B+Tree Hybrid |
|---|---|---|---|
| 書き込み性能 | ⭐非常に高い（シーケンシャル書き込み） | ⭐低い（ランダム書き込み+ページ分割） | ⭐高い（書き込みはLSM経由） |
| 読み取り性能 | ⭐中（多層検索が必要） | ⭐高い（単一ツリー検索） | ⭐高い（ホットデータはCache経由） |
| 書き込み増幅 | ⭐中（Compactionオーバーヘッド） | ⭐高い（ページ再書き込み+ログ） | ⭐中 |
| 空間増幅 | ⭐中（多バージョン+Tombstone） | ⭐低い（インプレース更新） | ⭐低い |
| クラッシュリカバリ | ⭐高速（WALリプレイ） | ⭐低速（Redo/Undo Log） | ⭐高速 |
| 範囲クエリ | ⭐良い（SSTable順序付き） | ⭐良い（リーフチェーン） | ⭐良い |
| 並発制御 | ⭐シンプル（追記書き込み） | ⭐複雑（細粒度ロック） | ⭐中 |
| ユースケース | 書き込み集中型 | 読み取り集中型 | 混合ワークロード |
選定の推奨
- LSM-Tree：書き込み集中、時系列データ、ログストレージ（推奨第一選択）
- B+Tree：読み取り集中、トランザクション頻繁、ポイントクエリ中心
- Hybrid：読み書き混合、レイテンシ敏感なOLTPシナリオ
まとめと展望
本記事では6つのコアモジュールから完全なLSM-Treeストレージエンジンを構築：MemTableインメモリテーブル→SSTableディスク永続化→WAL先行書き込みログ→Compactionマージ戦略→Bloom Filter→Block Cache。Rustの所有権システムがメモリ安全性を保証し、crossbeamロックフリースキップリストが高並発MemTableを提供し、tokio非同期ランタイムがCompactionと読み書きの並行性を実現。
今後の方向性：カラムファミリ（Column Family）によるマルチデータ分離、分散Compactionによるノード間並列、ZSTD圧縮によるストレージコスト削減、永続メモリ（PMEM）によるWALボトルネック解消。LSM-Treeストレージエンジンの本質は「追記書き込みでインプレース更新を置き換える」ことではなく、「順序付きマージの確実性でランダム書き込みの予測不可能性を置き換える」こと。
オンラインツール推奨
- JSONフォーマッター：/ja/json/format — SSTableメタデータとCompaction設定のデバッグ
- ハッシュ計算：/ja/encode/hash — Bloom FilterハッシュとKeyチェックサムの計算
- Base64コーデック：/ja/encode/base64 — WALレコードとバイナリデータのエンコード
- コードフォーマッター：/ja/dev/code-formatter — Rustストレージエンジンコードのフォーマット
関連記事
- Rust Tokio Channelパターン — Compactionタスクキューの実装
- Rust Axum Webフレームワーク — ストレージエンジンHTTPインターフェースの構築
- Rust所有権とメモリガイド — Rustメモリ安全モデルの理解
外部リファレンス
まとめ：Rustデータベースカーネルストレージエンジンの6つのコアモジュールは、メモリからディスクまでの完全なデータパスを構成：MemTableロックフリー並発書き込み→SSTable順序付きフラッシュ永続化→WALクラッシュリカバリ保障→Compaction領域回収と読み取り最適化→Bloom Filter高速フィルタリング→Block Cacheホットデータ高速化。Rustの所有権システムがメモリ安全をゼロコストで実現し、crossbeamとtokioが並発と非同期を自然に融合。LSM-Treeストレージエンジンの本質は「追記書き込みでインプレース更新を置き換える」ことではなく、「順序付きマージの確実性でランダム書き込みの予測不可能性を置き換える」こと。
ブラウザローカルツールを無料で試す →
#Rust数据库内核#存储引擎#LSM Tree#B+Tree#WAL#2026#编程语言