Сервисы, решающие какие-либо задачи в контексте нашего местоположения достаточно прочно вошли в нашу жизнь. Большинство смартфонов может при наличии доступа в интернет вызвать нам такси, рассчитать, через сколько приедет автобус, проложить маршрут с учетом пробок и различных предпочтений пользователя или показать друзей поблизости. Задачки вроде поиска ближайших кафе или достопримечательностей стали для них тривиальны и обычно могут быть решены вообще без доступа ко всемирной паутине. В данной статье я хочу рассмотреть некоторые инструменты для решения подобных задач и сравнить их производительность между собой.
Постановка задачи
Необходимо выбрать средства для разработки сервиса, в который пользователи периодически загружают свое местоположение, а другие пользователи ищут своих «соседей». Примерами сервисов, решающих подобные задачи могут быть сервисы заказа такси, социальные сети и игры вроде 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. PostgreSQL v9.5.2
Ссылка на документацию (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))
Так же видим использование геоиндекса.
Реализация 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 | 114.878 | 8.908 |
Redis | 1098.604 | 5.016 |
Все данные в таблице представлены в секундах, значение среднее по 5 тестам.
Ссылка на репозиторий проекта.
Если вы знаете другой инструмент для эффективного решения поставленной задачи — пишите в комментарии, с интересом рассмотрю.
Автор: artemyl2011