3. FTL垃圾回收算法：触发条件、回收策略与数据迁移

垃圾回收，说白了就是FTL里的“大扫除”。

SSD用久了，总会有一些“脏”块——里面既有有效数据，又有无效数据。这时候就需要垃圾回收来腾出空间。我做了这么多年存储，见过不少因为垃圾回收没做好，导致SSD性能像过山车一样的案例。今天咱们就把它彻底讲透。

3.1 垃圾回收的触发条件

什么时候该做垃圾回收？这不是拍脑袋决定的。我习惯把触发条件分成两类：主动触发和被动触发。

3.1.1 主动触发

• 空闲块数量低于阈值：这是最常见的。比如系统设定空闲块少于10%时，后台就开始回收。我在项目中一般设两个阈值——一个软阈值（比如15%）开始后台慢速回收，一个硬阈值（比如5%）强制快速回收。
• 定时触发：有些系统会在空闲时段主动做回收。嗯，这个策略在消费级SSD里用得比较多。

3.1.2 被动触发

• 写请求到来时无空闲块：这是最糟糕的情况。主机要写数据，但FTL发现没地方放了，只能先停下手头的活，赶紧回收一个块出来。我曾经遇到过这种场景，延迟直接飙到几百毫秒，用户体验极差。
• 系统进入低功耗模式前：有些嵌入式设备在休眠前会强制做一次回收，确保下次唤醒时有足够的空闲空间。

3.2 回收策略：选哪个块来“牺牲”？

确定了要回收，下一个问题就是：回收哪个块？ 这里有两个经典算法，我分别说说我的体会。

3.2.1 贪心算法（Greedy Algorithm）

贪心算法的思路很简单：选无效页最多的块。因为无效页越多，需要迁移的有效数据就越少，回收效率就越高。

// 贪心算法伪代码
Block select_greedy() {
    Block best = NULL;
    int max_invalid = -1;
    
    for each block in all_blocks {
        if (block.invalid_pages > max_invalid) {
            max_invalid = block.invalid_pages;
            best = block;
        }
    }
    return best;
}

这个算法有什么问题？我举个例子你就明白了。假设有两个块：

块编号	无效页数	有效页数	擦除次数
块A	60	4	100
块B	55	9	10

贪心算法会选块A，因为它无效页最多。但块A已经被擦除了100次，而块B才10次。你想想看，如果每次都选块A，它很快就会达到擦除寿命上限，变成坏块。这就是贪心算法的致命缺陷——不考虑磨损均衡。

3.2.2 成本效益算法（Cost-Benefit Algorithm）

成本效益算法，说白了就是在贪心的基础上，加了一个“年龄”因子。它不光看无效页多不多，还看这个块被擦除了多少次。

公式长这样：

效益 = (无效页数 / 总页数) / (擦除次数 * 数据迁移代价)

其中数据迁移代价 = 有效页数 × 每页迁移时间。所以综合下来：

效益 = (无效页比例) / (擦除次数 × 有效页数)

这个公式的妙处在于：

• 无效页比例越高，效益越大（跟贪心一样）
• 擦除次数越多，效益越小（避免过度磨损）
• 有效页越多，效益越小（迁移代价高）

我习惯在代码里这样实现：

// 成本效益算法伪代码
Block select_cost_benefit() {
    Block best = NULL;
    double max_benefit = -1.0;
    
    for each block in all_blocks {
        double invalid_ratio = (double)block.invalid_pages / PAGES_PER_BLOCK;
        double cost = block.erase_count * block.valid_pages;
        double benefit = invalid_ratio / cost;
        
        if (benefit > max_benefit) {
            max_benefit = benefit;
            best = block;
        }
    }
    return best;
}

3.3 回收过程中的数据迁移与元数据更新

选好了要回收的块，接下来就是实际操作了。这个过程分三步走：

3.3.1 第一步：读取有效数据

从被回收的块中，把所有的有效页读出来。注意，只读有效页，无效页直接跳过。我见过有些新手工程师把整个块都读出来，白白浪费了带宽。

3.3.2 第二步：写入新块

把读出来的有效页，写入到一个空闲块中。这里有个细节：写入顺序。最好按照LBA的逻辑顺序写入，这样后续读性能会更好。当然，如果你用的是全映射FTL，顺序就没那么重要了。

3.3.3 第三步：更新映射表

数据搬走了，映射关系也得跟着变。原来LBA指向旧块的物理页号，现在要改成指向新块的物理页号。这一步如果做不好，数据就丢了。

// 数据迁移与元数据更新伪代码
void garbage_collect(Block *victim) {
    // 1. 读取所有有效页
    Page *valid_pages[MAX_PAGES];
    int count = 0;
    for each page in victim->pages {
        if (page.is_valid) {
            valid_pages[count++] = read_page(page);
        }
    }
    
    // 2. 写入新块
    Block *new_block = get_free_block();
    for (int i = 0; i < count; i++) {
        int new_pbn = write_page(new_block, valid_pages[i]);
        
        // 3. 更新映射表
        int lba = valid_pages[i].lba;
        update_mapping(lba, new_pbn);
    }
    
    // 4. 擦除旧块
    erase_block(victim);
    add_to_free_list(victim);
}

3.4 知识体系总览

下面这张图，把垃圾回收的核心逻辑串起来了。我建议你多看几遍，理解每个环节之间的依赖关系。

3.5 写在最后

垃圾回收算法，说白了就是一门“取舍”的艺术。你要在回收效率、磨损均衡、写放大、延迟抖动之间找到平衡点。没有银弹，只有针对你的应用场景做定制。

我个人建议，刚入门的朋友先从成本效益算法入手，跑通了再考虑优化。别一上来就想搞什么机器学习预测回收，先把基础打牢。