13 млрд счётчиков и 220 000 RPS на запись: проектируем Key-Value-хранилище для Спамообороны

Привет! Меня зовут Тимур Нургалиев, я тимлид в команде Спамообороны. Яндекс Почта обрабатывает миллиарды писем, из них около 20–30% — спам. Технологии, которые мы создаём в команде, блокируют массовые рассылки и отправляют вредоносные письма в соответствующую папку.

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

Как работает Спамооборона

Для начала объясню, как работает Спамооборона. Если кратко, то это сервис, который умеет отличать хорошие письма от плохих с помощью набора признаков, которые мы извлекаем из писем.

Какие признаки помогают определить спам?

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

Если в письме есть ссылка, мы можем ответить на вопросы:

Сколько раз эта ссылка встречалась в письмах?
Сколько пользователей жаловались на письма с такой ссылкой?
Сколько пользователей извлекли эти письма из спама?

Такие признаки мы называем статистиками. Они дают следующие сигналы Спамообороне:

Массовость. Среднестатистический человек не рассылает тысячи писем в день.
Кардинальность геозон. Обычный человек не отправляет письма из десяти стран за день.
Статистика прочтений. Даже проморассыльщики не отправляют сразу тысячи писем людям, которые не получали от них даже приветственного письма.
Репутация. Если люди массово жалуются на письмо с темой «Купи слона», скорее всего, это спам.

Как считаем статистики

У нас есть часть письма, к примеру, ссылка. Давайте вычислим от неё нормализованное значение, а после возьмем хеш. В Спамообороне такой хеш мы называем шинглом. Шингл — хеш‑сумма от некоторого нормализованного «кусочка» письма: IP‑адреса отправителя, email отправителя, темы письма, ссылок письма и прочего.

Вместе с шинглом мы сохраняем его тип или номер — то, из какой части письма мы его взяли. Например, 8 — тема, 14 — From, 15 — IP‑адрес, 42 — имя аттача, 62 — чек‑сумма аттача. Всего в Спамообороне используется 75 различных типов шинглов.

По паре из шингла и его типа мы накапливаем статистику:

сколько раз мы посчитали письма с таким шинглом хорошими или плохими;
сколько пользователей пометили письма с этим шинглом как спам или наоборот.

Как работаем с посчитанной статистикой

Один из механизмов, который применяется в Спамообороне — это правила. По своей сути это эвристики, которые могут либо сработать, либо не сработать на письме. Если правило срабатывает, эта эвристика добавляет в Spam Score положительное или отрицательное значение. А итоговый вердикт выносится по общему Spam Score. Например, если Spam Score письма превысил 100 — это спам, в противном случае мы считаем письмо хорошим.

На картинке ниже приведу пример правила. Слева псевдокод для него, справа — как оно выглядит в наших конфигах.

На картинке видно: если в письме встречается 14-й тип шингла и 99% писем с этим шинглом мы помечаем как спам, мы добавляем этому письму Spam Score 1,5, что немного приближает письмо к блокировке.

Как Спамооборона работает со статистикой: пример

Мы рассмотрели, как собранные статистики работают в правилах. Теперь давайте объединим всё вместе и посмотрим, как Спамооборона работает с накопленной статистикой. Представим, что нам пришло вот такое письмо:

Что происходит дальше:

Сначала мы вычислим шинглы от различных «кусочков» этого письма, таких как:
- адрес отправителя;
- IP‑адрес отправителя;
- тема письма;
- чек‑сумма вложения (значение, вычисленное по набору данных, в нашем случае, по файлу вложения, и позволяющее проверить его целостность);
- название.
Если есть ссылка, то мы вычисляем шинглы и от неё.
После того, как все шинглы вычислены, мы идём в шинглеры — сервисы, которые хранят и отдают статистики по шинглам.
Помимо расчёта статистик, мы вычисляем другие признаки письма. Здесь мы используем два вида информации: которую извлекли из него и которую узнали из внешних источников. Примеры таких признаков:
- информация о получателе;
- информация об отправителе;
- информация о файлах;
- эмбеддинги, олученные применением ML‑моделей к тексту письма.
После того как мы извлекли все эти признаки, на их основе вычисляем правила. Те самые эвристики, что считают Spam Score.
Когда признаки и правила вычислены, мы передаём вычисления в CatBoost, который выдаст итоговый вердикт — хорошее ли это письмо или нет.

Ну всё, разобрались. Давайте перейдём к самому интересному и рассмотрим архитектуру такого шинглера.

Что под капотом у шинглера

Шинглер — это сервис, хранящий статистику по шинглам за последнее время. Он умеет накручивать и возвращать счётчики по набору пар «шингл + тип». Собственно, это и есть Key‑Value‑хранилище, но со своими особенностями, которые задаёт наша предметная область.

Особенности шинглера:

По каждому письму нужно вычислить около 40 различных счётчиков. Это более 200 тысяч обновлений счётчиков в секунду. В сутки выходит около 13 миллиардов различных шинглов, по которым нужно обновить значение.
Одинаковая нагрузка на чтение и на запись. По каждому письму нужно сначала получить статистику по всем шинглам, а затем обновить эту статистику.
Крупные рассылки и спам‑атаки приводят к большому рейту запросов на конкретные шинглы. Это горячие ключи, но мы не знаем, когда они станут горячими и насколько сильно.
Не так важна идеальная точность, главное — посчитать статистику.

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

Считаем уникальные значения в шинглере

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

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

Такой запрос решают парные шинглы:

uid_rcpt_shingle — хеш от пары <uid, rcpt>. Этот шингл будет вычисляться как хеш от пары из отправителя и получателя. Считаем, сколько раз пользователь с данным uid писал данному получателю rcpt. В нём накапливается статистика о том, сколько писем данный отправитель послал данному получателю за определённый период (например, за день).

unique_rcpt_shingle — хеш от uid. Второй шингл мы считаем как хеш от отправителя. Считаем количество уникальных получателей, которым писал пользователь c данным uid. Такие шинглы мы называем уникальными, или сокращённо униками.

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

Чтобы было понятнее, покажу на примере:

Пользователь с uid=71 послал первое за сутки письмо на адрес tea‑mur@yandex.ru.
Запрашиваем увеличение счётчиков для пары шинглов 30 и 31.
- Шингл 30: 1a0d25c934 162 402 — вычисляется как хеш от строки 71_tea‑mur@yandex.ru;
- Шингл 31: 120d322bf9a3cdc7 — вычисляется как хеш от строки 71.

Для шингла 30 все счётчики нулевые, поэтому мы накрутим как счётчик для 30-го, так и счётчик для 31-го шингла.
Если пользователь отправит ещё одно письмо на адрес tea‑mur@yandex.ru, мы не будем увеличивать счётчик для 31-го шингла. Это связано с тем, что значение по 30-му шинглу уже не будет равно нулю за этот период времени.

Архитектура старого шинглера

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

Хранили счётчики в памяти за последние 48 часов, то есть за два дня в разбивке по часам.
Периодически сбрасывали эту информацию на диск.
Через L3-балансировщик запрос попадал на одну из равнозначных реплик.
Реплика применяла обновления у себя и асинхронно сообщала об изменениях другим.

Если происходил запрос на чтение, мы приходили в одну из реплик и получали более‑менее актуальные данные.

Но в чём проблемы такого шинглера?

Все счётчики были ограничены 2ˆ16. Это проблема реализации, а не архитектуры. В нашем случае это приводило к тому, что счётчики переполнялись даже за такой короткий период, как два дня. Спамооборона начинала пропускать письма, которые ранее с удовольствием реджектила.
Отсутствие шардирования данных, поэтому у нас не было возможности масштабироваться.
Не было репликации данных после переезда хоста. Когда хост перемещался с одной машины на другую, он терял всю накопленную статистику и начинал заново. Это снова приводило к тому, что Спамооборона пропускала письма, которые ранее отклонялись.
Была информация по каждому счётчику только за вчера и сегодня, не хватало гранулярности и диапазона хранимых значений.
Доступность в две девятки и слабые гарантии надёжности.

Архитектура нового шинглера

Хранение

Что мы изменили:

Теперь мы храним счётчики в персистентной шардированной базе данных.
Фактор репликации 3.
Шардируем по значению шингла. Берём остаток от шингла на количество шардов, которые используются в нашей базе данных. Так как шингл — это хеш‑сумма, значения распределяются равномерно по всем шардам.
Если шинглы парные, определяем номер шарда по унику. Такие шинглы всегда поступают в одном запросе на обновление данных, поэтому у нас всегда есть парный шингл. Рассчитывая номер шарда таким образом, мы можем локально на одном шарде проверить, была ли уже произведена накрутка парного счётчика за текущий период времени.
При переезде новые узлы скачивают данные со старых. Фоновый процесс чистит базу от старых данных.

В качестве базы данных решили использовать поисковый индекс. Аргументы в пользу такого выбора:

Быстрые запросы по интервалу. Индекс позволяет оперативно вернуть значения счётчиков за какой‑то интересующий нас период времени.
Большая часть данных неизменна. Мы меняем счётчики только за текущий период.

Мы использовали готовый индекс из Яндекс 360 для поиска по Почте на базе Apache Lucene. Наша задача заключалась лишь в настройке конфигурации и указании полей для индексирования.

Ниже покажу, как выглядит индексация:

Первичный ключ в поисковом индексе представляет собой строку. В нашем случае строка выглядит следующим образом: <префикс>_<шингл>_<тип шингла>_<период>_<номер периода>.

Десятиминутный счетчик → mass_in_5791f8cac2b7d8dd_14_10m_2 831 519 счётчик массовости по шинглу 14: 5791f8cac2b7d8dd за десятиминутку № 2 831 519 от «начала эпохи» (2023–11–02 07:50).

Суточный счетчик → mass_in_5791f8cac2b7d8dd_14_1d_19 663 — счётчик массовости по шинглу 14: 5791f8cac2b7d8dd за день № 19 663 от «начала эпохи» (2023–11–02).

Префикс используется для указания имени сервиса, для которого мы накапливаем счётчики. Это позволяет хранить отдельные версии счётчиков для различных сервисов, например, в Спамообороне — для входящей и исходящей почты отдельно.
Берём шингл и его тип.
Период, за который мы считаем счётчик.
Номер периода с «начала эпохи».

Запись

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

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

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

Если приходит новый запрос на обновление счётчиков, а у нас в памяти уже есть счётчики за последний период, мы просто складываем новые значения с уже существующими. Нам неважно, накрутить счётчик один раз на 5 или пять раз на 1. Это снижает число обновлений. Фоновый процесс, который обходит буфер, подменяет рандомизированный шард пустым и отправляет пачку в очередь на индексацию.

Для снижения нагрузки на индекс при чтении используем кэш в памяти самого приложения.

Группируем шинглы в запросе по шардам. Если информация про шингл в кэше актуальна, берём её оттуда, иначе идём в поисковый индекс.

Новый шинглер: плюсы

Мы устранили проблему со счётчиками — они теперь ограничены в 2^63 и вряд ли переполнятся.
Увеличили гранулярность и время хранения. Теперь храним счётчики за последние сутки в разбивке по 10 минут и за последние две недели в разбивке по дням. Гранулярность позволяет нам видеть распределение того, как приходят запросы на конкретные шинглы, и определять роботную нагрузку.
Починили скачивание данных с «соседей» при перезаливке хоста.
Обеспечили масштабируемость. Можем увеличивать нагрузку, пока нам будет хватать шардов, и количество хранимых данных.
Увеличили показатели по надёжности и доступности.
Количество неответов в неделю уменьшилось в 15 раз. Теперь данные, попадая в очередь, надёжно сохраняются и остаются в поисковом бэкенде до истечения срока их хранения. После этого они будут удалены фоновым процессом.

Новый шинглер: минусы

Был один сервис, а стало три: сервис с бизнес‑логикой, очередь и поисковый бэкенд. Это всё нужно поддерживать.
Увеличилась потребность в железе.
Среднее время ответа выросло — но это некритично, потому что мы укладываемся в желаемое время ответа.

Использование шинглеров позволяет Спамообороне оперативно определять и блокировать спам‑атаки. А обновив архитектуру шинглера, мы стали делать это ещё надёжнее и эффективнее. Надеюсь, мой рассказ оказался полезным и вы открыли для себя что‑то новое в работе Спамообороны и проектировании сервисов.

ссылка на оригинал статьи https://habr.com/ru/articles/850856/