Escanear mil millones de filas en una base de datos ultrarrápida

Antecedentes

Una base de datos local contiene casi 1.300 millones de filas únicas. Cada fila está asociada indirectamente con una latitud y longitud (ubicación) específicas. Cada fila tiene un sello de fecha.

Caso de uso

El problema es el siguiente:

1. El usuario establece una fecha de inicio / finalización y un rango de valores (por ejemplo, 100 a 105).
2. El sistema reúne todas las filas que coinciden con la fecha dada, agrupadas por ubicación.
3. El sistema realiza determina las ubicaciones que, durante esas fechas, tienen una probabilidad estadística de caer en el rango de valores dado.
4. El sistema muestra todas las ubicaciones coincidentes para el usuario.

Este es un problema de velocidad y escala.

Pregunta

¿Cuál es la arquitectura de solución menos costosa que pueda imaginar que permitiría que dicho sistema recupere resultados para los usuarios en menos de cinco segundos?

Sistema actual

El entorno es actualmente:

• PostgreSQL 8.4 (la actualización es posible; cambiar de base de datos no es una opción)
• R y PL / R
• XFS
• WD VelociRaptor
• 8 GB de RAM (Corsair G.Skill; 1.3 GHz)
• Quad Core Genuino Intel 7 (2.8 GHz)
• Ubuntu 10.10

Las actualizaciones de hardware son aceptables.

Actualización: estructura de la base de datos

Los miles de millones de filas están en una tabla similar a:

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

• id: clave principal
• tomado - Fecha asignada a la fila
• location_id - Referencia a la latitud / longitud
• categoría: una descripción de los datos
• valor1 .. 3 - Los otros valores que el usuario puede consultar

La takencolumna suele tener fechas consecutivas por location_id, a veces cada ubicación tiene datos de 1800 a 2010 (aproximadamente 77,000 fechas, muchas de ellas duplicadas ya que cada ubicación tiene datos en el mismo rango de fechas).

Hay siete categorías y las tablas ya están divididas por categoría (usando tablas secundarias). Cada categoría contiene ~ 190 millones de filas. En el futuro cercano, el número de filas por categoría superará los mil millones.

Hay aproximadamente 20,000 ubicaciones y 70,000 ciudades. Las ubicaciones están correlacionadas con la ciudad por latitud y longitud. Asignar cada ubicación a una ciudad en particular significa encontrar los límites de la ciudad, lo cual no es una tarea trivial.

Ideas

Algunas ideas que tengo incluyen:

• Encuentre un servicio en la nube para alojar la base de datos.
• Cree una banda de incursión SSD (excelente video).
• Cree una tabla que amalgame todas las ubicaciones por ciudad (cálculo previo).

¡Gracias!

Lo más importante es estar absolutamente seguro de dónde está ahora el cuello de botella para un número determinado de solicitudes representativas, ya que no puede cambiar las bases de datos.

Si realiza escaneos completos de la tabla, necesita índices apropiados.

Si espera en E / S, necesita más memoria para el almacenamiento en caché (Jeff Atwood mencionó recientemente que los sistemas de 24 Gb eran accesibles en sistemas de escritorio).

Si espera en la CPU, necesita ver si sus cálculos pueden optimizarse.

Esto requiere un sombrero DBA puntiagudo y un sombrero de sistema operativo, pero vale la pena para asegurarse de que está ladrando el árbol correcto.

¿Qué hay de dividir la tabla en varias partes ubicadas en diferentes hosts en función del sello de fecha? Esto es escalable horizontalmente, y siempre que tenga un número suficiente de cuadros, podría escribir un pequeño motor de agregación sobre estas configuraciones.

Si ve que el sello de fecha está cambiando demasiado, entonces podría realizar una partición en función de las ubicaciones, nuevamente escalable horizontalmente. (¡Ojalá no agreguen muchas más latitudes / longitudes!)

El peor de los casos es que el rango de fechas cubra todas las fechas en su base de datos.

Está buscando leer 1.300 millones de registros y hacer algún tipo de análisis en cada registro frente a los valores ingresados, en una máquina física, en menos de 5 segundos. El resultado puede ser todas las ubicaciones o ninguna: no sabe nada de antemano.

Dados estos parámetros, diría que probablemente imposible.

Basta con mirar su disco duro: la velocidad máxima sostenida es inferior a 150 MB / s. Leer 1.300 millones de registros llevará más de 5 segundos. En cuanto a la CPU, no podrá realizar ningún tipo de análisis estadístico de 1.300 millones de registros en 5 segundos.

Su única esperanza (tm :-)) es encontrar algún tipo de función de búsqueda basada en los valores ingresados ​​por el usuario que reducirá la búsqueda (en unos pocos órdenes de magnitud). Puede calcular esta función de búsqueda sin conexión. Sin saber más sobre los criterios de coincidencia exacta, no creo que nadie pueda decirle cómo hacerlo, pero un ejemplo sería dividir el rango de valores en un intervalo discreto y crear una búsqueda que le brinde todos los registros en ese intervalo. Siempre que el intervalo sea lo suficientemente pequeño, puede hacer un trabajo real en él, por ejemplo, eliminar las entradas que no coinciden con el valor introducido por el usuario. Básicamente intercambiando espacio por tiempo.

Es posible conservar todos los registros (o al menos la parte importante) en la memoria. Probablemente no en 8GB. Esto al menos eliminará la porción de E / S del disco, aunque incluso el ancho de banda de la memoria puede ser insuficiente para escanear todo en 5 segundos. En cualquier caso, esta es otra técnica para acelerar este tipo de aplicaciones (combinar con mi sugerencia anterior).

Menciona el uso de un servicio en la nube. Sí, si paga suficiente CPU e IO muscular y particiona su base de datos en muchos servidores, puede forzar / dividir y conquistarla.

Segundo comentario de rwong a la pregunta: PostgreSQL ofrece tipos y herramientas de índices apropiados (índices GIST, índices GIN, Postgis, tipos geométricos) de tal manera que los datos relacionados con la geodata y la fecha y hora se puedan buscar a lo largo de esos criterios sin muchos problemas.

Si sus consultas sobre estos criterios toman segundos, probablemente significa que no se están utilizando dichos índices. ¿Puedes confirmar que has investigado esto según corresponda?

Dado que usa PostgreSQL y los datos de latitud / longitud, definitivamente también debe usar PostGIS, de esa manera puede agregar un índice espacial GiST a su base de datos para ayudar a acelerar las cosas.

Tengo una tabla de este tipo (con 350k filas) con una configuración mucho más pequeña que la suya (2 núcleos y apenas 2Gb de RAM) pero las búsquedas toman menos de un segundo.

Tal vez podría romper un modelo relacional como hizo Essbase con su arquitectura OLAP: Essbase Wikipedia

Lo que quiero decir es crear una tabla por ciudad, terminando así con más de 1000 tablas. No una mesa como usted sugirió, sino muchas. Indice cada tabla por fecha y ubicación. Muchas tablas, muchos índices -> más rápido.

En cuanto a su idea de encontrar un servicio en la nube para alojar la base de datos, ¿ya se ha encontrado con SimpleGeo ? Simplemente cortan la cinta en un servicio de almacenamiento que aparentemente está "específicamente ajustado para almacenar y consultar datos de ubicación realmente, muy rápido", aunque el costo de almacenar y consultar en más de mil millones de filas podría hacer que este enfoque sea inviable.

Esperas que una bicicleta corra en la carretera. actualmente está buscando una solución para abordar este problema solamente, no está previendo el problema, ¿qué pasa si tiene 2 mil millones de registros? la escalabilidad debe ser abordada. La respuesta es simple uso de bases de datos de objetos. por ejemplo, caché Intersystems

y créeme, no soy de un sistema intermedio ;-)