java - 构建自定义过滤器以在每个标识符的 M 个时间单位内处理 N 个请求

Question

我正在尝试构建一个自定义过滤器，它只处理每个标识符每 M 个时间单位(比如 1 秒)的 N 个请求(比如 100 个)。所有大于 N 的请求都将被拒绝或忽略。 Request 是一个包含标识符、时间戳和其他卫星数据的对象(过滤器不应处理卫星数据)。

首先想到的是有一个 ConcurrentHashMap[String, AtomicInteger] ，它会有每个标识符的请求数，但后来我无法理解使用哪个数据结构来跟踪每秒的这些计数，这个数据结构也应该是能够清理，因为它很快就会增长，我们不需要维护过去的数据。

这也意味着一个可能的解决方案将具有一种数据结构，该结构能够仅存储时间戳之间的增量，并确保每个标识符在 M 个时间单位内不超过 N 个请求。

这听起来像是一个速率限制器，可能有可用的标准库或选项，但我想了解如何构建它因此寻找一些指针而不是直接代码解决方案。

Answer 1

这是一种方法。

以 (time_rounded_off, count) 形式存储值.只有在 time_rounded_off = current_time_rounded_off 时才处理请求和 count < max_count .

当舍入时间增加时，计数器将重置为 0，您将重新开始处理。

这种设计有利于保持业务规则，但如果在您的基础架构上处理突然爆发的请求过于困难，则效果不佳。为此，我建议您保留一个 exponential moving average您正在处理多少请求/秒。只要下降到足够低，您就可以接受另一个请求。

使用这种方法，您的值将是 (timestamp, average) 形式的对.现在更新它的过程就是将时间戳更新为当前时间戳，然后用平均值乘以一个衰减因子(取决于时间戳的不同)。如果您收到请求的速度快于它处理的速度，结果将是以正确的近似速率对它们进行采样。

您现在可以使用两个参数，衰减率和平均值。您可以为特定速率选择是指每小时 360,000 次、每分钟 6000 次、每秒 100 次还是每 0.1 秒 10 次。它们之间的区别在于您必须一次处理的“突发”的潜在大小。