🔗 功能：大块存储

• 目标：支持在块存储中缓存大型（即大于数据库槽大小）响应。
• 状态：已完成
• 版本: 3.5
• 开发者：AlexRousskov 和 Dmitry Kurochkin
• 更多：基于 块存储 功能。

🔗 定义

• 小：适合单个数据库槽（在小型块存储中，槽大小与最大大小相同，所有缓存条目都很小）。
• 大：不小。
• 巨大：以 GB 为单位。

🔗 设计目标

• 小型块存储的设计目标在此通过引用引入。
• 与小型块存储一样的小文件性能。
• 支持大型响应。
• 支持巨型响应。
• 合理的范围请求支持（例如，避免加载整个文件来提供“最后 100 字节”的范围）。
• 启动速度更快是理想的。

非目标

• 与小型块存储数据库的二进制兼容性。

🔗 数据库文件结构

数据库文件以通常的头部槽开始。之后是数据库条目槽。所有槽的大小都相同（例如，16KB 或 32KB）。

slot
slot
…
slot

每个槽可以是以下两种类型之一，详细说明如下：头部槽和数据槽。

🔗 头部槽

magic1
db size and other aggregate meta data about the db
stored db map size
stored db map pointer
0

头部应与小型块存储头部类似。数据库映射字段在初始实现中不会被使用，但可能用于指示数据库索引的存在和描述其位置，以便将来代码版本使用。

🔗 数据槽

magic2
StoreEntry key
First slot pointer in the entry chain
Next slot pointer in the entry chain
Entry chain version
StoreEntry embryo (STORE_META_STD)
Weight
0
raw entry data

单个缓存条目可能包含多个数据库槽，形成一个“条目链”。

第一个槽指针字段包含条目链中第一个槽的地址。这用于查找需要被清除以腾出空间给更有价值条目的条目（块根据条目键哈希到槽地址）。条目链中的第一个槽将指向自身或最后一个链槽（XXX）。

下一个槽指针字段包含条目链中下一个槽的地址。

每次覆盖条目时，条目版本都会增加。计数器回绕是可以接受的。版本用于在数据库映射验证期间检测“悬空”槽。悬空槽不再属于任何存储的条目，但也没有被标记为空（例如，由于工作进程或磁盘进程崩溃）。条目链版本是条目第一个槽的版本。如果条目链包含一个具有不同条目链版本的槽，则整个链无效，在数据库验证过程中，其所有槽都会被标记为空。

StoreEntry 的胚胎（STORE_META_STD）用于在检测到命中时为给定槽创建 StoreEntry 对象。XXX：研究我们是否必须存储该信息，还是可以在加载完第一个命中槽之前延迟使用胚胎数据。

权重字段可能被 LFU 类似的替换策略使用。当两个条目链竞争同一个数据库槽时，权重较高的条目获胜（但会损失部分权重）。XXX：详细说明权重计算算法，以及因此的替换策略。XXX：考虑使用 LRU 替代。

所有槽指针均为 4 字节（32 位）无符号整数，零表示空指针。即使是 2TB 的数据库，如果每个槽 8KB，也只需要 28 位来枚举所有可能的 2.68 亿个槽。

🔗 数据库映射

该映射是一个固定大小项的数组。数组中的项位置对应于数据库中的槽位置。存储键被哈希以查找对应的项位置（此设计与小型块存储使用的相似）。每个项包含对应数据槽的非数据部分，以及原子锁和相关状态成员。

要锁定一个条目链，请锁定与第一个链槽对应的映射项。无需锁定每个单独的映射项（对应链中的所有槽）。

🔗 设计决策

已经考虑了几种备选设计方案，并已被拒绝或推迟。其中一些在此记录。

1. 初始实现将扫描整个数据库以构建内存中的缓存目录映射（StoreMap）。最终，我们将开始将映射保存到磁盘并在启动时加载，以减少数据库加载时间。我们需要更多关于数据库加载时间的信息，这可能会影响数据库映射的存储和加载方式。
2. 有可能支持一种不依赖于映射项到槽的对应关系的哈希算法。这种算法需要一个映射，除了前一个和下一个指针外，还存储“当前”或“此”槽的指针。这将有助于避免持久冲突（两个热门缓存条目互相驱逐）。然而，在共享内存中使用乐观原子锁实现这种算法非常困难。我们想先实现一个简单的版本。
3. 我们可以像传统文件系统那样，将数据库槽指针分组到 inode、间接节点和双重间接节点中。这将使我们能够更快地搜索条目中的特定偏移量，而无需逐个映射项地扫描条目链。当哈希算法稳定后（这将影响我们是否需要从槽到条目的指针来查找要驱逐的受害者时），应考虑此优化。
4. 在大多数缓存条目大于一个槽的配置中，可以通过将映射拆分为两个来节省 RAM 和映射 I/O：一个“下一个槽”映射（版本号加上每个槽的一两个 4 字节指针）和一个 inode 映射（每个缓存条目一个较大的项，包含所有条目元数据）。当映射结构和哈希算法稳定后，尤其是在数据库槽数量与缓存条目数量之间存在至少数量级差异的情况下（在满载数据库中），应考虑此优化。

🔗 缓慢的缓存索引构建

块存储通常比 UFS 存储构建其内存索引慢。

Rock: 2016/09/13 00:25:34|   Took 1498.42 seconds (3972.24 objects/sec).
UFS:  2016/09/13 00:00:51|   Took 5.71 seconds (533481.90 objects/sec).

较长的索引构建时间是上述设计决策 #1 的副作用。这里有几个重要的细节。

1. Squid 自身启动并不慢。缓存索引构建很慢。
2. Squid 在构建块索引的同时可以处理请求，包括缓存命中，但索引确实会影响 Squid 的整体性能和命中率。
3. 避免将加载“少量”UFS 条目（来自干净的 swap 状态）与扫描块的所有可用缓存槽进行比较。在 UFS 缓存刚开始使用且条目很少（swap.state 小）时，观察到的差异最大。块存储关注的是 Squid 长时间运行且缓存已满的情况（常见且预期的用例）。
4. 我们实际上是在比较块的从头开始构建索引与 UFS 的干净索引加载。如果您删除所有 swap 状态文件，UFS 的索引时间可能比块的差。如果您保留脏的 swap 状态文件，则 UFS 索引可能会显着减慢；例如，在 Squid 崩溃后会发生这种情况。块索引不依赖于之前的 Squid 状态。
5. 块的索引代码可以，而且很可能 会被 以各种方式进行优化。其中涉及许多权衡，一些优化可能会损害运行时性能。例如，存在以下权衡：
   • 在运行时维护磁盘索引（即 swap 状态文件）（然后在关闭时保存一个干净的索引），就像 UFS 存储那样，以及
   • 像块存储那样，在启动时通过扫描整个缓存来从头构建索引。

类别：功能

导航：站点搜索，站点页面，类别，🔼 向上