注册

FastKV：一个真的很快的KV存储组件

一、前言


KV存储无论对于客户端还是服务端都是重要的构件。

对于Android客户端而言，最常见的莫过于SDK提供的SharePreferences(以下简称SP)，但其低效率和ANR问题饱受诟病。

后来官方又推出了基于Kotlin的DataStore, 其中的Preferences DataStore，换汤不换药，底层的存储策略还是一样的，目测该有的问题还是有。

18年年末微信开源了MMKV, 有较高热度。

我之前写过一个叫LightKV的Android客户端的KV存储组件，开源时间比MMKV要早一点，但关注量不多……不过话说回来，由于当时认知不足，LightKV的设计也不够成熟。


1.1 SP的不足


关于SP的缺点网上有不少讨论，这里主要提两个点：



  • 保存速度较慢

SP用内存层用HashMap保存，磁盘层则是用的XML文件保存。

每次更改，都需要将整个HashMap序列化为XML格式的报文然后整个写入文件。

归结其较慢的原因：

1、不能增量写入；

2、序列化比较耗时。



  • 可以能会导致ANR

public void apply() {

    // ...省略无关代码...

    QueuedWork.addFinisher(awaitCommit);

    Runnable postWriteRunnable = new Runnable() {

        @Override

        public void run() {

            awaitCommit.run();

            QueuedWork.removeFinisher(awaitCommit);

        }

    };

    SharedPreferencesImpl.this.enqueueDiskWrite(mcr, postWriteRunnable);

}

public void handleStopActivity(IBinder token, boolean show, int configChanges,

                               PendingTransactionActions pendingActions, boolean finalStateRequest, String reason) {

    // ...省略无关代码...

    // Make sure any pending writes are now committed.

    if (!r.isPreHoneycomb()) {

        QueuedWork.waitToFinish();

    }

}

Activity stop时会等待SP的写入任务，如果SP的写入任务多且执行慢的话，可能会阻塞主线程较长时间，轻则卡顿，重则ANR。


1.2 MMKV的不足



  • 没有类型信息，不支持getAll

    MMKV的存储用类似于Protobuf的编码方式，只存储key和value本身，没有存类型信息（Protobuf用tag标记字段，信息更少）。

    由于没有记录类型信息，MMKV无法自动反序列化，也就无法实现getAll接口。
  • 读取相对较慢

    SP在加载的时候已经将value反序列化存在HashMap中了，读取的时候索引到之后就能直接引用了。

    而MMKV每次读取时都需要重新解码，除了时间上的消耗之外，还需要每次都创建新的对象。

    不过这不是大问题，相对SP没有差很多。
  • 需要引入so, 增加包体积

    引入MMKV需要增加的体积还是不少的，且不说jar包和aidl文件，光是一个arm64-v8a的so就有四百多K。


虽然说现在APP体积都不小，但毕竟增加体积对打包、分发和安装时间都多少有些影响。



  • 文件只增不减

    MMKV的扩容策略还是比较激进的，而且扩容之后不会主动trim size。

    比方说，假如有一个大value，让其扩容至1M，后面删除该value，哪怕有效内容只剩几K，文件大小还是保持在1M。
  • 可能会丢失数据

    前面的问题总的来说都不是什么“要紧”的问题，但是这个丢失数据确实是硬伤。

    MMKV官方有这么一段表述：

    通过 mmap 内存映射文件，提供一段可供随时写入的内存块，App 只管往里面写数据，由操作系统负责将内存回写到文件，不必担心 crash 导致数据丢失。





这个表述对一半不对一半。

如果数据完成写入到内存块，如果系统不崩溃，即使进程崩溃，系统也会将buffer刷入磁盘；

但是如果在刷入磁盘之前发生系统崩溃或者断电等，数据就丢失了，不过这种情况发生的概率不大；

另一种情况是数据写一半的时候进程崩溃或者被杀死，然后系统会将已写入的部分刷入磁盘，再次打开时文件可能就不完整了。

例如，MMKV在剩余空间不足时会回收无效的空间，如果这期间进程中断，数据可能会不完整。
MMKV官方的说明可以佐证：



CRC校验失败之后，MMKV有两种应对策略：直接丢弃所有数据，或者尝试读取数据（用户可以在初始化时设定）。

尝试读取数据不一定能恢复数据，甚至可能会读到一些错误的数据，得看运气。


这个过程是比较容易复现的，下面是其中一种复现路径：



  2. 新增和删除若干key-value
    得到数据如下：




  2. 插入一个大字符串，触发扩容，扩容前会触发垃圾回收




  3. 断点打在执行memmove的循环中，执行一部分memmove, 然后在手机上杀死进程






  2. 再次打开APP，数据丢失


相比之下，SP虽然低效，但至少不会丢失数据。


二、FastKV


在总结了之前的经验和感悟之后，笔者实现了一个高效且可靠的版本，且将其命名为: FastKV。


2.1 特性


FastKV有以下特性：



  2. 读写速度快

    • FastKV采用二进制编码，编码后的体积相对XML等文本编码要小很多。
    • 增量编码：FastKV记录了各个key-value相对文件的偏移量，更新数据时，可以直接在对应的位置写入数据。
    • 默认用mmap的方式记录数据，更新数据时直接写入到内存即可，没有IO阻塞。


  3. 支持多种写入模式

    • 除了mmap这种非阻塞的写入方式，FastKV也支持常规的阻塞式写入方式，
      并且支持同步阻塞和异步阻塞（分别类似于SharePreferences的commit和apply)。


  4. 支持多种类型

    • 支持常用的boolean/int/float/long/double/String等基础类型。
    • 支持ByteArray (byte[])。
    • 支持存储自定义对象。
    • 内置StringSet编码器 (为了兼容SharePreferences)。


  5. 方便易用

    • FastKV提供了了丰富的API接口，开箱即用。
    • 提供的接口其中包括getAll()和putAll()方法，
      所以迁移SharePreferences等框架的数据到FastKV很方便，当然，迁移FastKV的数据到其他框架也很方便。


  6. 稳定可靠

    • 通过double-write等方法确保数据的完整性。
    • 在API抛IO异常时提供降级处理。


  7. 代码精简

    • FastKV由纯Java实现，编译成jar包后体积仅30多K。



2.2 实现原理


2.2.1 编码


文件的布局：



[data_len | checksum | key-value | key-value｜....]




  • data_len: 占4字节, 记录所有key-value所占字节数。
  • checksum: 占8字节，记录key-value部分的checksum。

key-value的数据布局：


+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| delete_flag | external_flag | type  | key_len | key_content |  value  |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

|     1bit    |      1bit     | 6bits |  1 byte |             |         |


  • delete_flag ：标记当前key-value是否删除。
  • external_flag: 标记value部分是否写到额外的文件。

    注：对于数据量比较大的value,放在主文件会影响其他key-value的访问性能，因此，单独用一个文件来保存该value, 并在主文件中记录其文件名。
  • type: value类型，目前支持boolean/int/float/long/double/String/ByteArray以及自定义对象。
  • key_len: 记录key的长度，key_len本身占1字节，所以支持key的最大长度为255。
  • key_content: key的内容本身，utf8编码。
  • value: 基础类型的value, 直接编码（little-end）；

    其他类型，先记录长度（用varint编码），再记录内容。

    String采用UTF-8编码，ByteArray无需编码，自定义对象实现Encoder接口，分别在Encoder的encode/decode方法中序列化和反序列化。

2.2.2 存储




  • mmap

    为了提高写入性能，FastKV默认采用mmap的方式写入。




  • 降级

    当mmap API发生IO异常时，降级到常规的blocking I/O，同时为了不影响当前线程，会将写入放到异步线程中执行。




  • 数据完整性

    如果在写入一部分的过程中发生中断（进程或系统），则文件可能会不完整。

    故此，需要用一些方法确保数据的完整性。

    当用mmap的方式打开时，FastKV采用double-write的方式：数据依次写入A/B两个文件，确保任何时刻总有一个文件完整的； 加载数据时，通过checksum、标记、数据合法性检验等方法验证数据的正确性。

    double-write可以防止进程崩溃后数据不完整，但mmap是系统定时刷盘，若在刷盘系统崩溃或者断电，仍会丢失更新（之前的数据还在，仅丢失更新）。 可以通过调用force()强制刷盘，但这就不能发挥mmap的优点了。

    基于此，FastKV也支持用blocking I/O的方式写文件（比mmap慢，但是能确保数据真正落盘）。

    当用blocking I/O的写入时，先写临时文件，完整写入后再删除主文件，然后重命名临时文件为主文件。

    FastKV支持同步的和异步的blocking I/O，写入方式类似于SP的commit和apply，但是序列化key-value的部分是增量的，比SP的序列化整个HashMap的方式要快许多。




  • 更新策略（增/删/改）

    新增：写入到数据的尾部。

    删除：delete_flag设置为1。

    修改：如果value部分的长度和原来一样，则直接写入原来的位置；
    否则，先写入key-value到数据尾部，再标记原来位置的delete_flag为1（删除），最后再更新文件的data_len和checksum。




  • gc/truncate

    删除key-value时会收集信息（统计删除的个数，以及所在位置，占用空间等）。

    GC的触发点有两个：

    1、新增key-value时剩余空间不足，且已删除的空间达到阈值，且腾出删除空间后足够写入当前key-value, 则触发GC；

    2、删除key-value时，如果删除空间达到阈值，或者删除的key-value个数达到阈值，则触发GC。

    GC后如果不用的空间达到设定阈值，则触发truncate（缩小文件大小）。




2.3 使用方法


2.3.1 导入


dependencies {

    implementation 'io.github.billywei01:fastkv:1.0.2'

}

2.3.2 初始化


    FastKVConfig.setLogger(FastKVLogger)

    FastKVConfig.setExecutor(ChannelExecutorService(4))

初始化可以按需设置日志回调和Executor。

建议传入自己的线程池，以复用线程。


日志接口提供三个级别的回调，按需实现即可。


    public interface Logger {

        void i(String name, String message);


        void w(String name, Exception e);


        void e(String name, Exception e);

    }

2.3.3 数据读写



  • 基本用法

    FastKV kv = new FastKV.Builder(path, name).build();

    if(!kv.getBoolean("flag")){

        kv.putBoolean("flag" , true);

    }


  • 保存自定义对象

    FastKV.Encoder<?>[] encoders = new FastKV.Encoder[]{LongListEncoder.INSTANCE};

    FastKV kv = new FastKV.Builder(path, name).encoder(encoders).build();


    String objectKey = "long_list";

    List<Long> list = new ArrayList<>();

    list.add(100L);

    list.add(200L);

    list.add(300L);

    kv.putObject(objectKey, list, LongListEncoder.INSTANCE);


    List<Long> list2 = kv.getObject("long_list");

FastKV支持保存自定义对象，为了加载文件时能自动反序列化，需在构建FastKV实例时传入对象的编码器。

编码器为实现FastKV.Encoder的对象。

比如上面的LongListEncoder的实现如下：


public class LongListEncoder implements FastKV.Encoder<List<Long>> {

    public static final LongListEncoder INSTANCE = new LongListEncoder();


    @Override

    public String tag() {

        return "LongList";

    }


    @Override

    public byte[] encode(List<Long> obj) {

        return new PackEncoder().putLongList(0, obj).getBytes();

    }


    @Override

    public List<Long> decode(byte[] bytes, int offset, int length) {

        PackDecoder decoder = PackDecoder.newInstance(bytes, offset, length);

        List<Long> list = decoder.getLongList(0);

        decoder.recycle();

        return (list != null) ? list : new ArrayList<>();

    }

}

编码对象涉及序列化/反序列化。

这里推荐笔者的另外一个框架：github.com/BillyWei01/…


2.3.4 For Android


Android平台上的用法和常规用法一致，不过Android平台多了SharePreferences API，以及支持Kotlin。

FastKV的API兼容SharePreferences, 可以很轻松地迁移SharePreferences的数据到FastKV。

相关用法可参考：github.com/BillyWei01/…


三、 性能测试



  • 测试数据：搜集APP中的SharePreferenses汇总的部份key-value数据（经过随机混淆）得到总共四百多个key-value。由于日常使用过程中部分key-value访问多，部分访问少，所以构造了一个正态分布的访问序列。
  • 比较对象： SharePreferences 和 MMKV
  • 测试机型：荣耀20S

测试结果：



























写入(ms)读取(ms)
SharePreferences14906
MMKV349
FastKV141


  • SharePreferences提交用的是apply, 耗时依然不少。
  • MMKV的读取比SharePreferences要慢一些，写入则比之快许多。
  • FastKV无论读取还是写入都比另外两种方式要快。

四、结语


本文探讨了当下Android平台的各类KV存储方式，提出并实现了一种新的存储组件，着重解决了KV存储的效率和数据可靠性问题。

目前代码已上传Github: github.com/BillyWei01/…


作者：呼啸长风
链接：https://juejin.cn/post/7018522454171582500
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
0
分享
2021-10-15

0 个评论

要回复文章请先登录或注册

一个开放、互助、协作、创意的社区

关于imGeek
关于专职工程师值守
社区财富榜
赞助商
友情链接
热门标签
京ICP备2023000793号