削除とコンパクション

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. 元のデータはセグメントファイルに残ったままです

論理削除を採用する理由

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バッチの後にコンパクション

削除ビットマップ

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

• 保存: 削除済みドキュメントIDのHashSet（AHashSet<u64>）
• 検索: O(1) – ハッシュセットによる検索

ビットマップはインデックスセグメントと一緒に永続化され、リカバリ時にWALから再構築されます。

次のステップ

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