Realtime-статистика счетчиков с использованием битмапов

В свое время я додумался до использования двоичного представления данных в качестве наиболее быстрого способа обработки и передачи флагов. К примеру, посмотрите на даты в календаре сайта. Информация о днях со статьями получается из двоичной записи числа длиной 31 бит. Но все это - баловство по сравнении с тем, как битовые карты (bitmap-ы) используют в описанной ниже статье. Серверным приложением хранения данных служит Redis, пример запроса на Java, но это не значит, что идея не переносима. Например, при определенном упорстве и наличии расширения gmp можно реализовать учетную статистику средствами PHP/MySQL. Я предлагаю вам к прочтению только перевод статьи. Идею развивайте самостоятельно :)

Сначала пару слов о Redis. Это демон *nix, может хранить данные в виде ключ-значение в оперативной памяти. Так же он способен кешировать эти данные на винт. Это не все его плюшки, но достаточно для понимания статьи. В официальном мануале Redis каждая операция оценена временем выполнения вида O(f(x)). Наиболее быстрые по времени выполнения операции оцениваются как O(1). Подробнее об этой оценке можно почитать в Википедии и здесь.

Быстрые и простые метрики в реальном времени посредством битовых карт Redis

Оригинал: Fast, easy, realtime metrics using Redis bitmaps © Chandra Patni, 29/10/2011.

Некоторые понятия в переводе на русский звучат совсем коряво, приношу свои извинения.

В Spool (был такой сервис закладок в инете - прим.перев.) мы считаем наши ключевые метрики в реальном времени. Традиционно, показатели собираются в пакетном режиме (ежечасно, ежедневно, и т.д) Redis поддерживая битмэпы позволяет нам выполнять такие вычисления в реальном времени с экстримально эффективным использованием пространства (речь про память и место на винтах - прим.перев.) В симуляции 128 миллионов пользователей, вычисление типичного показателя, такого как "уникальные посетители за день", заняло меньше 50мс на MacBook Pro и всего 16Мб памяти.

Приведенный комп Мас - это обычный ноутбук. Т.о. полученные результаты симуляции - это очень круто (прим.перев.).

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

Битмэп или битсет это массив нулей и единиц. Бит в битсете может быть установлен в 0 или 1, и каждая позиция в массиве называется смещением (offset). Такие битовые операции, как логическое AND, OR, XOR и другие, вполне применимы к битмэпам.

Для дальнейшего ликбеза загляние в Википедию.

Population count

"Population count" дословно переводится "количество населения", применительно к информации подразумевает количество единиц в двоичной записи каких-либо данных. Рискну назвать это по-русски, как "счетчик единиц" (прим.перев.).

Количество единиц битмэпа это число бит, установленных в 1. Есть эффективные алгоритмы для расчета этого количества. К примеру, подсчет единиц битмэпа, заполненного на 90% и содержащего миллиард бит, займет 21.1мс на все том же MacBook Pro. Есть даже ассемблерные инструкции группы SSE4 для получения счетчика единиц, как целого числа.

Битмэпы в Redis

Redis принимает бинарные ключи и бинарные значения. Битмэпы - ничто иное, как бинарные значения. Операция setbit(key, offset, value), которая занимает O(1) времени выполнения, устанавливает значение бита в 0 или 1 по определенному смещению для переданного ключа.

Простой пример: активность пользователей за день

Для подсчета уникальных юзеров, которые залогинились сегодня, мы создаем битмэп, где каждый пользователь определяется смещением на карте. Когда пользователь посещяет страницу или выполняет действие, которое нужно считать, ставим в единицу бит по адресу (смещению), соответствующую id пользователя. Ключ, определяющий соответствующий битмэп, это функция с именем действия юзера и меткой времени (timestamp).

В этом простом примере, с каждым входом юзера мы выполняем

redis.setbit(daily_active_users, user_id, 1)

Эта операция установит в 1 бит по соответствующему смещению в битмэпе "daily_active_users". По времени выполнения займет O(1). Выполним подсчет единиц в этом битмэпе, результат - 9 уникальных пользователей залогинилось сегодня. Ключ "daily_active_users" значение 1011110100100101.

Запрос на получение "рopulation count" можно выполнить в любое время, т.о. получаем статистику реального времени (прим.перев.)

Конечно, поскольку дневная активность пользователей меняется каждый день, нам нужно создавать новый битмэп ежедневно. И мы делаем это простым добавлением даты в имя ключа битмэпа. Например, если мы хотим подсчитать ежедневных уников, которые проиграли хотя бы одну песню в музыкальном приложении в конкретный день, мы можем задать имя ключа так "play:yyyy-mm-dd". Если мы хотим подсчитать число уникальных юзеров, проигрывающих песню каждый час, можно назвать ключ "play:yyyy-mm-dd-hh". В дальнейшем изложении мы будем придерживаться дневных уников, проигравших песню. Для сбора дневных метрик, мы просто будем поднимать бит (ставить с 1) в ключе play:yyyy-mm-dd, когда юзер слушает песню. Это операция O(1) времени выполнения.

redis.setbit(play:yyyy-mm-dd, user_id, 1)

Уникальные пользователи, прослушавшие песню сегодня - это количество единиц (population count) битмэпа, хранящихся в значении ключа play:yyyy-mm-dd. Для подсчета недельных или месячных метрик, мы просто можем объединить дневные битмэпы (логическое ИЛИ) за неделю или месяц, и затем вычислить счетчик единиц результирующего битмэпа.

Вы так же очень просто можете создать более сложные метрики. Например, премиум-юзвери, кто прослушал песню в Ноябре, получатся так:

Сравнение производительности с использованием 128 миллионов пользователей

Таблица ниже демонстрирует сравнение дневных уникальных вычислений, расчитанных за каждый день, 7 дней и 30 дней для 128 миллионов пользователей. Метрики 7 и 30 расчитаны объединением дневных битмэпов.

Оптимизация

В примере выше мы смогли оптимизировать расчеты недели и месяца за счет кеширования дневных, недельных, месячных счетчиков в Redis. Это очень гибкий подход. Дополнительный плюс кеширования в том, что оно позволяет проводить быструю групповую аналитику, типа уникальные пользователи за неделю, кто так же является юзерами мобильников - пересечение битмэпа мобильных пользователей с битмэпом недельной активности. Или, если мы хотим посчитать уникальных посетителей, пришедших повторно за последние N дней, имея кешированные уникальные счетчики, сделать это легко - возьмите предыдущие N-1 дней из кеша и объедините со счетчиком реального времени. Это займет всего 50мс.

Пример кода

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

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
  Jedis redis = new Jedis("localhost");
...
  public int uniqueCount(String action, String date) {
    String key = action + ":" + date;
    BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
    return users.cardinality();
  }

Следующий сниппет считает уников с заданным действием и списком дат.

import redis.clients.jedis.Jedis;
import java.util.BitSet;
...
  Jedis redis = new Jedis("localhost");
...
  public int uniqueCount(String action, String... dates) {
    BitSet all = new BitSet();
    for (String date : dates) {
      String key = action + ":" + date;
      BitSet users = BitSet.valueOf(redis.get(key.getBytes()));
      all.or(users);
    }
    return all.cardinality();
  }

14 июля 2016

Сегодня я пробовал реализовать эту идею в связке Redis + PHP 7.0. И застрял на такой проблеме: php::gmp_popcount() работает только с двоичными числами или GMP объектами. А Redis возвращает битмапы, как строки. Т.о. нужны костыли, чтоб преобразовать побитно то, что отдал Redis, в то, что сможет понять GMP. Некогда решать эту запарку. В итоге клевая затея через PHP не удалась.