FAL Partition Config Dynamically

[LianYangCn]

当前版本在 fal_cfg.h 通过定义 FAL_PART_TABLE 来定义 partition
但是，我在使用 Nodemcu(ESP32) 的时候 NodeMCU 是通过 partitions.csv 来定义分区的，如果要正常使用 flashdb
有两个途经，

1. 是根据 partitions.csv 自动生成 fal_cfg.h
2. 在初始化的时候使用 原生的API 去动态生成 FAL_PART_TABLE 的内容

我个人认为 2 是更好的方法，可以适用更多的系统

所以，我建议给 FAL 增加动态初始化 FAL_PART_TABLE 的能力，我觉得这个改动也不大

[armink]

FAL 有这个 API ，你可以读取 CSV ，解析出来，再通过下面的 API 设置进去

void fal_set_partition_table_temp(struct fal_partition *table, size_t len);

[LianYangCn]

BUT,
void fal_set_partition_table_temp(struct fal_partition *table, size_t len);
第一句就是 assert(init_ok);

也就是 说 fal_set_partition_table_temp 依赖 fal_partition_init
fal_partition_init 函数要么是使用初始化的 FAL_PART_TABLE， 要么 自己找一遍；完了再检查一下，才会置 init_ok

所以你原始的设计是不是不支持这么做？

[armink]

先调用 fal_partition_init 再调用 fal_set_partition_table_temp 就行

[LianYangCn]

测试可用，但是希望能够更优雅

[armink]

嗯，确实可以把这个断言去掉，当时想多了，你方便提交个 PR 不 ;>

[LianYangCn]

刚刚已经在 NodeMcu dev-esp32 分支上运行了 FlashDB
独立一个分区去存放FlashDB, 效果不错

存取小量数据，FlashDB 表现非常优秀

我简单的进行了一下不严谨的测试
测试用的 key 是 ”0“ - ”4000“， value 使用对应的 "AA0" - "AA4000"

我首先测试了 500 条数据， 读取速度非常快，没有什么延迟的感觉
然后测试了 4000 条数据，读取速度能感觉到延迟，但最大延迟控制在1秒以内

不太确定 FlashDB 内部使用的什么算法，但是

4000条 数据的时候，
测试 key = ”1“, 无延迟感读取；
测试 key = "2000", 大概有少于1秒的延迟
测试 key = ”3999“, 大概有约1秒的延迟
测试 key = "not_exist", 大概有约1秒的延迟

当然 FlashDB 的缓存还是非常有效的，读取一次以后，延迟马上就没有了

我翻看了一下文档，issue / discussions 和 源代码， 没有关于 FlashDB 使用的算法，相关的 issue 都没有回复或者说明，我比较笨，当然也比较懒，不会通过源代码反向分析算法。

我有一个不成熟的想法，是不是可以这样

1. 是否可以考虑增加 FAL 类似一层，去扩展一种或者多种，虽然更消耗RAM或者FLASH，但是可以获取更快的搜索速度的算法
2. 基于上面类似想法，是否可以引入一种字符串压缩算法， 比如 Smaz

以上是我不成熟的两个小建议，你的项目，你决定

希望 FlashDB 能够发展壮大

[armink]

你这测试的太专业了 👍

确实，目前 FlashDB 当存储容量过大时，检索效率会比较低，其设计原理可以参考这篇文档 https://github.com/armink/EasyFlash/blob/master/docs/zh/design.md

目前 FlashDB 的设计还比较简单，所以实现起来也比较轻量级，只有 5K 左右的代码，普通的嵌入式平台可能就够用了。

如果想要再来优化一下性能，那么可能我会优先关注大家的使用场景（主要是需求），再好去设计。当时设计 FlashDB 的初衷更多的是为了存储参数，一个设备的参数一般不会太多，所以目前对参数保存的需求是够了的。

所以，你也可以讲讲你的使用场景，我们可以一起有针对性的设计一下。

[LianYangCn]

我简单的看了一下 design

请允许我耍一下流氓，我们抛开需求，我的想法是，

1. 当前 FlashDB 存储比较简单高效（能实现如此稳定又不失扩展性，表示佩服）
2. 从源代码看，不考虑缓存，搜索是线性查找的方式 O(n)
3. 不改动现在的代码，通过构建一个 基于 hash 的 index 来把搜索速度提升到 O(1)
4. 不改动现在的代码，通过构建一个 基于 b+tree 的 index 来把速度提升到 O(logn)
5. hash 虽然效率高，但是有点浪费RAM，不过如果预先知道数量，至少可以减少 rehash 的次数
6. b+tree 虽然效率低一点点，浪费RAM比较少，还可以查找范围，但是FlashDB 是 KV 数据库嘛，范围好像不重要，hash可能是最佳选择
7. 那么最后问题来了，index 保存在哪里呢？如果是动态构建，启动速度会慢点；如果保存在 FLASH上面，又要用FLASHDB本身

我试一下动态构建 hash 看看内存占用怎么样？效果会不会爽

[armink]

其实现在的 FlashDB 的 cache 机制就是动态构建 Hash index 方式，只是默认的 index 容量有点小。

你需要 4K 数据都提速，直接把 FDB_KV_CACHE_TABLE_SIZE 设置为 4K 就好了，只需要多花费 32KB RAM，不知道这样能不能满足你的需求？

[LianYangCn]

下面这段代码

FlashDB/src/fdb_kvdb.c

Lines 218 to 223 in cea7a06

	for (i = 0; i < FDB_KV_CACHE_TABLE_SIZE; i++) {
	if ((db->kv_cache_table[i].addr != FDB_DATA_UNUSED) && (db->kv_cache_table[i].name_crc == name_crc)) {
	char saved_name[FDB_KV_NAME_MAX];
	/* read the KV name in flash */
	_fdb_flash_read((fdb_db_t)db, db->kv_cache_table[i].addr + KV_HDR_DATA_SIZE, (uint32_t *) saved_name, FDB_KV_NAME_MAX);

从以上代码可以看出来，只是用crc32来hash了一下key，并没有用hash直接hit，还是直接去遍历查找的，所以这里还是需要改进一下，如果不改动，恐怕4K数据的时候作用还是不太明显
因为，ESP32 的 RAM 和 FLASH 都是通过SPI外挂的，只改 FDB_KV_CACHE_TABLE_SIZE 相当于，从 外挂 FLASH 改到 外挂 RAM去搜索

[LianYangCn]

下面这段代码

FlashDB/src/fdb_kvdb.c

Lines 218 to 223 in cea7a06

	for (i = 0; i < FDB_KV_CACHE_TABLE_SIZE; i++) {
	if ((db->kv_cache_table[i].addr != FDB_DATA_UNUSED) && (db->kv_cache_table[i].name_crc == name_crc)) {
	char saved_name[FDB_KV_NAME_MAX];
	/* read the KV name in flash */
	_fdb_flash_read((fdb_db_t)db, db->kv_cache_table[i].addr + KV_HDR_DATA_SIZE, (uint32_t *) saved_name, FDB_KV_NAME_MAX);

从以上代码可以看出来，只是用crc32来hash了一下key，并没有用hash直接hit，还是去遍历查找的O(n)没有变，所以这里还是需要改进一下，如果不改动，恐怕4K数据的时候作用还是不太明显
因为，ESP32 的 RAM 和 FLASH 都是通过SPI外挂的，只改 FDB_KV_CACHE_TABLE_SIZE 相当于，从 外挂 FLASH 改到 外挂 RAM去搜索

我这两天写了一个分支用 hash index 思想重写了cache 试了一下，速度已经是 O(1) 了

4000个记录，查找任意一个，我这个人肉计时器都感受不到任何延迟，从1 到 4000 都很快能索引出来

表现非常优秀

但是，可是，BUT

构建索引的速度实在太慢了，4000个记录，居然要5分钟，忍不了，

我看看到底是谁花了5分钟，太过分了

[armink]

4000个记录，查找任意一个，我这个人肉计时器都感受不到任何延迟，从1 到 4000 都很快能索引出来

厉害呀，期待看看你的杰作

[LianYangCn]

我多检查几遍，就推送

[LianYangCn]

@armink

FlashDB/src/fdb_kvdb.c

Lines 1633 to 1638 in cea7a06

	FDB_DEBUG("KVDB size is %u bytes.\n", db_max_size(db));
	result = _fdb_kv_load(db);
	#ifdef FDB_KV_AUTO_UPDATE
	if (result == FDB_NO_ERR) {

4000 条数据的时候，1635 这一句执行了3分50秒 左右，构建hash执行了1分15秒 左右

[armink]

_fdb_kv_load 会对整个 db 进行校验检查，估计时间都浪费在 Flash 读取上了

[LianYangCn]

能不能不校验，后者加快校验，或者延迟校验，1分左右还能忍 4分钟忍不了啊

[armink]

检查的目的主要还是为了掉电恢复，感觉是可以优化的，降低检查的范围

• 检查各个 sector 的状态
• 如果扇区存在过 GC 或者当前 正在写入 再去校验

[LianYangCn]

这里有个误会 _fdb_kv_load 函数里面就有更新 cache 的操作，我没有注意所以我又做一遍，我去掉以后，启动速度快了1分钟，现在启动时间大概是4分钟

[armink]

嗯，上面我提到了降低校验范围完善以后，初始化速度还能提升很多

[LianYangCn]

Test case 安排了一下

1. 电脑是1T NVME 固态
2. i5 9xxx 系列 CPU 基于 Liunx Demo 修改
3. MacOS 11.5.2 系统

200 条记录
开启HASH以后，测试日志如下

[FlashDB][sample][kvdb][bench] get the '     197' value is     VALUE197
[FlashDB][sample][kvdb][bench] get the '     198' value is     VALUE198
[FlashDB][sample][kvdb][bench] get the '     199' value is     VALUE199
[FlashDB][sample][kvdb][bench] ===========================================================
[FlashDB][main] 
Bench time: 4466554

关闭HASH以后，测试日志如下

[FlashDB][sample][kvdb][bench] get the '     198' value is     VALUE198
[FlashDB][sample][kvdb][bench] get the '     199' value is     VALUE199
[FlashDB][sample][kvdb][bench] ===========================================================
[FlashDB][main] 
Bench time: 7173490

效果还行

[armink]

Good Job

[LianYangCn]

我用的是 ESP32 做的实验
说真的 FlashDB 已经做的很不错了

FlashDB/src/fdb_kvdb.c

Lines 1478 to 1490 in 44a414e

	return true;
	} else if (kv->crc_is_ok && kv->status == FDB_KV_WRITE) {
	/* update the cache when first load */
	update_kv_cache(db, kv->name, kv->name_len, kv->addr.start);
	}
	return false;
	}
	/**
	* Check and load the flash KV.
	*
	* @return result

如果将上面的 1481 注释掉以后，初始化时间减少到 2 秒，说明主要问题还是 hash index 构建上

所以我简单的找了一下，
由于我使用的 ESP32 HIMEM 作为 hash index 存放内存，这部分内存并没有直接映射到内存地址上去，需要做页交换，所以我首先怀疑是不是这部分交换过于频繁的问题，所以简单调整了一下
现在 5000 条数据下，初始化时间在29秒左右

考虑到 hash 算法的特性，我觉得将 hash 存入 flash 的性价比有点低，主要是

1. 磨损平衡不太好写
2. hash 随机对单个元素也不是太好写

现在有两个办法

1. 进一步提升初始化时间
2. 初始化不去构造hash index，边用边构造

你能信，我把hash算法改了一下，现在初始化速度降到了

当当当（音效）

3秒

5000条数据 3秒 启动太完美了

[armink]

哇，是如何做到的？

[LianYangCn]

用 FNV hash 算法 替代了原来的 CRC32 + Robert Jenkins 算法
我多测试一下，也会提PR的

[armink]

Murmur3 看着性能也不错嘛，感觉都可以把 hash + cache 这部分独立出来一个模块来管理了

[LianYangCn]

有空可是试一试 murmur3 ，但是更让我感兴趣的是 murmur3 的随机性看上去 比 FNV 好很多