Зачем самостоятельно писать специализированные структуры данных?
— потому что можем?
— просто так захотелось?
— NIH (not invented here).
Лучше вместо этого использовать
... надёжные, современные, масштабируемые, отказоустойчивые, поддерживаемые, проверенные временем, одобренные сообществом технологии, разработанные лучшими инженерами, написавшими идеальный код, который решает в точности нужную вам задачу.
Для классификации посещений сайтов на человеческие / роботные.
Разработан в 2012 году для нужд Яндекс.Метрики.
Я не могу ни подтвердить ни опровергнуть
тот факт, что он до сих пор работает в продакшене.
Набор серверов, отправляем в них информацию о трафике.
Серверы обновляют и выдают статистику по свойствам трафика.
По статистике работает машинно-обученная формула.
— Время события
— IP адрес, IP-сеть, геолокация;
— Cookie пользователя;
— URL и Referer, а также их домены;
— User-Agent;
...
Счётчики — число событий по ключу:
— например — количество хитов для IP-сети класса C за минуту.
Кардинальности — число уникальных значений для ключа:
— пример: число уникальных cookie для IP-адреса;
— пример: число уникальных IP-адресов для cookie;
— пример: число уникальных сайтов, посещённых пользователем за час.
Статистики по времени:
— пример: дисперсия разницы между соседними событиями.
Входящий трафик 600 000 событий в секунду,
— 30 млрд. событий в сутки.
На каждое событие, обновляем статистику по 15 ключам
— 10 млн. key lookups/sec.
Какое железо использовать для 10 млн. lookups/sec.?
HDD — 100..300 lookups/sec.
Потребуется 100 000 HDD без резервирования или ~ 10 000 серверов.
SSD — ~ 100 000 lookups/sec.
Потребуется 100 SSD без резервирования или 10 серверов?
— но зачёркиваем, так как чтение/запись 1:1.
RAM — 10 млн. / 40 млн. / 500 млн. LL cache misses / sec.
Хотим хранить данные 1..2 суток.
Наиболее жирные ключи — UserID, URL, Referer, IP.
Кардинальности:
— URL — 1.5 млрд. в сутки.
— UserID — 450 млн. в сутки;
— IP — 100 млн. в сутки;
Всего ~5 млрд ключей.
Статистика по одному ключу — в районе 1 КБ.
— 5 ТБ в сутки.
В 2012 году на один сервер использовалось 128 GB оперативки.
— 40 серверов без дублирования.
Даже один URL может быть больше нескольких килобайт.
— никогда не храним строки, только 8-байтовые хэши.
Нужно считать очень плохую статистику.
1. Счётчики.
UInt64 count = 0;
void update() { ++count; }
8 байт — отвратительно много.
Можно ли посчитать от одного до миллиарда, используя один байт?
Можно ли посчитать от одного до миллиарда, используя один байт?
Да — для этого надо просто использовать генератор случайных чисел.
— для counter < 8, прибавляем единицу с вероятностью 1.
— для counter [8..16), прибавляем единицу с вероятностью 1/2.
— для counter [16..24), прибавляем единицу с вероятностью 1/4.
— ...
— для counter [128..256), прибавляем единицу с вероятностью 1/231.
Ожидаемое значение оценивается
методом максимального правдоподобия.
Метод может быть как недетерминированным, так и детерминированным, если вместо генератора случайных чисел использовать хэш-функцию от данных.
2. Кардинальности.
Очевидно, что нужно использовать HyperLogLog.
2.5 КБ — ошибка ~1% — слишком хорошо, надо хуже.
24 байта — ошибка ~50% — вот теперь нормально.
Уже можно поместить 50 кардинальностей в 1 КБ.
5 ТБ в сутки — 50 серверов без дублирования.
— но нужна x2 репликация для отказоустойчивости;
— но нужно хранить данные чуть больше суток.
У нас нет 100 серверов. Задача неразрешима.
Решение — не хранить статистики по ключам,
которые встречаются редко.
Если мы увидели IP адрес впервые — ничего про него не храним.
Если мы встретили его 16 раз — начинаем считать статистику.
Но чтобы понять, что он встретился в шестнадцатый раз
— надо это где-то хранить.
Решение — Counting Bloom Filter.
Из 128 GB на сервере, выделим 10..20 GB на CBF.
CBF работает как «губка», через которую просеиваются
только важные ключи.
Объём оставшихся данных уменьшается до сотни GB
и помещается на один сервер.
Недостаток — теперь если использовать 3 хэш-функции, придётся делать в 3 раза больше кэш-промахов.
10 млн. в секунду -> 30 млн. в секунду.
Это всё ещё может работать... даже на одном сервере.
Или изобрести cache-local Counting Bloom Filter?
Предположим, что сервер должен обрабатывать
~ 1 млн. запросов в секунду.
Какими технологиями написать такой сервер?
— coroutines/fibers?
— DPDK?
У нас realtime антифрод, но отправлять данные
будем всё-равно пачками по 1000 .. 10 000 событий.
Задержка в одну секунду приемлима,
а в секунду приходит 600 000 событий.
Будем использовать обычный HTTP сервер с пулом потоков.
Как обеспечить конкурентную обработку
одновременно приходящих запросов?
Может быть использовать lock-free структуры данных?
Как обеспечить конкурентную обработку
одновременно приходящих запросов?
Может быть использовать lock-free
структуры данных?
Нет, лучше сделать в сервере один глобальный mutex, и обрабатывать в один момент времени
один запрос, а остальные будут ждать.
Размениваем latency на throughput.
Как распараллелить обработку запросов по процессорным ядрам?
Разбить все данные по остатку от деления хэша от ключа на N корзин.
Все структуры данных в сервере (Counting Bloom Filter, Hash Tables) имеются в N экземплярах.
Входящая пачка данных передаётся для обработки пулу потоков, каждый из которых обрабатывает свои ключи.
— внутреннее шардирование.
между серверами?
— никак :(
Каждый сервер записывает на диск лог запросов и позволяет реплике считывать и обрабатывать этот лог.
Этот же лог используется для восстановления после сбоя.
Репликация асинхронная eventually inconsistent.
Три варианта:
— разбить все данные на корзины по часам и удалять старые корзины;
— экспоненциальное сглаживание: с некоторой периодичностью делить значения счётчиков в два раза;
— периодически сбрасываем дамп на диск, перезапускаем сервер и считываем из дампа только актуальные данные.
На вход: одно событие — 50 столбцов UInt64 — 400 байт
~ 4 GBit/sec.
На выход:
— передавать все посчитанные статистики
— 500 столбцов UInt32 —
2 КБ ~ 20 GBit/sec.
— передавать только результат машинно-обученной формулы
— float — 4 байта на событие.
Но у нас 1 GBit сеть :(
Просто будем сжимать данные.
LZ4 — слишком слабо.
QuickLZ — на 2012 год лучше альтернативы не было,
сейчас не актуально.
2019 год — используйте ZSTD или Brotli.
Как принимать решение о роботности трафика?
Машинно-обученная MatrixNet формула.
Сейчас более совершенная технология доступна
в open-source: CatBoost.
— Redis;
— Aerospike;
— Couchbase;
— Cassandra.
Бонус:
— YT Dynamic Tables;
— RTMR;
— YDB.
Хорошо представлять возможности железа.
Хорошо представлять свойства задачи и её численные характеристики.
Хорошо представлять внутреннее устройство доступных хранилищ данных.
Самоуверенность и отвага.
Использовать арифметику, чтобы соотнести
свойства задачи с возможностью железа.
Быть готовым разбираться, если теория не сходится с практикой.
База данных истории посетителей.
Расчёт сессий посетителей.
— специализированные структуры данных на SSD+RAM.