Was ist das Besondere an DBMS für Daten im RAM

    Konstantin Osipov ( kostja )


    Konstantin Osipov

    Wie ist die Idee des Berichts entstanden? Ich spreche nicht gerne über Features, insbesondere über zukünftige Features. Es stellt sich heraus, dass die Leute nicht wirklich gerne zuhören. Sie hören gerne, wie alles funktioniert. Dies ist ein Bericht darüber, wie alles funktioniert oder meiner Meinung nach in einem modernen DBMS funktionieren sollte.

    Ich werde versuchen, es so zu machen, dass wir von der Makroebene auf die Mikroebene heruntergehen können, d.h. Wie wir, indem wir zuerst Makroprobleme abwerfen, einen Raum schaffen, den wir auf der mittleren Ebene und auf der Mikroebene auswählen können.



    Auf Makroebene sollte so ein modernes DBMS aufgebaut sein. Warum haben wir heute die Möglichkeit, neue Datenbanken zu erstellen, warum können wir nicht die aktuelle Datenbank verwenden und mit ihrer Leistung zufrieden sein, einen Patch dafür schreiben oder sie verschärfen? Einfach einen Patch schreiben, der ihn beschleunigt, wenn er langsam ist? Aus welchem ​​Lösungsraum wählen wir?



    Nachdem wir einige grundlegende Architekturprinzipien festgelegt haben, müssen wir uns weiter unten mit dem Ingenieurwesen befassen. Abgesehen von der Tatsache, dass es Datenbanken gibt, die Transaktionen mithilfe der Versionskontrolle für mehrere Versionen verarbeiten, und Datenbanken, die Transaktionen mithilfe von Sperren verarbeiten, wirkt sich die Art und Weise, wie Sie diesen Algorithmus implementiert haben (relativ gesehen, wie direkt Ihre Hände sind), direkt auf die Leistung aus. Wenn Sie mit dem ersten Faktor das Dutzendfache des Produktivitätswachstums erzielen, mit dem zweiten Faktor das Zwei- bis Dreifache, aber es ist auch wichtig, dass Sie sich nicht schämen, dass Redis dasselbe ist, obwohl es strukturell einfacher ist. Ein Tuzik-Heizkissen gefällt Ihnen nicht, weil Sie trotz der Tatsache, dass es eine Million Funktionen gibt, nicht an Leistung usw. verlieren. Das ist Engineering.

    Der zweite Teil des Berichts befasst sich mit dem Algorithmus und der Datenstruktur, d.h. Wie reparieren wir einige grundlegende technische Ansätze, arbeiten mit Threads usw. Und wir sagen, wie wir die Datenstrukturen implementieren, die am schnellsten sind und es uns ermöglichen, Daten schneller und besser als alles andere zu verarbeiten und zu speichern.

    Der 3. und 4. Teil sind die wütendsten, weil ich dort versuche, zumindest die Spitze über unsere implementierten Algorithmen und Datenstrukturen zu informieren.

    DBMS-Architektur. Wo soll ich anfangen? Warum gibt es 2015 ein Zeitfenster für eine moderne Datenbank?



    Lassen Sie mich an die Grundvoraussetzungen erinnern, dies ist der Raum, in dem wir spielen können. Es gibt ACID-Anforderungen, die wir erfüllen müssen. Jede Datenbank, die glaubt, ACID überspringen zu können, unterliegt meiner Meinung nach keiner ernsthaften Prüfung, d. H. Das ist so ein Handwerk am Knie, weil früher oder später klar wird, dass Sie die Daten, die sie Ihnen geben, immer noch nicht verlieren müssen, benutzerfreundlich sein müssen, konsistent sein müssen usw. Dies ist eine akademische Definition, aber in der Tat gibt es sogar in ACID auf einem so kleinen Objektträger Abgründe, d.h. Sie können 2-3-4 Stunden über ihn sprechen.

    Was ist HALTBARKEIT? Wenn ich darüber spreche, sage ich immer, was HALTBARKEIT in Bezug auf den Atomkrieg ist. Ist Ihre Datenbank im Falle eines wahrscheinlichen Angriffs eines Gegners DAUERHAFT? Oder ISOLATION - was ist das? Warum soll sich die Sichtbarkeit zweier Transaktionen nicht gegenseitig beeinflussen? Aber was ist, wenn ich ein trickreicher Typ bin, ich habe 2 Laptops, die ich von einem Laptop zum anderen verbunden habe? In einen Laptop sagte ich beginne, füge ein, dann schaute ich, was ich dort einfügte, traf eine Entscheidung auf der Grundlage dessen, in den zweiten Laptop, den ich startete, fügte ich bereits die Daten ein, die ich mit meinen Augen betrachtete. Wie schlau ich bin, ich habe ISOLATION getäuscht. Gibt es hier irgendwelche Garantien? Dies sind jedoch die Spielregeln.

    Und einer von ihnen, der grundlegendste, der einen sehr ernsten Einfluss auf die Leistung hat, ist die Isolation. Warum? Weil die Isolierung von Transaktionen voneinander so viele Dinge auf einmal betrifft. Das heißt Sie können jemanden dazu bringen, ihre Version der Daten zu lesen, ohne eine andere Person zu stören (wie Postgres funktioniert, MySQL mit InnoDB). Aber sobald es um die Aufnahme geht, haben wir ein Dilemma. Wir haben keine Möglichkeit, zwei Teilnehmer zu isolieren, die versuchen, dieselben Daten zu aktualisieren und sich gleichzeitig aus algorithmischer Sicht vollständig voneinander zu isolieren.



    Wir müssen in der einen oder anderen Form einem anderen Teilnehmer signalisieren, dass zur gleichen Zeit jemand anderes mit diesen Daten arbeitet. Dies wird theoretisch durch das Konzept eines Zeitplans formalisiert (ich habe ein Beispiel für einen Zeitplan gegeben). Wir haben Datenelemente, d. H. X und Y sind unsere Daten, 1 und 2 sind unsere Teilnehmer, r und w sind Operationen. Teilnehmer lesen oder schreiben Daten, E ist der Zeitplan, nach dem sie arbeiten.



    Letztendlich ist die einzige eindrucksvolle Möglichkeit, Isolation bereitzustellen, durch Sperren, d.h. Die Grundlage für die Datenbanken von vor 20, 30 Jahren war, dass sie auf zweiphasigen Sperren basieren.



    Das heißt Um einen seriellen Zeitplan zu erstellen, müssen die Teilnehmer Sperren für die Objekte erfassen, die sie ändern. Gleichzeitig gibt es eine Konkurrenzkontrolle mit mehreren Versionen, die es uns ermöglicht, ihre Erfassung in einigen Fällen zu vermeiden oder zu verzögern, d. H. Wir können am Ende, zum Zeitpunkt des Commits, bereits überprüfen, in irgendeiner Weise bestätigen, dass die Integrität nicht verletzt wurde. Das heißt Sperren wirken sich nicht wesentlich auf die Teilnehmer aus. Dennoch erfordern solche Algorithmen in bestimmten Szenarien auch bei der Steuerung von Wettbewerben mit mehreren Versionen Sperren für nicht vorhandene Objekte. Der strengste Serialisierungsmodus - im klassischen DBMS heißt er serialisierbar und erfordert weiterhin Sperren.



    Dies ist ein grundlegender Mechanismus, und er ist in der akademischen Gemeinschaft durch das Zwei-Phasen-Blockierungs-Theorem festgelegt, das mehr oder weniger grundlegend ist, d.h. Wir müssen diese Schlösser akkumulieren. Klassische DBMS basieren auf diesem Schema.



    Darüber hinaus wurden die klassischen DBMS ursprünglich im Universum entwickelt, in dem das Verhältnis von Festplatte zu Arbeitsspeicher völlig anders ist als heute. Relativ gesehen waren 640 KB Speicher und 100 MB Festplatte möglich - und das war gut so. Das heißt das Verhältnis ist irgendwo 1 zu 100. Jetzt ist das Verhältnis oft 1 zu 1000, d.h. Diese Beziehungen haben sich geändert. Und die Geschwindigkeiten haben sich noch radikaler geändert, d.h. Wenn der RAM früher nur 100-mal schneller war als eine Festplatte, ist er jetzt 1000- oder 10000-mal schneller als eine Festplatte. Es gab eine radikale Veränderung in den Verhältnissen, aus denen wir wählen mussten.



    Ein klassisches Beispiel dafür, warum dies wichtig ist, ist, dass klassische DBMS auf dem Prinzip des zweistufigen Speichers basieren, d. H. Sie haben eine Art Darstellung von Daten auf der Festplatte und Sie haben eine Darstellung von Daten im Speicher. Durch den Arbeitsspeicher wird Ihre Ansicht auf der Festplatte zwischengespeichert. Sie müssen zwangsläufig einen Kompromiss zwischen der effektiven Arbeit mit einer Festplatte und der effektiven Arbeit mit dem Speicher eingehen.

    Insbesondere, um effektiv mit der Festplatte zu arbeiten ... Achten Sie auf den Leerraum auf der Folie - dies ist eine typische Seite eines typischen DBMS, in dem Zeilen gespeichert werden. Normalerweise ist die Seite nicht voll, weil unser Speicherplatz nicht teuer ist und die Kosten für das Schreiben auf eine Festplatte nicht proportional zur Größe des Schreibvorgangs, sondern proportional zur Anzahl der Festplattenzugriffe steigen. Dementsprechend ist es für uns sinnvoll, Löcher auf der Festplatte zu haben, da es nicht beängstigend ist, dass wir dieses Loch aufzeichnen. Das Aufzeichnen eines Lochs kostet uns nichts.

    Im RAM ist die Geschichte völlig anders. Dort ist es wichtig, dass die Daten so wenig Platz wie möglich belegen, da die Gesprächskosten in etwa gleich sind. RAM hat mehr oder weniger den gleichen Preis für Direktzugriff bzw. es ist für uns sinnvoll, die Dinge so kompakt wie möglich zu gestalten. Einer dieser Faktoren ist, dass, wenn Sie ein DBMS für RAM von Grund auf neu erstellen, es für Sie sinnvoll ist, mehr oder weniger grundlegende Algorithmen und Datenstrukturen zu überprüfen, auf denen Sie vorgehen, d. H. Sie können diese Löcher loswerden - dies ist nur ein Beispiel.

    Übrigens, wenn wir über dieses Beispiel sprechen, bekommen wir eine interessante Geschichte. Viele sagen: "Warum brauchen wir DBMS X, wir verwenden DBMS Y und fügen nur Speicher hinzu." Ich habe solche Szenarien gesehen, wenn Leute Datenbanken nehmen, die für Second-Hand-Läden bestimmt sind, d.h. Für die Disk Base geben MySQL, Postgres, Mongo, eine bestimmte Menge an Speicher, alles passt in ihr Gedächtnis und sie sind glücklich. Nur die wirtschaftliche Berechnung hier ist sofort fehlerhaft, denn wenn Sie die Datenbank im Speicher machen, dann ist ein typischer Speicherbedarf, d.h. Die Menge des belegten Speichers kann um ein Vielfaches geringer sein, da nicht alle mit dem Speichern auf der Festplatte verbundenen Headheds vorhanden sind. Aus wirtschaftlicher Sicht ist es falsch, ein DBMS, das zur Speicherung auf einer Festplatte vorgesehen ist, wegzuwerfen und alle Daten in den Speicher zu stellen.



    Meine solchen Erfindungen basieren nicht auf einem leeren Ort. Im Jahr 2008 wurde ein Artikel von einem der Klassiker der DBMS-Welt veröffentlicht, der eine Analyse der Aktivitäten enthält, die das DBMS in verschiedenen Subsystemen durchführt, d. H. Wie viel Prozent Aufwand und was ist das DBMS. Die Hauptblockierungs-Subsysteme wurden identifiziert, Latching ist die gleiche Blockierung, aber nur auf einer niedrigeren Ebene, wenn wir nicht Daten, sondern Prozesse blockieren müssen, die miteinander interagieren. Und in diesem Artikel wird der Schluss gezogen, dass nur 12% des modernen DBMS für nützliche Arbeit, alles andere für diese magischen Buchstaben ACID und für die Interaktion mit veralteten Architekturen, d.h. arbeiten, aufgebaut auf dem Prinzip veralteter Architekturen. Aus dieser Grafik ergibt sich dieses Zeitfenster

    Wie können wir all diese Blockierungen, das Fliegen usw. loswerden? Stücke? Wie können wir den Aufwand für die Übertragung von Daten von Speicherplatten und das Ändern von Präsentationsformaten verringern? Hier sind die Grundlagen, die ich geschrieben habe und die die Grundlage der Tarantool-Architektur bildeten:



    Tatsächlich ist dies keine eindeutige Architektur. Wenn Sie sich Memcached, Redis und VoltDB ansehen, stellt sich heraus, dass wir nicht die einzigen sind, d. H. dann nehmen wir und fangen an, relativ gesehen, in unserer Liga zu konkurrieren. Wir gehen in unsere Liga, in der wir folgendes sagen:

    • Wir haben 100% der Daten im RAM gespeichert,
    • Wir führen Transaktionen nacheinander aus, damit wir keine Sperren vornehmen müssen. Wir haben nicht das eigentliche Konzept des Sperrens. Wir geben nur die Menge an RAM auf, die wir für eine Transaktion zugewiesen haben. Sie verwendet sie ausschließlich. Dann führen wir die nächste Transaktion durch.

    Trotzdem sagen wir, dass wir die Daten zersplittern werden, d.h. Da unsere horizontale Skalierung die Norm ist, versuchen wir nicht einmal, die Datenbank auf einem Computer effizient zu betreiben. Eine Maschine ist heute noch ein Supercomputer. 48 Kerne, die unterschiedliche Kosten für den Zugriff auf RAM haben, d.h. Wenn Sie von einem Core auf eine Site zugreifen, haben Sie einen Preis und von einem anderen Core auf dieselbe Site einen anderen Anreizpreis. Dies ist bereits ein Supercomputer, und zu sagen, dass effizientes Arbeiten an einem Computer die gleiche Aufgabe ist, die vor 10 bis 20 Jahren nicht mehr erforderlich war, sodass wir dieses Problem überhaupt nicht lösen werden.

    Es gibt einen interessanten Punkt in dieser ganzen Geschichte. Wir sagen, dass wir ein DBMS in unserem Speicher haben, das Transaktionen sequentiell ausführt. Was ist los? Wenn wir während der Transaktion keine Daten verlieren müssen, müssen wir diese in das Protokoll schreiben, d. H. Wir können diese Arbeit nicht abbrechen. Wir haben noch ein Tagebuch, das Tagebuch ist auf der Festplatte gespeichert. Wenn wir jede Transaktion nacheinander in das Protokoll schreiben, tritt immer noch ein Leistungsproblem auf, da die Festplatte langsam ist, d. H. Die Tatsache, dass wir die CPU wenig nutzen, gibt uns nichts, die Festplatte ist langsam. Wir müssen herausfinden, wie ein Journal in großen Mengen zu 100 bei jeweils 1000 Transaktionen geschrieben werden kann, dann können wir diese Aufzeichnungskosten auf viele Transaktionen verteilen und den Floput erhöhen, d.h. Bandbreite. Auf diese Weise erhöhen wir nicht die Produktivität, d.h.



    Das Problem ist: Wie werden Transaktionen zurückgesetzt, wenn der Protokolleintrag fehlgeschlagen ist? Im Prinzip habe ich diese Technologien in der Literatur nicht gesehen, aber Tarantool verwendet eine Analogie zum Film. Angenommen, wir haben eine Transaktion im Speicher, die bereits abgeschlossen ist, und wir müssen sie in das Protokoll schreiben. Diese Transaktion wartet in der Schlange, bis eine langsame Festplatte sie schreibt. In diesem Moment ist eine andere Transaktion eingegangen, die dieselben Daten liest oder aktualisiert. Was soll ich mit ihr machen? Sie daran hindern, es zu tun? Wenn wir die Ausführung verbieten, wird unsere Produktivität stark sinken. Wenn wir die Ausführung zulassen, kann sich herausstellen, dass die Transaktion, die auf ihre Ausführung wartet, nicht aufgezeichnet wurde und der Speicherplatz aufgebraucht ist. Was sollen wir dann tun? Roll zurück. \

    Das Rollback in Tarantool erfolgt nach dem Prinzip der umgekehrten Promotion, d.h. Alle Transaktionen werden optimistisch nacheinander ausgeführt, ohne dass sie sich gegenseitig erwarten. Sobald ein Fehler auftritt, tritt der Fehler viel später auf, einige Zeit nachdem die Transaktion im Speicher ausgeführt wurde. Wir stoppen unser Förderband und drehen es in die entgegengesetzte Richtung. Wir werfen alles raus, was die "schmutzigen" Daten tatsächlich gesehen haben und starten die Pipeline neu. Dies ist eine wahnsinnig teure Operation. Es kann 10.000 Transaktionen unter hoher Last verlieren, aber weil Es kommt äußerst selten vor (es kommt im Betrieb nie vor). Sie behalten lediglich den Speicherplatz im Auge.

    Naja, "nie" ist kategorisch, aber tatsächlich passiert es nicht, wenn Sie der Ausrüstung folgen. Dies ist ein Kostenaufwand. Im Allgemeinen müssen Sie beim Entwerfen eines Systems das wahrscheinlichste Szenario berücksichtigen. Wenn Sie versuchen, die Kosten für Architekturentscheidungen gleich hoch zu halten, listen Sie einfach auf: Was passiert, wenn ein Rollback stattfindet, was passiert, wenn ein Commit stattfindet, was passiert, wenn noch etwas anderes vorhanden ist? im schlimmsten Fall bewerte dich.

    So fixiert Nach diesen Grundsätzen wenden wir uns den technischen Aspekten zu. Was ich zum Engineering sagen möchte.



    Auf der Konferenz wird ein Bericht über die im Speicher befindliche Datenbank mit dem Namen ChronicleMap veröffentlicht, und ChronicleMap ist interessant, da die Entwickler dieses DBMS sich zum Ziel gesetzt haben, eine Wartezeit von Mikrosekunden für die Aktualisierung des DBMS zu erreichen. Die Aufgabe war vor allem, dass das Update viel weniger Zeit in Anspruch nahm. In unserem Fall ist die Situation etwas anders. Und wir entscheiden diesen Kompromiss zu einem anderen Vorteil. Worüber reden wir? Stellen Sie sich vor, Sie müssen zur Konferenz und es gibt keine Staus. Was werden Sie mitnehmen? Sie werden ein Taxi nehmen und es wird schneller sein. Sie werden öffentliche Verkehrsmittel benutzen - es wird billig sein. Warum sind öffentliche Verkehrsmittel günstig? Weil es für viele Teilnehmer wertvoll ist. Beförderung erfolgt, d.h. Sie teilen die Betriebskosten mit allen. Und in unserem Fall ist das Ziel genau das.

    Wenn andere DBMS die Aufgabe zum Beispiel so einstellen, dass sie eine sehr geringe Latenzzeit aufweist, möglicherweise jedoch keinen maximalen Durchsatz, d. H. Bandbreite In unserer Situation haben wir festgestellt, dass die Latenz, die der Arbeitsspeicher uns gewährt, für uns ausreicht. Beispielsweise sind es einige Millisekunden, um eine Anforderung zu verarbeiten. Dies ist der Parameter, den wir erreichen möchten, und für den Rest möchten wir den Durchsatz optimieren, d. H. Bandbreite. Wir stellen sicher, dass die maximale Anzahl von Anfragen die Kosten untereinander teilt. Was bedeutet das aus technischer Sicht?

    Wir haben ein langsames Netzwerk, und das Netzwerk ist im Wesentlichen teuer. Der Austausch ist teuer, da wir vor vierzig Jahren in der alten Welt der Betriebssysteme lebten und es keinen Weg gibt, online zu gehen, ohne den Kern zu betrachten. Wir haben eine Festplatte, die auch sehr teuer ist, die Festplattenaufzeichnung selbst ist langsam, aber wir müssen eine Festplatte beschreiben, da dies die einzige Möglichkeit ist, Daten zu speichern, damit sie einen Stromausfall überstehen. Wir haben auch einen Transaktionsprozessor, der in einem Thread arbeitet und Transaktionen nacheinander ausführt, d. H. Der Transaktionsprozessor ist unsere Pipeline. Wie können wir diesen Förderer minimal für uns stehen lassen?

    Wenn für jede Anforderung eine Pipeline vorhanden ist, wird sie an das Netzwerk gesendet und anschließend an die Festplatte gesendet. Mit größter Wahrscheinlichkeit muss sie jedoch zweimal ausgeführt werden, d. H. Er muss die Anforderung lesen, verarbeiten, auf die Festplatte schreiben, antworten und dem Client das Ergebnis mitteilen. Das heißt Wir greifen zweimal auf das Netzwerk zu, einmal pro Festplatte. All diese Katavasie wird sehr lange dauern. Wir müssen sicherstellen, dass wir in Bezug auf eine Anfrage so schnell wie möglich aus dem Netzwerk lesen - so billig wie möglich. Was machen wir dafür? Wir sagen, dass unser Protokoll vollständig asynchron ist, wir arbeiten im Pipelining-Modus, d.h. Wir können die Anforderungen vieler Clients von einer Verbindung aus lesen und gleichzeitig auf alle Clients antworten. Das heißt Jeder Kunde bekommt seine eigene Antwort, wir multiplexen dies alles auf einen Socket und wir haben Pipeling auf jeder Ebene, d. h. Pipelining auf jeder Arbeitsebene. Und dies ist ein sehr wichtiger Kompromiss, um den das DBMS aufgebaut ist. Aus diesem Grund arbeiten wir im selben Thread. Daher bieten wir eine geringere Latenz als einige andere Multitread-Lösungen, reduzieren jedoch die Kosten für eine Anforderung.



    Unter dem Gesichtspunkt der Umsetzung ist es notwendig, einen Weg zu finden, um das Paradigma, in dem wir existieren werden, zu parallelisieren, in dem wir alles parallelisieren werden. Ein solches Paradigma ist eines der folgenden.



    Wir müssen tatsächlich eine davon auswählen. Wenn wir sagen, dass wir konkurrierende Threads haben, wir irgendwie Informationen zwischen diesen Threads austauschen, müssen wir eine Austauschmethode auswählen.

    Warum ist das in unserem Fall besonders wichtig? Weil die Wahl der Austauschmethode zwischen Threads nicht nur diese Kosten beeinflusst, die mehr oder weniger offensichtlich sind - zum Kernel, zur Festplatte, zum Netzwerk, sondern auch solche impliziten Dinge, zum Beispiel, wie oft wir den Cache, den Cache des Prozessors, leeren. d.h. Funktionieren wir und der Cache gut oder schlecht? Und da dies implizit geschieht, handelt es sich tatsächlich um eine Suche im Nebel. Etwas hat sich geändert - der Cache hat etwas besser funktioniert, Ihre Produktivität hat sich leicht erhöht.

    In welcher Welt leben wir gerade? Zusätzlich zu diesem großen RAM, mit dem wir es zu tun haben, verfügen wir über 16 bis 32 MB Level-3-Cache, der von allen Kernen gemeinsam genutzt wird. Je effizienter wir mit dem Level-3-Cache beginnen, desto besser arbeiten wir . Unsere Aufgabe ist es daher, den 3rd-Level-Cache so zu gestalten, dass er wirklich funktioniert und effizient arbeitet.

    Jetzt haben wir eine solche Wahl (siehe Folie oben), und wenn wir über Paradigmen sprechen, sollten wir eine Art Paradigma wählen, in dem all dies kodiert ist.

    Mit Blick auf die Zukunft werde ich sagen, dass wir das letzte Paradigma gewählt haben - dies ist ein Schauspielermodell, warum?



    Was ist mit Schlössern? Ich habe mein ganzes bewusstes Leben mit Mutexen programmiert - ein großartiges Werkzeug. Eines der Hauptprobleme von Mutexen für eine effektive Programmierung ist das Problem der Zusammensetzbarkeit. Worüber reden wir? Stellen Sie sich vor, Sie haben einen kritischen Abschnitt, den Sie beispielsweise in eine wettbewerbsfähige Datenstruktur einfügen. Die Datenstruktur arbeitet mit einer Reihe von Threads. Nehmen Sie diesen kritischen Abschnitt und kapseln Sie ihn in eine Methode ein. Sie haben eine Einfügemethode in einer Art Wettbewerbsdatenstruktur. Als nächstes haben Sie eine bestimmte Makrostruktur, die diese Datenstruktur verwendet, und sie sollte auch in dem kritischen Abschnitt funktionieren, d. H. Sie muss auch wettbewerbsfähig sein. Locks erlauben es nicht, einfach eine Methode von einer anderen zu nehmen und aufzurufen, man muss über 10 Mal nachdenken, warum? Dies führt nicht zu Deadlocks oder anderen Problemen, die ich hier beschrieben habe. Wo kommt das alles her? Sie können einfach keinen willkürlichen Code verwenden, der Sperren voneinander verwendet. Sie verlieren die Hauptprogrammiereigenschaft, wenn wir Kapselungen ausführen und Probleme in kleinere zerlegen können. Tatsächlich lösen wartungsfreie Algorithmen ein Problem - das Deadlock-Problem. Wartefreie Algorithmen sind nicht blockiert, weil sie nicht warten. Aber sie lösen keine anderen Probleme? bezogen auf Algorithmen? gebaut um das Schlossmodell. Wenn wir kapseln können, zerlegen Sie die Probleme in kleinere. Tatsächlich lösen wartungsfreie Algorithmen ein Problem - das Deadlock-Problem. Wartefreie Algorithmen sind nicht blockiert, weil sie nicht warten. Aber sie lösen keine anderen Probleme? bezogen auf Algorithmen? gebaut um das Schlossmodell. Wenn wir kapseln können, zerlegen Sie die Probleme in kleinere. Tatsächlich lösen wartungsfreie Algorithmen ein Problem - das Deadlock-Problem. Wartefreie Algorithmen sind nicht blockiert, weil sie nicht warten. Aber sie lösen keine anderen Probleme? bezogen auf Algorithmen? gebaut um das Schlossmodell.



    Deadlock ist ein Wartezyklus. Wir benutzen Sperren in der Reihenfolge A, B von einer Stelle im Code, wir benutzen Sperren in der Reihenfolge B und A. von einer anderen Stelle im Code. Und unter Last brach all dies zusammen - Deadlock.

    Was sind Escorts und Hotspots? Dies gilt auch für wartefreie Algorithmen. Was ist das Problem? Sie haben Ihr Programm unter der Annahme geschrieben, dass dieser wichtige Abschnitt mit zwei Threads arbeitet. Zum Beispiel hat sie einen Producer-Thread, einen Consumer-Thread, diese Threads wechseln durchschnittlich zu diesem kritischen Abschnitt ... Angenommen, sie haben eine Last von 1000 Anfragen pro Sekunde. Dementsprechend wenden sie sich 1000 Mal pro Sekunde dem kritischen Bereich zu - alles funktioniert für Sie. Dann ändern sich Ihre Umstände. Die Hardware ändert sich oder die Arbeit, die die Threads ausführen, ändert sich oder die Umgebung, mit der sie arbeiten, ändert sich, d. H. Sie haben immer noch das Unbekannte in diesem System. Wir sprechen über die Zusammensetzbarkeit, d.h. Sie beginnen, das System zu erweitern und zu optimieren, und Ihr kritischer Bereich wird plötzlich heiß. Sagen wir eine kleine Sache Das unter dem kritischen Abschnitt aktualisiert tatsächlich zwei Variablen, aber es beginnt zu zittern, nicht 1000-mal pro Sekunde, wie Sie es geplant haben, sondern 10.000-mal pro Sekunde, 100.000-mal pro Sekunde, und es gibt einen ständigen Kampf darum, Threads werden aus der Steuerung entfernt usw. . Was könnte als nächstes passieren?

    Sie können versuchen, mit Prioritäten oder der Reihenfolge zu spielen, d. H. Sie sagen, dass einige Anfragen mehr Priorität haben, andere weniger. Dies kann dazu führen, dass Anforderungen mit höherer Priorität für den kritischen Abschnitt Anforderungen mit niedrigerer Priorität zu ersetzen beginnen. Weniger Priorität nie erfüllt - das ist Hunger.

    Convoying ist genau die Situation, in der ein kleiner kritischer Abschnitt in einen großen Abschnitt eingebettet ist und Sie daher nicht in einen kleinen kritischen Abschnitt durchbrechen können.

    Es gibt viele verschiedene Situationen, die auf die eine oder andere Weise in einer Schlussfolgerung zum Ausdruck kommen - Sperren sind nicht zusammengesetzt. Das System besteht aus Sperren, und wenn dies das Hauptelement der Programmierung ist, können daraus keine skalierbaren Systeme erstellt werden.

    Das war nicht nur mir klar, sondern auch den Machern von Erlang, die es vor 30-40 Jahren geschafft haben. Wenn wir über das Tool sprechen, auf dem Tarantool geschrieben werden soll, wird dieses Tool im Großen und Ganzen wahrscheinlich Erlang genannt.



    Im Allgemeinen ist ein Ansatz, der das Problem der Zusammensetzbarkeit lösen kann, ein Ansatz der funktionalen Programmierung, bei dem kritische Abschnitte nicht explizit definiert werden und während der Ausführung Parallelitäten basierend auf funktionalen Abhängigkeiten bestimmt werden. Mit anderen Worten, Sie nehmen nirgendwo Sperren vor, aber wenn Sie dieselbe Funktion haben, ist sie funktional von einer anderen abhängig, und Sie können ihre Ausführung für den Autor transparent parallelisieren.

    Dies wird von allen Arten von funktionalen Sprachen verwendet, die dies ziemlich gut können. Sie haben keine gemeinsamen Daten und daher keine Konflikte um gemeinsame Daten, d. H. funktionale Programmierung scheint geeignet zu sein.

    Aber leider, wenn wir über Systemprogrammierung sprechen, d.h. Um eine funktionale Herangehensweise und Systemprogrammierung zu vereinbaren, haben wir keine Umgebung, auf die wir uns verlassen können.

    So kommen wir zu dem Modell, das ich am Anfang verwöhnt habe, und genau hierauf müssen wir uns konzentrieren, damit wir ein komplexes System erstellen und es billig machen können.



    Was macht das Actor-Modell attraktiv, d.h. unabhängiges Messaging-Modell? Wir haben ein Single-Thread-System, in diesem System gibt es bereits kooperatives Multitasking, d.h. Auf der Ebene eines Threads haben wir Mikroflows erstellt, die linear ausgeführt werden. Sie können miteinander wie über den gemeinsamen Speicher interagieren, da es dort keine Probleme gibt. Sie können jedoch auch durch das Senden von Nachrichten miteinander interagieren.

    Es bleibt für uns, das Problem für die Interaktion zwischen Threads zu lösen. Kehren wir zum Bild „Mass Messaging System“ zurück:



    У нас есть Network тред, Transaction Processor тред, Write Ahead Logging тред и для каждого запроса в каждом треде концептуально есть какая-то сущность – actor, актер. Задача актера в network треде – взять запрос, распарсить его, проанализировать его корректность и отправить сообщение «выполни этот запрос» Transaction processor’у. Transaction processor берет запрос, проверяет нет ли там duplicate key, нет ли там каких-то еще constraint violation, выполняет какие-то триггеры, вставляет его везде, и говорит: «Ок» соответствующему ему бади в write ahead log – запиши этот запрос на диск. Он берет запрос и записывает на диск.

    Im wahrsten Sinne des Wortes würden wir bei jeder Anfrage Nachrichten austauschen. Wir wollen das reduzieren, d.h. In diesem Paradigma möchten wir wirklich, dass die Entitäten in unserem Programm Nachrichten austauschen, aber die Kosten für diesen Austausch sind minimal, d. h. Wir brauchen einen Weg, um den Austausch zu multiplexen. Aufgrund der Tatsache, dass das Actor-Modell den Nachrichtenaustausch kapselt, können Nachrichten stapelweise gesendet werden. Das heißt Nehmen wir das Actor-Modell, sagen wir, dass Sie, um etwas zu tun, Nachrichten zwischen den entsprechenden Actors in verschiedenen Threads senden müssen. Jedes Mal, wenn eine Nachricht gesendet wird, werden wir den entsprechenden Actor fälschen, d. h. . Entfernen Sie es von der Steuerung und übertragen Sie die Steuerung auf den nächsten Akteur. So arbeiten wir ständig auf der Basis von Corutin in jedem Thread,

    Warum ist das ein zentrales Thema für mich? Ich habe sogar einen schönen Hypercube auf die Folie „Actor Model“ gezeichnet (siehe oben), in der ich versuche, die Bedeutung eines solchen Paradigmas hervorzuheben. Was ist die Eigenschaft eines Hyperwürfels? Die Tatsache, dass die Anzahl der Bindungen dort proportional zur Anzahl der Knoten wächst, d.h. nicht quadratisch, sondern proportional.

    Wenn Sie Tarantool verwenden, können die Scheitelpunkte in diesem Hypercube als separate Threads betrachtet werden. Wir möchten die Verbindung zwischen Threads niedrig halten, damit wir Verknüpfungen zwischen Threads über Verknüpfungen zwischen Scheitelpunkten herstellen. Und unsere Aufgabe ist es, eine geringe Anzahl von Verbindungen aufrechtzuerhalten, damit der Austausch billig ist.

    Wenn man sich an einige alte Supercomputer wie Kreia erinnert und sich das Design anschaut, stellt sich heraus, dass sie tatsächlich nach dem Prinzip der Hyperwürfel gebaut wurden. Wenn Sie sich gewöhnliche mechanische Telefonvermittlungsstellen ansehen, versuchen sie im Allgemeinen, dasselbe Problem zu lösen - wie man das Multiplexen vieler interagierender Einheiten in unseren dreidimensionalen Raum einfügt und es effektiv macht. Dies stellt sich als eine Art räumliches Denken heraus und nicht als Ingenieurwesen.

    Warum wird ein 4-dimensionaler Hyperwürfel gezeichnet? Ich habe nur über einen Thread und eine Interaktion in einem Thread gesprochen, aber beim Sharding tritt das gleiche Problem auf: Die Anforderung geht an einen beliebigen Knoten im Cluster, und dieser Knoten muss mit allen Knoten interagieren, um diese Anforderung zu verarbeiten. Wir haben das gleiche Problem des quadratischen Wachstums der Anzahl von Anleihen, d.h. Wir haben n Quadrat Links von der Anzahl der Teilnehmer. Und die einzige Möglichkeit, die Anzahl der Verbindungen zu steuern, besteht darin, sie irgendwie in einen solchen Raum zu treiben.

    Warum ist dieses Modell aus Sicht eines modernen Systems gut? Wenn Sie einen typischen Chip nehmen, ist dieses kleine Ding in der Mitte ein Level-3-Cache:



    Sehr unterhaltsam in diesem Sinne ist der Streit zwischen Fans von CISC- und RISC-Architekturen im Jahr 2015. Ich stehe für ARM-Prozessoren mit beiden Händen - sie haben die beste Energieeinsparung usw., aber das Argument über Architekturen bringt mich zum Lachen, denn die moderne CPU ist im Großen und Ganzen ein riesiger Cache der 3. Ebene, alles andere macht 15% aus Chip. Die Debatte darüber, welcher Prozessor in dieser Geschichte effizienter ist - derjenige, der mit Level-3-Cache arbeitet, ist besser, ist effektiv.



    Warum eignet sich das Actor-Modell auch für modernes Eisen? Wenn Sie sich den Zugriff auf den Level 3-Cache ansehen, ist es umso besser, je weniger wir dort sind. Jedes Mal, wenn wir gezwungen sind, eine Nachricht zu senden, d. H. Um die beiden Wettbewerbsprozesse zu synchronisieren, müssen wir diesen Austauschbus irgendwie blockieren, um die Datenkonsistenz sicherzustellen. Beispielsweise ändern Sie in Intel Daten in einem Prozess, und sie ändern sich schließlich in allen. Daher ist es für uns am besten, gemeinsam genutzte Daten nur selten zu ändern. Die Idee beim Messaging-Multiplexing ist genau das: Um diese Kosten zu teilen, sperren Sie den Austauschbus 1.000 bis 10.000 Mal pro Sekunde. Dies ist eine normale Leistung, die uns eine akzeptable Latenz von 1 bis 2 ms für die Verarbeitung einer Anfrage bietet und somit die Austauschkosten senkt.

    Teil 3 ist dem Gedächtnis gewidmet, dennoch sind wir ein DBMS im Gedächtnis, und wir sollten dem Gedächtnis viel Aufmerksamkeit widmen.



    Warum waren Teile 1 und 2? Ich habe versucht zu zeigen, wie wir vom gesamten Lösungsraum auf eine niedrigere Ebene absteigen.

    Jetzt haben wir das Problem für uns vereinfacht - wir haben keine Wettbewerbsfähigkeit, wir haben ein Gedächtnis, das ein Thread verarbeiten muss. Es gibt keinen gemeinsamen Speicher für Threads. Der gesamte Austausch zwischen Threads erfolgt über Messaging.

    Was ist als nächstes zu tun? Wie macht man die Arbeit mit Speicher effektiv in einem Thread?

    Auf der Folie habe ich gezeigt, wofür der klassische Manager nicht geeignet ist. Angenommen, wir haben unsere eigenen, welche Anforderungen haben wir dafür?



    Unsere besonderen Anforderungen sind vor allem die Unterstützung von Quoten. Wir garantieren dem Nutzer, dass wir nicht über den uns zugewiesenen Speicher hinausgehen. Wenn ein Fehler auftritt, stellt sich häufig die Frage: "Absturz bei Speichermangel?". Wir können, wenn der Code fehlerhaft ist, aber im Allgemeinen, wenn der Speicher nicht mehr ausreicht, das System das Speichern von Daten beenden, aber weiterarbeiten und aktuelle Daten bereitstellen. Dies ist eines der Ziele.

    Das zweite Ziel. Es gibt so etwas wie eine Verdichtung des Magazins. Wir müssen regelmäßig alle unsere Schnappschüsse auf die Festplatte und den gesamten Speicher spülen, um die Wiederherstellung zu beschleunigen, d. H. Dafür benötigen wir konsistente Speicher-Snapshots. Darüber hinaus benötigen wir konsistente Bilder, wenn wir die sogenannten interaktiven Transaktionen unterstützen möchten, d. H. Die auf dem Client gestartete Transaktion funktioniert. Wenn wir die klassische Multiversion-Parallelitätskontrolle durchführen möchten, benötigen wir auch konsistente Images.



    Die Speicherzuordnungen in diesem einzelnen Thread sind in einer bestimmten Hierarchie angeordnet, und die Hierarchie-Eckpunkte sind ein Speicheranbieter einer niedrigeren Ebene. Unser Ansatz ist, dass wir versuchen, so wenig wie möglich zu kapseln, wenn wir mit Speicher arbeiten, d. H. Wir stellen dem DBMS-Programmierer eine Reihe von Werkzeugen zur Verfügung, die für die jeweiligen Situationen geeignet sind. An der Spitze der Hierarchie steht ein globales Objekt. Im Prinzip kann es viele davon geben. Wir haben jetzt zwei davon - Speicher (Kontingent) für Daten und ein Kontingent für die Laufzeit.

    Das Kontingent für die Laufzeit ist jetzt nicht begrenzt, es kann jedoch festgelegt werden. Das globale Objekt an der Spitze der Hierarchie ist das Kontingent. Ein Kontingent ist ein sehr einfaches Objekt, in dem zwei Mengen gespeichert werden - das für Benutzer zulässige Volumen und das aktuell verbrauchte Volumen. Dies ist ein Wettbewerbsobjekt, das zwischen diesen drei Threads aufgeteilt wird.

    Der Quotennutzer ist die sogenannte Arena. Die Arena sieht folgendermaßen aus:



    Tatsächlich handelt es sich um einen Speichermanager, der nur mit sehr großen Speicherbereichen von 4 MB arbeiten kann. In diesem Fall besteht die Aufgabe der Arena darin, Speicher auf niedrigeren Ebenen bereitzustellen. Die Arena ist so konzipiert, dass Sie auch mit einer Vielzahl von Themen arbeiten können, d. H. Eine Arena kann eine Speicherquelle für viele Threads sein. Sie ist wettbewerbsfähig. Darüber hinaus ist die Hauptfunktion, die ausgeführt wird, die Adressraumverwaltung. Wir möchten, dass der Adressraum ausgerichtet und nicht fragmentiert wird. Wenn wir also anfangen, werden wir eine bestimmte Menge an Adressraum zuweisen, aber wir können auch über dieses zugewiesene Volumen hinausgehen, wenn das Kontingent nach dem Start erhöht wurde.

    Die nächste Ebene (und dies ist die erste Ebene, die auf der Ebene jedes Threads funktioniert) ist der Slab-Cache. Die Arena kann nur mit Platten der gleichen Größe betrieben werden. Dies ist die maximale Größe. Bei uns hängt eine Variable wie die maximale Datenmenge, die Sie in das System eingeben können, von der Größe der Arena ab. Das heißt Wenn Ihre Kapelle 8 MB benötigt, müssen Sie diese Zahl erhöhen. Die derzeitige Einschränkung ist nicht sehr schön, ich werde Ihnen sagen, wie wir sie entfernen werden.



    Häufig werden solche großen Speicherbereiche nicht benötigt, während für einige Low-Level-Allokatoren kleine Teile benötigt werden. Dazu haben wir einen lokalen Thread-Allokator, der slab_cache aufruft und auf dem sogenannten Buddy-System funktioniert.

    Das Buddy-Allokator-Prinzip lautet wie folgt. Während der Zuweisung ist das Problem der Speicherfragmentierung ein sehr ernstes Problem, nachdem wir eine Menge Speicher zugewiesen und dann freigegeben haben, d. H. Wir haben teilweise Stücke gefüllt. Angenommen, hier ist unsere große 4-MB-Platte, die wir gerade verwenden. Buddy slab_cache kann im Standardfall nur Teile mit einer Zweierpotenz von 2 kb bis 4 mb zurückgeben. Sein Vorteil ist, dass, wenn Sie das Stück zurückbringen, d.h. du hast es benutzt und zurückgegeben, er weiß, wie er seinen Nachbarn findet - Kumpel. Wenn der Nachbar ebenfalls frei ist, kombiniert er zwei Nachbarn, d.h. Er kann billig Speicher finden und defragmentieren, nachdem die Zuordnung aufgehoben wurde. In der Regel bleibt Ihr Speicher also lange Zeit defragmentiert, da bei der Arbeit mit dem Slab-Cache

    Ein wichtiger Punkt, der dabei hilft, ist, dass wir Adressen im unteren Bereich des Adressraums bei der Zuweisung bevorzugen, d. H. Bei der allgemeinen Zuweisung von Adressen auf allen Ebenen versuchen wir, die erste freie Adresse zu finden. Wenn Ihr System lange genug funktioniert hat, nachdem es eine Art Speicher freigegeben hat, beginnt es, den Speicher erneut zuzuweisen. Wir versuchen, die Daten im Adressraum nach unten zu verschieben. Dies löst auch Fragmentierungsprobleme.



    Der untergeordnete Allokator ist der klassische Pool-Allokator - ein Objektpool, der einfach Objekte aus dem Slab-Cache entnimmt, Slabs, z. B. 2 KB, 4 KB, diese Slabs platziert und Objekte derselben Größe ohne zusätzlichen Aufwand zuweisen kann . Die Hauptbeschränkung besteht darin, dass es nicht weiß, wie Objekte unterschiedlicher Größe zugeordnet werden.

    Angenommen, wir haben ein Verbindungsobjekt oder ein Glasfaserobjekt oder ein Benutzerobjekt, das heiß genug ist - sie werden häufig loyalisiert und freigegeben. Wir möchten, dass die Zuordnung solcher Objekte mit der Zuordnung auf dem Stapel vergleichbar ist, und verwenden dafür dedizierte Mempools. Es ist nicht immer möglich, mit einem dedizierten Mempool auszukommen, da das System nicht immer so ist, dass wir die Größe des Objekts im Voraus kennen.



    Und speziell für die Daten verwenden wir den klassischen Plattenverteiler, der auf mempool'e basiert, aber tatsächlich wird er ziemlich unterhaltsam gezogen. In der klassischen Plattenzuordnung ist die Größe des Objekts während der Aufhebung der Zuordnung nicht bekannt. Wir haben keine solche Einschränkung, wir kennen die Größe der Daten, die wir bereitstellen. Aus diesem Grund können wir Platten unterschiedlicher Größe für unterschiedliche Objektgrößen verwenden. Schauen Sie sich das Bild an - es gibt Objekte mit einer Größe von 24 Byte oder bis zu 24 Byte - für sie verwenden wir beispielsweise 4-KB-Platten. Objekte der Größe 32 sind immer noch 4 Kb-Platten, 40 sind immer noch 4 Kb-Platten, 48 - wir verwenden bereits 8 Kb-Platten. Daher können wir viele dieser Mapping-Größen haben, die keinen Speicher verschlingen.

    Das klassische Problem bei einem normalen Plattenverteiler ist, dass für jede Größe mindestens eine Platte erstellt werden muss. Das heißt Wenn Sie beispielsweise 200 Größen haben, dann haben Sie eine Platte von 4 MB, Sie haben ein Objekt in jeder Größe bereitgestellt - Sie haben bereits eine Feige! - 800 MB im Speicher werden von etwas belegt, aber es ist nicht belegt, es wurde verwendet. Dann skaliert dieses System, aber insgesamt ist es keine gute Geschichte. Daher handelt es sich normalerweise bei klassischen Plattenzuordnern um Kompromisse zwischen der Fragmentierung interner und externer Platten - wie viele Größen zu erhalten sind - viel oder wenig. Wir haben viel weniger Kompromisse, wir können es uns leisten, alle 8 Bytes einen Wachstumsschritt zu machen, d.h. Es gibt praktisch keine interne Fragmentierung. Für jeweils 8 Bytes haben wir eine eigene Platte.

    Als nächstes haben wir die Bibliothek unabhängig von Tarantool verfügbar gemacht. Ihre URL istgithub.com/tarantool/small , bitte sieh dir die codes an, es ist sehr klein, was auch meiner meinung nach ein vorteil ist. Es ist in sich selbst enthalten und alles, was ich hier unterschätzt habe, kann man einfach rtfs.



    Welche andere Art der Zuordnung gibt es? Wir haben einen wunderbaren Allokator, der nicht freigegeben werden kann. Sehr schön, denken Sie nicht darüber nach - Sie reservieren Speicher und alles. Tatsächlich können Sie einfach den gesamten Speicher freigeben, der jemals in diesem Allokator zugewiesen wurde - dies wird Regionsallokator genannt, regional, d. H. Es funktioniert nach dem Prinzip des Obj-Stacks. JCC hat viele ähnliche Allokatoren in verschiedenen Systemen, einschließlich Open Source. Ein wichtiger Vorteil von uns ist, dass alles in einer einzigen Hierarchie aufgebaut ist. Das heißt Der Regionszuordner verwendet den Plattencache auch als Provider für seine Platten.

    Warum kann man keine so gute String-Klasse schreiben, warum schreibt jeder Programmierer seine eigene String-Klasse? Da viele Aspekte zusammengeführt werden: Der Aspekt des Arbeitens mit dem Gedächtnis ist einer der wichtigsten Aspekte das Kopieren, die Semantik des Kopierens, der Aspekt des Arbeitens mit Zeichen usw. Das heißt Viele Probleme werden in einer Klasse gelöst. Wenn Sie ein solches universelles Werkzeug herstellen, können Sie es natürlich nicht für alle Fälle ideal machen.

    Wenn wir diese ganze Geschichte ausschließlich unter dem Gesichtspunkt der Speicherzuordnung betrachten, wie ist dann die Zeile oder ist es nur so, dass sich der Puffer vom Allokator unterscheidet? Ja nichts Wie unterscheidet sich ein Allokator von einem Container? Der Container hat eine Iteration, aus irgendeinem Grund hat der Allokator keine Iteration. Mit unseren Allokatoren können Sie Objekte durchlaufen. Wo liegt das Problem? Wir wissen, welche Objekte zugeordnet sind und welche nicht. Ein Allokator ist ein Container, eine Allokatorregion eine Zeichenfolge. Dies ist ein dynamisch wachsender Puffer. Und in diesem Sinne, wenn wir über Allokationsstrategien sprechen, ist ihre mehr oder weniger endliche Zahl, d.h. Wenn Ihre Leitung voll ist, können Sie die Größe des zugewiesenen Puffers verdoppeln oder so etwas wie ein Seil verwenden, d. h. Ihre Zeichenfolge kann aus Segmenten bestehen. Oder Sie können sich nie die Mühe machen, Speicherplatz freizugeben - kopieren Sie den Speicher einfach an einen neuen Speicherort und geben Sie sich damit zufrieden. Dies ist, was Reallock macht - es stellt sich heraus, dass "ich immer noch einen Schwanz habe, der ein defragmentierter Overhead ist und den ich verwenden kann, und ich werde keinen Verkauf tätigen." Das heißt Sie haben eine feste Anzahl von Strategien. Und für diese feste Anzahl von Strategien für die Arbeit mit Puffern haben wir nur drei Strukturen erstellt. Dies geschieht alles in C, das diese Strategien implementiert, d.h. verdoppeln mit Wachstum, Segmenten und einfach an einen neuen Ort kopieren. Und für diese feste Anzahl von Strategien für die Arbeit mit Puffern haben wir nur drei Strukturen erstellt. Dies geschieht alles in C, das diese Strategien implementiert, d.h. verdoppeln mit Wachstum, Segmenten und einfach an einen neuen Ort kopieren. Und für diese feste Anzahl von Strategien für die Arbeit mit Puffern haben wir nur drei Strukturen erstellt. Dies geschieht alles in C, das diese Strategien implementiert, d.h. verdoppeln mit Wachstum, Segmenten und einfach an einen neuen Ort kopieren.

    Wir haben also eine solche Grundlage. Auf dieser Grundlage können wir Strukturen aufbauen, in denen wir Daten speichern und mit dem vierten Teil unseres Berichts fortfahren. Das wütendste Highlight ist, wie Sie sehen, vorhanden. Worüber werden wir hier sprechen?



    Es gibt eine Datenstruktur, die sich an der Grenze zwischen Container, Allokator und Baum befindet - aus irgendeinem Grund wird diese Datenstruktur als Matratze bezeichnet. Warum eine Matratze? Dies ist eine so listige Abkürzung (Sie werden sehen, dass wir auf so etwas gierig sind). Das System selbst heißt klein - das ist eine kleine Objektzuordnung. Eine Matratze ist eine Speicheradressübersetzung. Das heißt eine matratze ist so ein benutzerraum tlb. Dies ist eine Art System, das Speicher zuweist und Adressen in einen 32-Bit-Raum übersetzt. Darüber hinaus haben wir, was wichtig ist, wenn wir nur einen Übersetzer hätten, relativ gesehen eine 8-Byte-Adresse, und wir möchten ihr 32-Bit-Bezeichner geben. Wir müssen diese Zuordnung zwangsläufig irgendwo speichern, wir müssen Adressen irgendwo speichern. Wir verwenden zusätzlichen Speicher. Wir werden es auf Kosten der Matratze los. Die Matratze ist auch ein Allokator, und Broadcast-System. Es ordnet ein Objekt zu, das in der Größe ausgerichtet werden muss. Es kann entweder 16 Bytes oder 32 oder 64 sein. - Muss eine Zweierpotenz sein. Und gibt seinen 32-Bit-Bezeichner zurück. Wie arbeitet er

    Tatsächlich ist dies ein Baum mit drei Ebenen. In der ersten Ebene gibt es einen Wurzelblock und in dem Wurzelblock sind Zeiger auf den Umfang der ersten Ebene gespeichert. Die Gesamtzahl solcher Extent'ov ist 2048, weil wir die ersten 11 Bits einer 32-Bit-Zahl für die Adressierung im Root-Block verwenden. Einstieg in die Ausdehnung, d.h. bis zur zweiten Ebene des Baumes bestimmen wir den Ort, an dem unsere Adresse speziell gespeichert ist - hierfür unser Gedächtnis, d. h. Hierfür verwenden wir die zweiten 11 Bits der Adresse. Dies ermöglicht es uns, noch tiefer zu springen, und an diesem bestimmten Ort befindet sich unser Gedächtnis, d.h. Es gibt keinen Zeiger, sondern den zugewiesenen Speicher.

    Bei der Freigabe arbeiten wir mit diesem System als klassischer Baum, d.h. Wir haben eine Liste der freien Objekte. Tatsächlich findet die endgültige Freigabe hier nie statt, aber natürlich freigegebene Blöcke werden zu freien Blättern hinzugefügt und können jederzeit wiederverwendet werden. Die Leistung einer solchen Datenstruktur beträgt 10 Millionen Operationen pro Sekunde auf mehr oder weniger durchschnittlichen Geräten. Aus diesem Grund kämpfen wir so für eine gute Arbeit mit Caches, weil wir wollen, dass so etwas vollständig in den L-3-Cache passt, dann wird es effizient funktionieren.

    Какое еще важное свойство у этой системы? Мы сделали ее многоверсионной, т.е. есть возможность поддерживать несколько версий одной и той же структуры данных. Для того чтобы сделать снепшот, мы можем заморозить матрас. Вы пробовали морозить ваш матрас? Мы замораживаем структуру данных, все обновления происходят с новой ее версией, мы замораживаем ее по классическому принципу многоверсионных деревьев – когда нам идет обращение на изменение к какому-то extent’у матраса, мы делаем копию, у нас copy on write классический при заморозке. После того, как происходит разморозка, т.е. мы сделали снепшот, мы добавляем размороженные сегменты в free лист и все. И начинаем ее повторно использовать. Возвращаясь, мы замораживаем эту структуру данных, получаем консистентную итерацию по всей памяти, которая была через нее аллоцирована.

    Was ist hier wichtig? In dieser Struktur ordnen wir bereits Objekte unserer Indizes zu, d.h. Unsere Indizes sind so angeordnet, dass sie immer über die Matratze vergeben werden. Wir werden gefragt, wie viel schneller ist Tarantool std :: map? Im Allgemeinen, schneller, erzähle ich Ihnen davon. Aber es ist wichtig, dass wir durch dieses Ding auch besser skalieren als std :: map.



    Wenn Sie sich an diese langwierige Geschichte über Mehrebenen-Allokatoren erinnern, können wir diese Matratze als Konzept verwerfen (wir werden dies in Version 1.7 tun), um zumindest alle Daten dieser Hierarchie und diesen gesamten Platten-Allokator als Ganzes zu speichern. Denn wenn es möglich ist, Adressen zu senden, d.h. Wenn Sie Adressen im laufenden Betrieb ändern, können Sie einfach einen Allokator basierend auf der Speicherbereinigung erstellen, die speziell auf unsere Datenanforderungen zugeschnitten ist.

    Wie kann ein solcher Allokator eingerichtet werden? Stellen Sie sich vor, dass Ihre Zuordnung auf dem Protokollprinzip basiert, d. H. Für Sie ist die Zuordnung nur ein Eintrag in einem endlosen Tagebuch. Sie passiert immer am Ende der Zeitschrift. Sie weisen immer zu und fügen am Ende Folgendes hinzu: nahm 10 Bytes - fein, nahm 15 - fein, Sie haben keinen Overhead, keine Fragmentierung, Sie haben immer das Maximum, das Sie zum Ausrichten der Wortgrenzen benötigen, Sie haben keine andere Fragmentierung. Das Magazin ist komplett kompakt. Wunderschön.

    Was tun, wenn Speicher freigegeben wird? Der Speicher wird freigegeben, was bedeutet, dass irgendwo ein Teil des Protokolls fragmentiert wird, d.h. Es gibt sowohl fleißige als auch befreite Stücke. Was kann getan werden? Sie können das am meisten defragmentierte Ausmaß nehmen und es vollständig umschreiben, es vollständig bis zum Ende kopieren, den gesamten freien Platz wegwerfen, alle freigegebenen Blöcke wegwerfen, die belegten Blöcke bis zum Ende werfen, die Adressen in der Matratze ersetzen - alles funktioniert.

    Wir haben bereits einen Prototyp von so etwas erstellt, leider funktioniert es in der Praxis langsamer als die manuelle Verwaltung des Speichers, aber das Schöne daran ist, dass es überhaupt keine Stifte gibt Wir haben jetzt einen Plattenverteiler, den der Benutzer drehen muss. Hier haben Sie keine Fragmentierung, der maximale Handle für den Benutzer, den wir in dieser Situation geben können, ist, wie aktiv wir den alten Speicher defragmentieren möchten. Wir werden es tun. Damit die Matratze eine grundlegende Sache in der Architektur ist, werden wir auf ihrer Basis weitere Strukturen aufbauen.

    Was haben wir schon gebaut?



    Bevor ich über unsere Hashes spreche, lassen Sie uns über klassische Hashes sprechen. Was ist typisch für einen unerfahrenen Webprogrammierer? Wir alle wissen, dass ein Hash die schnellste Datenstruktur ist - er hat asymptotisch konstante Suchkosten. Großartig, wir fangen an, den Hash für absolut alles zu verwenden. Wir archivieren unser kleines System, es geht in Produktion und dann suchen wir nach Hexen. Hexen in Form solcher Reaktionszeitsprünge, die einmal am Tag, einmal alle zwei, einmal pro Woche auftreten, wenn eine Putzfrau Blumen einschenkt, wissen wir nicht, woher sie kommen, warum sie bei unseren Tests nicht auftreten? Wir können dieses System nicht modellieren, sie kommen nur in der Produktion vor.

    Ich spreche mit solchem ​​Sarkasmus darüber, weil ich das in meinem Leben wiederholt gesehen habe, als ein C ++ - Programmierer einen Hash nimmt und zum Beispiel alle Benutzer darin speichert. Am Abend werden dann Personen zur Site hinzugefügt, die Anzahl der Benutzer nimmt zu, und die Größe des Hash wird geändert. Während die Größe des Hashs geändert wird, raucht jeder, jeder wartet, wir sehen es in der Grafik so, also sind klassische Hashes einfach nicht für ein DBMS geeignet, denn wenn Sie eine große Datenmenge haben, können Sie es sich nicht leisten, die Größe zu ändern.



    Hier kommen wir zu der wütendsten Geschichte in der gesamten Präsentation - genau wie unser Hash mit linearem Wachstum funktioniert. Das heißt Unser Hash wird niemals in der Größe verändert. Genauer gesagt, die Größe wird immer und für jede Einfügung geändert. Wie funktioniert es

    Zunächst ist das zugrunde liegende Hash-Objekt eine 16-Byte-Struktur. Der Wert von 8 Bytes ist entweder ein Schlüssel oder ein Zeiger auf Daten, und zwei 32-Bit-Zahlen sind ein Hash vom Schlüssel und ein Zeiger auf das nächste Element. Es wird oben rechts auf der Folie erstellt.

    Weiterhin ist der Schlüsselparameter des Hash die Maske. Eine Maske ist die Zweierpotenz, die die aktuelle Größe abdeckt. Das heißt Wenn wir die aktuelle Hash-Größe haben, die jetzt 3 Elemente hat, ist die Maske 4, wenn der Hash 4 Elemente hat, sind 4, 5 Elemente Maske 8. Somit haben wir eine virtuelle Hash-Größe. Die Größe des virtuellen Hashs wird klassisch geändert, dies ist jedoch nur eine Zahl. Tatsächlich haben wir dieses Verzeichnis nicht mit einer Hash-Tabelle. Bei jedem Einfügen wird dem Hash 1 Element hinzugefügt.

    Еще важный элемент – есть указатель на текущий бакет, который можно ресайзить. Допустим, у нас количество элементов в хэше – 2, указателем на текущий бакет будет 0. Мы добавили новый элемент, мы при этом делаем сплит нулевому бакету и передвигаем указатель на следующий, мы добавляем следующий элемент, мы делаем сплит первому бакету, и у нас появляется 4 бакета, и мы рестартуем наш счетчик ресайза, у нас 4 бакета – счетчик ресайза находится на нулевом бакете. Добавляем 5-ый элемент, снова сплитаем нулевой бакет. У нас появляется 5 элементов, нулевой бакет засплитан, маска равна 8-ми. Таким образом, добавляем элементы, доходим до 4-х, снова расплитали первые 4 элемента, у нас появилось 8 элементов. Так переустанавливаем счетчик на 0 снова, есть указатель на текущий бакет, которым будем сплитать при вставке, и каждая вставка приводит к сплиту.

    Дальше может произойти следующая вещь – мы можем попасть при вставке на оверфлоу, т.е. мы можем попасть на оверфлоу чейн, т.е. на коллизионную цепочку. Мы можем при вставке попасть ровно на тот бакет, который мы ресайзим – тогда все вообще хорошо, мы просто вставляем новое значение по биту, либо мы можем попасть в бакет, который мы не ресайзим при хэшировании, но у нас есть гарантия, что у нас есть место куда вставить. При каждой вставке мы добавляем 1 элемент.

    Еще на всю эту систему можно посмотреть следующим образом: этот cоver или маска определяет значимые биты в хэше, которые учитываются при положении значения в хэше. Когда мы ее удваиваем, у нас следующий бит становится значимым, и мы ресайзим, постепенно учитывая этот значимый бит.

    Suchen Sie in der Literatur nach "linearem Hashing für zweistufigen Speicher für eine Festplatte". Sie finden eine ziemlich klare Erklärung. Ich habe dieses System zum ersten Mal kennengelernt, als ich in MySQL gearbeitet habe, und wir haben es Monty Hash genannt, weil der Hash auf diese Weise in MySQL erstellt wurde. Und wir haben es lange gebraucht.

    Was ist der Hauptpunkt? Stellen Sie sicher, dass die Kosten für die Größenänderung der Hash-Tabellen gleichmäßig verteilt sind und die Gesamtleistung nicht beeinträchtigen.



    Unsere Bäume sind auch etwas Besonderes. Was ist das Besondere an ihnen? Tarantool 1.3 und 1.4 verwendeten klassische Bäume als RAM und sie sind ziemlich gut, aber was ist mit dem klassischen Baum falsch? Zwei Dinge: Der erste ist ein Overhead für einen Zeiger, jeder Scheitelpunkt hat zwei Zeiger, was zu teuer ist. 16 Byte für einen Wert auszugeben, den wir in einem Baum speichern, ist teuer, das wollen wir nicht. Der zweite ist das Gleichgewicht. Sogar die AVL-Bäume sind ziemlich ausgeglichen, aber verglichen mit dem B-Baum, den ich später erörtern werde, ist das Gleichgewicht unbefriedigend, ich zeige dann die Zahlen - das Gleichgewicht ist unzureichend, d.h. Sie können das Gleichgewicht erheblich verbessern, um 30-40%. Und als Ergebnis einer solchen Organisation sind sie für den Cache völlig unfreundlich, d.h. Jeder Übergang durch den Baum wird höchstwahrscheinlich dazu führen, dass Sie eine Cache-Zeile benötigen. Dies haben Sie nicht im Cache, da es wahrscheinlich ist, dass Ihre Knoten versehentlich im Adressraum verschmiert sind. Daher können Sie dem Prädiktor nichts Gutes darüber sagen, an welche Adresse Sie sich wenden werden. Deshalb haben wir unsere Bäume gemacht - das sind B + * Bäume:



    Was ist die Idee? Die Tatsache, dass wir in jedem Block nicht ein Element speichern, sondern viele - durchschnittlich 20 Elemente, vielleicht 40. Und wir machen diesen Speicher so, dass er gut in den Cache passt, damit wir nach einer Gelegenheit im Block suchen können, nicht Durchlaufen Sie die Cache-Zeilen, damit alles in die Cache-Zeile passt.

    Außerdem speichern wir Elemente nur in Blättern, um diesen Baumtitel so kompakt wie möglich zu gestalten, damit er wieder in den Cache passt. Wir spülen durch die Blätter und machen die Iteration des Baumes schnell. Das heißt Um über einen Baum zu iterieren, müssen wir nach oben zurückkehren und über die Blätter iterieren. Und wir verwenden die Matratze für die Zuordnung, um die Bäume einfrieren zu können, sodass die Zeiger 32-Bit zu den Knoten des Baums sind.

    Es funktioniert so:



    Im Durchschnitt besteht ein Baum aus drei Ebenen, in der Regel mit mehr oder weniger realer Tabellengröße. Dies ist ein Baum, der sehr gut ausbalanciert ist.

    Was ist der Unterschied zwischen einem B + -Baum, einem B + * -Baum und klassischen B-Bäumen, die Daten an Zwischenscheitelpunkten usw. speichern? Dieser Baum garantiert die Füllung jedes Blocks um 2/3, die Füllung mit Elementen, um diese Füllung mit Ausgleich zu gewährleisten. Dies ist ein klassisches Gesetz. Wenn Sie das Feld so ausfüllen möchten, dass Ihr Durchschnitt bei der Neuausrichtung 1/2 beträgt, müssen Sie nur den Nachbarn betrachten und die Elemente auf irgendeine Weise zwischen dem aktuellen Knoten und dem benachbarten Knoten mischen. Es hat einen Durchschnitt von 1/2, Sie haben einen Durchschnitt von 1/2 - es sollte passen, wenn es nicht passt, dann müssen Sie definitiv einen Split machen, und Ihre durchschnittliche Belegung wird bleiben, Sie werden immer noch 1/2 Belegung haben. Wenn Sie eine durchschnittliche Belegung von 2/3 haben, d.h. Wenn Sie einen höheren Indikator erreichen möchten, müssen Sie beim Ausgleich nicht auf einen Nachbarn, sondern auf zwei schauen. und sogar drei, je nach Konfiguration. Und dementsprechend verteilen Sie Ihre Daten zwischen ihnen. Einen solchen Baum wieder ins Gleichgewicht zu bringen ist ziemlich teuer, aber der Baum ist sehr gut ausbalanciert.

    Was sind unsere Ergebnisse?



    Wir haben einen geringen Overhead pro Speichereinheit und ein sehr gutes Gleichgewicht, d.h. Bei der Suche werden durchschnittlich 1,1 log (N) Vergleichsoperationen durchgeführt. Darüber hinaus funktionieren diese Vergleichsoperationen sehr gut mit dem Cache, da alle diese Baumblöcke gut in den Cache passen.

    Tatsächlich ist der Baum so gut, dass wir manchmal gar nicht bemerken, dass er schneller ist - ein Hash oder ein Baum in Version 1.6. Nach unseren Messungen ist der Hash jetzt etwa 30-40% schneller, d.h. dort ist die logarithmische Komplexität und dort ist sie konstant und der Gewinn beträgt nur 40%, da dieser Logarithmus in der Tat nur beim Betrachten von 2-3 Cachelines ausgedrückt wird, und im Hash kann dies der Durchschnittswert von 2 Cachelines von Views sein. Das heißt Die Kosten der Datenstruktur werden nicht in klassischen Operationen gemessen, sondern daran, wie gut sie mit dem Cache funktionieren.

    Kontaktdaten


    » Kostja
    » Mail.ru Unternehmensblog

    Dieser Bericht ist eine Abschrift einer der besten Reden auf der Entwicklerkonferenz für hoch belastete Systeme HighLoad ++ . Jetzt bereiten wir die Konferenz 2016 aktiv vor - dieses Jahr wird HighLoad ++ am 7. und 8. November in Skolkovo stattfinden.

    Konstantin ist Mitglied des HighLoad ++ Program Committee und unser regelmäßiger Redner. Im Jahr 2016 wird Kostya im Bericht „ Speicherung von Daten auf Vinyl “ über die neue Speicher-Engine in Tarantool sprechen .

    Übrigens, das gesamte Programmkomitee von HighLoad ++ empfiehlt die Tarantool- Plattform einstimmig . Dies ist eine unserer wunderbaren (russischen) Entwicklungen und verdient zumindest Aufmerksamkeit.

    Einige dieser Materialien werden von uns auch in einer Online-Schulung zur Entwicklung hochbelasteter Systeme verwendet.HighLoad.Guide ist eine Kette von speziell ausgewählten Briefen, Artikeln, Materialien und Videos. Bereits in unserem Lehrbuch mehr als 30 einzigartige Materialien. Verbinde dich!

    Nur registrierte Benutzer können an der Umfrage teilnehmen. Bitte komm rein .

    Sie und die Tarantool-Datenbank?

    • 20,3% Nichts vom Wort "überhaupt" 42
    • 63,1% Ich habe von dieser Datenbank gehört, aber noch nicht 130 verwendet
    • 7,7% Ich habe versucht zu pflücken, aber wirklich nichts ausgewählt 16
    • 3,3% Alles ist ernst, wir planen, Tarantool in unserem Projekt 7 zu verwenden
    • 5,3% Wir verwenden Tarantool bereits in unserem Projekt! 11

    Jetzt auch beliebt: