什么是MMKV

MMKV 是基于 mmap 內(nèi)存映射的 key-value 組件，底層序列化/反序列化使用 protobuf 實(shí)現(xiàn)，性能高，穩(wěn)定性強(qiáng)。目前已移植到 Android / macOS / Win32 / POSIX 平臺(tái)并開(kāi)源。

MMKV 原理

內(nèi)存準(zhǔn)備

通過(guò) mmap 內(nèi)存映射文件，提供一段可供隨時(shí)寫(xiě)入的內(nèi)存塊，App 只管往里面寫(xiě)數(shù)據(jù)，由操作系統(tǒng)負(fù)責(zé)將內(nèi)存回寫(xiě)到文件，不必?fù)?dān)心 crash 導(dǎo)致數(shù)據(jù)丟失。這里最重要的是mmap函數(shù)：

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offsize);

• start：指向欲映射的內(nèi)存起始地址，通常設(shè)為 NULL，代表讓系統(tǒng)自動(dòng)選定地址，映射成功后返回該地址。

• 參數(shù)length：代表將文件中多大的部分映射到內(nèi)存。必須是分頁(yè)的整數(shù)倍。

• 參數(shù)prot：映射區(qū)域的保護(hù)方式?？梢詾橐韵聨追N方式的組合：

  • PROT_EXEC 映射區(qū)域可被執(zhí)行

  • PROT_WRITE 映射區(qū)域可被寫(xiě)入

  • PROT_NONE 映射區(qū)域不能存取

  • PROT_READ 映射區(qū)域可被讀取

• 參數(shù)flags：影響映射區(qū)域的各種特性。在調(diào)用mmap()時(shí)必須要指定MAP_SHARED 或MAP_PRIVATE。

  • MAP_FIXED 如果參數(shù)start所指的地址無(wú)法成功建立映射時(shí)，則放棄映射，不對(duì)地址做修正。通常不鼓勵(lì)用此flag。
  • MAP_SHARED對(duì)映射區(qū)域的寫(xiě)入數(shù)據(jù)會(huì)復(fù)制回文件內(nèi)，而且允許其他映射該文件的進(jìn)程共享。
  • MAP_PRIVATE 對(duì)映射區(qū)域的寫(xiě)入操作會(huì)產(chǎn)生一個(gè)映射文件的復(fù)制，即私人的“寫(xiě)入時(shí)復(fù)制”（copy on write）對(duì)此區(qū)域作的任何修改都不會(huì)寫(xiě)回原來(lái)的文件內(nèi)容。
  • MAP_ANONYMOUS建立匿名映射。此時(shí)會(huì)忽略參數(shù)fd，不涉及文件，而且映射區(qū)域無(wú)法和其他進(jìn)程共享。
  • MAP_DENYWRITE只允許對(duì)映射區(qū)域的寫(xiě)入操作，其他對(duì)文件直接寫(xiě)入的操作將會(huì)被拒絕。
  • MAP_LOCKED 將映射區(qū)域鎖定住，這表示該區(qū)域不會(huì)被置換（swap）。

• 參數(shù)fd：要映射到內(nèi)存中的文件描述符。如果使用匿名內(nèi)存映射時(shí)，即flags中設(shè)置了MAP_ANONYMOUS，fd設(shè)為-1。

• 參數(shù)offset：文件映射的偏移量，通常設(shè)置為0，代表從文件最前方開(kāi)始對(duì)應(yīng)，offset必須是分頁(yè)大小的整數(shù)倍。

MMKV中的源碼如下：

bool MemoryFile::mmap() {
    auto oldPtr = m_ptr;
    m_ptr = (char *) ::mmap(m_ptr, m_size, PROT_READ | PROT_WRITE, MAP_SHARED, m_diskFile.m_fd, 0);
    if (m_ptr == MAP_FAILED) {
        MMKVError("fail to mmap [%s], %s", m_diskFile.m_path.c_str(), strerror(errno));
        m_ptr = nullptr;
        return false;
    }
    MMKVInfo("mmap to address [%p], oldPtr [%p], [%s]", m_ptr, oldPtr, m_diskFile.m_path.c_str());
    return true;
}

1. mmap系統(tǒng)調(diào)用使得進(jìn)程之間通過(guò)映射同一個(gè)普通文件實(shí)現(xiàn)共享內(nèi)存。普通文件被映射到進(jìn)程地址空間后，進(jìn)程可以像訪問(wèn)普通內(nèi)存一樣對(duì)文件進(jìn)行訪問(wèn)，不必再調(diào)用read()，write（）等操作。
2. mmap并不分配空間, 只是將文件映射到調(diào)用進(jìn)程的地址空間里（但是會(huì)占掉你的 virutal memory）, 然后你就可以用memcpy等操作寫(xiě)文件, 而不用write()了。
3. 寫(xiě)完后，內(nèi)存中的內(nèi)容并不會(huì)立即更新到文件中，而是有一段時(shí)間的延遲，你可以調(diào)用msync()來(lái)顯式同步一下, 這樣你所寫(xiě)的內(nèi)容就能立即保存到文件里了。不過(guò)通過(guò)mmap來(lái)寫(xiě)文件這種方式?jīng)]辦法增加文件的長(zhǎng)度, 因?yàn)橐成涞拈L(zhǎng)度在調(diào)用mmap()的時(shí)候就決定了。
4. 如果想取消內(nèi)存映射，可以調(diào)用munmap()來(lái)取消內(nèi)存映射。

數(shù)據(jù)組織

數(shù)據(jù)序列化方面MMKV選用 protobuf 協(xié)議（下文簡(jiǎn)稱PB），pb 在性能和空間占用上都有不錯(cuò)的表現(xiàn)。PB是一種輕便的高效的結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)的格式。它適用于數(shù)據(jù)傳輸和數(shù)據(jù)存儲(chǔ)的場(chǎng)景。

• Tag - Length - Value 的數(shù)據(jù)存儲(chǔ)方式

  每一個(gè)數(shù)據(jù)都是以 Tag-Length-Value 方式表示，然后把所有數(shù)據(jù)拼接成一個(gè)字節(jié)流，最終實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)和傳輸?shù)墓δ堋?/p>

  這種存儲(chǔ)方式的優(yōu)點(diǎn)是：

  1. 不需要分隔符就能分隔開(kāi)字段，減少了分隔符的使用；
  2. 各字段存儲(chǔ)的非常緊湊，存儲(chǔ)空間利用率高；
  3. 若該字段沒(méi)有值，則該字段在序列化后的二進(jìn)制數(shù)據(jù)流中是完全不存在的，即該字段不會(huì)被編碼進(jìn)二進(jìn)制串中。

• Length - Value 的數(shù)據(jù)存儲(chǔ)方式

  在MMKV中，由于所有的存儲(chǔ)都是KV形式，不需要Tag標(biāo)識(shí)字段。每一條鍵值對(duì)，存儲(chǔ)的形式如下：

MMKV提供的是通用 kv 組件，key 可以限定是 string 字符串類型，value 則多種多樣（int/bool/double 等）。要做到通用的話，需要將 value 通過(guò) protobuf 協(xié)議序列化成統(tǒng)一的內(nèi)存塊（buffer），然后就可以將這些 KV 對(duì)象序列化到內(nèi)存中。

偽代碼實(shí)現(xiàn)如下：

message KV {
    string key = 1;
    buffer value = 2;
}

-(BOOL)setInt32:(int32_t)value forKey:(NSString*)key {
    auto data = PBEncode(value);
    return [self setData:data forKey:key];
}

-(BOOL)setData:(NSData*)data forKey:(NSString*)key {
    auto kv = KV { key, data };
    auto buf = PBEncode(kv);
    return [self write:buf];
}

寫(xiě)入優(yōu)化

上文講過(guò)PB的優(yōu)點(diǎn)：各字段存儲(chǔ)的非常緊湊，沒(méi)有分隔符；這反過(guò)來(lái)導(dǎo)致了PB沒(méi)有增量更新的能力，因?yàn)槿绻麛?shù)據(jù)段中的長(zhǎng)度變化，會(huì)導(dǎo)致后續(xù)的字節(jié)流無(wú)法解碼。

標(biāo)準(zhǔn) protobuf 不提供增量更新的能力，每次寫(xiě)入都必須全量寫(xiě)入。考慮到主要使用場(chǎng)景是頻繁地進(jìn)行寫(xiě)入更新，需要有增量更新的能力，這里MMKV的做法：

1. 將增量 kv 對(duì)象序列化后，直接 append 到內(nèi)存末尾，放棄對(duì)之前數(shù)據(jù)的修改。
2. 這樣同一個(gè) key 會(huì)有新舊若干份數(shù)據(jù)，最新的數(shù)據(jù)在最后。
3. 同時(shí)內(nèi)存中維護(hù)了一個(gè)Dict，會(huì)根據(jù)Key去重，此時(shí)讀取Key則會(huì)獲取到最新的value。
4. 在程序下次冷啟動(dòng)第一次打開(kāi) mmkv 時(shí)，不斷用后讀入的 value 替換之前的值，就可以保證內(nèi)存中Dict數(shù)據(jù)是最新有效的。

空間增長(zhǎng)

為了解決PB增量更新的問(wèn)題，我們引入 append 。這帶來(lái)了新的問(wèn)題，就是不斷 append 的話，文件大小會(huì)增長(zhǎng)得不可控。例如同一個(gè) key 不斷更新的話，是可能耗盡幾百 M 甚至上 G 空間，而事實(shí)上整個(gè) kv 文件就這一個(gè) key，不到 1k 空間就存得下。這明顯是不可取的。需要在性能和空間上做個(gè)折中，MMKV的做法：

1. 以內(nèi)存 pagesize 為單位申請(qǐng)空間，在空間用盡之前都是 append 模式。
2. 當(dāng) append 到文件末尾時(shí)，進(jìn)行文件重整、key 排重，嘗試序列化保存排重后的全量結(jié)果。
3. 排重后空間還是不夠用的話，將文件擴(kuò)大一倍，直到空間足夠。

偽代碼實(shí)現(xiàn)如下：

-(BOOL)append:(NSData*)data {
    if (space >= data.length) {  //1.判斷要寫(xiě)入的數(shù)據(jù)大小和剩余空間大小
        append(fd, data);
    } else {
        newData = unique(m_allKV); //2.根據(jù)字典，對(duì)相同的Key去重，獲取去重后的數(shù)據(jù)
        if (total_space >= newData.length) { //3.判斷去重后新的大小和總空間大小
            write(fd, newData);
        } else {
            while (total_space < newData.length) { //4.將文件擴(kuò)大一倍，直到空間足夠。
                total_space *= 2;
            }
            ftruncate(fd, total_space);
            write(fd, newData); //5. 全量寫(xiě)入文件
        }
    }
}

MMKV中的源碼實(shí)現(xiàn)：

bool MMKV::ensureMemorySize(size_t newSize) {
    if (!isFileValid()) {
        MMKVWarning("[%s] file not valid", m_mmapID.c_str());
        return false;
    }

    if (newSize >= m_output->spaceLeft() || (m_crypter ? m_dicCrypt->empty() : m_dic->empty())) { //判斷要寫(xiě)入的數(shù)據(jù)大小和剩余空間大小，相當(dāng)于上文偽代碼的第1步。
        // remove expired keys
        if (m_enableKeyExpire) {
            filterExpiredKeys();
        }
        // try a full rewrite to make space
        auto preparedData = m_crypter ? prepareEncode(*m_dicCrypt) : prepareEncode(*m_dic); //根據(jù)字典去重并編碼后，獲取去重后的數(shù)據(jù)，相當(dāng)于上文偽代碼的第2步
        // dic.empty() means inserting key-value for the first time, no need to call msync()
        return expandAndWriteBack(newSize, std::move(preparedData), m_crypter ? !m_dicCrypt->empty() : !m_dic->empty());
    }
    return true;
}

bool MMKV::expandAndWriteBack(size_t newSize, std::pair<mmkv::MMBuffer, size_t> preparedData, bool needSync) {
    auto fileSize = m_file->getFileSize();
    auto sizeOfDic = preparedData.second; //去重后的數(shù)據(jù)長(zhǎng)度
    size_t lenNeeded = sizeOfDic + Fixed32Size + newSize; // 新增后的總長(zhǎng)度 =Fixed32Size(內(nèi)容長(zhǎng)度的編碼) + 去重后的數(shù)據(jù)長(zhǎng)度 + 新增的長(zhǎng)度
    size_t nowDicCount = m_crypter ? m_dicCrypt->size() : m_dic->size();
    size_t laterDicCount = std::max<size_t>(1, nowDicCount + 1);
    // or use <cmath> ceil()
    size_t avgItemSize = (lenNeeded + laterDicCount - 1) / laterDicCount;
    size_t futureUsage = avgItemSize * std::max<size_t>(8, laterDicCount / 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 || (needSync && (lenNeeded + futureUsage) >= fileSize)) { //判斷新增后的總大小和總文件大小，相當(dāng)于上文偽代碼的第3步
        size_t oldSize = fileSize;
        do {
            fileSize *= 2;
        } while (lenNeeded + futureUsage >= fileSize);  //擴(kuò)大一倍后再次比較，直到空間大小足夠。相當(dāng)于上文偽代碼的第4步
        MMKVInfo("extending [%s] file size from %zu to %zu, incoming size:%zu, future usage:%zu", m_mmapID.c_str(),
                 oldSize, fileSize, newSize, futureUsage);

        // if we can't extend size, rollback to old state
        // this is a good place to mock enlarging file failure
        if (!m_file->truncate(fileSize)) {
            return false;
        }

        // check if we fail to make more space
        if (!isFileValid()) {
            MMKVWarning("[%s] file not valid", m_mmapID.c_str());
            return false;
        }
    }
    return doFullWriteBack(std::move(preparedData), nullptr, needSync); //重新寫(xiě)入文件。相當(dāng)于上文偽代碼的第5步
}

數(shù)據(jù)校驗(yàn)

考慮到文件系統(tǒng)、操作系統(tǒng)都有一定的不穩(wěn)定性，MMKV另外增加了 crc 校驗(yàn)，對(duì)無(wú)效數(shù)據(jù)進(jìn)行甄別。

循環(huán)冗余校驗(yàn)（Cyclic Redundancy Check， CRC）是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包或電腦文件等數(shù)據(jù)產(chǎn)生簡(jiǎn)短固定位數(shù)校驗(yàn)碼的一種散列函數(shù)，主要用來(lái)檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤。

CRC 算法的基本思想是將傳輸?shù)臄?shù)據(jù)當(dāng)做一個(gè)位數(shù)很長(zhǎng)的數(shù)。將這個(gè)數(shù)模二除以另一個(gè)數(shù)。得到的余數(shù)作為校驗(yàn)數(shù)據(jù)附加到原數(shù)據(jù)后面。

實(shí)際應(yīng)用時(shí)，發(fā)送方和接收方按以下方式通信：

1. 發(fā)送方和接收方在通信前，約定好一個(gè)預(yù)設(shè)整數(shù)作為除數(shù)。
2. 發(fā)送方在發(fā)送前根據(jù)原始數(shù)據(jù)和約定好的除數(shù)進(jìn)行模二除法運(yùn)算生成余數(shù)（即CRC碼），然后將其附加到原始數(shù)據(jù)后面一起發(fā)送給接收方。
3. 接收方收到后將其模二除以約定好的除數(shù)，當(dāng)且僅當(dāng)余數(shù)為0時(shí)接收方認(rèn)為沒(méi)有差錯(cuò)。

詳細(xì)關(guān)于CRC校驗(yàn)原理，可參考筆者的另一篇文章用人話講CRC校驗(yàn)原理。