database - optimizador - cuando usar indices en base de datos
Sorted String Table(SSTable) o B+Tree para un índice de base de datos? (4)
Usando dos bases de datos para ilustrar este ejemplo: CouchDB y Cassandra .
CouchDB
CouchDB usa un Árbol B + para índices de documentos (usando una modificación inteligente para trabajar en su entorno de solo apéndice). Más específicamente, a medida que se modifican los documentos (insertar / actualizar / eliminar), se anexan al archivo de base de datos en ejecución, así como a una hoja completa. -> Ruta del nodo desde el árbol B + de todos los nodos efectuados por la revisión actualizada justo después del documento.
Estas revisiones indexadas por pieza están alineadas junto con las modificaciones, de modo que el índice completo es una unión de las modificaciones de índice más recientes adjuntas al final del archivo junto con las piezas adicionales más atrás en el archivo de datos que aún son relevantes y no han sido incluidas. ha sido modificado aún
La búsqueda del árbol B + es O (logn).
Cassandra
Cassandra mantiene las claves de registro ordenadas, en memoria, en tablas (pensemos en ellas como matrices para esta pregunta) y las escribe como tablas separadas (ordenadas) de cadenas ordenadas de vez en cuando.
Podemos pensar en la colección de todas estas tablas como el "índice" (según tengo entendido).
Se requiere que Cassandra compacte / combine estas tablas de cadenas ordenadas de vez en cuando, creando una representación de archivo más completa del índice.
La búsqueda de una matriz ordenada es O (logn).
Pregunta
Asumiendo un nivel similar de complejidad entre mantener parcial B + trozos de árbol en CouchDB versus índices parciales de cadena ordenada en Cassandra y dado que ambos proporcionan O (logn) tiempo de búsqueda cuál crees que haría una mejor representación de un índice de base de datos y por qué ?
Estoy especialmente curioso si hay un detalle de implementación sobre uno que hace que sea particularmente atractivo o si ambos son un lavado y simplemente elige cualquier estructura de datos con la que prefiera trabajar / tiene más sentido para el desarrollador.
Gracias por los pensamientos.
Al comparar un índice de BTree con un índice de SSTable, debe considerar la complejidad de escritura:
Al escribir aleatoriamente en un BTree de copiado en escritura, incurrirá en lecturas aleatorias (para hacer la copia del nodo y la ruta de la hoja). Por lo tanto, mientras escribe mi ser secuencial en el disco, para conjuntos de datos más grandes que la RAM, estas lecturas aleatorias se convertirán rápidamente en el cuello de la botella. Para un índice similar a SSTable, tal lectura no ocurre en la escritura, solo habrá escrituras secuenciales.
También debería considerar que, en el peor de los casos, cada actualización de un BTree podría generar log_b N IOs, es decir, podría terminar escribiendo 3 o 4 bloques para cada clave. Si el tamaño de la clave es mucho menor que el tamaño del bloque, esto es extremadamente costoso. Para un índice similar a SSTable, cada IO de escritura contendrá tantas claves nuevas como sea posible, por lo que el costo de IO para cada clave es más parecido a 1 / B.
En la práctica, esto hace que SSTable parezca miles de veces más rápido (para escrituras aleatorias) que BTrees.
Al considerar los detalles de implementación, hemos encontrado que es mucho más fácil implementar índices similares a SSTable (casi) sin bloqueos, mientras que las estrategias de bloqueo para BTrees se han vuelto bastante complicadas.
También debe volver a considerar sus costos de lectura. Estás en lo cierto que un BTree es O (log_b N) IO aleatorio para lecturas de puntos aleatorias, pero un índice similar a SSTable es en realidad O (#stables.log_b N). Sin un esquema de fusión decente, #stables es proporcional a N. Existen varios trucos para eludir esto (usando Bloom Filters, por ejemplo), pero estos no ayudan con consultas de rango pequeño y aleatorio. Esto es lo que encontramos con Cassandra:
http://www.acunu.com/blogs/richard-low/cassandra-under-heavy-write-load-part-ii/
Esta es la razón por la cual Castle, nuestro motor de almacenamiento (GPL), se fusiona de forma ligeramente diferente, y puede lograr mucho mejor (O (log ^ 2 N)) rendimiento de consultas de rango con una ligera compensación en el rendimiento de escritura (O (log ^ 2 N / B)). En la práctica, encontramos que es más rápido que el índice SSTable de Cassandra para las escrituras también.
Si quieres saber más sobre esto, he dado una charla sobre cómo funciona:
Algunas cosas que también deberían mencionarse sobre cada enfoque:
B-trees
- Se supone que las operaciones de lectura / escritura son logarítmicas
O(logn). Sin embargo, una sola escritura en la base de datos puede generar múltiples escrituras en el sistema de almacenamiento . Por ejemplo, cuando un nodo está lleno, debe dividirse, lo que significa que habrá 2 escrituras para los 2 nuevos nodos y 1 escritura adicional para actualizar el nodo padre. Puede ver cómo podría aumentar si el nodo padre también estuviera lleno. - Por lo general, los árboles B se almacenan de tal manera que cada nodo tiene el tamaño de una página. Esto crea un fenómeno llamado amplificación de escritura , donde incluso si un byte único necesita actualizarse, se escribe una página completa.
- Las escrituras suelen ser aleatorias (no secuenciales), por lo tanto , más lentas especialmente para los discos magnéticos.
SSTables
- Los SSTables se usan generalmente en el siguiente enfoque. Hay una estructura en memoria, llamada memtable, como describió. De vez en cuando, esta estructura se vacía al disco a un SSTable. Como resultado, todas las escrituras van a la memtable, pero las lecturas pueden no estar en la memtable actual, en cuyo caso se buscan en los SSTables persistentes .
- Como resultado, las escrituras son
O(logn). Sin embargo, siempre tenga en cuenta que están hechos en memoria, por lo que deben ser órdenes de magnitud más rápidas que las operaciones logarítmicas en el disco de B-trees. En aras de la exhaustividad, debemos mencionar que las escrituras también se escriben en un registro de escritura anticipada para recuperación de fallos. Pero, dado que todas estas son escrituras secuenciales, se espera que sean mucho más eficientes que las escrituras aleatorias de B-trees . - Cuando se sirve desde la memoria (desde el memtable), se espera que las lecturas sean mucho más rápidas también . Pero, cuando hay que buscar en los SSTables basados en disco, más antiguos, las lecturas pueden volverse bastante más lentas que los B-trees. Hay varias optimizaciones en torno a eso, como el uso de filtros de bloom, para comprobar si un SSTable contiene un valor sin realizar lecturas de disco.
- Como mencionaste, también hay un proceso en segundo plano, llamado compactación , que se usa para combinar SSTables. Esto ayuda a eliminar los valores eliminados y evitar la fragmentación, pero puede causar una carga de escritura significativa, lo que afecta el rendimiento de escritura de las operaciones entrantes.
Como se hace evidente, una comparación entre estos 2 enfoques es mucho más complicada. En un intento extremadamente simplificado de proporcionar una comparación concreta, creo que podríamos decir que:
- Los SSTables proporcionan un rendimiento de escritura mucho mejor que los B-trees. Sin embargo, se espera que tengan un comportamiento menos estable, debido a las compactaciones en curso. Un ejemplo de esto se puede ver en esta comparación de referencia .
- B-trees son usualmente preferidos para casos de uso, donde la semántica de transacción es necesaria. Esto se debe a que cada clave se puede encontrar solo en un solo lugar (en contraste con SSTable, donde podría existir en múltiples SSTables con valores obsoletos en algunos de ellos) y también porque se podría representar un rango de valores como parte del árbol. Esto significa que es más fácil realizar mecanismos de bloqueo a nivel de clave y rango.
Referencias
LSM-Trees es mejor que B-Trees en el motor de almacenamiento estructurado. Convierte la escritura aleatoria a aof de una manera. Aquí hay un src de LSM-Tree: https://github.com/shuttler/lsmtree