Algoritmos para optimización con almacenamiento en disco rápido (SSD)?

Question

Dado que los Discos de Estado Sólido (SSD) están disminuyendo en precio y pronto prevalecerán como unidades de sistema, y ​​dado que sus velocidades de acceso son significativamente más altas que los medios magnéticos rotativos, qué algoritmos estándar obtendrán en rendimiento del uso de SSD para el almacenamiento local? Por ejemplo, la alta velocidad de lectura aleatoria de las SSD hace que una tabla hash basada en disco sea una viabilidad para grandes hashstables; 4 GB de espacio en disco están disponibles, lo que hace viable la conversión a hash a todo el rango de un entero de 32 bits (más para la búsqueda que para la población, que aún tardaría mucho tiempo); mientras que este tamaño de una tabla hash sería prohibitivo para trabajar con medios giratorios debido a la velocidad de acceso, no debería ser un problema tanto con SSD.

¿Hay otras áreas donde la inminente transición a SSD proporcionará ganancias potenciales en el rendimiento algorítmico? Prefiero ver el razonamiento sobre cómo una cosa funcionará en lugar de la opinión; No quiero que esto se vuelva polémico.

Answer 1

Su ejemplo de hashtables es de hecho la estructura de base de datos clave que se beneficiará. En lugar de tener que cargar un archivo completo de 4 GB o más en la memoria para buscar valores, la SSD puede probarse directamente. El SSD es aún más lento que la RAM, por órdenes de magnitud, pero es bastante razonable tener una tabla hash de 50GB en el disco, pero no en la memoria RAM a menos que pague mucho dinero por una gran plancha.

Un ejemplo son las bases de datos de posiciones de ajedrez. Tengo más de 50 GB de posiciones hash. Existe un código complejo para tratar de agrupar las posiciones relacionadas entre sí en el hash, por lo que puedo buscar en 10 MB de la tabla a la vez y espero reutilizar algo para múltiples consultas de posición similares. Hay un montón de código y complejidad para hacer esto eficiente.

Reemplazado con una SSD, pude eliminar toda la complejidad de la agrupación en clústeres y simplemente utilizar hash aleatorios realmente tontos. También obtuve un aumento en el rendimiento ya que solo obtengo los datos que necesito del disco, no grandes fragmentos de 10MB. La latencia es de hecho más grande, pero la aceleración neta es significativa ... y el código de súper limpieza (20 líneas, no más de 800) es quizás aún más agradable.

Answer 2

No te engañes. Los SSD todavía son mucho más lentos que la memoria del sistema. Cualquier algoritmo que elija usar la memoria del sistema sobre el disco duro va a ser mucho más rápido, en igualdad de condiciones.

Answer 3

Las SSD son solo significativamente más rápidas para el acceso aleatorio. El acceso secuencial al disco es solo dos veces más eficiente que las unidades de rotación convencionales. Muchos discos SSD tienen un peor rendimiento en muchos escenarios, lo que los hace funcionar peor, como se describe en here.

Mientras que los SSD mueven la aguja considerablemente, son mucho más lentos que las operaciones de la CPU y la memoria física. Para su ejemplo de tabla hash de 4 GB, puede ser capaz de mantener más de 250 MB de un SSD para acceder a los cubos aleatorios de la tabla hash. Para una unidad de rotación, sería afortunado romper los MB/s de un solo dígito. Si puede mantener esta tabla hash de 4 GB en la memoria, puede acceder a ella en el orden de gigabytes por segundo, mucho más rápido que incluso un SSD muy rápido.

El artículo al que se hace referencia enumera varios cambios realizados por MS para Windows 7 cuando se ejecuta en SSD, lo que puede darle una idea del tipo de cambios que podría considerar realizar. En primer lugar, está desactivado SuperFetch para la obtención previa de datos fuera del disco; está diseñado para evitar tiempos de acceso aleatorio lentos para el disco que se alivian con los SSD. Defrag está deshabilitado, porque tener archivos dispersos en el disco no es un golpe de rendimiento para las SSD.

Answer 4

Ipso facto, cualquier algoritmo que se pueda imaginar que requiera muchas E/S de disco aleatorias (al azar es la palabra clave, que ayuda a arrojar el principio de localidad a las aves, eliminando la utilidad de mucho almacenamiento en caché eso continúa).

Pude ver ciertos sistemas de bases de datos ganando de esto sin embargo. MySQL, por ejemplo, utilizando el motor de almacenamiento MyISAM (donde los registros de datos son básicamente CSV glorificados). Sin embargo, creo que las tablas grandes serán la mejor opción para obtener buenos ejemplos.

Answer 5

Las SSD son mucho más rápidas para las lecturas aleatorias, un poco para las lecturas secuenciales y más lentas para las escrituras (aleatorias o no).

Así que una tabla hash basada en disco es correctamente no útil con una SSD, ya que ahora lleva mucho tiempo actualizarla, pero la búsqueda en el disco se vuelve (en comparación con un disco duro normal) muy barata.