KV V0.0.3 设计方案

[TOC]

背景

Key-value键值对存储在MCU项目中有很大的应用空间。BabyOS初期推出了一份比较粗糙的KV存储方案,现在希望对其进行重新设计,配合BabyOS使用,尽可能满足项目开发者的需要。

本次将记录详细的设计方案,有兴趣的爱好者均可以参与,讨论和修改方案,向BabyOS仓库提交代码。

问:开源社区已有easyflash等支持KV的项目了,怎么还重新搞一个呢?

答:出于两个方面:①技术爱好者不会停止“造轮子”,生命在于折腾。②希望BabyOS搭配的KV软件模块出自于BabyOS爱好者之手!

仓库地址:https://gitee.com/notrynohigh/BabyOS

文档地址:https://gitee.com/notrynohigh/BabyOS/wikis/Key-Value模块V0.0.3设计方案

[欢迎在wiki页面进行反馈和评论,也可以加入开发者群进行讨论!]

预期功能:

序号 功能点 一句话描述 备注
1 读取 用户根据key值得到value key: char * 字符串
value:
{
uint8_t *pvalue;
uint32_t len;
}
2 查询value长度 用户根据key可以查询到对应value的长度
3 修改(新建) 用户根据key新建或修改值 新建和修改是一样的
只需要提供修改接口
4 删除 用户不需要一项key-value对,
通过key进行删除
5 多区块 用户开辟了多块区域存储不同重要等级
的数据,多块区域都可以支持KV存储
6 支持存储器 用户希望可以存数据的地方就可以使用KV 使用BabyOS已有驱动
的存储器,持续更新
7 支持大数据块写入 用户希望写入的数据不局限于最小擦除单元
8 支持擦写均衡 用户希望做到擦写均衡保证FLASH的寿命
9 减小内存消耗 用户希望不要过多占用内存空间 实现后评估消耗内存的情况

旧方案的问题

①将key字符串转换为uint32_t类型的ID,无法避免有重复的ID出现。

原先这么设计主要是考虑比较数值快于比较字符串。待解决重复ID的问题。

②将存储空间分为两块,分为使用区和备份区。极大的降低了Flash的使用率。

③使用区域分为了表头区和数据区,无法以最优方案分配表头区和数据区各多少空间。

原先这么设计主要是考虑,表头区数据结构大小固定,可以快速查找。

④每次使用区域满后将数据整理到备份区,然后切换使用区和备份区的角色。数据搬运的频次多,而且量比较大。

重新设计存储策略,已保证预期功能的实现。

V0.0.3设计方案

区块状态

区块:Flash的最小擦除大小。

区块存在以下几种状态:

Empty (空)、Writable(使用中)、Full(满)、Messy(待整理)、Joint(联合区块)

../_images/BabyOSK-Vstatus.png

数据结构

考虑到有FLASH不支持单字节写入,数据结构每个单元使用4个字节宽度。

区块头部结构

存储项 数据类型 说明
标识符 uint32_t 固定 0x625F6B76
状态位 uint32_t [3] [0] 使用中
[1] 满/联合区块
[2]脏满

KV数据结构

存储项 数据类型 说明
标志符 uint32_t 固定 0x625F6B76
数据状态 uint32_t [31:24] 0xAA 已修改 0x55 已删除
[23:0] 修改后,存放的新地址
(新地址同区块可用,地址为当前区块的偏移地址
新地址跨区块则填0xFFFFFF)
key的md5值 uint64_t key计算md5的结果
value的校验值 uint32_t value计算CRC32的结果
key/value的长度 uint32_t [31:24] key的长度
[23] 联合体标记
[22:0] value的数据长度
key key限制在 1~255个字符。
value 数据由联合区块组成时,此处为联合区块地址
地址1/地址2.....每个地址占4个字节

区块整理

区块使用考虑均衡的问题,优先使用空区块,如果仅剩下1个空区块便进行脏区块的整理。

整理后的脏区块变为空区块,原先的空区块变为可写入区块。

区块1 2 3 4
脏满
脏满 脏满
脏满 脏满 脏满
脏满 脏满 可写入
脏满 脏满 脏满
可写入 脏满 脏满
脏满 脏满 脏满
脏满 可写入 脏满
脏满 脏满 脏满
脏满 脏满 可写入
脏满 脏满 脏满

代码流程

初始化流程

初始化主要确定:可写入区块、空区块数量以及可写入区块内的偏移(即下一个数据写入的地方)。

../_images/BabyOSK-Vinit.png

整理区块流程

BabyOS K-V整理区块流程

写入数据流程

BabyOS K-V写入数据流程

读取数据流程

BabyOS K-V读取数据流程

查找数据流程

BabyOS K-V查找数据流程