RT-Thread-flashdb内部实现浅析RT-Thread问答社区

flashdb内部实现浅析

发布于 2023-12-28 10:47:22 浏览：3166 订阅该版

[tocm]

### FlashDB的实现

[FlashDB](https://github.com/armink/FlashDB)是一款基于Flash整页擦除细粒度写入特性，为嵌入式系统定制的一款小型数据库。支持键值对（kvdb）和时间序列（tsdb）2种数据类型。设计上，Flash基本满足数据库事务的原子性、一致性、隔离性和持久性要求。

#### 数据结构实现

##### kvdb页头
一个FlashDB的数据库只能配置为支持一种数据类型（kvdb或tsdb），至少为其分配2个flash页。每个flash页都包含一个flash页头。初始化flash数据库时，会格式化所有数据库使用的flash页，然后在每个flash页的起始位置写入页头数据，kvdb页头数据对应的C代码定义如下：
```c
struct sector_hdr_data {
    struct {
        uint8_t store[FDB_STORE_STATUS_TABLE_SIZE];
        uint8_t dirty[FDB_DIRTY_STATUS_TABLE_SIZE];
    } status_table;
    uint32_t magic;
    uint32_t combined;
    uint32_t reserved;
};
typedef struct sector_hdr_data *sector_hdr_data_t;
```

其中每个成员的作用如下：
- status_table
store和dirty 2个标志中每个状态位错开在不同字节写入，利用了Flash整块擦除细粒度写的特点，保证标志更新操作的原子性同时，减少对Flash的擦除次数。
store使用3个Flash写单元（宏FDB_WRITE_GRAN定义写单元的比特大小，FDB_WRITE_GRAN为8时对应3个字节）表示页空间的4种状态（。状态FDB_SECTOR_STORE_UNUSED（全0xff，因为flash擦除后读出全为0xff）表示未格式化，FDB_SECTOR_STORE_EMPTY（单元1写零）表示当前页已经格式化但未使用，FDB_SECTOR_STORE_USING（单元1和2写零）表示当前页已经部分使用但是还有剩余空间，FDB_SECTOR_STORE_FULL（单元1,2和3写零）表示当前页空间完全使用玩了已经没有剩余空间。
dirty使用3个Flash写单元（宏FDB_WRITE_GRAN定义写单元的比特大小，FDB_WRITE_GRAN为8时对应3个字节）表示的Flash页空间回收的4种状态。FDB_SECTOR_DIRTY_UNUSED为Flash页擦除后的读出状态，FDB_SECTOR_DIRTY_FALSE（单元1写零）表示当前页已经格式化但未使用，FDB_SECTOR_DIRTY_TRUE（单元1和2写零）表示当前页已有条目写入，FDB_SECTOR_DIRTY_GC表示当前Flash页已经有过GC（垃圾回收，即已经对标记为删除的条目进行了回收）操作。

- magic
用于检查Flash页是否已格式化的魔数，(char [4])magic = {'F', 'D', 'B', '0'};

- combined
数据库下一页的页偏移，用于实现基于非连续Flash页的数据库，固定为0xFFFFFFFF，所以此功能目前代码没有实现

- reserved
保留，未使用

根据上面的介绍，数据库的Flash页头信息只有status_tablez字段会有数据库操作过程中变化，其他字段在数据库格式化后保持不变。

##### kvdb条目
第一个kvdb条目紧挨着页头数据写入flash。为了尽可能小的空间占用和灵活的数据条目大小支持，FlashDB检索条目时，先用魔数定位条目的位置，再对定位到的数据作CRC32检查有效性。代码中没有单独表示Flash中kvdb条目的结构体，kvdb条目的数据由`kv_hdr_data_t`结构体，和相应的key, value组成，写入过程参见create_kv_blob函数，完整的kvdb条目可用如下结构体表示：

```c
struct fdb_kv_item {
    uint8_t status_table[KVDB_STATUS_TABLE_SIZE];       /**< node status, @see fdb_kv_status_t */
    uint32_t magic;                              	    /**< magic word(`K`, `V`, `0`, `0`) */
    uint32_t len;                                		/**< node total length (header + name + value), must align by FDB_WRITE_GRAN */
    uint8_t name_len;                            		/**< name length */
    uint32_t value_len;                          		/**< value length */
    char name[FDB_KV_NAME_MAX];                  		/**< name */
    uint8_t value;                               		/**< value */
};
typedef struct fdb_kv_item *fdb_kv_item_t;
```

其中每个成员的作用如下：
- status
保存kvdb条目当前的状态，数组大小KVDB_STATUS_TABLE_SIZE取决于宏FDB_WRITE_GRAN定义写单元的比特大小，FDB_WRITE_GRAN为8时数组大小为5，状态数组status值对应的标志如下：

| status读出值                   | 表示状态          | 备注                                                         |
| :------------------------------ | :----------------- | :------------------------------------------------------------ |
| {0xFF, 0xFF, 0xFF, 0xFF, 0xFF} | FDB_KV_UNUSED     | flash擦除后的读出状态，当前空间未使用                        |
| {0, 0xFF, 0xFF, 0xFF, 0xFF}    | FDB_KV_PRE_WRITE  | kvdb条目已部分写入，代码中表示KV条目状态标志本身已写入       |
| {0, 0, 0xFF, 0xFF, 0xFF}       | FDB_KV_WRITE      | kvdb条目完全写入                                             |
| {0, 0, 0, 0xFF, 0xFF}          | FDB_KV_PRE_DELETE | kvdb条目准备删除                                             |
| {0, 0, 0, 0, 0xFF}             | FDB_KV_DELETED    | kvdb条目完成删除                                             |
| {0, 0, 0, 0, 0}                | FDB_KV_ERR_HDR    | kvdb条目校验失败或者其他错误，status最后一个单元会写零，GC时会被回收 |

- magic
  用于检索kvdb条目的魔数，`(char [4])magic = {'K', 'V', '0', '0'};`

- len

kvdb条目的总长度

- name_len

key的长度

- value_len

value的长度

- name

key的内容

- value

value的内容

上述kvdb数据内容实际写入flash的位置按结构体成员所占空空间和GRAN定义的写入单元对齐写入到Flash。

##### 写入flash的数据结构

FlashDB页格式化后，随后每次新增kv和更新kv，都会往后的Flash剩余空间紧挨着写入。只是在更新kv时，将前面的kv条目status标记为删除。以下说明了源码中的[boot_count示例代码](https://github.com/armink/FlashDB/blob/master/samples/kvdb_basic_sample.c)演示的kvdb条目创建和更新操作后的flash读出内容，配置作为flashDB页的起始地址为0x8030000：

![kvdb_readout.jpg](https://oss-club.rt-thread.org/uploads/20231228/20dd6c3f6bfca76b19d61b2f0bb7b1db.jpg.webp)

从flash读出的数据可以看出，flash页头大致只有一个标识的作用。页头和条目内部数据并不是完全紧挨着。因为FDB_WRITE_GRAN为8，写入数据的对齐方式和C代码中结构体中对齐方式一致。 后一kv条目紧挨着前一条。

##### tsdb页头

为了便于tsdb页条的检索，tsdb的页头包含额外的时序（时间戳）信息，指示该页包含条目的最小时序和最大时序，源码中的tsdb页头定义如下：

```c
struct sector_hdr_data {
    uint8_t status[FDB_STORE_STATUS_TABLE_SIZE]; /**< sector store status @see fdb_sector_store_status_t */
    uint32_t magic;                              /**< magic word(`T`, `S`, `L`, `0`) */
    fdb_time_t start_time;                       /**< the first start node's timestamp */
    struct {
        fdb_time_t time;                         /**< the last end node's timestamp */
        uint32_t index;                          /**< the last end node's index */
        uint8_t status[TSL_STATUS_TABLE_SIZE];   /**< end node status, @see fdb_tsl_status_t */
    } end_info[2];
    uint32_t reserved;
};
typedef struct sector_hdr_data *sector_hdr_data_t;
```

- status
  表示当前页的空间使用情况，和kvdb页头的status_table.store用法相同

- magic

用于检查Flash页是否已格式化的魔数，(char [4])magic = {'T', 'S', 'L', '0'};

- start_time

首次写入tsdb条目的时间，时间格式用户自定义（fsdb初始化函数需用户传入get_time回调函数）

- end_info[i].time

最近写入tsdb条目的时间，为了实现数据库操作的原子性，这里用到了2个end_info

- end_info[i].index

最近写入tsdb条目的地址

- end_info[i].status

最近写入tsdb条目的状态

- reserved

保留，未使用

tsdb设计上不仅要提供写入条目的时间点的查找，还要实现基于时间区间的查找，所以页表头也保存了当前页最早和最新条目的时序

##### tsdb条目

相比于kvdb基于魔数和CRC检验的条目检索方式，tsdb采用查找表的方式。包含**条目时序**，**值长度**和**值索引**的固定长度**条目键**从页头向页尾排布，**值索引**指向从页尾向页头排布的**条目值**，**条目值**可以是一个或多个数值，**条目键**和**条目值**的C代码表示如下：

```c
struct fdb_tsl_item {
    fdb_tsl_status_t status;                     /**< node status, @see fdb_log_status_t */
    fdb_time_t time;                             /**< node timestamp */
    uint32_t log_len;                            /**< log length, must align by FDB_WRITE_GRAN */
    uint32_t offset;							 /**< log address in current page */
};

char log[i];									/**< log data */
```

- status

保存tsdb条目当前的状态，表示方法同kvdb的status，tsdb条目包含6种状态标志，所以使用5个字节：

| status读出值                   | 表示状态             | 备注                                                   |
  | :------------------------------ | :-------------------- | :------------------------------------------------------ |
  | {0xFF, 0xFF, 0xFF, 0xFF, 0xFF} | FDB_TSL_UNUSED       | flash擦除后的读出状态，当前空间未使用                  |
  | {0, 0xFF, 0xFF, 0xFF, 0xFF}    | FDB_TSL_PRE_WRITE    | tsdb条目已部分写入，代码中表示TS条目状态标志本身已写入 |
  | {0, 0, 0xFF, 0xFF, 0xFF}       | FDB_TSL_WRITE        | tsdb条目完全写入                                       |
  | {0, 0, 0, 0xFF, 0xFF}          | FDB_TSL_USER_STATUS1 | tsdb条目用户自定义状态1，可用于表示数据已和云端同步    |
  | {0, 0, 0, 0, 0xFF}             | FDB_TSL_DELETED      | tsdb条目完成删除                                       |
  | {0, 0, 0, 0, 0}                | FDB_TSL_USER_STATUS2 | tsdb条目用户自定义状态2                                |

- time

tsdb写入时间

- log_len

tsdb条目值长度

- offset

tsdb条目的值索引，即条目值保存位置的页头偏移

- log

tsdb条目值

#### 缓存实现

#### GC实现

#### 其他功能的实现和改进点

#### db.sector_cache_table
因为数据项的大小和地址都是随机的，sector_cache_table用于缓存最近使用的sector剩余空间的起始地址。配合函数update_sector_cache用于更新cache和get_sector_from_cache用于简单地检查cache

#### format_sector
format_sector在检测sector未使用的情况下，如果未设置db->parent.not_formatable，会自动执行一次format_sector。但是在_fdb_kv_load流程中，根据如果check_fail_load == SECTOR_NUM，又会进行一次format_sector。

#### 磨损平衡的实现
- 条目删除时并不会马上格式化数据所占用的空间，而是标记条目状态位为删除，所以后面新增的条目会往扇区后面的空间持续写入。只有当所有扇区都写满的时候，才会启动回收，清空扇区中标记为已删除数据占用的空间，再次进行写入。
- 每次数据更新时不是在原来的位置上更改，而是在新的位置写入数据，将原来的数据占用的标记为删除