开发中,我们总会需要存储些 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
MMKV 是 Tencent
开源的跨平台 kv
存储,其优点是:
1.可以跨平台使用,如果有跨平台需求,这是不二之选
2.文件增量写入,使用 proto 序列化数据,并且使用了 mmap
,所以写入很快。
问:文件增量是一个怎样的逻辑?
答:每次写入一个 kv
, 就直接在文件末尾追加这个 kv
的数据。当然,如果多次写入同一个 key
,那么就会在文件中写入多份数据,这是以空间换时间的思路。在首次加载时,会从文件开始读到文件结束,对于重复 key
, 后读的就会覆盖前面读的,所以如果有很多重复,这里就会存在额外耗时,当然,MMKV
会进行数据的重整理,就是把内存数据重新落盘,这样就去掉了重复 key
。
而 MMKV
依旧是会把所有数据一次性加载到内存,所以依旧不能用于很多 kv
的情况。
LevelDB
LevelDB 是 google
开源的,基于 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
字节(存储了 flag
、key
在 Key
文件的位置以及 value
在 Value
文件的位置)。
其操作流程为:
- 写数据:通过
key
定位Index
位置,如果key
不存在,则写Key
文件,然后写Value
文件,这两者都是追加写。写完更新Index
文件信息。 - 读数据:通过
key
定位Index
位置,然后通过Index
信息读取Value
文件。
因为直接借助了 mmap
, 所以其读写速度都是很快的,而且保证了数据刷入磁盘(当然这是非强制宕机的情况)。而且 mmap
也是在访问时才真的读取磁盘页,实际内存占用不大,而且可以由系统管理刷回。
当然,因为使用 mmap
,所以也有潜在的问题:
1.数据太多导致虚拟内存用尽。当然这还是有难度的,即使是10w个 kv
, Index
用量大概为:10w * 20 / 0.75
大约 2.6M
的空间(0.75 为加载因子),Value
以平均 500
字节的长度,大约 48M
的长度。对于一般应用,这个是足够的了。当然如果在非压缩,不应用 CRC32
的情况, Index
可以直接存储8字节以下的 value
,空间就更可控了。
2.如果 key
算出来 hash
冲突很高,由于采用线性探测法,也会导致读写性能变差。 Index
文件还存在扩容的重量级操作。
3.由于 Key
和 Value
都采用追加写,在多次重复 kv
写入后,Value
就会存在很多过时数据,所以 EmoKV
依然有重整理的步骤。
当然,由于是个人开发的这个库,就还能聊更多细节的点:
1.EmoKV
采用写加锁,读没有加锁,而是采用乐观锁 StampedLock
类似的方式。每次写时增加版本号,读取时,先读取当前版本号,如果读取完之后,发现版本号变了,如果变化版本大于1或者且最近一次修改为当前 kv
, 则重新读。因为一般读比写快,而且读写冲突概率低,这样更合理
2.由于写分了多个步骤,所以要考虑写入过程中进程退出的情况:我这里采用的方式是写入前先备份索引数据,并先写标记位,如果初始化时发现有标记时,就将备份数据还原回去,上一份数据失败。当然,使用者还可以开启 crc32
校验数据。
3.对于数据压缩和 crc32
校验,一般的想法都是在 c++
上实现,不过我嫌写起来困难,就在 kotlin
层调用内置库方法实现了。
4.使用 raii
管理内存,所以内存泄漏的可能性很低。
读写性能对比
最后,我简单对比了 LevelDB
、MMKV
、EmoKV
的读写速度。(本来打算用 benchmark
的,不过不知为何,我的 win
机一直跑不起来,报 Activity Missing
,各种搜索都没解决。只得放弃,用单元测试时间代替。)
个人测试的是 1w
数据的读写。
写入数据
单线程读取
多线程读取
因为并不是真的 benchmark
,所以数据具有偶然性,但大体数量级没差。如果你有兴趣,也可以根据不同实现方案,简要分析下为何数据是这个样子?
最后,这个是个人第一次 c++
实战,或许有诸多不正确不完美的地方,欢迎大家来做 Code Review
。