一种用于查询不同时间间隔内事件数量的数据结构

Question

我的程序在一秒钟内接收来自不同类型的数千个事件。例如，拥有数百万不同IP地址的用户可以在一秒钟内访问100k API。我想保持统计数据，并限制1分钟、1小时、1天等时间内的访问次数。所以我需要每个用户在最后一分钟、一小时或一天内的事件计数，我希望它像一个滑动窗口。在这种情况下，事件类型是用户地址。

我开始使用时间序列数据库，流入数据库;但它未能每秒插入100k个事件，并且聚合查询以在一分钟或一小时内查找事件计数甚至更糟。我确信InfluxDB无法每秒插入100k事件并同时执行300k聚合查询。

我不想从数据库中检索事件，因为它们只是一个简单的地址。我只想在不同的时间间隔里，尽可能快地数出来。我想获得特定时间间隔(例如，过去1小时)内x类型事件的数量。

我不需要将统计数据存储在硬盘中；所以也许一个在不同时间间隔内保持事件计数的数据结构对我来说是好的。另一方面，我需要它像一个滑动窗口。

我想到的另一个解决方案是将RAM中的所有事件存储在一个链表中，并对其进行迭代以回答查询，但是因为事件的数量太多，所以将所有事件保存在RAM中不是一个好主意。

是否有任何良好的数据结构甚至数据库用于此目的？

Answer 1

您可以考虑用hazelcast集群代替简单的ram。我也认为灰色或简单的弹性搜索，但有了这种负载，你应该测试一下。你也可以考虑你的数据结构。您可以为每个地址构建一个小时图，并将事件放入小时桶中。当时间过了一个小时，您可以计算这个小时的存储桶中的计数和缓存。当您需要一个分钟粒度时，您可以转到小时桶，并在该小时列表下统计事件。

Answer 2

关于事件输入格式以及如何将事件传递到统计后端，您没有提供足够的详细信息：它是udp消息流、http put/post请求还是smth else。

一种可能的解决方案是使用Yandex Clickhouse数据库。建议模式的粗略描述：

1. 使用缓冲区存储引擎将来自应用程序的传入原始事件加载到基于内存的表中事件
2. 在另一个基于内存的表中创建具有每分钟聚合的具体化视图 事件每分钟使用缓冲区引擎
3. 对事件“每小时”中每小时聚合的数据执行相同的操作
4. （可选）将Grafana与点击式数据源插件结合使用来构建仪表板

在Clickhouse中，与任何磁盘表无关的DB缓冲区存储引擎将完全保留在内存中，较旧的数据将自动替换为新数据。这将为您提供原始数据的简单内务管理。

如果您想在磁盘上保留统计信息，还可以使用MergeTree存储引擎创建表（物化视图）EventsPerMinute和EventsPerHour。Clickhouse可以轻松处理数十亿条记录。

在每秒 100K 个事件时，您可能需要在数据库前面安装某种整形器/负载平衡器。