设计 一个带外部存储的 KV 存储
· 阅读需 3 分钟
需求
- 数据大小:值的数据大小过大,无法保存在内存中,我们应该利用外部存储来存储它们。然而,我们仍然可以将数据键保存在内存中。
- 单主机解决方案。没有分布式设计。
- 优化写入。
解决方案
- 内存哈希表索引 + 索引提示文件 + 数据文件
- 仅追加以优化写入。仅有一个活动数据文件用于写入。并将活动数据压缩到旧的数据文件中以供读取。
组件
-
内存中的
HashMap<Key, <FildId, ValueOffset, ValueSize, Timestamp>>
-
数据文件布局
|crc|timestamp|key_size|value_size|key|value|
...
- (索引)提示文件,内存哈希表可以从中恢复
操作
删除:通过内存哈希表获取位置,如果存在,则前往磁盘上的位置将值设置为一个魔法数字。
获取:通过内存哈希表获取位置,然后前往磁盘上的位置获取值。
放置:追加到活动数据文件并更新内存哈希表。
定期压缩策略
-
复制最新条目:内存哈希表始终是最新的。停止并复制到新文件中。时间复杂度为 O(n),n 是有效条目的数量。
- 优点:对于过期或删除的条目效率高。
- 缺点:如果过期的条目很少,会消耗存储空间。可能会使空间翻倍。(可以通过让一个辅助节点定期进行压缩工作来解决,例如,Hadoop 辅助名称节点)。
-
扫描并移动:对于每个条目,如果是最新的,移动到已验证部分的尾部。时间复杂度为 O(n),n 是所有条目的数量。
- 优点:
- 缩小大小
- 不需要额外的存储空间
- 缺点:
- 复杂,需要通过事务同步哈希表和存储。可能会影响性能。
- 优点:
后续问题
- 如何检测可以压缩的记录?
- 使用时间戳。
- 如果一个哈希表无法适应单台机器的内存怎么办?
- 一致性哈希,Chord DHT,查询时间复杂度为 O(logn),使用指针表,而不是这里的 O(1) 使用哈希表。