Dans cet article, nous examinerons en détail comment l'arborescence B + est créée dans une base de données Apache Ignite distribuée.

Il y a déjà quelques articles sur les arbres H sur les arbres B ( un , deux ), mais ils sont plus probablement théoriques et même s'ils contiennent une implémentation, ils ne sont pas prêts pour la production . De cela, il y a un intérêt à regarder la mise en œuvre qui est utilisée dans la vie.

Avant de lire l'article plus loin, je vous conseille de regarder une conférence de Maxim Babenko , si vous ne savez toujours pas ce qu'est l'arbre B en théorie. Mais je n'ai pas besoin de connaître Java en profondeur ou le projet Apache Ignite - j'écrirai les détails explicitement ou le cacherai sous les spoilers.

Lors de la lecture des sources Ignite, je vous conseille de sauter les arguments des méthodes dans votre esprit, dont la signification n'est pas très claire et de lire les noms des fonctions - il est beaucoup plus facile de lire le corps de la fonction si vous savez à l'avance ce qu'elle fait.

Veuillez noter que je ne suis pas le développeur principal d'Apache Ignite et que j'ai peut-être mal compris quelque chose du code. J'ai donc mis la phrase «pour autant que je comprends», qui devrait être ajoutée mentalement avant chaque phrase affirmative.

Pourquoi l'arbre B + dans Apache Ignite

Apache Ignite est une base de données en mémoire, mais depuis la version 2.1, elle possède un magasin de données persistantes - une fonction pour enregistrer les données sur le disque (n'a rien à voir avec la structure des données persistantes ) . Par conséquent, il est clair pourquoi une structure est nécessaire pour la mémoire externe, il reste à comprendre pourquoi ils n'en ont pas choisi une autre.

Pour commencer, l'arbre B + est une optimisation de l'arbre B, où les valeurs sont stockées uniquement dans les feuilles. Dans cette optimisation, davantage de clés tiennent dans un nœud, ce qui augmente le degré de ramification. Par conséquent, il n'y a pas beaucoup de raisons d'utiliser l'arbre B classique.

B * et B + * - sont plus denses sur le disque, mais leurs performances sont moins bonnes, car nous stockons les données de la RAM, les performances sont plus importantes pour nous.

À en juger par les repères, un arbre LSM est plus rapide à écrire, mais plus lent à lire. De plus, la perte en lecture est supérieure au gain en écriture, donc pour un cas général hypothétique, je prendrais aussi l'arbre B +.

Il existe également d'étranges arbres fractals , cependant, apparemment, ils sont brevetés et mis en œuvre uniquement dans TokuDB .

Personnellement, je suis plus intéressé par la raison pour laquelle il était impossible de prendre un backend de disque prêt à l'emploi, comme LevelDB ? Une réponse partielle est que PDS prend en charge le stockage tiers.

Mise en œuvre de grandes cellules

Au départ, GridGain a développé Apache Ignite, mais avant de partir pour l'open source, il portait le nom de la société, donc certains noms de composants commencent par Grid et d'autres par Ignite . Par conséquent GridCursor , mais IgniteTree . Il n'y a pas d'autre logique ici.

Le code Apache Ignite est écrit dans les modèles de meilleures pratiques Java, et chaque classe hérite d'une interface, sinon une. Depuis l'interface IgniteTree et lancez la danse. Je donne le code sans javadoc, pour faire court.

 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 } } 

L'interface IgniteTree décrit un ensemble standard d'opérations. Veuillez noter qu'avoir une recherche de gamme vous oblige à tricoter des feuilles dans une liste. Le bonus prend en charge une opération d'enregistrement arbitraire - invoke .

L'opération put ne prend qu'un seul argument de type T sans clé. Vous ne trouverez pas d'explication à cela dans IgniteTree , mais la réponse est masquée dans l'en-tête BPlusTree .

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

Comme vous pouvez le voir, la valeur hérite de la clé, par conséquent, dans l'opération put, la clé est calculée à partir de la valeur. Cela ne limite pas la fonctionnalité de l'arborescence. Mon hypothèse est qu'il est plus compact de stocker des ensembles.

Habituellement, ils font un ensemble de carte en attachant une constante de mémoire à la valeur. Cependant, dans l'arborescence B +, seules les clés sont stockées dans les nœuds; si la valeur stocke également la clé, dans les feuilles, il suffit de stocker uniquement les valeurs . Et si l'arbre est un ensemble, il se trouve automatiquement que dans les feuilles, il n'y aura que des clés sans valeurs de déchets.

Examinons maintenant le code de recherche d'élément.

 /** * @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 de l'algorithme de traversée de l'arbre B est restée inchangée: ils descendent l'arbre récursivement jusqu'à la feuille souhaitée: si la valeur est présente, alors ils retournent le résultat, et sinon, alors null . La récursivité a apparemment été laissée pour plus de commodité, de toute façon, les arbres B ne sont pas profonds.

J'ai été surpris car il y avait une installation claire dans ma tête: la récursivité est toujours supprimée dans un projet réel ( il n'y a pas d'optimisation de récursivité de queue en Java , la récursivité est acceptable dans les projets dans d'autres langages). Mais vraiment, la hauteur de l'arbre B est mesurée en unités, car la taille du bloc de commande $$$2 ^ {10}$, et le nombre de données de la commande $$$2 ^ {40}$et la hauteur sera $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

Apache Ignite aime la simultanéité . Par conséquent, l'arborescence prend en charge la modification compétitive. Au moment de l'opération, une page est bloquée, mais un autre thread peut modifier le reste de l'arborescence afin qu'une deuxième lecture soit nécessaire. Et donc la procédure peut atteindre la racine.

Au début, je ne comprenais pas la signification d'une telle fonctionnalité, car le disque est lent et un thread traitera calmement toutes les opérations d'E / S. Il est clair que la recherche dans le nœud chargé à partir du disque coûte un peu et pendant ce temps, vous pouvez charger le disque avec une autre opération, mais des tentatives répétées grugeront le gain. Cependant, il m'est apparu que dans cette implémentation, les nœuds n'étaient pas immédiatement vidés sur le disque après la modification, mais ils étaient suspendus dans la mémoire pendant un certain temps, afin d'appliquer ensuite de nombreuses modifications à la fois. Aucune donnée n'est perdue grâce à Write Ahead Log. Plus d'informations à ce sujet à la fin de l'article.

Voyons maintenant le code pour ajouter un élément.

 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 seule différence est qu'après la détection de la position, le code se transforme en replace et insert . Vous ne pouvez plus regarder le code de remove . Le mécanisme de base est celui des tentatives répétées de parcourir récursivement l'arborescence avec un objet spécial en fonction de l'opération: Get , Put ou Remove .

Invoke fonctionne de la même manière, seule l'opération a lieu avec une copie de l'enregistrement, puis son type est déterminé: NOOP pour la lecture, REMOVE pour la suppression et PUT pour la mise à jour ou l'ajout, puis l'objet Put ou Remove correspondant est généré, qui est appliqué à l'enregistrement dans l'arborescence.

Utiliser

Ci-dessous, j'examinerai de plus près deux BPlusTree CacheDataTree : CacheDataTree et PendingEntriesTree . Overboard est la mise en œuvre d'index - c'est un sujet pour une discussion séparée, pour lequel je ne suis pas encore prêt.

Avant de poursuivre, je précise que la carte distribuée locale a une fonctionnalité IgniteCache et s'appelle IgniteCache - ci-après simplement un cache.

CacheDataTree

CacheDataTree est un mappage de plusieurs IgniteCache sur le disque. Le tri est à plusieurs niveaux: triez d'abord par identifiant de cache pour regrouper les clés dans un cache, puis par hachage.

CacheDataTree pas sur la plage, car les index sont implémentés dans les héritiers de H2Tree extends BPlusTree , donc le type spécifique de tri n'est pas important: tout est suffisant pour les opérations put et get . La comparaison des hachages est plus rapide que les objets. Mais plus important encore, un hachage uniforme remplira l'arbre plus densément.

Les arbres s'équilibrent pour ne pas dégénérer en liste. Mais si vous ajoutez des clés uniformément réparties à l'arborescence de recherche, elle sera automatiquement équilibrée. Étant donné que les arbres B commencent à s'équilibrer lorsque des problèmes surviennent et que les hachages mélangent les clés de manière égale, le tri par hachage réduit la fréquence de l'équilibrage.

L'utilisation de hachages dans l'arbre de recherche n'est pas une idée aussi étrange qu'il y paraît, son développement logique conduira à un tri mappé de tableau Hash .

PendingEntriesTree

PendingEntriesTree stocke les clés des données au fil du temps et est utilisé comme défini. Le tri est à plusieurs niveaux: d'abord trié par identifiant de cache pour regrouper les clés dans un cache, puis par durée de vie. Vient ensuite un autre tour de comparaison - apparemment purement technique, pour distinguer les éléments. À partir du tri, il est facile de deviner que cette classe est utilisée pour rechercher des plages. Cette arborescence duplique les clés d'entrée du cache pour la préemption.

Comprenez comment fonctionne cette aventure séparée.

 @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); 

Détails d'implémentation

Travailler avec des pages dans Offheap

Offheap est une technique pour optimiser la gestion manuelle de la mémoire dans une langue avec un garbage collector.

C'est un mythe qu'en raison du ramasse-miettes tout ralentit, les collecteurs coûtent généralement un pourcentage misérable de performances . Même les gros tas en eux-mêmes ne sont pas un problème, car les collecteurs fonctionnent de manière compétitive (par exemple, CMS et G1 en Java), et les serveurs ont des dizaines de cœurs . Bien sûr, le collecteur ajoute des pauses imprévisibles à l'application, ce qui est important pour les jeux, mais tolérable pour la base de données.

Mais ce qui sera vraiment le problème, c'est une violation de l'hypothèse générationnelle sur un grand tas.

Et ici, c'est une chose telle qu'avant l'avènement de PDS, Apache Ignite était positionné principalement comme un cache entre les services et une base de données de disques (par exemple, Hadoop ). Par conséquent, les cartes dans Ignite sont appelées IgniteCache et ont la fonctionnalité d'extrusion correspondante. Et les caches violent simplement l'hypothèse générationnelle - en eux, la probabilité qu'un objet soit supprimé augmente avec le temps. Par conséquent, dans ce cas, Offheap pour le stockage des données utilisateur améliore les performances.

Plus de bonus:

• Offheap facilite l'implémentation de structures contenant plus de éléments Integer.MAX_VALUE .
• Si vous conservez un groupe de moins de 32 Go, les liens pèseront 4 octets , ce qui économise quelques gigaoctets.
• Puisque le collecteur construit un graphe d'objets, il consomme de la mémoire proportionnellement à leur nombre. Et le nombre d'objets est proportionnel au tas. Le collecteur consomme également un processeur, qui est mieux dépensé pour la compression de données, par exemple.
• Sur de très grands tas, même si l'hypothèse générationnelle n'est pas violée dans son ensemble, il y aura encore pas mal d'objets anciens en valeur absolue qui la violeront.

Étant donné que les données sont ensuite envoyées sur le disque, les objets sont sérialisés en mémoire directement via unsafe , puis cette zone de mémoire est utilisée pour le tampon d'E / S.

Écrire le journal à l'avance

Write Ahead Log est un journal des opérations avec une structure linéaire, ce qui lui coûte une constante, contrairement à un arbre. L'arborescence est mise à jour moins fréquemment et si des données sont perdues en raison d'une chute, elles sont restaurées à partir du journal en appliquant des opérations à partir du dernier état enregistré. Le résultat est une amélioration des performances sans compromettre la fiabilité. Je vous conseille de jeter un œil à l'interface IgniteWriteAheadLogManager - il y a une documentation détaillée.

Contournement de noeud

Comme les nœuds dans les arbres B ne sont pas petits, ils sont contournés par la recherche binaire. Pour cela, les descendants de la classe BPlusTree.GetPageHandler sont BPlusTree.GetPageHandler , et pour différentes opérations ils sont différents.

 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; 

Liste des fiches

Pour contourner efficacement la gamme, les feuilles sont liées à une liste. BPlusTree.ForwardCursor , qui va de feuille en feuille, est renvoyé comme résultat de recherche. Apparemment, le passage du curseur n'est pas isolé des autres opérations de l'arborescence, car lors du passage, le verrou n'est pris que sur une seule page. Je n'ai pas trouvé de mécanisme de synchronisation qui protège l'accès aux méthodes de curseur.

Conclusion

Étant donné que l'arborescence B + dans Apache Ignite est jeune par rapport à d'autres bases de données relationnelles, nous obtenons l'ensemble nécessaire pour une arborescence B + prête pour la production:

• WAL offre une sécurité bon marché, en conséquence, l'arborescence se met rarement à jour sur le disque.
• Offheap avec des données sous forme sérialisée.
• Concurrence - pour des parties de l'arborescence chargées en mémoire.