четверг, сентября 11, 2014

Легковесная аналитика с битовыми картами Redis и Lua

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

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

Мы выделили следующие требования:
  • Выводить все показатели (например, количество уникальных клиентов в данном месте) как за диапазон дат так и за конкретную дату или месяц.
  • Уметь просматривать эти показатели за произвольный период рекламной кампании. Т.е. не заранее установленный диапазон "За неделю" или "Прошедшие 30 дней", а "28 октября 2013 - 17 ноября 2013".
  • Уметь масштабироваться до нескольких десяткой тысяч уникальных клиентов для одной витрины.  
  • Метрики должны работать очень быстро.
Достаточно быстры мы пришли к выводу, что традиционные решения в виде отложенных заданий или предварительно агрегированных
результатов не подходят, если необходимо поддерживать произвольные временные периоды для таких показателей. Каждый запрос должен выполняться "на лету". Оказалось, что выполнять подобные запросы на MySQL оказалось слишком дорогим даже при текущем количестве данных. Запрос одной метрики доходил иногда до нескольких секунд.

Redis

В Redis 2.6, были введены две дополнительные и довольно мощные функции: Битовые карты (Bitmaps) и поддержка Lua скриптов. 

Битовые карты

Битовые карты - это массив битов (нулей и единиц). В Redis можно установить и прочитать значение бита по заданному индексу в обычном ключе с помощью команд SETBIT и GETBIT. Например, в нашем случае, если клиенты с id = 2 и id = 6 зарегистрировались 12 ноября 2013. в витрине c id = 5 то это выглядело бы так:
Redis.setbit('business:5:customers:2013-11-12', 2, 1)
Redis.setbit('business:5:customers:2013-11-12', 6, 1)
Эти команды выставят биты с индексами 2 и 6 в единицу для ключа “business:5:customers:2013-11-12”. Символически значеним этого ключа станет последовательность "0010001".

Теперь, если мы хотим узнать сколько уникальных пользователей было в выбранной ветрине в указанный день мы можем просто выполнить
Redis.bitcount('business:5:customers:2013-11-12')
Команда BITCOUNT выполнить очень быстрый подсчет количества единиц в этой битовой строке. В нашем примере это будет 2.

В Redis мы может не только подсчитывать количество единиц с bitcount, но и выполнять битовые операции “AND”, “OR”, “XOR”, и “NOT”.

Вернёмся к нашим рекламным запросам. Чтобы  найти количество уникальных клиентов за указанный промежуток времени мы можем выполнить:
# Все ключи (даты) для которых вычисляем результат
keys = ['business:5:customers:2013-11-12', 'business:5:customers:2013-11-13', … to any date]
# Вычисляем пересечение всех указанных bitmaps и сохраняем в "business:5:customers:total"
Redis.bitop('OR', 'business:5:customers:total',  keys)
# Вычисляем количество
Redis.bitcount('business:5:customers:total')
Этот запрос даст нам количество уникальных клиентов за выбранный период.

Далее, если мы хотим взять этот результат и посчитать сколько мужчин было среди этих клиентов, мы можем выполнить битовое "И" полученной битовой карты с картой, которая отражает идентификаторы клиентов в мужской пол:
# Ключи для которых нужно провести расчёт
keys = ['business:5:customers:total', 'users:males']
# Посчитать пересечение ключе и сохранить результат в "business:5:males:total"
Redis.bitop('AND', 'business:5:males:total', keys)
# Посчитать количество
Redis.bitcount('business:5:males:total')
Резюмируя - битовые маски это чертовски крутая вещь.

Однако, не все, что нам нужно подсчитывать требует битовые маски. Такие штука, как "Чисто визитов" не требует уникальности для каждого пользователи и чтобы экономить память мы можем использовать обычный счётчик в Redis. Например инкриментировать счетчик визитов
Redis.incr('business:5:visits:2013-11-12')
Вот как это было изначально при расчете общего числа за отрезок времени в Ruby:
(start_date...end_date).each do |date|
  sum += Redis.get('business:5:visits:#{date}')
end
Это оказалось довольно медленно при подсчете за большое количество дней, и привело к появлению большого числа запросов к Redis для одной метрики.

На помощь приходит LUA 

Redis 2.6+ позволяет писать Lua скрипты, которые могут быть выполнены на Redis сервере. Внутри такого скрипты можно вызывать любые Redis команды. Это позволяет создавать аналоги хранимых процедур SQL. Таким образом, наша сумма из примеры выше может быть заменена следующим:

(выполняется в Redis) sum.lua:
local sum = 0
# для каждого ключа, который мы хотим суммировать
for index, key in ipairs(KEYS) do
  # Выполним команду Redis.get(key) чтобы получить значение ключа
  local value = tonumber(redis.call('GET', key))
  if value then
    sum = sum + value
  end
end
return sum
И вызов из Ruby
keys = []
(start_date...end_date).each do |date|
  keys << 'businesses:5:visits:#{date}''
end
#В продакшен окружении мы воспользуемся уже загруженным скриптом через evalsha, вместо eval
Redis.eval(`cat sum.lua`, keys)
Это небольшое изменение даёт вам возможность сильно увеличить скорость выполнения запроса и выполнить только 1 запрос к Redis вместо 365, если вы запрашиваете данные за год.

Плюсы и минусы


Как и всегда при использования такого подхода есть плюсы и минусы:

Плюсы:
  • Redis хранит все данные в памяти как ключ-значение и это очень быстро.
  • Используя битовые карты можно хранить большие объемы данные о пользователях в очень небольшом объеме памяти. И выполнять расчеты с ними ОЧЕНЬ быстро. Парни из Spool говорят "В тесте с 128 миллионами пользователей получение типичной метрики вида `уникальные пользователи за сутки` займет менее 50 мс на MacBook Pro, при этом займет всего 16 мб оперативной памяти". Очень крутая штука.
  • Lua скрипты позволяют сохранить присущую Redis скорость на сложных запросах.
  • Очень просто делать метрики в "реальном времени". События, которые мы хотим подсчитывать просто увеличивают счётчики или выставляют биты.
Минусы (примечание переводчика - как по мне, очень надуманные минусы):
  • Память стоит дороже, чем диск.
  • Redis это хранилище ключ-значение, тут нет зависимостей и типичного для ORM хранения данных из коробки. Нужно самому заботится об организации и именовании ключей, чтобы не запутаться.
  • Так как Redis - это хранилище в оперативной памяти для кейсов как у нас (не простой кеш, а скорее постоянное хранилище) сохранение данных на диск имеет решающее значение, а это порой не тривиально (см. http://redis.io/topics/persistence)
Оригинал на английском языке http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/


Отправить комментарий