Субботник по базам данных

Как перестать бояться
и начать разрабатывать
специализированные структуры данных

Зачем?

Зачем самостоятельно писать специализированные структуры данных?

— потому что можем?
— просто так захотелось?
— NIH (not invented here).

Лучше вместо этого использовать

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

Realtime антифрод

Для классификации посещений сайтов на человеческие / роботные.

Разработан в 2012 году для нужд Яндекс.Метрики.

Я не могу ни подтвердить ни опровергнуть
тот факт, что он до сих пор работает в продакшене.

Realtime антифрод

Набор серверов, отправляем в них информацию о трафике.

Серверы обновляют и выдают статистику по свойствам трафика.

По статистике работает машинно-обученная формула.

Какие свойства трафика есть

— Время события

— IP адрес, IP-сеть, геолокация;

— Cookie пользователя;

— URL и Referer, а также их домены;

— User-Agent;

...

Какую статистику можно считать

Счётчики — число событий по ключу:
— например — количество хитов для IP-сети класса C за минуту.

Кардинальности — число уникальных значений для ключа:
— пример: число уникальных cookie для IP-адреса;
— пример: число уникальных IP-адресов для cookie;
— пример: число уникальных сайтов, посещённых пользователем за час.

Статистики по времени:
— пример: дисперсия разницы между соседними событиями.

Арифметика: Throughput

Входящий трафик 600 000 событий в секунду,
— 30 млрд. событий в сутки.

На каждое событие, обновляем статистику по 15 ключам
— 10 млн. key lookups/sec.

Какое железо использовать для 10 млн. lookups/sec.?

Арифметика: Throughput

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.

Арифметика: Volume

Хотим хранить данные 1..2 суток.
Наиболее жирные ключи — UserID, URL, Referer, IP.

Кардинальности:
— URL — 1.5 млрд. в сутки.
— UserID — 450 млн. в сутки;
— IP — 100 млн. в сутки;

Арифметика: Volume

Всего ~5 млрд ключей.
Статистика по одному ключу — в районе 1 КБ.
— 5 ТБ в сутки.

В 2012 году на один сервер использовалось 128 GB оперативки.
— 40 серверов без дублирования.

Как поместить статистику по ключу в 1 КБ?

Даже один URL может быть больше нескольких килобайт.

— никогда не храним строки, только 8-байтовые хэши.

Как поместить статистику по ключу в 1 КБ?

Нужно считать очень плохую статистику.

1. Счётчики.

UInt64 count = 0; void update() { ++count; }

8 байт — отвратительно много.

Можно ли посчитать от одного до миллиарда, используя один байт?

Как поместить статистику по ключу в 1 КБ?

Можно ли посчитать от одного до миллиарда, используя один байт?

Да — для этого надо просто использовать генератор случайных чисел.

— для counter < 8, прибавляем единицу с вероятностью 1.
— для counter [8..16), прибавляем единицу с вероятностью 1/2.
— для counter [16..24), прибавляем единицу с вероятностью 1/4.
— ...
— для counter [128..256), прибавляем единицу с вероятностью 1/231.

Ожидаемое значение оценивается
методом максимального правдоподобия.

Метод может быть как недетерминированным, так и детерминированным, если вместо генератора случайных чисел использовать хэш-функцию от данных.

Как поместить статистику по ключу в 1 КБ?

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
и помещается на один сервер.

Counting Bloom Filter

Недостаток — теперь если использовать 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.

https://github.com/catboost/

Альтернативы

— Redis;
— Aerospike;
— Couchbase;
— Cassandra.

Бонус:

— YT Dynamic Tables;
— RTMR;
— YDB.

Как перестать бояться?

Хорошо представлять возможности железа.
Хорошо представлять свойства задачи и её численные характеристики.
Хорошо представлять внутреннее устройство доступных хранилищ данных.

Самоуверенность и отвага.

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

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

Далее

База данных истории посетителей.

Расчёт сессий посетителей.

— специализированные структуры данных на SSD+RAM.

?