C++ 设计命中计数器

命中计数器因此在广泛的领域中具有差异化的应用。例如，执行 Web 服务在跟踪用户流、分析用户行为和管理资源方面非常有用。命中计数器的主要用途是在给定的一段时间内计算某个特定资源（如网页）被访问的次数，以衡量近期活动的趋势。

关键要求

命中计数器需要高效地处理两个主要操作：命中计数器需要高效地处理两个主要操作

记录命中：这包括记录访问事件，并附带事件发生的时间。

检索命中计数：这意味着要计算在特定时间段内（例如 5 分钟）发生的访问事件的数量。

这些操作必须以极高的效率执行，以便系统能够在用户负载增加的时期提供充分的服务。

数据结构选择

选择合适的数据结构对于命中计数器的性能至关重要。所使用的结构必须允许轻松地添加具有高命中率的新内容并处理低命中率的内容。有几种选择可以完成这项工作；然而，双端队列（deque）是最合适的选择之一。

方法一：维护一个用于滑动窗口的双端队列

双端队列（deque）是一种 STL，它提供在列表或队列的两端进行快速插入和删除的功能。此属性对于存储时间戳以保持时间戳的滑动窗口是必需的。当产生新的命中时，数据被附加到双端队列的末尾，而早于指定时间间隔（“时间窗口”-例如 5 分钟）的命中则从结构的另一端出队。这将使双端队列始终只包含感兴趣的窗口大小内的正确时间戳。

操作概述

记录一次命中

当记录一次命中时，当前时间戳被附加到双端队列的末尾。

随后，从双端队列的前端检查，任何超出 5 分钟窗口的**时间戳**都会被移除。这会使双端队列保持最新，只包含相关周期内的**时间戳**。

检索命中次数

要获取过去 5 分钟内的命中次数，首先需要清理双端队列以移除任何过时的**时间戳**。清理后双端队列的大小即代表了过去 5 分钟内的命中次数。

程序

输出

 
Number of hits at timestamp 400: 5
Number of hits at timestamp 450: 4
Number of hits at timestamp 500: 3
Number of hits at the current time: 1   

解释

• HitCounter 类
  HitCounter 类是封装在滑动时间窗口内计数命中常见逻辑的主要结构。它存储命中的**时间戳**在一个双端队列中，并提供**记录**新命中和检索新命中数量的方法。
• 构造函数
  构造函数 HitCounter(int window_size_seconds) 使用特定的时间窗口（以秒为单位）初始化命中计数器。例如，五分钟窗口可以表示为三百秒。
  它验证窗口大小大于零，以防止无效配置。
• 私有成员
  Std::deque<int> hits：这是一个用于存储命中**时间戳**的双端队列。双端队列中的每个元素代表命中发生的**时间**（以自纪元以来的秒数计）。
  int window_size：这是滑动窗口的大小（以秒为单位）。它决定了命中计数器必须回溯多长时间才能认为命中是“最新的”。
• 记录命中
  hit() 方法有两种版本
  无参数：在当前时间记录命中。它使用 getCurrentTimestamp() 方法获取当前**时间**（以秒为单位），并将此**时间戳**添加到双端队列中。
  带时间戳参数：允许您手动指定命中的**时间戳**，这对于测试或模拟不同**时间**的命中非常有用。
  记录命中后，会调用 cleanUpOldHits() 方法来移除双端队列中所有早于所需**时间**窗口的**时间戳**。这确保了双端队列中只存储最新的命中。
• 检索命中次数
  getHits() 方法返回当前**时间**窗口内的命中次数。它首先调用 cleanUpOldHits() 以确保双端队列只包含有效、最新的**时间戳**。然后，它简单地返回双端队列的大小，这代表了最新命中次数。
  与 hit() 方法一样，getHits() 也可以带或不带**时间戳**调用。不带**时间戳**调用时，它使用当前**时间**。
  实用工具方法
  getCurrentTimestamp()：此方法检索当前**时间**，表示自 Unix 纪元（1970 年 1 月 1 日）以来的秒数。它使用 C++ 标准库的 std::chrono 部分来处理**时间**。
  cleanUpOldHits()：此方法负责通过移除任何过时的**时间戳**来维护双端队列。它将双端队列的**前端**（最旧的命中）与当前**时间**减去窗口长度进行比较。如果**时间戳**超出了有效窗口，则将其从双端队列中移除。此方法会重复执行，直到双端队列中的所有**时间戳**都在有效**时间**范围内。
• 错误处理
  代码包含错误检查，以确保无效参数（包括负**窗口**长度或**时间戳**）能够通过抛出异常得到妥善处理。这使得代码更加健壮，并且更易于调试。
• 主函数（示例用法）
  main() 函数演示了如何使用HitCounter 类。它模拟在特定**时间戳**记录命中，并在不同**时间**点检查命中次数。
  这部分代码旨在测试和展示 HitCounter 类的功能。它说明了命中计数器在记录新命中时的行为，以及它如何有效地更新滑动窗口内的命中计数。

复杂度分析

时间复杂度

代码的**时间复杂度**围绕记录命中和检索命中次数期间执行的操作。

记录一次命中（hit() 方法）

插入到双端队列：将新的**时间戳**添加到双端队列的**后端**是一个O(1) 操作，因为 std::deque 允许在两端进行高效插入。

清理旧命中： cleanUpOldHits() 方法从**前端**遍历双端队列，移除过时的时间戳。在最坏的情况下，当双端队列中的所有元素都过时时，此操作可以移除双端队列中的所有元素，导致 O(n) 的**时间复杂度**，其中 n 是双端队列中的元素数量。

hit() 的总**时间复杂度**

平均情况：在正常使用中，只需要移除少量元素，该操作趋向于 O(1)。

最坏情况：如果双端队列中充满了过时的元素，则操作可能是 O(n)。

检索命中次数（getHits() 方法）

清理旧命中：getHits() 方法在返回双端队列大**小**之前也会调用 cleanUpOldHits()。如上所述，这在平均情况下可能需要 O(1)，在最坏情况下可能需要 O(n)。

返回双端队列的大**小**：std::deque 上的 size() 函数以 O(1) **时间**运行，因为它只是返回当前元素的数量。

getHits() 的总**时间复杂度**

平均情况：O(1)，用于检查和移除过时的元素。

最坏情况：O(n)，如果需要移除许多元素。

空间复杂度

代码的**空间复杂度**主要由双端队列中用于存储**时间戳**的存储决定。

存储**时间戳**

双端队列：双端队列存储命中的**时间戳**。双端队列的最大**大**取决于**时间**窗口内的命中次数。如果系统在**时间**窗口内记录了 m 次命中，则**空间复杂度**可能是O(m)。

窗口**大**：窗口长度不会直接影响**空间复杂度**，但它会影响存储的命中次数的最大值。较大的窗口长度可能导致存储更多**时间戳**，从而增加**空间**利用率。

其他变量

其他变量使用的**空间**，例如 window_size 和函数中的临时变量，是恒定的，不取决于输入**大**。因此，它们的**空间复杂度**为O(1)。

方法二：使用哈希表实现可变窗口

使用哈希表（或 C++ 中的 std::unordered_map）实现具有可变**时间**窗口的命中计数器是另一种方法，它提供了灵活性和效率，尤其是在您需要支持不同的窗口**大**或同时跟踪多个不同**时间**窗口的命中时。这种方法与基于双端队列的方法不同，它利用哈希表来存储**时间戳**及其对应的命中次数，从而允许更精细地控制命中计数过程。

它是如何工作的？

在此方法中，命中计数器维护一个HashMap，其中键是**时间戳**（四舍五入到一定的粒度，例如秒），值是在这些**时间戳**记录的命中次数。这种结构允许您高效地存储和检索任何特定**时间**窗口的命中次数。

程序

输出

 
Hits in the last 300 seconds: 2
Hits in the last 100 seconds: 0
Hits in the last 200 seconds from 500: 2
Hits in the last 300 seconds after cleanup: 0   

解释

• HitCounter 类概述
  HitCounter 类封装了命中计数器的功能。它包括记录命中、检索特定**时间**窗口内的命中次数以及清理超出给定**时间**范围的旧命中的方法。该类使用 std::unordered_map<int, int>（等同于其他语言中的 HashMap）来存储每个**时间戳**的命中次数。此外，std::vector<int> 用于维护**时间戳**的顺序，这有助于清理过程。
• 记录一次命中
  该类有两个 hit() 方法
  void hit()：此方法在当前**时间**命中。它内部调用第二个 hit() 方法，并将当前**时间戳**作为参数。
  void hit(int timestamp)：此方法记录在指定**时间戳**的命中。如果**时间戳**为负，则抛出异常。然后将**时间戳**四舍五入到最近的 2 秒（在这种情况下，由于**时间戳**已为秒，因此无需进一步四舍五入）。该方法检查时间戳是否已存在于 unordered_map 中。如果存在，则命中计数将递增。如果不存在，则创建一个新的条目，初始计数为 1。**时间戳**也会被添加到 vector 中以保持顺序。
• 检索命中次数
  该类提供了两种检索特定**时间**窗口内命中次数的方法
  int getHitsInLast(int windowSizeSeconds)：此方法返回从当前**时间**起过去 windowSizeSeconds 秒内的命中次数。它调用第二个 getHitsInLast() 方法，并将当前时间戳作为参数。
  int getHitsInLast(int windowSizeSeconds, int timestamp)：此方法返回从特定**时间戳**起过去 windowSizeSeconds 秒内的命中次数。它首先检查**时间戳**和窗口**大**是否有效（即非负且大于 0）。然后，它遍历 unordered_map 以查找所有在所需**时间**窗口内的**时间戳**。对于每个有效**时间戳**，它将相应的命中次数添加到运行总计中，然后返回。
  unordered_map 的查找和插入通常是 O(1) 操作，这使得命中计数和检索过程非常高效。
• 清理旧命中
  cleanUp(int windowSizeSeconds) 方法负责移除超出指定**时间**窗口的旧命中。此方法对于处理内存使用至关重要，因为它可防止 unordered_map 和 vector 无限增长。
  该方法计算到期**时间**，这是**根据**当前**时间**和所需窗口长度应保留的最早**时间戳**。然后，它遍历有序**时间戳**的 vector。如果发现一个早于到期**时间**的**时间戳**，则将其从 vector 中移除，并从 unordered_map 中删除相应的条目。
  此过程确保只有在所需**时间**窗口内的有效**时间戳**才会被保留在内存中，从而优化了**空间**和性能。
• 实用函数
  此实现使用了两个实用函数
  int getCurrentTimestamp()：此函数返回自纪元（Unix **时间**）以来的当前**时间**（以秒为单位）。它用于获取当前**时间戳**以记录命中或计算近期**时间**窗口内的命中次数。
  int roundToSecond(int timestamp)：尽管存在此函数，但此实现主要将**时间戳**原样返回，因为**时间戳**已为秒。如果需要不同的粒度（例如毫秒），则可以扩展或修改此函数。
• 主函数
  main() 函数演示了如何在实践中**使用**HitCounter 类。它模拟了一系列在特定**时间戳**的命中，然后检索了不同**时间**窗口内的命中次数。它还演示了如何清理旧命中以保持高效的内存使用。
  模拟命中：调用 hit() 方法在不同的**时间戳**记录命中，从而在多个**时间**点模拟命中。这会使用多个条目设置 unordered_map 和 vector。
  检索命中：getHitsInLast() 方法使用不同的窗口**大**小和**时间戳**来检索指定**时间**窗口内的命中次数。这演示了命中计数器如何用于跟踪不同**时间**段的命中。
  清理：调用 cleanUp() 方法以移除超出特定**时间**窗口的旧命中。这说明了 HitCounter 类的内存管理能力。

复杂度分析

时间复杂度

记录一次命中（hit(int timestamp))

插入到 unordered_map：由于哈希表实现，在 std::unordered_map 中插入或更新值通常在平均情况下为 O(1)。哈希函数将元素均匀分布在桶中，从而在大多数情况下提供恒定的访问**时间**。

插入到 vector：附加到 std::vector 是平均 O(1) 操作，因为它只是将元素添加到末尾。但是，如果 vector 需要重新调整**大**小（当 vector 的容量超出时发生），则操作会迅速变为 O(n)，其中 n 是 vector 的当前**大**。但这种重**大**调整是偶尔发生的，因此平均**时间**仍为 O(1)。

总**时间复杂度**：平均 O(1)。

检索命中次数（getHitsInLast(int windowSizeSeconds, int timestamp))

遍历 unordered_map：该函数需要遍历 unordered_map 中的条目，以对指定**时间**窗口内的命中次数求和。迭代次数取决于映射的**大**，在最坏情况下最多为 O(n)，其中 n 是存储的唯一**时间戳**的数量。

在实践中，如果**时间**窗口很小或唯一**时间戳**的数量有限，则迭代次数可能要少得多。

总**时间复杂度**：最坏情况为 O(n)。

清理旧命中（cleanUp(int windowSizeSeconds))

迭代和从 vector 中删除：该方法遍历 vector 以移除过时的**时间戳**。从 std::vector 的**前端**删除元素对于每个元素来说都是 O(1) 操作，但平均**时间复杂度**可能是O(k)，其中 k 是要删除的元素数量。

从 unordered_map 中删除：从 unordered_map 中删除每个元素平均为 O(1)。

总**时间复杂度**：O(1)，其中 k 是已删除元素的数量。

空间复杂度

unordered_map<int, int>

unordered_map 的**空间复杂度**为O(n)，其中 n 是存储的唯一**时间戳**的数量。映射中的每个条目都存储一个**时间戳**（键）和相应的命中次数（值）。

Vector<int>

vector 的**空间复杂度**同样为O(n)，其中 n 是存储的唯一**时间戳**的数量。vector 按记录顺序存储每个**时间戳**。

总**空间复杂度**：O(n) 用于存储命中，其中 n 是正在跟踪的当前**时间**窗口内唯一**时间戳**的数量。unordered_map 和 vector 使用的内存量随唯一**时间戳**的数量呈线性增长。

命中计数器设计的优点

实时流量监控

命中计数器对于实时监控网站流量至关重要。它使网站管理员和开发人员能够跟踪访问网站的用户数量、访问**时间**以及哪些页面获得的流量最大。

这些实时数据对于理解用户参与度和行为模式非常有价值。例如，如果观察到流量突然激增，可能表明某个内容已获得病毒式传播，需要立即关注以确保服务器能够处理增加的负载。

性能分析和优化

分析命中计数器收集的数据使开发人员能够识别流量高峰**时间**并了解网站在不同负载条件下的性能。通过了解大多数用户何时活跃，管理员可以优化服务器资源，以确保网站保持响应迅速和快速。

这对于高流量网站尤其重要，因为性能问题可能导致用户体验不佳和收入损失。此外，数据还可以指导缓存策略、负载均衡和其他性能优化技术的实施。

安全监控和威胁检测

命中计数器可以通过帮助检测异常流量模式在安全监控中发挥关键作用。例如，命中次数的突然、无法解释的增加可能表示分布式拒绝服务 (DDoS) 攻击。通过监控和分析流量数据，管理员可以设置触发警报或自动防御的阈值，以应对异常模式。这种主动的安全方法有助于在潜在威胁造成重大损害之前保护网站。

数据驱动的业务决策

从命中计数器获得的见解可以直接影响业务决策。例如，通过分析访问次数最多的页面，企业可以识别热门产品或服务，并相应地调整其营销策略。此外，了解随**时间**的用户交互有助于企业评估新功能或活动的效果，从而做出更明智的决策。这种数据驱动的方法确保业务策略与用户兴趣和行为保持一致，从而取得更有效的结果。

结论

总之，命中计数器不仅仅是一个简单的页面访问计数工具。它作为 Web 应用程序的关键组成部分，提供对流量监控、性能优化、安全、业务决策和用户体验增强至关重要的见解。实施设计良好的命中计数器（尤其是利用 unordered_map 和 deque 等高效数据结构）的好处远远超出了基本跟踪。这样的系统提供了管理现代 Web 流量所需的**可扩展性、灵活性和效率。