用于流数据的数据结构

Question

您应该使用哪种数据结构，以便您的服务器能够告诉您在任何时间点上一小时内处理的请求数？

例如，在10:20:23你询问处理了多少个请求;它必须告诉你从9:20:23到现在的总数。同样，在10:00时，它必须从9:00告诉你总数。

Answer 1

一种选择是将所有数据存储在按时间排序的标准动态数组中。每当有传入的请求时，都会将其附加到数组的末尾。

要查看过去一小时内发生了多少次请求，可以对数组执行二进制搜索，以查找小时内发生的第一次请求。比较这个数组元素的索引和元素的总数会给你在那个时间窗口中的总请求数。

为了防止数组变得太大，一种选择是将数组视为越来越多的环形缓冲区。每当数组中的空间用尽时，对数组中的第一个元素进行二进制搜索，在过去一小时内发生。之前的所有元素都可以被丢弃。如果将阵列存储为环形缓冲区，则可以通过调整开始位置以从逻辑上将其从缓冲区中删除，从而有效地在O（1）时间内删除所有这些元素。如果您仍然需要更多的空间，那么您可以将环形缓冲区的大小加倍并复制旧的元素。如果你强制执行一个策略，如果在丢弃旧元素（比如75％）之后填充的缓冲区中有多个不变的部分被填满，则总是复制所有内容，然后这需要每插入一次O（1）次。

简而言之，您可以获得O（1）插入和O（log n）最近一次查询过去一小时内有多少请求的最坏情况查找。

希望这会有所帮助！