Работа в рамках предмета "Проектирование высоконагруженных приложений" программы "Веб-разработка" образовательного центра VK в МГТУ им. Баумана
Выполнила Валова София
- Тема и целевая аудитория
- Расчет нагрузки
- Глобальная балансировка нагрузки
- Локальная балансировка нагрузки
- Логическая схема БД
- Физическая схема БД
- Алгоритмы
- Технологии
- Обеспечение надежности
- Схема проекта
- Выбор оборудования и хостинга
Темой курсовой работы выбран агрегатор такси Яндекс.Такси
Аудитория
Согласно отчетам за второй квартал 2024 год аудитория сервиса составляет 49 млн пользователей в месяц, с увеличением аудитории на 16% от года к году 1
Основная аудитория это Россия, но так же сервис предоставляет услуги еще в 17 странах
Функционал
- Указать адрес
- Динамический расчет стоимости и времени поездок
- "Маркетплейс" водителей и пользователей
- Выйти на линию
- Принять заказ
- Рейтинг и отзывы на водителей
- Оформить заказ
- Отслеживание местоположения такси
- Просмотр информации о заказе
- Написать сообщение в чат
- История заказов
Продуктовые решения
- Предложить точку останова, если это сэкономит время и деньги пользователю
- Совместные поездки
- Кэшбэк баллами
- MAU - 49 млн
- DAU - 4 млн (в 2020 году 2), предположим, что сейчас 5 млн
- Средний размер хранилища пользователя:
| Хранимые данные | Размер единицы | Количество на пользователя | Размер на пользователя |
|---|---|---|---|
| Персональные данные (ФИО, почта, пароль и т.д.) | 1 КБ |
1 |
1 Кб |
| Аватар | 200 Кб |
1 |
200 Кб |
| Сохраненные адреса | 0,5 КБ |
6 |
3 Кб |
| История поездок* | 60 Кб |
150** |
8800 Кб |
*Расчет поездки: адреса, информация о водителе, стоимость, машина, дата, статус поездки, метаданные, маршрут и другое = 60 Кб
** За 2023 было совершено 3,29 млрд поездок, яндекс такси занимает 80% рынка, тогда количество заказов через данный сервис составляет 2,5 млрд3 Получается в месяц 208 млн поездок, если MAU 49 млн, то в среднем совершается 4 поездки в месяц -> 50 поездок в год. Предположим, что средний пользователь пользуется такси 3 года -> 150 поездок
Итого - 9 Мб * 50 млн = 430 Пб
- Среднее количество действий пользователя, водителя в день:
Оформление заказа:4 заказа/мес / 30 сут/мес = 0,13
Посмотреть стоимость:0,13 * 3 = 0,4предположим пользователь 2 раза проверит стоимость такси, на третий раз закажет
Выйти на линию:25
Принять заказ:25
Отслеживание местоположения такси:3*4 / 30 = 0,4пользователя проверит местоположение 3 раза - после оформления, когда пройдет половина от времени, за которое такси должно приехать, и за 5 минут до приезда
Просмотр информации о поездке:2*4 / 30 = 0,27пользователь совершит действие два раза: первый - чтоб ознакомитсья с машиной, второй - уточнить модель и номер машины
- Размер хранения в разбивке по типам данных
| Тип | Размер |
|---|---|
| Фото | 9 Тб |
| Данные о поездках | 140 Тб |
| Данные о пользователях и таксистах | 47 Гб |
- Сетевой трафик
- Пиковое потребление в теченнии суток (в Гбит/с) - разбивка по существенным типам трафика (для выбора сетевых интерфейсов)
- Суммарный суточный (Гбайт/сутки) - разбивка по существенным типам трафика (опционально, для подсчета стоимости хостинга)
| Тип | Суммарный | Пиковый |
|---|---|---|
| API | 50к запросов * 86400 с * 2 Кб / (1024 * 1024) = 8200 Гбайт/сутки |
82000 * 8 бит * 2 = 100к Гбит/с |
| Статические файлы | 80 запросов * 86400 с * 200 Кб / (1024 * 1024) = 1300 Гбайт/сутки |
1300 * 8 бит * 2 = 20к Гбит/с |
- RPS в разбивке по типам запросов (запросов в секунду) - для основных запросов
| Тип | Среднее | Пиковое |
|---|---|---|
| Оформление заказа*** | 80 | 160 |
| Запрос на расчет стоимости поездок | 240 | 480 |
| Выйти на линию | 80 | 160 |
| Отказаться от поездки | 7 | 10 |
| Отправка местоположения водителя **** | 40к | 80к |
***7 млн поездок в день - 80 в секунду, в 2015 году пиковое значение было в 2,1 раза больше среднего 4
****7 млн поездок в день, 25 поездок в день делает водитель => 280 000 водителей. Из наблюдения за экраном телефона таксиста во время поездки, задержка по отображению перемещения 2-3 секунды. Тогда пусть данные о местоположении отображаются каждые 2-3 секунды => в секунду ~100к запросов, будем также считать, что в пик работает 80% водителей (rps 80к пик, среднее в 2 раза меньше)
taxi.yandex.ru - основной домен яндекс такси
ride.taxi.yandex.ru - запросы, связанные с поездками: расчет цены, "маркетплейс" водителей и пользователей
pro.taxi.yandex.ru - запросы из Яндекс Про (приложение для водителей яндекс такси)
user.taxi.yandex.ru - запросы от пользователей
Для обслуживания запросов по Россиии ДЦ расположим в Москве, Новосибирске, из средней азии запросы так же идут в Новосибирск, для европейских, африканских стран и ОАЭ - в Стамбуле.
66% пользователей Яндекс Такси из России, значит на Россию приходится 4,62 млн поездок/день и 2,64 млн пользователей. На остальные страны приходится 2,38 млн поездок/день и 1,36 млн пользователей/день.
Количество поездок в центральной России составляет 60%.
ДЦ в Москве обслуживает все запросы центральной России и является основным ДЦ.
Локальные ДЦ принимаеют запросы от ride.taxi.yandex.ru и user.taxi.yandex.ru, то есть запросы на расчет цены поездок, составление маршрутов и запросы от водителей. Запросы от юзеров идут в Московский ДЦ.
| ДЦ | Млн пользователей/день | Млн поездок/день | RPS | Запросы |
|---|---|---|---|---|
| Москва | 1,6 | 2,8 | 20к | Все для центральной России и действия юзеров |
| Новосибирск | 1 + 0,68 = 1,68 |
1,8 + 1,1 = 2,9 |
13 + 8к = 21к |
Расчет цены поездок, составление маршрутов, запросы от водителей |
| Стамбул | 0,68 | 1,1 | 8к | Расчет цены поездок, составление маршрутов, запросы от водителей |
RPS по ДЦ и запросам
| ДЦ\Запрос | Расчет стоимости поездки | Выйти на линию | Оформить заказ | Отправка местоположения водителя |
|---|---|---|---|---|
| Москва | 96 | 32 | 80 | 16к |
| Новосибирск | 40 + 64 = 106 |
13 + 21 = 34 |
- | `6,6к + 10к = 16,6к |
| Стамбул | 40 | 13 | - | 6,6к |
Для балансировки использовать Geo-based DNS, так как расположение серверов обусловлено географией
В качестве L7-балансировщика работает Envoy, алгоритмы балансировки: Least Connections для сервисов расчета цен и "маркетплейса водителей и пользователей" (так как это затратные по времени операции), для остальных - Round-Robin.
Протокол VRRP позволяет нескольким хостам работать как единое целое, предоставляя один виртуальный IP-адрес. В случае отказа главного резервный автоматически становится главным
SSL-терминация будет происходить на балансировщике. У ДЦ в Москве и Новосибирске ~20к rps, в Стамбуле 6к, рассчитаем для 20к: время на установление соединения - 300мс -> для обработки запросов потребуется 6000 с
| Таблица | БД | Размер строки, бит | Кол-во записей | Объем | Чтение, Кбит/с | Запись, Кбит/с |
|---|---|---|---|---|---|---|
| ride | PostgreSQL | 530 | 4 млрд | 2 Тб | 255 | 425 |
| driver | PostgreSQL | 870 | 1 млн | 830 Мб | 135 | - |
| passanger | PostgreSQL | 370 | 300 млн | 100 Гб | 135 | - |
| car | PostgreSQL | 116 | 3 млн | 330 Мб | 70 | - |
| garage | PostgreSQL | 130 | 40 млн | 4,8 ГБ | 82 | |
| type | PostgreSQL | 64 | 100 | 6 Кб | - | - |
| statistics | Clickhouse | 86 | 8 млрд | 640 Гб | - | 53 |
| rating | PostgreSQL | 14 | 80 млн | 1 Гб | 9 | 3 |
| driver rating values | PostgreSQL | 106 | 2,5 мдрд | 240 Гб | - | 10 |
| passanger rating values | PostgreSQL | 106 | 2,5 млрд | 240 Гб | - | 10 |
| geoposition | ClickHouse | 36 | 1 трлн | 30 Тб | - | 10000 |
| current geoposition | Redis | 76 | 280 тыс | 20 Мб | 25 | 20000 |
| demand | Redis | 148 | 7 млн | 1 Гб | 115 | 115 |
| proposal | Redis | 128 | 7 млн | 950 Мб | 66 | 82 |
| Таблица | Запросы |
|---|---|
| ride | INSERT INTO ride(passanger_id, start_address, end_address, price, status) ..-создание заказаUPDATE ride SET garage_id=$1, points=$2, waiting_duration=$3, waiting_price=$4, status=$5, started_at=$6 WHERE id=$7- начало поездкиUPDATE ride SET price=$1, fee=$2, duration=$3, status=$4 WHERE id=$5-завершение поездкиSELECT id, garage_id, route_points, start_address, end_address, price, started_at, duration, status WHERE id=$1 - данные об определенной поездкеSELECT id, garage_id, route_points, start_address, end_address, price, started_at, duration, status WHERE passanger_id=$1 ORDER BY started_at-история поездок пользователя |
| driver/passanger rating | UPDATE .. SET raiting=$1, count=$2 WHERE .._id=$3 - каждый раз, когда пользователя оценилиSELECT rating FROM .. WHERE .._id=$1 |
| driver/passanger | SELECT .. FROM driver/passanger WHERE id=$1 - данные о водителях/пользователяхЗапись происходит редко |
| current geoposition | UPDATE сurrent_geoposition SET point=$1, status=$2, speed=$3, at=$4 WHERE driver_id=$5 - каждые 3 секундыSELECT driver_id, point, status, speed, at WHERE id=$1SELECT driver_id, point, status, speed, at WHERE at=$1 AND status=$2 |
| geoposition | INSERT INTO сurrent_geoposition(driver_id, point, at, ride_id) .. - каждые 3 секундыSELECT driver_id, point, at WHERE ride_id=$1 ORDER BY atSELECT driver_id, point, at WHERE at<$1 AND at>$2 |
| car | SELECT .. FROM car WHERE id=$1 - данные о машине по id |
| garage | SELECT driver_id, car_id, class, options FROM garage WHERE id=$1 |
| demand | INSERT INTO demand(start_address, ride_id, class, options, hegaxon_id) ..SELECT id, start_address, ride_id, class, options, hegaxon_id FROM demand WHERE hegaxon_id IN ($1, $2..) |
| proposal | INSERT INTO proposal(driver_geo, class, options, hegaxon_id, garage_id) ..SELECT id, driver_geo, class, options, hegaxon_id, garage_id FROM proposal WHERE hegaxon_id IN ($1, $2..) |
- таблица type хранит марки и модели машин, когда водитель берет новую машину ему предлагается список марок и моделей из этой таблицы. И в таблицу car сохраняется не id вида машины, а model и brand, избавляемся от join таким образом
- Основной БД для храненения данных является PostgreSQL
- Сессии пользователей будут храниться в Redis
- В таблице statistics хранятся данные по поездкам для аналитики, поэтому так же будем использовать Clickhouse
- Таблица current-geoposition, proposal, demand должны быть быстро доступны, так как на основе их подбираются водители и пассажиры и рассчитываются цены. Так что эти таблицы будем хранить в Redis, так как она работает в оперативной памяти и обеспечивает быстрый доступ к данным.
- Kafka для динамического ценообразования и расчета спроса, данные так же кешируются в Redis 5
- S3-хранилище для хранения сгенерированных карт спроса и аватарок 5
Будем использовать BTree индекс, он хорошо подходит для столбцов, являющихся ключами
- Ride: по passanger_id, started_at
- Current geoposition: по driver_id, at, status
- Geoposition: по ride_id, at
- Driver Rating: по driver_id
- Passanger Rating: по passanger_id
- Demand: по hegaxon_id
- Proposal: по hegaxon_id
- PostgreSQL: https://github.com/jackc/pgx
- Redis: https://github.com/redis/go-redis
- Kafka: https://github.com/segmentio/kafka-go
- S3: https://github.com/aws/aws-sdk-go
Таблица Ride довольна велика, произведем партицирование по started_at, это позволяет разделять данные о поездках по месяцам, retention policy управляет правилами хранения данных, тогда партиции по истечении 7 лет удаляются из PostgreSQL и переносятся в ClickHouse
Geoposition особенно велика, произведем партицирование по полю at (в партиции данные за месяц), по истечении определенного времени старые партиции удаляются.
- PostgreSQL: 1 мастер хост и 2 ведущих
- Clickhouse: мультимастеринг(2 мастер хоста) и 2 ведущих
Для хранения информации о местоположении водителей используется геопространнственный индекс, он реализован с помощью библиотеки H3 от Uber. Вся планета разбита на шестиугольники(гексагоны), у каждого свой 64-битный идентификатор. Водитель отправляет свою геолокацию каждые 3-4 секунды, на основе широты и долготы определяется гексагон, в котором находится водитель.
Когда пассажир оформляет заказ, добавляется запись о заказе в талицу Demand, начинается поиск водителей по дорожному графу(внешний сервис), запись о водителе сохраняется в таблицу Proposal. Таким образом накапливается список водителей и пассажиров, в котором надо эффективно распределить пары. Для каждого гексагона выбираются водители и пассажиры, для каждой пары рассчитывается время подачи. Задача системы сделать так, чтобы общее время подачи было минимальным. Иногда бывает, что на какой-то конкретный заказ подача не так мала, как могла бы быть, то есть не всегда приезжает ближайший водитель, но суммарное время подачи все равно минимальное
Самая главная задача динамического ценообразования – предоставлять возможность заказать такси всегда. Достигается она с помощью коэффициента surge pricing coefficient, на который умножается базовая цена. Если выставить сурдж слишком большим – снизится спрос слишком сильно, будет избыток свободных машин. Если выставить слишком низким – пользователи будут видеть «нет свободных машин». Таикм образом обеспечивается баланс спроса и предложения.5 Коэффициент расчитывается, как отношение заказов к водителям в гексагоне.
| Технология | Область применения | Мотивационная часть |
|---|---|---|
| Go | Backend | Высокая скорость разработки, асинхронность, стандартная библиотека включает много всего |
| Swift | iOS | Основной язык разработки приложений под iOS, разработан Apple |
| Kotlin | Android | Kotlin является официальным языком для Android-разработки, что обеспечивает активную поддержку и обновления от Google |
| PostreSQL | Основная SQL БД | Реляционная база данных с открытым исходным кодом, обеспечивающая высокую надежность и целостность данных |
| ClickHouse | Хранение статистики поездок | Разработанная Яндексом колончатая OLAP-БД, отлично подходит для аналитики |
| Redis | Хранение таблиц с большой нагрузкой | In-memory БД обеспечивает быстрый доступ к данным |
| Kafka | Асинхронный стриминговый сервис | Обработки асинхронных задач и обмен сообщениями между сервисами |
| AWS S3 | Хранилище картинок | Объектно-ориентированное хранилище, распространенный способ хранения статики |
| Envoy | Прокси-сервер | L7-балансировщик |
| Vault | Система управления секретами | Шифрование, гибкие политики доступа |
| React+TypeScript | Frontend | Библиотека для создания интерфейсов на основе компонентов, позволяет управлять их состоянием |
| VictoriaMetrics | Хранилище метрик | БД для хранения данных временных рядов, может хранить данные длительный период |
| Grafana | Визуализации и анализа данных | Популярная платформа для создание дашбордов, может подключаться к множеству исnочников данных |
| Kubernetes | Деплой | Автоматизация развертывания и управления приложений, отказоустойчивости и масштабирования |
| Компонент | Способы резервирования |
|---|---|
| Сервисы | Средставами Kubernetes обеспечивается перезапуск и масштабирование подов |
| PostgreSQL | Отказоустойчивость обеспечивается автоматическим переключением ролей узлов кластера с помощью Patroni, WAL обеспечивает восстановление в случае сбоев6 Дифференциальное резервное копирование7 |
| Redis | Предоставляет механизм(RDB) резервирования на основе снэпшотов |
| ClickHouse | Имеет инструменты для создания и восстановления бэкапов. Репликация реализуется с помощью движка таблиц ReplicatedMergeTree, он обеспечивает автоматическую синхронизацию данных между репликами |
| Kafka | Создание снэпшотов дисков или с помощью встроенного механизма Mirror Maker создание резервного кластера |
| Envoy | Наличие нескольких экземпляров с одним виртуальным ip |
Перед БД необходимо располагать прокси-серверы для мультиплексирования запросов
| Сервис | Целевая пиковая нагрузка приложения, rps | CPU | RAM | Net |
|---|---|---|---|---|
| Ride, Surge, Dispatch | 1k | 128 | 512 GB | 24 Кбит/с |
| Driver | 81k | 700 | 512 GB | 38 Мбит/с |
| Envoy | 85k | 16 | 64 GB | 249 Мбит/с |
| Postgres | 1,2k | 64 | 512 GB | 170 Кбит/с |
| Redis | 160k | 16 | 16 GB | 19 Мбит/с |
| ClickHouse | 80k | 64 | 32 GB | 2,7 Мбит/с |
| Kafka | 80k | 64 | 32 GB | 2,7 Мбит/с |
Ride, Surge, Dispatch хоть и имеют сравнительно небольшой rps, но у них самые нагруженные вычисления
Envoy - 1 core per 10k rps, request+response=3 KB
| Название | Хостинг | Конфигурация | Cores | Cnt | Аренда |
|---|---|---|---|---|---|
| kubenode RSD | own | 6338/64GB/NVMe256GB/10Gb/s | 16 | 8 | 30к руб/мес |
| kubenode Driver | own | 6338/4х32GB/NVMe100GB/25Gb/s | 64 | 5 | 80к руб/мес |
| kubenode Envoy | own | 6338/64GB/NVMe256GB/25Gb/s | 16 | 12 | 30к руб/мес |
| kubenode Postgres | own | 2х6338/16x32GB/NVMe4T/25Gb/s | 64 | 2 | 400к руб/мес |
| kubenode Redis | own | 6338/16GB/NVMe256GB/10Gb/s | 16 | 10 | 20к руб/мес |
| kubenode ClickHouse | own | 6338/16GB/NVMe4T/10Gb/s | 16 | 10 | 180к руб/мес |
| kubenode Kafka | own | 6338/16GB/NVMe512GB/10Gb/s | 16 | 2 | 40к руб/мес |