Фильтрация JSON: как мы проводили конкурс на самый быстрый алгоритм
Привет, меня зовут Костя Плешаков, я Архитектор в Quadcode. В статье расскажу, как мы организовали конкурс, который помог решить проблему исключения некоторых данных (в нашем API) в процессе отправки на фронт. В результате мы получили высокопроизводительный алгоритм фильтрации JSON с использованием векторных инструкций Intel® AVX2.
Исторически сложилось
Начиная с 2014 года наша компания занимается разработкой собственной торговой платформы. Примерно в 2016 году в период бурного роста мы осознали, что выбранная до этого монолитная архитектура больше не позволяет нам развиваться и приняли волевое решение обратиться к набирающей в то время популярность микросервисной архитектуре. К сожалению, совершая этот переход мы допустили ряд стратегических ошибок, одна из которых и стала причиной появления решения, о котором мы расскажем в этой статье.
При проектировании взаимодействий между микросервисами полезно разделять их на внутренние (backend) и внешние (их обычно называют BFF — «backend for frontend»). Внутренние микросервисы взаимодействуют только друг с другом и реализуют непосредственно бизнес-логику со всей сопутствующей механикой. BFF используется frontend«ом и, если говорить упрощённо, выполняет роль адаптера всей микросервисной системы для нужд и удобства frontend. Это позволяет снизить влияние backend и frontend друг на друга.
Как правило, разработкой BFF занимаются команды, которые пишут и сам frontend, но в нашем случае всё сложилось немного не так. В погоне за скоростью разработки и внедрения новых фич мы напрямую соединяли frontend с внутренними сервисами, которые реализуют бизнес-логику, в итоге оказавшись заложниками зафиксированных в этих взаимодействиях интерфейсов. Проблема осложнялась ещё и тем, что многие интерфейсы использовались не только frontend«ом, но и другими backend-сервисами, а также инфраструктурой аналитики и backoffice по опять же историческим причинам.
Для frontend«a, аналитики и backoffice нужны разные наборы данных. Поскольку часто мы использовали один и тот же интерфейс (например, событие, связанное с торговой сделкой), то данные для всех потребителей просто объединялись.Это приводило к росту бессмысленного трафика для frontend«a, но зато экономило, как нам казалось, много сил. В один прекрасный момент мы столкнулись с ситуацией, когда в одних из самых высоконагруженных событиях нашей системы потребовалось передавать чувствительную информацию, которую нельзя «выпускать наружу». Разумеется, это произошло в тот самый момент, когда ни на backend, ни на frontend не было ресурсов для того, чтобы перевести хотя бы это одно событие на концепцию BFF.
Фильтрация
Мы приняли очередное волевое решение — купировать проблему путём внедрения особого механизма фильтрации данных. Все сообщения в нашей системе кодируются в формате JSON, структура сообщений, к счастью, уже почти везде формализована и описана на специальном DSL (domain specific language). Это позволяет нам на уровне DSL помечать те или иные поля в сообщениях как «чувствительные», что доводится до сведения механизма фильтрации, который в свою очередь убирает всё лишнее из данных на их пути к frontend.
Прелесть этого решения, к сожалению, чисто алгоритмическая: если предположить, что на вход фильтрации всегда приходит корректный JSON, то для самой фильтрации совсем не обязательно производить его полноценный парсинг. В общем-то мы сразу догадались, что можно изобрести не очень сложный алгоритм, который за один проход по JSON-документу уберёт из него всё лишнее. Причем, для этого даже не нужен большой объем дополнительной памяти — раз уж фильтрация не может сделать документ больше, то все изменения можно произвести в том же участке памяти, где записан исходный JSON документ. Мы пришли к выводу, что именно в таком виде задачу можно решить достаточно эффективно с точки зрения производительности, и фильтрация всех данных на пути к frontend не потребует от нас серьёзных затрат на вычислительные ресурсы.
Главный недостаток решения — оно, конечно, настоящий костыль, но надёжно локализованный. Его внедрение не должно привести к сильному увеличению сложности системы или как-то помешать нам перейти на концепцию BFF в будущем. Этот переход мы теперь планируем в спокойном режиме в рамках более серьёзных архитектурных изменений системы.
Конкурс
Преимуществом решения является и то, что разработка и внедрение фильтрации почти не требуют внимания ни со стороны backend, данные из которого надо фильтровать, ни со стороны frontend. Задачу можно решить силами отдельной команды, а у нас как раз есть подходящая — команда, разрабатывающая наш внутренний транспорт и гейты для websocket подключений.
Разумеется, кроме алгоритма фильтрации нужно разработать всю инфраструктуру для его работы — это как раз та часть задачи, которую в нашем случае эффективно могли сделать только в транспортной команде. А вот разработку самого алгоритма фильтрации можно было сделать и за её пределами, так как это хорошо локализуемый алгоритм.
Чтобы не решать в очередной раз ресурсные задачи, мы объявили конкурс среди разработчиков на написание такого алгоритма. К счастью, эта задача могла быть успешно выделена из общего объёма работы, а также была уж очень интересна алгоритмически. В результате конкурса мы получили прекрасное решение, но обо всём по порядку.
Анонс конкурса
Наше руководство быстро осознало, что проведение конкурса с денежными призами не обойдётся компании дороже, чем выплата зарплаты разработчикам за эту же работу. Также в нашей компании очень серьёзно относятся к формированию такой рабочей среды, которая помогает мотивировать сотрудников. Другими словами, мы любим проводить классные мероприятия, и проблема чаще всего только в том, чтобы их придумать, а не в том, чтобы найти на них средства.
В итоге мы договорились на общий призовой фонд в 300 тысяч рублей, который решили разделить на три равные части. Дело в том, что большая часть разработчиков у нас пишет на Golang, но внутренний транспорт, включая место для вставки фильтрации, написаны на C++. Мы решили, что Golang разработчики могут решать задачу на своём языке, а при необходимости мы без особых проблем перепишем решение на C++. Поэтому у нас появилось два приза по 100 тысяч рублей — за первое место на C++ и первое место на Golang.
Оставшиеся 100 тысяч рублей мы решили использовать для мотивации как можно большего числа разработчиков принять участие в конкурсе и сделали это следующим образом. Остаток призового фонда распределялся между всеми участниками, которые предоставили работающее решение, при этом они сами определяли, каким образом приз должен быть распределён. Мы попытались добавить в этот процесс немного айтишного веселья и затеяли что-то вроде игры в дилемму заключённого.
После определения победителя мы провели среди всех остальных участников серию тайных голосований, в каждом из которых они выбирали между ответами «да» и «нет». Условие было такое: как только большинство голосов набирает ответ «да», голосование заканчивается. Вся серия вопросов была озвучена заранее:
«Разделить ли остаток между двумя случайно выбранными участниками?» Большинство с небольшим перевесом проголосовало против.
«Разделить ли остаток между четырьмя случайно выбранными участниками?»
Тут почти все проголосовали за.«Разделить ли остаток между всеми участниками?»
Вариант оказался не самым популярным.
Для того, чтобы провести голосование тайно, мы решили пойти на очередную гиковскую хитрость и попросили участников писать в чат md5 сумму от своего ответа с солью: сначала все писали свои хеш-суммы (фиксируя таким образом свой ответ), а потом раскрывали ответ с солью. Мы быстренько проверяли хеш-сумму и убеждались, что участники не изменили своё решение, глядя на решения других конкурсантов.
Чтобы выбрать случайных победителей, мы хотели придумать какой-нибудь криптографический протокол, но наши помощники из HR уговорили взять более наглядное решение в виде вращающегося барабана, найденного где-то в Интернете. Было немного грустно отказываться от духа безудержной ИТ-вечеринки, но на мероприятие собралось много коллег из других департаментов, так что, наверное, это было правильным решением.
К сожалению, мы не очень хорошо подготовились в плане выражения интересной дилеммы в качестве игры для распределения остатка призового фонда, но сама идея оказалась рабочей — это позволило привлечь для участия в конкурсе даже тех разработчиков, которые точно знали, что не смогут занять первое место.
Сложности в организации конкурса
Несколько слов о проблемах технического характера при организации конкурса.
Очень сложным оказалось подготовить автоматизированную инфраструктуру для регулярного подведения промежуточных итогов. Беглый поиск готовых решений ничего нам не дал, но это было ожидаемо — обычно в конкурсах выдаются очки за решение многих задач, а время ограничивается очень грубо, у нас же задача была одна, а время надо было измерять очень точно, что само по себе является не такой уж простой задачей.
Делали мы всё «на коленке», поэтому в качестве инфраструктуры выдали каждому участнику собственный git-репозиторий с заготовкой программы, которая умела принимать тестовые данные, выдавать результат и замерять среднее время работы, включая вычисление среднеквадратичного отклонения, которое мы планировали использовать для определения спорных ситуаций.
На специальном сервере, который обычно использовался для performance-тестирования, мы запустили простенький скрипт, который непрерывно обходил все репозитории, собирал статистику работы решений и подготавливал отчёт. Этот отчёт использовался для генерации статической HTML-странички с рейтингами участников (отчёт раздавался обычным nginx в докере). Забавным оказалось то, что некоторые коллеги, которые не принимали участия в конкурсе, вызвались переверстать нам страничку с рейтингами, и вокруг этого выросло вообще отдельное обсуждение. Такой подход годится только тогда, когда есть стопроцентная уверенность, что коллеги не будут мухлевать — с этим проблем у нас не возникло. В будущем при проведении конкурсов нужно будет более серьёзно отнестись к такого рода автоматизациям и сделать их заранее.
Другая сложность нас поджидала при подготовке тестовых данных. Тут даже говорить особо нечего — генерировать случайные JSON и подходящие для них случайные условия фильтрации так, чтобы это всё было релевантно реальным данным, действительно сложно. Этим тоже надо заниматься заранее.
И наконец третий вывод: мы правильно решили, что сама задача фильтрации отлично подходит для конкурса с любых точек зрения, но совершенно недооценили объём технической работы, которую нужно было проделать для организации конкурса. В итоге конкурс можно считать выгодным для бизнеса только с учётом элементов team building при его проведении — то есть кроме эффективного решения задачи мы ещё очень классно провели время.
Слово победителю
Владимир (так зовут нашего победителя, также Вова автор статьи TDD есть опиум для народа) поделился рассказом о том, какие варианты рассматривал и что в итоге выбрал. Стоит заметить, что он был единственным участником на C++, но его алгоритм оказался немного быстрее лучших решений и на Golang.
Первый подход был абсолютно стандартным — взять первый попавшийся парсер JSON, с его помощью распарсить входные данные, потом пройтись и удалить все элементы, которые не попали в whitelist и сериализовать JSON обратно. Т.к. тесты были подготовлены организаторами конкурса, это было относительно просто и быстро сделать. Правда, производительность такого решения оставляла желать лучшего.
Второй подход был основан на том факте, что JSON парсеры типично пытаются распарсить значения. К примеру, если встречается число, его разбирают и валидируют. А по условиям конкурса это было не обязательно и даже мешало. Для типов double, например, где десериализация и сериализация часто происходила с небольшой потерей точности, на выходе получали не то, что на входе, что приводило к падению тестов. Для фильтрации достаточно было понимать, где начинается и кончается токен, и что это за токен (e.g., ключ в словаре или значение в массиве). Также гарантировалось, что входящие JSON-файлы всегда имеют правильную структуру, поэтому проверять её тоже смысла не было.
Поэтому было принято решение написать свой маленький парсер безо всяких проверок, фактически — просто токенизатор. Это дало очень существенный прирост. Постепенно в процессе оптимизаций удалось совместить токенизацию и фильтрацию вместе — в один проход, без дополнительных выделений памяти. Т.е. «идём» по данным побайтово, анализируем символы и как только «понимаем», что токен закончился, проверяем его на попадание в whitelist. Если не попали в этот список, отбрасываем и идём дальше. Если попали — записываем этот токен сразу после предыдущего валидного токена. Т.к. выходной JSON гарантированно меньше или равен входящему, мы можем писать в тот же массив данных, из которого читаем, благодаря чему не пришлось отдельно выделять память под результат.
Несмотря на то что я постарался максимально оптимизировать всё что мог, в один прекрасный день я увидел на дашборде с результатами, что моя реализация на C++ медленнее, чем вариант коллег, которые писали на Go. Вскоре в чате проскочила информация, что для достижения такого результата они использовали simdjson-go — реализацию парсера на основе инструкций AVX2.
С багажом новой информации я приступил к третьему подходу — парсеру на AVX2. Но поскольку знаний реализовать это всё самостоятельно не хватило, вскоре я взялся за изучение, а потом и за вырезание кусков из simdjson, этой же библиотеки, только на C++. Результатом стал токенизатор «по мотивам» simdjson, кстати, он получился на удивление маленьким — менее 200 строк. Его работа немного отличалась от того, что было на предыдущем этапе: он разбирал сразу весь JSON, сохраняя в массив начало каждого найденного токена (а для строк ещё и конец, чтобы не мучаться и не искать конец строки с учётом escape символов). Далее, как и в предыдущем случае, идем по тексту при помощи индекса, находим начало следующего токена, проверяем, фильтруем и т.п. Этот подход и стал тем, что подарил мне победу.
Далее, ради интереса я при помощи утилиты c2goasm портировал токенизатор с C++ на Go, а фильтрацию написал самостоятельно. Поскольку моя версия парсинга JSON была переработана под задачу фильтрации, а коллеги, как я понял, использовали исходную версию из simdjson-go, то и для варианта на Go у меня получился самый быстрый результат.
Итоги
В результате мы получили восхитительный алгоритм фильтрации, который использует расширенные инструкции AVX 256 процессора Intel и на наших серверах выдаёт производительность чуть меньше 10 гигабит в секунду на одном ядре (наш стандартный процессор: Intel® Xeon® CPU E3–1270 v6 @ 3.80GHz). Теоретически это позволяет нам фильтровать весь трафик, увеличив аппаратные мощности для обработки соединений пользователей менее, чем на 10% в худшем случае. В конце концов мы включили фильтрацию почти везде, где нам нужно, и вообще не заметили какой-либо деградации в метриках — докупать оборудование не пришлось.
Алгоритм фильтрации мы планируем выложить в открытый доступ, но для этого нужно провести определённую работу по его выделению и оформлению в библиотеку. Вы можете помочь нам ускорить этот процесс, выразив заинтересованность в комментариях, а если вы понимаете, что такой алгоритм — это именно то, что вам нужно, то не стесняйтесь и пишите в комментарии или мне напрямую на почту.
