*Dies ist Teil Nr. 1 von a Serie Wo jemand Fragen zu Geth stellen kann und ich werde versuchen, die höchste gewählt pro Woche mit einem Mini -Bericht zu beantworten. Die höchste gestimmte Frage dieser Woche war: Könnten Sie teilen, wie sich die flache DB -Struktur von der Legacy -Struktur unterscheidet?*
Staat in Ethereum
Bevor wir uns in eine Beschleunigungsstruktur eintauchen, werden wir ein wenig zusammenfassen, was Ethereum anruft Zustand und wie es derzeit auf den verschiedenen Abstraktionsebenen gespeichert wird.
Ethereum unterhält zwei verschiedene Arten von Zustandsarten: die Kontenmenge; und eine Reihe von Speicherplätzen für jedes Vertragskonto. Von a rein abstrakte PerspektiveBeide sind einfache Schlüssel-/Wert -Zuordnungen. Die Kontenkartenadressen für Nonce, Saldo usw. Eine Speicherfläche eines einzelnen Vertragskartens beliebige Schlüssel – definiert und vom Vertrag verwendet – zu willkürlichen Werten.
Leider wäre das Speichern dieser Schlüsselwertpaare als flache Daten sehr effizient, die Überprüfung ihrer Richtigkeit rechnerisch unlösbar. Jedes Mal, wenn eine Änderung vorgenommen wird, müssten wir alle Daten von Grund auf neu gehassten.
Anstatt den gesamten Datensatz ständig zu haben, konnten wir ihn in kleine zusammenhängende Stücke aufteilen und einen Baum darüber bauen! Die ursprünglichen nützlichen Daten wären in den Blättern, und jeder interne Knoten wäre ein Hash von allem, was darunter ist. Dies würde es uns ermöglichen, nur eine logarithmische Anzahl von Hashes neu zu berechnen, wenn etwas geändert wird. Diese Datenstruktur hat tatsächlich einen Namen, es ist die berühmte Merkle Tree.
Leider fallen wir immer noch etwas kurz in der Rechenkomplexität. Das obige Merkle -Baum -Layout ist sehr effizient darin, Modifikationen an vorhandenen Daten zu integrieren, aber Insertionen und Löschungen verschieben die Chunk -Grenzen und ungültig und ungültig alle Der berechnete Hashes.
Anstatt den Datensatz blindend zu zerkleinern, können wir die Schlüssel selbst verwenden, um die Daten in einem Baumformat basierend auf gemeinsamen Präfixen zu organisieren! Auf diese Weise würde ein Einfügen oder Löschen nicht alle Knoten verschieben, sondern ändert sich nur den logarithmischen Pfad von Wurzel zu Blatt. Diese Datenstruktur wird als a genannt Patricia Tree.
Kombinieren Merkle Patricia TreeDie tatsächliche Datenstruktur, die zur Darstellung des Zustands in Ethereum verwendet wird. Garantierte logarithmische Komplexität für Änderungen, Einfügungen, Löschungen und Überprüfungen! Ein winziges Extra ist, dass Schlüssel vor dem Einsetzen gehasht werden, um die Versuche auszugleichen.
Staatliche Lagerung in Ethereum
Die obige Beschreibung erklärt Warum Ethereum speichert seinen Staat in einem Merkle Patricia -Baum. Leider ist jede Wahl so schnell wie die gewünschten Operationen ein Kompromiss. Die Kosten von logarithmische Aktualisierungen und logarithmische Überprüfung Ist logarithmische Lesungen und logarithmischer Speicher für Jeder einzelne Schlüssel. Dies liegt daran, dass jeder interne Trieknoten einzeln auf die Festplatte gespeichert werden muss.
Ich habe im Moment keine genaue Zahl für die Tiefe des Account-Tries, aber vor ungefähr einem Jahr haben wir die Tiefe von 7 gesättigt. Dies bedeutet, dass jede Trieoperation (z. B. Lesenbilanz, Schreiben von Nonce) mindestens 7-8 interne Knoten berührt und somit mindestens 7-8 persistierende Datenbankzugriffe ausführt. LevelDB organisiert seine Daten auch in maximal 7 Stufen, sodass von dort aus einen zusätzlichen Multiplikator vorhanden ist. Das Nettoergebnis ist, dass a einzel Der Zugriff auf den Zustand wird voraussichtlich verstärkt in 25-50 zufällig Datenträgerzugriffe. Multiplizieren Sie dies mit allen Liesen und schreibt, dass alle Transaktionen in einem Block -Touch und Sie zu a kommen beängstigend Nummer.
[Of course all client implementations try their best to minimize this overhead. Geth uses large memory areas for caching trie nodes; and also uses in-memory pruning to avoid writing to disk nodes that get deleted anyway after a few blocks. That’s for a different blog post however.]
So schrecklich diese Zahlen auch sind, dies sind die Kosten für den Betrieb eines Ethereum -Knotens und die Fähigkeit, zu jeder Zeit den gesamten Staat zu überprüften. Aber können wir es besser machen?
Nicht alle Zugriffe sind gleich erzeugt
Ethereum stützt sich auf kryptografische Beweise für seinen Staat. Die Festplattenamplifikationen gibt es nicht, wenn wir unsere Fähigkeit beibehalten möchten, alle Daten zu überprüfen. Das heißt, wir kann – und tun – Vertrauen Sie den Daten, die wir bereits überprüft haben.
Es macht keinen Sinn, jeden Zustandsgegenstand zu überprüfen und zu überprüfen, jedes Mal, wenn wir ihn von der Festplatte hochziehen. Der Merkle Patricia Tree ist für Schreibvorgänge unerlässlich, aber es ist ein Overhead für Lesevorgänge. Wir können es nicht loswerden und wir können es nicht schlächen; Aber das bedeutet nicht Wir müssen es unbedingt überall nutzen.
Ein Ethereum -Knoten greift an verschiedenen Orten auf den Zustand zu:
- Beim Importieren eines neuen Blocks führt die Ausführung von EVM-Code eine mehr oder weniger ausgewogene Anzahl von staatlichen Lese- und Schreibvorgängen durch. Ein Denial-of-Service-Block könnte jedoch wesentlich mehr Lesevorgänge als Schreibvorgänge ausführen.
- Wenn ein Knotenoperator den Zustand abruft (z. B. z. B. ETH_CALL und Familie), EVM -Codeausführung liest nur (sie kann auch schreiben, aber diese werden am Ende weggeworfen und sind nicht bestehen).
- Wenn ein Knoten synchronisiert ist, fordert er Status von Remote -Knoten an, die ihn ausgraben und über dem Netzwerk servieren müssen.
Basierend auf den oben genannten Zugriffsmustern wird eine Reihe von Knotenoperationen, wenn wir Kurzschluss liest, um nicht auf den Status -Trie zu schlagen signifikant Schneller. Es könnte sogar einige neuartige Zugriffsmuster (wie die staatliche Iteration) ermöglichen, die zuvor unerschwinglich teuer waren.
Natürlich gibt es immer einen Kompromiss. Ohne den Trie loszuwerden, ist jede neue Beschleunigungsstruktur zusätzlicher Overhead. Die Frage ist, ob der zusätzliche Overhead genügend Wert bietet, um ihn zu rechtfertigen.
Zurück zu den Wurzeln
Wir haben diesen magischen Merkle Patricia Tree gebaut, um alle unsere Probleme zu lösen, und jetzt möchten wir ihn für Lesevorgänge umgehen. Welche Beschleunigungsstruktur sollten wir verwenden, um die Lesevorgänge wieder schnell zu machen? Wenn wir den Trie nicht brauchen, brauchen wir keine der eingeführten Komplexität. Wir können den ganzen Weg zurück zu den Ursprüngen gehen.
Wie zu Beginn dieses Beitrags erwähnt, die theoretisches Ideal Die Datenspeicherung für den Status von Ethereum ist ein einfacher Schlüsselwertgeschäft (separat für Konten und jeden Vertrag). Ohne die Einschränkungen des Merkle Patricia Tree gibt es “nichts”, dass uns die ideale Lösung tatsächlich implementiert!
Vor einiger Zeit stellte Geth seine vor Schnappschuss Beschleunigungsstruktur (standardmäßig nicht aktiviert). Ein Schnappschuss ist eine vollständige Ansicht des Ethereum -Staates in einem bestimmten Block. In Bezug auf die abstrakte Implementierung handelt es sich um eine Mülldeponierung aller Konten und Speicherplätze, die durch einen Flat-Schlüssel-Wert-Store dargestellt werden.
Wann immer wir auf ein Konto oder einen Speicherplatz zugreifen möchten, zahlen wir nur 1 LevelDB-Lookup anstelle von 7-8 gemäß dem Trie. Die Aktualisierung des Snapshots ist auch theoretisch einfach. Nach der Verarbeitung eines Blocks machen wir 1 zusätzliches LevelDB -Schreiben pro aktualisierter Slot.
Der Snapshot reduziert im Wesentlichen Lesevorgänge von O (log n) auf O (1) (Times LevelDB Overhead) auf Kosten der Erhöhung der Schreibvorgänge von O (log n) auf O (1 + log n) (Times LevelDB -Overhead) und erhöhtes Speicher Speicher von O (N log n) auf O (n + n log N).
Teufel steht im Detail
Die Aufrechterhaltung einer nutzbaren Momentaufnahme des Ethereum -Staates hat seine Komplexität. Solange Blöcke nacheinander kommen und sich immer auf dem letzten auf dem Letzten aufbauen, funktioniert der naive Ansatz, Änderungen in den Snapshot zu verschmelzen. Wenn es jedoch einen Mini -Reorg gibt (sogar einen einzigen Block), sind wir in Schwierigkeiten, weil es keinen Rückgängig macht. Persistente Schreibvorgänge sind Einwegbetrieb für eine Flat-Daten-Darstellung. Um die Sache noch schlimmer zu machen, ist der Zugriff auf den älteren Zustand (z. B. 3 Blöcke für einige DApp oder 64+ für schnelle/snap -Synchronisierung) unmöglich.
Um diese Einschränkung zu überwinden, besteht Geths Snapshot aus zwei Entitäten: einer anhaltenden Scheibenschicht, die eine vollständige Schnappschuss eines älteren Blocks ist (z. B. Kopf-128); und ein Baum von In-Memory-Diff-Schichten, die die Schreibvorgänge oben sammeln.
Immer wenn ein neuer Block verarbeitet wird, fusionieren wir die Schreibvorgänge nicht direkt in die Scheibenschicht, sondern erstellen Sie nur eine neue In-Memory-Diff-Schicht mit den Änderungen. Wenn genügend In-Memory-Diff-Schichten oben gestapelt sind, werden die unteren zusammengeführt und schließlich zur Festplatte gedrückt. Immer wenn ein Zustandsgegenstand gelesen werden soll, beginnen wir in der obersten Diff -Schicht und gehen weiter nachwärts, bis wir es finden oder die Festplatte erreichen.
Diese Datenrepräsentation ist sehr leistungsfähig, da sie viele Probleme löst. Da die In-Memory-Diff-Schichten in einen Baum zusammengebaut werden, können sie flachere, als 128 Blöcke, einfach die Diffschicht zum Elternblock auswählen und von dort nach vorne bauen. Dapps und Remote -Synzer, die älteren Staat benötigen, haben Zugriff auf 128 neuere. Die Kosten steigen um 128 MAP-Lookups, aber 128 In-Memory-Lookups sind Größenordnungen schneller als 8 Scheiben, die verstärkt 4x-5x durch LevelDB liest.
Natürlich gibt es viele, viele Gotchas und Vorbehalte. Ohne auf zu viele Details einzugehen, ist eine schnelle Auflistung der feineren Punkte:
- Selbstzerstörungen (und Deletionen) sind spezielle Tiere, die eine Abfahrt des Kurzschlussschichtschichts benötigen.
- Wenn es eine tiefere Reorg als die persistente Scheibenschicht gibt, muss der Schnappschuss vollständig verworfen und regeneriert werden. Das ist sehr teuer.
- Beim Herunterfahren müssen die In-Memory-Diff-Schichten in ein Tagebuch aufgehalten und wieder aufgeladen werden, ansonsten wird der Schnappschuss beim Neustart nutzlos.
- Verwenden Sie die untersten Diff-Schicht als Akkumulator und spülen Sie nur, um die Speicherverwendung zu überschreiten. Dies ermöglicht Deduping -Schreibvorgänge für die gleichen Slots über Blöcke hinweg.
- Weisen Sie einen Lese -Cache für die Festplattenschicht zu, damit Verträge, die immer wieder auf denselben alten Slot zugreifen, keine Festplattenhits verursachen.
- Verwenden Sie kumulative Blühenfilter in den Memory-Diff-Schichten, um schnell festzustellen, ob es eine Chance gibt, dass ein Element in den Diffs liegt, oder ob wir sofort auf die Festplatte gehen können.
- Die Schlüssel sind nicht die Rohdaten (Kontoadresse, Speicherschlüssel), sondern die Hashes davon, um sicherzustellen, dass der Schnappschuss die gleiche Iterationsreihenfolge wie der Merkle Patricia -Baum hat.
- Das Erzeugen der persistenten Scheibenschicht benötigt wesentlich mehr Zeit als das Schnittfenster für den Status, sodass selbst der Generator der Kette dynamisch folgen muss.
Das Gute, das Schlechte, das Hässliche
Geths Schnappschuss -Beschleunigungsstruktur reduziert die Komplexität des Zustands der staatlichen Lesung um etwa eine Größenordnung. Dies bedeutet, dass lesebasierte DOs eine Größenordnung schwerer zu ziehen sind. Und ETH_CALL Aufrufe erhalten eine Größenordnung schneller (wenn nicht die CPU -Grenze).
Der Snapshot ermöglicht auch die fließende Iteration der letzten Blöcke. Dies war eigentlich der Hauptgrund für den Aufbau von Schnappschüssenwie es die Schaffung des Neuen erlaubte Schnappnahme Synchronisierungsalgorithmus. Das zu beschreiben, dass dies ein völlig neuer Blog -Beitrag ist, aber die neuesten Benchmarks auf Rinkeby sprechen Bände:
Natürlich sind die Kompromisse immer vorhanden. Nach Abschluss der ersten Synchronisation dauert es ungefähr 9-10 Stunden, um den anfänglichen Schnappschuss zu konstruieren (danach live gepflegt) und dauert etwa 15+GB zusätzlichen Festplattenraum.
Was den hässlichen Teil betrifft? Nun, wir haben über 6 Monate gebraucht, um mich zuversichtlich genug zu fühlen, um es zu versenden, aber selbst jetzt liegt es hinter dem –Schnappschuss Flag und es gibt noch Tuning und Polieren, um die Speicherverwendung und die Absturzwiederherstellung zu erledigen.
Alles in allem sind wir sehr stolz auf diese Verbesserung. Es war eine wahnsinnige Menge an Arbeit und es war ein großer Schuss im Dunkeln, alles umzusetzen und zu hoffen, dass es funktioniert. Genau als lustige Tatsache wurde die erste Version von Snap Sync (Leaf Sync) vor 2,5 Jahren geschrieben und seitdem blockiert, weil uns die notwendige Beschleunigung fehlte, um sie zu sättigen.
Epilog
Ich hoffe, Sie haben diesen ersten Beitrag von genossen Fragen Sie nach Geth. Ich brauchte ungefähr doppelt so viel, um es zu beenden, als ich wollte, aber ich hatte das Gefühl, dass das Thema die zusätzliche Zeit verdient. Wir sehen uns nächste Woche.
[PS: I deliberately didn’t link the asking/voting website into this post as I’m sure it’s a temporary thing and I don’t want to leave broken links for posterity; nor have someone buy the name and host something malicious in the future. You can find it among my Twitter posts.]
