Каков самый быстрый/простой способ подсчета активных пользователей за последнюю минуту?

Вы работаете в Zynga и хотите подсчитать количество активных игроков в настоящее время для разных игр. Ваш веб-сервер обрабатывает пинги из разных игр, и каждый пользователь имеет уникальный идентификатор GUID. Должна иметь возможность запрашивать количество активных пользователей за одну игру за раз. Активными пользователями являются те, кто получил ping в последнюю минуту.

Строки журнала поступают непрерывно на веб-сервер:

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();
  }
};

Ответы

Ответ 1

Предполагая, что это решение в реальном времени, вы можете обрабатывать запросы ping в O (1), генерировать текущую статистику игрока в O (1) и использовать пространство O (num_player), жертвуя некоторой точностью. Ключ должен дискретировать тайминги.

Обзор

Основная идея состоит в том, чтобы представлять дискретные временные интервалы в качестве объектов и хранить в этих объектах следующее свойство: количество отдельных игроков, которые пинговали в течение этого интервала времени, которые не были отсканированы. Чтобы запросить количество активных пользователей, вычислите взвешенную сумму последних х временных интервалов, которые составляют последнюю минуту.

Подробнее

Сначала выберите приемлемое временное разрешение. В этом примере я выбираю 15-секундные интервалы.

Поддерживайте пять структур данных PingInterval, чтобы представить пять из этих интервалов (охватывая еще 1 интервал, чем 1 минуту). PingInterval содержит одно свойство: счетчик. Эти PingIntervals поддерживаются в PingMonitor. Каждый раз, когда игрок пингует, обновляйте карту в PingMonitor, которая отображает каждого игрока на текущий временной интервал. Когда вы выполняете это сопоставление, выполните следующие шаги, которые поддерживают подсчеты в пределах PingIntervals (в соответствии с характеристиками, описанными в разделе обзора).

Если игрок уже отображен на интервал и является текущим интервалом, ничего не делайте.
Иначе, если игрок сопоставляется с интервалом, который не является текущим интервалом,
- уменьшает счетчик старых интервалов,
- увеличить счетчик текущих интервалов,
- и сопоставьте этого игрока с этим интервалом.
Иначе, если игрок не отображен на интервал вообще,
- увеличить счетчик текущих интервалов,
- сопоставить плеер с текущим интервалом.

(Если PingInterval для представления текущего времени еще не существует, установите самый старый PingInterval равным null, создайте новый PingInterval поточно-безопасным способом, а затем продолжите как обычно.)

Если вы хотите запросить количество активных пользователей, вычислите взвешенную по времени сумму последних пяти интервалов времени. Например, если вы находитесь всего на 5 секунд в текущем временном интервале (что означает, что следующие 10 секунд этого интервала еще не были выполнены), вычислите это значение: 2/3 * самый старый интервал + сумма из четырех последних интервалов.

Другие мысли

Пять интервалов очень консервативны; мы могли бы увеличить число значительно для большей точности (возможно, один раз в секунду), и это все равно позволит нам значительно сэкономить. Важная часть состоит в том, что наши времена теперь являются дискретными интервалами. Это означает, что, когда мы переходим к подсчету числа активных пользователей, нам не нужно смотреть на каждое индивидуальное время (равное количеству пользователей); вместо этого мы можем посмотреть на х бит времени, которые мы предопределили.

Ответ 2

Мой подход состоял бы в том, чтобы использовать deque (называемый очередью в остальной части этого сообщения), чтобы все GUID были нажаты на это, что наблюдается, т.е. таким образом упорядочивается по возрасту. Кроме того, я бы использовал hashmap, содержащий указатели на записи любого GUID, присутствующего в очереди.

Когда новый GUID помещается в очередь, старая запись (если она есть) будет просматриваться в hashmap, удалена из очереди, а новая назначается вместо этого в hashmap.

По прошествии времени все записи в очереди, которые превышают порог возраста, будут выведены (и удалены из хэш-карты).

Длина очереди (число активных пользователей a.k.a.) может отслеживаться как отдельная переменная, чтобы избежать перескока через очередь для каждого запроса.

Для поддержки нескольких игр просто добавьте такую структуру для каждого идентификатора игры.

Сложность: O (1) вставка/удаление наблюдений (с учетом идеального хэша, т.е. никаких столкновений), O (1) запрос, O (n) пространство.

Ответ 3

EDIT: Я полагаю, что этот вопрос касался не получения ответа в реальном времени на вопрос "сколько пользователей сейчас активен", а скорее получение исторических значений - сколько пользователей было активным в 15:25. Я сохраняю прежнее решение ниже нового:

Итак, вы хотите знать, сколько пользователей сейчас активны, сохраняйте очередь за игру. Всякий раз, когда вы видите новую запись в журнале, узнайте, к какой игре она принадлежит, и добавьте ее в очередь игры. После каждого добавления очистка старых записей в начале очереди (все записи старше 1 минуты на момент очистки).

Когда вас попросят количество активных пользователей в игре, выполните ту же самую очистку в очереди игры и верните глубину очереди.

Держите хэш, сопоставляя игры с очередями, и вы получили операцию O (N), где N - количество строк в журнале - каждая строка обрабатывается не более двух раз - один раз для ее добавления, один раз для ее удаления, Вы также делаете дополнительное сравнение для добавления и поиска (при принятии решения о записи в очередь не достаточно старо), но это постоянное время времени N. So O (N) во всех.

Предыдущий ответ на этот другой вопрос: Увидев, что не так много минут (1440 в день), я бы создал вектор для каждой игры с слотом для каждой минуты.

Перейдите по файлу журнала, чтобы каждая строка получила время, округлите его до ближайшей минуты и добавьте 1 к соответствующему слоту в массиве. Как только вы закончите, вы будете точно знать, сколько активных пользователей было для каждой игры в каждую минуту.

Сложность - O (N), где N - количество строк в файле журнала.

Чтобы поддерживать несколько игр, просто используйте хеш для отображения из названия игры в вектор.

Теперь это предполагает, что вы проверяете только активных пользователей на всех минутах (1:00:00, 1:01:00 и т.д.). Это, вероятно, то, что вам нужно делать в любом случае.

Ответ 4

Это будет моя последовательность ответов:

Зачем беспокоиться? Проще всего подсчитывать, сколько пользователей активно. Разве это недостаточно, чтобы знать это?
Если вы действительно заботитесь о новейшей информации, включите подсчет во второй раз (как описано Cheeken). Это будет точно до доли секунды.
Хорошо, если точность в реальном времени является "необходимой", и вы хотите взять интервью у меня о структурах данных, позвольте использовать кучу клиентов, набранных по последнему времени активности (как описано Мастер Йодой).
Если нужна точность в реальном времени, и мы должны были сделать это в процессе производства, позвольте использовать сервер структуры данных Redis. Мы сохраняем отсортированный набор клиентов, забитых последним временем активности. Мы можем запросить, сколько клиентов было активным в последнюю минуту или в последний час с помощью команды zcount. Это полезно и надежно.