問題の声明
ユーザーが自分の位置を定期的にアップロードし、他のユーザーが「隣人」を探すサービスを開発するためのツールを選択する必要があります。 このような問題を解決するサービスの例には、タクシーサービス、ソーシャルネットワーク、 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 ++のような高速プログラミング言語ですべてを書き換えてシステムを高速化する機能は、この記事のフレームワークでは考慮されませんが、そのようなソリューションの実現可能性が証明されれば戦闘条件で使用できます。
- 指定されたシステムでは、すべての要求が順番に処理されます。これは、問題のモジュールの前に要求のキューを置き、1つのスレッドでモジュールの操作を行うことに相当します。 戦闘でシステムを使用する場合、開発されたモジュールはほとんどの場合、複数のスレッドでリクエストを処理します。
- すべてのテストは、8 Gb RAM、Intel Core i5 2.6 GHz、SSDのハードウェアを搭載したラップトップで実行されます。 サーバーハードウェアの構成は異なる可能性があります。
- 使用されているすべてのツールは、同じ量の割り当てられたRAMを除いて、デフォルトの構成で使用されます（この時点では、標準的な方法で構成に適しています）。 この記事で選択したツールの構成は考慮されません。
実装
行（受け入れられた用語に応じて、ドキュメントまたは別の行）は、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']] } } } )
検索語の説明：
{ "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。 ST_DWithinを使用した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()
検索語の説明：
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。 ST_Distanceを使用した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_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()
更新速度のテストを担当するコードは、前の段落で説明した実装と変わりません。
検索語の説明：
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)
この場合、インデックスは使用されず、テーブル内のすべての値が表示されますが、これは非常に低速です。
PostgreSQLのEXPLAINの詳細をご覧ください 。
実装3. Redis v3.2.0
Geofunction Documentation Link検索と更新の速度をテストするコード：
@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)
redisについて説明する類似物はありません。そのようなコマンドは必要ないため、redisは同様の機能が必要となる複雑なクエリを対象としていません。
もう1つの機能に気付くのは簡単です-redisでは、キーから削除することはできません（SQLのキーに最も近いものはテーブルです。キーには、数値などの単純な値、またはセットなどの複雑な値を含めることができます）、これに関する知識を使用する必要があります内部表現： ZREMコマンドは、セットから値を削除します。
おわりに
テストは、30,000個のオブジェクトと同じ数のリクエストで実施されました。 必要に応じて、コード内の対応するパラメーターを置き換えることにより、他の値のセットでテストできます。 テスト結果は表に示されています：
| 楽器 | 検索時間 | 更新時間 |
|---|---|---|
| モンゴッド | 320.415 | 14.275 |
| PostgreSQL（ST_DWithin） | 114.878 | 8.908 |
| PostgreSQL（ST_Distance） | 1829.920 | -
（実装と結果はPostgreSQL（ST_DWithin）に似ています） |
| レディス | 1098.604 | 5.016 |
表のすべてのデータは、5つのテストの平均値である秒単位で表示されます。
プロジェクトリポジトリにリンクします。
タスクを効果的に解決するための別のツールを知っている場合-コメントを書いて、興味を持って検討します。
更新1： ST_Distanceを使用したPostgreSQL実装が追加されました。 この実装はインデックスを使用しないため、検索が長く続きます。