Numérisation d'un milliard de lignes dans une base de données ultra-rapide

Contexte

Une base de données locale contient près de 1,3 milliard de lignes uniques. Chaque ligne est indirectement associée à une latitude et une longitude spécifiques (emplacement). Chaque ligne a un timbre à date.

Cas d'utilisation

Le problème est le suivant:

1. L'utilisateur définit une date de début / fin et une plage de valeurs (par exemple, 100 à 105).
2. Le système rassemble toutes les lignes qui correspondent à la date donnée, regroupées par emplacement.
3. Le système détermine les emplacements qui, pendant ces dates, ont une probabilité statistique de tomber dans la plage de valeurs donnée.
4. Le système affiche tous les emplacements correspondants à l'utilisateur.

C'est un problème de vitesse et d'échelle.

Question

Quelle est l'architecture de solution la moins chère que vous pouvez imaginer qui permettrait à un tel système de récupérer des résultats pour les utilisateurs en moins de cinq secondes?

Système actuel

L'environnement est actuellement:

• PostgreSQL 8.4 (la mise à niveau est possible; le changement de base de données n'est pas une option)
• R et PL / R
• XFS
• WD VelociRaptor
• 8 Go de RAM (Corsair G.Skill; 1,3 GHz)
• Quad core Genuine Intel 7 (2,8 GHz)
• Ubuntu 10.10

Les mises à niveau matérielles sont acceptables.

Mise à jour - Structure de la base de données

Les milliards de lignes sont dans un tableau ressemblant à:

id | taken | location_id | category | value1 | value2 | value3

• id - Clé primaire
• prise - Date affectée à la ligne
• location_id - Référence à la latitude / longitude
• catégorie - Une description des données
• value1 .. 3 - Les autres valeurs que l'utilisateur peut interroger

La takencolonne est généralement des dates consécutives par location_id, parfois chaque emplacement a des données de 1800 à 2010 (environ 77 000 dates, beaucoup d'entre elles étant dupliquées car chaque emplacement a des données dans la même plage de dates).

Il existe sept catégories et les tableaux sont déjà divisés par catégorie (en utilisant des tableaux enfants). Chaque catégorie contient environ 190 millions de lignes. Dans un avenir proche, le nombre de lignes par catégorie dépassera le milliard.

Il y a environ 20 000 emplacements et 70 000 villes. Les emplacements sont corrélés à la ville par la latitude et la longitude. Attribuer chaque emplacement à une ville particulière signifie trouver les limites de la ville, ce qui n'est pas une tâche triviale.

Des idées

Voici quelques idées que j'ai:

• Trouvez un service cloud pour héberger la base de données.
• Créez une bande de raid SSD (superbe vidéo).
• Créez un tableau qui regroupe tous les emplacements par ville (pré-calcul).

Je vous remercie!

La chose la plus importante est d'être absolument certain où le goulot d'étranglement est maintenant pour un nombre donné de demandes représentatives car vous ne pouvez pas changer de base de données.

Si vous effectuez des analyses complètes de table, vous avez besoin d'index appropriés.

Si vous attendez sur les E / S, vous avez besoin de plus de mémoire pour la mise en cache (Jeff Atwood a récemment mentionné que les systèmes 24 Gb étaient accessibles sur les systèmes de bureau).

Si vous attendez sur CPU, vous devez voir si vos calculs peuvent être optimisés.

Cela nécessite un chapeau DBA pointu et un chapeau de système d'exploitation, mais cela en vaut la peine pour vous assurer d'aboyer la bonne arborescence.

Que diriez-vous de partitionner la table en plusieurs morceaux situés sur différents hôtes en fonction de l'horodatage? Ceci est évolutif horizontalement, et tant que vous avez suffisamment de boîtes, vous pouvez écrire un petit moteur d'agrégation au-dessus de ces configurations.

Si vous voyez que l'horodatage change trop, vous pouvez alors partitionner en fonction des emplacements - à nouveau évolutif horizontalement. (Espérons qu'ils n'ajoutent pas beaucoup plus de latitudes / longitudes!)

Le pire scénario est que la plage de dates couvre toutes les dates de votre base de données.

Vous cherchez à lire 1,3 milliard d'enregistrements et à effectuer une sorte d'analyse sur chaque enregistrement par rapport aux valeurs entrées, sur une machine physique, en moins de 5 secondes. Le résultat peut être tous les emplacements ou aucun - vous ne savez rien à l'avance.

Compte tenu de ces paramètres, je dirais probablement impossible.

Il suffit de regarder votre disque dur: le taux maximum soutenu est inférieur à 150 Mo / s. La lecture de 1,3 milliard d'enregistrements prendra plus de 5 secondes. Côté CPU, vous ne pourrez pas faire d'analyse statistique sur 1,3 milliard d'enregistrements en 5 secondes.

Votre seul espoir (tm :-)) est de trouver une sorte de fonction de recherche basée sur les valeurs entrées par l'utilisateur qui restreindra la recherche (de quelques ordres de grandeur). Vous pouvez calculer cette fonction de recherche hors ligne. Sans en savoir plus sur les critères de correspondance exacts, je ne pense pas que quiconque puisse vous dire comment le faire, mais un exemple serait de partitionner la plage de valeurs en un intervalle discret et de créer une recherche qui vous donnera tous les enregistrements de cet intervalle. Tant que l'intervalle est suffisamment petit, vous pouvez y faire un vrai travail, par exemple l'élagage des entrées qui ne correspondent pas à la valeur entrée par l'utilisateur. Fondamentalement, échange d'espace contre du temps.

Il peut être possible de conserver tous les enregistrements (ou au moins la partie importante) en mémoire. Probablement pas en 8 Go. Cela éliminera au moins la partie d'E / S du disque, même si la bande passante mémoire peut être insuffisante pour tout parcourir en 5 secondes. En tout cas, c'est une autre technique pour accélérer ce genre d'applications (combiner avec ma suggestion précédente).

Vous mentionnez l'utilisation d'un service cloud. Oui, si vous payez pour suffisamment de CPU et de muscle IO et partitionnez votre base de données sur de nombreux serveurs, vous pouvez la forcer / diviser et la conquérir.

J'appuie le commentaire de rwong sur la question: PostgreSQL propose des types d'index et des outils appropriés (index GIST, index GIN, Postgis, types géométriques) de telle manière que les géodonnées et les données liées à l'heure / date devraient être consultables le long de ces critères sans trop de problèmes.

Si vos requêtes sur ces critères prennent quelques secondes, cela signifie probablement qu'aucun index de ce type n'est utilisé. Pouvez-vous confirmer que vous avez enquêté sur ces questions comme il convient?

Étant donné que vous utilisez PostgreSQL et des données de latitude / longitude, vous devez également utiliser PostGIS, de cette façon, vous pouvez ajouter un index spatial GiST à votre base de données pour accélérer les choses.

J'ai une telle table (avec 350k lignes) avec une configuration beaucoup plus petite que la vôtre (2 cœurs et à peine 2 Go de RAM) mais les recherches prennent moins d'une seconde.

Peut-être pourriez-vous casser un modèle relationnel comme Essbase l'a fait avec leur architecture OLAP: Essbase Wikipedia

Ce que je veux dire, c'est créer une table par ville, se retrouvant ainsi avec plus de 1000 tables. Pas une table comme vous l'avez suggéré, mais plusieurs. Indexez chaque table par date et lieu. De nombreuses tables, de nombreux index -> plus rapide.

En ce qui concerne votre idée de trouver un service cloud pour héberger la base de données, avez-vous déjà rencontré SimpleGeo ? Ils viennent de couper le ruban sur un service de stockage qui est apparemment "spécifiquement réglé pour stocker et interroger les données de localisation vraiment, très rapidement" - bien que le coût de stockage et d'interrogation sur plus d'un milliard de lignes puisse rendre cette approche irréalisable.

vous vous attendez à ce qu'un vélo roule sur l'autoroute. actuellement, vous cherchez une solution pour résoudre ce problème uniquement, vous ne prévoyez pas le problème si vous avez 2 milliards d'enregistrements? l'évolutivité doit être abordée. la réponse est des bases de données d'objets à usage simple. ex: cache intersystèmes

et croyez vous moi je ne suis pas intersystèmes ;-)