Architecture de trouver des objets mobiles géolocalisés

Question

J'ai actuellement un DB Postgres rempli d'env. 300.000 ensembles de données de véhicules en mouvement dans le monde entier. Ma question très fréquemment répétée est: Donnez-moi tous les véhicules dans un rayon de 5/10/20mile. Actuellement, je passe environ 600 à 1200 ms dans la base de données pour préparer l'ensemble des objets-véhicules localisés.

Je cherche à améliorer énormément ce temps, idéalement d'un ou deux ordres de grandeur si possible. Je travaille dans un environnement Ruby on Rails 3.0beta si cela est pertinent.

Des idées comment architecturer l'ensemble du système pour accélérer cette requête? Toute base de données NoSQL capable de fournir ce type de performance de géolocalisation? Je sais que MongoDB travaille sur une extension pour faciliter ce scénario mais ne l'a pas encore essayé. Toute utilisation intelligente de Redis pour y parvenir? Un problème avec SQL-DB semble ici être que je ne peux pas utiliser d'index parce que mes véhicules se déplacent principalement, ce qui signifie que je devais constamment créer des index DB qui, à eux seuls, sont probablement plus chers que la recherche sans index.

Dans l'attente de vos pensées, merci!

Answer 1

Même si vos véhicules circulent constamment, je suppose qu'ils ont une limite de vitesse. Ce que vous pouvez faire est de créer une sorte de système de coordonnées discrètes, un exemple serait la partie entière de la coordonnée lat/long. Ensuite, vous mettez ces valeurs dans des colonnes séparées, en gardant l'emplacement exact dans une autre colonne. Vous devriez alors pouvoir indexer les colonnes entières, car les véhicules ne bougeront pas tellement qu'ils changeront très souvent ces valeurs. Lorsque vous effectuez une recherche, vous devez d'abord découvrir ce que les "carrés" sont intéressants, et restreindre votre requête aux vechicles à l'intérieur de ces sqeares, en utilisant les colonnes indexées. Ensuite, vous devez faire une recherche complète de tous les véhicules dans chaque carré. Le nombre de véhicules que vous devez faire une recherche complète devrait maintenant être seulement une petite fraction de tous les vechiles. L'efficacité de cette stratégie dépend bien entendu de la distribution de vos vechiles. Si 50% d'entre eux se trouvent dans une certaine ville quelque part cela ne fonctionnera pas, mais en supposant que le plus grand groupe de véhicules dans un endroit est de 5 à 10%, cela devrait améliorer la performance.

Answer 2

Si vous utilisez le bon algorithme pour organiser vos données, vous pourrez utiliser un spatial index qui peut considérablement accélérer vos requêtes.

La meilleure pratique pour le domaine de la géolocalisation est d'utiliser un geohash, quad-tree, R-tree ou structure de données similaire (R arbres sont les plus génériques, mais il semble que vous vous interrogez des données de point, de sorte que ne peut pas importer) . Dans chaque cas, vous pouvez créer un index spatial qui utilise une seule colonne linéaire dans laquelle chaque valeur représente une boîte englobante de taille et de forme différentes. Cela devrait vous permettre de répondre à la plupart des requêtes avec une seule requête de plage dans votre base de données. Les indices spatiaux peuvent être mis en œuvre dans SQL (PostGIS, MS SQL, MySQL ont tous types de données spatiales et indices spatiaux utilisant une de ces techniques) ou NoSQL (populaire pour son évolutivité horizontale, AppEngine a geomodel, SimpleGeo utilise Cassandra, Foursquare utilise MongoDB).

L'utilisation d'un index peut être compliquée par des points en mouvement constant, mais je pense que les écritures, même légèrement plus lourdes, que les index de mise à jour, ne seraient pas votre goulot d'étranglement.