专栏首页呼啸长风的专栏FastKV:一个真的很快的KV存储组件
原创

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

一、前言

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

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

18年年末微信开源了MMKV, 写入速度前者快很多。

后来Android官方又推出了基于Kotlin的DataStore, 测试了一下,发现写入很慢。

我之前写过一个叫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,后面即使触发GC,哪怕有效内容有几K,文件大小还是保持在1M。
  • 可能会丢失数据 前面的问题总的来说都不是什么“要紧”的问题,但是这个丢失数据确实是硬伤。 MMKV官方有这么一段表述:通过 mmap 内存映射文件,提供一段可供随时写入的内存块,App 只管往里面写数据,由操作系统负责将内存回写到文件,不必担心 crash 导致数据丢失。

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

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

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

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

例如,MMKV在剩余空间不足时会回收无效的空间,如果这期间进程中断,数据可能会不完整。

MMKV官方的说明可以佐证:

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

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

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

  1. 新增和删除若干key-value 得到数据如下:
  1. 插入一个大字符串,触发扩容,扩容前会触发垃圾回收
  2. 断点打在执行memmove的循环中,执行一部分memmove, 然后在手机上杀死进程
  1. 再次打开APP,数据丢失

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

二、FastKV

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

2.1 特性

FastKV有以下特性:

  1. 读写速度快 - FastKV,二进制编码,编码后的体积相对XML等文本编码要小很多; - 增量编码:FastKV记录了各个key-value相对文件的偏移量(包括失效的key-value), 从而在更新数据时可以直接在指定的位置写入数据。 - 默认用mmap的方式记录数据,更新数据时直接写入到内存即可,没有IO阻塞。
  2. 支持多种写入模式 - 除了mmap这种非阻塞的写入方式,FastKV也支持常规的阻塞式写入方式, 并且支持同步阻塞和异步阻塞(分别类似于SharePreferences的commit和apply)。
  3. 支持多种类型
    • 支持常用的boolean/int/float/long/double/String等基础类型;
    • 支持ByteArray (byte[]);
    • 支持存储对象。
    • 内置Set<String>的编码器 (为了方便兼容SharePreferences)。
  4. 方便易用 - FastKV提供了了丰富的API接口,开箱即用。 - 提供的接口其中包括getAll()和putAll()方法, 所以迁移SharePreferences等框架的数据到FastKV很方便,当然,迁移FastKV的数据到其他框架也很方便。
  5. 稳定可靠
    • 通过double-write等方法确保数据的完整性。
    • 在API抛IO异常时提供降级处理。
  6. 代码精简
    • 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, 标记,数据合法性检验等方法验证数据的正确性。
  • 更新策略(增/删/改) 新增:写入到数据的尾部。 删除: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<>();
    }
}

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

这里推荐笔者的另外一个框架:https://github.com/BillyWei01/Packable

2.3.4 For Android

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

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

相关用法可参考:https://github.com/BillyWei01/FastKV/blob/main/android_case_CN.md

三、 性能测试

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

测试结果:

写入(ms)

读取(ms)

SharePreferences

1258

3

DataStore

16650

3

MMKV

25

9

FastKV

16

1

  • SharePreferences提交用的是apply, 耗时依然不少。
  • DataStroe写入很慢。
  • MMKV的读取比SharePreferences/DataStore要慢一些,写入则比之快许多。
  • FastKV无论读取还是写入都比其他方式要快。

四、结语

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

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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vivo 大规模特征存储实践

    本文旨在介绍 vivo 内部的特征存储实践、演进以及未来展望,抛砖引玉,吸引更多优秀的想法。

    2020labs小助手
  • 深入Go的Map使用和实现原理

    线性探测,字面意思就是按照顺序来,从冲突的下标处开始往后探测,到达数组末尾时,从数组开始处探测,直到找到一个空位置存储这个key,当数组都找不到的情况下回扩容(...

    阿伟
  • 【HBase】HBase迷你版MiniBase学习笔记

    HBase相对复杂,想要快速啃下来比较困难。而MiniBase吸收了HBase最核心的引擎部分的精华,希望可以通过学习MiniBase以小见大,能够对自己理解H...

    皮皮熊
  • 如何建设一个不限用户数且永远免费的Serverless SQL Database

    经历了 18 个月有挑战的工作后,我们运行第一个真正的可伸缩的 Serverless SQL Database。它现在可以使用了,而且免费。继续读下去,去了解 ...

    wubx
  • 区块链存储爆炸:问题、分析与优化

    DeFi、GameFi等去中心化应用的蓬勃发展,极大地增加了对低交易费用的高性能区块链的需求。然而,构建高性能区块链的一个关键挑战是存储爆炸。下图是取自 Eth...

    用户7358413
  • 选redis还是memcache,源码怎么说?

    memcache和redis是互联网分层架构中,最常用的KV缓存。不少同学在选型的时候会纠结,到底是选择memcache还是redis。

    架构师之路
  • 教你读懂大数据的技术生态圈

    大数据本身是个很宽泛的概念,Hadoop生态圈(或者泛生态圈)基本上都是为了处理超过单机尺度的数据处理而诞生的。你可以把它比作一个厨房所需要的各种工具:锅碗瓢盆...

    华章科技
  • 美团万亿级 KV 存储架构与实践

    在 2019 年 QCon 全球软件开发大会(上海站)上,美团高级技术专家齐泽斌分享了《美团点评万亿级 KV 存储架构与实践》,本文系演讲内容的整理,第一部分讲...

    美团技术团队
  • WiscKey —— SSD 介质下的 LSM-Tree 优化

    LSM-tree 是大数据时代一个经典的存储结构,是 Bigtable,Habse,LevelDB,RocksDB 等大数据存储的构建基础。LSM-tree 高...

    青藤木鸟
  • hbase源码系列(十三)缓存机制MemStore与Block Cache

    这一章讲hbase的缓存机制,这里面涉及的内容也是比较多,呵呵,我理解中的缓存是保存在内存中的特定的便于检索的数据结构就是缓存。 之前在讲put的时候,put是...

    岑玉海
  • 谈谈 KV 存储集群的设计要点

    不同于无数据的逻辑层框架,KV 存储系统的架构设计会更复杂、运维工作更繁琐、运营过程中可能出现的状况更多、bug 收敛时间会更长。一句话:团队自己做一个 KV ...

    廖念波
  • TiKV 源码解析系列文章(十一)Storage - 事务控制层

    TiKV 是一个强一致的支持事务的分布式 KV 存储。TiKV 通过 raft 来保证多副本之间的强一致,事务这块 TiKV 参考了 Google 的 Perc...

    PingCAP
  • 三篇文章了解 TiDB 技术内幕:说计算

    上一篇文章介绍了 TiDB 如何存储数据,也就是 TiKV 的一些基本概念。本篇将介绍 TiDB 如何利用底层的 KV 存储,将关系模型映射为 Key-Valu...

    PingCAP
  • TiDB EcoSystem Tools 原理解读系列(二)TiDB-Lightning Toolset 介绍

    TiDB-Lightning Toolset 是一套快速全量导入 SQL dump 文件到 TiDB 集群的工具集,自 2.1.0 版本起随 TiDB 发布,速...

    PingCAP
  • 增值税:多层关键值商店的渐近成本分析(CS.DC)

    在过去的几年中,键值(KV)商店设计的数量不断增加,每种设计都针对不同的需求进行了优化。此外,随着存储技术的进步,KV商店的设计空间变得更加复杂。最近的KV商店...

    蔡小雪7100294
  • PingCAP刘奇:如何构建一个NewSQL数据库

    大家好,我是PingCAP CEO刘奇。今天我将和大家分享一下如何构建一个NewSQL数据库。 首先,来介绍下我自己。和你们当中很多人一样,我是一名开源Hack...

    CSDN技术头条
  • 我们为什么放弃了TiDB,选择自研NewSQL

    Fusion-NewSQL是由滴滴自研的在分布式KV存储基础上构建的NewSQL存储系统。Fusion-NewSQ兼容了MySQL协议,支持二级索引功能,提供超...

    Bug开发工程师
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

    这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如:lsm派系难道只有lsm tree这一类存储模型吗?如果答案是否定的,...

    jaydenwen123
  • GaussDB(for Redis)揭秘第13期:如何搞定推荐系统存储难题?

    【摘要】 GaussDB(for Redis)轻松搞定推荐系统核心存储,为企业级应用保驾护航。

    玖柒的小窝

扫码关注云+社区

领取腾讯云代金券