Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

In der riesigen, unsichtbaren Infrastruktur, die die moderne Welt antreibt, werden Daten ständig über Netzwerke von Computern geschrieben, gespeichert und abgerufen. Diese Systeme müssen robust genug sein, um Informationen sicher zu halten, selbst wenn einzelne Maschinen ausfallen, abstürzen oder von böswilligen Akteuren kompromittiert werden. Um dies zu erreichen, zerlegen Ingenieure eine einzelne Datei oft in viele Teile und verteilen diese an verschiedenen Orten, eine Technik, die als Informationsverteilung (Information Dispersal) bekannt ist. Dies stellt sicher, dass das Originaldokument auch dann noch aus den verbleibenden Fragmenten rekonstruiert werden kann, wenn einige Teile verloren gehen. Eine beständige Herausforderung besteht jedoch darin, das Gleichgewicht der Kosten für diesen Schutz zu finden. Die sichere Speicherung von Daten erfordert in der Regel das Vorhalten zusätzlicher Kopien, was Speicherplatz verbraucht, während das Bewegen dieser Daten, um defekte Teile zu reparien oder sie für die Nutzung abzurufen, erhebliche Bandbreite beansprucht. Jahrelang waren die effizientesten Methoden zur Datenspeicherung langsam und teuer in der Reparatur, während die schnellsten Methoden zur Behebung defekter Knoten unglaublich verschwenderisch in Bezug auf den Speicherplatz waren.

Die Forscher Thomas Locher und Yvonne-Anne Pignolet haben eine neue Methode entwickelt, die diesen Zielkonflikt aufbricht und einen Weg bietet, Daten über alle diese Dimensionen hinweg gleichzeitig effizient zu speichern, zu verteilen und wiederherzustellen. Ihre Arbeit konzentriert sich auf eine spezifische Art von System, das als asynchrone verifizierbare Informationsverteilung bezeichnet wird, bei der Computer nicht über den exakten Zeitpunkt von Nachrichten übereinstimmen müssen, um korrekt zu funktionieren, aber dennoch in der Lage sind, die Gültigkeit und Konsistenz der gehaltenen Daten zu verifizieren. Das Team hat ein neuartiges Protokoll eingeführt, das Daten in einer gitterartigen Struktur organisiert, wodurch Knoten gerade so viel Information teilen können, dass fehlende Teile rekonstruiert werden können, ohne ganze Dateien herunterladen zu müssen. Dieser Ansatz reduziert die Menge der zu speichernden Daten sowie die für die Reparatur eines ausgefallenen Computers benötigte Bandbreite erheblich, während gleichzeitig die für den Abruf der Informationen erforderliche Geschwindigkeit beibehalten wird.

Der Kern dieses neuen Systems liegt darin, wie die Daten vor dem Versenden angeordnet werden. Anstatt die Information als eine einfache Liste von Fragmenten zu behandeln, kodieren die Forscher sie in eine zweidimensionale Matrix, oder ein Gitter aus Zeilen und Spalten. Stellen Sie sich die Daten als eine große Tabellenkalkulation vor, in der jede Zelle ein kleines Stück der Originaldatei enthält. Das System wendet dann einen mathematischen Prozess an, um die leeren Zellen dieses Gitters aufzufüllen, wodurch ein Netz aus Redundanz entsteht. Jedem Computer im Netzwerk wird eine spezifische Zeile und eine spezifische Spalte aus diesem Gitter zugewiesen. Er speichert nur die Daten, die zu dieser Zeile und dieser Spalte gehören, zusammen mit einem kleinen kryptografischen Beweis, der die Korrektheit der Daten verifiziert. Diese Struktur ist der Schlüssel zur Effizienz des Systems. Da jeder Computer ein Stück der Zeile und der Spalte jedes anderen Computers besitzt, können sie sich gegenseitig helfen, die Lücken zu füllen, falls eine Maschine ausfällt, ohne eine zentrale Instanz kontaktieren oder den gesamten Datensatz herunterladen zu müssen.

Wenn ein neuer Datensatz gespeichert werden muss, beginnt der Prozess damit, dass ein Client die ursprünglichen Gitterinformationen an das Netzwerk sendet. Die Forscher haben einen cleveren Handshake-Mechanismus entworfen, um sicherzustellen, dass dies schnell und ohne Verschwendung von Bandbreite geschieht. Der Client sendet die notwendigen Daten an jeden Computer und wartet auf eine Bestätigung, dass die Daten empfangen wurden. Wenn ein Computer nicht antwortet, sendet der Client nicht einfach die gesamte Datei erneut an alle. Stattdessen sendet er ein kleines, gezieltes Update, das nur die fehlenden Teile enthält, an die spezifischen Computer, die sie benötigen. Die anderen Computer im Netzwerk, die bereits ein Fragment der fehlenden Daten in ihrem eigenen Speicher halten, leiten diese spezifischen Teile dann an die problematischen Knoten weiter. Dieser kooperative Schritt bedeutet, dass das Netzwerk den Speichervorgang mit deutlich weniger gesamtem Datentransfer abschließen kann als bisherige Methoden, die oft den vollständigen Datensatz mehrfach senden mussten, um sicherzustellen, dass jeder eine Kopie besitzt.

Das Abrufen der Daten ist gleichermaßen optimiert. Wenn ein Benutzer eine Datei lesen möchte, fragt er eine ausreichende Anzahl von Computern nach deren Zeilendaten. Aufgrund der Art und Weise, wie das Gitter konstruiert wurde, kann der Benutzer die Originaldatei allein aus diesen Zeilen rekonstruieren, ohne jeden einzelnen Knoten im Netzwerk kontaktieren zu müssen. Das System verifiziert die Integrität der Daten mithilfe der neben den Fragmenten gespeicherten kryptografischen Beweise und stellt so sicher, dass keine korrupten oder bösartigen Informationen zurückgegeben werden. Dieser Abrufprozess ist so effizient wie die besten bestehenden Methoden, was bedeutet, dass die Geschwindigkeit beim Lesen der Daten nicht geopfert wurde, um die anderen Verbesserungen zu erzielen.

Vielleicht ist der bedeutendste Fortschritt die Art und Weise, wie das System Reparaturen handhabt, wenn ein Computer ausfällt. In älteren Systemen erforderte der Ersatz eines defekten Knotens oft, dass die neue Maschine den gesamten Datensatz aus dem Netzwerk herunterlädt, um ihren Anteil wieder aufzubauen – ein Prozess, der bei großen Dateien Tage dauern konnte und enorme Mengen an Bandbreite verbrauchte. In diesem neuen Protokoll muss ein Ersatzknoten nur wenige andere Computer kontaktieren, um seine spezifischen Zeilen- und Spaltendaten wiederherzustellen. Diese Nachbarn senden nur die kleinen Informationsstücke, die sich mit der Position des neuen Knotens im Gitter schneiden. Der neue Knoten verwendet diese Fragmente dann, um seinen vollständigen Speicheranteil mathematisch zu rekonstruieren. Dies reduziert die Menge der während einer Reparatur übertragenen Daten erheblich und macht das System für groß angelegte, reale Anwendungen praktikabel, bei denen Knoten häufig dem Netzwerk beitreten oder es verlassen.

Die Forscher analysierten ihr Protokoll gegenüber bestehenden Standards und fanden, dass es diese durchweg über alle Bereiche hinweg übertrifft. Für ein Netzwerk von einhundert Computern, die eine ein Gigabyte große Datei speichern, erfordert ihre Methode, dass jeder Knoten nur dreißig Megabyte speichert, während eine führende Alternative fünfundvierzig Megabyte benötigt. Dieser Unterschied mag bei einer einzelnen Datei gering erscheinen, aber skaliert auf Petabytes an Daten in einem globalen Netzwerk, übersetzt sich dies in eine Reduktion der gesamten Speicheranforderungen um anderthalb Petabyte. Ebenso benötigt ein neuer Knoten bei einem Ausfall im Vergleich zur bisherigen besten Methode deutlich weniger Daten: Er muss nur fünfundvierzig Terabyte an Daten herunterladen, um sich selbst zu reparieren, statt fünfundsiebzig Terabyte. Dies spart dreißig Terabyte an Traffic, was bei voller Netzwerkkapazität fast drei Tage an Reparaturverkehr entspricht, der nicht mehr benötigt wird.

Das Team untersuchte auch eine Variation ihres Protokolls, die es Benutzern ermöglicht, das System basierend auf ihren spezifischen Bedürfnissen abzustimmen. Durch Anpassung eines einzelnen Parameters können Betreiber wählen, den genutzten Speicherplatz noch weiter zu minimieren, auf Kosten eines etwas höheren Bandbreitenbedarfs für Reparaturen und Abruf. Diese Flexibilität macht das Protokoll für eine breite Palette von Szenarien geeignet, von dezentralen Archiven, die die Effizienz der LangzeitSpeicherung priorisieren, bis hin zu Hochleistungssystemen, die einen schnellen Datenzugriff benötigen. Die Arbeit zeigt, dass es möglich ist, verteilte Speichersysteme zu entwerfen, die nicht nur theoretisch optimal in einem Bereich sind, sondern praktisch effizient über den gesamten Lebenszyklus der Daten hinweg – vom Moment des Schreibens bis zum Moment der Reparatur oder des Abrufs.

Diese Forschung bietet einen konkreten Weg nach vorn für die nächste Generation verteilter Speichersysteme, indem sie die Engpässe adressiert, die deren Skalierbarkeit bisher begrenzt haben. Indem die Autoren bewiesen haben, dass geringer Speicher-Overhead, niedrige Kommunikationskosten beim Schreiben und eine effiziente Knotenreparatur koexistieren können, haben sie eine große Barriere für den Einsatz robuster, dezentraler Datennetzwerke beseitigt. Die Ergebnisse sind nicht bloß theoretisch; die spezifischen in der Studie abgeleiteten Konstanten lassen sich direkt in messbare Einsparungen bei Betriebskosten und Netzwerkkapazität übersetzen. Da Systeme wie dezentrale Archive und Blockchain-Lösungen stetig wachsen, werden Protokolle, die Daten effizient verwalten können, ohne die Zuverlässigkeit zu opfern, immer wichtiger werden, und diese neue Methode bietet eine ausgewogene, hochperformante Grundlage für diese Zukunft.