In der Welt der Datenstrukturen gibt es immer wieder Momente, in denen eine bestimmte Technologie oder Methode scheinbar unabhängig voneinander mehrfach erfunden wird. Dies bezeichnet man als Multiple Discovery, ein Phänomen, das besonders dann auftritt, wenn soziale und technologische Bedingungen reif für eine bestimmte Erfindung sind. Ein pulsierendes Beispiel dafür sind sogenannte Prolly Trees – neuartige Baumstrukturen, die sowohl in der Informatik als auch in der Datenverwaltung zunehmend an Bedeutung gewinnen. Doch warum eigentlich werden Prolly Trees immer wieder neu erfunden? Was macht sie so wertvoll, und wie entwickelte sich diese Technologie in den letzten Jahren? Diese Fragen lassen sich am besten durch einen Blick auf die Entstehungsgeschichte und die technischen Eigenschaften der Prolly Trees beantworten. Multiple Discoveries in der Wissenschaft sind keine Seltenheit.
Bekannte Beispiele sind die unabhängige Entwicklung der Infinitesimalrechnung durch Isaac Newton und Gottfried Leibniz oder die fast gleichzeitig formulierte Evolutionstheorie von Charles Darwin und Alfred Russel Wallace. Der Grundgedanke dahinter ist, dass Erfindungen oft weniger das Ergebnis eines einzelnen Genies sind, sondern vielmehr das Produkt sozialer und technologischer Voraussetzungen. Sobald die Bedingungen reif sind, treten Entdeckungen gehäuft auf. Genau dieses Muster lässt sich bei den Prolly Trees beobachten. Eine Prolly Tree ist im Kern eine Art Merkle Tree, der durch die Anwendung von Content-Defined Chunking – also einer inhaltsabhängigen Datenaufteilung – rekursiv aufgebaut wird.
Diese Kombination bewirkt, dass Daten effizient versioniert, verglichen und verändert werden können. Die Vorteile dieser Datenstruktur sind vielfältig: Prolly Trees speichern Daten in einer probabilistisch balancierten Baumstruktur, die einzigartig ist – unabhängig davon, wie der aktuelle Zustand erreicht wurde. Dies nennt man History Independence. Hinzu kommt das Prinzip der strukturellen Teilung, was bedeutet, dass bei der Speicherung von mehreren Versionen nur die Unterschiede zusätzlichen Speicherplatz benötigen. Dadurch sind sie auch bei der Berechnung von Differenzen zwischen Datenständen äußerst effizient.
Die Idee, Daten rekursiv über Inhalte zu chunkisieren und die so entstehenden Chunks als Baum zu organisieren, wird von verschiedenen Projekten verfolgt. Doch der Begriff „Prolly Tree“ wurde erstmals 2015 vom Projekt Noms geprägt, einem Datenmanagementsystem, das die Vorteile dieser Struktur herausstellte. Noms war bahnbrechend in der Art, wie es diese Technologien zur Versionierung relationaler Datenbanken einsetzte. Allerdings war Noms nicht das erste System, das diese grundlegenden Konzepte verwendete. Im Jahr 2009 entwickelte der Entwickler Avery Pennarun mit dem Tool Bup eine Methode, große Dateien durch Rolling-Hash-Funktionen in Git-Objekte zu zerlegen.
Obwohl Pennarun zwar technisch gesehen eine Prolly Tree implementierte, gab er dieser Struktur keinen Namen und machte sie auch nicht offiziell zum Thema. Auch andere Forschungsgruppen entdeckten eigenständig ähnliche Strukturen. So entstand 2019 am französischen Institut Inria der Begriff „Merkle Search Trees“, die viele Eigenschaften der Prolly Trees teilen, aber durch eine andere Baumbildungsmethode auf Basis der Anzahl führender Nullen ihrer Schlüssel unterscheiden. Diese Innovation brachte neue Vorteile in der Steuerung der Struktur und wurde später beispielsweise in Blueskys Protokoll ATProto eingesetzt, welches auf dezentralisierte Netzwerke zielt. 2020 folgte eine weitere unabhängige Entwicklung an der DePaul University, bei der es darum ging, Docker-Container effizienter zu speichern.
Die Forscher beschrieben sogenannte Content-Defined Merkle Trees – ebenfalls nahe Verwandte der Prolly Trees –, die die Datenstruktur bei der Verwaltung großer Dateien für Containeroptimierung nutzten. Diese Arbeit inspiriert sogar aktuelle Projekte wie XetHub, die es zu einer Git-Erweiterung ausbauten und damit vor allem im Bereich von Datenmanagement und Wissenschaftsdaten Anklang fanden. Diese Geschichte zeigt eines sehr deutlich: Prolly Trees sind keine Zufallsentdeckung eines einzelnen Autors, sondern das Produkt einer evolutionären Entwicklung in der Informatik. Die Vorarbeiten von Merkle Trees, die bereits in den 70er Jahren patentiert wurden, und das Content-Defined Chunking aus den 90er Jahren legten das Fundament für diese moderne Datenstruktur. Erst durch zunehmende Anforderungen an verteilte Versionierung, effiziente Speicherverwaltung und Konzepte wie Conflict-Free Replicated Data Types (CRDTs) wurde der tatsächliche Bedarf für Prolly Trees deutlich.
Von besonderem Interesse ist dabei, dass verschiedene Implementierungen ihren eigenen Schwerpunkt setzen und die Baumstruktur je nach Anwendungsfall optimieren. Ob es die probabilistische Balancierung von Noms ist, die order-unabhängige Chunking-Methode von Inria oder die anwendungsorientierte Speicheroptimierung bei DePaul – jede Lösung signalisiert einen unterschiedlichen Ansatz im Umgang mit großen, sich verändernden Datensätzen. Die weite Verbreitung dieser Idee über verschiedene Institutionen und Projekte hinweg spricht auch für ein starkes Zukunftspotential der Prolly Trees. Sie eignen sich hervorragend für Versionierungssysteme, die inkrementelle Updates effizient verwalten müssen, ohne dass dabei redundanter Speicher oder unnötige Rechenzeit verschwendet werden. Dies ist besonders wichtig in Zeiten stetig wachsender Datenmengen, bei denen traditionelle Methoden an ihre Grenzen stoßen.
Dabei ist auch die Bezeichnung „Prolly Tree“ ein interessantes Thema. Da unterschiedliche Entwicklergruppen den Baum unterschiedlich benannten, besteht noch keine einheitliche Terminologie. Entweder hört man von Merkle Search Trees, Content-Defined Merkle Trees oder eben Prolly Trees. Bei DoltHub, einem der Hauptakteure, wird der Begriff Prolly Tree verwendet, da diese Bezeichnung aus der Noms-Entwicklung stammt und aufgrund ihrer Popularität in Entwicklerkreisen am geläufigsten ist. Für Nutzer und Entwickler ist es daher hilfreich, die zugrundeliegende Technik zu verstehen, anstatt sich an die Bezeichnungen zu klammern – denn letztlich geht es darum, Daten effizient zu versionieren, zu vergleichen und zu synchronisieren.
Die Innovationskraft der Prolly Trees besteht somit weniger darin, je ein völlig neues mathematisches Prinzip zu schaffen, sondern vielmehr darin, bekannte Konzepte neu zu kombinieren und an aktuelle Anforderungen anzupassen. Sie sind ein Paradebeispiel dafür, wie technologische Evolution durch multiple unabhängige Entwicklungen bereichert wird. Ihre Rolle in der Speicherung und Versionierung großer, strukturierter Daten wird in den kommenden Jahren sicher weiter wachsen. Wer sich mit der Zukunft von Datenmanagement, verteilten Systemen und kollaborativem Arbeiten auseinandersetzt, kommt an dieser Datenstruktur kaum vorbei. Zusammenfassend verdeutlicht die Geschichte der Prolly Trees, wie soziale und technologische Rahmenbedingungen Innovationen formen.
Sie sind nicht nur faszinierende Ingenieurskunst, sondern auch ein Beleg für das Prinzip, dass Erfindungen oft mehrfach und unabhängig entstehen, sobald die Zeit reif ist. Gleichzeitig zeigen sie technische Lösungen für drängende Herausforderungen in der modernen Datenwelt – von Blockchain bis Containerisierung, von verteilten Netzwerken bis Versionierung. Für technologisch Interessierte, Softwareentwickler und Datenwissenschaftler bieten Prolly Trees spannende Perspektiven und praktische Werkzeuge, um die stetig wachsende Datenflut intelligent zu managen und nutzbar zu machen.
