专柜要求
我想实现一个特殊的计数器:所有增量操作在固定时间段(比如 30 天)后超时。
一个例子:
- 第 0 天:计数器 = 0。TTL = 30 天
- 第 1 天:递增计数器 (+1)
- 第 2 天:递增计数器 (+1)
- 第 3 天:计数器的值 == 2
- 第 31 天:计数器的值 == 1
- 第 32 天:计数器的值 == 0
天真的解决方案
一个天真的实现是维护一组时间戳，其中每个时间戳等于增量的时间。计数器的值等于集合减去所有超时的时间戳后的大小。
这个朴素的计数器有 O(n) 空间(集合的大小)，有 O(n) 查找和 O(1) 插入。这些值是准确的。
更好的解决方案(对我来说)
交易速度和内存力确保准确性。
我想要一个具有 O(1) 查找和插入、O(1) 空间的计数器。准确度 < 准确。
或者，我会接受 O(log n) 空间和查找。
计数器表示应适合存储在数据库字段中，即，我应该能够快速更新和轮询计数器，而无需太多(反)序列化开销。
我本质上是在寻找一个类似于 HyperLogLog 计数器的计数器，但用于不同类型的近似计数:递减增量与不同元素的数量
我怎样才能实现这样的计数器？
最佳答案
如果您可以接受 24 小时粒度，那么您可以将计数器分到 k 个桶中，其中 k 是最长 TTL 中的天数。
递增是一个复杂度为 O(1) 的操作 - 只需递增具有索引 (k-TTL) 的存储桶中的值，以及当前总和。
读取是另一个 O(1) 操作，因为您只需读取当前总和。
每晚都会有一个 cronjob 从现在过期的桶中弹出(并在另一端添加一个值为 0 的桶)，并将您的计数器减少该桶中的总和(这是一个后台任务，因此它不会影响您的插入或读取操作)
关于algorithm - 如何实现随时间衰减的计数器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42295046/