shesl-meow
博客 标签 分类 笔记
游戏
2048
shesl-meow

目录

💾客户端本地存储技术

佘崧林
   约 5250 字   预计阅读 11 分钟    次阅读  

在实习过程中，在字节跳动内部分享上学习的东西

客户端本地存储主要有以下的几个作用：

  1. 作为网络 IO 的缓存：缓存图片、缓存接口的 Response；
  2. 保存配置或者数据：配置信息、状态信息、日志信息、Crash 信息等；
  3. 作为内存的 Backing Store：暂存大文件、征用扩展内存；

方法论：如何分析各种存储方案，主要考虑以下几个特性：

  1. 读写性能：平均读写性能、最坏读写性能；
  2. 并发性能：是否线程安全、读写操作互相并发的能力；
  3. 数据完整性：数据损失或丢失的概率；
  4. 空间性能：存储相同的数据，需要的磁盘与内存空间；

Plist

plist 是一种 xml 格式，是 iOS 中最常用的配置存储数据格式，下面是一个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
	<key>quiz</key>
	<dict>
		<key>question</key>
		<array>
			<dict>
				<key>text</key>
				<string>What does 'API' stand for?</string>
				<key>answer</key>
				<string>API stands for Application Programming Interface.</string>
			</dict>
			<dict>
				<key>text</key>
				<string>What's so good about pragmatic REST?</string>
				<key>answer</key>
				<string>It's focused on the api consumer, so it makes it easier for developers to contribute to your app library!</string>
			</dict>
		</array>
		
	</dict>
</dict>
  • 读写性能都是 O(n)，必须全部从磁盘中读出写入；
  • 数据完整性：每次都要全量读写。断电等不可抗力发生时，数据损失发生概率更大；
  • 磁盘空间复杂度 O(n)，内存空间复杂度 0；
  • 并发性能需要自己实现；

适用场景：

  • Plist 不适合存储过多数据，这样会造成比较严重的读/写延时。同时也会增加 Plist 损坏的概率，导致数据丢失。
  • Plist 适合与简单少量配置存储的场景，这种情况下，性能可以接受，操作的实现也足够简洁。

NSUserDefault

NSUserDefault 是常用的客户端 K-V 存储方案，其底层使用 Plist 文件存储，不同于直接操作 Plist 文件读写数据：

  • NSUserDefault 内部设置了内存缓存，大大提升了读性能；
  • 通过异步跨线程的延时同步机制，NSUserDefault 会在写入事件发生后的一段时间批量的处理写入操作，提升写入性能。

性能分析：

  • 读操作一般是直接读取内存，平均时间复杂度为 0；最坏读性能发生初始化之前，时间复杂度 O(n)；
  • 如果平均 x 次写入进行一次全量写回，平均时间复杂度 O(n/x)；最坏就是连续全量写回 O(n)；
  • 数据完整性：NSUserDefault 的异步延时同步机制很有可能导致数据在极端情况下无法触发，但是相对于 Plist，其有更少的回写次数。所以其数据损坏的可能性比 Plist 小，但是数据丢失的概率比 Plist 大。
  • 空间性能：除了内存开销，与 plist 一致；
  • 并发性能：NSUserDefault 是线程安全的，但是不支持并发；

NSUserDefault 是 Plist 的优化：

  • 有更好的读写性能、以及更友好简单的操作接口；
  • 但是它需要额外的内存开销，而且写性能依然比较差，经常会触发全量回写，没有质的提升，依然只推荐存储较少的数据；
  • 它规模可以比 Plist 大，4M 以内是比较推荐的值（超过4M，Console 会有 Warning）。
  • 在性能提升的同时，也更容易导致数据丢失，不建议存储非常重要的配置数据

MMKV

mmap 技术

在了解 MMKV 技术之前我们需要先了解一下 mmap 技术：

技术痛点：

  • 在传统读写文件时，我们通常需要在内存中自己设置 buffer；以及处理文件与内存的同步（seek、write、read）。这通常比较复杂，我们还需要适当的 fsync 调用。

解决方案：

  • Unix 操作系统提供了一个叫做 mmap 的函数，其底层适用 swap 实现。它将文件映射到进程的一块虚拟地址空间上，操作文件简化为直接操作内存。

示例程序：下面是一个拷贝文件的示例程序：

1
2
3
4
5
6

auto mmap_src = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd_src, 0);
auto mmap_dst = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd_dst, 0);
if (mmap_src == MAP_FAILED || mmap_dst == MAP_FAILED) {
    return ;
}
memcpy(mmap_dst, mmap_src, size);

因为这种方案使用了虚拟内存系统的 swap 机制，mmap 有以下特性：

  1. 并不占用进程内存：他是直接映射到操作系统对 IO 设备的缓存 PageCache 上。相对于正常IO操作，他直接就省去了PageCache 复制数据到进程中的 Buffer 这一步骤，省去了一大笔内存复制的开销。
  2. 数据共享：多个进程如果映射到同一文件，因为他们会映射到相同的物理内存上。一个典型的例子就是动态库加载，动态库就是通过 mmap 来实现共享的。
  3. 回写特性：手动 msync 触发；在 munmap、进程被杀死、内存紧张时自动触发；部分操作系统也会定期回写。只要数据写入了内存，即使写入进程被杀死，操作系统也会负责数据的回写。

注意这个技术的第三点，也就是说如果我们不关心回写磁盘的问题，操作系统也会自动完成。

MMKV 技术

什么是 MMKV（开源地址：https://github.com/Tencent/MMKV）？

  • MMKV 是腾讯开源的一个 k-v 存储库，旨在替代 NSUserDefault；

  • Plist 的写入瓶颈在于文件中没有数据结构，不能直接进行查询和数据插入操作，导致每次必须全量写入序列化后的数据；

  • MMKV 技术使用 mmap 在内存中映射了一个简单的数据结构；这个数据结构大概是以下几个部分：

    META_INFOKEY_SIZEKEY_VALUEDATA_SIZEDATA_VALUE
    一些基本信息
    比如检测数据完整性的 CRC    		键大小键值大小值

MMKV 技术的工作流程：

  • 读数据：MMKV 在初始化的时候会通过 mmap 读取所有的数据，然后在内存中生成一个 Dictionary。
  • 写数据：当有一个新 pair 时，首先写入缓存，然后在 mmap 文件尾部追加一个 pair。
  • 注意⚠️：MMKV 文件中对于一个 Key 可能有多个 Pair 存在。即使一直操作同一个Pair，也会导致MMKV文件的增大。当 MMKV 写入的数据将要超过相关文件的大小时，MMKV 会进行 mumap 操作，并扩大文件长度，重新进行 mmap 操作，同时用内存缓存中的数据全量写入，覆写原来的 MMKV 文件内容，在此时完成 key-value 一对多的数据去重，解决了 MMKV 文件占用过大的问题。

性能分析：

  • 读性能：正常时直接读取内存，所以平均读性能时间复杂度为 0；初始化时需要全量读取到内存中，并且 MMKV 不覆盖的特性每个键有多个值对应。设每个键有 k 个存储记录，时间复杂度 k*O(n)；
  • 写性能：通常的操作仍然在内存中进行，复杂度 0；最坏情况是触发了 swap，全量写回 O(n)；
  • 空间性能：因为冗余记录的存在，空间复杂度 k*O(n)；内存空间复杂度 O(n)。
  • 并发性能：线程安全，但是不支持并发；

MMKV 彻底解决了 NSUserDefault 写入性能慢的问题，写入性能几乎达到内存级别，但是偶尔还是会有全量回写的情况发生。另外 MMKV 在正常情况下大大降低了数据丢失的风险（app 被突然杀死），但是对于突然断电的情况，可能会有比较大的风险。

SQLite

为了实现不依赖缓存的高效读/写，我们需要更高级的数据结构，基于 B-Tree 的 SQLite，是移动端目前一个比较好的选择，除了提供高效读写性能外，SQL 的强大查询能力也为我们实现高效 ORM 系统提供了基础。

DELETE 模式

SQLite 提供了标准的事务回滚机制。为了实现事务回滚，SQLite 提供了日志的概念，即在写入数据到 B-Tree前记录一份日志到临时文件，如果事务写入失败，则通过日志恢复老的数据。

SQLite 的默认日志模式为 DELETE 模式，即在写入完成后删除日志文件。

性能分析：

  • 读性能（平均与最坏相同）：假设 B-Tree 单个节点最多有 x 个孩子，则查询复杂度为 $$O(log_{x} n)$$，通常情况下，访问的节点数目不会超过 4 个。

  • 写性能（平均与最坏相同）：查询老数据 $$O(log_x n)$$，写入日志 O(1)，写入 B-Tree $$O(log_x n)$$。 所以总共的 IO 复杂度为 $$O(2 * log_x n)$$。

  • 空间性能：SQLite 的空间性能较差，主要是因为：

    1. B-Tree 的数据结构需要维护许多额外的索引，会带来极大的空间开销；
    2. 删除语句执行之后，默认不会删除相关的信息，而是将节点标记为可重用。

  • 并发性能：SQLite 默认提供多种线程模式，可以设置为由 SQLite 提供线程安全的保证，也可以设置为有用户自行保证。在保证每个线程使用一个连接的情况下，SQLite 也支持读并发，但不支持读写并发和写写并发。

    SQLite 因为是天生多进程支持，锁级别是文件锁，文件锁的最大问题是不能像普通锁一样有自动唤醒机制，在获取锁失败后 SQLite 会过一段时间尝试再次获取锁（类似于自旋），如果超出一定的次数就会抛出 SQLite-Busy 错误。

DELETE 模式下的 SQLite，在读性能上有比较好的表现，平均和最坏性能都非常稳定。但是写入性能远远慢于读性能，为了安全，频繁的fsync 调用也会大大拖慢写入性能。但是由于其是增量操作模式，每次操作的数据不会很大，在正常情况下，写入性能也足够使用，至少远远高于传统的文件写入方式。

WAL 模式

WAL 是 SQLite 新引进的一种日志技术，其旨在提升 SQLite 的写入性能，以及并发性。

工作流程：

  • WAL 模式下 SQLite 直接将新写入的数据转化为一个日志，追加在 WAL 文件的尾部（由于是追加，这个过程是顺序写，写入性能几十倍于随机写）
  • 追加完以后，写入操作完成。
  • 当写入的数据量到达一定阈值（默认为 4M）的时候，通过一个叫做 checkpoint 的过程，将 WAL 中记录的日志全部统一写回 B-Tree，然后删除 WAL 文件。

关于 checkpoint 主要会面临的难题：

  • 写入峰值（在写入操作触发了 checkpoint 操作时后这次写入会非常慢）、WAL 文件大小控制；

性能分析：

  • 平均读性能：读数据时先会从 WAL 文件查找数据，文件中有一个叫做 shm 的索引文件提供加速，WAL 大小控制在 10M 以内，查找效率接近于 B-Tree；如果 WAL 文件找不到则会进入 B-Tree 中查找。所以我们可以认为 IO 复杂度为 $$O(log_x n)$$

    最坏读性能：如果 WAL 文件过大，则读性能退化为线性，m 个日志记录的 IO 复杂度为 $$O(m)$$

  • 平均写性能：写入只需要追加日志到 WAL 文件的尾部就完成了写入。又因为 WAL 文件的结构并不像 B-Tree 那样复杂，可以不需要每次写入 WAL 都进行 fsync，写入开销为 O(1)

    最坏写性能：当 SQLite 需要进行 Checkpoint 时，首先需要从 WAL 中读取数据，其次插入B-Tree，假设WAL 文件有 m 个日志，则写入开销为 $$m * O( log_x n ) + O(m)$$

  • 数据完整性：WAL 文件损坏较容易恢复，完整性优于 DELETE 模式；

  • 空间性能：WAL 文件还是运行的临时文件，空间性能与 DELETE 模式相似；

  • 并发性能：WAL 模式提供了读写并发的能力，当一个读者进入 WAL 文件时，会找到最后一个没有被写入的节点并进行 mark，如 log6，然后在这个 log 之前的数据中进行查找相关 key 比较老的副本，而数据写入依然可以并发的 Append 到 WAL 文件的尾部。由于 SQLite-Busy 的问题依然存在，如果无法处理Busy，依然可以认为SQLite在WAL模式下也没有并发能力。

YYCache

YYCache 是一个基于 SQLite 的持久化缓存框架，其作为 YYWebImage 的配套图片缓存广为人知。

它有以下特点：

  • YYCache 的接口是 K-V 形式的，并提供了淘汰策略。
  • YYCache 的持久化层由 SQLite 与文件系统混合组成。
  • YYCache 的 SQLite 中有一张 manifest 表来存储数据和淘汰策略相关的信息。

YYCache 一些机制分析：

  • 小文件优化：对于 20KB 以下的文件直接存入 SQLite，节省磁盘空间。因为使用 mmap 操作文件系统，每个单独文件的大小一定是页表大小的整数倍（4K 或 8K）；
  • 淘汰机制：为了维护 LRU (Least Recently Used) 相关数据，YYCache 每次读写入一个数据还需要额外记录 last_access_time 和 modification_time 数据，同时在整体大小超过阈值的时候，Query 全表找到最老的数据并批量删除。这为整个系统带来了额外的开销。
  • checkpoint 策略：YYCache 使用 SQLite 的 WAL 模式，并采用了默认的Checkpoint 策略。
  • 注意⚠️：YYCache 的原生实现在进行读取操作后并没有进行 reset（只在每次读操作开始前 reset），这可能导致读行为一直不结束，进而导致 Checkpoint 无法回收正在被读取的数据，极端情况下会导致 WAL 膨胀到 GB 级别，最终导致 WAL 的 Checkpoint 永远无法完成，数据库读写操作全部直接卡死。

性能分析：

  • 平均读性能：通常情况下，读数据时，为了维护 LRU 信息，还需要进行一次 last_access_time 写操作，所以其 IO 性能为 $$O(log_x n) + O(1)$$。如果命中了缓存，则只有写 IO 操作，即 O(1)。

    最坏读性能：就是触发 checkpoint 时，WAL 文件有 m 个日志，则 IO 性能为 $$m * O( log_x n ) + O(m) + O(log_x n)$$

  • 平均写性能，同 WAL 模式的 SQLite，O(1)

  • 最坏写性能，如果触发了 LRU 阈值，会进行全表扫描以及 delete，再加上 checkpoint，IO 复杂度为 $$O(n) + m * O( log_x n ) + O(m)$$

  • 数据完整性能，同 WAL 模式的 SQLite。

  • 空间性能，由于有额外字段记录 LRU 信息，会大于存储数据的本身，另外 YYCache 有内存缓存，大小是常数 k，复杂度为 O(k)。

  • 并发性能，YYCache 采用了互斥模式，线程安全，但不能并发。

YYCache 作为一个缓存框架本身是很优秀的，特别在存储图片时，还会根据文件大小选择最合适的方案进行存储，减小了磁盘占用和碎片文件，提升了写入效率。但是 LRU 本身的开销还是非常大，基于全盘扫描的淘汰以及默认的 checkpoint 策略可能会导致比较严重的卡顿，自身的 Bug 还可能导致用户无限 ANR，空间占用也比较大。虽然 YYCache 的接口是 K-V 的，但是我们建议，当需要有淘汰机制的时候才选择 YYCache，如果只是需要一个 K-V 库请选用其他方案或者自己实现。

WCDB

WCDB 是腾讯开源的一个 SQLite 封装，其提供了高速 ORM 系统，以及针对 SQLite 进行了不少优化。

下面列举这个封装做的几件事情：

  • 优化并发能力：在WCDB 为了解决 SQLite-Busy 的问题，直接修改源码去除了 SQLite 的文件锁，使用正常的唤醒机制替换。这使得 SQLite 的并发能力得到充分的释放。
  • checkpoint 策略：SQLite 默认策略执行的两个缺点是，写入峰值与 WAL 文件无限增长：
    • 对于前者，WCDB 使用异步 checkpoint 的方式：定义 sqlite3_wal_hook 函数用于执行 checkpoint，WAL 文件大小超过阈值后，开启新的线程等待 2s 执行这个函数，从而不会阻塞写入；
    • 对于后者，为了防止 WAL 文件无限增长，当文件大小超过阈值后，WCDB 会锁死 DB，阻塞新的读写操作，直到 checkpoint 完成。

性能分析：

  • 平均与最坏写性能均为 $$O(log_x n)$$；

  • 平均写性能为 O(1)，最坏写性能为执行 checkpoint 时，因为进行了异步优化，所以用户无感知；

  • 数据完整性能：WCDB 会定期备份 master 表，并在损坏时自动恢复，数据完整性能优于 WAL 模式的 SQLite。

  • 空间性能：除了数据库开销外，还有备份 master 表的开销，但是该开销是固定的，所以空间性能和 WAL 模式下的 SQLite 类似。

  • 并发性能：线程安全，支持读读并发，读写并发，不支持写并发。

更新于 2019-11-12
 客户端, 数据库, 字节跳动
返回 | 主页