KV 存储那些事儿

简介: 开发中,我们总会需要存储些 KV 数据,虽然看上去简单,但考虑因素也是很多的,实现手段也就各有差异。今天,我们就来看看 Android 目前有哪些 KV 库可以供我们使用,以及其有哪些优缺点。

开发中,我们总会需要存储些 KV 数据,虽然看上去简单,但考虑因素也是很多的,实现手段也就各有差异。今天,我们就来看看 Android 目前有哪些 KV 库可以供我们使用,以及其有哪些优缺点。

SharedPreferences


这个是 Android 很早就内置的 KV 存储库了, 不过由于其缺点多,目前除了拿来做源码分析和数落外,就没人会推荐使用了。其被诟病的点主要有以下几个:

1.首次子线程加载,在加载未完成时,主线程读取会阻塞等待加载完成。

2.会整个文件加载到内存,并且是 xml 格式。所以如果存储很多 kv,首次加载会很耗时,而且占内存,占存储。

3.commit 会阻塞写文件,并且是每次写入整个文件,所以一般用 apply。4.waitToFinish 会阻塞主线程,可能造成 ANR。

Jetpack DataStore


官方终于不想听开发者对 sp 的吐槽了,然后开发了 DataStore 这个新库,相比于 sp, 它有以下几个改进:

1.使用协程、Flow 等工具,在 Dispatchers.IO读写,不会阻塞主线程,当然这也导致必须在协程环境调用。

2.可以使用 proto 来序列化数据,因而存储体积会小很多

3.不需要调用 commit/apply


但其依旧是初始化时读取整个文件,写入时覆盖整个文件,对于很多 kv 的场景依旧不友好。

MMKV


MMKVTencent 开源的跨平台 kv 存储,其优点是:

1.可以跨平台使用,如果有跨平台需求,这是不二之选

2.文件增量写入,使用 proto 序列化数据,并且使用了 mmap,所以写入很快。


问:文件增量是一个怎样的逻辑?

答:每次写入一个 kv, 就直接在文件末尾追加这个 kv 的数据。当然,如果多次写入同一个 key,那么就会在文件中写入多份数据,这是以空间换时间的思路。在首次加载时,会从文件开始读到文件结束,对于重复 key, 后读的就会覆盖前面读的,所以如果有很多重复,这里就会存在额外耗时,当然,MMKV 会进行数据的重整理,就是把内存数据重新落盘,这样就去掉了重复 key

MMKV 依旧是会把所有数据一次性加载到内存,所以依旧不能用于很多 kv 的情况。

LevelDB


LevelDBgoogle 开源的,基于 LSM-Tree(Log Structured Merge Trees)


首先我们来了解下它的工作原理。


其核心结构为:

1.MemTable: 一个内存 kv 表, 其key 是有序的。

2.SSTable:将其 MemTable 落地到磁盘,就是 SSTable 了,其 key 是有序的,所以可以二分查找。

3.WAL: write ahead log, 在写数据时,先写入 WAL, 再写入 MemTable, 主要用于数据恢复,例如如果 MemTable 还没落地就杀死了进程,那么重启时可以用 WAL 恢复出 MemTable

其具体工作流程为:

写数据


1.写 WAL

2.写入 MemTable

3.如果 MemTable 多到一定程度,则落地成一个 SSTable

读数据


1.先看 MemTable 里有没有,如果有,则代表是刚写过的,直接返回,如果没有,则进行下一步。

2.查找最新落地的 SSTable,如果有,则返回,如果没有,则寻找下一个 SSTable,知道最后一个 SSTable


当然,如果落地了非常多的 SSTable, 如果最后一个 SSTable 才存在我们的数据,那查找就会非常耗时,所以这里就有很多优化。诸如:SSTable 合并,布隆过滤器、Cache等。

综上,LevelDB 的写入很快,读取反而很复杂的库。很适用于写多于读的场景。当然它读取还是很可观的。并且它不会把所有数据读入内存,所以终于是一个可以用于很多 kv 的场景了。


但是,它是一个纯 c++ 库,并不是面向 Android 而生,当然有人把它接入了 Android,例如:hf/leveldb-android,使得 Android 也能使用它,可惜的是,这个库并没有继续更新了。


而且 LevelDB 会产生 Lock 文件以防止其它进程使用,但如果我强杀进程,这个文件还在,所以 Open 可能会失败,需要再主动删文件。。。

EmoKV


最后,就要来吹一波自己新造的这个轮子了,具体用法可以前往官网查看 造这个轮子的主要原因是,LevelDB 的的确确不更新了,而且对于 Android, 可能依旧是读大于写多一点。所以我思考了下,搞了这个库,顺便实践了下 c++ (写起来真特么痛苦~)。


EmoKV 主要有以下几个结构:

1.Key 文件: 存储 key 值的文件,采用mmap + 追加写的方式

2.Value 文件: 存储 value 值的文件,采用mmap + 追加写的方式

3.Index 文件: 一个文件 HashMap 的实现, 所有 kv 都记录在这里,每个 kv 固定 20 字节(存储了 flagkeyKey 文件的位置以及 valueValue 文件的位置)。


其操作流程为:

  • 写数据:通过 key 定位 Index 位置,如果 key 不存在,则写 Key 文件,然后写 Value 文件,这两者都是追加写。写完更新 Index 文件信息。
  • 读数据:通过 key 定位 Index 位置,然后通过 Index 信息读取 Value 文件。


因为直接借助了 mmap, 所以其读写速度都是很快的,而且保证了数据刷入磁盘(当然这是非强制宕机的情况)。而且 mmap 也是在访问时才真的读取磁盘页,实际内存占用不大,而且可以由系统管理刷回。


当然,因为使用 mmap,所以也有潜在的问题:

1.数据太多导致虚拟内存用尽。当然这还是有难度的,即使是10w个 kvIndex 用量大概为:10w * 20 / 0.75 大约 2.6M 的空间(0.75 为加载因子),Value 以平均 500 字节的长度,大约 48M 的长度。对于一般应用,这个是足够的了。当然如果在非压缩,不应用 CRC32 的情况, Index 可以直接存储8字节以下的 value,空间就更可控了。

2.如果 key 算出来 hash 冲突很高,由于采用线性探测法,也会导致读写性能变差。 Index 文件还存在扩容的重量级操作。

3.由于 KeyValue 都采用追加写,在多次重复 kv 写入后,Value 就会存在很多过时数据,所以 EmoKV 依然有重整理的步骤。


当然,由于是个人开发的这个库,就还能聊更多细节的点:

1.EmoKV 采用写加锁,读没有加锁,而是采用乐观锁 StampedLock 类似的方式。每次写时增加版本号,读取时,先读取当前版本号,如果读取完之后,发现版本号变了,如果变化版本大于1或者且最近一次修改为当前 kv, 则重新读。因为一般读比写快,而且读写冲突概率低,这样更合理

2.由于写分了多个步骤,所以要考虑写入过程中进程退出的情况:我这里采用的方式是写入前先备份索引数据,并先写标记位,如果初始化时发现有标记时,就将备份数据还原回去,上一份数据失败。当然,使用者还可以开启 crc32 校验数据。

3.对于数据压缩和 crc32校验,一般的想法都是在 c++ 上实现,不过我嫌写起来困难,就在 kotlin 层调用内置库方法实现了。

4.使用 raii 管理内存,所以内存泄漏的可能性很低。

读写性能对比


最后,我简单对比了 LevelDBMMKVEmoKV 的读写速度。(本来打算用 benchmark 的,不过不知为何,我的 win 机一直跑不起来,报 Activity Missing,各种搜索都没解决。只得放弃,用单元测试时间代替。)


个人测试的是 1w 数据的读写。

写入数据


4b795f4f7a07780cbba76c685df9e67.png

单线程读取


6c302acbe0a817a1adf9c53cde6d878.png

多线程读取


8531fa011043b9570c63821a3fe56ea.png

因为并不是真的 benchmark,所以数据具有偶然性,但大体数量级没差。如果你有兴趣,也可以根据不同实现方案,简要分析下为何数据是这个样子?


最后,这个是个人第一次 c++ 实战,或许有诸多不正确不完美的地方,欢迎大家来做 Code Review


目录
相关文章
|
2月前
|
存储 缓存 固态存储
一文看懂存储,你看懂了吗?
一文看懂存储,你看懂了吗?
|
3月前
|
存储 Kubernetes 测试技术
在k8s中,有哪些存储?
在k8s中,有哪些存储?
|
12月前
|
存储 网络协议 NoSQL
从零实现kv存储V1.0:array初版
从零实现kv存储V1.0:array初版
80 1
|
12月前
|
存储 测试技术
从零实现kv存储V2.0
从零实现kv存储V2.0
161 1
|
6月前
|
存储 缓存 NoSQL
键值存储
键值存储
315 1
|
存储 NoSQL Java
从Redis源码上来聊聊KV模型-Hash数据类型
>之前就说了要来西索Redis,现在来辣! >本文的部分内容参考自《小林Coding》,部分地方根据源代码进行剖析。 >Redis源码地址:https://github.com/redis/redis.git >阅读本文之前建议先阅读我的上一篇文章:[神奇,Redis存储原理竟然是这样! – Karos (wzl.fyi)](https://www.wzl.fyi/2023/07/20/986/)
227 3
从Redis源码上来聊聊KV模型-Hash数据类型
|
存储 缓存 固态存储
一文看懂存储
一文看懂存储
231 1
|
存储 SQL NoSQL
存储的未来
存储的未来
117 1
|
存储 应用服务中间件 nginx
k8s--数据存储、EmptyDir存储
k8s--数据存储、EmptyDir存储
|
存储 算法
实现分布式 kv—1 Standalone KV
TinyKV 是 PingCAP 的一个开源课程:https://github.com/tidb-incubator/tinykv,旨在实现一个简易的分布式 kv,其中很多代码框架它已经提供了,我们只需要填充具体的逻辑即可。
415 0