Привет, Хабр, на связи Okko! У нас одна из самых больших медиатек в России, поэтому мы постоянно работаем над развитием алгоритмов поиска и рекомендаций. Новые фичи тестируются с помощью А/Б тестов, количество фичей неустанно растет, поэтому было решено создать специальную платформу для проведения экспериментов. Она позволила бы удобно их заводить и настраивать, сплитовать трафик в онлайн-режиме и формировать результаты экспериментов.

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

Начнем с БАЗЫ

А/Б тест — это контролируемый эксперимент, при котором контрольная группа пользователей видит старый функционал сайта, а тестовая — функционал с новой фичей. Сравнивая целевые метрики, которые считаются для каждой группы, можно определить, насколько успешными были нововведения, и принять решение об их раскатке на всех пользователей.

Эксперименты проводятся над сегментами пользователей, то есть каким-то конкретным подмножеством, например:

• мужчины старше 18 с устройством на платформе Android и приложением не новее версии v42.24;

• подписчики с детским профилем, которые смотрят более 20 часов контента в месяц;

• пользователи web-версии, имеющие активную подписку.

Основной процесс эксперимента — это сплитование трафика или распределение пользователей по экспериментам и группам. Чтобы фича, которую мы тестируем, появилась на клиентском устройстве, каждый запрос должен пройти через сервис сплитования трафика, обогатиться информацией о группах, и только потом пойти в целевой сервис. Который, имея эту информацию, отобразит юзеру новый функционал.

Внутри сервиса процесс сплитования состоит из трёх этапов.

1. Определить в какие сегменты попал пользователь.

2. Для экспериментов, в сегменты которых попал пользователь, вычислить хеши, используя id юзера и соль эксперимента.

3. По полученным хешам определить, попал ли пользователь в эксперимент. Если попал, то в какую группу.

Нюанс

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

Но есть нюанс.

Технические требования оказались строгими из-за того, что все запросы клиента должны проходить через сервис сплитования. А именно:

• пропускная способность до N тысяч rps;

• доступность сервиса 99.99% времени;

• время ответа не более 10 мс при 100 активных экспериментах.

Но время ответа нашего сервиса значительно превышало требуемое… 

Чтобы не тратить время каждого запроса на поход в базу за списком экспериментов, архитектура была реализована таким образом: все активные эксперименты на старте загружаются в оперативную память, а информация о пользователе приходит с запросом. То есть внешних факторов, влияющих на скорость ответа, нет, а все «тормоза» только в CPU операциях. Что ж, крякнули, плюнули и надежно склеили скотчем пошли искать неоптимальные места.

Стандартные оптимизации

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

Slots

Сервис написан в лучших традициях чистой архитектуры: есть внешний и внутренний слои, в каждом слое свои классы для обозначения объектов. Внешний слой — интерфейс для общения по API с клиентами, в качестве базового класса там используется pydantic.BaseModel. Объекты таких классов очень удобно инициализировать из json, который приходит в каждом запросе, к тому же есть приятный бонус — автоматическая валидация входящих данных.

Внутренний слой содержит все расчеты и бизнес-логику. Здесь pydantic принес бы больше неудобств, чем пользы, ведь тратить время на валидацию объектов после каждого изменения — непозволительная роскошь в модуле сплитования. Решили использовать dataclass. Но вычислений много, извлечь максимальную скорость хотелось и из него, поэтому для каждого датакласса указали в __slots__ все используемые аргументы. (Мы начинали писать сервис на Python 3.9, когда замечательной конструкции @dataclass(slots=True) ещё не было ?)

Посмотрим на замеры: создание экземпляра класса и запись в аргумент работают на 7% быстрее со слотами. Однако доступ к аргументу оказался на 1% медленнее без слотов.

>>> %timeit UserContextWithSlots(**request_json)
>>> 954 ns ± 4.8 ns

>>> %timeit UserContextWithoutSlots(**request_json)
>>> 1.03 µs ± 94.3 ns

>>> %timeit ctx_w_slots.app_version = '12.1.1'
>>> 14.5 ns ± 0.239

>>> %timeit ctx_wtht_slots.app_version = '12.1.1'
>>> 15.5 ns ± 0.592

>>> %timeit ctx_w_slots.app_version
>>> 15 ns ± 0.337 ns

>>> %timeit ctx_wtht_slots.app_version
>>> 14.8 ns ± 0.0967

Из-за того, что полученные значения мизерные и выражены в микро- и наносекундах, погрешность довольно сильно может влиять на них. Гораздо информативнее взглянуть на изменения во времени выполнения целого запроса на расчёт сегментов. В 99 перцентиле это время стало на 11% меньше!

Ещё быстрее было бы использовать только dict или какую-нибудь реализацию frozendict, но тогда код становится менее читаемым, его сложнее проверять линтерами, и мелькают флешбеки по временам Python 2.7. Учитывая это, в качестве базового класса для внутреннего слоя оставили dataclass c использованием __slots__.

Python 3.9 vs 3.11

Исторически сложилось, что мы начали писать сервис на Python 3.9. Но к моменту, когда потребовались оптимизации, уже вышла стабильная версия Python 3.11, которая должна была стать сильно быстрее своих предшественников.

Мы поддались искушениям и решили мигрировать на 3.11. В процессе выяснилось, что некоторые библиотеки надо обновить, а от некоторых и вовсе отказаться. Было больно, но теплилась надежда, что миграция даст больший эффект, чем добавление slots. И не зря. 99 перцентиль времени, которое мы тратили на расчёт групп для пользователя, уменьшился на целых 24%!

Довольно очевидный пункт оказался очень эффективным. Но стоит закладывать риски на то, что не все зависимости могут поддерживать новые версии. Благо, сервис был ещё не в проде, поэтому мы могли себе такое позволить ?

Трейсинг

Трейсинг — очень удобный инструмент для профилирования кода. Он позволяет смотреть на ход выполнения любого запроса: где были задержки, сколько каких функций было вызвано за время обработки. Мы довольно часто пользуемся таким инструментом, а конкретно библиотекой opentelemetry, которая очень проста в использовании: чтобы начать собирать трейсы функции, достаточно повесить на неё декоратор.

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

Выглядит классно, но в случае большого rps столько трейсов невозможно отсмотреть, да и не нужно. Кроме того, трейсинг занимает драгоценные ресурсы CPU. Даже если мы будем выборочно собирать трейсы, рядом с тредом, выполняющим полезную работу, будет существовать ещё один, занимающийся их отправкой на сервер. Это видно на флеймграфе, приведённом ниже. 

Трафик для графиков симулирован искусственно, поэтому сервер мог простаивать без расчетов, что видно в левой части флеймграфа. Для корректности будем считать  за 100% CPU время без учёта этого кусочка.

12% времени CPU тратится на трейсинг, поэтому мы отключили его и оставили только на тестовом окружении.

То есть мы думали, что отключили. В начале и конце запроса было видно работу декораторов, собирающих трейсы, суммарно занимающих порядка 3% CPU.

Оказалось, что была отключена лишь отправка данных на сервер, но не их сбор. Решение пришло сразу — декоратор декоратора! Если в енвах было указано использовать трейсер, тогда он применялся как раньше. Иначе функция оставалась такой, как будто её не декорировали вовсе. 

def tracer(use_trace: bool) -> Callable[[FuncT], FuncT]:
    def decor(func: FuncT) -> FuncT:
        if not use_trace:
            return func

        return src_tracer.start_as_current_span(func.__name__)(func)

    return decor

Теперь все разработчики отдела в Okko знают об этой истории и у новых библиотек проверяют, что нужный функционал работает так, как требуется в проекте.

Валидация

Как упоминалось ранее, сервис без сайд-эффектов. Он не меняет состояния во внешних базах, и весь результат выполнения HTTP-запроса содержится только в ответе на него. Если отключить валидацию входного json, то даже в случае ошибки мы ответим 500 с пустым телом. А если не отключать её, будет 422 и такое же пустое тело ответа. Зачем-таки платить больше (временем CPU)? Можно без зазрения совести отключить на проде ресурсозатратное действие, а интеграции проверять на тестовом окружении перед релизами.

Сказано — сделано! Чтобы сильно не перевирать архитектуру сервиса и не смешать слои абстракций, заменили pydantic объекты из внешнего слоя на обычные dict’ы.

Было

Стало

Хотя это и не несёт больших рисков, всё же сервис без валидации как водка без пива. Чтобы иметь хоть какое-то понимание качества входных данных, мы включили валидацию для каждого 1000-го запроса. На метриках это не сказывается, а если интеграция вдруг поломается, рейт ошибок 422 укажет нам на это.

Если в вашем сервисе тратится много времени на валидацию, задумайтесь, возможно и вам поможет такое решение!

json vs protobuf

Результаты вычисления сегментов для каждого юзера мы логируем в Kafka, а затем они перекладываются в Clickhouse для проведения аналитических исследований и запуска некоторых технических джоб. Конечно, осуществлять логирование из основных worker-процессов было бы непозволительно долго, для чего был создан отдельный процесс, занимающийся только отправкой данных в Kafka (об этом подробнее в одной из следующих статей).

Внешние требования таковы, что в Kafka должны передаваться данные в формате protobuf. На один запрос может формироваться несколько десятков объектов, требующих сериализации, потому что мы логируем участие юзера в каждом эксперименте для удобства оперирования этими данными. Поэтому есть два пути: сформировать protobuf в worker’е и передать данные процессу, который занимается отправкой, или сразу передать данные специализированному процессу и поручить ему сериализацию и отправку.

Второй путь интуитивно кажется более оптимальным для worker’а. Но надо иметь в виду, что для передачи данных между процессами их тоже нужно сериализовать. Классический путь – json. Итого, нужно определить что быстрее — конвертировать в protobuf или в json.

На примере представлен датакласс, в котором реализован метод __bytes__, под капотом сериализующий в protobuf, и его конкурент json. Как видно, protobuf примерно в 8 раз медленнее json’а. Поэтому решили в worker’е сериализовать данные в json для передачи между процессами, а уже в соседнем процессе упаковывать в protobuf.

exp_part = ExperimentParticipation(
    eventName=assigned_enum,
    userId=123,
    profileId=None,
    groupName=control_enum,
    expId=1,
    expRunId=0,
    userContext=some_long_string,
)
exp_part_json = {
   'eventName': 'group_assigned',
   'userId': 123,
   'profileId': None,
   'groupName': 'control',
   'expId': 1,
   'expRunId': 0,
   'userContext': some_long_string,
}

>>> %timeit bytes(exp_part)
>>> 10.5 µs ± 370 ns
>>> %timeit orjson.dumps(exp_part_json)
>>> 1.29 µs ± 40.7 ns

Продвинутые оптимизации

Далее рассмотрим несколько оптимизаций, которые мы придумали, учитывая специфику нашей сплитовалки.

Оптимизация проверки версий

На флеймграфах выше видно, что бОльшая часть ресурсов CPU приходится на расчёт сегментов (segments_resolve). Эта часть кода претерпела множество оптимизаций, о которых мы расскажем в отдельной статье. А сейчас лишь небольшой интересный кусочек.

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

Первая реализация оператора сравнения версий проводилась в лучших традициях Python-разработки: нашли библиотеку, которая решает задачу, проверили количество звездочек в git’e и успешно внедрили в проект. Однако флеймграф показал, что простая на вид операция занимает порядка 1,5% от всего времени вычисления сегментов. Пришлось разбираться, как под капотом производятся проверки.

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

Посовещавшись с коллегами, мы выяснили, что в компании есть правила формирования версий: целые числа, разделенные точкой. Зная это, достаточно было преобразовать строки версий в тюплы целых чисел и сравнить их. Любимый Python делает это очень быстро.

В результате оптимизации оператора сравнений, получили ускорение вычисления сегментов на 1%.

Оптимизация расчета групп

Чтобы объяснить суть следующей оптимизации, расскажу еще немного деталей сплитования. Эксперименты проводятся только на части трафика, и только в слоях, которые помогают избегать ситуаций, когда эксперименты зависимые. Пользователь не должен участвовать сразу в обоих экспериментах.

Объясню на примере. Слой определяется своей солью (некоторой строкой) и состоит из 10 тысяч бакетов. Создается эксперимент с 5% трафика в группе А и 10% трафика в группе Б. Для этого в слое выделяется 50 и 100 бакетов для групп А и Б соответственно. Эти бакеты зарезервированы и не могут быть выделены другому эксперименту. Если понадобится создать зависимый эксперимент, в этом же слое будут зарезервированы другие бакеты.

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

hash(user_id, salt) % BUCKETS_NUM

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

Для компактности бакеты в группах хранятся в виде списка блоков, где блок определяется индексом первого бакета и количеством идущих вслед за ним бакетов. Например, для вышеописанного случая в группе A может храниться единственный блок бакетов 0-49, а может быть два, 0-10 и 11-49, или три и т.д. Разбивка бакетов по блокам строго не регламентирована, поэтому вычислять группу эксперимента, проходясь по всем блокам, избыточно. Ведь блоков может быть много, а бакет в слое, в который попадет юзер — один-единственный.

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

bucket_id = splitter.split(entity=user_id, layer=experiment.salt, buckets_count=BUCKET_MAX_COUNT)

for name, info in experiment.groups.items():
    if bucket_id in info: # проверка на вхождение бакета в каждый из блоков
        return name

Кто мы? Разработчики! Чего мы хотим? Константный алгоритм!

Конечно, мы так не рассуждали, но оказалось, что для более оптимального алгоритма отлично подойдет хеш-таблица, которая будет хранить номер бакета и название группы. Эту таблицу мы поместили в атрибуты эксперимента и с помощью метода get_group_name в одну строку получали название группы:

return experiment.get_group_name(bucket_id)

Безусловно, такое ускорение сопровождается дополнительными тратами оперативной памяти, но в нашем случае память стоит дешевле времени ?

Итог

Как в фильмах, где каждая мелкая деталь, каждый кадр и каждая реплика актера влияют на общее впечатление от картины, так и в процессе построения высоконагруженного сервиса, небольшие оптимизации и усовершенствования могут привести к грандиозным результатам. Это лишь первая часть многосерийной драмы про оптимизацию сервиса сплитования в Okko. А что было дальше – читайте в следующих статьях!