Almacenamiento óptimo de la estructura de datos para una búsqueda rápida y persistencia.

Question

Guión

Tengo los siguientes métodos:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Inicialmente estoy pensando en el almacenamiento en el formulario:

itemId -> userId, userId, userId

y

userId -> itemId, itemId, itemId

AddItemSecurity se basa en cómo obtengo datos de una API de terceros, GetValidItemIds Así es como quiero usarlo en tiempo de ejecución.

Hay potencialmente 2000 usuarios y 10 millones de artículos.Las identificaciones de los artículos están en el formulario:2007123456, 2010001234 (10 dígitos donde los primeros cuatro representan el año).

AddItemSecurity no tiene que actuar súper rápido, pero GetValidIds necesita ser subsegundo.Además, si hay una actualización de un archivo existente itemId Necesito eliminar ese itemId para los usuarios que ya no están en la lista.

Estoy tratando de pensar en cómo debería almacenar esto de manera óptima.Preferiblemente en disco (con almacenamiento en caché), pero quiero que el código sea mantenible y limpio.

Si la identificación del elemento había comenzado en 0, pensé en crear una matriz de bytes de la longitud de MaxItemId / 8 para cada usuario y establecer un bit verdadero/falso si el elemento estaba presente o no.Eso limitaría la longitud de la matriz a poco más de 1 MB por usuario y brindaría búsquedas rápidas, así como una manera fácil de actualizar la lista por usuario.Al persistir en esto como Archivos asignados en memoria con el marco .Net 4 creo que también obtendría un almacenamiento en caché decente (si la máquina tiene suficiente RAM) sin implementar yo mismo la lógica de almacenamiento en caché.Analizar la identificación, eliminar el año y almacenar una matriz por año podría ser una solución.

La lista ItemId -> UserId[] se puede serializar directamente en el disco y leer/escribir con un modo normal. FileStream para conservar la lista y diferenciarla cuando haya cambios.

Cada vez que se agrega un nuevo usuario, todas las listas también deben actualizarse, pero esto se puede hacer todas las noches.

Pregunta

¿Debo seguir probando este enfoque o hay otros caminos que también deberían explorarse?Creo que el servidor SQL no funcionará lo suficientemente rápido y generaría una sobrecarga (al menos si está alojado en un servidor diferente), pero mis suposiciones podrían estar equivocadas.Se agradece cualquier idea o idea sobre el asunto.Y quiero intentar solucionarlo sin agregar demasiado hardware :)

[Actualización 2010-03-31]

Ahora he probado con SQL Server 2008 en las siguientes condiciones.

• Tabla con dos columnas (userid,itemid) ambas son Int
• Índice agrupado en las dos columnas.
• Se agregaron ~800.000 elementos para 180 usuarios - Total de 144 millones de filas
• RAM asignada de 4 GB para servidor SQL
• Portátil de doble núcleo a 2,66 ghz
• disco SSD
• Utilice un SqlDataReader para leer todos los ID de elemento en una lista
• Recorrer a todos los usuarios

Si ejecuto un hilo, el promedio es de 0,2 segundos.Cuando agrego un segundo hilo, sube a 0,4 segundos, lo cual todavía está bien.A partir de ahí los resultados van disminuyendo.Agregar un tercer hilo hace que muchas consultas duren hasta 2 segundos.Un cuarto hilo, de hasta 4 segundos, un quinto aumenta algunas de las consultas hasta 50 segundos.

La CPU está funcionando mientras esto sucede, incluso en un hilo.Mi aplicación de prueba requiere algo debido al ciclo rápido y SQL el resto.

Lo que me lleva a la conclusión de que no escalará muy bien.Al menos no en mi hardware probado.¿Hay formas de optimizar la base de datos, por ejemplo, almacenar una matriz de int por usuario en lugar de un registro por elemento?Pero esto hace que sea más difícil eliminar elementos.

[Actualización 2010-03-31 #2]

Hice una prueba rápida con los mismos datos colocándolos como bits en archivos mapeados en memoria.Funciona mucho mejor.Seis subprocesos producen tiempos de acceso entre 0,02 y 0,06 segundos.Puramente vinculado a la memoria.Los archivos mapeados fueron mapeados por un proceso y otros seis accedieron a ellos simultáneamente.Y como la base de SQL ocupaba 4 GB, los archivos en el disco ocupaban 23 MB.

Answer 1

Después de muchas pruebas, terminé usando archivos asignados en memoria, marcándolos con el bit disperso (NTFS), usando código de Archivos dispersos NTFS con C#.

Wikipedia tiene una explicación de lo que es archivo escaso es.

Los beneficios de usar un archivo disperso es que no tengo que preocuparme por el rango en el que se encuentran mis identificaciones.Si solo escribo identificaciones entre 2006000000 y 2010999999, el archivo solo asignará 625.000 bytes del desplazamiento 250.750.000 en el archivo.Todo el espacio hasta ese desplazamiento no está asignado en el sistema de archivos.Cada identificación se almacena como un bit establecido en el archivo.Algo así como tratado como una matriz de bits.Y si la secuencia de identificación cambia repentinamente, se asignará en otra parte del archivo.

Para recuperar qué ID están configurados, puedo realizar una llamada al sistema operativo para obtener las partes asignadas del archivo disperso y luego verifico cada bit en esas secuencias.Además, comprobar si una identificación particular está configurada es muy rápido.Si queda fuera de los bloques asignados, entonces no está allí; si está dentro, es simplemente una lectura de un byte y una verificación de máscara de bits para ver si está configurado el bit correcto.

Entonces, para el escenario particular en el que tienes muchas identificaciones que deseas verificar con la mayor velocidad posible, esta es la forma más óptima que he encontrado hasta ahora.

Y lo bueno es que los archivos asignados en memoria también se pueden compartir con Java (lo que resultó ser algo necesario).Java también admite archivos asignados en memoria en Windows, y la implementación de la lógica de lectura/escritura es bastante trivial.

Answer 2

Realmente creo que deberías probar una buena base de datos antes de tomar una decisión.Algo como esto será un desafío de mantener en el largo plazo.Su base de usuarios es bastante pequeña.SQL Server debería poder manejar lo que necesita sin ningún problema.

Answer 3

2000 usuarios no está tan mal, pero con 10 millones de elementos relacionados realmente deberías considerar poner esto en una base de datos.Las bases de datos realizan todo el almacenamiento, la persistencia, la indexación, el almacenamiento en caché, etc.que necesitas y funcionan muy bien.

También permiten una mejor escalabilidad hacia el futuro.Si de repente necesita lidiar con dos millones de usuarios y miles de millones de configuraciones, contar con una buena base de datos hará que el escalado no sea un problema.