Android平台MMKV的原理及实现

作者: Peakmain | 来源:发表于2021-08-25 15:16 被阅读0次

前言

源码的位置：
https://github.com/Peakmain/Video_Audio/tree/master/app/src/main/cpp/src
我的简书:https://www.jianshu.com/u/3ff32f5aea98
我的Github:https://github.com/peakmain

Protobuf协议

什么是Protobuf

protobuf 是google开源的一个序列化框架，类似xml，json。但是它存储的方式是二进制
MMKV就是基于protobuf协议进行数据存储

数据结构

image.png

上面的图片我们可以知道，ProtoBuf存储结构是总长度->key的长度->key的内容->value的长度->value的内容...
总长度我们可以用int来存储，也就是4个字节进行存储
key的长度实际就是字符串的长度(我们定义key只能是字符串)

PortoBuf写入方式

一个字节有8位，我们将后7位用来保存数据，第一位用来判断是否还有字节，如果没有则为0，如果有则为1。
如何判断当前是否还有字节？
因为我们只保存后7位字节，而7位字节全是1的是7F，所以当我们的数大于7F则表示我们还有字节

image.png
当我们的数据大于7F,如何存储？
我们以5201314数据进行分析,首先将5201314转成字节码0100 1111 0101 1101 1010 0010
1、当前数据大于7F,我们先取最低的七位，也就是010 0010，第一位补1，则数据是1010 0010写入文件
2、5201314右移动7F，左边不足补0，原数据则变成000 0000 1001 1110 1011 1011(大于7F)
3、取出最低七位,1011 1011写入文件。
4、5201314右移动7F，左边不足补0，原数据则变成000 0000 0000 0001 0011 1101
5、取出最低七位,1011 1101写入文件。原数据则变成000 0000 0000 0000 0000 0010
6、这时候数据小于07F，则直接将直接将0000 0010写入文件，结束

上述步骤结束之后拿到数据

1、1010 0010
2、1011 1011
3、1011 1101
4、0000 0010

既然已经将数据存储了，那如何取出数据？
1、我们将0000 0010拼接到1011 1101之前，因为1011 1101中之后后七位是有效数据，所以第一位需要去掉首位，此时的原数据就是0000 0010 011 1101
2、依次推论，将上面拼好的数据放到1011 1011之前，得到数据0000 0010 011 1101 011 1011
3、再将上面拼好的数据放到1010 0010之前，得到数据0 0000 0100 1111 0101 1101 1010 0010
4、去除无效位数0，也就还原了原来的数据0100 1111 0101 1101 1010 0010

代码实现
上面写入方式了解之后，看起来还是挺简单，但是代码怎么写呢？

1、我们现在写入一个int的数据，怎么获取它的大小?
7F的字节码是0111 1111，也就是说第一位是1就代表需要两个字节来存。因此我们可以让我们当前的value&(0xFFFFFFFF<<7)，判断是否等于0，如果等于0则表示需要一个字节就可以

    1111 1111 1111 1111 1111 1111 1000 0000            (0xffffffff<<7)
&   0000 0000 0000 0000 0000 0000 0110 1110            (110)
=   0000 0000 0000 0000 0000 0000 0000 0000            0

假设我们的value现在是150，因为值已经大于0x7F(也就是上述不成立)，这时候我们需要将value&(0xFFFFFFFF<<14),如果等于0则表示需要2个字节

    1111 1111 1111 1111 1100 0000 0000 0000            (0xffffffff<<14)
&   0000 0000 0000 0000 0000 0000 1001 0110            (150)
=   0000 0000 0000 0000 0000 0000 1000 0000            0

以此推论，最终我们可以写出如下代码

int32_t ProtoBuf::computeInt32Size(int32_t value) {
    //0xffffffff 表示 uint 最大值
    //<< 7 则低7位变成0 与上value
    //如果value只要7位就够了则=0,编码只需要一个字节，否则进入其他判断
    if ((value & (0xffffffff << 7)) == 0) {
        return 1;
    } else if ((value & (0xffffffff << 14)) == 0) {
        return 2;
    } else if ((value & (0xffffffff << 21)) == 0) {
        return 3;
    } else if ((value & (0xffffffff << 28)) == 0) {
        return 4;
    }
    return 5;
}

2、我们现在存一个key和value的数据，应该怎么计算它的大小(也就是下图的红框区域的大小)

image.png

首先key的长度其实也就是

int32_t keyLength = key.length();

然后保存key的长度+key内容的长度:

 int32_t size = keyLength + ProtoBuf::computeInt32Size(keyLength);

value的长度+value内容的长度

 size += value->length() + ProtoBuf::computeInt32Size(value->length());

所以获取key+value大小的完整代码

int32_t ProtoBuf::computeItemSize(std::string key, ProtoBuf *value) {
    int32_t keyLength = key.length();
    // 保存key的长度与key数据需要的字节
    int32_t size = keyLength + ProtoBuf::computeInt32Size(keyLength);
    // 加上保存value的长度与value数据需要的字节
    size += value->length() + ProtoBuf::computeInt32Size(value->length());
    return size;
}

3、如何写入数据
我们上面分析了写入方式，那么我们现在直接假设写入的key数据的长度是字符串110，因为110小于0x7F所以直接写入，则直接写入即可

 if (value <= 0x7f) {
            writeByte(value);
            return;
 }
void ProtoBuf::writeByte(int8_t value) {
    if (m_position == m_size) {
        //满啦，出错啦
        return;
    }
    //将byte放入数组
    m_buf[m_position++] = value;
}

如果key数据的长度是字符串150，因为此时大于0x7f，将150转成字符串 1001 1000 ，首先记录低七位，

(value & 0x7F)

将第一位的数据变成1,再移除低7位

            writeByte((value & 0x7F) | 0x80);
            //7位已经写完了，处理更高位的数据
            value >>= 7;

原理如下

         0111 1111            (0x7F)
&        1001 1000             (150)
=        0001 1000           
|        1000 0000             (0X80)
=        1001 1000

此时key的长度已经全部写完，那key的内容怎么写呢，其实也很简单，直接将key的内容拷贝到数组就可以了

  memcpy(m_buf + m_position, data->getBuf(), numberOfBytes);

因此写入string数据的完整代码可以写成如下

void ProtoBuf::writeByte(int8_t value) {
    if (m_position == m_size) {
        //满啦，出错啦
        return;
    }
    //将byte放入数组
    m_buf[m_position++] = value;
}

void ProtoBuf::writeRawInt(int32_t value) {
    while (true) {
        //每次处理7位数据，如果写入的数据 <= 0x7f（7位都是1）那么使用7位就可以表示了
        if (value <= 0x7f) {
            writeByte(value);
            return;
        } else {
            //大于7位，则先记录低7位，并且将最高位置为1
            //1、& 0x7F 获得低7位数据
            //2、| 0x80 让最高位变成1，表示超过1个字节记录整个数据
            writeByte((value & 0x7F) | 0x80);
            //7位已经写完了，处理更高位的数据
            value >>= 7;
        }
    }
}
void ProtoBuf::writeString(std::string value) {
    size_t numberOfBytes = value.size();
    writeRawInt(numberOfBytes);
    memcpy(m_buf + m_position, value.data(), numberOfBytes);
    m_position += numberOfBytes;
}

4、如何读取数据？
如果当前的最高位，也就是第一位是0，则表示是一个字节，直接返回就可以

    if ((tmp >> 7) == 0) {
        return tmp;
    }

如果最高位1代表还有数据，我们首先读取低7位的数据

 int32_t result = tmp & 0x7f;

再读取一个字节，将后面的读取到字节左移7位拼接到上一个数据的低7位

int32_t ProtoBuf::readInt() {
    uint8_t tmp = readByte();
    //最高1位为0  这个字节是一个有效int。
    if ((tmp >> 7) == 0) {
        return tmp;
    }
    //获得低7位数据
    int32_t result = tmp & 0x7f;
    int32_t i = 1;
    do {
        //再读一个字节
        tmp = readByte();
        if (tmp < 0x80) {
            //读取后一个字节左移7位再拼上前一个数据的低7位
            result |= tmp << (7 * i);
        } else {
            result |= (tmp & 0x7f) << (7 * i);
        }
        i++;
    } while (tmp >= 0x80);
    return result;
}
int8_t ProtoBuf::readByte() {
    if (m_position == m_size) {
        return 0;
    }
    return m_buf[m_position++];
}

至此ProtoBuf的读取和写入都已经基本差不多了，我们来看mmap

内存映射MMAP

SharedPreferences的弊端

SharedPreferences采用的是IO写入数据

image.png
通信的本质借助内核
- 左边的进程把数据从用户空间copy到内核空间
- 右边的进程把数据从内核空间copy到用户空间

页、页框、页表

基本概念
- CPU执行一个进程的时候，都会访问内存
- 但是并不是直接访问物理内存地址，而是通过虚拟地址访问物理内存地址
页：将进程分配的虚拟地址空间划分成的块，对应的大小叫做页面的大小
页框：将物理地址划分的块
页表：记录每一对页和页框的映射关系
页面大小是4k，或者4k的整数倍

image.png

mmap

原理：通过mmap映射文件的一块到用户空间，那么现在通过操作mmap返回的指针，就可以操作mmap映射的用户空间，同时相当于操作文件

image.png
函数

 void * mmap(void *addr, size_t len, int prot, int flags, int fd, off_t of    fset);

参数
- add:地址，当为NULL的时候，由系统分配
- len:内存的大小
- prot:
  - PROT_EXEC内容可以被执行；
  - PROT_READ:内容可以被读取；
  - PROT_WRITE:内容可以被写入;
  - PROT_NONE:内容不可访问
- flags:MAP_SHARED:共享；MAP_PRIVATE:私用；MAP_ANONYMOUS:匿名映射(不基于文件)，fd传入-1
- fd：打开文件的句柄
- fset：偏移大小,必须是4k的整数倍，一个物理页映射是4k

核心代码的实现

具体代码大家可以看我的github:https://github.com/Peakmain/Video_Audio/tree/master/app/src/main/cpp/src/mmkv/MMKV.cpp

初始化，代码很简单，主要创建一个文件夹和创建文件名字为peakmain_mmkv

image.png

int32_t DEFAULT_MMAP_SIZE =getpagesize();
void MMKV::initializeMMKV(const char *path) {
    g_rootDir = path;
    //创建文件夹
    mkdir(g_rootDir.c_str(), 0777);
}

MMKV::MMKV(const char *mmapID) {
    m_path = g_rootDir + "/" + mmapID;
    loadFromFile();
}

MMKV *MMKV::defaultMMKV() {
    MMKV *kv = new MMKV(DEFAULT_MMAP_ID);
    return kv;
}

打开文件，并获取文件的大小

    m_fd = open(m_path.c_str(), O_RDWR | O_CREAT, S_IRWXU);
    //获取文件的具体大小
    struct stat st = {0};
    if (fstat(m_fd, &st) != -1) {
        m_size = st.st_size;
    }

我们需要保证文件的大小是页的整数倍，也就是4k的整数倍,因为文件大小被增加了，那么增加的内容需要被设置为0

    if (m_size < DEFAULT_MMAP_SIZE || (m_size % DEFAULT_MMAP_SIZE != 0)) {
        //调整为4k整数倍
        int32_t oldSize = m_size;
        //新的4k整数倍
        m_size = ((m_size / DEFAULT_MMAP_SIZE) + 1) * DEFAULT_MMAP_SIZE;
        if (ftruncate(m_fd, m_size) != 0) {
            m_size = st.st_size;
        }
        //如果文件大小被增加了， 让增加这些大小的内容变成空
        zeroFillFile(m_fd, oldSize, m_size - oldSize);
    }

mmap去映射文件

    m_ptr = static_cast<int8_t *>(mmap(nullptr, m_size, PROT_READ | PROT_WRITE, MAP_SHARED, m_fd, 0));

获取到文件句柄之后，我们获取文件原来的大小(上面我们分析了，文件的前四个字节为内容的总长度)

  memcpy(&m_actualSize, m_ptr, 4);

如果m_actualSize>0，代表原来的文件是有值得，那么就需要将原有的数据保存hashmap

    if (m_actualSize > 0) {
        ProtoBuf inputBuffer(m_ptr + 4, m_actualSize);
        //清空
        map.clear();
        //已有的数据添加到Map
        while (!inputBuffer.isAtEnd()) {
            std::string key = inputBuffer.readString();
            LOGE("key=%s ", key.c_str());
            if (key.length() > 0) {
                ProtoBuf *value = inputBuffer.readData();
                if (value && value->length() > 0) {
                     //相当于java的Hashmap的add
                    map.emplace(key, value);
                }
            }
        }
    }
    m_output = new ProtoBuf(m_ptr + 4 + m_actualSize,
                            m_size - 4 - m_actualSize);

这里有人可能不懂为什么这里是m_ptr + 4 + m_actualSize，这里的目的是将我们的buf指向没有被填写的位置

mmap写入数据
1、计算value需要多少个字节，将写入到ProtoBuf,再用一个key为string，value为ProtoBuf的类似java HashMap的unordered_map去存

void MMKV::putInt(const std::string &key, int32_t value) {
    //value需要几个字节
    int32_t size = ProtoBuf::computeInt32Size(value);
    ProtoBuf *buf = new ProtoBuf(size);
    buf->writeRawInt(value);
    map.emplace(key, buf);
    appendDataWithKey(key, buf);
}

2、计算待写入数据的大小(也就是key+key的长度+value+value的长度)，如果当前待写入数据的大小大于剩余的空间大小，就需要扩大内存。如果内存足够则直接放入数据即可

void MMKV::appendDataWithKey(std::string key, ProtoBuf *value) {
    //待写入数据的大小
    int32_t itemSize = ProtoBuf::computeItemSize(key, value);
    if (itemSize > m_output->spaceLeft()) {
        //内存不够
        //计算map的大小
        int32_t needSize = ProtoBuf::computeMapSize(map);
        //加上总长度
        needSize += 4;
        //扩容的大小
        //计算每个item的平均长度
        int32_t avgItemSize = needSize / std::max<int32_t>(1, map.size());
        int32_t futureUsage = avgItemSize * std::max<int32_t>(8, (map.size() + 1) / 2);
        if (needSize + futureUsage >= m_size) {
            int32_t oldSize = m_size;
            //如果在需要的与将来可能增加的加起来比扩容后还要大，继续扩容
            do {
                //扩充一倍
                m_size *= 2;

            } while (needSize + futureUsage >= m_size);
            //重新设定文件大小
            ftruncate(m_fd, m_size);
            zeroFillFile(m_fd, oldSize, m_size - oldSize);
            //解除映射
            munmap(m_ptr, oldSize);
            //重新映射
            m_ptr = (int8_t *) mmap(m_ptr, m_size, PROT_READ | PROT_WRITE, MAP_SHARED, m_fd, 0);
        }
        m_actualSize = needSize - 4;
        memcpy(m_ptr, &m_actualSize, 4);
        LOGE("extending  full write");
        delete m_output;
        m_output = new ProtoBuf(m_ptr + 4,
                                m_size - 4);
        auto iter = map.begin();
        for (; iter != map.end(); iter++) {
            auto k = iter->first;
            auto v = iter->second;
            m_output->writeString(k);
            m_output->writeData(v);
        }
    } else {
        //内存够
        m_actualSize += itemSize;
        memcpy(m_ptr, &m_actualSize, 4);
        m_output->writeString(key);
        m_output->writeData(value);
    }

mmap取出数据，只需要从map中取出数据就可以

int32_t MMKV::getInt(std::string key, int32_t defaultValue) {
    auto itr = map.find(key);
    if (itr != map.end()) {
        ProtoBuf *buf = itr->second;
        int32_t returnValue = buf->readInt();
        //多次读取，将position还原为0
        buf->restore();
        return returnValue;
    }
    return defaultValue;
}

Android平台MMKV的原理及实现

前言

Protobuf协议

内存映射MMAP

SharedPreferences的弊端

页、页框、页表

mmap

核心代码的实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读