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

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

编辑：我假设这个问题不是关于“现在有多少用户活跃”的实时答案，而是关于历史值——下午3:25有多少用户处于活跃状态。我将保持旧解决方案低于新解决方案：

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

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

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

另一个问题的前一个答案是：鉴于没有那么多分钟（每天1440分钟），我会为每场比赛创建一个向量，每分钟有一个时段。

查看日志文件，为每一行获取时间，将其四舍五入到最接近的分钟，并在数组中的适当位置添加1。完成后，您将准确知道每场比赛每分钟有多少活跃用户。

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

要支持多个游戏，只需使用哈希将游戏名称映射到其矢量即可。

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

Answer 2

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

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

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

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

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

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

Answer 3

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

概述

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

细节

首先，选择一个可接受的时间分辨率。在这个例子中，我选择了15秒的间隔。

维护五个PingInterval数据结构来表示其中的五个时间间隔(跨越1分钟以上的时间间隔)。PingInterval包含一个属性:计数器。这些PingIntervals在PingMonitor中维护。每次玩家pings时，在PingMonitor中更新一个映射，将每个玩家映射到当前时间间隔。当您执行这个映射时，采取以下步骤，这些步骤将计数保持在PingIntervals内(根据我在概述部分描述的特征)。

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

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

  当您想要查询活动用户的数量时，请计算最后五个间隔时间间隔的经过时间加权和。例如，如果距离当前时间间隔只有5秒（意味着该间隔的下10秒尚未发生），则计算该值：2/3*4个最新间隔的最旧间隔总和。

  其他想法

  五个间隔非常保守；我们可以大幅增加数字以获得更高的精度（可能是每秒一次），这仍然可以为我们节省大量成本。重要的是，我们的时间现在是离散的时间间隔。这意味着当我们统计活跃用户的数量时，我们不必每次都查看（这等于用户的数量）；相反，我们可以查看预定义的x个时间段。