Как найти ближайшее кафе, достопримечательность, свободное такси глазами программиста

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

Постановка задачи


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

Способ решения задачи


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

from abc import ABCMeta, abstractmethod


class AbstractStorage(object):
    __metaclass__ = ABCMeta

    @abstractmethod
    def prepare_storage_for_experiment(self, test_data):
        pass

    @abstractmethod
    def experiment_search(self, test_data):
        pass

    @abstractmethod
    def experiment_update(self, test_data):
        pass

    @abstractmethod
    def clear_storage(self):
        pass


Измерение времени выполняется при помощи Profilehooks.

Принятые упрощения


  1. Здесь и далее весь код написан на языке Python; со всеми описанными ниже инструментами можно работать из других распространенных языков программирования, если не указано иное. Возможность ускорить работу системы, переписав все на более быстром языке программирования вроде c/c++ в рамках данной статьи рассматриваться не будет, хотя вполне может быть применена в боевых условиях, если доказана целесообразность такого решения.
  2. В приведенной системе все запросы обрабатываются последовательно, что эквивалентно наличию очереди запросов перед рассматриваемым модулем и работе модуля в один поток; при использовании системы в бою разрабатываемый модуль скорее всего будет обрабатывать запросы в несколько потоков.
  3. Все тесты запускаются на ноутбуке со следующим набором железа: 8 Gb RAM, Intel Core i5 2,6 GHz, SSD. Конфигурация серверного железа с большой вероятностью будет другой.
  4. Все используемы инструменты будут использоваться с конфигурацией по умолчанию за исключением одинакового объема выделенной оперативной памяти(там, где этот момент поддается конфигурации стандартными средствами). Конфигурирование выбранных инструментов в рамках данной статьи рассмотрено не будет.

Реализация


Строка(документ или другое — в зависимости от принятой терминологии) состоит из id и пары координат во внутреннем представлении системы. По каждому из столбцов построен индекс в случае, если система позволяет это делать. Во всех реализациях будет представлен код, ответственный за поиск и обновление. Ссылка на полный код проекта на github будет дана в конце статьи.

Реализация 1. MongoDB v3.2.6
Ссылка на документацию по геопоиску

Код, ответственный за тестирование скорости поиска и обновлений:

@timecall(immediate=True)
def experiment_search(self, test_data):
    def find_point(point):
        cursor = self.collection.find(
            {
                MongoStorage.key_position:
                    {
                        '$near':
                            {
                                '$geometry':
                                    {
                                        'type': "Point",
                                        'coordinates': [point['lng'], point['lat']]
                                    },
                                '$maxDistance': 10000
                            }
                    }
            }
        )
        return cursor[0] if cursor.count() > 0 else None

@timecall(immediate=True)
def experiment_update(self, test_data):

    for t in test_data:
        self.collection.update_one(
            {
                MongoStorage.key_id: t["id"]
            },
            {
                '$set': {
                    MongoStorage.key_position: {
                        'type': "Point",
                        'coordinates': [t['position']['lng'], t['position']['lat']]
                    }
                }
            }
        )

Explain для поискового запроса:

{
	"queryPlanner" : {
		"plannerVersion" : 1,
		"namespace" : "taxi_geo_experiment_test_db.taxi_driver_collection",
		"indexFilterSet" : false,
		"parsedQuery" : {
			"key_position" : {
				"$near" : {
					"$geometry" : {
						"type" : "Point",
						"coordinates" : [
							37.3816328351611,
							55.01604115262
						]
					},
					"$maxDistance" : 10000
				}
			}
		},
		"winningPlan" : {
			"stage" : "GEO_NEAR_2DSPHERE",
			"keyPattern" : {
				"key_position" : "2dsphere"
			},
			"indexName" : "key_position_2dsphere"
		},
		"rejectedPlans" : [ ]
	},
	"serverInfo" : {
		"host" : "host",
		"port" : 27017,
		"version" : "3.2.6",
		"gitVersion" : "05552b562c7a0b3143a729aaa0838e558dc49b25"
	},
	"ok" : 1
}

Видим, что используется геоиндекс.

Реализация 2.1. PostgreSQL v9.5.2 с использованием ST_DWithin
Ссылка на документацию (postgis)

Код, ответственный за тестирование скорости поиска и обновлений:

@timecall(immediate=True)
def experiment_search(self, test_data):
    cursor = self.db_connect.cursor()

    for item in test_data:
        request = "SELECT * FROM {table_name} " \
                  "WHERE ST_DWithin({column_geo},ST_MakePoint({lat},{lng}), 10000)".format(
            table_name=PostgreSQLStorage.table_name,
            column_geo=PostgreSQLStorage.column_position,
            lat=item["lat"],
            lng=item["lng"])
        cursor.execute(request)
        search_result = cursor.fetchall()


@timecall(immediate=True)
def experiment_update(self, test_data):
    cursor = self.db_connect.cursor()

    for item in test_data:
        request = "UPDATE {table_name} set {update_column_name}=ST_MakePoint({lat},{lng}) " \
                  "where {id_column_name}={id}".format(
            table_name=PostgreSQLStorage.table_name,
            update_column_name=PostgreSQLStorage.column_position,
            id_column_name=PostgreSQLStorage.column_id,
            lat=item["position"]["lat"],
            lng=item["position"]["lng"],
            id=item["id"]
        )
        cursor.execute(request)
        self.db_connect.commit()

Explain для поискового запроса:

 Index Scan using geo_index on taxi_drivers  (cost=0.14..10.51 rows=1 width=36)
   Index Cond: (driver_position && '0101000020E6100000C8EA77DD72C44B404C0305B698B04240'::geography)
   Filter: (('0101000020E6100000C8EA77DD72C44B404C0305B698B04240'::geography && _st_expand(driver_position, '10000'::double precision)) AND _st_dwithin(driver_position, '0101000020E6100000C8EA77DD72C44B404C0305B698B04240'::geography, '10000'::double precision, true))

Так же видим использование геоиндекса.

Реализация 2.2. PostgreSQL v9.5.2 с использованием ST_Distance
Ссылка на документацию (postgis)

Код, ответственный за тестирование скорости поиска:
@timecall(immediate=True)
def experiment_search(self, test_data):
    cursor = self.db_connect.cursor()

    for item in test_data:
        request = "SELECT * FROM {table_name} " \
                  "WHERE ST_Distance({column_geo},ST_MakePoint({lat},{lng})) < 10000".format(
            table_name=PostgreSQLStorage.table_name,
            column_geo=PostgreSQLStorage.column_position,
            lat=item["lat"],
            lng=item["lng"])
        cursor.execute(request)
        search_result = cursor.fetchall()


Код, ответственный за тестирование скорости обновления, не отличается от реализации, описанной в предыдущем пункте.
Explain для поискового запроса:
 Seq Scan on taxi_drivers  (cost=0.00..8241.00 rows=10000 width=60)
   Filter: (_st_distance(driver_position, '0101000020E61000003B2CDE5519AA4B402B1697185FED4240'::geography, '0'::double precision, true) < '10000'::double precision)

В данном случае индекс не используется, будут просмотрены все значения в таблице, что значительно медленнее.
Подробнее про EXPLAIN в PostgreSQL.

Реализация 3. Redis v3.2.0
Ссылка на документацию по геофункциям

Код, ответственный за тестирование скорости поиска и обновлений:

@timecall(immediate=True)
def experiment_search(self, test_data):
    i = 0
    for item in test_data:
        command = "GEORADIUS {key} {lng} {lat} {dist_km} km WITHCOORD WITHDIST".format(
            key=RedisStorage.KEY_DRIVERS,
            lat=item["lat"],
            lng=item["lng"],
            dist_km=10
        )
        result = self._redis.execute_command(command)

@timecall(immediate=True)
def experiment_update(self, test_data):
    for item in test_data:
        command_rm = "ZREM {key} \"{id}\"".format(
            key=RedisStorage.KEY_DRIVERS,
            id=item["id"]
        )
        self._redis.execute_command(command_rm)
        command_add = "GEOADD {key} {lng} {lat} \"{id}\"".format(
            key=RedisStorage.KEY_DRIVERS,
            lat=item["position"]["lat"],
            lng=item["position"]["lng"],
            id=item["id"]
        )
        self._redis.execute_command(command_add)

Аналога explain для redis нет, так как в подобной команде нет необходимости, redis не предназначен для сложных запросов, в которых подобный функционал может потребоваться.

Несложно заметить еще одну особенность — в redis нельзя удалить из ключа(ближайший аналог ключа в SQL — таблицы; ключ может содержать как простое значение, например, число, так и сложное — например, множество) один из геообъектов, для этого надо воспользоваться знаниями о внутреннем представлении: команда ZREM удаляет значение из множества.

Вывод


Тестирование проводилось на 30 000 объектов и таком же количестве запросов. При необходимости можно провести тестирование на других наборах значений, заменив соответствующие параметры в коде. Результаты тестирования представлены в таблице:
Инструмент Время на поиск Время на обновление
MongoDB 320.415 14.275
PostgreSQL(ST_DWithin) 114.878 8.908
PostgreSQL(ST_Distance) 1829.920
(реализация и результат аналогичны PostgreSQL(ST_DWithin))
Redis 1098.604 5.016

Все данные в таблице представлены в секундах, значение среднее по 5 тестам.

Ссылка на репозиторий проекта.

Если вы знаете другой инструмент для эффективного решения поставленной задачи — пишите в комментарии, с интересом рассмотрю.

Update 1: Добавлена реализация PostgreSQL с использованием ST_Distance. Данная реализация не использует индекс, соответственно, поиск работает дольше.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 10
  • 0
    Есть ощущение, что ST_Distance в постгисе побыстрее работает
    • +1
      В случае постановки задачи из статьи ST_Distance работать быстрее не будет, так как реализация с ST_Distance не использует индексы. Добавил в статью реализацию с использованием ST_Distance, так как не единожды встречал это предположение.
    • 0
      Спасибо, за хороший обзор!
      • 0
        Было бы интересно увидеть в сравнительной таблицы couchdb и mysql (движок желательно именно MyISAM, он проще и быстрее).
        • 0
          Насколько я знаю, mysql не имеет ни нативной поддержки вычисления кратчайшего расстояния между двумя точками по их географическим координатам, ни аналога ST_DWithin из PostgreSQL (поправьте, если я не прав, желательно аргументировав ссылками на соответствующие разделы документации). В связи с этим использовать mysql для поиска «соседей», расстояние до которых менее заданного, накладывает дополнительные ограничения:
          1. необходимо самостоятельно реализовать расчет расстояния(не сложно, но требует поддержки дополнительного кода)
          2. собственная реализация скорее всего не будет оптимально использовать индекс

          Второе ограничение можно обойти при помощи различных упрощений (например, заменив окружность квадратом, который, в зависимости от условий задачи вписан в нее/описан около нее и построить другой индекс), однако, сравнение будет некорректно, так как эти же упрощения можно применить и к другим средствам.
          • 0
            По поводу couchdb — я не имею достаточное экспертизы по этому инструменту, но все же постараюсь ответить.

            Во-первых — Вы имеете ввиду именно couchdb(http://couchdb.apache.org) или ответвившийся couchbase(http://www.couchbase.com)? — первая, как я понял из документации, по умолчанию вообще не имеет нативной поддержки геопоиска, вторая — на уровне bounding box, то есть решение поставленной в статье задачи по дефолту так же невозможно, только с хаками, описанными для mysql

            Во-вторых, как я опять же понял из документации, couchdb by design не предназначена для частых обновлений — подробнее здесь, здесь и в документации. Следовательно, этот инструмент нельзя для сервисов вроде заказа такси, каршеринга и других подобных, где обновление координат выполняется часто. Данные могут быть неактуальны, так как приведенные статьи опубликованы довольно давно.

            P.S. интересно будет услышать по этому вопросу мнение людей, которые использовали couchdb в бою, например, от 1999 — автора одной из приведенных статей
            • 0
              Для Mysql можно декларировать функцию (подробнее). Несложной манипуляцией можно создать необходимые индексы.
              CouchDB примитивен, затрагивает отдельный уровень обработки данных. Скорость работы couchdb обусловлена в том числе и его простотой. Хранение данных можно настроить другими средствами (хранить полностью в озу, или настроить репликации на жесткий диск), так что частые обновления — тут совсем не фактор. Предложенные Вами статьи 4-5 летней давности. Для обработки гео-данных есть geocouch.
              • 0
                Я к чему это все?! Суть в том, что там, где важна скорость, часто выгоднее использовать простые решения, чем оптимизированные мега-комбайны.

                Поведаю коротенькую историю. Около 10 лет назад устроился на работу в среднюю организацию. На тот момент были офисы в четырех городах: Москва (~40 человек), Питер (5 человек), Киев и Минск (~по 10 человек). Информационные задачи обслуживала самописная CRM на php, которая в свое время модернизировалась из CRM на основе Microsoft Office. Как раз в период времени пока работал там, она переписывалась с устаревшей php4 на php5. Обслуживал все это хозяйство сервер на Windows Server 2000 (или 2003 — уже не вспомню). Руководство получило от меня инициативу, помимо перехода на новый php, обновить и СУБД. На тот момент БД управляла mysql3. Вся СУБД со всеми зависимостями умещалась в один файл mysqld-max.exe, на моей памяти, весом чуть больше 1мб. В итоге, мне было предложено найти что-нибудь стабильней/быстрей. По скорости, с этой версией даже близко не могли сравниться ни 4я, ни 5я, ни даже 6я бета версии mysql. По итогу, позже перешли на MS SQL-сервер (это уже не по моей инициативе, по-моему, были какие-то требования для MS BizTalk), а после моего ухода компания перешла на какую-то несамописную расширяемую CRM (тоже уже не могу вспомнить какую).
                • 0
                  Про простоту в общем случае согласен, но в данном конкретном случае не уверен, что хранимая процедура в mysql будет работать быстрее, чем нативная функция в postgres.

                  Дабы не быть голословным, постараюсь добавить к сравнению, как только появится время.
          • 0
            (ошибся веткой)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.