Введение

В данной статье я хочу рассказать о своем опыте участие в конкурсе Highloadcup 2018 от Mail.ru. О конкурсе я узнал из поста на хабре, а изначальной мотивацией принять участие было желание более опытных коллег посоревноваться.

В рамках конкурса нужно было спроектировать и упаковать в Docker приложение, которое реализовывает несложное, но объемное по бизнес-логике REST API. Требуется реализовать 4 GET-запроса и 3 POST-запроса. Затем решение нужно отправить в docker-registry, после оно будет обстрелено с помощью yandex-tank разными профилями обстрела. В ЛК участника будет виден результат обстрела.

Примерный объем данных: 1 300 000 пользователей. Ограничение сервера, на котором обстреливается решение: 2 Гб ОЗУ, 10 ГБ HDD.

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

Бета-раунд

Бета-раунд нужен для того, чтобы команда mail.ru могла с помощью сообщества найти недочеты в задании, а также в системе обстрела. Я решил попробовать следующий стек: golang + reindexer

Reindexer - это inmemory БД, написанная на C++, также имеет расширение для golang. Поддерживает несколько режимов работы. Builtin - режим, когда БД хранится в самом приложении. Также есть возможность работы в серверном режиме. Статья на хабре.

Данная база показала себя как очень быстрая и удобная, но со временем я уперся в ряд ограничений:

• builtin-движок потреблял намного больше памяти, чем серверный вариант;
• документация неполная и местами противоречивая;
• группировка с помощью фасет не работает по составным индексам (или работает неочевидным образом);
• иногда демон начинал потреблять CPU и отказывался принимать запросы;
• “собственный” механизм получения данных (не sql)
• отсутствие возможности ограничивать использования оперативной памяти (из-за этого пришлось отказаться, так как в следующих раундах данные не влезли).

Отборочный раунд

В отборочный раунде было увеличено количество данных и RPS. Пришлось искать другие варианты для хранения данных. Решил попробовать golang + sphinx

Положительные стороны:

• наличие функциональных realtime-индексов;
• возможность указывать количество памяти, которое будет выделено;
• sphinxql - расширение sql-языка запросов;
• поддержка json;
• встроенная система фасет;
• наличие множественных атрибутов.

Отрицательные стороны:

• невозможность группировки по множественным атрибутам, если в группировке участвует обычный атрибут;
• Sphinx выдержал максимум 40 rps (скорее всего я не смог его правильно приготовить, но времени изучать глубже больше не было).

Далее выбор пал на golang + tarantool.

Положительные стороны:

• развернутая документация;
• поддержка sql;
• поддержка lua-скриптов для реализации логики на стороне БД;
• возможность указать количество памяти для vanyl-движка;
• компактность хранения данных в memrx-движке;
• очень быстрый для фильтрации.

Отрицательные стороны:

• поддержка sql только в alpha-версии;
• не всегда очевидная работа планировщика запросов;
• ответ в yaml не всегда удобно парсить;
• не очень удобный клиент на golang
• медленно работают запросы с группировкой.

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

После нескольких ночей появился сплав из прямых индексов по данным, в которых идентификаторы строк отсортированы, а также эмпирически выбраны наборы фильтров, для которых следует использовать fullscan.

Особенностью механизм “собственной” фильтрации было то, что мне пришлось придумать, как пересекать упорядоченные множества “слева”. Позднее я увидел в чате, что подобные алгоритмы относятся к sorted stream intersection.

Финал

Финальный раунд проходил автоматически, но для обстрела применялись “особые” волны с засекреченным rps.

Я занял 53 место. Результат мог быть лучше. если бы я использовал ОЗУ более эффективно и уместил бы все данные в память. Позднее пришла идея хранить данные в битсетах, попробую в следующий раз.

Заключение

Мне очень понравился конкурс. Это очень мощный стимул изучать что-то новое в совершенно разных областях. По итогам я узнал/изучил:

• представление о golang;
• опыт работы с goroutines;
• особенности работы GC;
• особенность алгоритма Нейгла и флаг tcp no delay при работе с сокетами;
• способы упаковки и хранения данных: delta-compression, bitset;
• особенности парсеров json;
• какие есть утечки памяти в php;
• особенности системных вызовов epoll и низкоуровневой работы;
• навык написания кода: от пилотного прототипа до дальнейшего развития в условиях проверки разных гипотез;
• Красно-черные деревья, LSM-деревья, битсеты.

Исходники

• итоговое решение: https://github.com/rsimkin/highloadcup-2018
• BitSet, который бы помог: https://github.com/rsimkin/basic-bitset