搜索系统中的延迟删除与空间压缩

在构建高性能搜索系统时，我们经常面临一个两难境地：如何快速响应删除请求，同时保证索引文件的紧凑性和查询效率？

直接在磁盘上的倒排索引中删除文档是极其昂贵的。因为倒排索引通常是高度压缩且连续存储的，为了删除一个文档 ID，你可能需要重写整个索引段。

因此，大多数现代搜索系统（如 Lucene 或我们今天讨论的架构）都采用了 延迟删除（Lazy Deletion） 策略。删除操作只是在内存或特定的 "墓碑" 文件（Tombstone file）中标记该文档为 "已删除"。真正的物理删除和空间回收，发生在一个被称为 段合并（Segment Merge） 的后台过程中。

今天，我们将通过 Zig 语言来演示这一过程的核心逻辑：如何在合并多个索引段时，通过位图（Bitmap）过滤掉已删除的文档，实现空间压缩。

核心设计：位图过滤与流式合并

合并过程本质上是一个多路归并排序，但在归并的过程中，我们需要引入一个 "过滤器"。

输入：多个旧的索引段（Segments），每个段包含一系列有序的文档 ID。
删除集：一个全局或分段的位图，标记了哪些 ID 是 "死" 的。
输出：一个新的、更紧凑的索引段，仅包含 "活" 的文档。

这种设计将昂贵的 IO 操作推迟到了合并阶段，而合并阶段通常是顺序读写，对磁盘非常友好。

Zig 实现演示：净室重构

我们将模拟一个简化的场景：合并两个整数列表（代表文档 ID），并过滤掉黑名单中的 ID。为了演示 Zig 的内存安全特性，我们将显式管理内存分配器。

const std = @import("std");
const Allocator = std.mem.Allocator;

/// 模拟一个简单的索引段迭代器
const SegmentIterator = struct {
    docs: []const u32,
    current: usize = 0,

    pub fn next(self: *SegmentIterator) ?u32 {
        if (self.current >= self.docs.len) return null;
        const doc = self.docs[self.current];
        self.current += 1;
        return doc;
    }

    pub fn peek(self: *SegmentIterator) ?u32 {
        if (self.current >= self.docs.len) return null;
        return self.docs[self.current];
    }
};

/// 模拟删除集合（使用简单的哈希表代替位图，便于演示）
const DeletionSet = std.AutoHashMap(u32, void);

/// 合并器：执行多路归并和过滤
const IndexMerger = struct {
    allocator: Allocator,
    deletion_set: DeletionSet,

    pub fn init(allocator: Allocator, deletions: DeletionSet) IndexMerger {
        return IndexMerger{
            .allocator = allocator,
            .deletion_set = deletions,
        };
    }

    /// 执行合并，返回新的紧凑文档列表
    pub fn merge(self: *IndexMerger, segment_a: []const u32, segment_b: []const u32) ![]u32 {
        var list = std.ArrayList(u32).init(self.allocator);
        errdefer list.deinit();

        var iter_a = SegmentIterator{ .docs = segment_a };
        var iter_b = SegmentIterator{ .docs = segment_b };

        // 经典的双指针归并算法，增加了 "is_alive" 检查
        while (true) {
            const val_a = iter_a.peek();
            const val_b = iter_b.peek();

            var candidate: u32 = 0;

            if (val_a != null and val_b != null) {
                if (val_a.? < val_b.?) {
                    candidate = iter_a.next().?;
                } else if (val_a.? > val_b.?) {
                    candidate = iter_b.next().?;
                } else {
                    // ID 相同（在分片索引中通常不应发生，但为了鲁棒性处理）
                    candidate = iter_a.next().?;
                    _ = iter_b.next();
                }
            } else if (val_a != null) {
                candidate = iter_a.next().?;
            } else if (val_b != null) {
                candidate = iter_b.next().?;
            } else {
                break; // 均为空，合并结束
            }

            // 关键步骤：过滤掉已删除的文档
            if (!self.deletion_set.contains(candidate)) {
                try list.append(candidate);
            }
        }

        return list.toOwnedSlice();
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // 1. 准备模拟数据
    const seg1 = [_]u32{ 1, 3, 5, 7, 9 };
    const seg2 = [_]u32{ 2, 4, 6, 8, 10 };

    // 2. 标记 ID 为 3, 4, 9 的文档为已删除
    var deletions = DeletionSet.init(allocator);
    defer deletions.deinit();
    try deletions.put(3, {});
    try deletions.put(4, {});
    try deletions.put(9, {});

    // 3. 执行合并
    var merger = IndexMerger.init(allocator, deletions);
    const result = try merger.merge(&seg1, &seg2);
    defer allocator.free(result);

    // 4. 验证输出：3, 4, 9 应该消失了
    std.debug.print("Merged Docs: {any}\n", .{result});
    // 预期输出: { 1, 2, 5, 6, 7, 8, 10 }
}

权衡分析

在上述代码中，我们看到了 "Merge-Time Deletion" 的核心逻辑。

优势：

写入吞吐量高：删除操作变成了简单的追加写（追加到删除日志），无需随机 IO。
空间回收彻底：合并后的新段不仅去除了死数据，通常还会重新进行 Delta 编码压缩，进一步节省空间。

劣势：

读放大：在合并发生前，查询需要同时读取索引和删除位图来过滤结果，这稍微增加了查询时的计算量。
空间暂时浪费：已删除的数据在合并前仍然占用磁盘空间。

总结

延迟删除是存储系统设计中 "以空间换时间" 策略的经典应用。通过将物理删除推迟到合并阶段，我们在保证高并发写入性能的同时，最终实现了数据的一致性和空间的紧凑性。Zig 语言显式的内存控制和错误处理机制，非常适合编写这种对资源敏感的系统底层逻辑。