En este artículo, veremos en detalle cómo se hace el árbol B + en una base de datos distribuida Apache Ignite .

Ya hay un par de artículos sobre árboles H en árboles B ( uno , dos ), pero es más probable que sean teóricos e incluso si contienen una implementación, entonces no están listos para la producción . A partir de esto, hay un interés en observar la implementación que se utiliza en la vida.

Antes de seguir leyendo el artículo, le aconsejo que vea una conferencia de Maxim Babenko , si aún no sabe qué es el árbol B en teoría. Pero no necesito conocer Java en profundidad ni el proyecto Apache Ignite: escribiré los detalles explícitamente u los ocultaré bajo spoilers.

Al leer las fuentes de Ignite, le aconsejo que omita los argumentos de los métodos en su mente, cuyo significado no es muy claro y que lea los nombres de las funciones; es mucho más fácil leer el cuerpo de la función si sabe de antemano lo que hace.

Tenga en cuenta que no soy el desarrollador principal de Apache Ignite y podría haber entendido mal algo del código. Entonces, saqué la frase "hasta donde yo entiendo", que debe agregarse mentalmente antes de cada oración afirmativa.

¿Por qué B + tree en Apache Ignite?

Apache Ignite es una base de datos en memoria, pero desde la versión 2.1 tiene un almacén de datos persistente , una función para guardar datos en el disco (no tiene nada que ver con la estructura de datos persistente ) . Por lo tanto, está claro por qué se necesita una estructura para la memoria externa, queda por entender por qué no eligieron otra.

Para empezar, el árbol B + es una optimización del árbol B, donde los valores se almacenan solo en hojas. En esta optimización, caben más claves en un nodo, lo que aumenta el grado de ramificación. Por lo tanto, no hay muchas razones para usar el árbol B clásico.

B * y B + *: son más densos en el disco, pero tienen peor rendimiento, porque almacenamos datos de RAM, el rendimiento es más importante para nosotros.

A juzgar por los puntos de referencia, un árbol LSM es más rápido en la escritura, pero más lento en la lectura. Además, la pérdida en la lectura es mayor que la ganancia en la escritura, por lo que para un caso general hipotético, también tomaría el árbol B +.

También hay árboles fractales extraños, sin embargo, aparentemente, están patentados e implementados solo en TokuDB .

Personalmente, estoy más interesado en por qué era imposible tomar un backend de disco ya preparado, como LevelDB . Una respuesta parcial es que PDS admite almacenamiento de terceros.

Implementación de células grandes

Inicialmente, GridGain desarrolló Apache Ignite, pero antes de partir a código abierto llevaba el nombre de la compañía, por lo que algunos nombres de componentes comienzan con Grid y otros con Ignite . Por GridCursor tanto, GridCursor , pero IgniteTree . No hay otra lógica aquí.

El código Apache Ignite está escrito en los patrones de mejores prácticas de Java, y cada clase hereda una interfaz, si no una. Desde la interfaz IgniteTree y comienza el baile. Doy el código sin javadoc, para abreviar.

 public interface IgniteTree<L, T> { public T put(T val) throws IgniteCheckedException; public void invoke(L key, Object x, InvokeClosure<T> c) throws IgniteCheckedException; public T findOne(L key) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper) throws IgniteCheckedException; public GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException; public T findFirst() throws IgniteCheckedException; public T findLast() throws IgniteCheckedException; public T remove(L key) throws IgniteCheckedException; public long size() throws IgniteCheckedException; interface InvokeClosure<T> { void call(@Nullable T row) throws IgniteCheckedException; T newRow(); OperationType operationType(); } enum OperationType { NOOP, REMOVE, PUT } } 

La interfaz IgniteTree describe un conjunto estándar de operaciones. Tenga en cuenta que para realizar una búsqueda por rango, debe tejer hojas en una lista. El bono admite una operación de registro arbitrario: invoke .

La operación put toma solo un argumento de tipo T sin una clave. No encontrará una explicación para esto en IgniteTree , sin embargo, la respuesta está oculta en el encabezado BPlusTree .

 public abstract class BPlusTree<L, T extends L> extends DataStructure implements IgniteTree<L, T> 

Como puede ver, el valor hereda la clave, por lo tanto, en la operación de venta, la clave se calcula a partir del valor. Esto no limita la funcionalidad del árbol. Supongo que es más compacto almacenar juegos.

Por lo general, se establecen fuera del mapa al adjuntar una constante de basura al valor. Sin embargo, en el árbol B +, solo las claves se almacenan en nodos; si el valor también almacena la clave, entonces en las hojas es suficiente almacenar solo los valores . Y si el árbol es un conjunto, automáticamente resulta que en las hojas solo habrá claves sin valores basura.

Ahora veamos el código de búsqueda del elemento.

 /** * @param g Get. * @throws IgniteCheckedException If failed. */ private void doFind(Get g) throws IgniteCheckedException { for (;;) { // Go down with retries. g.init(); switch (findDown(g, g.rootId, 0L, g.rootLvl)) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; default: return; } } } /** * @param g Get. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result findDown(final Get g, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { long page = acquirePage(pageId); try { for (;;) { // Init args. g.pageId = pageId; g.fwdId = fwdId; Result res = read(pageId, page, search, g, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert g.pageId != pageId; assert g.fwdId != fwdId || fwdId == 0; // Go down recursively. res = findDown(g, g.pageId, g.fwdId, lvl - 1); switch (res) { case RETRY: checkInterrupted(); continue; // The child page got split, need to reread our page. default: return res; } case NOT_FOUND: assert lvl == 0 : lvl; g.row = null; // Mark not found result. return res; default: return res; } } } finally { if (g.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

La base del algoritmo transversal del árbol B se ha mantenido sin cambios: descienden el árbol recursivamente a la hoja deseada: si el valor está presente, entonces devuelven el resultado, y si no, entonces null . La recursión aparentemente se dejó por conveniencia, de todos modos, los árboles B no son profundos.

Me sorprendió porque había una instalación clara en mi cabeza: la recursión siempre se elimina en un proyecto real ( no hay una optimización de recursión de cola en Java , la recursión es aceptable en proyectos en otros idiomas). Pero realmente, la altura del árbol B se mide en unidades, porque el tamaño del bloque de orden $$$2 ^ {10}$y la cantidad de datos del pedido $$$2 ^ {40}$y la altura será $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

Apache Ignite ama la concurrencia . Por lo tanto, el árbol admite modificaciones competitivas. En el momento de la operación, una página está bloqueada, pero otro hilo puede modificar el resto del árbol para que se requiera una segunda lectura. Y así el procedimiento puede llegar a la raíz.

Al principio, no entendí el significado de dicha funcionalidad, porque el disco es lento y un hilo procesará con calma todas las operaciones de E / S. Está claro que la búsqueda en el nodo cargado desde el disco cuesta un poco y durante este tiempo puede cargar el disco con otra operación, pero los intentos repetidos consumirán la ganancia. Sin embargo, me di cuenta de que en esta implementación los nodos no se enjuagaron inmediatamente en el disco después de la modificación, sino que se quedaron en la memoria por un tiempo, para luego aplicar muchas modificaciones a la vez. No se pierden datos gracias a Write Ahead Log. Encontrará más información al final del artículo.

Ahora veamos el código para agregar un elemento.

 private T doPut(T row, boolean needOld) throws IgniteCheckedException { checkDestroyed(); Put p = new Put(row, needOld); try { for (;;) { // Go down with retries. p.init(); Result res = putDown(p, p.rootId, 0L, p.rootLvl); switch (res) { case RETRY: case RETRY_ROOT: checkInterrupted(); continue; case FOUND: // We may need to insert split key into upper level here. if (!p.isFinished()) { // It must be impossible to have an insert higher than the current root, // because we are making decision about creating new root while keeping // write lock on current root, so it can't concurrently change. assert p.btmLvl <= getRootLevel(); checkInterrupted(); continue; } return p.oldRow; default: throw new IllegalStateException("Result: " + res); } } } catch (IgniteCheckedException e) { throw new IgniteCheckedException("Runtime failure on row: " + row, e); } catch (RuntimeException e) { throw new IgniteException("Runtime failure on row: " + row, e); } catch (AssertionError e) { throw new AssertionError("Assertion error on row: " + row, e); } finally { checkDestroyed(); } } /** * @param p Put. * @param pageId Page ID. * @param fwdId Expected forward page ID. * @param lvl Level. * @return Result code. * @throws IgniteCheckedException If failed. */ private Result putDown(final Put p, final long pageId, final long fwdId, final int lvl) throws IgniteCheckedException { assert lvl >= 0 : lvl; final long page = acquirePage(pageId); try { for (;;) { // Init args. p.pageId = pageId; p.fwdId = fwdId; Result res = read(pageId, page, search, p, lvl, RETRY); switch (res) { case GO_DOWN: case GO_DOWN_X: assert lvl > 0 : lvl; assert p.pageId != pageId; assert p.fwdId != fwdId || fwdId == 0; res = p.tryReplaceInner(pageId, page, fwdId, lvl); if (res != RETRY) // Go down recursively. res = putDown(p, p.pageId, p.fwdId, lvl - 1); if (res == RETRY_ROOT || p.isFinished()) return res; if (res == RETRY) checkInterrupted(); continue; // We have to insert split row to this level or it is a retry. case FOUND: // Do replace. assert lvl == 0 : "This replace can happen only at the bottom level."; return p.tryReplace(pageId, page, fwdId, lvl); case NOT_FOUND: // Do insert. assert lvl == p.btmLvl : "must insert at the bottom level"; assert p.needReplaceInner == FALSE : p.needReplaceInner + " " + lvl; return p.tryInsert(pageId, page, fwdId, lvl); default: return res; } } } finally { if (p.canRelease(pageId, lvl)) releasePage(pageId, page); } } 

La única diferencia es que después de detectar la posición, el código se replace e insert . Ya no puedes ver el código de remove . El mecanismo básico es que con intentos repetidos de caminar recursivamente a través del árbol junto con un objeto especial dependiendo de la operación: Get , Put o Remove .

Invoke funciona de la misma manera, solo la operación se realiza con una copia del registro, luego se determina su tipo: NOOP para leer, REMOVE para eliminar y PUT para actualizar o agregar, y luego se genera el objeto Put o Remove correspondiente, que se aplica al registro en el árbol.

Uso

A continuación, BPlusTree un vistazo más de cerca a dos BPlusTree CacheDataTree : CacheDataTree y PendingEntriesTree . Overboard es la implementación de índices: este es un tema para una discusión por separado, para la cual aún no estoy listo.

Antes de continuar, IgniteCache que el mapa distribuido local tiene una funcionalidad IgniteCache y se llama IgniteCache , en adelante simplemente un caché.

CacheDataTree

CacheDataTree es una asignación de múltiples IgniteCache al disco. La ordenación es multinivel: primero ordena por ID de caché para agrupar las claves en un caché, y luego por hash.

CacheDataTree no itera sobre el rango, ya que los índices se implementan en los herederos de H2Tree extends BPlusTree , por lo que el tipo específico de clasificación no es importante: cualquiera es suficiente para las operaciones de put y get . Comparar hashes es más rápido que los objetos. Pero lo más importante, un hash uniforme llenará el árbol más densamente.

Los árboles se equilibran para que no se degeneren en una lista. Pero si agrega claves distribuidas uniformemente al árbol de búsqueda, se equilibrará automáticamente. Dado que los árboles B comienzan a equilibrarse a medida que surgen problemas, y los hashes mezclan claves de manera uniforme, la clasificación por hash reduce la frecuencia del equilibrio.

Usar hashes en el árbol de búsqueda no es una idea tan extraña como parece, su desarrollo lógico conducirá a un trie mapeado de matriz Hash .

PendingEntriesTree

PendingEntriesTree almacena claves para datos a lo largo del tiempo y se utiliza como conjunto. La ordenación es multinivel: primero ordenada por ID de caché para agrupar claves en una caché, y luego por tiempo de vida. La siguiente es otra ronda de comparación, aparentemente, puramente técnica, para distinguir entre elementos. De la clasificación es fácil adivinar que esta clase se usa para buscar rangos. Este árbol duplica las claves de entrada de caché para la preferencia.

Comprende cómo funciona esta aventura separada.

 @Override public boolean expire( GridCacheContext cctx, IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> c, int amount ) 

 private final IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion> expireC = new IgniteInClosure2X<GridCacheEntryEx, GridCacheVersion>() { @Override public void applyx(GridCacheEntryEx entry, GridCacheVersion obsoleteVer) { boolean touch = !entry.isNear(); while (true) { try { if (log.isTraceEnabled()) log.trace("Trying to remove expired entry from cache: " + entry); if (entry.onTtlExpired(obsoleteVer)) touch = false; break; } catch (GridCacheEntryRemovedException ignore) { entry = entry.context().cache().entryEx(entry.key()); touch = true; } } if (touch) entry.context().evicts().touch(entry, null); } }; 

 cctx.cache().removeEntry(this); 

Detalles de implementación

Trabajar con páginas en Offheap

Offheap es una técnica para optimizar la gestión manual de la memoria en un idioma con un recolector de basura.

Es un mito que, debido al recolector de basura, todo se ralentiza, por lo general, los recolectores cuestan un porcentaje miserable de rendimiento . Incluso los montones grandes en sí mismos no son un problema, porque los recopiladores trabajan de manera competitiva (por ejemplo, CMS y G1 en Java), y los servidores tienen docenas de núcleos . Por supuesto, el recopilador agrega pausas impredecibles a la aplicación, lo cual es importante para los juegos, pero tolerable para la base de datos.

Pero lo que realmente será el problema es una violación de la hipótesis generacional en un gran montón.

Y aquí es tal cosa que antes del advenimiento de PDS, Apache Ignite se posicionó principalmente como un caché entre servicios y una base de datos de disco (por ejemplo, Hadoop ). Por lo tanto, los mapas en Ignite se llaman IgniteCache y tienen la funcionalidad de extrusión correspondiente. Y los cachés simplemente violan la hipótesis generacional: en ellos, la probabilidad de que un objeto se elimine aumenta con el tiempo. Por lo tanto, en este caso, Offheap para almacenar datos de usuario mejora el rendimiento.

Más bonificaciones:

• Offheap facilita la implementación de estructuras que contienen más de elementos Integer.MAX_VALUE .
• Si mantiene un montón de menos de 32 GB, los enlaces pesarán 4 bytes , lo que ahorra unos pocos gigabytes.
• Como el recopilador crea un gráfico de objetos, consume memoria en proporción a su número. Y el número de objetos es proporcional al montón. El recopilador también consume una CPU, que se gasta mejor para la compresión de datos, por ejemplo.
• En montones muy grandes, incluso si la hipótesis generacional no se viola en su conjunto, todavía habrá muchos objetos antiguos en valor absoluto que la violarán.

Como los datos se envían al disco, los objetos se serializan en la memoria directamente a través de unsafe , y luego esta área de memoria se utiliza para el búfer de E / S.

Escribir registro a continuación

Write Ahead Log es un registro de operaciones con una estructura lineal, que agrega costos constantes, a diferencia de un árbol. El árbol se actualiza con menos frecuencia, y si los datos se pierden debido a una caída, se restauran del registro mediante la aplicación de operaciones que comienzan desde el último estado guardado. El resultado es un rendimiento mejorado sin comprometer la fiabilidad. Le aconsejo que eche un vistazo a la interfaz IgniteWriteAheadLogManager : hay documentación detallada.

Bypass de nodo

Como los nodos en los árboles B no son pequeños, se omiten mediante la búsqueda binaria. Para esto, se BPlusTree.GetPageHandler descendientes de la clase BPlusTree.GetPageHandler , y para diferentes operaciones son diferentes.

 private int findInsertionPoint(int lvl, BPlusIO<L> io, long buf, int low, int cnt, L row, int shift) throws IgniteCheckedException { assert row != null; int high = cnt - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = compare(lvl, io, buf, mid, row); if (cmp == 0) cmp = -shift; // We need to fix the case when search row matches multiple data rows. //noinspection Duplicates if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // Found. } return -(low + 1); // Not found. } 

 if (cmp == 0) cmp = -shift; 

Lista de hojas

Para sortear el rango de manera eficiente, las hojas están vinculadas a una lista. BPlusTree.ForwardCursor , que va de hoja en hoja, se devuelve como un resultado de búsqueda. Aparentemente, el paso del cursor no está aislado de otras operaciones en el árbol, porque Al pasar, el bloqueo se toma solo en una página. No encontré un mecanismo de sincronización que proteja el acceso a los métodos del cursor.

Conclusión

Dado que el árbol B + en Apache Ignite es joven en comparación con otras bases de datos relacionales, obtenemos el conjunto necesario para el árbol B + listo para producción:

• WAL ofrece seguridad barata, como resultado, el árbol rara vez se actualiza en el disco.
• Offheap con datos en forma serializada.
• Concurrencia : para partes del árbol cargadas en la memoria.