在最近一分钟内计算活跃用户的最快/最简单的方法是什么

Question

您在Zynga工作，想要计算不同游戏的当前活跃玩家数量。您的 Web 服务器处理来自许多不同游戏的 ping，每个用户都有一个唯一的 GUID。必须能够一次查询一个游戏的活动用户数。活跃用户是指在最后一分钟被ping的用户。

日志行连续进入 Web 服务器：

10.1.12.13 - - "http://zynga.com/ping?guid=<guid>&game=<gameID>" -

计算活跃用户的最快/最简单的方法是什么？请建议一个45分钟的答案和一些代码。

---

我的版本

// web server interface, every time ping comes in count() will be called
// void count(String gameId, String guid)
// int getNumberActivePlayers(String gameId)
struct Record{
  String gameID;
  String guid;
};
class PingStorage{
private:
  max_heap<long, Record> storage;
public:
  //    O(log(n))
  //  n = total number of elements in storage
  void count(String gameId, String guid){
    long currentTimeStamp = getUnixTimeStamp();
    Record rec ;
    rec.gameId = gameId;
    rec.guid = guid;
    storage.add(currentTimeStamp, rec);
  }
  //N = numner of records in last ,minutes in storage
  //O(N)
  int getNumberActivePlayers(String gameId){
    map<String, Set<string> > game2user;
    long tillTimeStamp = getUnixTimeStampNow() - 60;
    while(true){
      pair<long, Record> rec = storage.getMax(); //O(1)
      if(rec.first <= tillTimeStamp) break;  
      Set<String> temp = game2user[rec.gameid]; //O(1)
      temp.add(rec.userid); //O(log(N)) - O(1)
    }
    return game2user[gameID].size();
  }
};

Answer 1

假设这是一个实时解决方案，您可以在 O（1） 中处理 ping 请求，在 O（1） 中生成当前玩家统计信息，并通过牺牲一些准确性来使用 O（num_player） 空间。关键是离散时序。

概述

基本思想是将离散时间间隔表示为对象，并在这些对象中存储以下属性：在此时间间隔内 ping 但此后未执行 ping 操作的不同玩家的数量。 若要查询活动用户数，请计算构成最后一分钟的最近 x 时间间隔的加权和。

详

首先，选择可接受的时间分辨率。 在此示例中，我选择 15 秒间隔。

维护五个 PingInterval 数据结构来表示其中的五个间隔（跨越的间隔比 1 分钟多 1 个）。 PingInterval 包含一个属性：计数器。 这些 PingIntervals 在 PingMonitor 中维护。 每次玩家 ping 时，更新 PingMonitor 中的地图，将每个玩家映射到当前时间间隔。 执行此映射时，请执行以下步骤，这些步骤将计数保持在 PingIntervals 内（根据我在概述部分中描述的特征）。

• 如果玩家已映射到间隔，并且它是当前间隔，则不执行任何操作。
• 否则，如果玩家映射到的间隔不是当前间隔，
  • 减少旧间隔的计数，
  • 增加当前间隔的计数，
  • 并将该玩家映射到该间隔。
• 否则，如果播放器根本没有映射到间隔，
  • 增加当前间隔的计数，
  • 将播放器映射到当前间隔。

（如果表示当前时间的 PingInterval 尚不存在，请将最早的 PingInterval 设置为 null，以线程安全的方式创建新的 PingInterval，然后照常继续。

如果要查询活动用户数，请计算过去五个时间间隔的时间加权和。 例如，如果当前时间间隔仅 5 秒（意味着该时间间隔的下一个 10 秒尚未发生），请计算此值：2/3 * 最早间隔 + 4 个最新间隔的总和。

其他想法

五个间隔是非常保守的;我们可以大大扩展数字以获得更高的准确性（也许每秒一个），它仍然可以为我们提供显着的节省。 重要的是，我们的时间现在是离散的间隔。 这意味着当我们去计算活跃用户的数量时，我们不必查看每个单独的时间（等于用户数量）;相反，我们可以查看我们预定义的 X 个时间箱。

Answer 2

我的方法是使用一个双端（在本文的其余部分称为队列），将所有 GUID 推送到观察到的 GUID，即按年龄排序。此外，我将使用哈希映射，其中包含指向队列中存在的任何 GUID 条目的指针。

将新的 GUID 推送到队列时，将在哈希映射中查找旧条目（如果有），从队列中删除，并将新条目分配给哈希映射。

随着时间的推移，队列中超过年龄阈值的所有条目都将被弹出（并从哈希图中删除）。

队列

的长度（即活动用户数）可以作为单独的变量进行跟踪，以避免在每个查询中跳转队列。

要支持多个游戏，只需为每个游戏ID添加这样的结构。

复杂性：O（1） 插入/删除观察（给定完美哈希，即没有冲突），O（1） 查询，O（n） 空间。

Answer 3

编辑

：我认为这个问题不是关于获得"现在有多少用户活跃"这个问题的实时答案，而是获取历史值 - 有多少用户在下午3：25活跃。我将旧解决方案保留在新解决方案下方：

所以，你想知道现在有多少用户处于活动状态，为每个游戏保持队列。每当您看到新的日志条目时，请找出它属于哪个游戏，并将其添加到游戏的队列中。每次添加后，清理队列开头的旧条目（清理时超过 1 分钟的所有条目）。

当询问游戏中的活动用户数时，对游戏的队列执行相同的清理，并返回队列的深度。

保留一个将游戏映射到队列的哈希值，你得到了一个 O（N） 操作，N 是日志中的行数 - 每行最多处理两次 - 一次用于添加它，一次用于删除它。您还可以在每次添加和查找时进行额外的比较（当确定队列条目不够旧时），但这是恒定时间乘以 N。所以 O（N） 在总共。

对另一个问题的先前回答：看到没有那么多分钟（每天 1440 分钟），我会为每个游戏创建一个向量，每分钟都有一个插槽。

遍历日志文件，对于每一行获取时间，将其四舍五入到最接近的分钟数，并将 1 添加到数组中的相应插槽中。完成后，您将确切地知道每场比赛每分钟有多少活跃用户。

复杂度 - O（N），其中 N 是日志文件中的行数。

要支持多个游戏，只需使用哈希从游戏名称映射到其向量。

现在，这假设您只检查整分钟边界（1：00：00、1：01：00 等）的活动用户。无论如何，这可能是您需要做的。

Answer 4

这将是我的答案序列：

1. 何苦？最简单的方法是每分钟计算有多少用户处于活动状态。知道这些还不够吗？
2. 如果你真的关心最新的信息，让我们逐秒计数（如Cheeken所描述的）。这将精确到几分之一秒。
3. 好吧，如果实时准确性是"必要的"，并且您想就数据结构采访我，那么让我们使用按上次活动时间评分的一堆客户（如尤达大师所述）。
4. 如果需要实时准确性，并且我们要在生产中执行此操作，那么让我们使用数据结构服务器 Redis。我们维护一组按上次活动时间评分的客户。我们可以使用 zcount 命令查询在最后一分钟或最后一小时内有多少客户处于活动状态。这是有用且可靠的。