设计一个带外部存储的 KV 存储

需求

1. 数据大小：值的数据大小过大，无法保存在内存中，我们应该利用外部存储来存储它们。然而，我们仍然可以将数据键保存在内存中。
2. 单主机解决方案。没有分布式设计。
3. 优化写入。

解决方案

• 内存哈希表索引 + 索引提示文件 + 数据文件
• 仅追加以优化写入。仅有一个活动数据文件用于写入。并将活动数据压缩到旧的数据文件中以供读取。

组件

1. 内存中的 HashMap<Key, <FildId, ValueOffset, ValueSize, Timestamp>>

2. 数据文件布局

|crc|timestamp|key_size|value_size|key|value|
...

3. （索引）提示文件，内存哈希表可以从中恢复

操作

删除：通过内存哈希表获取位置，如果存在，则前往磁盘上的位置将值设置为一个魔法数字。

获取：通过内存哈希表获取位置，然后前往磁盘上的位置获取值。

放置：追加到活动数据文件并更新内存哈希表。

定期压缩策略

• 复制最新条目：内存哈希表始终是最新的。停止并复制到新文件中。时间复杂度为 O(n)，n 是有效条目的数量。

  • 优点：对于过期或删除的条目效率高。
  • 缺点：如果过期的条目很少，会消耗存储空间。可能会使空间翻倍。（可以通过让一个辅助节点定期进行压缩工作来解决，例如，Hadoop 辅助名称节点）。

• 扫描并移动：对于每个条目，如果是最新的，移动到已验证部分的尾部。时间复杂度为 O(n)，n 是所有条目的数量。

  • 优点：
    • 缩小大小
    • 不需要额外的存储空间
  • 缺点：
    • 复杂，需要通过事务同步哈希表和存储。可能会影响性能。

后续问题

• 如何检测可以压缩的记录？
  • 使用时间戳。
• 如果一个哈希表无法适应单台机器的内存怎么办？
  • 一致性哈希，Chord DHT，查询时间复杂度为 O(logn)，使用指针表，而不是这里的 O(1) 使用哈希表。