Обслуживайте кластеры карт в 50 раз быстрее, используя более интеллектуальное кэширование

Компоненты карты с маркерами местоположения сегодня широко распространены в мобильных приложениях. Например, в приложении Airbnb на видном месте представлены такие маркеры, полученные из веб-службы, для представления доступных объектов недвижимости на карте.

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

Тем не менее, обслуживающие кластеры могут создавать узкие места в производительности, поскольку веб-служба должна извлекать из базы данных каждый отдельный маркер в заданном географическом регионе. К счастью, эту проблему можно решить с помощью стратегии кэширования. Чтобы лучше понять, как спроектировать и поддерживать кеш, давайте рассмотрим пример конечной точки API карты, которую я создал для приложения Playsports.

Проблема масштабирования и простое решение

На карте Playsports каждый маркер представляет спортивное сооружение. Конечная точка API карты должна возвращать список маркеров и кластеров маркеров с заданным уровнем масштабирования и ограничивающей рамкой.

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

Вначале максимальное количество маркеров в любой достижимой ограничивающей рамке в Playsports составляло ~400, в результате чего скорость конечной точки составляла ~0,5 секунды. Для этого варианта использования было достаточно реализации наивного решения.

Однако по мере роста числа маркеров неэффективность механизма становилась очевидной. После того, как мы добавили ~10 000 новых маркеров спортивных сооружений, скорость конечной точки снизилась до ~4,3 секунды при некоторых уровнях масштабирования. Этот показатель намного ниже продолжительности в одну секунду, которая обычно считается максимально допустимой задержкой для действия пользователя в мобильном приложении.

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

1. Из базы данных извлеките все маркеры в ограничительной рамке . Для большинства приложений этот шаг должен включать получение сведений о маркере, помимо позиционирования широты/долготы. Например, маркеры Airbnb включают в себя цену, то, просмотрел ли пользователь уже недвижимость и отметил ли он ее как избранную.
2. На извлеченных маркерах запустите алгоритм кластеризации карты, который включает уровень масштабирования.
3. Верните кластеры и (подробные) маркеры клиенту.

По мере увеличения количества маркеров производительность на шагах 1 и 2 ухудшается:

• Когда ограничивающая рамка достаточно велика и более 10 000 маркеров требуют подробного поиска через JOIN, запрос к базе данных резко замедляется (на 1–2 секунды).
• Передача 10 000 элементов алгоритму кластеризации карт занимает еще ~250 миллисекунд.

Предполагая постоянный размер окна, когда ограничивающая рамка относительно велика, уровень масштабирования обычно низкий (т. е. сильно уменьшен). При низких уровнях масштабирования результаты, как правило, отдают предпочтение кластерам, чтобы избежать визуальной скученности. Таким образом, наибольший потенциал для оптимизации лежит на первом шаге решения, когда загружаются тысячи отдельных маркеров. Нам не нужно большинство этих маркеров в результате. Нам нужно только, чтобы каждый из них учитывался в кластере.

Архитектура оптимизированного решения

Наивное решение требует значительно больше времени для выполнения запроса в худшем случае: максимальная ограничивающая рамка в области с высокой плотностью маркеров. Напротив, оптимизированное решение заняло бы всего 73 мс, что соответствует ускорению примерно в 58 раз. С высокого уровня это выглядит так:

1. Стратегия кэширования. Извлекайте маркеры и кластеры в ограничительной рамке из кэша для определенного уровня масштабирования.
2. Дополнительная информация о маркере (необязательно). Усовершенствуйте маркеры с помощью полезной нагрузки, полученной из базы данных.
3. Возврат результата. Верните маркеры и кластеры клиенту.

Основная сложность заключается в архитектуре кэша (т.е. первый шаг).

Шаг 1: Стратегия кэширования

Этот основной этап состоит из шести компонентов:

Технология

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

Кэш для каждого уровня масштабирования

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

• Для высоких уровней масштабирования (т. е. при приближении) результат будет в пользу отдельных маркеров, за исключением областей с высокой плотностью маркеров.
• При низких уровнях масштабирования (т. е. при значительном уменьшении масштаба) результат будет в пользу кластеров, за исключением областей с разреженными маркерами.

Карты Google поддерживают уровни масштабирования от нуля до максимум 20, в зависимости от области. (Диапазоны, поддерживаемые другими картографическими сервисами, аналогичны. Например, Mapbox использует уровни масштабирования от нуля до максимума 23.) Поскольку эти уровни масштабирования также являются целочисленными значениями, мы можем просто создать отдельный кэш для каждого уровня масштабирования.

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

Типы данных кэша

В каждом кэше будут храниться кластеры и отдельные маркеры. Для любого типа записи нам нужно будет заполнить несколько полей:

Однако Redis позволяет пользователям сохранять только местоположение плюс одну строку в качестве значения в геопространственном наборе. Чтобы обойти это ограничение, мы сериализуем вышеуказанные поля в строку JSON. Затем мы используем эту строку в качестве значения в Redis. Максимальный размер ключей и значений в Redis составляет 512 МБ, что более чем достаточно для этого варианта использования.

Заполнение кешей

Чтобы заполнить кэши, мы извлекаем все маркеры из базы данных. Для каждого уровня масштабирования мы выполняем алгоритм кластеризации карты. Мы используем GEOADD Redis, чтобы вставить полученные маркеры и кластеры в кэш соответствующего уровня масштабирования и передать широту и долготу, а также ранее описанную строку JSON.

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

Запрос кэша

Для входящего запроса мы передаем заданную ограничивающую рамку команде Redis GEOSEARCH , которая запрашивает кеш с заданным уровнем масштабирования для получения маркеров и кандидатов в кластеры в области.

Разработка плана обновления кэша

Обновление 20-уровневого кэша стоит дорого, поэтому лучше обновлять его так редко, как позволяют требования вашего проекта. Например, добавление или удаление спортивного объекта в Playsports только помечает кеш как устаревший; затем ежечасное задание cron обновляет кеш, если это необходимо. Подробнее об этом в разделе «Устаревание кэша».

Шаг 2: Дополнительные сведения о маркере (необязательно)

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

Наше оптимизированное решение берет идентификаторы отдельных маркеров из результатов кеша и извлекает их данные из базы данных. Теперь мы ищем только отдельные маркеры, оставшиеся после кластеризации. Их не будет слишком много ни при уменьшении карты (поскольку у нас будут в основном кластеры), ни при увеличении (поскольку область будет маленькой).

Напротив, простое решение ищет все маркеры в ограничивающей рамке (и их детали) перед кластеризацией. Таким образом, этот шаг — необязательный, но критически важный для многих приложений — теперь выполняется намного быстрее.

Шаг 3: Возврат результата

Создав кластеры и улучшив отдельные маркеры, мы можем доставить их клиенту. Если не считать некоторых несущественных пограничных случаев, полученные данные почти идентичны исходному решению, но мы можем предоставить их намного быстрее.

Дополнительные соображения

Теперь давайте рассмотрим два дополнительных фактора:

Потребности в ресурсах

Предположим, что карта приложения содержит всего N маркеров. Поскольку существует до 20 уровней масштабирования, нам потребуется хранить не более 20N элементов кэша. На практике, однако, фактическое количество элементов кэша часто намного меньше из-за кластеризации, особенно при более низких уровнях масштабирования. На самом деле общее количество элементов кеша, распределенных по всем кешам Playsports, составляет всего ~2N.

Кроме того, если мы предположим, что длина значения кэша (строкового JSON) составляет ~250 символов (разумное предположение, по крайней мере, для Playsports), а размер строки равен 1 байту на символ, то объем кэш-памяти, необходимый для Значения JSON будут примерно 2 * N * 250 байт.

К этому рисунку мы добавляем внутренние структуры данных Redis для отсортированных наборов, используемых GEOADD . Redis использует 85 МБ памяти для 1 миллиона небольших пар ключ-значение, поэтому мы можем предположить, что внутренние ресурсы Redis занимают менее 100 байт на элемент кэша. Это означает, что мы можем использовать экземпляр Redis с 1 ГБ оперативной памяти для поддержки до 1,4 миллиона маркеров. Даже в маловероятном сценарии, когда маркеры будут равномерно распределены по всей карте, что приведет к тому, что количество элементов кеша приблизится к 20N, N все равно может возрасти до ~140 000. Поскольку экземпляр Redis может обрабатывать более 4 миллиардов ключей (точнее, 2 ³² ), это не является ограничивающим фактором.

Кэш устаревания

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

После каждого обновления базы данных мы ставили задание обновления кэша в очередь. Эта очередь ограничит количество задач до M в час. Этот компромисс позволяет получать обновления быстрее, чем ежечасно, сохраняя при этом относительно низкую нагрузку на систему (в зависимости от M).

Стратегии кэширования перевешивают алгоритмы кластеризации карты

Оптимизированное решение для Playsports — более чем в 50 раз быстрее, чем простое решение — сработало хорошо. Он должен продолжать хорошо работать, пока мы не достигнем 1,4 миллиона маркеров или более чем в 100 раз превысим существующие данные.

Для большинства запросов веб-сервисов на основе карт требуется некоторая форма предварительного расчета для обеспечения масштабируемости. Тип используемой технологии, а также конкретный дизайн будут зависеть от бизнес-требований. Необходимость устаревания кэша, увеличение маркеров и количество маркеров — важные характеристики, которые необходимо учитывать при разработке решения.

Дальнейшее чтение в блоге Toptal Engineering:

• Обзор лучших картографических онлайн-инструментов для веб-разработчиков: от дорожной карты к дорожной карте
• Приключения в программировании и разработке GPS: Учебное пособие по геопространственной информации