Estructuras de datos para aplicaciones intensivas en datos [PDF]

 (cs-people.bu.edu)
4 puntos por GN⁺ 2024-02-10 | 1 comentarios | Compartir por WhatsApp
  • Las estructuras de datos clave-valor son un componente central de los sistemas basados en datos, y su rendimiento puede variar mucho según la carga de trabajo y las condiciones del hardware
  • La estructura física se divide en datos distribuidos, metadatos para la exploración y algoritmos de almacenamiento y búsqueda; también se les llama métodos de acceso, contenedores de datos o estructuras de búsqueda
  • La carga de trabajo se expresa como una combinación de consultas puntuales, consultas por rango, inserciones, eliminaciones y modificaciones, y la capacidad y el costo de la memoria y del almacenamiento persistente también forman parte de los requisitos de diseño
  • El B+-tree es fuerte en lectura y consultas por rango, pero cuando aumentan las inserciones y modificaciones, la reorganización de nodos hoja se vuelve una carga; el LSM-tree maneja muchas inserciones mediante buffering y fusiones
  • En entornos donde el movimiento de datos se vuelve el cuello de botella, hay que elegir estructuras existentes o diseñar nuevas según las nuevas aplicaciones, los cambios de hardware y el crecimiento de los datos

El problema que resuelven las estructuras de datos clave-valor

  • Las estructuras de datos clave-valor se usan ampliamente en aplicaciones intensivas en datos y, por la versatilidad del modelo clave-valor, sirven como base de muchos sistemas
  • Una clave se asigna a un valor, pero un mismo valor puede estar vinculado a varias claves
  • El significado del valor cambia según la aplicación
    • Puede ser un registro de una base de datos relacional
    • Puede ser un DataFrame de Pandas
    • Puede ser un conjunto de campos que una aplicación analiza y utiliza en un sistema NoSQL
    • En sistemas que manejan datos de redes sociales, puede incluir referencias a objetos grandes como imágenes o videos

Composición física y alcance de aplicación

  • Físicamente, una estructura de datos clave-valor se compone de tres elementos
    • Datos almacenados con un layout específico
    • Metadatos opcionales que ayudan a explorar los datos
    • Algoritmos que soportan operaciones de almacenamiento y búsqueda
  • Las estructuras de datos se usan de distintas formas en sistemas de datos, sistemas operativos, sistemas de archivos, compiladores y sistemas de red
  • Los ejemplos del libro se centran principalmente en sistemas de datos a gran escala y dispositivos de almacenamiento secundario, pero el análisis y el enfoque de diseño también aplican a sistemas en memoria
  • Este análisis está orientado a entornos con jerarquías de memoria y almacenamiento de dos o más niveles

La carga de trabajo y el costo determinan el diseño

  • La aplicación o carga de trabajo puede representarse como una combinación de operaciones clave-valor

    • Consultas puntuales

    • Consultas por rango

      • Inserción
      • Eliminación
      • Modificación
      • La capacidad necesaria y el costo de la memoria y del almacenamiento persistente también forman parte de los requisitos de la aplicación
      • La estructura de datos que debe optimizarse cambia según el tipo de sistema
      • Los sistemas de archivos administran metadatos y contenido de archivos con estructuras de datos optimizadas para actualizaciones frecuentes
      • Los compiladores administran variables con un hash map durante el ciclo de vida de las variables y representan la forma completa del programa como un abstract syntax tree
      • Los dispositivos de red necesitan estructuras de datos especializadas para almacenar y acceder eficientemente a tablas de enrutamiento

El contraste entre B+-tree y LSM-tree

  • El B+-tree se usa mucho para equilibrar costo de lectura y costo de escritura en cargas de trabajo con pocas inserciones y actualizaciones, y muchas consultas puntuales y por rango
  • Un alto fan-out de nodos reduce los accesos a memoria auxiliar necesarios al bajar desde la raíz hasta la hoja, y los niveles superiores se almacenan en caché en jerarquías de memoria más rápidas
  • Mantiene todas las claves ordenadas en los nodos hoja y enlaza los nodos hoja como una lista ligada para soportar consultas por rango
  • Cuando aumentan las inserciones y actualizaciones, se requiere reorganizar o dividir nodos hoja, lo que puede convertirse en un cuello de botella de rendimiento
  • El LSM-tree usa un enfoque distinto para cargas de trabajo con muchas inserciones
    • Coloca todas las actualizaciones en un buffer común en memoria
    • Cuando el buffer se llena, lo vacía a disco
    • Cuando se acumulan buffers, los fusiona en colecciones de datos ordenados más grandes
    • Las modificaciones se manejan con una política out-of-place, y dentro de la estructura pueden existir varias parejas clave-valor con la misma clave
    • El valor actual de una clave específica lo tiene la pareja clave-valor insertada más recientemente

Estructuras de datos adaptativas

  • Además del enfoque de diseñar una estructura de datos anticipando la carga de trabajo, también se abordan estructuras que se acercan gradualmente a una forma ideal durante la ejecución
  • En su diseño original, B+-tree y LSM-tree imponen ordenamiento dentro de nodos residentes en disco para responder todas las consultas puntuales o por rango
  • Las estructuras de datos adaptativas pueden comenzar con uno o más nodos desordenados y ordenarse gradualmente cuando surge la oportunidad
  • Database cracking usa los patrones de acceso de las consultas entrantes para reorganizar físicamente los datos subyacentes de forma continua e incremental
  • El objetivo es mejorar el rendimiento de consultas futuras

Jerarquía de hardware y muro de memoria

  • La evolución del hardware crea nuevos retos y oportunidades para el diseño de estructuras de datos
  • En la jerarquía de almacenamiento, los niveles inferiores ofrecen más espacio a menor precio pero con mayor latencia de acceso, mientras que los niveles superiores, más cercanos al procesador, son más rápidos pero más pequeños y con mayor costo por byte
  • La capa que se convierte en cuello de botella para una aplicación específica depende del tamaño de los datos de la aplicación y de la capacidad de almacenamiento de cada nivel
  • El B+-tree originalmente buscaba maximizar el fan-out para reducir accesos a disco, pero a medida que la memoria creció y los datos pasaron a caber en RAM o en memoria auxiliar no volátil, los trade-offs cambiaron de forma importante
  • Los B+-tree en memoria muestran el mejor rendimiento con fan-out pequeño
  • El muro de memoria (memory wall) se refiere a la tendencia de ampliación de la brecha entre la velocidad del procesador y la velocidad de la memoria fuera del chip
  • Desde inicios de los años 2000, los sistemas operativos y los sistemas de gestión de datos se han rediseñado para optimizar el uso de la memoria caché

Espacio de diseño y lineamientos

  • Se organiza el espacio de decisiones del diseño de estructuras de datos y se explica cómo elegir la estructura adecuada según los objetivos de la aplicación y la carga de trabajo
  • Como el hardware y las propiedades de los datos siguen cambiando, el diseño de estructuras de datos también requiere innovación continua
  • El espacio de diseño organizado y los lineamientos sirven para elegir la estructura existente más adecuada o para diseñar una nueva estructura de datos ajustada a una carga de trabajo específica

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-02-10
Opiniones en Hacker News

  • Apenas lo hojeé, pero este texto es un material de investigación excelente que cubre un campo enorme.
    No se limita a enumerar estructuras de datos: ayuda a ordenar mentalmente los factores que hay que considerar al crear o usar estructuras de datos en aplicaciones.

    • Entra fácilmente entre los mejores libros técnicos que he leído.

  • Uno de los autores de este libro dirige un laboratorio de investigación en esta área.
    También tienen una herramienta genial que ayuda a diseñar estructuras de datos óptimas: http://daslab.seas.harvard.edu/datacalculator/

    • Es difícil encontrar dónde está la herramienta real.

  • Me gustaría conocer más recursos recomendados sobre este tema.
    El paper es excelente, y conozco Designing Data-Intensive Applications de Martin Klepmann, pero ese libro está más cerca de las bases de datos que de las estructuras de datos.

  • Falta la comparación entre array de estructuras y estructura de arrays, que es muy importante si estás diseñando una estructura para contener ciertos tipos de datos analíticos.

    • En la sección 6.1 se tratan las ventajas y desventajas del almacenamiento orientado a filas y orientado a columnas, y sus motivos.
      Así que sí lo discuten, pero no lo explican con los términos array de estructuras/estructura de arrays.

  • Me gustaría comprar un ejemplar, pero en Amazon cuesta 100 dólares.

    • Sigo esperando que alguien innove en la industria del libro y rompa la dependencia de Amazon.
      Es una estructura rota en la que pierden tanto los autores como los lectores.

  • Hace falta una tabla de contenidos.

    • Si lo abres con Firefox, se ve la tabla de contenidos completa: https://imgur.com/a/cgdy0nY
    • Subí el PDF y le pedí a ChatGPT 4 que generara una tabla de contenidos, pero le está costando bastante procesarlo.
      Pasó lo mismo aunque le pedí que ignorara los encabezados y pies de página; pensé que el estado del arte ya había mejorado mucho más.