System design - Яндекс Пробки | Гео базы данных | High load
Проектирую сервис наподобие Яндекс Пробки, который в риал-тайме считывает уровень пробок на дорогах и отдает эту информацию клиентам. Система выдерживает высокую нагрузку и масштабируема (в каждом узле). ——— Канал в телеграме: https://t.me/distributed_system_design Платный курс с роадмапом: https://t.me/tribute/app?startapp=sUJx 1-1 консультация / мок-собеседование: ser.sysd.channel@gmail.com По другим вопросам: ser.sysd.channel@gmail.com ——— В чем основная идея архитектуры: Дорожный сегмент - кусок дороги, для которого показываем уровень пробки. В одном регионе (напр., РФ/СНГ) под миллиард таких сегментов. Из-за этого храним их в бд. Для поиска сегментов по координатам используем geohash. БД шардируем. Новые дороги строят редко, поэтому бд в основном read-only. GPS-координаты неточны. По GPS координате нельзя точно сказать, по какому дорожному сегменту едет водитель. Координаты от водителя поступают во веб-сокету. Для нескольких последних координат (траектории) и дорожных сегментов в окрестности этих координат считаем реальное положение водителя. Реальные положения водителей складываем в кафку и в консьюмере считаем среднии скорости по дорожным сегментам. ——— Тайм-коды: 00:00 Функциональные требования. 00:59 Нефункциональные требования. 05:39 Схема сервиса. Веб-сокеты, кафка. 10:48 Гео базы данных. Geohash. S2. 20:06 Схема бд с дорогами, шардирование. 25:14 Выбор бд. 26:11 Схема сервиса. Продолжение. Мэтчинг gps в реальное положение водителя. 27:02 Рассчет скорости водителей на дорожном сегменте. 28:54 Клиент читает уровень пробок. 29:58 Как точно выдержать 10 млн rps. 31:37 Обходимся без кафки и делаем рассчеты на websocket-серверах. 32:52 Более эффективное распределение водителей по серверам. (далее немного теории вероятности) 35:14 Как можно рассчитывать реальное расподожение водителя на дороге. Цепи Маркова. Алгоритм Витерби. 39:12 Вероятности задаем и храним в бд с дорогами. Статья про geohash и s2: https://benfeifke.com/posts/geospatial-indexing-explained/ Алгоритм Витерби: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D0%B8%D1%82%D0%B5%D1%80%D0%B1%D0%B8 Канал в телеграмме (есть чат): https://t.me/distributed_system_design
Проектирую сервис наподобие Яндекс Пробки, который в риал-тайме считывает уровень пробок на дорогах и отдает эту информацию клиентам. Система выдерживает высокую нагрузку и масштабируема (в каждом узле). ——— Канал в телеграме: https://t.me/distributed_system_design Платный курс с роадмапом: https://t.me/tribute/app?startapp=sUJx 1-1 консультация / мок-собеседование: ser.sysd.channel@gmail.com По другим вопросам: ser.sysd.channel@gmail.com ——— В чем основная идея архитектуры: Дорожный сегмент - кусок дороги, для которого показываем уровень пробки. В одном регионе (напр., РФ/СНГ) под миллиард таких сегментов. Из-за этого храним их в бд. Для поиска сегментов по координатам используем geohash. БД шардируем. Новые дороги строят редко, поэтому бд в основном read-only. GPS-координаты неточны. По GPS координате нельзя точно сказать, по какому дорожному сегменту едет водитель. Координаты от водителя поступают во веб-сокету. Для нескольких последних координат (траектории) и дорожных сегментов в окрестности этих координат считаем реальное положение водителя. Реальные положения водителей складываем в кафку и в консьюмере считаем среднии скорости по дорожным сегментам. ——— Тайм-коды: 00:00 Функциональные требования. 00:59 Нефункциональные требования. 05:39 Схема сервиса. Веб-сокеты, кафка. 10:48 Гео базы данных. Geohash. S2. 20:06 Схема бд с дорогами, шардирование. 25:14 Выбор бд. 26:11 Схема сервиса. Продолжение. Мэтчинг gps в реальное положение водителя. 27:02 Рассчет скорости водителей на дорожном сегменте. 28:54 Клиент читает уровень пробок. 29:58 Как точно выдержать 10 млн rps. 31:37 Обходимся без кафки и делаем рассчеты на websocket-серверах. 32:52 Более эффективное распределение водителей по серверам. (далее немного теории вероятности) 35:14 Как можно рассчитывать реальное расподожение водителя на дороге. Цепи Маркова. Алгоритм Витерби. 39:12 Вероятности задаем и храним в бд с дорогами. Статья про geohash и s2: https://benfeifke.com/posts/geospatial-indexing-explained/ Алгоритм Витерби: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D0%B8%D1%82%D0%B5%D1%80%D0%B1%D0%B8 Канал в телеграмме (есть чат): https://t.me/distributed_system_design