- No se te ocurren estructuras de datos o algoritmos “totalmente nuevos”. Casi todas las ideas “nuevas” se basan en el conocimiento existente. Por ejemplo, los árboles rojo-negros (1972) son árboles de búsqueda binarios más metadatos utilizados para el equilibrio que son más rápidos que los árboles AVL (el primer BST de autoequilibrio inventado en 1962) para inserciones y eliminaciones.
- Toma lo que sabe y da un salto intuitivo más allá.
Por ejemplo:
Empiezas con un problema. El segundo dispositivo de almacenamiento en bloque de escalamiento horizontal en el que trabajé tuvo problemas con los tiempos de espera de SCSI donde los volúmenes dejaron de responder durante decenas de segundos. Rastreé el problema hasta el subsistema que asignaba persistentemente bloques de volumen de clientes a direcciones locales que estaba compuesto por un diario de transacciones circulares que volcaba las entradas a una matriz con entradas en orden de página física cuando todavía diferían en el momento en que se sobrescribían. Las escrituras en la matriz eran escrituras aleatorias con una granularidad de sector de 512 bytes. Todas las escrituras en el sistema pasaron por un caché no volátil que se vació a través del algoritmo del elevador. Cuando ocurrieron muchos cambios permanentes (como que las páginas se movieran a una instantánea más nueva que todavía existía cuando se eliminó una más antigua), las escrituras secuenciales se bloquearon en escrituras aleatorias por un total del mismo tamaño. Una sola escritura secuencial de 256K podría bloquearse durante 4 segundos ya que las escrituras aleatorias de 512 512 bytes se enjuagaron.
El caché no volátil también tenía la misma vulnerabilidad a la pérdida de energía con las escrituras en vuelo que los medios giratorios, lo que significa que podría tener datos antiguos, datos nuevos o un error de lectura con granularidad de sector. Si esto sucediera, tendríamos que reconstruir un servidor de almacenamiento completo porque no sabíamos qué bloques lógicos estaban en las páginas físicas asignadas por las entradas de matriz perdidas. Se produciría una pérdida de datos del cliente si esto le sucediera a la última copia autorizada durante un evento de falla múltiple.
- ¿Existe un algoritmo para contar el número de subcadenas cuya suma es divisible por 3?
- ¿Qué habilidades matemáticas son necesarias para la programación de computadoras?
- ¿Qué entero decimal está representado por 0xE4 en una notación de complemento a dos de 8 bits?
- ¿Podemos obtener una función continua si la variable de entrada es discreta?
- ¿Cuándo fue la última vez que se descubrió el número primo más grande sin la ayuda de una computadora?
Mira otros requisitos y datos relacionados. Todos los datos de mapeo de páginas caben en la memoria. La estructura de datos tenía que manejar transacciones que abarcaban múltiples entradas, aunque la mayoría afectaba una página (márquela sucia o limpia con respecto a sus réplicas) y no estábamos usando ninguna que afectara más de dos páginas. Las escrituras secuenciales en el disco giratorio son relativamente rápidas, en ese momento se ejecutan alrededor de 50M / segundo o 100K sectores / segundo. La mayor parte del tiempo en IO más cortas es el tiempo de búsqueda y la latencia rotacional con cada bloque adicional que cuesta poco. Las escrituras aleatorias son lentas, en ese momento se ejecutan alrededor de 70-120 sectores / segundo dependiendo de la profundidad de la cola. Las entradas de página tenían menos de 32 bytes, por lo que había espacio adicional en los sectores donde se escribía en el diario con solo una o dos entradas.
Mira qué más sabes. Leí los documentos de John Osterhout y Margo Seltzer sobre sistemas de archivos estructurados de registro y construí una variante para mi último dispositivo de almacenamiento de bloques de escala horizontal, donde lo fundamental es que escriba datos en cualquier espacio disponible, nunca sobrescriba en el lugar, y en algunos punto podría recoger basura.
Considere otros enfoques que sabe que no funcionarán y tenga en cuenta sus deficiencias. Por ejemplo, podría volcar una copia de matriz completa a la vez y alternar entre versiones válidas. Sin embargo, en mi producto anterior noté que las escrituras secuenciales más grandes podrían causar problemas de latencia con la cola ingenua implementada por las unidades de disco que tenían implicaciones comerciales negativas debido a los clientes de referencia utilizados al comprar hardware para ejecutar servidores de Microsoft Exchange.
Después de pensar en los callejones sin salida, da el salto intuitivo: ¿qué tal una estructura circular que no se voltea en otro lugar? Mezcle las entradas de “actualización” en orden de bloque físico con nuevas entradas de transacciones y conserve la invariante de nunca sobrescribir la entrada estable de un iteración circular anterior o su reemplazo hasta que esos datos se hayan reescrito más a lo largo del registro. Las escrituras individuales no necesitan ser más grandes que un solo sector para un impacto de latencia limitado y las escrituras múltiples siempre son secuenciales, excepto cuando el registro se ajusta. Preservar la invariante es más simple de lo que parece: simplemente no permite que el nuevo extremo del registro en vuelo se acerque más al nuevo final actual que la cantidad de sectores necesarios para mantener un conjunto de datos completo.
Podría caber 13 entradas en un sector de 512 bytes. Usando 1 para actualizar y 12 para nuevos datos (el código admitía una combinación arbitraria de entradas nuevas / antiguas y no necesitaba ambas en cada sector, pero esa mezcla hace que la aritmética sea divertida) a 100K sectores / segundo que fueron 1.2M entradas de registro un segundo versus una tasa de descarga máxima de 120 por segundo, 10,000 veces más rápido. Como todos los bloques siempre se reescribieron, no hubo oportunidad para la descomposición de bits. La gran ganancia de rendimiento también significó que con la combinación no volátil de caché y escritura, haciendo secuencias secuenciales intercaladas secuenciales en la salida, podría duplicarlo para eliminar los modos de falla objetables y seguir siendo 5000X más rápido.
El código de clasificación / descomposición se convirtió en el nuevo cuello de botella que nos limita a 7000 entradas por segundo con estructuras de datos replicadas (frente a 120 antes sin replicar), que es solo una mejora de 58X, pero fue suficiente para mover el impacto de eliminación de instantáneas por debajo del nivel de ruido de medición en lugar de causar 30 segundos + demoras.
HP adquirió LeftHand Networks por $ 360 millones y (presumiblemente, funcionó muy bien) vende mi estructura de datos en la HP P4000 SAN en forma de dispositivos físicos y virtuales.
