Локация и реальное время: обзор с выбором ответа
Синтез с выбором ответа по кейсам локации и реального времени: пространственное индексирование и ловушка границы ячейки, write-heavy фанаут локаций, contraction hierarchies для маршрутизации и отсортированное множество за лидербордом.
Шесть решений, проходящих сквозь четыре кейса. Каждое — выбор у доски: как индексировать пространство, где запускать фанаут, какой алгоритм переживёт континентальный граф, какая структура отвечает «мой ранг среди миллионов» — не определение для зубрёжки.
Подтвердите, что умеете выбрать пространственный индекс под паттерн доступа, починить ловушку границы ячейки, разместить фанаут локаций на верном слое, отвергнуть наивный Dijkstra на континентальном масштабе и выбрать структуру, делающую ранг-одного дешёвым.
Сервис поиска рядом запрашивает лишь собственную ячейку geohash пользователя и ранжирует места в ней. Пользователи сообщают, что явно близкий магазин иногда пропадает. Фикс?
Квадратная сетка фиксированного разрешения переполняется на Таймс-сквер (одна ячейка держит десятки тысяч мест), а океанские ячейки пусты, и задержка плотных запросов ужасна. Какое структурное изменение помогает больше всего?
Система «друзья рядом» принимает 2 млн гео-пингов/с. Инженер предлагает на каждый пинг загружать друзей публикатора, доставать их локации и толкать близким. Почему предпочесть pub/sub по региону?
Команда строит континентальную маршрутизацию наивным Dijkstra; корректно, но секунды на запрос с раскрытием миллионов узлов. Какая предобработка заставит запросы трогать лишь тысячи узлов, всё ещё возвращая точный кратчайший путь?
Лидерборд хранит очки в SQL-таблице с индексом по score. Top-10 быстр, но показ каждому из 12 млн игроков его живого ранга давит базу. Корень и фикс?
Вы шардите лидерборд по диапазону очков по узлам, потому что один узел не держит его. Как всё ещё отвечать на ГЛОБАЛЬНЫЙ ранг игрока без скана?
- 01Почему запрос близости должен брать соседей ячейки, не одну ячейку?
- 02Почему ранг-одного дёшев в ZSET, но дорог в SQL?
Сквозная мысль юнита — верная схема выпадает из паттерна доступа. Близость read-heavy и медленно меняется, так что строишь пространственный индекс и запрашиваешь ячейку плюс её соседей как грубый фильтр, ранжируя уцелевших по точному расстоянию; перекос плотности чинится адаптивным разрешением (quadtree, S2/H3). «Друзья рядом» инвертируют это в поток записи, так что толкаешь по WebSocket из эфемерного TTL-хранилища и маршрутизируешь через pub/sub по региону, гоняя фильтр друг-и-радиус на краю-подписчике, а не как join по графу+гео на приёме. Maps определяется предвычислением: тайлы на CDN, маршрутизация через contraction hierarchies, чтобы запрос ехал на горстке сокращений вместо раскрытия миллионов узлов, с живым трафиком как отдельным оверлеем весов. Лидерборду нужны обновление, top-k и ранг-одного вместе, что даёт отсортированное множество за O(log n), где SQL ORDER BY делает ранг счётом O(n) — и оно шардится по диапазону очков с глобальным рангом из по-шардовых счётчиков.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.