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

Question

Dado que los discos de estado sólido (SSD) están disminuyendo de precio y pronto serán más frecuentes a medida que las unidades del sistema, y ??dado que sus tasas de acceso son significativamente más altas que los medios magnéticos giratorios, qué algoritmos estándar ganarán en rendimiento con el uso de ¿SSDs para almacenamiento local? Por ejemplo, la alta velocidad de lectura aleatoria de los SSD hace que una tabla hash basada en disco sea viable para grandes hashstables; Se dispone fácilmente de 4 GB de espacio en disco, lo que hace viable el hashing para todo el rango de un entero de 32 bits (más para la búsqueda que para la población, lo que aún llevaría mucho tiempo); Si bien este tamaño de una tabla hash sería prohibitivo trabajar con medios rotativos debido a la velocidad de acceso, no debería ser un problema tan grande con los SSD.

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

Answer 1

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

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

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

Answer 2

Los SSD son solo significativamente más rápidos para el acceso aleatorio. El acceso secuencial al disco tiene solo el doble de rendimiento que las unidades rotativas convencionales. Muchos SSD tienen peor rendimiento en muchos escenarios, lo que hace que tengan un rendimiento peor, como se describe aquí .

Si bien los SSD mueven la aguja considerablemente, siguen siendo mucho más lentos que las operaciones de la CPU y la memoria física. Para su ejemplo de tabla hash de 4GB, es posible que pueda mantener más de 250 MB / s de un SSD para acceder a cubos aleatorios de la tabla hash. Para una unidad de rotación, tendría la suerte de romper el MB / s de un solo dígito. Si puede mantener esta tabla hash de 4 GB en la memoria, podría 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 que MS realizó para Windows 7 cuando se ejecuta en SSD, lo que puede darle una idea del tipo de cambios que podría considerar realizar. Primero, SuperFetch para la captación previa de datos del disco está deshabilitado: está diseñado para evitar tiempos de acceso aleatorio lentos para el disco que se alivian mediante SSD. La desfragmentación está deshabilitada, porque tener archivos dispersos en el disco no es un problema de rendimiento para los SSD.

Answer 3

Ipso facto, cualquier algoritmo que se pueda imaginar que requiere mucha E / S aleatoria de disco (aleatoriamente es la palabra clave, que ayuda a lanzar el principio de localidad a las aves, eliminando así la utilidad de un montón de almacenamiento en caché que continúa).

Pude ver que ciertos sistemas de bases de datos se benefician de esto. 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 hash muy grandes serán su mejor opción para obtener buenos ejemplos.

Answer 4

Los SSD son mucho más rápidos para lecturas aleatorias, un poco para lecturas secuenciales y más lentos para escrituras (aleatorias o no).

Por lo tanto, una tabla hash basada en disco no es útil con un SSD, ya que ahora lleva mucho tiempo actualizarlo, pero buscar en el disco se vuelve (en comparación con un disco duro normal) muy barato.

Answer 5

No te engañes. Los SSD siguen siendo mucho más lentos que la memoria del sistema. Cualquier algoritmo que elija usar la memoria del sistema en el disco duro seguirá siendo mucho más rápido, todas las demás cosas serán iguales.