5

在 cs.stackexchange 上问过这个问题.. 投了反对票.. 因为我不是很清楚.. 所以我会在这里尝试更具体..

Q - 设计一个数据结构来返回最近 1 分钟内 Web 服务器的连接数。

假设 -

  1. 服务器有大量传入连接..如印度铁路预订或社交网络网站等。
  2. 假设这是一个大数据问题..那么我有基础设施来运行大数据作业..

我在寻找：

  1. 效率 - 是否可以在 O(1) 中做到这一点？如果，比如说，我们在 O(n) 中进行。问题是，如果需要 N 毫秒来计算答案。有更多的连接在 N 毫秒中排队。我应该如何解决这个问题。 . 或者我只能忽略小的延迟和 O(n) 是一个好的表现

  2. 推理/方法 - 我们是否在生产中的无数部署中做类似的事情？有没有类似的问题..？

  3. 这是“大数据”吗？最后 N（N 为 10）分钟内存储连接的数据是大数据问题吗？

我的努力：我知道——

  1. 与 Web 服务器的连接在被线程服务之前被放入队列中
  2. 每个连接都有一个时间戳

方法 -

  1. 将连接放入队列后，立即将其写入文件..（至少它的时间戳和连接的句柄/唯一标识符）
  2. 一旦客户端请求“在过去 1 分钟内给我 num 个连接” .. 处理文件以找出连接数 .. 我们知道当前时间（以毫秒为单位），并且我们必须找到时间戳落在 currentTime 中的连接 - 60 秒
  3. 可以使用 map reduce 运行此作业。我还知道该文件已对数据进行了排序（按时间戳）。

我还运行一个守护进程，它删除超过 10 分钟的条目/文件.. 这样我就不会存储不需要的数据

4

1 回答 1

12

排队方式

  • 使用队列。

  • 每当有新请求出现时，就将其排入队列。

  • 每当我们需要获取最后一分钟的请求数时，首先将所有发生时间超过一分钟的条目出列（这是因为队列中的条目是按顺序插入的，因此队列是排序的）。然后返回队列的大小（可以O(1)通过存储这个变量来返回大小）。

  • 由于您说每秒有很多请求，因此您也可以在收到新请求时将旧条目出列，这应该使队列接近正确的大小，从而最大限度地减少计数操作所花费的时间。

    这将O(k)适用于入队和获取计数，其中k是在任何长度的时间段内发生的最大请求数t，其中t是任何两个请求之间的最大持续时间（例如，如果我们在以下毫秒获得请求：1,2,3,5,15,20，最大持续时间是20-15 = 5，以5毫秒为单位发生的最大请求数是4（即1,2,3,5发生在周期内1-5））。

  • 另一种方法是运行一个计时器，它可以使旧条目出列。

    这将O(1)用于排队和O(m)计时器运行和获取计数，其中m是等于计时器频率的任何长度周期的最大请求数。例如，1,2,3,5,15,20再次使用，计时器间隔为6毫秒。以毫秒为单位发生的最大请求数6将是4（即1,2,3,5发生在 period 内1-6）。

这是“大数据”吗？

好吧，这实际上取决于您每秒收到的请求数。我们通常会谈论许多 TB 的大数据数据（并且随着计算机变得更强大而增加），我认为只有在最后一分钟的请求才会接近这些数字。

基于计数的方法

如果您对一个小错误感到满意，您可以执行以下操作：

有一个固定大小的队列（比如说 60，每个元素表示给定秒的请求 - 是一个简单的整数值）。这可以实现为循环数组。

let count= 表示最后一秒请求数的变量，初始化为0。

有一个变量存储最后一个请求的第二个值（以便能够确定队列中的元素用于哪一秒）。

当我们收到一个新请求时，将所有指示比一分钟前的秒数长的元素出列，count按出列值递减，并随着count.

当我们需要获取最后一秒的请求数时，将所有指示秒数超过一分钟前的元素出列count，并按出列值递减，然后返回count。

鉴于我们的队列是固定大小的，每个操作最多会占用O(1)（或者，如果您愿意，队列的大小在O(m)哪里）。m

这会给你最多 1 秒的错误。你当然可以玩弄这个错误。例如，如果你想要一个半秒的错误，只需将队列的大小加倍，然后每半秒转到下一个元素。

于 2013-08-23T07:10:48.003 回答