Як знайти найближче кафе, пам'ятка, вільне таксі очима програміста

Сервіси, вирішальні завдання у контексті нашого місця розташування досить міцно увійшли в наше життя. Більшість смартфонів може при наявності доступу в інтернет викликати нам таксі, розрахувати, через скільки приїде автобус, прокласти маршрут з урахуванням пробок і різних уподобань користувача або показати друзів поблизу. Задачки зразок пошуку найближчих кафе або пам'яток стали для них тривіальні і зазвичай можуть бути вирішені взагалі без доступу до всесвітньої павутини. У даній статті я хочу розглянути деякі інструменти для вирішення подібних завдань і порівняти їх продуктивність між собою.

Постановка завдання

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

Посилання репозиторій проекту.

Якщо ви знаєте інший інструмент для ефективного вирішення поставленого завдання — пишіть в коментарі, з цікавістю розгляну.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.