Structural Sharing selbst implementieren: Persistente Datenstrukturen in JavaScript

1. Das Kopierproblem bei unveränderlichen Updates

Unveränderliche Zustandsverwaltung ist in modernen JavaScript-Anwendungen die Regel, nicht die Ausnahme. Der naive Ansatz, ein Update umzusetzen, ist eine vollständige tiefe Kopie des gesamten Objekts oder Arrays, gefolgt von einer Änderung an der Kopie. Bei kleinen, flachen Strukturen ist das unproblematisch. Bei großen, tief verschachtelten Bäumen, etwa einem Dokumentenmodell mit tausenden Knoten, wird eine vollständige Kopie bei jedem einzelnen Update schnell zum Performance-Problem.

Structural Sharing löst genau dieses Problem. Statt die gesamte Struktur zu duplizieren, wird nur der Pfad von der Wurzel bis zum geänderten Knoten neu aufgebaut, während alle übrigen, unveränderten Teilbäume unverändert von der alten Version referenziert werden. Das Ergebnis ist eine neue, vollständig unveränderliche Version der Struktur, die den Großteil ihres Speichers mit der vorherigen Version teilt, statt ihn zu duplizieren. Diese Technik ist als Structural Sharing bekannt und liegt Bibliotheken wie Immutable.js sowie den persistenten Datenstrukturen in Clojure und Scala zugrunde.

2. Grundidee: Persistente Datenstrukturen und geteilte Teilbäume

Eine persistente Datenstruktur bewahrt bei jeder Änderung ihre vorherige Version vollständig, statt sie zu überschreiben. Der Begriff "persistent" bezieht sich hier nicht auf Festplattenspeicherung, sondern auf die Persistenz der alten Version im Speicher: nach einem Update existieren sowohl die alte als auch die neue Version gleichzeitig und beide bleiben vollständig funktionsfähig. Structural Sharing ist die Implementierungstechnik, die das effizient möglich macht, indem gemeinsame, unveränderte Teile zwischen beiden Versionen geteilt werden.

Der Kernmechanismus heißt Path Copying: bei einer Änderung an einem Knoten in einer Baum- oder Listenstruktur werden nur dieser Knoten und alle seine Vorfahren bis zur Wurzel neu erzeugt. Jeder neu erzeugte Vorfahre erhält Referenzen auf die unveränderten Geschwisterknoten der alten Version, statt diese zu kopieren. Bei einem ausbalancierten Baum mit n Knoten müssen dadurch für ein Update nur O(log n) Knoten neu erzeugt werden, statt aller n Knoten.

Ein weiterer wichtiger Aspekt der Persistenz ist die Unveränderlichkeit jedes einzelnen Knotens selbst. Ein Knoten in einer persistenten Datenstruktur wird nach seiner Erzeugung nie mehr verändert, üblicherweise durchgesetzt mit Object.freeze. Diese Garantie ist die Voraussetzung dafür, dass ein Knoten sicher zwischen mehreren Versionen der Struktur geteilt werden kann, ohne dass eine spätere Mutation an einer Version versehentlich auch die andere Version verändert.

3. Path Copying an einer einfach verketteten Liste

Am einfachsten lässt sich Structural Sharing an einer einfach verketteten Liste demonstrieren. Eine solche Liste besteht aus Knoten, die jeweils einen Wert und eine Referenz auf den nächsten Knoten enthalten. Fügt man ein neues Element am Anfang der Liste ein, muss lediglich ein neuer Kopfknoten erzeugt werden, der auf die bestehende, unveränderte restliche Liste zeigt. Die gesamte alte Liste bleibt unangetastet und wird vollständig mit der neuen Version geteilt.

Interessanter wird es beim Einfügen oder Ändern eines Elements in der Mitte der Liste. Hier müssen alle Knoten vor der Änderungsstelle neu erzeugt werden, weil ihre next-Referenz angepasst werden muss, während alle Knoten nach der Änderungsstelle unverändert von der alten Version übernommen werden. Das ist der Kern von Path Copying: nur der Pfad bis zur Änderung wird kopiert, der Rest wird geteilt.

// Immutable singly linked list with structural sharing
function cons(value, next) {
  return Object.freeze({ value, next });
}

function prepend(list, value) {
  // Only one new node is created, the rest is shared unchanged
  return cons(value, list);
}

function updateAt(list, index, newValue) {
  if (list === null) return null;
  if (index === 0) return cons(newValue, list.next); // shares list.next unchanged
  // Path copying: this node must be recreated because its "next" changes
  return cons(list.value, updateAt(list.next, index - 1, newValue));
}

const original = cons(1, cons(2, cons(3, null)));
const updated = updateAt(original, 1, 99);

console.log(original.next.value); // 2 — untouched
console.log(updated.next.value);  // 99 — new node
console.log(original.next.next === updated.next.next); // true — shared tail

4. Structural Sharing in einem binären Baum

Bäume zeigen den Vorteil von Structural Sharing noch deutlicher als lineare Listen, weil jeder innere Knoten typischerweise mehrere Kindknoten hat, von denen nur einer auf dem Pfad zur Änderung liegt. Ändert man einen Wert im linken Teilbaum eines binären Suchbaums, muss der rechte Teilbaum überhaupt nicht angefasst werden. Die neue Wurzel erhält eine neue Referenz auf den neu erzeugten linken Teilbaum und dieselbe, unveränderte Referenz auf den alten rechten Teilbaum.

Bei einem ausbalancierten Baum mit tausend Knoten reduziert dieses Prinzip die Anzahl der bei einem Update neu erzeugten Knoten auf etwa zehn, den Pfad von der Wurzel zum geänderten Blatt. Die übrigen 990 Knoten werden unverändert zwischen alter und neuer Version geteilt. Genau dieses logarithmische Verhalten macht Structural Sharing für große, häufig aktualisierte Baumstrukturen praktisch relevant, etwa für Undo-Historien oder kollaborative Editoren.

// Immutable binary search tree with structural sharing
function node(value, left = null, right = null) {
  return Object.freeze({ value, left, right });
}

function insert(tree, value) {
  if (tree === null) return node(value);
  if (value < tree.value) {
    // Only the left path is recreated, the right subtree is shared
    return node(tree.value, insert(tree.left, value), tree.right);
  }
  if (value > tree.value) {
    // Only the right path is recreated, the left subtree is shared
    return node(tree.value, tree.left, insert(tree.right, value));
  }
  return tree; // value already present, no change needed
}

let treeV1 = null;
for (const v of [50, 30, 70, 20, 40]) treeV1 = insert(treeV1, v);

const treeV2 = insert(treeV1, 35);
console.log(treeV1.right === treeV2.right); // true — right subtree fully shared

5. Vom Baum zum Trie: Skalierung auf größere Strukturen

Ein unbalancierter binärer Baum kann im schlechtesten Fall zu einer verketteten Liste degenerieren, bei der ein Update wieder O(n) statt O(log n) Knoten kopiert. Produktionsreife Implementierungen von Structural Sharing, etwa in Clojure oder in Immutable.js, verwenden deshalb sogenannte Hash Array Mapped Tries: breite, flache Bäume mit typischerweise 32 Kindern pro Knoten, indiziert über Teile des Hash-Werts oder Index eines Schlüssels.

Die höhere Verzweigung eines Tries reduziert die effektive Baumtiefe drastisch: selbst bei einer Million Einträgen bleibt die Tiefe bei etwa vier bis fünf Ebenen, weil jede Ebene den Suchraum um den Faktor 32 statt nur um den Faktor 2 reduziert. Für ein Update müssen dadurch nur vier bis fünf Knoten neu erzeugt werden, unabhängig von der Gesamtgröße der Struktur. Diese Konstruktion ist der Grund, warum Structural Sharing auch bei sehr großen, häufig aktualisierten Sammlungen praktikabel bleibt.

6. Referenzgleichheit als Nebeneffekt nutzen

Ein wichtiger praktischer Nutzen von Structural Sharing liegt außerhalb der reinen Speicherersparnis: weil unveränderte Teilbäume garantiert dieselbe Referenz behalten, wird ein einfacher Referenzvergleich mit === zu einem korrekten und extrem billigen Test auf inhaltliche Gleichheit. Ein Teilbaum, der sich nicht geändert hat, ist nach einem Update immer noch exakt derselbe Objektverweis wie zuvor, nie eine Kopie mit identischem Inhalt.

Genau dieser Effekt ist die Grundlage für die schnellen Vergleiche in React über shouldComponentUpdate oder React.memo: statt einer teuren Deep-Equality-Prüfung reicht ein einfacher Referenzvergleich, weil unveränderte Teile des Zustandsbaums durch Structural Sharing garantiert dieselbe Referenz behalten. Ohne diese Garantie müsste jede Komponente bei jedem Update eine vollständige inhaltliche Prüfung durchführen, was bei komplexen Anwendungen spürbar langsamer wäre.

7. Speicherverhalten: was wirklich geteilt wird

Ein verbreitetes Missverständnis ist, Structural Sharing würde den Speicherverbrauch auf null reduzieren. Tatsächlich wird bei jedem Update immer noch der Pfad von der Wurzel bis zum geänderten Knoten neu allokiert, dieser Speicher ist also zusätzlich zur alten Version notwendig. Der Gewinn liegt darin, dass die Größe dieses neu allokierten Pfads logarithmisch statt linear mit der Gesamtgröße der Struktur wächst.

Wichtig ist außerdem, dass alte Versionen nur dann Speicher freigeben können, wenn keine Referenz mehr auf sie existiert. Wer aus Debugging- oder Undo-Gründen absichtlich viele alte Versionen einer Struktur aufbewahrt, verhindert damit die Garbage Collection dieser Versionen, selbst wenn Structural Sharing den Speicherbedarf pro Version gering hält. Für eine Undo-Historie mit hunderten Zwischenschritten summiert sich das trotz Sharing zu spürbarem Speicherverbrauch, den man bewusst begrenzen sollte, etwa durch eine maximale Historientiefe.

In der Praxis lohnt sich ein Blick auf die tatsächliche Update-Häufigkeit, bevor man sich für Structural Sharing entscheidet. Eine Konfigurationsstruktur, die einmal beim Programmstart erzeugt und danach nie mehr geändert wird, profitiert nicht von der Technik, weil es schlicht keine wiederholten Updates gibt, deren Kosten sich amortisieren könnten. Der Vorteil zeigt sich erst bei Strukturen, die im laufenden Betrieb wiederholt und häufig aktualisiert werden.

8. Grenzen: wann sich Structural Sharing nicht lohnt

Für kleine, flache Objekte mit wenigen Feldern bringt Structural Sharing keinen messbaren Vorteil gegenüber einer einfachen flachen Kopie mit dem Spread-Operator. Der Implementierungsaufwand für Trie-basierte persistente Strukturen lohnt sich erst ab einer gewissen Größe oder Update-Frequenz, typischerweise bei Sammlungen mit hunderten bis tausenden Elementen, die häufig aktualisiert werden.

Ein zweiter Grenzfall betrifft Strukturen, die bei jedem Update fast vollständig verändert werden, etwa ein sortiertes Array nach dem Einfügen eines neuen kleinsten Elements. Hier gibt es kaum unveränderte Teilbäume, die geteilt werden könnten, und Structural Sharing bringt in diesem speziellen Fall keinen Vorteil gegenüber einer vollständigen Neuerstellung. Die Technik entfaltet ihren Wert vor allem bei lokalisierten, punktuellen Änderungen an großen Strukturen, nicht bei globalen Umwälzungen der gesamten Daten.

Eine praktische Faustregel: sobald ein Zustandsbaum größer als ein paar Dutzend Einträge wird und mehrmals pro Sekunde aktualisiert wird, etwa bei einem kollaborativen Editor oder einer Echtzeit-Datenvisualisierung, überwiegt der Nutzen von Structural Sharing deutlich den zusätzlichen Implementierungsaufwand gegenüber einer naiven vollständigen Kopie.

9. Structural Sharing im Vergleich zu Alternativen

Die folgende Tabelle stellt Structural Sharing den gängigen Alternativen für unveränderliche Updates gegenüber und zeigt die jeweiligen Kompromisse bei Performance und Implementierungsaufwand.

Für viele Anwendungen ist eine fertige Bibliothek der pragmatischere Weg, aber das Verständnis der zugrunde liegenden Path-Copying-Technik hilft, Performance-Probleme bei eigenen Zustands-Updates gezielt zu diagnostizieren und zu entscheiden, wann Structural Sharing tatsächlich den Implementierungsaufwand rechtfertigt.

10. Zusammenfassung

Structural Sharing löst das Kopierproblem unveränderlicher Updates, indem nur der Pfad von der Wurzel bis zum geänderten Knoten neu erzeugt wird, während alle unveränderten Teilbäume unangetastet mit der alten Version geteilt werden. Diese Technik, bekannt als Path Copying, reduziert die Update-Kosten von linear auf logarithmisch bei balancierten Bäumen und auf nahezu konstant bei breiten Tries mit hoher Verzweigung.

Der praktische Nutzen reicht über reine Speicherersparnis hinaus: garantierte Referenzgleichheit für unveränderte Teile macht einfache ===-Vergleiche zu einem korrekten Ersatz für teure Deep-Equality-Prüfungen, ein Effekt, den React und andere Frameworks für schnelle Re-Render-Entscheidungen nutzen. Für kleine, flache Strukturen bleibt eine einfache Kopie ausreichend, für große, häufig aktualisierte Bäume und Sammlungen ist Structural Sharing die Technik, die Performance und Korrektheit gleichzeitig sicherstellt.

11. FAQ: Structural Sharing selbst implementieren