3

我在一次采访中被问到这个问题。细节是假设我们收到数百万个事件。每个事件都有一个时间戳和其他详细信息。系统设计要求最终用户能够查询最近 10 分钟或 9 小时或可能是 3 个月内最频繁的记录。

事件可以看如下

event_type: {CRUD + Search}
event_info: xxx
timestamp : ts...
4

2 回答 2

4

弄清楚这一点的最简单方法是查看其他流处理或 map reduce 库是如何做到这一点的（我感觉你的面试官已经看过这些库）。它基本上是实时地图减少（您也可以查找它是如何工作的）。

我将概述两种事件处理技术。实际上，大多数公司都需要两者兼得。

新学校流处理（实时）

让我们暂时假设他们不想要实际事件，而是更可能的聚合情况（我认为这是您问题的意图）

一个示例流处理项目是pipelinedb（他们在主页底部有它的工作原理）。

  1. 事件进入队列/环形缓冲区
  2. 工作进程分批读取这些事件并将它们汇总到部分存储桶或窗口中。
  3. 最后是组合器或减速器，它采用微批次并实际进行更新。一个例子是事件计数。因为我们使用的是来自上述事件的队列，所以根据队列，我们​​可能会有多个消费者来执行组合操作。

因此，如果您想要分钟计数，您将每分钟进行汇总，并且只存储该分钟的事件总和。事实证明，这在空间上相当小，因此您可以将其存储在内存中。

如果您想要这些月或日甚至年的计数，您只需将所有分钟计数桶相加即可。

现在，这种技术当然存在一个主要问题。您需要先验地知道要收集哪些聚合和枢轴。

但是您可以非常快速地查找结果。

老派数据仓库（分区）和 Map Reduce（批处理）

现在让我们假设他们确实想要某个时间段的实际事件。这很昂贵，因为如果将所有事件存储在一个地方，查找和检索就很困难。但是，如果您使用时间是分层的这一事实，您可以将事件存储在元组树中。

您想要实际事件的原因是因为您正在进行临时查询并且愿意等待查询执行。

  1. 您需要某种队列来处理事件流。
  2. 工作人员读取队列并根据时间对事件进行分区。例如，您将在某一天有一个分区。这类似于分片。许多存储系统都支持这一点（例如 postgres 分区）。
  3. 当您想要在一段时间内发生一定数量的事件时，您可以合并分区。
  4. 分区本质上是分层的（分钟 < 小时 < 天等），这意味着您可以对它们进行树状操作。

有一些方法可以存储称为时间序列数据的此类事件，以便分区索引是自动且快速的。这些被称为TSDB，您可以通过 google 获取更多信息。

一个示例 TSDB 产品将是 influxdb。

现在回到时间（或至少人类如何表示时间）是有组织的树的事实，我们可以执行并行化操作。这是因为树是 DAG（有向无环图）。使用 DAG，您可以进行一些分析并基本上对分支进行递归操作（也称为 fork/join）。

一个示例通用并行存储产品将是 citusdb。

当然，这种方法有一个巨大的缺点。它是昂贵的！即使您通过增加节点数量来加快速度，您也必须为这些节点（分布式分片）付费。理论上，性能应该线性扩展，但实际上这不会发生（我会为您保存细节）。

于 2017-05-25T19:20:51.667 回答
3

我认为您需要将数据持久保存到磁盘

  • 查询持续时间非常模糊，并且由于某些不可预见的情况（例如进程终止，机器故障等），数据可能会丢失。

  • 由于内存限制（数百万个事件），您无法将所有事件都保存在内存中

我建议使用 mysql 作为数据存储，并将时间戳作为索引键之一。但是两个事件可能具有相同的时间戳。因此，使用自动增量 id + 时间戳创建一个复合索引键。

Mysql的优点：

  • 超可靠的复制
  • 支持各种CRUD操作和查询

在每个查询中，您基本上可以根据需要获取时间戳的范围。

  • 先数数。满足查询的事件。 

    select count(*) from `events` where timestamp >= x and timestamp <=y.

  • 如果满足查询的事件过多，则分批查询。

     select * from 'events' where timestamp >= x and timestamp <=y limit 1000 offset 0; 
 select * from 'events' where timestamp >= x and timestamp <=y limit 1000 offset 1000;

    依此类推..直到偏移量<=匹配第一个查询的事件计数。

于 2017-05-25T19:20:42.567 回答