Платформа ценообразования Авито

Решение команды Calculus Enjoyers

Backend - Golang

Frontend - HTML/CSS/JavaScript

Test - Python
Вы можете протестировать работу сервиса поднимая на локальном устройстве(все нужные зависимости в ридми каждой директории)

Содержание

• Платформа ценообразования Авито
  • Решение команды Calculus Enjoyers
• Содержание
• Technologies & Tools
• Фишки
• UI
  • Веб-сайт поддержки аналитиков от CalculusEnjoyers
    • Создание Хранилища
    • Манипулирование Матрицей Цен
    • Загрузки
• Архитектура решения кейса
  • Диаграмма работы сервисов
  • Оптимизации
  • Алгоритм get_price (подробно)
• Не функциональные требования:
• Тестирование продукта
• Инструкция запуска

Technologies & Tools

1. Языки: Golang, Python, JavaScript
2. Системы хранения данных: Redis, PostgreSQL
3. Конфиги: JSON, YAML
4. Скрипты: bash
5. Сетевые протоколы, утилиты: https, curl

Фишки

1. User Interface для аналитиков с возможностью точечного изменения значений в существующих матрицах цен. Удобное изменение baseline и discount матриц позволяет корректировать storage, не закрывая браузер.
2. Сервис сбора метрик работы сервиса, данные выводятся напрямую аналитику.
3. Оптимизированная работа с таблицами возврата цен.
4. Использование Redis system для быстрого ответ пользователю.
5. Тестирование продукта нагрузочно
6. Unit тесторование продукта
7. Персистентность, при перезагрузке сервиса восстанавливаются данные таблиц
8. Отсутствие моргающих цен - при обновлении цены, ее выдача будет доступна пользвателям сразу
   (менее чем за секунду)

UI

Веб-сайт поддержки аналитиков от CalculusEnjoyers

Веб-сайт предоставляет инструменты для управления аналитикой. Ниже приведено описание основных разделов и команд, доступных на сайте:

Создание Хранилища

• Описание: Позволяет пользователям ввести id базовой матрицы и id сегментов с соответствующими им id матриц скидок.
• Поля для заполнения:
  • Введите id базовой матрицы в предоставленное поле ввода.
  • Укажите id сегмента и соответствующий ему id матрицы скидок.
  • Нажмите кнопку "+" для добавления большего количества пар id сегмента и id матрицы скидок.
  • Нажмите кнопку "Показать JSON-данные", чтобы отобразить JSON-объект с введенными данными.

Манипулирование Матрицей Цен

• Описание: Позволяет пользователям обновлять или вставлять строки в матрицу, искать id матрицы в менеджере цен и получать название матрицы из менеджера цен.
• Поля для заполнения:
  • Для обновления или вставки строк:
    • Введите id матрицы в соответствующее поле ввода.
    • Укажите id локации, id категории и новые цены для строк, которые необходимо обновить/вставить.
    • Нажмите кнопку "+" для добавления дополнительных строк.
    • Нажмите кнопку "Обновить таблицу", чтобы применить изменения.
  • Для поиска id матрицы в менеджере цен:
    • Введите название матрицы в поле ввода.
    • Нажмите кнопку "Сделать запрос", чтобы проверить существование матрицы или получить автоматически присвоенный id.
  • Для получения названия матрицы из менеджера цен:
    • Введите id матрицы в поле ввода.
    • Нажмите кнопку "Сделать запрос", чтобы получить название матрицы.

Загрузки

• Описание: Предоставляет ссылки для загрузки графа локаций (дерево локаций с их id) и графа микрокатегорий (дерево категорий с их id).

Архитектура решения кейса

1. MultiUser price_retrieval - сервер, позволяющий получать стоймость по локации и категории для пользователей.
2. MultiUser price_management - сервер, напрямую взаимодействующий с таблицами PostgreSQL, созданный для ответов на запросы retrieval сервера, а также API для аналитиков, позволяющий изменять цены в таблицах, обновлять storage (baseline и discount таблицы).
3. MultiUser price_ui - веб-приложение для аналитиков с графическим интерфейсом, который позволяет проводить манипуляции с текущими таблицами и получать информацию(подробнее выше).

Диаграмма работы сервисов

Оптимизации

1. Используем кеширование на пути дерева (категорий, локаций), оптимизация отлично себя показала на нагрузочных тестах увеличив RPS с 85 до 350, кеш мы чистим при изменении исходной таблицы или раз в полчаса как написано ниже (с указанием причины). Кроме того, дерево поиска сначала проверяет приоритетные таблицы (с дисконт-сегментами для user_id, которые мы передаем из UI в формате JSON).

2. Разделение таблиц, эта оптимизация дает ускорение на больших объемах данных, так как мы на каждый запрос поиск данных происходит в таблице размером на один-два порядка меньше, кроме того, часть самых частых запросов закешировано. В этой части мы делим таблицу по microcategory_id ( мотивация ниже), но также имеем возможность в два действия изменить matrix_size, и делить таблицу на matrix_size элементов(сейчас тесты подобраны чтобы делить на интересные нам таблицы), в production на примерно равные таблицы и когда произведено много запросов set_price добавлено делаем перебалансировку в ночное время суток, когда трафик снижен до минимальных значений.

3. Для каждого пользователя мы знаем его скидочные категории, и мы их выгружаем при создании price_retrieval. Таким образом когда мы делаем запрос для пользователя мы уже за O(1) знаем надо ли нам ходить в скидочный сегмент или нет. Это достаточно сильная оптимизация, так как если для пользователя нет скидок, то и смысла ходить нет, а такое обычно у большинства.

4. Используем оптимизированные API, наши сервера слушают пользователей асинхронно, поэтому имеется возможность в MultiUser обращения.

5. В качестве БД была использована PostgreSQL, как архитектура, бесплатная, простая к использованию и показывающая отличный perfomance в скорости работы относительно других OpenSource решений (выводы сделаны на основе графиков YaTalks2023 и ресурсов habr)

   • NoSQL требует больше памяти, хоть может быть выгоден для небольшого числа данных(как, например, у нас кеш для дерева), поэтому был сделан выбор в пользу SQL, чтобы соблюсти баланс скорости ко времени, также рассматривалась MySQL (со схожими показателями).
   • При разделении таблицы, то как мы написали скрипт согласно документации вставка в основную таблицу будет проходит также не более чем по matrix_size элементам, и вставка в нашу таблицу разбиения также вставляет в основную(не надо делать два разных запроса к бд) Таким образом благодаря выбору PostgreSQL у нас есть возможность сделать всего 1 запрос на вставку в нужную область
   • Хранение данных в файлах, например, JSON - очень медленный способ для такого объема данных, и вставка в них работает за O(длина файла), в отличие от предыдущих технологий.

Алгоритм get_price (подробно)

1. Пользователь для получения цены задает запрос в сервис price_retriver. В начале алгоритма мы совершаем подъем по location_tree и microcategory_tree.
2. На первом шаге используем алгоритм подъема с оптимизацией в виде кеширования на всем пути подъема по дереву (если мы получили ответ в i вершине, а начали в j, то кешируем ответ для всех вершин на пути с j по i).
3. Если вершина была в кеше, то возвращаем ответ и не поднимаемся дальше. В качестве кеша используем систему Redis, тк она наиболее быстрая и идеально подходит для нашего дерева, в котором более 250'000 вершин.
4. Если запрос не в кеше, мы его поместим во всех вершинах, находящихся на пути, в процессе возвращения ответа. А пока его там нет, идем в connector, который кеширует дерево, и отправляет запрос в сервис, общающийся с DataBase.
5. Запрос попадает в сервис price_manager по ручке get_price в виде http запроса, в котором передается 3 аргумента.
6. Внутри сервиса стоит наша главная оптимизация. Так как исходная baseline_matrix очень большая, то и поиск по ней происходит долго. Мы разбиваем ее на матрицы (которые тоже автоматически создаются в нашем сервисе) меньшего размера (в среднем если исходная матрица 250к строк, то дополнительные около 25к строк). Поиск требует загрузки в память, а разбиение на части позволяет не загружать всю таблицу в память. Особенно эффективно, когда удаётся разбить так, что категории, к которым происходит частые обращения попали в одну партицию.
7. Внутри самого сервиса мы однозначно умеем сопоставлять за O(1) (за счет matrix naming) имя матрицы, в которую отправить запрос, и, таким образом, мы имеем возможность для всех запросов поиска цены ходить в определенную матрицу.
   • Разбитие на матрицы происходит по параметру microcategory_id, так как размерность дерева этого параметра примерно совпадает с размерностью дерева локаций, а общая таблица представляет собой их декартово произведение (в общем случае).
8. Как только к нам пришел элемент, мы по цепочке, как показано, отдаем пользователю. Все клиенты к обоим серверам подключаются асинхронно и с помощью стресс-тестов мы смогли замерить RPS нашей системы. На всех этапах мы передаем небольшие запросы и лишь ответ пользователю собираем в виде JSON файла.

Не функциональные требования:

1. Сервис имеет все возможности для масштабирования, так как в нашей реализации несколько микросервисов связанны между собой исключительно по API, и не знают о внутреннем устройстве друг друга. Внутри сервисов нет "magic const" и захардкоженных map, вместо этого в config сервера пердаются названия JSON-файлов, где собрана основная информация (при желании имеется возможность JSON заменить на YAML|SQL|NoSQL), но для тестирования с небольшим числом userов это - идеальный вариант. Также наши сервисы поддерживают логгирование ошибок при запросах и обработке, что может оказать существенную помощь в дебаге и масштабируемости на всех этапах использования нашего сервиса.

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

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

4. Отдача как показывают stress test для 99.9% пользователей происходит менее чем за 200мс.

5. Сервис также крутится на машине, и любые ошибки его не убьют(также есть back up tables) тк они обрабатываются, а пользователю вернется лишь отсутствие ответа. В остальное время он доступен.

6. На протяжении всей работы сервиса собираются метрики с помощью prometheus. Подсчитывается RPS и время работы каждого запроса к price_retriever, price_manager, обрабатывается информация о cache misses. Через удобный графический интерфейс grafana можно мониторить состояние сервиса.

Тестирование продукта

1. Командой были написаны stress тесты, которые представляют выбор из доступных loc_id и micro_id для больших baseline_matrix_table, discount_matrix_table, где размер baseline - 250'000 строк, а discount - 4000, также выбраны userid положены в JSON, чтобы была полноценная симуляция реального мира. На таких тестах при запоминании кеша происходит постепенный рост RPS с 300 до 500 с вышеперечисленными оптимизациями.
2. Детерминированные тесты, находящиеся в каждом сервисе, для проверки корректности выдачи цены.

Инструкция запуска

Подробные README по запуску находятся в соответствующих папках репозитория. Названия папок совпадают с названиями сервисов.

1. price_retrieval - сервис получения цен для пользователей
2. price_management - сервис работы с базой данных, отвечающий за запросы аналитиков и выдаче по запросу get_price (тема кейса)
3. price_ui - сервис для аналитиков с GUI
4. data_base_generation - скрипты (НЕ нужно запускать, базы данных создадутся автоматически при запуске price_management) для создания тестовых DataBase (3 таблицы discount_matrix и 3 таблицы baseline_matrix для теста корректности, предоставленные в приложениях к кейсу).