In diesem Artikel werden wir uns detailliert ansehen, wie der B + -Baum in einer verteilten Apache Ignite- Datenbank erstellt wird.

Es gibt bereits einige Artikel über H-Bäume auf B-Bäumen ( eins , zwei ), aber sie sind eher theoretisch und selbst wenn sie eine Implementierung enthalten, sind sie nicht produktionsbereit . Daraus ergibt sich ein Interesse an der Implementierung, die im Leben verwendet wird.

Bevor Sie den Artikel weiter lesen, empfehle ich Ihnen, sich einen Vortrag von Maxim Babenko anzuschauen, wenn Sie immer noch nicht wissen, was der B-Baum theoretisch ist. Aber ich muss Java oder das Apache Ignite-Projekt nicht genau kennen - ich werde entweder die Details explizit schreiben oder sie unter Spoilern verstecken.

Beim Lesen von Ignite-Quellen empfehle ich Ihnen, die Argumente von Methoden in Ihrem Kopf zu überspringen, deren Bedeutung nicht sehr klar ist, und die Namen von Funktionen zu lesen. Es ist viel einfacher, den Funktionskörper zu lesen, wenn Sie im Voraus wissen, was er tut.

Bitte beachten Sie, dass ich nicht der Hauptentwickler von Apache Ignite bin und möglicherweise etwas aus dem Code missverstanden habe. Also habe ich den Satz "soweit ich verstehe" ausgesprochen, der vor jedem positiven Satz mental hinzugefügt werden sollte.

Warum B + Baum in Apache Ignite

Apache Ignite ist eine speicherinterne Datenbank, verfügt jedoch seit Version 2.1 über einen persistenten Datenspeicher - eine Funktion zum Speichern von Daten auf der Festplatte (hat nichts mit der persistenten Datenstruktur zu tun) . Daher ist klar, warum eine Struktur für den externen Speicher benötigt wird. Es bleibt zu verstehen, warum sie keine andere gewählt haben.

Der B + -Baum ist zunächst eine Optimierung des B-Baums, bei dem Werte nur in Blättern gespeichert werden. Bei dieser Optimierung passen mehr Schlüssel in einen Knoten, wodurch der Verzweigungsgrad erhöht wird. Daher gibt es nicht viel Grund, den klassischen B-Baum zu verwenden.

B * und B + * - sind auf der Festplatte dichter, haben aber eine schlechtere Leistung, weil Wir speichern Daten aus dem RAM, Leistung ist uns wichtiger.

Nach Benchmarks zu urteilen , ist ein LSM-Baum beim Schreiben schneller, beim Lesen jedoch langsamer. Darüber hinaus ist der Leseverlust größer als der Schreibverlust, sodass ich für einen hypothetischen allgemeinen Fall auch den B + -Baum nehmen würde.

Es gibt auch seltsame fraktale Bäume , die jedoch anscheinend nur in TokuDB patentiert und implementiert sind .

Persönlich interessiert mich mehr, warum es unmöglich war, ein fertiges Festplatten-Backend wie LevelDB zu verwenden ? Eine teilweise Antwort ist, dass PDS Speicher von Drittanbietern unterstützt.

Implementierung großer Zellen

Ursprünglich entwickelte GridGain Apache Ignite, aber bevor es zu Open Source ging, trug es den Namen des Unternehmens, sodass einige Komponentennamen mit Grid und andere mit Ignite . Daher GridCursor , aber IgniteTree . Hier gibt es keine andere Logik.

Apache Ignite-Code wird in den Java-Best-Practice-Mustern geschrieben, und jede Klasse erbt eine Schnittstelle, wenn nicht eine. Über die IgniteTree Oberfläche starten Sie den Tanz. Ich gebe den Code ohne Javadoc, kurz.

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

Die IgniteTree Schnittstelle beschreibt einen Standardsatz von Operationen. Bitte beachten Sie, dass Sie für eine Bereichssuche Blätter in einer Liste stricken müssen. Der Bonus unterstützt eine beliebige Aufzeichnungsoperation - invoke .

Die put Operation akzeptiert nur ein Argument vom Typ T ohne Schlüssel. In IgniteTree finden Sie keine Erklärung dafür. Die Antwort ist jedoch im BPlusTree Header versteckt.

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

Wie Sie sehen können, erbt der Wert den Schlüssel. Daher wird bei der Put-Operation der Schlüssel aus dem Wert berechnet. Dies schränkt die Funktionalität des Baums nicht ein. Ich gehe davon aus, dass das Speichern von Sets kompakter ist.

Normalerweise setzen sie die Karte außer Kraft, indem sie dem Wert eine Garbage-Konstante hinzufügen. Im B + -Baum werden jedoch nur Schlüssel in Knoten gespeichert. Wenn der Wert auch den Schlüssel speichert, reicht es in den Blättern aus, nur die Werte zu speichern. Und wenn der Baum eine Menge ist, stellt sich automatisch heraus, dass es in den Blättern nur Schlüssel ohne Müllwerte gibt.

Schauen wir uns nun den Elementsuchcode an.

 /** * @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); } } 

Die Basis des B-Tree-Traversal-Algorithmus ist unverändert geblieben: Sie senken den Baum rekursiv zum gewünschten Blatt ab. Wenn der Wert vorhanden ist, geben sie das Ergebnis zurück, und wenn nicht, dann null . Die Rekursion wurde anscheinend der Einfachheit halber verlassen, die B-Bäume sind nicht tief.

Ich war überrascht, weil ich eine klare Installation in meinem Kopf hatte: Die Rekursion wird in einem realen Projekt immer entfernt ( in Java gibt es keine Optimierung der Schwanzrekursion , die Rekursion ist in Projekten in anderen Sprachen akzeptabel). Aber tatsächlich wird die Höhe des B-Baums in Einheiten gemessen, weil die Größe des Ordnungsblocks $$$2 ^ {10}$und die Anzahl der Bestelldaten $$$2 ^ {40}$und die Höhe wird sein $$$\ frac {log (2 ^ {40})} {log (2 ^ {10})} = 4$.

Apache Ignite liebt Parallelität . Daher unterstützt der Baum wettbewerbsfähige Änderungen. Zum Zeitpunkt des Vorgangs ist eine Seite blockiert, aber ein anderer Thread kann den Rest des Baums so ändern, dass ein zweiter Lesevorgang erforderlich ist. Und so kann die Prozedur die Wurzel erreichen.

Zuerst habe ich die Bedeutung solcher Funktionen nicht verstanden, da die Festplatte langsam ist und ein Thread alle E / A-Vorgänge ruhig verarbeitet. Es ist klar, dass die Suche in dem von der Festplatte geladenen Knoten ein wenig kostet und Sie während dieser Zeit die Festplatte mit einer anderen Operation laden können, aber wiederholte Versuche verschlingen den Gewinn. Dann wurde mir jedoch klar, dass in dieser Implementierung die Knoten nach der Änderung nicht sofort auf die Festplatte geleert wurden, sondern eine Weile im Speicher hingen, um dann viele Änderungen gleichzeitig anzuwenden. Dank Write Ahead Log gehen keine Daten verloren. Mehr dazu am Ende des Artikels.

Sehen wir uns nun den Code zum Hinzufügen eines Elements an.

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

Der einzige Unterschied besteht darin, dass der Code nach dem Erkennen der Position replace und insert . Der remove kann nicht mehr überwacht werden. Der grundlegende Mechanismus besteht darin, dass bei wiederholten Versuchen, je nach Vorgang rekursiv durch den Baum zu gehen, zusammen mit einem speziellen Objekt: Get , Put oder Remove .

Invoke funktioniert auf die gleiche Weise, nur der Vorgang findet mit einer Kopie des Datensatzes statt, dann wird sein Typ bestimmt: NOOP zum Lesen, REMOVE zum Löschen und PUT zum Aktualisieren oder Hinzufügen, und dann wird das entsprechende Put oder Remove Objekt generiert, das auf den Datensatz im Baum angewendet wird.

Verwenden Sie

Im Folgenden werde ich zwei BPlusTree näher betrachten: CacheDataTree und PendingEntriesTree . Über Bord ist die Implementierung von Indizes - dies ist ein Thema für eine separate Diskussion, für die ich noch nicht bereit bin.

Bevor ich IgniteCache , werde ich klarstellen, dass die lokal verteilte Karte IgniteCache Funktionen hat und IgniteCache heißt - im Folgenden einfach ein Cache.

CacheDataTree

CacheDataTree ist eine Zuordnung mehrerer IgniteCache zur Festplatte. Die Sortierung erfolgt auf mehreren Ebenen: Zuerst nach Cache-ID sortieren, um Schlüssel in einem Cache zu gruppieren, und dann nach Hashes.

CacheDataTree iteriert nicht über den Bereich, da Indizes in den Nachfolgern von H2Tree extends BPlusTree und H2Tree extends BPlusTree . Daher ist die spezifische Art der Sortierung nicht wichtig: Für put und get Operationen ist keine ausreichend. Das Vergleichen von Hashes ist schneller als bei Objekten. Noch wichtiger ist jedoch, dass ein einheitlicher Hash den Baum dichter füllt.

Bäume balancieren so, dass sie nicht zu einer Liste ausarten. Wenn Sie dem Suchbaum jedoch gleichmäßig verteilte Schlüssel hinzufügen, wird dieser automatisch ausgeglichen. Da B-Bäume bei auftretenden Problemen mit dem Balancieren beginnen und Hashes die Schlüssel gleichmäßig mischen, verringert das Sortieren nach Hashes die Häufigkeit des Balancierens.

Die Verwendung von Hashes im Suchbaum ist keine so seltsame Idee, wie es scheint. Ihre logische Entwicklung wird zu einem Hash-Array-Mapping-Versuch führen .

PendingEntriesTree

PendingEntriesTree speichert Schlüssel für Daten im Laufe der Zeit und wird wie festgelegt verwendet. Die Sortierung erfolgt auf mehreren Ebenen: Zuerst nach Cache-ID sortiert, um Schlüssel in einem Cache zu gruppieren, und dann nach Lebensdauer. Als nächstes folgt eine weitere Vergleichsrunde - anscheinend rein technisch, um zwischen Elementen zu unterscheiden. Aus der Sortierung lässt sich leicht ableiten, dass diese Klasse zur Suche nach Bereichen verwendet wird. Dieser Baum dupliziert die Cache-Eintragsschlüssel für die Vorauszahlung.

Verstehe, wie dieses separate Abenteuer funktioniert.

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

Implementierungsdetails

Arbeiten Sie mit Seiten in Offheap

Offheap ist eine Technik zur Optimierung der manuellen Speicherverwaltung in einer Sprache mit einem Garbage Collector.

Es ist ein Mythos, dass aufgrund des Müllsammlers alles langsamer wird und Sammler normalerweise einen miserablen Prozentsatz der Leistung kosten. Auch große Haufen an sich sind kein Problem, denn Sammler arbeiten wettbewerbsfähig (z. B. CMS und G1 in Java), und Server verfügen über Dutzende von Kernen . Natürlich fügt der Collector der Anwendung unvorhersehbare Pausen hinzu, was für Spiele wichtig, für die Datenbank jedoch tolerierbar ist.

Aber was wirklich das Problem sein wird, ist eine Verletzung der Generationshypothese auf einem großen Haufen.

Und hier ist es so, dass Apache Ignite vor dem Aufkommen von PDS hauptsächlich als Cache zwischen Diensten und einer Festplattendatenbank (zum Beispiel Hadoop ) positioniert wurde. Daher heißen die Maps in Ignite IgniteCache und verfügen über die entsprechende Extrusionsfunktionalität. Und Caches verletzen nur die Generationshypothese - in ihnen steigt die Wahrscheinlichkeit, dass ein Objekt gelöscht wird, mit der Zeit. In diesem Fall verbessert Offheap zum Speichern von Benutzerdaten daher die Leistung.

Weitere Boni:

• Offheap erleichtert die Implementierung von Strukturen, die mehr als Integer.MAX_VALUE Elemente enthalten.
• Wenn Sie weniger als 32 GB behalten, wiegen die Links 4 Byte , was einige Gigabyte spart.
• Da der Kollektor ein Diagramm von Objekten erstellt, verbraucht er proportional zu ihrer Anzahl Speicher. Und die Anzahl der Objekte ist proportional zum Heap. Der Kollektor verbraucht auch eine CPU, die beispielsweise besser für die Datenkomprimierung verwendet wird.
• Selbst wenn die Generationshypothese nicht als Ganzes verletzt wird, gibt es auf sehr großen Haufen immer noch ziemlich viele alte Objekte im absoluten Wert, die sie verletzen.

Da die Daten dann auf die Festplatte gesendet werden, werden die Objekte direkt durch unsafe Daten in den Speicher serialisiert, und dieser Speicherbereich wird dann für den E / A-Puffer verwendet.

Schreiben Sie ein Protokoll voraus

Write Ahead Log ist ein Protokoll von Operationen mit einer linearen Struktur, dessen Hinzufügen im Gegensatz zu einem Baum eine Konstante kostet. Der Baum wird seltener aktualisiert. Wenn Daten aufgrund eines Sturzes verloren gehen, werden sie aus dem Protokoll wiederhergestellt, indem Vorgänge angewendet werden, die mit dem zuletzt gespeicherten Status beginnen. Das Ergebnis ist eine verbesserte Leistung, ohne die Zuverlässigkeit zu beeinträchtigen. Ich empfehle Ihnen, einen Blick auf die IgniteWriteAheadLogManager Oberfläche zu IgniteWriteAheadLogManager - es gibt eine detaillierte Dokumentation.

Knotenumgehung

Da die Knoten in den B-Bäumen nicht klein sind, werden sie durch binäre Suche umgangen. Hierzu werden Nachkommen der BPlusTree.GetPageHandler Klasse BPlusTree.GetPageHandler , und für verschiedene Operationen sind sie unterschiedlich.

 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 der Blätter

Um den Bereich effizient zu umgehen, werden Blätter an eine Liste gebunden. BPlusTree.ForwardCursor , der von Blatt zu Blatt wechselt, wird als Suchergebnis zurückgegeben. Anscheinend ist die Cursorpassage nicht von anderen Operationen im Baum isoliert, weil Beim Übergeben wird die Sperre nur auf einer Seite aufgehoben. Ich habe keinen Synchronisationsmechanismus gefunden, der den Zugriff auf Cursormethoden schützt.

Fazit

Da der B + -Baum in Apache Ignite im Vergleich zu anderen relationalen Datenbanken noch jung ist, erhalten wir den erforderlichen Satz für den produktionsbereiten B + -Baum:

• WAL bietet billige Sicherheit, daher wird der Baum selten auf der Festplatte aktualisiert.
• Offheap mit Daten in serialisierter Form.
• Parallelität - für Teile des Baums, die in den Speicher geladen werden.