Im Herbst 2019 fand im Mail.ru Cloud iOS-Team eine lang erwartete Veranstaltung statt. Die Hauptdatenbank zur dauerhaften Speicherung des Anwendungsstatus ist für die mobile Welt ziemlich exotisch geworden Lightning Memory-Mapped-Datenbank (LMDB). Unter dem Schnitt wird Ihre Aufmerksamkeit auf die ausführliche Rezension in vier Teilen gelenkt. Lassen Sie uns zunächst über die Gründe für eine so nicht triviale und schwierige Wahl sprechen. Kommen wir dann zur Betrachtung der drei Wale im Herzen der LMDB-Architektur: speicherzugeordnete Dateien, B+-Baum, Copy-on-Write-Ansatz zur Implementierung von Transaktions- und Multiversionierung. Zum Schluss noch der praktische Teil zum Nachtisch. Darin werden wir uns ansehen, wie man ein Basisschema mit mehreren Tabellen, einschließlich einer Indextabelle, zusätzlich zur Low-Level-Schlüsselwert-API entwirft und implementiert.​

Inhalt

1. Umsetzungsmotivation
2. LMDB positionieren
3. Drei Wale LMDB
   3.1 Wal Nr. 1. Speicherzugeordnete Dateien
   3.2 Wal Nr. 2. B+-Baum
   3.3 Wal #3. Copy-on-Write
4. Entwerfen eines Datenschemas auf Basis der Schlüsselwert-API
   4.1 Grundlegende Abstraktionen
   4.2 Tabellenmodellierung
   4.3 Modellierung von Beziehungen zwischen Tabellen

1. Umsetzungsmotivation

Einmal im Jahr, im Jahr 2015, haben wir uns darum gekümmert, eine Metrik zu erstellen, wie oft die Schnittstelle unserer Anwendung verzögert. Wir haben das nicht einfach so gemacht. Wir beschweren uns immer häufiger darüber, dass die Anwendung manchmal nicht mehr auf Benutzeraktionen reagiert: Schaltflächen werden nicht gedrückt, Listen scrollen nicht usw. Über die Mechanik der Messungen ich sagte auf AvitoTech, daher gebe ich hier nur die Reihenfolge der Zahlen an.

Die Messergebnisse wurden für uns zu einer kalten Dusche. Es stellte sich heraus, dass die durch Einfrierungen verursachten Probleme viel größer sind als alle anderen. Wenn vor der Erkenntnis dieser Tatsache der wichtigste technische Indikator für die Qualität absturzfrei war, dann nach dem Fokus verschoben auf frostfrei.

Gebaut haben Dashboard mit Einfrierungen und ausgegeben zu haben quantitativ и Qualität Bei der Analyse ihrer Ursachen wurde der Hauptfeind klar: schwere Geschäftslogik, die im Hauptthread der Anwendung ausgeführt wird. Eine natürliche Reaktion auf diese Schande war der brennende Wunsch, sie in die Arbeitsabläufe zu integrieren. Für eine systematische Lösung dieses Problems haben wir auf eine Multithread-Architektur basierend auf leichtgewichtigen Akteuren zurückgegriffen. Ich habe ihr Adaptionen für die iOS-Welt gewidmet zwei Threads im kollektiven Twitter und Artikel über Habré. Im Rahmen der aktuellen Geschichte möchte ich diejenigen Aspekte der Entscheidung hervorheben, die die Wahl der Datenbank beeinflusst haben.​

Das Akteurmodell der Systemorganisation geht davon aus, dass Multithreading sein zweites Wesen ist. Modellobjekte darin überschreiten gerne Thread-Grenzen. Und das tun sie nicht manchmal und an manchen Orten, sondern fast ständig und überall.

​Die Datenbank ist eine der Eckpfeilerkomponenten im dargestellten Diagramm. Seine Hauptaufgabe besteht darin, ein Makromuster zu implementieren Gemeinsame Datenbank. Wenn es in der Unternehmenswelt zum Organisieren der Datensynchronisierung zwischen Diensten verwendet wird, dann im Fall einer Akteurarchitektur für Daten zwischen Threads. Daher brauchten wir eine solche Datenbank, deren Arbeit in einer Multithread-Umgebung nicht einmal minimale Schwierigkeiten bereitet. Das bedeutet insbesondere, dass die daraus abgeleiteten Objekte mindestens threadsicher und im Idealfall überhaupt nicht veränderbar sein müssen. Wie Sie wissen, kann Letzteres gleichzeitig von mehreren Threads aus genutzt werden, ohne dass auf Sperren jeglicher Art zurückgegriffen werden muss, was sich positiv auf die Leistung auswirkt.

Der zweite wichtige Faktor, der die Wahl der Datenbank beeinflusste, war unsere Cloud-API. Es wurde vom Git-Ansatz zur Synchronisierung inspiriert. So wie er, auf den wir zielten Offline erste API, was für Cloud-Clients mehr als angemessen erscheint. Es wurde davon ausgegangen, dass sie nur einmal den vollständigen Zustand der Cloud herauspumpen würden und die Synchronisierung dann in den allermeisten Fällen durch fortlaufende Änderungen erfolgen würde. Leider befindet sich diese Möglichkeit noch im theoretischen Bereich, und in der Praxis haben die Kunden noch nicht gelernt, wie man mit Patches arbeitet. Dafür gibt es eine Reihe objektiver Gründe, die wir, um die Einführung nicht zu verzögern, in der Klammer weglassen. Viel interessanter sind nun die aufschlussreichen Ergebnisse der Lektion darüber, was passiert, wenn die API „A“ sagt und ihr Konsument nicht „B“ sagt.

Wenn Sie sich also Git vorstellen, das beim Ausführen eines Pull-Befehls, anstatt Patches auf einen lokalen Snapshot anzuwenden, seinen vollständigen Status mit dem vollständigen Status des Servers vergleicht, dann haben Sie eine ziemlich genaue Vorstellung davon, wie die Synchronisierung erfolgt tritt bei Cloud-Clients auf. Es ist leicht zu erraten, dass es für seine Implementierung notwendig ist, zwei DOM-Bäume im Speicher mit Metainformationen über alle Server- und lokalen Dateien zuzuweisen. Es stellt sich heraus, dass, wenn ein Benutzer 500 Dateien in der Cloud speichert, zur Synchronisierung zwei Bäume mit 1 Million Knoten neu erstellt und zerstört werden müssen. Aber jeder Knoten ist ein Aggregat, das einen Graphen von Unterobjekten enthält. Vor diesem Hintergrund waren die Profilierungsergebnisse zu erwarten. Es stellte sich heraus, dass selbst ohne Berücksichtigung des Zusammenführungsalgorithmus der Vorgang des Erstellens und anschließenden Zerstörens einer großen Anzahl kleiner Objekte einen hübschen Cent kostet. Die Situation wird durch die Tatsache verschärft, dass die grundlegende Synchronisierungsoperation in einer großen Anzahl enthalten ist von Benutzerskripten. Damit legen wir das zweite wichtige Kriterium bei der Auswahl einer Datenbank fest – die Fähigkeit, CRUD-Operationen ohne dynamische Zuweisung von Objekten zu implementieren.

Andere Anforderungen sind traditioneller und ihre vollständige Liste ist wie folgt.

1. Thread-Sicherheit.
2. Mehrfachverarbeitung. Dies wird durch den Wunsch bestimmt, dieselbe Datenbankinstanz zu verwenden, um den Status nicht nur zwischen Threads, sondern auch zwischen der Hauptanwendung und iOS-Erweiterungen zu synchronisieren.
3. Die Fähigkeit, gespeicherte Entitäten als nicht veränderliche Objekte darzustellen.​
4. Mangel an dynamischen Zuweisungen innerhalb von CRUD-Operationen.
5. Transaktionsunterstützung für Basiseigenschaften ACIDSchlüsselwörter: Atomizität, Konsistenz, Isolation und Zuverlässigkeit.
6. Geschwindigkeit bei den beliebtesten Fällen.

Angesichts dieser Anforderungen war und ist SQLite eine gute Wahl. Allerdings bin ich im Zuge der Auseinandersetzung mit Alternativen auf ein Buch gestoßen „Erste Schritte mit LevelDB“. Unter ihrer Leitung wurde ein Benchmark geschrieben, der die Arbeitsgeschwindigkeit mit verschiedenen Datenbanken in realen Cloud-Szenarien vergleicht. Das Ergebnis übertraf die kühnsten Erwartungen. In den gängigsten Fällen – dem Setzen eines Cursors auf eine sortierte Liste aller Dateien und einer sortierten Liste aller Dateien für ein bestimmtes Verzeichnis – erwies sich LMDB als zehnmal schneller als SQLite. Die Wahl lag auf der Hand.

2. LMDB-Positionierung

LMDB ist eine sehr kleine Bibliothek (nur 10 Zeilen), die die unterste grundlegende Datenbankschicht implementiert – den Speicher.

Das obige Diagramm zeigt, dass der Vergleich von LMDB mit SQLite, das noch höhere Ebenen implementiert, im Allgemeinen nicht korrekter ist als der Vergleich von SQLite mit Core Data. Es wäre fairer, dieselben Speicher-Engines als gleichwertige Konkurrenten zu bezeichnen – BerkeleyDB, LevelDB, Sophia, RocksDB usw. Es gibt sogar Entwicklungen, bei denen LMDB als Speicher-Engine-Komponente für SQLite fungiert. Das erste derartige Experiment im Jahr 2012 Ich verbrachte Autor LMDB Howard Chu. Ergebnisse erwies sich als so faszinierend, dass seine Initiative von OSS-Enthusiasten aufgegriffen wurde und angesichts dessen ihre Fortsetzung fand LumoSQL. Im Januar 2020 ist Den Shearer der Autor dieses Projekts vorgeführt es auf LinuxConfAu.

Die Hauptanwendung von LMDB ist die Verwendung als Engine für Anwendungsdatenbanken. Ihr Aussehen verdankt die Bibliothek den Entwicklern OpenLDAP, die mit BerkeleyDB als Grundlage ihres Projekts äußerst unzufrieden waren. Abkehr von der bescheidenen Bibliothek bbaumHoward Chu gelang es, eine der beliebtesten Alternativen unserer Zeit zu schaffen. Er widmete dieser Geschichte sowie der internen Struktur von LMDB seinen sehr coolen Bericht. „Die Lightning Memory-Mapping-Datenbank“. Leonid Yuriev (alias yleo) von Positive Technologies in seinem Vortrag auf der Highload 2015 „Die LMDB-Engine ist ein besonderer Champion“. Darin spricht er über LMDB im Kontext einer ähnlichen Aufgabe der Implementierung von ReOpenLDAP, und LevelDB wurde bereits vergleichender Kritik ausgesetzt. Als Ergebnis der Implementierung erhielt Positive Technologies sogar einen sich aktiv entwickelnden Fork MDBX mit sehr leckeren Features, Optimierungen und Fehlerbehebung.

LMDB wird häufig auch als Ist-Speicher verwendet. Zum Beispiel der Browser Mozilla Firefox wählte es für eine Reihe von Anforderungen und ab Version 9 Xcode bevorzugt Es ist SQLite zum Speichern von Indizes.

Die Engine hat sich auch in der Welt der mobilen Entwicklung durchgesetzt. Gebrauchsspuren können vorhanden sein finden im iOS-Client für Telegram. LinkedIn ging noch einen Schritt weiter und wählte LMDB als Standardspeicher für sein selbst entwickeltes Daten-Caching-Framework Rocket Data erzählte in einem Artikel im Jahr 2016.

LMDB kämpft erfolgreich um einen Platz an der Sonne in der Nische, die BerkeleyDB nach dem Übergang unter die Kontrolle von Oracle hinterlassen hat. Die Bibliothek wird für ihre Geschwindigkeit und Zuverlässigkeit geschätzt, auch im Vergleich zu ihresgleichen. Wie Sie wissen, gibt es kein kostenloses Mittagessen, und ich möchte den Kompromiss hervorheben, den Sie bei der Wahl zwischen LMDB und SQLite in Kauf nehmen müssen. Das obige Diagramm zeigt deutlich, wie die erhöhte Geschwindigkeit erreicht wird. Erstens zahlen wir nicht für zusätzliche Abstraktionsebenen zusätzlich zum Festplattenspeicher. Natürlich kann man in einer guten Architektur immer noch nicht auf sie verzichten, und sie werden zwangsläufig im Anwendungscode auftauchen, aber sie werden viel dünner sein. Sie verfügen nicht über Funktionen, die für eine bestimmte Anwendung nicht erforderlich sind, beispielsweise die Unterstützung von Abfragen in der SQL-Sprache. Zweitens wird es möglich, die Zuordnung von Anwendungsvorgängen zu Anforderungen an den Festplattenspeicher optimal zu implementieren. Wenn SQLite in meiner Arbeit sich aus den durchschnittlichen Anforderungen einer durchschnittlichen Anwendung ergibt, dann sind Sie als Anwendungsentwickler mit den Hauptlastszenarien bestens vertraut. Für eine produktivere Lösung müssen Sie sowohl für die Entwicklung der Erstlösung als auch für den anschließenden Support einen höheren Preis zahlen.

3. Drei Wale LMDB

Nachdem Sie die LMDB aus der Vogelperspektive betrachtet haben, ist es an der Zeit, tiefer einzusteigen. Die nächsten drei Abschnitte widmen sich der Analyse der wichtigsten Wale, auf denen die Speicherarchitektur beruht:

1. Speicherzugeordnete Dateien als Mechanismus zum Arbeiten mit der Festplatte und zum Synchronisieren interner Datenstrukturen.
2. B+-Baum als Organisation der gespeicherten Datenstruktur.
3. Copy-on-Write als Ansatz zur Bereitstellung von ACID-Transaktionseigenschaften und Multiversionierung.

3.1. Wal Nr. 1. Speicherzugeordnete Dateien

Memory-Mapping-Dateien sind ein so wichtiges Architekturelement, dass sie sogar im Namen des Repositorys auftauchen. Probleme beim Zwischenspeichern und Synchronisieren des Zugriffs auf gespeicherte Informationen sind vollständig dem Betriebssystem ausgeliefert. LMDB enthält selbst keine Caches. Dies ist eine bewusste Entscheidung des Autors, da Sie durch das direkte Lesen von Daten aus zugeordneten Dateien viele Abstriche bei der Implementierung der Engine machen können. Nachfolgend finden Sie eine bei weitem nicht vollständige Liste einiger davon.

1. Die Aufrechterhaltung der Konsistenz der Daten im Speicher bei der Arbeit mit ihnen aus mehreren Prozessen liegt in der Verantwortung des Betriebssystems. Im nächsten Abschnitt wird diese Mechanik ausführlich und mit Bildern besprochen.
2. Das Fehlen von Caches entlastet LMDB vollständig vom Overhead, der mit dynamischen Zuweisungen verbunden ist. Beim Lesen von Daten wird in der Praxis der Zeiger auf die richtige Adresse im virtuellen Speicher gesetzt und nichts weiter. Klingt nach Fantasie, aber in der Repository-Quelle sind alle Calloc-Aufrufe in der Repository-Konfigurationsfunktion konzentriert.
3. Das Fehlen von Caches bedeutet auch, dass es keine mit der Synchronisierung verbundenen Sperren für den Zugriff darauf gibt. Leser, von denen beliebig viele gleichzeitig existieren können, stoßen auf ihrem Weg zu den Daten auf keinen einzigen Mutex. Dadurch ist die Lesegeschwindigkeit hinsichtlich der Anzahl der CPUs ideal linear skalierbar. In LMDB werden nur Änderungsvorgänge synchronisiert. Es kann immer nur ein Autor gleichzeitig sein.
4. Ein Minimum an Caching- und Synchronisationslogik schützt den Code vor einer äußerst komplexen Art von Fehlern, die mit der Arbeit in einer Multithread-Umgebung verbunden sind. Auf der Usenix OSDI 2014-Konferenz gab es zwei interessante Datenbankstudien: „Nicht alle Dateisysteme sind gleich: Über die Komplexität der Erstellung absturzkonsistenter Anwendungen“ и Datenbanken aus Spaß und Profit quälen. Von ihnen erhalten Sie Informationen sowohl über die beispiellose Zuverlässigkeit von LMDB als auch über die nahezu fehlerfreie Implementierung der ACID-Eigenschaften von Transaktionen, die diese in demselben SQLite übertrifft.
5. Der Minimalismus von LMDB ermöglicht es, die maschinelle Darstellung seines Codes vollständig im L1-Cache des Prozessors zu platzieren, mit den daraus resultierenden Geschwindigkeitseigenschaften.

Leider sind in iOS speicherzugeordnete Dateien nicht so rosig, wie wir es gerne hätten. Um bewusster über die damit verbundenen Nachteile zu sprechen, ist es notwendig, sich an die allgemeinen Prinzipien für die Implementierung dieses Mechanismus in Betriebssystemen zu erinnern.

Allgemeine Informationen zu speicherzugeordneten Dateien

Das Betriebssystem ordnet jeder ausführbaren Anwendung eine Entität zu, die als Prozess bezeichnet wird. Jedem Prozess wird ein zusammenhängender Adressbereich zugewiesen, in dem er alles ablegt, was er zum Funktionieren benötigt. Die niedrigsten Adressen enthalten Abschnitte mit Code und fest codierten Daten und Ressourcen. Als nächstes kommt der nach oben wachsende Block des dynamischen Adressraums, der uns als Heap bekannt ist. Es enthält die Adressen von Entitäten, die während des Programmbetriebs erscheinen. Oben befindet sich der vom Anwendungsstapel verwendete Speicherbereich. Es wächst oder schrumpft, das heißt, seine Größe ist auch dynamischer Natur. Damit Stapel und Heap sich nicht gegenseitig drücken und stören, sind sie an verschiedenen Enden des Adressraums getrennt. Zwischen den beiden dynamischen Abschnitten befindet sich oben und unten ein Loch. Die Adressen in diesem mittleren Abschnitt werden vom Betriebssystem verwendet, um einem Prozess verschiedene Entitäten zuzuordnen. Insbesondere kann es einer Datei auf der Festplatte einen bestimmten fortlaufenden Satz von Adressen zuordnen. Eine solche Datei wird als speicherzugeordnete Datei bezeichnet.​

Der einem Prozess zugewiesene Adressraum ist riesig. Theoretisch ist die Anzahl der Adressen nur durch die Größe des Zeigers begrenzt, die durch die Bitzahl des Systems bestimmt wird. Wenn ihm physischer Speicher 1-in-1 zugewiesen würde, würde der erste Prozess den gesamten Arbeitsspeicher verschlingen und von Multitasking wäre keine Rede.​

Aus Erfahrung wissen wir jedoch, dass moderne Betriebssysteme beliebig viele Prozesse gleichzeitig ausführen können. Dies ist möglich, weil sie den Prozessen nur auf dem Papier viel Speicher zuweisen, in Wirklichkeit aber nur den Teil in den physischen Hauptspeicher laden, der hier und jetzt benötigt wird. Daher wird der mit dem Prozess verbundene Speicher als virtuell bezeichnet.

Das Betriebssystem organisiert den virtuellen und physischen Speicher in Seiten einer bestimmten Größe. Sobald eine bestimmte Seite des virtuellen Speichers benötigt wird, lädt das Betriebssystem diese in den physischen Speicher und legt die Entsprechung zwischen ihnen in einer speziellen Tabelle fest. Wenn keine freien Slots vorhanden sind, wird eine der zuvor geladenen Seiten auf die Festplatte kopiert und die angeforderte Seite tritt an ihre Stelle. Dieser Vorgang, auf den wir gleich zurückkommen werden, nennt sich Swapping. Die folgende Abbildung veranschaulicht den beschriebenen Vorgang. Darauf wurde Seite A mit Adresse 0 geladen und auf der Hauptspeicherseite mit Adresse 4 abgelegt. Dieser Umstand spiegelte sich in der Korrespondenztabelle in Zelle Nummer 0 wider.​

Bei speicherabgebildeten Dateien ist die Geschichte genau die gleiche. Logischerweise sollen sie durchgehend und vollständig im virtuellen Adressraum platziert werden. Sie gelangen jedoch Seite für Seite und nur bei Bedarf in den physischen Speicher. Die Änderung solcher Seiten wird mit der Datei auf der Festplatte synchronisiert. Somit können Sie Datei-I/O durchführen, indem Sie einfach mit Bytes im Speicher arbeiten – alle Änderungen werden vom Betriebssystemkern automatisch in die Originaldatei übertragen.​
​
Das Bild unten zeigt, wie LMDB seinen Status synchronisiert, wenn von verschiedenen Prozessen aus mit der Datenbank gearbeitet wird. Indem wir den virtuellen Speicher verschiedener Prozesse auf dieselbe Datei abbilden, verpflichten wir das Betriebssystem de facto dazu, bestimmte Blöcke seiner Adressräume transitiv miteinander zu synchronisieren, und genau hier sieht LMDB vor.​
​

Eine wichtige Nuance besteht darin, dass LMDB die Datendatei standardmäßig über den Schreibsystemaufrufmechanismus ändert und die Datei selbst im schreibgeschützten Modus angezeigt wird. Dieser Ansatz hat zwei wichtige Implikationen.

Die erste Konsequenz ist allen Betriebssystemen gemeinsam. Sein Kern besteht darin, Schutz vor unbeabsichtigter Beschädigung der Datenbank durch falschen Code zu bieten. Wie Sie wissen, können die ausführbaren Anweisungen eines Prozesses von überall in seinem Adressraum frei auf Daten zugreifen. Gleichzeitig bedeutet die Anzeige einer Datei im Lese-/Schreibmodus, wie wir gerade erinnert haben, dass jede Anweisung sie zusätzlich ändern kann. Wenn sie dies versehentlich tut und beispielsweise versucht, ein Array-Element an einem nicht vorhandenen Index tatsächlich zu überschreiben, kann sie auf diese Weise versehentlich die dieser Adresse zugeordnete Datei ändern, was zu einer Beschädigung der Datenbank führt. Wenn die Datei im schreibgeschützten Modus angezeigt wird, führt der Versuch, den ihr entsprechenden Adressraum zu ändern, zum Programmabsturz mit dem Signal SIGSEGV, und die Datei bleibt intakt.

Die zweite Konsequenz ist bereits spezifisch für iOS. Weder der Autor noch andere Quellen erwähnen es ausdrücklich, aber ohne es wäre LMDB für die Ausführung auf diesem mobilen Betriebssystem ungeeignet. Der nächste Abschnitt ist seiner Betrachtung gewidmet.

Besonderheiten von speicherzugeordneten Dateien in iOS

Im Jahr 2018 gab es einen wunderbaren Bericht auf der WWDC Tiefer Einblick in den iOS-Speicher. Darin heißt es, dass in iOS alle Seiten, die sich im physischen Speicher befinden, einem von drei Typen angehören: schmutzig, komprimiert und sauber.

Sauberer Speicher ist eine Sammlung von Seiten, die sicher aus dem physischen Speicher ausgelagert werden können. Die darin enthaltenen Daten können bei Bedarf aus ihren ursprünglichen Quellen erneut geladen werden. In diese Kategorie fallen schreibgeschützte, speicherzugeordnete Dateien. iOS scheut sich nicht, die einer Datei zugeordneten Seiten jederzeit aus dem Speicher zu entladen, da sie garantiert mit der Datei auf der Festplatte synchronisiert werden.
​
Alle geänderten Seiten gelangen in den schmutzigen Speicher, unabhängig davon, wo sie sich ursprünglich befanden. Insbesondere werden auch speicherabgebildete Dateien, die durch Schreiben in den ihnen zugeordneten virtuellen Speicher verändert werden, auf diese Weise klassifiziert. LMDB mit Flag öffnen MDB_WRITEMAP, nachdem Sie Änderungen daran vorgenommen haben, können Sie es selbst sehen.​

​Sobald eine Anwendung zu viel physischen Speicher beansprucht, komprimiert iOS ihre fehlerhaften Seiten. Die Menge an Speicher, die durch schmutzige und komprimierte Seiten belegt wird, ist der sogenannte Speicherbedarf der Anwendung. Wenn ein bestimmter Schwellenwert erreicht wird, folgt der OOM-Killer-Systemdämon dem Prozess und beendet ihn zwangsweise. Dies ist die Besonderheit von iOS im Vergleich zu Desktop-Betriebssystemen. Im Gegensatz dazu ist eine Reduzierung des Speicherbedarfs durch das Auslagern von Seiten vom physischen Speicher auf die Festplatte in iOS nicht vorgesehen. Über die Gründe kann man nur spekulieren. Vielleicht ist das Verfahren zum intensiven Verschieben von Seiten auf die Festplatte und zurück für mobile Geräte zu energieaufwändig, oder iOS spart die Ressource des Neuschreibens von Zellen auf SSD-Festplatten, oder vielleicht waren die Designer mit der Gesamtleistung des Systems, in dem sich alles befindet, nicht zufrieden ständig getauscht. Wie dem auch sei, die Tatsache bleibt bestehen.

Die bereits erwähnte gute Nachricht ist, dass LMDB standardmäßig nicht den mmap-Mechanismus zum Aktualisieren von Dateien verwendet. Daraus folgt, dass die gerenderten Daten von iOS als sauberer Speicher eingestuft werden und nicht zum Speicherbedarf beitragen. Dies kann mit dem Xcode-Tool namens VM Tracker überprüft werden. Der Screenshot unten zeigt den virtuellen Speicherstatus der iOS Cloud-Anwendung während des Betriebs. Zu Beginn wurden darin 2 LMDB-Instanzen initialisiert. Der erste durfte seine Datei auf 1 GB virtuellen Speicher abbilden, der zweite auf 512 MB. Trotz der Tatsache, dass beide Speicher eine gewisse Menge an residentem Speicher belegen, trägt keiner von ihnen zur schmutzigen Größe bei.

Jetzt ist es Zeit für die schlechten Nachrichten. Dank des Swap-Mechanismus in 64-Bit-Desktop-Betriebssystemen kann jeder Prozess so viel virtuellen Adressraum beanspruchen, wie der freie Speicherplatz auf der Festplatte für seinen potenziellen Swap zulässt. Das Ersetzen von Swap durch Komprimierung in iOS reduziert das theoretische Maximum drastisch. Jetzt müssen alle lebenden Prozesse in den Hauptspeicher (Lese-RAM) passen, und alle Prozesse, die nicht hineinpassen, unterliegen einer erzwungenen Beendigung. Es wird wie oben erwähnt Berichtund in amtliche Dokumentation. Infolgedessen schränkt iOS die für die Zuweisung über mmap verfügbare Speichermenge stark ein. Hier hier Sie können sich die empirischen Grenzen der Speichermenge ansehen, die mit diesem Systemaufruf auf verschiedenen Geräten zugewiesen werden kann. Bei den modernsten Smartphone-Modellen ist iOS um 2 Gigabyte großzügiger geworden, bei den Top-Versionen des iPad um 4. In der Praxis muss man sich natürlich auf die jüngsten unterstützten Gerätemodelle konzentrieren, bei denen alles sehr traurig ist. Schlimmer noch: Wenn Sie sich den Speicherstatus der Anwendung in VM Tracker ansehen, werden Sie feststellen, dass LMDB bei weitem nicht der Einzige ist, der speicherzugeordneten Speicher beansprucht. Gute Teile werden von Systemzuordnungen, Ressourcendateien, Bild-Frameworks und anderen kleineren Raubtieren aufgefressen.

Als Ergebnis von Experimenten in der Cloud kamen wir zu den folgenden Kompromisswerten für den von LMDB zugewiesenen Speicher: 384 Megabyte für 32-Bit-Geräte und 768 für 64-Bit-Geräte. Nachdem dieses Volumen aufgebraucht ist, beginnen alle Änderungsvorgänge mit dem Abschluss des Codes MDB_MAP_FULL. Wir beobachten solche Fehler bei unserer Überwachung, sie sind jedoch klein genug, um in dieser Phase vernachlässigt zu werden.

Ein nicht offensichtlicher Grund für den übermäßigen Speicherverbrauch durch den Speicher können langlebige Transaktionen sein. Um zu verstehen, wie diese beiden Phänomene zusammenhängen, wird es uns helfen, die verbleibenden zwei LMDB-Wale zu betrachten.

3.2. Wal Nr. 2. B+-Baum

Um Tabellen über einem Schlüsselwertspeicher zu emulieren, müssen die folgenden Vorgänge in seiner API vorhanden sein:

1. Einfügen eines neuen Elements.
2. Suchen Sie nach einem Element mit einem bestimmten Schlüssel.
3. Ein Element löschen.
4. Iterieren Sie Schlüsselintervalle in ihrer Sortierreihenfolge.

Die einfachste Datenstruktur, mit der alle vier Operationen problemlos implementiert werden können, ist ein binärer Suchbaum. Jeder seiner Knoten ist ein Schlüssel, der die gesamte Teilmenge der untergeordneten Schlüssel in zwei Teilbäume unterteilt. Links sind diejenigen, die kleiner als das übergeordnete Element sind, und rechts diejenigen, die größer sind. Das Erhalten eines geordneten Schlüsselsatzes wird durch eine der klassischen Baumdurchquerungen erreicht.​

Binärbäume haben zwei grundlegende Nachteile, die verhindern, dass sie als Festplattendatenstruktur effektiv sind. Erstens ist der Grad ihres Gleichgewichts unvorhersehbar. Es besteht ein erhebliches Risiko, Bäume zu erhalten, bei denen die Höhe verschiedener Äste stark variieren kann, was die algorithmische Komplexität der Suche im Vergleich zu den Erwartungen erheblich verschlechtert. Zweitens beraubt die Fülle an Querverbindungen zwischen Knoten Binärbäumen ihre Lokalität im Speicher. Nahe Knoten (in Bezug auf Verbindungen zwischen ihnen) können sich auf völlig unterschiedlichen Seiten im virtuellen Speicher befinden. Infolgedessen kann selbst eine einfache Durchquerung mehrerer benachbarter Knoten in einem Baum den Besuch einer vergleichbaren Anzahl von Seiten erfordern. Dies ist selbst dann ein Problem, wenn wir über die Effektivität von Binärbäumen als In-Memory-Datenstruktur sprechen, da ständig rotierende Seiten im Prozessor-Cache nicht billig sind. Wenn es darum geht, häufig knotenbezogene Seiten von der Festplatte hochzuladen, wird es richtig schlimm. bedauerlich.

B-Bäume lösen als Weiterentwicklung binärer Bäume die im vorherigen Absatz genannten Probleme. Erstens sind sie selbstausgleichend. Zweitens teilt jeder ihrer Knoten die Menge der untergeordneten Schlüssel nicht in zwei, sondern in M ​​geordnete Teilmengen auf, und die Anzahl M kann ziemlich groß sein und in der Größenordnung von mehreren Hundert oder sogar Tausenden liegen.

Damit:

1. Jeder Knoten verfügt über eine große Anzahl bereits geordneter Schlüssel und die Bäume sind sehr niedrig.
2. Der Baum erhält die Eigenschaft der Lokalität im Speicher, da Schlüssel mit ähnlichen Werten natürlicherweise nebeneinander auf einem oder benachbarten Knoten liegen.
3. Reduziert die Anzahl der Transitknoten beim Absteigen im Baum während eines Suchvorgangs.
4. Reduziert die Anzahl der gelesenen Zielknoten für Bereichsabfragen, da jeder von ihnen bereits eine große Anzahl geordneter Schlüssel enthält.

LMDB verwendet eine Variante des B-Baums namens B+-Baum zum Speichern von Daten. Das obige Diagramm zeigt die drei darin enthaltenen Knotentypen:

1. Oben ist die Wurzel. Es verwirklicht nichts weiter als das Konzept einer Datenbank innerhalb eines Repositorys. Innerhalb einer einzelnen LMDB-Instanz können Sie mehrere Datenbanken erstellen, die den zugeordneten virtuellen Adressraum gemeinsam nutzen. Jeder von ihnen beginnt mit seiner eigenen Wurzel.
2. Auf der untersten Ebene befinden sich die Blätter (Leaf). Nur sie enthalten die in der Datenbank gespeicherten Schlüssel-Wert-Paare. Das ist übrigens die Besonderheit von B+-Bäumen. Wenn ein normaler B-Baum die Wertanteile an den Knoten aller Ebenen speichert, dann gibt es die B+-Variation nur auf der niedrigsten Ebene. Nachdem wir diese Tatsache behoben haben, nennen wir im Folgenden den Untertyp des in LMDB verwendeten Baums einfach einen B-Baum.
3. Zwischen der Wurzel und den Blättern gibt es 0 oder mehr technische Ebenen mit Navigationsknoten (Zweigknoten). Ihre Aufgabe ist es, den sortierten Schlüsselsatz auf die Blätter aufzuteilen.

Physisch gesehen sind Knoten Speicherblöcke einer vorgegebenen Länge. Ihre Größe beträgt ein Vielfaches der Größe der Speicherseiten im Betriebssystem, über die wir oben gesprochen haben. Die Knotenstruktur ist unten dargestellt. Der Header enthält Metainformationen, die offensichtlichste davon ist beispielsweise die Prüfsumme. Als nächstes kommen Informationen über Offsets, entlang derer sich Zellen mit Daten befinden. Die Rolle von Daten können entweder Schlüssel sein, wenn es sich um Navigationsknoten handelt, oder ganze Schlüssel-Wert-Paare im Fall von Blättern. Mehr über die Struktur von Seiten können Sie in der Arbeit lesen „Bewertung leistungsstarker Schlüsselwertspeicher“.

Nachdem wir uns mit dem internen Inhalt der Seitenknoten befasst haben, werden wir den LMDB-B-Baum in der folgenden Form weiter vereinfacht darstellen.

Seiten mit Knoten werden nacheinander auf der Festplatte angeordnet. Seiten mit einer höheren Nummer befinden sich am Ende der Datei. Die sogenannte Metaseite (Metaseite) enthält Informationen über Offsets, mit denen sich die Wurzeln aller Bäume finden lassen. Wenn eine Datei geöffnet wird, durchsucht LMDB die Datei Seite für Seite vom Ende bis zum Anfang auf der Suche nach einer gültigen Metaseite und findet darüber vorhandene Datenbanken.​

Nachdem wir nun eine Vorstellung von der logischen und physischen Struktur der Datenorganisation haben, können wir mit der Betrachtung des dritten Wals von LMDB fortfahren. Mit seiner Hilfe erfolgen alle Speicheränderungen transaktional und isoliert voneinander, wodurch die Datenbank als Ganzes auch die Multiversionseigenschaft erhält.

3.3. Wal #3. Copy-on-Write

Bei einigen B-Tree-Operationen werden eine ganze Reihe von Änderungen an seinen Knoten vorgenommen. Ein Beispiel ist das Hinzufügen eines neuen Schlüssels zu einem Knoten, der bereits seine maximale Kapazität erreicht hat. In diesem Fall ist es notwendig, erstens den Knoten in zwei Teile zu teilen und zweitens einen Link zu dem neu ausgegliederten untergeordneten Knoten in seinem übergeordneten Knoten hinzuzufügen. Dieses Verfahren ist möglicherweise sehr gefährlich. Wenn aus irgendeinem Grund (Absturz, Stromausfall usw.) nur ein Teil der Änderungen aus der Serie erfolgt, bleibt der Baum in einem inkonsistenten Zustand.

Eine herkömmliche Lösung, um eine Datenbank fehlertolerant zu machen, besteht darin, neben dem B-Baum eine zusätzliche festplattenbasierte Datenstruktur hinzuzufügen, das Transaktionsprotokoll, auch bekannt als Write-Ahead-Protokoll (WAL). Es handelt sich um eine Datei, an deren Ende, genau vor der Änderung des B-Baums selbst, die beabsichtigte Operation geschrieben wird. Wenn also während der Selbstdiagnose eine Datenbeschädigung festgestellt wird, konsultiert die Datenbank das Protokoll, um sich selbst zu bereinigen.

LMDB hat eine andere Methode als Fehlertoleranzmechanismus gewählt, die Copy-on-Write genannt wird. Das Wesentliche besteht darin, dass die Daten auf einer vorhandenen Seite nicht aktualisiert werden, sondern zunächst vollständig kopiert werden und alle Änderungen bereits in der Kopie vorgenommen werden.​

Damit die aktualisierten Daten verfügbar sind, ist es außerdem erforderlich, die Verknüpfung zu dem aktuell gewordenen Knoten im übergeordneten Knoten in Bezug auf diesen zu ändern. Da es hierfür auch geändert werden muss, wird es ebenfalls vorkopiert. Der Prozess wird rekursiv bis zur Wurzel fortgesetzt. Die Daten auf der Metaseite ändern sich zuletzt.​​

Wenn der Prozess während des Aktualisierungsvorgangs plötzlich abstürzt, wird entweder keine neue Metaseite erstellt oder sie wird erst am Ende auf die Festplatte geschrieben und ihre Prüfsumme ist falsch. In beiden Fällen sind die neuen Seiten nicht erreichbar und die alten sind nicht betroffen. Dadurch entfällt die Notwendigkeit, dass LMDB Protokolle vorausschreibt, um die Datenkonsistenz aufrechtzuerhalten. De facto übernimmt die oben beschriebene Struktur der Datenspeicherung auf der Festplatte gleichzeitig deren Funktion. Das Fehlen eines expliziten Transaktionsprotokolls ist eines der Merkmale von LMDB, das eine hohe Datenlesegeschwindigkeit bietet.​

Das resultierende Konstrukt, genannt „Append-Only B-Tree“, bietet auf natürliche Weise Transaktionsisolation und Multiversionierung. In LMDB ist jeder offenen Transaktion eine aktuelle Baumwurzel zugeordnet. Solange die Transaktion nicht abgeschlossen ist, werden die damit verbundenen Seiten des Baums niemals geändert oder für neue Datenversionen wiederverwendet. Sie können also beliebig lange genau mit dem Datensatz arbeiten, der zu diesem Zeitpunkt relevant war Zeitpunkt, zu dem die Transaktion geöffnet wurde, auch wenn der Speicher zu diesem Zeitpunkt weiterhin aktiv aktualisiert wird. Dies ist die Essenz der Multiversionierung und macht LMDB zu einer idealen Datenquelle für unsere Liebsten UICollectionView. Nachdem Sie eine Transaktion geöffnet haben, müssen Sie den Speicherbedarf der Anwendung nicht erhöhen, indem Sie die aktuellen Daten hastig in eine speicherinterne Struktur pumpen und befürchten, nichts mehr übrig zu haben. Diese Funktion unterscheidet LMDB von demselben SQLite, das sich einer derart vollständigen Isolation nicht rühmen kann. Nachdem in letzterer zwei Transaktionen eröffnet und in einer davon ein bestimmter Datensatz gelöscht wurde, kann derselbe Datensatz in der zweiten verbleibenden Transaktion nicht mehr abgerufen werden.

Die Kehrseite der Medaille ist der möglicherweise deutlich höhere Verbrauch an virtuellem Speicher. Die Folie zeigt, wie die Datenbankstruktur aussehen wird, wenn sie gleichzeitig mit drei offenen Lesetransaktionen geändert wird, die verschiedene Versionen der Datenbank betrachten. Da LMDB keine Knoten wiederverwenden kann, die von den mit den tatsächlichen Transaktionen verknüpften Roots aus erreichbar sind, hat der Speicher keine andere Wahl, als einen weiteren vierten Root im Speicher zuzuweisen und die geänderten Seiten erneut darunter zu klonen.

An dieser Stelle ist es nicht überflüssig, sich an den Abschnitt über speicherzugeordnete Dateien zu erinnern. Es scheint, dass uns der zusätzliche Verbrauch an virtuellem Speicher nicht sonderlich stören sollte, da er nicht zum Speicherbedarf der Anwendung beiträgt. Gleichzeitig wurde jedoch festgestellt, dass iOS bei der Zuteilung sehr geizig ist und wir keine 1-Terabyte-LMDB-Region auf einem Server oder Desktop von der Schulter des Masters aus bereitstellen können, ohne überhaupt über diese Funktion nachzudenken. Wenn möglich, sollten Sie versuchen, die Laufzeit von Transaktionen so kurz wie möglich zu halten.

4. Entwerfen eines Datenschemas auf Basis der Schlüsselwert-API

Beginnen wir mit der Analyse der API, indem wir uns die grundlegenden Abstraktionen ansehen, die von LMDB bereitgestellt werden: Umgebung und Datenbanken, Schlüssel und Werte, Transaktionen und Cursor.

Ein Hinweis zu Code-Auflistungen

Alle Funktionen in der öffentlichen LMDB-API geben das Ergebnis ihrer Arbeit in Form eines Fehlercodes zurück, in allen nachfolgenden Auflistungen wird deren Überprüfung der Übersichtlichkeit halber jedoch weggelassen. In der Praxis haben wir unseren eigenen Code verwendet, um mit dem Repository zu interagieren. Gabel C++-Wrapper lmdbxx, in denen Fehler als C++-Ausnahmen auftreten.

Als schnellste Möglichkeit, LMDB mit einem iOS- oder macOS-Projekt zu verbinden, biete ich meinen CocoaPod an POSLMDB.

4.1. Grundlegende Abstraktionen

Umfeld

Struktur MDB_env Dies ist das Repository des internen Status der LMDB. Familie von Präfixfunktionen mdb_env ermöglicht Ihnen, einige seiner Eigenschaften zu konfigurieren. Im einfachsten Fall sieht die Initialisierung der Engine so aus.

mdb_env_create(env);​
mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

In der Mail.ru Cloud-Anwendung haben wir die Standardwerte nur für zwei Parameter geändert.

Die erste ist die Größe des virtuellen Adressraums, dem die Speicherdatei zugeordnet ist. Leider kann der spezifische Wert selbst auf demselben Gerät von Lauf zu Lauf erheblich variieren. Um diese Funktion von iOS zu berücksichtigen, wählen wir die maximale Speichermenge dynamisch aus. Ab einem bestimmten Wert halbiert es sich sukzessive bis zur Funktion mdb_env_open wird kein anderes Ergebnis zurückgeben als ENOMEM. Theoretisch gibt es auch den umgekehrten Weg: Weisen Sie der Engine zunächst ein Minimum an Speicher zu und erst dann, wenn Fehler eingehen MDB_MAP_FULL, erhöhen Sie es. Es ist jedoch viel dorniger. Der Grund dafür ist, dass das Verfahren zum Neuzuordnen des Speichers mithilfe der Funktion verwendet wird mdb_env_set_map_size macht alle Entitäten (Cursor, Transaktionen, Schlüssel und Werte) ungültig, die zuvor von der Engine empfangen wurden. Die Berücksichtigung einer solchen Wendung der Ereignisse im Code wird zu erheblichen Komplikationen führen. Wenn Ihnen der virtuelle Speicher dennoch sehr am Herzen liegt, dann könnte dies ein Grund sein, einen Blick auf den weit fortgeschrittenen Fork zu werfen. MDBX, wobei zu den deklarierten Funktionen die „automatische Anpassung der Datenbankgröße im laufenden Betrieb“ gehört.

Der zweite Parameter, dessen Standardwert uns nicht passte, regelt die Mechanismen zur Gewährleistung der Thread-Sicherheit. Leider gibt es zumindest in iOS 10 Probleme mit der Thread-Local-Storage-Unterstützung. Aus diesem Grund wird im obigen Beispiel das Repository mit dem Flag geöffnet MDB_NOTLS. Darüber hinaus ist es auch erforderlich Gabel C++-Wrapper lmdbxxum Variablen mit und in diesem Attribut auszuschneiden.

Datenbanken

Die Datenbank ist eine separate Instanz des B-Baums, über den wir oben gesprochen haben. Die Eröffnung erfolgt im Rahmen einer Transaktion, was zunächst etwas seltsam erscheinen mag.

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

Tatsächlich handelt es sich bei einer Transaktion in LMDB um eine Speichereinheit und nicht um eine bestimmte Datenbank. Mit diesem Konzept können Sie atomare Operationen an Entitäten durchführen, die sich in verschiedenen Datenbanken befinden. Theoretisch eröffnet sich dadurch die Möglichkeit, Tabellen in Form unterschiedlicher Datenbanken zu modellieren, ich bin jedoch einmal den anderen Weg gegangen, der weiter unten ausführlich beschrieben wird.

Schlüssel und Werte

Struktur MDB_val modelliert das Konzept sowohl eines Schlüssels als auch eines Werts. Das Repository hat keine Ahnung von deren Semantik. Für sie ist etwas, das anders ist, nur ein Array von Bytes einer bestimmten Größe. Die maximale Schlüsselgröße beträgt 512 Byte.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Der Store verwendet einen Komparator, um die Schlüssel in aufsteigender Reihenfolge zu sortieren. Wenn Sie es nicht durch Ihr eigenes ersetzen, wird das Standardformat verwendet, das sie Byte für Byte in lexikografischer Reihenfolge sortiert.​

Transaktionen

Das Transaktionsgerät ist ausführlich beschrieben in vorheriges Kapitel, deshalb werde ich hier ihre Haupteigenschaften in einer kurzen Zeile wiederholen:

1. Unterstützung für alle grundlegenden Eigenschaften ACIDSchlüsselwörter: Atomizität, Konsistenz, Isolation und Zuverlässigkeit. Ich kann nicht anders, als festzustellen, dass in Bezug auf die Haltbarkeit unter macOS und iOS ein Fehler in MDBX behoben wurde. Sie können mehr in ihrem lesen README.
2. Der Ansatz für Multithreading wird durch das Schema „Einzelschreiber/Mehrfachleser“ beschrieben. Autoren blockieren sich gegenseitig, aber sie blockieren nicht die Leser. Leser blockieren weder Autoren noch sich gegenseitig.
3. Unterstützung für verschachtelte Transaktionen.
4. Multiversionsunterstützung.

Multiversioning in LMDB ist so gut, dass ich es in Aktion demonstrieren möchte. Der folgende Code zeigt, dass jede Transaktion mit genau der Version der Datenbank arbeitet, die zum Zeitpunkt ihrer Öffnung relevant war, und vollständig von allen nachfolgenden Änderungen isoliert ist. Das Initialisieren des Repositorys und das Hinzufügen eines Testdatensatzes ist nicht von Interesse, daher bleiben diese Rituale unter dem Spoiler.

Einen Testeintrag hinzufügen

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Optional empfehle ich, den gleichen Trick mit SQLite auszuprobieren und zu sehen, was passiert.

Multiversionierung bringt sehr schöne Vorteile für das Leben eines iOS-Entwicklers. Mit dieser Eigenschaft können Sie die Aktualisierungsrate der Datenquelle für Bildschirmformulare einfach und natürlich an die Benutzerfreundlichkeit anpassen. Nehmen wir zum Beispiel eine solche Funktion der Mail.ru Cloud-Anwendung wie das automatische Laden von Inhalten aus der Systemmediengalerie. Bei einer guten Verbindung ist der Client in der Lage, mehrere Fotos pro Sekunde zum Server hinzuzufügen. Wenn Sie nach jedem Download aktualisieren UICollectionView Bei Medieninhalten in der Cloud des Benutzers können Sie bei diesem Vorgang auf 60 fps und flüssiges Scrollen verzichten. Um häufige Bildschirmaktualisierungen zu verhindern, müssen Sie die Datenänderungsrate in der Basis irgendwie begrenzen UICollectionViewDataSource.

Wenn die Datenbank keine Multiversionierung unterstützt und Sie nur mit dem aktuellen Status arbeiten können, müssen Sie ihn zum Erstellen eines zeitstabilen Daten-Snapshots entweder in eine speicherinterne Datenstruktur oder in eine temporäre Tabelle kopieren. Jeder dieser Ansätze ist sehr teuer. Bei der In-Memory-Speicherung erhalten wir sowohl die Speicherkosten, die durch die Speicherung konstruierter Objekte verursacht werden, als auch die Zeitkosten, die mit redundanten ORM-Transformationen verbunden sind. Der temporäre Tisch ist ein noch teureres Vergnügen, das nur in nicht trivialen Fällen sinnvoll ist.

Multiversioning LMDB löst das Problem der Aufrechterhaltung einer stabilen Datenquelle auf sehr elegante Weise. Es reicht aus, nur eine Transaktion zu eröffnen und voilà – bis wir sie abschließen, ist der Datensatz garantiert fixiert. Die Logik der Aktualisierungsrate liegt jetzt vollständig in den Händen der Präsentationsschicht, ohne dass nennenswerte Ressourcen anfallen.

Cursor

Cursor bieten einen Mechanismus für die geordnete Iteration über Schlüssel-Wert-Paare durch Durchlaufen eines B-Baums. Ohne sie wäre es unmöglich, die Tabellen in der Datenbank, der wir uns jetzt zuwenden, effektiv zu modellieren.

4.2. Tabellenmodellierung

Mit der Eigenschaft „Schlüsselreihenfolge“ können Sie eine Abstraktion der obersten Ebene, beispielsweise eine Tabelle, über Basisabstraktionen erstellen. Betrachten wir diesen Vorgang am Beispiel der Haupttabelle des Cloud-Clients, in der Informationen zu allen Dateien und Ordnern des Benutzers zwischengespeichert sind.

Tabellenschema

Eines der häufigsten Szenarios, für die die Struktur einer Tabelle mit einem Ordnerbaum geschärft werden sollte, besteht darin, alle Elemente auszuwählen, die sich in einem bestimmten Verzeichnis befinden. Ein gutes Datenorganisationsmodell für effiziente Abfragen dieser Art ist Adjazenzliste. Um es zusätzlich zum Schlüsselwertspeicher zu implementieren, ist es notwendig, die Schlüssel von Dateien und Ordnern so zu sortieren, dass sie nach ihrer Zugehörigkeit zum übergeordneten Verzeichnis gruppiert werden. Um außerdem den Inhalt des Verzeichnisses in der für einen Windows-Benutzer gewohnten Form anzuzeigen (Ordner zuerst, dann Dateien, beides alphabetisch sortiert), ist es notwendig, die entsprechenden Zusatzfelder in den Schlüssel aufzunehmen.

​Das Bild unten zeigt, wie die Darstellung von Schlüsseln als Array von Bytes je nach Aufgabenstellung aussehen kann. Zuerst werden die Bytes mit der übergeordneten Verzeichniskennung (rot) platziert, dann mit dem Typ (grün) und bereits am Ende mit dem Namen (blau). Nachdem sie vom Standard-LMDB-Komparator in lexikografischer Reihenfolge sortiert wurden, werden sie geordnet auf die erforderliche Art und Weise. Durch sequentielles Durchlaufen von Tasten mit demselben roten Präfix erhalten wir die ihnen zugeordneten Werte in der Reihenfolge, in der sie auf der Benutzeroberfläche angezeigt werden sollen (rechts), ohne dass eine zusätzliche Nachbearbeitung erforderlich ist.

Serialisieren von Schlüsseln und Werten

Es gibt weltweit viele Methoden zur Serialisierung von Objekten. Da wir keine anderen Anforderungen als die Geschwindigkeit hatten, haben wir uns für die schnellstmögliche Variante entschieden – einen Speicherauszug, der von einer Instanz der C-Sprachstruktur belegt wird. Der Schlüssel eines Verzeichniselements kann also durch die folgende Struktur modelliert werden NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Speichern NodeKey im Lagerbedarf im Objekt MDB_val Positionieren Sie den Zeiger auf die Daten an der Adresse am Anfang der Struktur und berechnen Sie deren Größe mit der Funktion sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

Im ersten Kapitel zu Datenbankauswahlkriterien habe ich die Minimierung dynamischer Zuordnungen im Rahmen von CRUD-Operationen als wichtigen Auswahlfaktor erwähnt. Funktionscode serialize zeigt, wie sie im Fall von LMDB beim Einfügen neuer Datensätze in die Datenbank vollständig vermieden werden können. Das vom Server eingehende Byte-Array wird zunächst in Stapelstrukturen umgewandelt und dann auf einfache Weise im Speicher abgelegt. Da es in LMDB auch keine dynamischen Zuweisungen gibt, können Sie im Vergleich zu iOS eine fantastische Situation erreichen: Verwenden Sie nur Stapelspeicher, um mit Daten auf dem gesamten Weg vom Netzwerk bis zur Festplatte zu arbeiten!

Bestellen von Schlüsseln mit einem binären Komparator

Die Schlüsselreihenfolgebeziehung wird durch eine spezielle Funktion namens Komparator angegeben. Da die Engine nichts über die Semantik der darin enthaltenen Bytes weiß, hat der Standardkomparator keine andere Wahl, als die Schlüssel in lexikografischer Reihenfolge anzuordnen und auf ihren Byte-für-Byte-Vergleich zurückzugreifen. Das Anordnen von Strukturen ähnelt dem Rasieren mit einer Schnitzaxt. In einfachen Fällen halte ich diese Methode jedoch für akzeptabel. Die Alternative wird unten beschrieben, aber hier werde ich auf ein paar Rechen achten, die auf dem Weg verstreut sind.

Das erste, was Sie im Auge behalten sollten, ist die Speicherdarstellung primitiver Datentypen. Daher werden auf allen Apple-Geräten Integer-Variablen im Format gespeichert Little Endian. Das bedeutet, dass sich das niedrigstwertige Byte auf der linken Seite befindet und Sie Ganzzahlen nicht anhand ihres Byte-für-Byte-Vergleichs sortieren können. Wenn Sie beispielsweise versuchen, dies mit einer Reihe von Zahlen von 0 bis 511 zu tun, erhalten Sie das folgende Ergebnis.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

Um dieses Problem zu lösen, müssen die Ganzzahlen in einem für den Bytekomparator geeigneten Format im Schlüssel gespeichert werden. Funktionen aus der Familie werden dabei helfen, die notwendige Transformation durchzuführen. hton* (insbesondere htons für Doppelbyte-Zahlen aus dem Beispiel).

Das Format zur Darstellung von Zeichenfolgen in der Programmierung ist, wie Sie wissen, ein Ganzes Geschichte. Wenn die Semantik von Zeichenfolgen sowie die zu ihrer Darstellung im Speicher verwendete Codierung darauf hindeuten, dass möglicherweise mehr als ein Byte pro Zeichen vorhanden ist, ist es besser, die Idee der Verwendung eines Standardkomparators sofort aufzugeben.

Das zweite, was Sie beachten sollten, ist Ausrichtungsprinzipien Strukturfeld-Compiler. Dadurch können im Speicher zwischen Feldern Bytes mit Müllwerten gebildet werden, was natürlich die Byte-Sortierung unterbricht. Um Müll zu vermeiden, müssen Sie die Felder entweder in einer streng definierten Reihenfolge deklarieren und dabei die Ausrichtungsregeln beachten, oder das Attribut in der Strukturdeklaration verwenden packed.

Schlüsselreihenfolge durch einen externen Komparator

Die Schlüsselvergleichslogik könnte sich für einen binären Komparator als zu komplex erweisen. Einer der vielen Gründe ist das Vorhandensein technischer Felder innerhalb der Bauwerke. Ich werde ihr Vorkommen am Beispiel eines uns bereits bekannten Schlüssels für ein Verzeichniselement veranschaulichen.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Bei aller Einfachheit verbraucht es in den allermeisten Fällen zu viel Speicher. Der Titelpuffer beträgt 256 Byte, obwohl Datei- und Ordnernamen im Durchschnitt selten mehr als 20–30 Zeichen umfassen.

​Eine der Standardtechniken zur Optimierung der Größe eines Datensatzes besteht darin, ihn auf seine tatsächliche Größe zuzuschneiden. Sein Wesen besteht darin, dass der Inhalt aller Felder variabler Länge in einem Puffer am Ende der Struktur gespeichert wird und ihre Längen in separaten Variablen gespeichert werden. Gemäß diesem Ansatz der Schlüssel NodeKey wird auf folgende Weise transformiert.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

Darüber hinaus wird während der Serialisierung nicht die Datengröße angegeben sizeof Die gesamte Struktur und die Größe aller Felder ist eine feste Länge plus der Größe des tatsächlich verwendeten Teils des Puffers.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

Durch das Refactoring konnten wir den von den Schlüsseln belegten Platz erheblich einsparen. Allerdings aufgrund des technischen Bereichs nameLength, ist der standardmäßige binäre Komparator nicht mehr für den Schlüsselvergleich geeignet. Wenn wir ihn nicht durch unseren eigenen ersetzen, ist die Länge des Namens ein wichtigerer Faktor bei der Sortierung als der Name selbst.

Mit LMDB kann jede Datenbank über eine eigene Schlüsselvergleichsfunktion verfügen. Dies geschieht über die Funktion mdb_set_compare unbedingt vor dem Öffnen. Aus offensichtlichen Gründen kann eine Datenbank während ihrer gesamten Lebensdauer nicht geändert werden. Am Eingang erhält der Komparator zwei Schlüssel im Binärformat und am Ausgang gibt er das Ergebnis des Vergleichs zurück: kleiner als (-1), größer als (1) oder gleich (0). Pseudocode für NodeKey sieht so aus.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

Solange alle Schlüssel in der Datenbank vom gleichen Typ sind, ist es zulässig, ihre Bytedarstellung bedingungslos in den Typ der Anwendungsstruktur des Schlüssels umzuwandeln. Hier gibt es eine Nuance, die jedoch weiter unten im Unterabschnitt „Datensätze lesen“ besprochen wird.

Wertserialisierung

Mit den Schlüsseln gespeicherter Datensätze arbeitet LMDB äußerst intensiv. Sie werden im Rahmen eines beliebigen Anwendungsvorgangs miteinander verglichen und die Leistung der gesamten Lösung hängt von der Geschwindigkeit des Komparators ab. In einer idealen Welt sollte der standardmäßige binäre Komparator ausreichen, um Schlüssel zu vergleichen. Wenn Sie jedoch wirklich Ihren eigenen verwenden müssten, sollte der Vorgang zum Deserialisieren der darin enthaltenen Schlüssel so schnell wie möglich sein.

Die Datenbank ist nicht besonders am Wertteil des Datensatzes (Wert) interessiert. Die Konvertierung von einer Bytedarstellung in ein Objekt erfolgt nur, wenn sie bereits vom Anwendungscode benötigt wird, beispielsweise um sie auf dem Bildschirm anzuzeigen. Da dies relativ selten vorkommt, sind die Anforderungen an die Geschwindigkeit dieses Verfahrens nicht so kritisch, und bei seiner Implementierung können wir uns viel freier auf die Bequemlichkeit konzentrieren. Um beispielsweise Metadaten über Dateien zu serialisieren, die noch nicht heruntergeladen wurden, verwenden wir NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

Es gibt jedoch Zeiten, in denen Leistung eine Rolle spielt. Wenn wir beispielsweise Metainformationen über die Dateistruktur der Benutzercloud speichern, verwenden wir denselben Objektspeicherauszug. Der Clou an der Aufgabe, ihre serialisierte Darstellung zu erzeugen, ist die Tatsache, dass die Elemente eines Verzeichnisses durch eine Klassenhierarchie modelliert werden.​

Für die Implementierung in der C-Sprache werden die spezifischen Felder der Erben in separate Strukturen herausgenommen und ihre Verbindung mit dem Basisfeld durch ein Feld vom Typ Union spezifiziert. Der eigentliche Inhalt der Union wird über das technische Attribut type angegeben.

typedef struct NodeValue {​
    EntityId localId;​
    EntityType type;​
    union {​
        FileInfo file;​
        DirectoryInfo directory;​
    } info;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeValue;​

Datensätze hinzufügen und aktualisieren

Der serialisierte Schlüssel und Wert können dem Speicher hinzugefügt werden. Hierzu wird die Funktion verwendet mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

In der Konfigurationsphase kann dem Repository erlaubt oder verboten werden, mehrere Datensätze mit demselben Schlüssel zu speichern.​​ Wenn die Duplizierung von Schlüsseln verboten ist, können Sie beim Einfügen eines Datensatzes festlegen, ob die Aktualisierung eines bereits vorhandenen Datensatzes zulässig ist oder nicht. Wenn das Ausfransen nur durch einen Fehler im Code verursacht werden kann, können Sie sich durch die Angabe des Flags dagegen absichern NOOVERWRITE.

Aufzeichnungen lesen

Die Funktion zum Lesen von Datensätzen in LMDB ist mdb_get. Wenn das Schlüssel-Wert-Paar durch zuvor abgelegte Strukturen dargestellt wird, sieht dieser Vorgang folgendermaßen aus.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

Die vorgestellte Auflistung zeigt, wie Sie durch die Serialisierung durch einen Dump von Strukturen dynamische Zuordnungen nicht nur beim Schreiben, sondern auch beim Lesen von Daten beseitigen können. Abgeleitet von Funktion mdb_get Der Zeiger sucht genau nach der virtuellen Speicheradresse, an der die Datenbank die Bytedarstellung des Objekts speichert. Tatsächlich erhalten wir eine Art ORM, das nahezu kostenlos ist und eine sehr hohe Geschwindigkeit beim Lesen von Daten bietet. Bei aller Schönheit des Ansatzes ist es notwendig, sich an einige damit verbundene Merkmale zu erinnern.

1. Bei einer schreibgeschützten Transaktion bleibt ein Zeiger auf eine Wertstruktur garantiert nur so lange gültig, bis die Transaktion geschlossen wird. Wie bereits erwähnt, bleiben die Seiten des B-Baums, auf denen sich das Objekt befindet, dank des Copy-on-Write-Prinzips unverändert, solange mindestens eine Transaktion auf sie verweist. Gleichzeitig können die Seiten, sobald die letzte damit verbundene Transaktion abgeschlossen ist, für neue Daten wiederverwendet werden. Wenn Objekte die Transaktion, durch die sie erstellt wurden, überleben müssen, müssen sie dennoch kopiert werden.
2. Bei einer Lese-/Schreibtransaktion ist der Zeiger auf den resultierenden Strukturwert nur bis zum ersten Änderungsvorgang (Schreiben oder Löschen von Daten) gültig.
3. Auch wenn die Struktur NodeValue nicht vollwertig, aber gekürzt (siehe Unterabschnitt „Anordnen von Schlüsseln durch einen externen Komparator“), über den Zeiger können Sie leicht auf seine Felder zugreifen. Die Hauptsache ist, es nicht zu dereferenzieren!
4. In keinem Fall können Sie die Struktur über den empfangenen Zeiger ändern. Alle Änderungen dürfen nur über die Methode vorgenommen werden mdb_put. Bei allem Wunsch wird dies jedoch nicht funktionieren, da der Speicherbereich, in dem sich diese Struktur befindet, im schreibgeschützten Modus abgebildet wird.
5. Ordnen Sie eine Datei dem Adressraum eines Prozesses neu zu, um mit der Funktion beispielsweise die maximale Speichergröße zu erhöhen mdb_env_set_map_size macht alle Transaktionen und zugehörigen Entitäten im Allgemeinen und Zeiger auf gelesene Objekte im Besonderen vollständig ungültig.

Schließlich ist noch ein Merkmal so heimtückisch, dass die Offenlegung seines Wesens nicht in einen weiteren Punkt passt. Im Kapitel über den B-Baum habe ich ein Diagramm der Organisation seiner Seiten im Speicher gegeben. Daraus folgt, dass die Adresse des Pufferanfangs mit serialisierten Daten absolut beliebig sein kann. Aus diesem Grund wird der Zeiger auf sie in der Struktur erhalten MDB_val und in einen Zeiger auf eine Struktur umgewandelt wird, ist im Allgemeinen nicht ausgerichtet. Gleichzeitig erfordern die Architekturen einiger Chips (im Fall von iOS ist dies armv7), dass die Adresse aller Daten ein Vielfaches der Größe eines Maschinenworts oder mit anderen Worten der Bitzahl des Systems beträgt (Für armv7 sind dies 32 Bit). Mit anderen Worten, eine Operation wie *(int *foo)0x800002 auf sie kommt einer Flucht gleich und führt zur Hinrichtung mit Urteil EXC_ARM_DA_ALIGN. Es gibt zwei Möglichkeiten, solch ein trauriges Schicksal zu vermeiden.

Die erste besteht darin, die Daten vorher in eine bekannt ausgerichtete Struktur zu kopieren. Auf einem benutzerdefinierten Komparator wird dies beispielsweise wie folgt widergespiegelt.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

Eine alternative Möglichkeit besteht darin, den Compiler im Voraus darüber zu informieren, dass Strukturen mit einem Schlüssel und einem Wert möglicherweise nicht mithilfe eines Attributs ausgerichtet werden aligned(1). Auf ARM kann der gleiche Effekt auftreten zu erreichen, und Verwendung des gepackten Attributs. In Anbetracht der Tatsache, dass sie auch zur Optimierung des von der Struktur eingenommenen Raums beiträgt, erscheint mir diese Methode jedoch vorzuziehen приводит um die Kosten für Datenzugriffsvorgänge zu erhöhen.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Bereichsabfragen

Um eine Gruppe von Datensätzen zu durchlaufen, bietet LMDB eine Cursor-Abstraktion. Schauen wir uns am Beispiel einer Tabelle mit uns bereits bekannten Benutzer-Cloud-Metadaten an, wie man damit arbeitet.

Im Rahmen der Anzeige einer Liste von Dateien in einem Verzeichnis müssen Sie alle Schlüssel finden, mit denen die untergeordneten Dateien und Ordner verknüpft sind. In den vorherigen Unterabschnitten haben wir die Schlüssel sortiert NodeKey sodass sie zuerst nach ihrer übergeordneten Verzeichnis-ID sortiert werden. Technisch gesehen reduziert sich die Aufgabe, den Inhalt eines Ordners zu erhalten, darauf, den Cursor auf die obere Grenze einer Gruppe von Schlüsseln mit einem bestimmten Präfix zu setzen und anschließend zur unteren Grenze zu iterieren.

Sie können die Obergrenze „auf der Stirn“ durch sequentielle Suche finden. Dazu wird der Cursor an den Anfang der gesamten Liste der Schlüssel in der Datenbank gesetzt und dann inkrementiert, bis der Schlüssel mit der übergeordneten Verzeichniskennung darunter erscheint. Dieser Ansatz hat zwei offensichtliche Nachteile:

1. Die lineare Komplexität der Suche, obwohl sie, wie Sie wissen, in Bäumen im Allgemeinen und in einem B-Baum im Besonderen in logarithmischer Zeit durchgeführt werden kann.​
2. Vergebens werden alle Seiten vor der gewünschten aus der Datei in den Hauptspeicher hochgehoben, was extrem teuer ist.

Glücklicherweise bietet die LMDB-API eine effiziente Möglichkeit, den Cursor zunächst zu positionieren. Dazu müssen Sie einen Schlüssel bilden, dessen Wert bekanntermaßen kleiner oder gleich dem Schlüssel ist, der sich an der Obergrenze des Intervalls befindet. In Bezug auf die Liste in der Abbildung oben können wir beispielsweise einen Schlüssel erstellen, in dem sich das Feld befindet parentId wird gleich 2 sein und der Rest wird mit Nullen gefüllt. Ein solcher teilweise gefüllter Schlüssel wird dem Eingang der Funktion zugeführt mdb_cursor_get zeigt den Betrieb an MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Wenn die Obergrenze der Schlüsselgruppe gefunden wird, iterieren wir darüber, bis entweder wir oder der Schlüssel mit einem anderen übereinstimmen parentId, sonst gehen die Schlüssel überhaupt nicht aus.​

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

Das Schöne ist, dass wir im Rahmen der Iteration mit mdb_cursor_get nicht nur den Schlüssel, sondern auch den Wert erhalten. Wenn zur Erfüllung der Auswahlbedingungen unter anderem die Felder aus dem Wertteil des Datensatzes überprüft werden müssen, sind diese ohne zusätzliche Gesten für sich selbst durchaus zugänglich.

4.3. Modellierung von Beziehungen zwischen Tabellen

Bisher ist es uns gelungen, alle Aspekte des Entwurfs und der Arbeit mit einer Einzeltabellendatenbank zu berücksichtigen. Wir können sagen, dass eine Tabelle eine Menge sortierter Datensätze ist, die aus Schlüssel-Wert-Paaren desselben Typs bestehen. Wenn Sie einen Schlüssel als Rechteck und den zugehörigen Wert als Kästchen darstellen, erhalten Sie ein visuelles Diagramm der Datenbank.

​

Allerdings kommt man im wirklichen Leben selten mit so wenig Blut aus. In einer Datenbank ist es oft erforderlich, erstens mehrere Tabellen zu haben und zweitens darin Selektionen in einer anderen Reihenfolge als dem Primärschlüssel durchzuführen. Der letzte Abschnitt ist den Fragen ihrer Entstehung und Verknüpfung gewidmet.

Indextabellen

Die Cloud-App verfügt über einen Abschnitt „Galerie“. Es zeigt Medieninhalte aus der gesamten Cloud, sortiert nach Datum. Für die optimale Umsetzung einer solchen Auswahl müssen Sie neben der Haupttabelle eine weitere mit einem neuen Schlüsseltyp erstellen. Sie enthalten ein Feld mit dem Erstellungsdatum der Datei, das als primäres Sortierkriterium dient. Da sich die neuen Schlüssel auf dieselben Daten beziehen wie die Schlüssel in der zugrunde liegenden Tabelle, werden sie Indexschlüssel genannt. Sie sind im Bild unten orange hervorgehoben.

Um die Schlüssel verschiedener Tabellen innerhalb derselben Datenbank voneinander zu trennen, wurde ihnen allen ein zusätzliches technisches Feld tableId hinzugefügt. Indem wir die Sortierung auf höchste Priorität setzen, gruppieren wir die Schlüssel zuerst nach Tabellen und bereits innerhalb der Tabellen – nach unseren eigenen Regeln.​

Der Indexschlüssel bezieht sich auf dieselben Daten wie der Primärschlüssel. Die einfache Implementierung dieser Eigenschaft durch die Zuordnung einer Kopie des Wertteils des Primärschlüssels ist aus mehreren Gesichtspunkten gleichzeitig suboptimal:​

1. Unter dem Gesichtspunkt des Platzbedarfs können die Metadaten recht umfangreich sein.
2. Aus Leistungssicht müssen Sie beim Aktualisieren der Knotenmetadaten zwei Schlüssel überschreiben.
3. Aus der Sicht der Codeunterstützung kommt es schließlich zu einem subtilen Fehler in Form von Dateninkonsistenzen im Speicher, wenn wir vergessen, die Daten für einen der Schlüssel zu aktualisieren.

Als nächstes werden wir überlegen, wie diese Mängel beseitigt werden können.

Organisation von Beziehungen zwischen Tabellen

Das Muster eignet sich gut zum Verknüpfen einer Indextabelle mit der Haupttabelle „Schlüssel als Wert“. Wie der Name schon sagt, ist der Wertteil des Indexdatensatzes eine Kopie des Primärschlüsselwerts. Dieser Ansatz beseitigt alle oben aufgeführten Nachteile, die mit der Speicherung einer Kopie des Wertteils des Primärdatensatzes verbunden sind. Die einzige Gebühr besteht darin, dass Sie zum Abrufen des Werts anhand des Indexschlüssels zwei Abfragen an die Datenbank anstelle einer durchführen müssen. Schematisch sieht das resultierende Datenbankschema wie folgt aus.

Ein weiteres Muster zum Organisieren von Beziehungen zwischen Tabellen ist „redundanter Schlüssel“. Sein Kern besteht darin, dem Schlüssel zusätzliche Attribute hinzuzufügen, die nicht zum Sortieren, sondern zum Neuerstellen des zugehörigen Schlüssels benötigt werden. Es gibt jedoch reale Beispiele für seine Verwendung in der Mail.ru-Cloud-Anwendung, um ein tiefes Eintauchen in die Mail.ru-Cloud-Anwendung zu vermeiden Im Zusammenhang mit bestimmten iOS-Frameworks werde ich ein fiktives, aber verständlicheres Beispiel geben.

Mobile Cloud-Clients verfügen über eine Seite, auf der alle Dateien und Ordner angezeigt werden, die der Benutzer mit anderen Personen geteilt hat. Da es relativ wenige solcher Dateien gibt und viele spezifische Informationen über die mit ihnen verbundene Publizität enthalten sind (wem Zugang gewährt wird, mit welchen Rechten usw.), wird es nicht sinnvoll sein, sie mit dem Wertanteil davon zu belasten der Eintrag in der Haupttabelle. Wenn Sie solche Dateien jedoch offline anzeigen möchten, müssen Sie sie trotzdem irgendwo speichern. Eine natürliche Lösung besteht darin, eine separate Tabelle dafür zu erstellen. Im Diagramm unten wird dem Schlüssel „P“ vorangestellt und der Platzhalter „propname“ kann durch den spezifischeren Wert „public info“ ersetzt werden.​

Alle eindeutigen Metadaten, für die die neue Tabelle erstellt wurde, werden in den Wertteil des Datensatzes verschoben. Gleichzeitig möchte ich die Daten zu Dateien und Ordnern, die bereits in der Haupttabelle gespeichert sind, nicht duplizieren. Stattdessen werden dem „P“-Schlüssel redundante Daten in Form der Felder „Knoten-ID“ und „Zeitstempel“ hinzugefügt. Dank ihnen können Sie einen Indexschlüssel erstellen, mit dem Sie den Primärschlüssel und schließlich die Metadaten des Knotens erhalten.

Abschluss

Wir bewerten die Ergebnisse der LMDB-Implementierung positiv. Danach sank die Zahl der Anwendungsstopps um 30 %.

Die Ergebnisse der geleisteten Arbeit fanden außerhalb des iOS-Teams Resonanz. Derzeit ist auch einer der Hauptabschnitte „Dateien“ in der Android-Anwendung auf die Verwendung von LMDB umgestiegen, und weitere Teile sind in Vorbereitung. Die C-Sprache, in der die Schlüsselwertspeicherung implementiert ist, war eine gute Hilfe, um die Anwendungsbindung darum herum zunächst plattformübergreifend in der Sprache C++ zu gestalten. Für eine nahtlose Verbindung der resultierenden C++-Bibliothek mit Plattformcode in Objective-C und Kotlin wurde ein Codegenerator verwendet Dschinn von Dropbox, aber das ist eine andere Geschichte.

Source: habr.com