Escenarioalmacenamiento óptimo de estructura de datos para la búsqueda rápida y la persistencia
tengo los siguientes métodos:
public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)
Inicialmente estoy pensando de 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
es cómo quiero usarlo en tiempo de ejecución.
Hay potencialmente 2000 usuarios y 10 millones de elementos. Los identificadores de artículo están en el formulario: 2007123456, 20100(10 dígitos, donde los primeros cuatro representan el año).
AddItemSecurity
no tiene que realizar superrápido, pero GetValidIds
debe ser subsegundo. Además, si hay una actualización en un itemId
existente, necesito eliminar ese itemId para los usuarios que ya no están en la lista.
Estoy tratando de pensar cómo debería almacenar esto de manera óptima. Preferiblemente en el disco (con almacenamiento en caché), pero quiero que el código se pueda mantener y limpiar.
Si la identificación del artículo había comenzado en 0, pensé en crear una matriz de bytes con la longitud 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 proporcionaría búsquedas rápidas, así como una manera fácil de actualizar la lista por usuario. Al persistir esto como Memory Mapped Files con el framework .Net 4 creo que también obtendría un caché decente (si la máquina tiene suficiente RAM) sin implementar la lógica de almacenamiento en caché. Analizar el ID, 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 FileStream
normal para poder conservar la lista y diferenciarla cuando haya cambios.
Cada vez que se agrega un nuevo usuario, todas las listas tienen que actualizarse también, pero esto se puede hacer todas las noches.
Pregunta
¿Debo seguir para probar este enfoque, o hay otros caminos que deben ser exploradas, así? Estoy pensando que SQL Server no funcionará lo suficientemente rápido, y que daría una sobrecarga (al menos si está alojado en un servidor diferente), pero mis suposiciones podrían ser incorrectas. Cualquier pensamiento o idea sobre el asunto es apreciado. Y quiero tratar de resolverlo sin añadir demasiado hardware :)
[Actualización 2010-03-31]
ahora he probado con el servidor SQL 2008 bajo las siguientes condiciones.
- tabla con dos columnas (ID de usuario, itemid) ambos son Int
- índice agrupado en las dos columnas
- Añadido ~ 800.000 títulos para 180 usuarios - Total de 144 millones de filas
- asignados 4 GB de RAM para SQL servidor
- de doble núcleo a 2,66 GHz portátil
- disco SSD
- Use un SqlDataReader para leer todos los itemid de en una lista
- Circuito sobre todos los usuarios
Si ejecuto un hilo, promedia en 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 están disminuyendo. Agregar un tercer hilo trae muchas consultas hasta 2 seonds. Un cuarto hilo, hasta 4 segundos, un quinto aumenta algunas de las consultas hasta 50 segundos.
La CPU está tejiendo mientras esto sucede, incluso en una rosca. Mi aplicación de prueba tarda un poco debido al ciclo rápido, y sql el resto.
Lo que me lleva a la conclusión de que no se escalará muy bien. Al menos no en mi hardware probado. ¿Hay formas de optimizar la base de datos, digamos almacenar una matriz de int por usuario en lugar de un registro por artículo? 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 de ponerlo en forma de bits en archivos de memoria asignada. Se desempeña mucho mejor. Seis hilos producen tiempos de acceso entre 0.02s y 0.06s. Puramente limitado a la memoria. Los archivos mapeados fueron mapeados por un proceso y accedidos por otros seis simultáneamente. Y como la base sql tomó 4gb, los archivos en el disco tomaron 23mb.
Sé que está usando C# y no tengo idea de cómo se implementan los archivos mapeados en memoria allí, pero es posible que desee ver esto para Java: 'http : //download.oracle.com/javase/6/docs/api/java/nio/channels/FileChannel.html#map (java.nio.channels.FileChannel.MapMode, long, long) ' – user183037
" Cambios realizados en el El búfer resultante eventualmente se propagará al archivo, pueden o no ser visibles para otros programas que han mapeado el mismo archivo ". - Si está usando múltiples hilos, debería tener cuidado con esta parte. – user183037
No he tenido problemas con multi threading o multi proc accediendo al mismo archivo. Si no me equivoco, dos hilos/procesos accederán a la misma página de memoria en el sistema operativo si acceden a los mismos datos, y el sistema operativo se encargará del almacenamiento en caché/paginación/puesta en cola de las solicitudes. Dicho esto, no soy un experto y, en mi opinión, tengo un escritor y lectores múltiples, y perderse una vez no es gran cosa. Si necesita estar 100% seguro en la secuencia de eventos, entonces puede que no quiera usar mmf's. Pero confiaría mucho en esto, ya que los mmf son una de las formas recomendadas de compartir datos entre aplicaciones. –