从零手写实现简易版MMKV（一）

概述

MMKV是支持多平台的高性能键值对持久化存储组件，其核心原理是利用mmap内存映射文件，关于它的详细介绍和更多原理参看MMKV开源git地址。

从零开始手写（其实是抄写-.-!）简易版MMKV（另起名叫EZKV），即先只关注最核心的功能（实现最小化系统），再从主干开枝散叶，逐步进行完善。

预期目标

第一版目标仅实现最基本的key-value数据存储和读取功能，先忽略数据加密、数据校验、数据容错、跨平台、线程同步、进程同步、ASHMEM等等等。

其中还涉及到几个比较关键的前置知识，需要提前熟悉：

• 【mmap内存映射文件】 最核心的原理。
• 【protobuf变长编码】 数据存储格式，key-value写入、读取、计算大小都是按照变长编码方式。必须先知道原理，才能理解代码中的位运算操作。

技术设计

主要逻辑在Native层，Java作为门面通过JNI调用C/C++。

以下列举了几个关键类的作用：

EZKV即操作门面，一个EZKV实例对应一个存储key-value数据的文件：

• m_mmapID：EZKV ID，默认为”ezkv.default”
• m_path：数据文件路径，EZKVPath_t是std::string的类型别名
• m_dic：缓存key-value的容器，EZKVMAP即std::unordered_map<std::string, KeyValueHolder>
• m_file：表示内存映射文件
• m_actualSize：记录存储的key-value数据的内容的大小
• m_output：用于写入key-value的辅助类

MemoryFile表示内存映射文件，封装内存映射相关操作，记录内存信息：

• m_name：数据文件路径
• m_fd：数据文件描述符
• m_ptr：m_fd内存映射分配的起始地址
• m_size：文件大小，也是映射内存分配的大小

KeyValueHolder用于记录一条KV对。注意m_dic中的value项不是直接存的value值，而是KeyValueHolder，通过其中记录的信息再来获取映射内存中的值：

• computedKVSize：基于offset的偏移量 = key size + key + value size， 可以直接定位到该KV对的value值
• keySize：key值占用的大小
• valueSize：value值占用的大小
• offset：从m_ptr开始到该KV对的偏移量，可以快速定位到该KV对

MMBuffer作用相当于读取或写入时的缓冲区：

union {
  struct {
    MMBufferCopyFlag isNoCopy;
    size_t size; // 几字节数据
    void *ptr; // 内存起始地址
  };
  struct {
    uint8_t paddedSize;
    // make at least 10 bytes to hold all primitive types (negative int32, int64, double etc) on 32 bit device
    // on 64 bit device it's guaranteed larger than 10 bytes
    uint8_t paddedBuffer[10]; // 用于存储较小的基本类型的值，存储在栈上，而不是堆上，避免malloc和free
  };
};
复制代码

CodedOutputData用于写入数据，封装了写入的方法：

• m_ptr：写入到的区域的起始地址
• m_size：可写入区域的大小
• m_position：当前写入位置

CodedOutputData用于读取数据，封装了读取的方法：

• m_ptr：从区域读取的起始地址
• m_size：可读取区域的大小
• m_position：当前读取位置

编码实现

完整项目工程见GitHub：github.com/chidehang/E…

SDK初始化

初始化主要完成三件事：
1.加载库、动态注册函数
2.初始化一些全局变量
3.创建存放数据文件的目录

提供给接入方的初始化方法，首先获取存储数据文件的目录的路径，接着加载库，最后调用native方法进行初始化，核心逻辑都在native方法中：

[EZKV.java]

public static String initialize(Context context) {
  String root = context.getFilesDir().getAbsolutePath() + "/ezkv";

  // 加载so库
  System.loadLibrary("ezkv");

  // 传入目录进行初始化
  nInitialize(root);
  EZKV.rootDir = root;
  return EZKV.rootDir;
}

private static native void nInitialize(String rootDir);
复制代码

JNI中函数有静态注册和动态注册，这里采用动态注册的方式，当执行loadLibrary后会回调JNI_OnLoad函数，在该函数中进行函数绑定注册：

[native-bridge.cpp]

extern "C" JNIEXPORT jint JNICALL JNI_OnLoad(JavaVM *vm, void *reserved) {
    // 提前缓存后续会用到但不会改变的jclass和g_fileID
    g_currentJVM = vm;
    JNIEnv *env;
    if (vm->GetEnv(reinterpret_cast<void **>(&env), JNI_VERSION_1_6) != JNI_OK) {
        return -1;
    }

    if (g_cls) {
        env->DeleteGlobalRef(g_cls);
    }
    static const char *clsName = "com/cdh/ezkv/EZKV";
    jclass instance = env->FindClass(clsName);
    if (!instance) {
        LOGE("fail to locate class: %s", clsName);
        return -2;
    }
    g_cls = reinterpret_cast<jclass>(env->NewGlobalRef(instance));
    if (!g_cls) {
        LOGE("fail to create global reference for %s", clsName);
        return -3;
    }

    // 动态注册函数
    int ret = registerNativeMethods(env, g_cls);
    if (ret != 0) {
        LOGE("fail to register native methods for class %s, ret = %d", clsName, ret);
        return -4;
    }

    g_fileID = env->GetFieldID(g_cls, "nativeHandle", "J");
    if (!g_fileID) {
        LOGE("fail to locate fileID");
        return -5;
    }

    return JNI_VERSION_1_6;
}
复制代码

TIPS：通常在库加载时提前缓存会用到的jclass和g_fileID，避免JNI调用时再查找，提升效率。

进一步看registerNativeMethods函数，在该方法中注册函数映射表：

[native-bridge.cpp]

static JNINativeMethod g_methods[] = {
        {"nInitialize", "(Ljava/lang/String;)V", (void *) ezkv::nInitialize},
        {"nGetDefaultEZKV", "()J", (void *) ezkv::nGetDefaultEZKV},
        {"nPageSize", "()J", (void *) ezkv::nPageSize},
        {"nEncodeInt", "(JLjava/lang/String;I)Z", (void *) ezkv::nEncodeInt},
        {"nDecodeInt", "(JLjava/lang/String;I)I", (void *) ezkv::nDecodeInt},
        {"nEncodeString", "(JLjava/lang/String;Ljava/lang/String;)Z", (void *) ezkv::nEncodeString},
        {"nDecodeString", "(JLjava/lang/String;Ljava/lang/String;)Ljava/lang/String;", (void *) ezkv::nDecodeString},
        // ···
};

static int registerNativeMethods(JNIEnv *env, jclass cls) {
    return env->RegisterNatives(cls, g_methods, sizeof(g_methods) / sizeof(g_methods[0]));
}
复制代码

JNINativeMethod结构体中name表示Java层的native方法名称，signature表示方法签名，fnPtr表示函数指针。
最终调用RegisterNatives函数进行动态注册。

完成库加载后，接着调用nInitialize方法进行初始化，实现对应的函数中的初始化逻辑：

[native-bridge.cpp]

EZKV_JNI void nInitialize(JNIEnv *env, jclass cls, jstring rootDir) {
  if (!rootDir) {
    return;
  }
  const char *kstr = env->GetStringUTFChars(rootDir, nullptr);
  if (kstr) {
    EZKV::initializeEZKV(kstr);
    env->ReleaseStringUTFChars(rootDir, kstr);
  }
}
复制代码

EZKV_JNI宏是static，限定函数的可见范围。

具体初始化逻辑放在initializeEZKV函数中：

[EZKV.cpp]

void initialize() {
    // 创建用于缓存EZKV实例的map
    g_instanceDic = new unordered_map<std::string, EZKV *>;
    // 获取一页内存大小（4KB）
    ezkv::DEFAULT_EZKV_SIZE = ezkv::getPageSize();
}

pthread_once_t once_control = PTHREAD_ONCE_INIT;

void EZKV::initializeEZKV(const EZKVPath_t &rootDir) {
    // 执行initialize函数
    pthread_once(&once_control, initialize);

    g_rootDir = rootDir;
    // 检查目录，不存在则创建
    mkPath(g_rootDir);
}
复制代码

pthread_once确保多线程环境中，仅会执行一次initialize函数。

EZKV实例初始化

获取EZKV实例主要逻辑是：
1.根据ID从g_instanceDic中查找，存在则直接返回
2.创建EZKV，构造函数中进行mmap相关初始化
2.1 根据ID获取数据文件路径，进行open->ftruncate->mmap操作
2.2 创建用于缓存key-value的map容器
2.3 读取数据文件中记录的KV内容大小
2.4 若有KV对，则读取到map中缓存
2.5 创建写入辅助对象CodedOutputData
3.将新建的EZKV添加进g_instanceDic

首先实现提供给接入方获取默认EZKV实例的defaultEZKV方法：

[EZKV.java]

private final long nativeHandle;

private EZKV(long handle) {
  // 记录Native对象指针
  nativeHandle = handle;
}

public static EZKV defaultEZKV() {
  if (rootDir == null) {
    throw new IllegalStateException("尚未初始化。");
  }
  // 调用native方法获取
  long handle = nGetDefaultEZKV();
  if (handle == 0) {
    return null;
  }
  return new EZKV(handle);
}
复制代码

实现对应的native函数：

[native-bridge.cpp]

EZKV_JNI jlong nGetDefaultEZKV(JNIEnv *env, jclass cls) {
  EZKV *kv = nullptr;
  kv = EZKV::defaultEZKV();
  return (jlong) kv;
}
复制代码

[EZKV.cpp]

EZKV *EZKV::defaultEZKV() {
    // DEFAULT_EZKV_ID是默认ID值为"ezkv.default"，DEFAULT_EZKV_SIZE即初始化时获取的内存页大小4KB
    return ezkvWithID(DEFAULT_EZKV_ID, DEFAULT_EZKV_SIZE);
}

EZKV *EZKV::ezkvWithID(const string &ezkvID, int size) {
    if (ezkvID.empty()) {
        return nullptr;
    }

    // 返回md5后的ID，如果是默认ID则原样返回
    auto mmapKey = mmapedKVKey(ezkvID);
    // 从map查找缓存
    auto itr = g_instanceDic->find(mmapKey);
    if (itr != g_instanceDic->end()) {
        // 已有则直接返回
        EZKV *kv = itr->second;
        return kv;
    }

    auto kv = new EZKV(mmapKey);
    (*g_instanceDic)[mmapKey] = kv;
    return kv;
}
复制代码

首次获取EZKV时没有缓存则新建，在构造函数中进行数据初始化操作：

[EZKV_Android.cpp]

EZKV::EZKV(const string &mmapID)
        : m_mmapID(mmapedKVKey(mmapID))
        , m_path(mappedKVPathWithID(mmapID)) // 目录拼接ID得到文件路径
        , m_dic(nullptr)
        // 创建MemoryFile
        , m_file(new MemoryFile(m_path)) {
    m_actualSize = 0;
    m_output = nullptr;

    // 创建key-value缓存容器
    m_dic = new EZKVMAP();

    // 从文件读取数据
    loadFromFile();
}
复制代码

得到数据文件路径m_path后，创建MemoryFile，在构造函数中打开文件进行映射：

[MemoryFile.cpp]

MemoryFile::MemoryFile(const EZKVPath_t &path)
  : m_name(path), m_fd(-1), m_ptr(nullptr), m_size(0) {
    reloadFromFile();
}

void MemoryFile::reloadFromFile() {
  if (isFileValid()) {
    // 容错检测，已经mmap过，则需要munmap，重置成员变量。
    clearMemoryCache();
  }

  // 打开文件
  m_fd = open(m_name.c_str(), O_RDWR | O_CREAT | O_CLOEXEC, S_IRWXU);
  if (m_fd < 0) {
    LOGE("fail to open:%s, %s", m_name.c_str(), strerror(errno));
  } else {
    // 获取文件大小赋值给m_size
    ezkv::getFileSize(m_fd, m_size);
    if (m_size < DEFAULT_EZKV_SIZE || (m_size % DEFAULT_EZKV_SIZE != 0)) {
      // 文件大小不是内存页大小整数倍
      size_t roundSize = ((m_size / DEFAULT_EZKV_SIZE) + 1) * DEFAULT_EZKV_SIZE;
      // 调整文件大小为4KB的整数倍
      truncate(roundSize);
    } else {
      // 进行内存映射
      auto ret = mmap();
      if (!ret) {
        doCleanMemoryCache(true);
      }
    }
  }
}
复制代码

getFileSize函数中通过fstat函数来获取文件信息。

获取到文件大小后，若文件大小不是4KB的整数倍，需要通过ftruncate函数扩容，并在文件扩容后填充’0’，最后执行mmap函数进行映射。

MemoryFile中完成了内存映射文件，并保存了映射内存地址和大小。接下来开始初始加载文件中的数据，在实现loadFromFile函数前先看下文件格式：

**文件起始固定4字节存储数据内容大小。**接着4字节存储ItemSizeHolder，加密场景使用，可先忽略。后面便开始存储key-value。

ItemSizeHolder值为0x00ffffff，按变长编码写入文件为0xffffff07，初始读取key-value时会跳过ItemSizeHolder占用的4字节。

如上图例子所示，头4字节的actualSize换算成十进制是20，后面数据内容占用20个字节（包括ItemSizeHolder和所有KV对）。

[EZKV_IO.cpp]

void EZKV::loadFromFile() {
    if (!m_file->isFileValid()) {
        m_file->reloadFromFile();
    }
    if (!m_file->isFileValid()) {
        LOGE("file [%s] not valid", m_path.c_str());
    } else {
        // 获取有效内容大小
        checkDataValid();
        auto ptr = (uint8_t *) m_file->getMemory();
        if (m_actualSize > 0) {
            // 有内容
            MMBuffer inputBuffer(ptr + Fixed32Size, m_actualSize, MMBufferNoCopy);
            clearDictionary(m_dic);
            // 读取key-value数据填充m_dic
            MiniPBCoder::decodeMap(*m_dic, inputBuffer);
            // 创建写入辅助类，从映射内存偏移4字节开始（头4字节是存内容大小），可写空间为fileSize-4字节
            m_output = new CodedOutputData(ptr + Fixed32Size, m_file->getFileSize() - Fixed32Size);
            // 定位到文件实际内容尾部，后续直接从尾部添加KV对
            m_output->seek(m_actualSize);
        } else {
            m_output = new CodedOutputData(ptr + Fixed32Size, m_file->getFileSize() - Fixed32Size);
        }
    }
}
复制代码

读取文件中记录的ActualSize：

[EZKV_IO.cpp]

void EZKV::checkDataValid() {
    // 读取文件前4byte获得内容大小
    m_actualSize = readActualSize();
}

size_t EZKV::readActualSize() {
    uint32_t actualSize = 0;
    // 内存拷贝起始4字节的数据到actualSize
    memcpy(&actualSize, m_file->getMemory(), Fixed32Size);
    return actualSize;
}
复制代码

PS：Fixed32Size值是4

checkDataValid函数中读取到数据内容大小，若有内容，则读取缓存到m_dic中。首先创建一个MMBuffer表示读取缓冲区，读取内存ptr + Fixed32Size位置，m_actualSize大小。接着执行decodeMap函数加载所有key-value：

[MiniPBCoder.cpp]

MiniPBCoder::MiniPBCoder(const MMBuffer *inputBuffer) {
  m_inputBuffer = inputBuffer;
  // 创建读取辅助类，用于读取MMBuffer中指定的内存位置和大小的数据
  m_inputData = new CodedInputData(m_inputBuffer->getPtr(), m_inputBuffer->length());
}

void MiniPBCoder::decodeMap(EZKVMAP &dic, const MMBuffer &oData, size_t position) {
  MiniPBCoder oCoder(&oData);
  // position用于指示从内存位置偏移position后开始读取，默认为0
  oCoder.decodeOneMap(dic, position);
}
复制代码

MiniPBCoder内通过CodedInputData来进行数据读取操作。

接着实现decodeOneMap函数：

[MiniPBCoder.cpp]

void MiniPBCoder::decodeOneMap(EZKVMAP &dic, size_t position) {
  auto block = [position, this](EZKVMAP &dictionary) {
    if (position) {
      m_inputData->seek(position);
    } else {
      // 跳过ItemSizeHolder
      m_inputData->readInt32();
    }
    // 开始不断读取key-value
    while (!m_inputData->isAtEnd()) {
      KeyValueHolder kvHolder;
      // 读key值
      const auto &key = m_inputData->readString(kvHolder);
      if (key.length() > 0) {
        // KeyValueHolder中并未直接保存value值，而是保存内存地址和size，
        // 因为不同类型的value有不同的解析方式，需要在具体取值时根据调用的方法分别处理。
        m_inputData->readData(kvHolder);
        if (kvHolder.valueSize > 0) {
          // value有值，保存到map中
          dictionary[key] = move(kvHolder);
        } else {
          // 移除key
          auto itr = dictionary.find(key);
          if (itr != dictionary.end()) {
            dictionary.erase(itr);
          }
        }
      }
    }
  };

  try {
    EZKVMAP tmpDic;
    // 执行lambda表达式block
    block(tmpDic);
    dic.swap(tmpDic);
  } catch (std::exception &exception) {
    LOGE("%s", exception.what());
  }
}
复制代码

通过CodedInputData从映射内存读取key-value，如果有重复key，则后读取的key-value会覆盖前面读取的key-value，因此m_dic中缓存的都是最新的key-value。

这里并没有把key-value真正的值存到m_dic中，而是存的KeyValueHolder。通过KeyValueHolder记录了值的基于映射内存地址的偏移位置和大小，待真正获取数据的时候再根据偏移位置和大小进行内存拷贝。

数据写入

在MMKV中按照protobuf变长编码方式组织数据，写入和读取key-value时，不同的value类型规则略有不同。
这里以int和string为例：

写入int类型value

Java层方法：

[EZKV.java]

public boolean encode(String key, int value) {
  return nEncodeInt(nativeHandle, key, value);
}

private native boolean nEncodeInt(long handle, String key, int value);
复制代码

实现对应Native函数：

[native-bridge.cpp]

EZKV_JNI jboolean nEncodeInt(JNIEnv *env, jobject obj, jlong handle, jstring oKey, jint value) {
  EZKV *kv = reinterpret_cast<EZKV *>(handle);
  if (kv && oKey) {
    string key = jstring2string(env, oKey);
    return (jboolean) kv->set((int32_t) value, key);
  }
  return (jboolean) false;
}
复制代码

[EZKV.cpp]

bool EZKV::set(int32_t value, EZKVKey_t key) {
    if (isKeyEmpty(key)) {
        return false;
    }
    // 计算按照变长编码方式存储value需要的大小
    size_t size = pbInt32Size(value);
    MMBuffer data(size);
    CodedOutputData output(data.getPtr(), size);
    // 写入value到MMBuffer中分配的空间（按变长编码方式）
    output.writeInt32(value);

    return setDataForKey(move(data), key);
}
复制代码

首先将value按照变长编码方式写入到缓冲区MMBuffer中分配的地址，然后执行setDataForKey函数。String类型的value写入最终也会执行setDataForKey函数，区别在于int类型时第三个参数isDataHolder为false，String类型时传true。

[EZKV_IO.cpp]

bool EZKV::setDataForKey(MMBuffer &&data, EZKVKey_t key, bool isDataHolder) {
    if ((!isDataHolder && data.length() == 0) || isKeyEmpty(key)) {
        return false;
    }

    auto itr = m_dic->find(key);
    if (itr != m_dic->end()) {
        // 有缓存
        auto ret = appendDataWithKey(data, itr->second, isDataHolder);
        if (!ret.first) {
            return false;
        }
        itr->second = std::move(ret.second);
    } else {
        // 无缓存
        auto ret = appendDataWithKey(data, key, isDataHolder);
        if (!ret.first) {
            return false;
        }
        m_dic->emplace(key, std::move(ret.second));
    }

    return true;
}
复制代码

添加key-value时，key也需要创建对应的MMBuffer。

• 当无缓存时，直接创建MMBuffer记录字符串的内存地址和大小：

[EZKV_IO.cpp]

EZKV::KVHolderRet_t
EZKV::appendDataWithKey(const MMBuffer &data, EZKVKey_t key, bool isDataHolder) {
    auto keyData = MMBuffer((void *) key.data(), key.size(), MMBufferNoCopy);
    return doAppendDataWithKey(data, keyData, isDataHolder, static_cast<uint32_t>(keyData.length()));
}
复制代码

KVHolderRet_t是std::pair<bool, ezkv::KeyValueHolder>的类型别名。

• 有缓存时，创建MMBuffer记录KeyValueHolder中记录的地址和大小：

[EZKV_IO.cpp]

EZKV::KVHolderRet_t
EZKV::appendDataWithKey(const MMBuffer &data, const KeyValueHolder &kvHolder, bool isDataHolder) {
    uint32_t keyLength = kvHolder.keySize;
    // size needed to encode the key
    // key黄色区块共占用的字节数
    size_t rawKeySize = keyLength + pbRawVarint32Size(keyLength);

    // ensureMemorySize() might change kvHolder.offset, so have to do it early
    // 每次新增数据前都要检查文件剩余空间是否足够，不足则需要重整扩容，该操作可能会修改kvHolder.offset，因此需要先进行该操作。
    {
        // 计算value绿色区块共占用字节数
        auto valueLength = static_cast<uint32_t>(data.length());
        if (isDataHolder) {
            // string或bytes较其他类型多了一个value length值的占用
            valueLength += pbRawVarint32Size(valueLength);
        }
        // 新增的KV对占的大小
        auto size = rawKeySize + valueLength + pbRawVarint32Size(valueLength);
        // 执行检查大小和重整扩容操作
        bool hasEnoughtSize = ensureMemorySize(size);
        if (!hasEnoughtSize) {
            return make_pair(false, KeyValueHolder());
        }
    }
    auto basePtr = (uint8_t *) m_file->getMemory() + Fixed32Size;
    MMBuffer keyData(basePtr + kvHolder.offset, rawKeySize, MMBufferNoCopy);

    return doAppendDataWithKey(data, keyData, isDataHolder, keyLength);
}
复制代码

最终都执行doAppendDataWithKey函数：

[EZKV_IO.cpp]

EZKV::KVHolderRet_t
EZKV::doAppendDataWithKey(const MMBuffer &data, const MMBuffer &keyData, bool isDataHolder, uint32_t originKeyLength) {
    // isDataHolder：avoid memory copying when encoding string & buffer。
    auto isKeyEncoded = (originKeyLength < keyData.length());
    auto keyLength = static_cast<uint32_t>(keyData.length());
    auto valueLength = static_cast<uint32_t>(data.length());
    if (isDataHolder) {
        // 如果是string或bytes需要额外存储一个size
        valueLength += pbRawVarint32Size(valueLength);
    }
    // 计算该kv的大小（黄色+蓝色+绿色区块的总大小）
    // size needed to encode the key
    size_t size = isKeyEncoded? keyLength : (keyLength + pbRawVarint32Size(keyLength));
    size += valueLength + pbRawVarint32Size(valueLength);

    // 检查剩余空间，不足则重整扩容
    bool hasEnoughtSize = ensureMemorySize(size);
    if (!hasEnoughtSize || !isFileValid()) {
        return make_pair(false, KeyValueHolder());
    }

    try {
        if (isKeyEncoded) {
            m_output->writeRawData(keyData);
        } else {
            // 依次写入key length值和key值
            m_output->writeData(keyData);
        }
        if (isDataHolder) {
            // 如果是string或bytes需要额外存储一个size
            m_output->writeRawVarint32((int32_t) valueLength);
        }
        // 依次写入value length值和value值
        m_output->writeData(data);
    } catch (std::exception &e) {
        LOGE("%s", e.what());
        return make_pair(false, KeyValueHolder());
    }

    // 当前数据内容大小作为新KV的offset
    auto offset = static_cast<uint32_t>(m_actualSize);

    // 更新数据内容大小
    m_actualSize += size;

    // 将新的内容大小写回文件头4字节
    writeActualSize(m_actualSize);

    // 构造KeyValueHolder记录该新增KV的偏移位置和大小，返回结果
    return make_pair(true, KeyValueHolder(originKeyLength, valueLength, offset));
}
复制代码

writeData函数实现：

[CodedOutputData.cpp]

void CodedOutputData::writeData(const MMBuffer &value) {
  // 写入值长度（变长编码）
  this->writeRawVarint32((int32_t) value.length());
  // 写入值
  this->writeRawData(value);
}
复制代码

writeActualSize函数实现：

[EZKV_IO.cpp]

bool EZKV::writeActualSize(size_t size) {
    oldStyleWriteActualSize(size);
    return true;
}

void EZKV::oldStyleWriteActualSize(size_t actualSize) {
    m_actualSize = actualSize;
    // 通过内存拷贝将新的大小写入文件头4字节
    memcpy(m_file->getMemory(), &actualSize, Fixed32Size);
}
复制代码

KeyValueHolder的构造函数实现：

[KeyValueHolder.cpp]

KeyValueHolder::KeyValueHolder(uint32_t keyLength, uint32_t valueLength, uint32_t off)
  : keySize(static_cast<uint16_t>(keyLength)), valueSize(valueLength), offset(off) {
    // keySize即key字符串长度，valueSize即蓝色区块存的值
    // 计算computedKVSize，即黄色区块+绿色区块占用的字节数
    computedKVSize = keySize + static_cast<uint16_t>(pbRawVarint32Size(keySize));
    computedKVSize += static_cast<uint16_t>(pbRawVarint32Size(valueSize));
  }
复制代码

读取数据时，通过KeyValueHolder的offset和computedKVSize即可快速定位到value的位置。

举个例子，写入”kInt”:1000的键值对
结果如下图所示：

第9个字节0x04换算成十进制是4，表示key=”kInt”占用4字节。
第14个字节0x02换算成十进制是2，表示value=1000按变长编码方式写入占2字节。

1000的二进制是1111101000，按照变长编码方式写入，
首先取低7位|0x80得到11101000
无符号右移7位，取低7位|0x80得到00000111
最终得到1110100000000111，换算成十六进制，即0xE807

写入String类型value

存储string和int数据的流程基本相同，只是在写入格式上有些区别，代码中具体体现在isDataHolder参数的判断处理。

实现对应的native函数：

[native-bridge.cpp]

EZKV_JNI jboolean nEncodeString(JNIEnv *env, jobject obj, jlong handle, jstring oKey, jstring oValue) {
  EZKV *kv = reinterpret_cast<EZKV *>(handle);
  if (kv && oKey) {
    string key = jstring2string(env, oKey);
    // 保存的vulue非空则写入，否则移除该key
    if (oValue) {
      string value = jstring2string(env, oValue);
      return (jboolean) kv->set(value, key);
    } else {
      kv->removeValueForKey(key);
      return (jboolean) true;
    }
  }
  return (jboolean) false;
}
复制代码

[EZKV.cpp]

bool EZKV::set(const string &value, EZKVKey_t key) {
    if (isKeyEmpty(key)) {
        return false;
    }
    // 创建MMBuffer保存value字符串数据
    return setDataForKey(MMBuffer((void *) value.data(), value.length(), MMBufferNoCopy), key, true);
}
复制代码

同写入int数据时一样，创建MMBuffer保存value数据后调用setDataForKey函数，其中再区分是否存在缓存调用不同的appendDataWithKey函数。
注意这里传入的isDataHolder参数为true。

当有缓存时：

[EZKV_IO.cpp]

EZKV::KVHolderRet_t
EZKV::appendDataWithKey(const MMBuffer &data, const KeyValueHolder &kvHolder, bool isDataHolder) {
    // ···
    {
        // 获取value字符串长度
        auto valueLength = static_cast<uint32_t>(data.length());
        if (isDataHolder) {
            // pbRawVarint32Size(valueLength)返回长度值本身按变长编码写入需要占用的大小
            // valueLength再加上该值，表示上图中绿色区块共占用的大小
            valueLength += pbRawVarint32Size(valueLength);
        }
        // ···
    }
    // ···

    return doAppendDataWithKey(data, keyData, isDataHolder, keyLength);
}
复制代码

最终一样执行doAppendDataWithKey函数：

[EZKV_IO.cpp]

EZKV::KVHolderRet_t
EZKV::doAppendDataWithKey(const MMBuffer &data, const MMBuffer &keyData, bool isDataHolder, uint32_t originKeyLength) {
    // ···
    auto valueLength = static_cast<uint32_t>(data.length());
    if (isDataHolder) {
        // 计算得到绿色区块大小
        valueLength += pbRawVarint32Size(valueLength);
    }
    // ···

    try {
        // ···
        if (isDataHolder) {
            // 绿色区块大小值按变长编码方式写入，即蓝色区块中存的值
            m_output->writeRawVarint32((int32_t) valueLength);
        }
        // ···
    } catch (std::exception &e) {
        LOGE("%s", e.what());
        return make_pair(false, KeyValueHolder());
    }

    // ···

    return make_pair(true, KeyValueHolder(originKeyLength, valueLength, offset));
}
复制代码

string类型数据写入时比int类型数据多写入一个value length，即字符串长度。当读取时key-value时，通过内存起始地址和字符串长度构建字符串。

举个例子，写入”kString”:”hello EZKV”的键值对
结果如下图所示：

第18个字节0x0A换算成十进制是10，即”hello EZKV”的长度10个字节。
第17个字节0x0B换算成十进制是11，即”hello EZKV”的长度加上长度值10占用的长度，共11字节。

数据重整和文件扩容

存储key-value的文件的初始大小为4KB，由于MMKV的写入策略是不停在文件中内容尾部添加数据，随着写入次数增加，不可避免的出现文件空间不足。因此在每次写入前需要检查大小，不足则进行重整扩容操作。

例如依次执行了：
1.save key1:hi
2.save key1:hello
3.save key2:aaa
4.save key3:bbb
5.remove key2
6.save key4:ccc
操作后，文件中的key-value和map缓存容器中的key-value如下图所示：

• 数据重整

即将map中的key-value写回到文件中，以此移除文件中过时冗余的key-value。

• 文件扩容

即当新增key-value时，文件空间不足，需要扩大文件后再将数据写回文件。

接下来实现ensureMemorySize函数：

[EZKV_IO.cpp]

bool EZKV::ensureMemorySize(size_t newSize) {
    // newSize即当前新增的key-value所需的大小
    // spaceLeft函数中通过内存大小和当前写入位置计算剩余空间大小
    if (newSize >= m_output->spaceLeft() || m_dic->empty()) {
        // 若新增KV所需大小大等剩余可写空间 或 map容器为空，则进行重整回写
        // try a full rewrite to make space
        auto fileSize = m_file->getFileSize();
        // 计算当前map中所有KV对所需空间（包含ItemSizeHolder的额外4字节）
        auto prepareData = prepareEncode(*m_dic);
        auto sizeOfDic = prepareData.second;
        // 再加上存actual size占用的4字节和新增KV对的大小得到总共需要的大小
        size_t lenNeeded = sizeOfDic + Fixed32Size + newSize;
        size_t dicCount = m_dic->size();
        size_t avgItemSize = lenNeeded / std::max<size_t>(1, dicCount);
        // 预估将来还会新增的大小=Max(8个KV对, 当前KV数的一半)
        size_t futureUsage = avgItemSize * std::max<size_t>(8, (dicCount + 1) / 2);
        // 1. no space for a full rewrite, double it
        // 2. or space is not large enough for future usage, double it to avoid frequently full rewrite
        // 如果所需空间超过文件大小 或者 虽然现在还没超过但预估后续操作将超过，则扩容
        if (lenNeeded >= fileSize || (lenNeeded + futureUsage) >= fileSize) {
            size_t oldSize = fileSize;
            // 文件扩容，大小不断两倍，直到满足想要的空间大小
            do {
                fileSize *= 2;
            } while (lenNeeded + futureUsage >= fileSize);
            LOGI("extending [%s] file size from %zu to %zu, incoming size:%zu, future usage:%zu",
                    m_mmapID.c_str(), oldSize, fileSize, newSize, futureUsage);

            // 文件扩容和重映射（ftruncate->zeroFillFile->munmap->mmap）
            // if we can't extend size, rollback to old state
            if (!m_file->truncate(fileSize)) {
                return false;
            }

            // check if we fail to make more space
            if (!isFileValid()) {
                LOGE("[%s] file not valid", m_mmapID.c_str());
                return false;
            }
        }
        // 回写数据
        return doFullWriteBack(move(prepareData));
    }

    return true;
}
复制代码

当空间不足时，计算重整数据后所需空间和预估将来使用空间（若数据重整空间仍不足，则ftruncate扩容文件和重新mmap映射内存），最后将map中的数据写回到文件。

prepareEncode函数计算当前已有数据大小总和：

[EZKV_IO.cpp]

static pair<MMBuffer, size_t> prepareEncode(const EZKVMAP &dic) {
    // make some room for placeholder
    // ItemSizeHolderSize占位，启用数据加密时用到
    size_t totalSize = ItemSizeHolderSize;
    // 累加KV集合中所有KV对占用大小
    for (auto &itr : dic) {
        auto &kvHolder = itr.second;
        // 通过computedKVSize和valueSize相加得到该KV对的大小
        totalSize += kvHolder.computedKVSize + kvHolder.valueSize;
    }
    return make_pair(MMBuffer(), totalSize);
}
复制代码

完成了文件扩容后，进行数据回写，实现doFullWriteBack函数：

[EZKV_IO.cpp]

bool EZKV::doFullWriteBack(std::pair<ezkv::MMBuffer, size_t> prepareData) {
    auto ptr = (uint8_t *) m_file->getMemory();
    auto totalSize = prepareData.second;

    // 重新mmap后，重建CodedOutputData，重置内存地址和大小和偏移量
    delete m_output;
    m_output = new CodedOutputData(ptr + Fixed32Size, m_file->getFileSize() - Fixed32Size);

    // 通过CodedOutputData将m_dic中的key-value写入文件
    memmoveDictionary(*m_dic, m_output, ptr, totalSize);

    // 保存新的数据内容大小
    m_actualSize = totalSize;

    // 将新的数据内容大小写入文件头4字节
    writeActualSize(m_actualSize);

    // make sure lastConfirmedMetaInfo is saved
    // 立即将内存数据写回磁盘（之前的写入操作只是拷贝到映射内存区域中），EZKV_SYNC表示等待操作完成函数才返回
    sync(EZKV_SYNC);
    return true;
}
复制代码

[EZKV_IO.cpp]

static void memmoveDictionary(EZKVMAP &dic, CodedOutputData *output, uint8_t *ptr, size_t totalSize) {
    auto originOutputPtr = output->curWritePointer();
    // make space to hold the fake size of dictionary's serialization result
    // 起始写入位置，从ItemSizeHolder之后写入
    auto writePtr = originOutputPtr + ItemSizeHolderSize;
    // reuse what's already in the file
    if (!dic.empty()) {
        // 若大部分kv对在文件中的位置相邻，排布紧凑，以下操作通过将相邻kv对合并成区块再拷贝，可以大幅减少内存复制次数。
        // sort by offset
        vector<KeyValueHolder *> vec;
        vec.reserve(dic.size());
        for (auto &itr : dic) {
            vec.push_back(&itr.second);
        }
        sort(vec.begin(), vec.end(), [](const auto &left, const auto &right) { return left->offset < right->offset; });

        // merge nearby items to make memmove quicker
        vector<pair<uint32_t, uint32_t>> dataSections; // pair(offset, size)
        dataSections.emplace_back(vec.front()->offset, vec.front()->computedKVSize + vec.front()->valueSize);
        for (size_t index = 1, total = vec.size(); index < total; index++) {
            auto kvHolder = vec[index];
            auto &lastSection = dataSections.back();
            // 判断该kv对和上一个kv对是否相邻
            if (kvHolder->offset == lastSection.first + lastSection.second) {
                // 相邻，扩大区块大小
                lastSection.second += kvHolder->offset + kvHolder->valueSize;
            } else {
                // 不相邻，添加新的区块
                dataSections.emplace_back(kvHolder->offset, kvHolder->computedKVSize + kvHolder->valueSize);
            }
        }
        // do the move
        auto basePtr = ptr + Fixed32Size;
        for (auto &section : dataSections) {
            // memmove() should handle this well: src == dst
            memmove(writePtr, basePtr + section.first, section.second);
            writePtr += section.second;
        }

        // update offset
        auto offset = ItemSizeHolderSize;
        for (auto kvHolder : vec) {
            kvHolder->offset = offset;
            offset += kvHolder->computedKVSize + kvHolder->valueSize;
        }
    }
    // hold the fake size of dictionary's serialization result
    // 写入0x00ffffff
    output->writeRawVarint32(ItemSizeHolder);
    auto writtenSize = static_cast<size_t>(writePtr - originOutputPtr);
    // 定位至内容结尾，后续从尾部添加数据
    output->seek(writtenSize - ItemSizeHolderSize);
}
复制代码

数据读取

读取int类型value

提供接入方调用的Java层方法：

[EZKV.java]

public int decodeInt(String key, int defaultValue) {
  return nDecodeInt(nativeHandle, key, defaultValue);
}

private native int nDecodeInt(long handle, String key, int defaultValue);
复制代码

实现对应的native函数：

[native-bridge.cpp]

EZKV_JNI jint nDecodeInt(JNIEnv *env, jobject obj, jlong handle, jstring oKey, jint defaultValue) {
  EZKV *kv = reinterpret_cast<EZKV *>(handle);
  if (kv && oKey) {
    string key = jstring2string(env, oKey);
    return (jint) kv->getInt32(key, defaultValue);
  }
  return defaultValue;
}
复制代码

getInt32函数：

[EZKV.cpp]

int32_t EZKV::getInt32(EZKVKey_t key, int32_t defaultValue) {
    if (isKeyEmpty(key)) {
        return defaultValue;
    }

    // 从m_dic中查找KeyValueHolder，创建MMBuffer保存value数据并返回
    auto data = getDataForKey(key);
    if (data.length() > 0) {
        try {
            // 根据MMBuffer保存的内存地址和大小读取value值（按变长编码方式）
            CodedInputData input(data.getPtr(), data.length());
            return input.readInt32();
        } catch (std::exception &e) {
            LOGE("%s", e.what());
        }
    }
    return defaultValue;
}
复制代码

首先通过getDataForKey函数从缓存容器中查找对应的key-value：

[EZKV_IO.cpp]

MMBuffer EZKV::getDataForKey(EZKVKey_t key) {
    auto itr = m_dic->find(key);
    if (itr != m_dic->end()) {
        // 计算数据内容在文件映射内存的基准位置
        auto basePtr = (uint8_t *) (m_file->getMemory()) + Fixed32Size;
        return itr->second.toMMBuffer(basePtr);
    }
    // 不存在则创建空的MMBuffer返回
    MMBuffer nan;
    return nan;
}
复制代码

toMMBuffer函数根据基准位置和KeyValueHolder自身保存的偏移位置和大小创建MMBuffer：

[KeyValueHolder.cpp]

MMBuffer KeyValueHolder::toMMBuffer(const void *basePtr) const {
  // 得到该KV对的起始位置
  auto realPtr = (uint8_t *) basePtr + offset;
  // 得到该KV对的value的起始位置
  realPtr += computedKVSize;
  // 创建MMBuffer记录value的内存地址和大小
  return MMBuffer(realPtr, valueSize, MMBufferNoCopy);
}
复制代码

得到value数据的内存地址和大小后，通过CodedInputData的readInt32函数读取int类型数据：

[CodedInputData.cpp]

int32_t CodedInputData::readInt32() {
  // 按照变长编码方式读取
  return this->readRawVarint32();
}
复制代码

读取string类型value

对应的native函数：

[native-bridge.cpp]

EZKV_JNI jstring nDecodeString(JNIEnv *env, jobject obj, jlong handle, jstring oKey, jstring defaultValue) {
  EZKV *kv = reinterpret_cast<EZKV *>(handle);
  if (kv && oKey) {
    string key = jstring2string(env, oKey);
    string value;
    // 查找value。存在返回true，否则返回false
    bool hasValue = kv->getString(key, value);
    if (hasValue) {
      return string2jstring(env, value);
    }
  }
  return defaultValue;
}
复制代码

实现getString函数：

[EZKV.cpp]

bool EZKV::getString(EZKVKey_t key, string &result) {
    if (isKeyEmpty(key)) {
        return false;
    }

    // 从map容器中查找value信息
    auto data = getDataForKey(key);
    if (data.length() > 0) {
        try {
            CodedInputData input(data.getPtr(), data.length());
            // 读取value字符串
            result = input.readString();
            return true;
        } catch (std::exception &e) {
            LOGE("%s", e.what());
        }
    }
    return false;
}
复制代码

这里同样调用getDataForKey查找value信息，若存在则创建MMBuffer保存value的内存地址和大小，然后创建CodedInputData读取MMBuffer数据。

readString函数读取指定区域的字符串：

[CodedInputData.cpp]

std::string CodedInputData::readString() {
  // 先读取字符串的长度，即上文string类型结构图中绿色区块中value length的值
  int32_t size = readRawVarint32();
  if (size < 0) {
    throw length_error("InvalidProtocolBuffer negativeSize");
  }

  auto s_size = static_cast<size_t>(size);
  // s_size即string.length
  if (s_size <= m_size - m_position) {
    // 通过内存地址和长度构造string（m_position指示当前读取的位置，初始为0）
    string result((char *) (m_ptr + m_position), s_size);
    // 更新读取位置
    m_position += s_size;
    return result;
  } else {
    throw out_of_range("readString(): InvalidProtocolBuffer truncatedMessage");
  }
}
复制代码

总结

这里完成了MMKV中基本的key-value存储和读取功能，忽略了高级扩展功能和健壮性代码，先着眼实现最核心的功能。

下一版将在当前基础上实现数据校验和多线程支持，继续完善功能。

完整代码可以查看github.com/chidehang/E… 的 practice01 分支。