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

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

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

Необходимо выбрать средства для разработки сервиса, в который пользователи периодически загружают свое местоположение, а другие пользователи ищут своих «соседей». Примерами сервисов, решающих подобные задачи могут быть сервисы заказа такси, социальные сети и игры вроде 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.

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

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

Реализация

Строка(документ или другое — в зависимости от принятой терминологии) состоит из 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. Данная реализация не использует индекс, соответственно, поиск работает дольше.