armink / FlashDB

An ultra-lightweight database that supports key-value and time series data | 一款支持 KV 数据和时序数据的超轻量级数据库
Apache License 2.0
1.93k stars 435 forks source link

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

Open eggcar opened 4 months ago

eggcar commented 4 months ago

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

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

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

eggcar commented 4 months ago

遍历打印了一下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 commented 4 months ago

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

eggcar commented 4 months ago

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

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

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

armink commented 3 months ago

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