Switch to english version or google translate this

Тестовое задание в команду высоких нагрузок VK

Публикация согласована ✅

Выполняет: Никита Лисоветин, студент группы М3339 кафедры КТ университета ИТМО (vkontakte, github)

Как анализировать миллиарды запросов в наносекунду и в то же время выдавать их топ за последнюю минуту? Просто используй эту map! Я проанализировал разные алгоритмы с математической основой, воплотил наилучший в программу и успешно протестировал. Поэтому не ссы в трусы и используй этот MapGetFreshTopK!

🚀 Быстрый запуск

Для компиляции решения и сборки библиотеки набрать в консоли из директории проекта:

./make_lib.sh

Для запуска тестов из директории проекта (тестирование занимает 15 минут, используются Google Tests):

#linux/macos
./run_tests.sh

#windows cmd
1. Run cmake-gui.exe
2. Set sourse code place *project_directory* (without spaces!)
3. Create and choose build_dir directory in root of *project_directory* (without spaces!)
3. Click "configure" and generate MinGW MakeFile
cd build_dir
cmake ..
make all
cd google_tests
Google_Tests_run.exe

☠️ Структура проекта

Название	Описание
main.cpp	Hello World! проверка работоспособности MapGetFreshTopK
map_get_fresh_top_k_lib	Директория с файлами и реализацией классов по заданию
map_get_fresh_top_k_lib/map_with_get_very_frequent.h	Класс `MapGetFreshTopK`
map_get_fresh_top_k_lib/frequency_estimation_analyzer.h	Класс `FrequencyEstimationAnalyzer`, реализующий анализатор для `MapGetFreshTopK`
google_tests	Директория с файлами для тестов
google_tests/tests.cpp	Google тесты
google_tests/accurate_frequency_analyzer.cpp	Класс `AccurateFrequencyAnalyzer`, реализующий точный анализатор для получения топа ключей по числу запросов (используется для проверки `MapGetFreshTopK`), не жалеющий память
google_tests/utility_functions.cpp	Много вспомогательных функций, используемых в Google тестах

Все файлы, классы, публичные методы и важные функции сопровождаются комментариями. Используется Google C++ Style Guide.

💎 Исходная формулировка задания

Часть 1.

На c++ (должно компилироваться g++ -std=c++11 без каких-нибудь внешних библиотек) нужно написать класс, который внутри себя должен хранить хеш-таблицу из строки в строку и уметь отвечать на запросы:

get key — получить ключ
set key value — изменить ключ

Можно считать, что длина ключа не превосходит 1Кб, а длина значения 1Мб.

Внутри должен быть встроен анализатор того, как часто какие ключи спрашивают. Потребляемая анализатором память не должна превышать какой-нибудь константы (например, мегабайт) вне зависимости от количества ключей/запросов, которые приходили в инстанс класса. Этот анализатор должен уметь выдавать топ ключей, которые спрашивали за последнее время. Эту фразу можно интерпретировать по-разному, но анализатор точно должен подходить под следующий критерий: если какой-то ключ за последнюю минуту спросили больше чем в 10% запросов, то такой ключ с 99% вероятностью должен попасть в вывод анализатора.

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

Часть 2.

Нужно написать unit-тесты на созданный класс, которые бы проверяли, что правильно находятся highload-ключи. Тестировать то, что сама хештаблица работает правильно не нужно. Сами тесты можно оформить в виде отдельного файла, который подключает написанный класс и вызывает его методы. А потом выводит на stdout правильно ли определились горячие ключи.

🚄 Задача в двух словах

В онлайне идёт поток данных (запросы с ключами)
Мы должны научиться отвечать в онлайне на запрос: "дай список ключей, которые могли встретиться в хотя бы 10% запросах за последнюю минуту"
ИМЕННО ЗА ПОСЛЕДНЮЮ МИНУТУ
Объем памяти анализатора фиксирован и не зависит от числа запросов
Результат запросов записываем в хеш-таблицу

⚡ Поиски решения в интернете

Известна задача "top K frequent elements in array", но она нам не подходит — у нас работа в онлайне. Наша же задача гуглится словами наподобие "top K frequent elements in data stream".

В результате я нашел и изучил следующие полезные статьи:

Помимо того, что существуют библиотеки, где уже реализован необходимый функционал (например, stream-lib for Java), выделяются следующие 3 подхода, применимые к именно нашему заданию (константа памяти, онлайн обработка):

Count-Min Sketch с Heavy Hitters Возможное решение. Несмотря на маленький размер таблицы и 2^8192 возможных значений ключей, нагрузка вряд ли будет превышать 100 миллионов запросов в секунду, поэтому коллизиии в таблице и большое количество хеш-функций могут не влиять сильно.
Lossy Counting Обрабатывает данные порциями (делит данные на куски и с каждым по-отдельности работает). Неплохо, но с первого взгляда алогритм сложен в реализации ввиду наличия постоянного ограничения на место, занимаемое анализатором (то есть сложно следить за порциями данных, результатами обработки (нагрузка может сильно меняться, а мы должны отдавать результат точно за 1 последнюю минуту))
Frequency Estimation На самом деле просто другой "Lossy Counting", обрабатывающий данные уже в потоке, а не порциями. Отличное решение

🎳 Сравнение разных подходов

2 или 3? Преимущества перед 3 неочевидны, но алгоритм гораздо сложнее. Оставляем 3.

1 или 3? При сравнении 1 и 3 для аналогичного действия в 1 мы считаем кучу раз разный хеш от ключа размером до 1 Кб, реализация довольно трудоемка, отсутствует готовая математическая теория для оценки ошибки в получаемом количестве запросов с данными популярными ключами.

Выиграл алгоритм 3. Frequency Estimation!!!

🔥 Метод бакетов

Все эти алгоритмы для получения топа за промежуток времени предполагают "бакеты" (сохранение результатов обработки данных в пакеты/колодцы, добавлять элементы в которые можно, а убирать — нет). Самый лучший подход в нашем случае следующий:

Отвечаем на запрос не про точно 60 последних секунд, а про последние 60-65 секунд (это "неустранимая погрешность", хотя её можно значительно уменьшить просто увеличив число бакетов). Храним 13 бакетов про последние не более 65 секунд. Каждые 5 секунд удаляем самый старый бакет и создаем новый. Обработка запросов get/set затрагивает все 13 бакетов. При запросе get_top_k() работаем с самым старым текущим бакетом

💘 Решение

Алгоритм и математическая составляющая (теория вероятности) отлично описаны в этой статье.

Согласно статье (см. 4 Conclusions), если хотим найти ключи A, встретившиеся хотя бы в $n * 10\%$ запросах, то alpha=0.1, точность ответа о количестве, с которым встретился ключ a из A, будет $(1-alpha)*n/m = (1-0.1)*n/m = 0.9*n/m$ . Чтобы выдать все ключи, которые встретились в 10% запросах в реальности, нам нужно рассмотреть все ключи, встретившиеся хотя бы $alpha*n — (1-alpha)*n/m = 0.1*n - 0.9*n/m$ раз. Таких $\leq n / (0.1*n - 0.9*n/m)$ , а в реальности <= 10.

Мы хотим, чтобы первое число было недалеко от второго (мы хотим всегда получать примерно топ-10, но никак не топ-50). Но в то же время, чтобы и m не было слишком большим (m — размер каждого из наших 13 хештейблов). Рассмотрим разные варианты:

m	1 / (0.1 - 0.9/m)
10	100
18	20
27	15
32	14
39	13
54	12
99	11

(сгенерировано скриптом python)

for i in range(10, 200):
	print(i, 1 / (0.1 - 0.9/i))

m = 54 и согласие на увидеть в редком случае 11 или 12 ключей (действительно популярных — в таком случае каждый должен встретиться в >= 8.3% запросах). Более "правильные" константы подберутся на практике.

🍔 Тестирование

Для всех тестов, кроме первых очевидных, используется класс AccurateFrequencyAnalyzer из файла google_tests/accurate_frequency_analyzer.h — анализатор, записывающий в статистику пары "ключ, время добавления" и при запросе GetActualTop() выдает ключи, которые встретились в точности в >= 10% запросах за ровно последнюю минуту. Он бы решал нашу задачу, если бы у нас не было ограничения на фиксированный постоянный размер анализатора, не зависящий от количества запросов в секунду.

Для более быстрого тестирования без потери качества в MapGetFreshTopK в тестах инициализируется анализатор не за последние 60 секунд, а последнюю 1 секунду. При этом количество бакетов и их размер такой же.

Так как наша структура работает неточно — мы выдаем результат всегда с запасом по времени, то иногда мы ошибаемся и проверка на корректность естественным образом фейлится. Поэтому есть два типа тестов:

Тесты ...OneGet проверяют корректность работы внутренних алгоритмов анализатора — не позже 1 секунды мы вызываем GetVeryFrequent один раз и проверяем правильный ли результат

Остальные тесты — проверяют, что количество ошибок <= 1%. Следующим образом: симулируется различное поведение запросов на разных промежутках времени (поведение четырех видов: есть горячие ключи, все ключи "холодные", только запросы GetVeryFrequent, полный рандом (мы однозначно не понимаем какие ключи горячие, а какие нет)). Каждые milliseconds_get_period миллисекунд (обычно 1) вызывается GetVeryFrequent нашего анализатора и точного анализатора и проверяется действительно ли все ключи из точного анализатора мы нашли. Если нет — то это ошибка и мы увеличиваем mistakes. В конце теста (в long_long тестах — многочисленных внутренних) мы сравниваем mistakes/global_get_num, где global_get_num количество операций GetVeryFrequent, с требуемой по заданию допустимой погрешностью 0.01.

В теории, если бы тесты проваливались, то нужно было бы увеличить константы (в первую очередь — увеличить количество бакетов), но все тесты успешно проходятся.

Так как мы тестируем нашу систему в искусственных условиях (мы выводим не топ-10, а те, для которых наша теория работает, то есть встречаются хотя бы в ~10%) и на искусственных тестах (какое-то время есть горячие ключи, какое-то вообще их нет, резкие изменения и переходы состояния системы и т.п.), то "неустранимая погрешность" иногда дает о себе знать и валит тесты (long_long_tests_one_hotkey/bad_tests). Поэтому:

Тесты могут падать, потому что они слишком точные
num_buckets = 20, bucket_size = 100 значительно уменьшает вероятность падения на этих тестах, но не исключает этого
Формулу минимального значения счетчика для элемента, с которого мы будем считать, что он входит в топ: ( $alpha*n — (1-alpha)*n/m = 0.1*n - 0.9*n/m$ ), заменим на $[0.1*n] - ]0.9*n/m[ - 2$

🔓 Открытые вопросы на будущее

Договориться о поведении get key, когда ключа нет. В текущем решении поведение аналогично поведению std::map::operator[]
Договориться об обработке ошибок. Где ловить и как обрабатывать или пробрасывать дальше?
Насколько мы жадны до памяти, производительности и точности результата? Сейчас сильная экономия на числе бакетов и их размерах, но, значительно увеличив их количество мы запросто получим гораздо более точный результат
Реализовать ли автоматический поиск числа бакетов и их размера для работы с любым процентом, начиная с которого ключ считается популярным (речь про 10%)? Это совсем несложно, но я решил, что задача о другом + с открытой ручной настройкой легче проводить исследования какие значения нужно выставить
Сделать ли возможным создание сразу нескольких анализаторов для одной хеш-таблицы? Чтобы знать топ-10 за последнюю минуту, час, день и т.п.

🏹 Возможные оптимизации

Для std::map новых бакетов использовать std::map старых, а не аллоцировать новую память под новый std::map
Значительно сократить количество std::map::find операций (при добавлении нового ключа делается std::find для каждого пакета) путем объединения std::map бакетов в один большой std::map of std::vector, где в векторе будут храниться указатели на элементы std::list<int64_t> соответствующих пакетов. Соответственно, при добавлении нового ключа мы всего лишь один раз ищем ключ в map, дальше проходимся по std::vector — если указатель null, то ключ не лежит в этом пакете, а если не null, то лежит
Сделать бакеты непересекающимися (чтобы каждый отвечал за свои 5 секунд), тогда мы резко сэкономим на операционном времени - при добавлении ключа мы будем обрабатывать только самый свежий бакет (сейчас обрабатываем все). Но при этом мы сильно потеряем точность нашего решения, потому что, если коротко — по топам непересекающихся бакетов нельзя наверняка судить о глобальном топе (топ всех топов — не топ). Однако, если мы живем в реальном мире и отслеживаем действительно глобальные продолжительные тренды (например, популярность больших тематик поисковых запросов), изменяющиеся очень медленно, то такое пренебрежение допустимо. Но, если у нас очень разнородная и непредсказуемая система, то недопустимо
Распараллелить на несколько потоков. Например, таким образом легко можно оптимизировать вставку ключа в бакеты (сейчас один поток последовательно обрабатывает каждый бакет), уменьшение значения количества встреч у всех элементов в бакете

👪 Контрибьюторы

Я рад любой идее, любому pull request и любому issue. Если у Вас что-то из этого есть — то обязательно поделитесь!

Текущий список контрибьюторов:

Никита Лисоветин, студент университета ИТМО, кафедры Компьютерных Технологий. Разработчик-программист.

📄 Лицензия

Map-Get-Fresh-Top-K GNU GPL лицензирован, как и написано в файле LICENSE.

turing228/map-get-fresh-top-k