提前标记sector为GC状态，并在kv iterator中跳过待GC的区块

[eggcar]

测试场景：频繁对同一个key改写其值，随着覆写的次数增多，每次再写入的时间会越来越久

大概过了一下代码，主要是遍历kv和遍历sector耗费大量时间，因为在这个场景下，大量的中间sector里全都是被删除的kv，能不能在某个位置检测sector内已没有有效数据，直接标记为FDB_SECTOR_DIRTY_GC，然后在kv iterator和sector iterator中直接跳过待GC的区块？

还没太完整跟踪所有相关的代码，还不太确定是否影响正常的GC功能，朱工能否先看下这个想法是否符合flashDB的设计原则？

[eggcar]

遍历打印了一下sector的信息，发现大部分情况下一个sector并不会完全用满，也就不太好判断标记sector为GC的时机，绝大部分情况下即便一个sector里的kv全部删除也会剩下几十个bytes的空间，实际使用时很难完全写满一个sector
调整threshold也许可行，不过不同的应用场景需要权衡，空间大区块多的场景可以牺牲一些存储密度，空间小的场景就不太需要关注性能，但这个方法终究不太通用

换个思路，目前每次分配一个kv对象时，alloc_kv首先要做一次全sector遍历统计sector使用量信息，再做一次遍历找Using状态的sector，如果所有Using-sector空间都不足，需要再做一次sector遍历找到空sector。

static uint32_t alloc_kv(fdb_kvdb_t db, kv_sec_info_t sector, size_t kv_size)
{
    uint32_t empty_kv = FAILED_ADDR;
    size_t empty_sector = 0, using_sector = 0;
    struct alloc_kv_cb_args arg = {db, kv_size, &empty_kv};
    /* sector status statistics */
    sector_iterator(db, sector, FDB_SECTOR_STORE_UNUSED, &empty_sector, &using_sector, sector_statistics_cb, false);
    if (using_sector > 0) {
        /* alloc the KV from the using status sector first */
        sector_iterator(db, sector, FDB_SECTOR_STORE_USING, &arg, NULL, alloc_kv_cb, true);
    }
    if (empty_sector > 0 && empty_kv == FAILED_ADDR) {
        if (empty_sector > FDB_GC_EMPTY_SEC_THRESHOLD || db->gc_request) {
            sector_iterator(db, sector, FDB_SECTOR_STORE_EMPTY, &arg, NULL, alloc_kv_cb, true);
        } else {
            /* no space for new KV now will GC and retry */
            FDB_DEBUG("Trigger a GC check after alloc KV failed.\n");
            db->gc_request = true;
        }
    }

    return empty_kv;
}

三次遍历耗时非常明显，感觉至少有两个改进点：

1. sector的使用量统计可以在初始化加载的时候统计一次，随后对db进行增删改操作时 实时更新而不需要每次都重新遍历全部sector，占用RAM很少，不过需要配合修改的地方很多
2. 寻找可用的sector应该合并成一次遍历，中间记录一下备选区块，找到合适的Using区块直接分配，找不到合适的Using区块就直接使用备选的Empty区块

其实第1条如果改动太麻烦的话，也可以把后两次的遍历合并到第一次的遍历里面去，目前的代码可能是为了代码简洁，在这个地方牺牲了不少性能。不过这个改进也只是常系数项的优化

[armink]

其实也不是每次都会执行三次遍历的，绝大多数情况下是两次遍历，第三次只有第二次分配不出来才会执行的

[eggcar]

其实也不是每次都会执行三次遍历的，绝大多数情况下是两次遍历，第三次只有第二次分配不出来才会执行的

是的，最坏情况是执行三次遍历，一般是两次，但是我跟踪了一下性能，前两次遍历已经耗时非常大了，而且两次耗时都很大，基本55开

我现在把fdb的读写做成独立线程的异步队列了，优先不要阻塞业务进程，过阵子有时间试一下这个地方可不可以优化

[armink]

嗯嗯，我们一般量产项目也会把这类 IO 阻塞类工作丢到后台异步任务中执行