Designing Data-Intensive Applications: 3. Storage and Retrieval

[guilleiguaran]

Esta semana a cargo @ricardorojass
Siguiente semana @julianduque

[ricardorojass]

Capítulo 3 Storage and Retrieval

Data Structures that power Databases

• Un log es una sequencia unica de registros usada por muchas bases de datos en varias formas.
• An index es una estructura de datos que puede mejorar el desempeño de la busqueda derivado del dato primario.
• Los index escogidos manualmente de forma correcta aceleran la lectura de las consultas, pero ralentiza la escritura.
• Compaction es un concepto general de remover los valores con segmentos antiguos y/o duplicados de los logs .

Hash indexes

• Hay ejemplos que incluyen mantener en memoria un hash map donde cada key es mapeada en disco.
  • Ideal para situaciones en las que el valor de cada key se actualiza con frecuencia.
  • Ideal para situaciones en las que el numero de keys es bajo.
• No es bueno para consultas de rango ya que los keys no estan ordenadas.

Ventajas de los logs

• Crash recovery: Todos los valores se guardan hasta que ya no se necesite, no hay problema si falla la actualizacion de un valor.
• Concurrency: Las actualizaciones se hacen en orden secuencial estricto y pueden ocurrir operaciones de lectura en concurrencia(multiple threads).
• Compactacion de datos antiguos evita el problema que los datos comiencen a fragmentarse todo el tiempo.

SSTables and LSM-Trees

• En lugar de mantener un log de valores sin clasificar, mantenga las secuencias de key-values ordenadas por clave.
  • El formato es llamado Sorted String Table(SSTable). Cada key solo debe aparecer una vez por archivo de segmento fusionado.
• Fusionar segmentos es mas simple y eficiente y se puede usar el algoritmo merge-sort.
• Se puede mantener un index de repuesto en lugar de todas las keys en la memoria, ya que todas las keys son secuenciales y se pueden usar para determinar la ubicacion de las keys en disco.
• Facil para comprimir segmentos ya que necesitan ser escaneados y recuperados de todos modos, ahorrando espacio en disco y tiempo en I/O.

B-Trees

• B-Trees pueden ser fragmentados todo el tiempo.
• LSM-Trees pueden ser comprimidos de una mejor manera.

Other Indexing Structures

• Secondary indexes: En bases de datos relacionales es muy comun poder crear varios index secundarios para mejorar el desempeño de los joins.
• Multi-column indexes
  • El Index concatenado concatena las keys en funcion del orden de clasificacion.
• Full-text search / fuzzy index
  • Permite hacer busquedas para keys similares, asi como tambien palabras mal escritas.
• In-memory database are growing
  • El costo en GB se esta reduciendo para el almacenamiento en RAM, lo que permite bases de datos en memoria mas baratas.
  • Soluciones para la durabilidad, como la escritura periodica en disco, hardware especial(battery-powered RAM) o estado de replicacion en otras maquinas.
  • El rendimiento in-memory no solo tiene que escribir en disco, sino que no necesita codificar las estructuras de datos en la memoria a algo que se pueda escribir y recuperar de manera eficiente en el disco.

Data Warehouses

• OLTP - online transaction processing
  • Numero pequeño de registros/consultas, utilizado para el usuario final y tener el ultimo estado de los datos.
• OLAP - online analytics processing
  • Gran numero de registros, historial de eventos, utilizado internamente para inteligencia empresarial.
• Column-oriented storage
  • Mas eficiente cuando las consultas solo necesitan pocas columnas, en lugar de cargar todas las filas, solo carga las columnas que necesita.
  • Cada columna es dueña de su propio archivo y es n de largo, con n como numero de filas.
  • Puede ser comprimido muy eficientemente usando bitmap encoding.
  • Escribir puede ser mas complicado, y usa LSM-Trees a menudo.
• Materialzed Views
  • Tablas de datos escritas que estan desnormalizadas, son mas rapidas para consultas ya que los valores estan precalculados.