削除とコンパクション

Laurusは二段階の削除戦略を採用しています。高速な**論理削除（Logical Deletion）と、それに続く定期的な物理コンパクション（Physical Compaction）**です。

ドキュメントの削除

#![allow(unused)]
fn main() {
// 外部IDでドキュメントを削除
engine.delete_documents("doc-1").await?;
engine.commit().await?;
}

論理削除

ドキュメントが削除された場合、インデックスファイルから即座に削除されるわけではありません。代わりに以下の処理が行われます。

graph LR
    Del["delete_documents('doc-1')"] --> Bitmap["Add internal ID\nto Deletion Bitmap"]
    Bitmap --> Search["Search skips\ndeleted IDs"]

1. ドキュメントの内部IDが**削除ビットマップ（Deletion Bitmap）**に追加されます
2. 検索時にビットマップがチェックされ、削除されたドキュメントが結果からフィルタリングされます
3. 元のデータはセグメントファイルに残ったままです

これはレキシカルインデックスと**ベクトル（HNSW）**インデックスの両方に一様に適用されます。HNSW では 削除されたノードはグラフに残り（グラフの連結性を保つためそのベクトルは引き続き利用されます）、 削除認識トラバーサルが結果から除外します。したがって削除で グラフが再構築されることはなく、コストはインデックスサイズに依らず O(1) のビットマップマークだけです。 物理的な回収は後段のコンパクションで行われます。

論理削除を採用する理由

Upsert（更新 = 削除 + 挿入）

既存の外部IDでドキュメントをインデックスすると、Laurusは自動的にUpsertを実行します。

1. 古いドキュメントが論理削除されます（そのIDが削除ビットマップに追加）
2. 新しい内部IDで新しいドキュメントが挿入されます
3. 外部IDから内部IDへのマッピングが更新されます

#![allow(unused)]
fn main() {
// 最初の挿入
engine.put_document("doc-1", doc_v1).await?;
engine.commit().await?;

// 更新: 古いバージョンが論理削除され、新しいバージョンが挿入される
engine.put_document("doc-1", doc_v2).await?;
engine.commit().await?;
}

物理コンパクション

時間の経過とともに、論理削除されたドキュメントが蓄積されスペースを浪費します。コンパクションは、削除済みエントリを含まないセグメントファイルを再書き込みすることでスペースを回収します。

graph LR
    subgraph "Before Compaction"
        S1["Segment 0\ndoc-1 (deleted)\ndoc-2\ndoc-3 (deleted)"]
        S2["Segment 1\ndoc-4\ndoc-5"]
    end

    Compact["Compaction"]

    subgraph "After Compaction"
        S3["Segment 0\ndoc-2\ndoc-4\ndoc-5"]
    end

    S1 --> Compact
    S2 --> Compact
    Compact --> S3

コンパクションの処理内容

1. 既存セグメントからすべての生存（未削除）ドキュメントを読み取ります
2. 削除済みエントリを含まない転置インデックスやベクトルインデックスを再構築します
3. 新しいクリーンなセグメントファイルを書き込みます
4. 古いセグメントファイルを削除します
5. 削除ビットマップをリセットします

コストと頻度

コンパクションのタイミング

• 書き込みが少ないワークロード: 定期的にコンパクション（例: 毎日または毎週）
• 書き込みが多いワークロード: 削除率がしきい値を超えた場合にコンパクション
• バルク更新後: 大量のUpsertバッチの後にコンパクション

自動コンパクション

HNSW ベクトルインデックスではコンパクションを自動実行できます。DeletionConfig::auto_compaction が有効な場合（既定）、commit() が削除率（削除ノード数 / コミット済み総ノード数）を確認し、 DeletionConfig::compaction_threshold（既定 0.3）に達するとコンパクションを起動します。 コンパクション後は削除率が 0 に戻るため、削除が再度蓄積するまで再発火せず、手動 optimize() なしに tombstone の増加を抑えられます。自分で制御したい場合は auto_compaction を false にします。

削除ビットマップ

削除ビットマップは、どの内部IDが削除されたかを追跡します。

• 保存: 削除済みドキュメントIDの Roaring ビットマップ。 セグメント寿命で累積する密な削除集合では、生のID列より劇的に小さくなります。例えば 10M ドキュメント・10% 削除のセグメントは on-disk で ~8MB ではなく ~125KB です。
• 検索: 分岐の少ないビットテスト。削除集合が大きくても CPU キャッシュに常駐しやすく、 is_deleted は lexical の per-document・vector の per-neighbour 検索ホットパスで呼ばれます。

ビットマップはインデックスセグメントと一緒に（.delmap ファイルとして）永続化され、リカバリ時に WALから再構築されます。on-disk 形式はバージョン管理されており、現在の writer は v4（Roaring）を 書き出し、reader は後方互換のため旧 v1〜v3（生ID列）形式も読み込めます。

次のステップ

• データの永続化方法: 永続化とWAL
• IDの管理と内部/外部IDのマッピング: ID管理