🔗 缓存摘要

• 作者：Niall Doherty*

🔗 什么是缓存摘要？

缓存摘要是互联网对象缓存服务器内容的摘要。它以紧凑（即压缩）的格式包含特定 URL 是否存在的指示。

压缩采用了“有损”技术，这意味着可以实现非常高的压缩率，但代价是信息不保证 100% 准确。

🔗 如何以及为何使用它们？

缓存服务器会定期互相交换它们的摘要。

当客户端请求一个对象（URL）时，缓存可以使用其对等节点的摘要来找出哪些对等节点（如果有的话）拥有该对象。然后，缓存可以从最近的对等节点请求该对象（Squid 使用 NetDB 数据库来确定这一点）。

请注意，Squid 只会在*已启用*的摘要中进行摘要查询。如果无法为对等节点获取有效的摘要，它将禁用该对等节点的摘要。当获取到有效的摘要时，它将再次启用该对等节点的摘要。

摘要中的检查速度非常快，它们消除了对每个请求都查询对等节点的需要。因此，

• 消除了延迟，客户端响应时间应得到改善。
• 网络利用率可能会得到改善。

请注意，使用缓存摘要（用于查询对等节点的缓存内容）和生成缓存摘要（供对等节点检索）是独立的。因此，缓存可以提供摘要供对等节点使用，而自身不使用此功能，反之亦然。

🔗 缓存摘要背后的理论是什么？

缓存摘要基于布隆过滤器——它们是一种用于表示具有查找能力（查找意味着“键是否存在于过滤器中？”）的键集合的方法。

在构建缓存摘要时：

• 分配一个 m 位的向量（一维数组），所有位最初设置为 0。
• 选择 k 个独立的哈希函数，h1, h2, …, hk，其范围为 {1, …, m}（即，使用任何一个函数对键进行哈希处理都会得到一个介于 1 和 m 之间的值）。
• 要操作的 n 个键的集合表示为：A = { a1, a2, a3, …, an }。

🔗 添加键

要添加一个键，会计算该键的每个哈希函数的值。因此，如果键表示为 *a*，则计算 h1(a), h2(a), …, hk(a)。

该键的每个哈希函数的值代表数组中的一个索引，并将其对应的位设置为 1。因此，具有 6 个哈希函数的摘要在添加每个键时会有 6 位被设置为 1。

请注意，添加许多*不同的*键可能会导致某个特定位被设置为 1 多次。

🔗 查询键

要查询键是否存在，如上所述，使用哈希函数从数组中计算索引。

• 如果数组中任何对应的位为 0，则该键不存在。

• 如果数组中所有对应的位都为 1，则该键*可能*存在。

请注意“*可能*”一词。摘要中可能发生*冲突*，导致摘要错误地指示键存在。这是紧凑表示所付出的代价。虽然冲突的概率永远无法降至零，但可以对其进行控制。摘要大小与添加条目数量的比例越大，概率越低。选择的哈希函数数量也影响概率。

🔗 删除键

要删除一个键，不能简单地将相关的位设置为 0，因为其中任何一位都可能由添加另一个键而设置为 1！

因此，为了支持删除，需要为数组中的每个位位置使用一个计数器。遵循的步骤是：

• 添加键时，将适当的位设置为 1 并递增相应的计数器。

• 删除键时，递减适当的计数器（当大于 0 时），如果计数器达到 0，*然后*将相应的位设置为 0。

🔗 Squid 中缓存摘要的大小如何确定？

在初始化时，*容量*被设置为缓存中可以（已）存储的对象数量。请注意，这里存在上限和下限。

使用一个任意常数 bits_per_entry（当前设置为 5）通过以下公式计算数组的大小：

number of bits in array = capacity * bits_per_entry + 7

因此，摘要的大小（以字节为单位）为：

digest size = int (number of bits in array / 8)

当发生摘要重建时，会测量缓存大小（容量）的变化。如果容量发生了足够大的变化（10%），则会释放并重新分配摘要数组内存，否则会重用相同的摘要。

🔗 Squid 使用哪些哈希函数（以及多少个）？

协议设计允许使用可变数量的哈希函数（k）。然而，Squid 使用一种非常高效的方法，具有固定的数量——四个。

Squid 不会对 URL 计算多个独立的哈希函数，而是使用键的 128 位 MD5 哈希（实际上是 URL 和 HTTP 检索方法的组合），然后将其分成四个相等的部分。

每个块模摘要大小（m）用作其中一个哈希函数的值——即位数组的索引。

注意：当 Squid 检索对象并将其存储在磁盘缓存中时，它会使用上面讨论的 MD5 哈希作为查找键将其添加到内存索引中。这意味着缓存摘要哈希函数的值已经可用，因此操作效率极高！

显然，修改代码以支持可变数量的哈希函数会更困难，并且很可能会降低效率。

🔗 对象如何添加到 Squid 的缓存摘要中？

内存索引中引用的每个对象都会被检查是否适合添加到摘要中。

许多对象不适合，例如私有对象、不可缓存对象、负缓存对象等，并会立即跳过。

接下来会进行*新鲜度*测试，以尝试猜测对象是否很快会过期，因为如果会，则将其添加到摘要中没有意义。会根据刷新模式检查对象是否过时……

由于 Squid 使用前面提到的 MD5 键在其索引中存储对象引用，因此每个对象都没有实际的 URL——这意味着使用的模式将回退到默认模式“.”。这是一个不幸的状况，但对此无能为力。稍后将向配置文件添加一个*cd_refresh_pattern*选项，至少能使混乱更清晰一些

请注意，最好对缓存摘要的刷新模式保持保守，即*不要*添加可能很快过期的对象。这将减少误命中次数。

🔗 Squid 是否支持缓存摘要中的删除？什么是 diffs/deltas？

Squid 不支持从摘要中删除。因此，必须定期从头开始重建摘要，以清除过时的位并防止摘要污染。

一个更复杂的选项是使用*diffs*或*deltas*。这些将通过构建新摘要并与当前/旧摘要进行比较来创建。它们本质上将包含自*上一个*摘要以来聚合的删除和添加。

由于使用它们所需的带宽应该更少，因此可以进行更频繁的更新（从而获得更准确的信息）。

成本

• RAM：在比较进行时，需要额外的 RAM 来保存两个摘要。
• CPU：可能微不足道。

🔗 本地摘要何时以及多久构建一次？

本地摘要在以下情况下构建：

• 启动后 store_rebuild 完成时（缓存内容已在内存中索引），以及
• 此后定期进行。目前，它每小时重建一次（在“智能”选择其他固定或动态变化的周期之前，需要更多数据和经验）。好处是本地缓存决定了过期时间，而对等节点必须遵守（稍后讨论）。

当（新的）摘要在内存中构建时，旧版本（存储在磁盘上）仍然有效，并将返回给任何请求它的对等节点。当摘要构建完成后，它将被交换到磁盘，覆盖旧版本。

重建过程 CPU 密集，但并非过分。由于 Squid 使用事件处理模型进行编程，因此采取的方法是将摘要构建任务分成块（即要添加的条目块），并将每个块注册为一个事件。如果 CPU 负载过高，可以延长构建时间——只要在下次重建之前完成即可！

未来将摘要构建实现为单独的进程/线程可能会更有效……

🔗 缓存摘要如何在对等节点之间传输？

缓存摘要使用标准的 HTTP 协议从对等节点获取（请注意，使用的是*拉取*而不是*推送*技术）。

首次访问对等节点后，会排队一个*peerDigestValidate*事件（此事件决定是否该从对等节点获取新版本的摘要）。排队延迟取决于已为验证排队的对等节点的数量——这样就不会同时获取所有不同对等节点的摘要。

响应摘要请求的对等节点将使用 HTTP *Expires*标头指定该摘要的过期时间。因此，请求缓存知道何时应请求该对等节点摘要的新副本。

注意：请求缓存使用 If-Modified-Since 请求，以防对等节点因某种原因未在上次获取摘要后重建其摘要。

🔗 缓存摘要如何以及存储在哪里？

🔗 本地构建的缓存摘要

由于本地摘要纯粹是为了方便邻居而生成的，因此严格来说不需要将其保存在内存中。然而，我们决定将本地摘要保存在内存中，部分原因是：

• 在每次摘要重建时，大约相同数量的内存将被（重新）分配。
• 内存需求可能非常小（与缓存服务器的其他需求相比）。
• 如果支持对摘要的持续更新（例如添加/删除），则有必要在内存中的摘要上执行这些操作。
• 如果支持 diffs/deltas，则“旧”摘要必须无论如何都要被交换到内存中进行比较。

当摘要在内存中构建时，它会被交换到磁盘，在那里它被存储为“正常”缓存项——这就是对等节点请求它的方式。

🔗 从对等节点获取的缓存摘要

当客户端查询到达时，需要*快速查找*以确定是否应向邻居缓存发出请求。因此，需要将所有对等摘要保存在内存中。

对等摘要也存储在磁盘上，原因如下：

• 恢复 如果停止并重新启动，可以从本地磁盘副本重用对等摘要（它们很快将使用 HTTP IMS 请求与相应的对等节点进行验证，如前所述）。
• 共享 对等摘要作为正常对象存储在缓存中。这允许它们被提供给邻居缓存。

🔗 如何解释缓存管理器中的缓存摘要统计信息？

可以通过缓存管理器或*squidclient*实用程序查看缓存摘要统计信息。以下示例分别显示了如何使用*squidclient*实用程序从本地主机请求可能的操作列表、从本地主机获取本地摘要统计信息、从本地主机获取刷新统计信息以及从另一个缓存获取本地摘要统计信息。

squidclient mgr:menu
squidclient mgr:store_digest
squidclient mgr:refresh
squidclient -h peer mgr:store_digest

可用的统计信息提供了大量有用的调试信息。刷新统计信息包括一个用于缓存摘要的部分，解释了为什么将项目添加到（或未添加到）摘要中。

以下示例显示了企业内部网络环境中 16GB 缓存的本地摘要统计信息（可能是下面讨论的有用参考）。

store digest: size: 768000 bytes
entries: count: 588327 capacity: 1228800 util: 48%
deletion attempts: 0
bits: per entry: 5 on: 1953311 capacity: 6144000 util: 32%
bit-seq: count: 2664350 avg.len: 2.31
added: 588327 rejected: 528703 ( 47.33 %) del-ed: 0
collisions: on add: 0.23 % on rej: 0.23 %

entries:capacity 是添加到摘要中的项目“可能”数量的度量。它代表在摘要创建开始时本地缓存中的项目数量——然而，目前存在上限和下限。此值乘以*bits: per entry*（任意常数）以得到*bits:capacity*，这是缓存摘要的大小（以位为单位）。将其除以 8 将得到*store digest: size*，即大小（以字节为单位）。

摘要中表示的项目数量由*entries:count*给出。这应该等于*added*减去*deletion attempts*。

由于（目前）在初始构建后不对摘要进行任何修改（不添加，也不支持删除），*deletion attempts*将始终为 0，而*entries:count*应等于*added*。

entries:util 并非真正重要的统计信息。最多，它衡量了存储中多少项目被认为适合进入缓存与多少项目被“准备”用于此。

rej 显示了多少对象被拒绝。对象不会被添加有多种原因，最常见的是刷新模式设置。请记住，（目前）将使用默认刷新模式来检查条目，并且请注意更改此模式可能会显著影响添加到摘要的项目数量！过于宽松会导致误命中增加，过于严格会导致误漏（False Misses）增加。另外请记住，在验证时（在对等节点上），将使用“真实”刷新模式——因此，将默认刷新模式保持保守是明智的。

bits: on 显示摘要中设置为 1 的位数。bits: util 将此数字表示为摘要总位数的一个百分比。正如我们前面所见，50% 的数字代表了最佳的权衡。过高的值（例如 > 75%）会导致更多的冲突，从而导致误命中，而较低的值意味着摘要未充分利用（浪费了不必要的 RAM）。请注意，对于开始填充的缓存来说，较低的值是正常的。

位序列是具有相同值的连续位序列。*bit-seq: avg.len*可以洞察哈希函数的质量。长值表示有问题，即使*bits:util*是 50%（> 3 = 可疑，> 10 = 非常可疑）。

🔗 什么是误命中，应如何处理？

当一个缓存认为对等节点拥有某个对象并向其请求，*但*对等节点无法满足请求时，就会发生误命中。

对等节点上过期的或陈旧的对象是误命中的常见原因。在查询时，对对等节点使用实际的刷新模式，并且陈旧的条目会被标记为待重新验证。然而，除非对等节点充当父节点，或者启用了*miss_access*，否则禁止重新验证。因此，客户端可能会收到错误消息而不是重新验证的对象！

误命中的频率可以降低，但永远无法完全消除，因此必须有一种健壮的方法来处理它们。Squid 设计的理念是使用轻量级技术，优化常见情况，并健壮地处理不常见情况（误命中）。

Squid 将很快支持 HTTP *only-if-cached*标头。向对等节点发出的对象请求将使用此标头，如果对象不可用，对等节点可以做出适当的响应，允许 Squid 识别情况。以下描述了 Squid 的目标：

• 使用缓存摘要来获得对对象在缓存层次结构中位置的良好估计。
• 对等节点之间持久的 HTTP 连接。将没有 TCP 启动开销，并且延迟和网络负载与 ICP（即快速）相似。
• 使用*only-if-cached* HTTP 标头进行 HTTP 误命中识别——允许回退到另一个对等节点，或者如果没有其他对等节点拥有该对象，则直接访问（或者，如果防火墙在后面，则*通过*父节点访问）。

🔗 如何跟踪/调试与缓存摘要相关的活动？

🔗 启用缓存摘要

如果您想使用缓存摘要（Squid 版本 2 中可用），您需要添加一个*configure*选项，以便编译相关的代码。

./configure --enable-cache-digests ...

🔗 access.log 条目看起来像什么？

如果由于邻居的缓存摘要中出现 HIT 而将请求转发给邻居，则*本地缓存*的 access.log 文件的层次结构（第 9 个）字段将显示为*CACHE_DIGEST_HIT/neighbour*。日志标签（第 4 个字段）应该显示 MISS。

在对等缓存上，请求应显示为来自第一个缓存的正常 HTTP 请求。

🔗 误命中看起来像什么？

最容易分析的情况是当涉及两个缓存（例如 A 和 B）且它们互不使用对方作为父节点时。在这种情况下，误命中将显示为 A 上的 CACHE_DIGEST_HIT，而在 B 上*不是* TCP_HIT（反之亦然）。如果 B 没有为 A 获取对象，则层次结构字段将显示为*NONE/-*（而 A 将收到访问被拒绝或禁止的消息）。如果对象在 B 上“不可用”，并且 B 没有为 A 启用*miss_access*（或不充当 A 的父节点），则会发生这种情况。

🔗 如何确定误命的原因？

假设 A 向 B 请求一个 URL 并收到误命中。

• 使用*squidclient*实用程序*PURGE* A 上的 URL，例如，squidclient -m PURGE 'URL'
• 使用*squidclient*实用程序从 A 请求对象，例如，squidclient 'URL'

请求的 HTTP 标头可用。有两个标头类型特别感兴趣：

• X-Cache - 这显示对象是否可用。
• X-Cache-Lookup - 这会保留在检查刷新规则*之前*存储表查找的结果（即，它指示在尝试任何验证之前对象是否可用）。

A 的 X-Cache 和 X-Cache-Lookup 标头都应显示 MISS。

如果 A 向 B 请求对象（如果摘要查找指示 B 拥有它——假设 B 是最近的对等节点，当然 ），那么将会有另一组来自 B 的这些标头。

如果 B 的 X-Cache 标头显示 MISS，则发生了误命中。这意味着 A 认为 B 拥有一个对象，但 B 告知 A 它无法检索该对象。它无法检索的原因由 X-Cache-Lookup 标头指示。如果

• X-Cache-Lookup = MISS 则 A 的（B 的版本）摘要已过时或已损坏，*或*摘要中发生了冲突（概率非常小），*或*B 最近已清除该对象。
• X-Cache-Lookup = HIT 则 B 拥有该对象，但刷新规则（或 A 的 max-age 要求）阻止 A 获得 HIT（验证失败）。

🔗 使用源代码

如果还有其他需要检查的内容，您可以随时查看源代码。主要的缓存摘要功能组织如下：

• CacheDigest.c (debug section 70) 通用缓存摘要例程

• store_digest.c (debug section 71) 本地缓存摘要例程

• peer_digest.c (debug section 72) 对等缓存摘要例程

请注意，在源代码中，“*Store Digest*”一词指的是本地创建的摘要。缓存摘要代码相当易于理解（一旦您了解了缓存摘要的工作原理）。

🔗 ICP 呢？

缺失部分

🔗 是否有缓存摘要规范？

现在有了，感谢 Martin Hamilton <martin AT net DOT lut DOT ac DOT uk> 和 AlexRousskov。

缓存摘要在 cache-digest-v5.txt 中进行了描述。

您会注意到格式类似于 Internet Draft。我们决定不将此文档提交为草案，因为缓存摘要在我们希望将其标准化之前可能会经历一些重要更改。

🔗 是否可以错开从对等节点检索 cache_digests 的时间？

Squid 已经有代码来分散摘要更新。该算法目前由*peer_digest.c*中的几个硬编码常量控制。例如，*GlobDigestReqMinGap*变量决定了两次请求摘要之间的最小间隔。您可能想尝试将 GlobDigestReqMinGap 的值从 60 秒增加到任何您觉得舒适的值（但它应该小于 hour/number_of_peers，当然）。

请注意，无论您做什么，您仍然需要给 Squid 足够的时间和带宽来获取所有摘要。根据您的环境，该带宽可能与 ICP 所需的带宽相同或不同。即将推出的摘要 delta（比摘要本身小 10 倍）可能是解决“大规模”问题的唯一方法。

回到 FAQ 索引

导航： 网站搜索、网站页面、分类、🔼 向上