实时显示一个时间段内最常见/最重复的元素

Question

我有用户生成的字符串以未定义的速率传入，其中一些是重复的数据，我希望在给定的固定时间周期(例如，在最后一个小时)中，在Go.中实时地计数前20位最常见的重复字符串。

唯一字符串的数量是不受任何限制的，因此，为了避免DoS，数据结构可能必须有最多元素的定义大小(例如，top-10k-元素和/或1MB的整体大小)，如果它们还没有任何重复项，则删除最近插入最少的元素(但永远不要删除任何新传入的元素！)。

我的理解是，这正是ngx_http_limit_req_module.c是实施的方式，这个方法在文档中被称为“漏桶”，然而，维基百科页面似乎表明，将从队列中删除的是新数据，而不是旧数据，因此，不确定这个概念是否适用。

无论如何，我尝试在Golang中寻找一个“漏桶”实现，到目前为止，我发现的最流行的结果是uber-go/ratelimit，它的API似乎根本不适合我的问题陈述-它只是实现了一些实际的速率限制队列，而不是在最后一个Y计数的实时顶部X。

有人能建议我想要的东西的正确名称吗，以及实现这个目标的最佳方法，最好是在Go？

Answer 1

这是两个问题。

1. 记录你选择要记录的名字。
2. 注意到没有出现在列表中的趋势名称。

对于第一个问题，我建议按名称，每分钟跟踪有多少。当它们结束时，将它们添加到一个正在运行的总数中，并将它们添加到一个队列中，以便在一小时内将其减去。这为您提供了60个每个名称的小对象，并且在运行的基础上，您将保持一个散列。

第二个问题更具挑战性。为此，我会使用概率方法。这样做的想法是，每个名称都使用唯一的id进行散列，并且您只保留了所看到的1000个最小的散列值(以及相关的名称)。(我马上给出一个算法。)您的散列值应该在最大的2^64之间均匀分布，与名称无关，所以常见的名称最终会出现在这个列表中。当他们这么做的时候，你就开始数他们！(你将失去最初的几个，但随着更多的工作，你可以估计有多少你错过了。这个优化可能比它更有价值。)

现在，我们如何保持千最小的哈希值？您可以使用优先级队列，该队列通常用堆来实现，以创建一个可更新的数据结构，在该结构中很容易提取最大的哈希值。所以你运行下面的伪代码。

create your priority queue of (hash, name)
for each name:
   hash hash of name and unique new id
   entry = (hash, name)
   if queue size < 1000:
       insert entry
   else if hash is smaller than the current max in the queue
      insert entry
      remove the largest entry