Erasure-Coding-Technik für verteilte Systeme
(transactional.blog)- Erasure Coding ist ein Kompromiss zwischen Speichereffizienz und Fehlertoleranz: Daten werden in Fragmente und Paritätsfragmente aufgeteilt, sodass Ausfälle mit weniger Speicherplatz als bei vollständiger Replikation überstanden werden können
- Das Grundmodell ist k+m=n; k ist die Anzahl der Datenfragmente, die zur Wiederherstellung nötig sind, m ist die Anzahl der Paritätsfragmente und zugleich die Zahl tolerierbarer Ausfälle, n ist die Gesamtzahl der Fragmente
- In Objekt- und Blob-Speichern kann statt einer dreifachen Vollreplikation eine Konfiguration wie 10+5 verwendet werden, um kleinere Fragmente auf mehr Server zu verteilen und den Speicherbedarf zu senken
- Quorum-Systeme können mit einfacher Mehrheitsentscheidung den Speicher nur begrenzt reduzieren; wird wie bei HRaft je nach Zahl verfügbarer Replikate zwischen 3+2, 2+2, 1+2 gewechselt, entstehen zusätzlicher Aufwand für Re-Encoding und Kapazitätsprovisionierung
- Für den praktischen Einsatz müssen sowohl die schwankenden Decoding-Kosten je nach Kombination der antwortenden Fragmente als auch die Unterschiede bei Metadaten und Alignment-Anforderungen von Jerasure, ISA-L und liberasurecode geprüft werden
Grundlegender Kompromiss zwischen Speichereffizienz und Ausfalltoleranz
- Es gibt zwei extreme Arten, eine Datei auf N Servern zu speichern
- Liegt auf allen Servern eine vollständige Kopie der Datei, geht die Datei selbst dann nicht verloren, wenn N-1 Server ausfallen, aber die Speicherkosten sind am höchsten
- Wird die Datei in N gleich große Fragmente geteilt und auf jedem Server nur eines gespeichert, ist die Speichereffizienz maximal, beim Lesen werden jedoch alle N Fragmente benötigt
- Erasure Coding steuert zwischen diesen beiden Extremen die Balance aus Speichereffizienz und Ausfalltoleranz
- Man kann einen Code so konstruieren, dass das Ziel erfüllt wird: „Die Datei wird in N Fragmente geteilt, soll aber auch dann wiederherstellbar sein, wenn M Fragmente zerstört werden“
- Dabei werden die kleinsten Fragmentgrößen erzeugt, die dieses Ziel erfüllen
- Die einfachste Intuition ist ein Beispiel mit 3 Servern, bei dem beliebige 2 ausreichen, um die gesamte Datei zu erhalten
- Die Datei wird in zwei Fragmente A und B geteilt
- Ein drittes Fragment C wird als A ⊕ B erzeugt
- Liest man A und B, werden sie direkt kombiniert; liest man A und C oder B und C, wird das fehlende Fragment per XOR rekonstruiert
- Alle Erasure Codes verallgemeinern dieses Muster durch Datenfragmente und Paritätsfragmente
Das k+m=n-Modell und Speicher-Overhead
- Eine Erasure-Code-Konfiguration wird als k + m = n beschrieben
- k: Anzahl der Fragmente, in die die Daten geteilt werden; zur Wiederherstellung eines Werts müssen mindestens k Fragmente gelesen werden
- m: Anzahl der erzeugten Paritätsfragmente; zugleich die Zahl tolerierbarer Leseausfälle bzw. Ausfälle
- n: Gesamtzahl der erzeugten Fragmente
- Die Größe eines einzelnen Ergebnisfragments beträgt 1/k der Originaldatei
- Erasure Codes werden meist über das Tupel
k+mbezeichnet- In der Literatur sind die Variablennamen nicht einheitlich
x+ybedeutet x Datenfragmente und y Paritätsfragmente
- Für Speicheranbieter ist das attraktiv, weil sich Ausfalltoleranz mit geringem Speicher-Overhead erreichen lässt
- Backblaze B2 verwendet 17+3 und toleriert 3 Ausfälle bei dem 1,18-fachen Speicherbedarf
- OVH Cloud toleriert mit einem 8+4-Code 4 Ausfälle bei dem 1,5-fachen Speicherbedarf
- Scaleway toleriert mit einem 6+3-Code 3 Ausfälle bei dem 1,5-fachen Speicherbedarf
- Der Hauptpreis ist der Tausch von geringerem Speicherverbrauch gegen mehr Leseanfragen
- Statt die Dateigröße von einer einzelnen Festplatte zu lesen, werden Anfragen an k+m Datenträger gesendet
- Speichersysteme für selten genutzte Daten sind gut geeignet, weil die zusätzliche IOPS-Last relativ klein ist und die Speichereinsparung stark ins Gewicht fällt
Algorithmusfamilie und MDS-Codes
- „Erasure Coding“ bezeichnet keinen einzelnen Algorithmus, sondern eine Algorithmusfamilie
- Reed-Solomon-Codes können allgemein zur Implementierung von Erasure Codes mit beliebigen k+m-Konfigurationen verwendet werden
- Es gibt auch eine Entsprechung zu RAID
- RAID-0 ist k+0 Erasure Coding
- RAID-1 ist 1+m Erasure Coding
- RAID-4 und RAID-5 sind leicht abgewandeltes k+1 Erasure Coding
- RAID-6 ist k+2 Erasure Coding
- Der Fokus dieses Texts liegt auf MDS-(Minimum Distance Separable)-Erasure-Codes
- MDS-Codes bieten eine quorumähnliche Eigenschaft, bei der beliebige m verlorene Fragmente toleriert werden
- Andere Erasure-Code-Familien können manche Kombinationen schon mit weniger als m Fragmenten rekonstruieren, während für andere Kombinationen mehr als m nötig sein können
- Wenn das erwartete Fehlermuster bekannt ist, kann ein Ansatz sinnvoll sein, bei dem häufige Fehler mit weniger Fragmenten rekonstruiert werden und seltene Ausnahmefälle mit mehr Fragmenten
- Als Beispiele in diese Richtung werden die Local Reconstruction Codes und SD Codes von Azure Storage genannt
Einsatz in Objektspeichern und Caches
- Der direkteste Anwendungsfall ist die Senkung von Speicherkosten und gleichzeitige Erhöhung der Dauerhaftigkeit in Systemen mit fester Replikatmenge
- Beispiele sind Blob-/Objektspeicher oder NFS-Speicher
- Ein Metadatenservice ordnet Dateipfade den Servern zu, auf denen die jeweilige Datei gespeichert ist
- Statt drei Replikate zu speichern, die jeweils die vollständige Datei enthalten, können 15 Replikate Fragmente einer 10+5 erasure-codierten Datei speichern
- Die insgesamt gespeicherte Datenmenge halbiert sich
- Die Ausfalltoleranz steigt auf mehr als das Doppelte
- Das allgemeinere Muster lautet: Statt Daten auf X Servern zu speichern, werden sie auf X+m Replikaten mit einem X+m-Erasure-Code abgelegt
- Das Beispiel eines Caching-Systems von Marc Brooker wendet dieses Muster auf einen Cache an
- Statt per konsistentem Hashing einen von k Cache-Servern auszuwählen, wird über k+m Cache-Server ein k+m-Erasure-Code verwendet
- Auf die langsamsten m Antworten muss nicht gewartet werden
- So können Speicherverbrauch und Tail-Latenz gleichzeitig verbessert werden
- Diese Einsparung hat den Preis höherer IOPS/QPS oder CPU-Last
- Vorausgesetzt wird, dass Speicherkapazität die limitierende Ressource ist und CPU-Reserven vorhanden sind
- In einem System, das bereits nahe an sein CPU-Limit kommt, ist das womöglich keine Sparmaßnahme
Grenzen von Quorum-Systemen und HRaft
- Bei 5 Replikaten passt ein einfaches Mehrheitsquorum mit mindestens 3 für Lesen und Schreiben auf der Leseseite gut zu einem 3+2-Erasure-Code
- Denn mit Ergebnissen von beliebigen 3 Replikaten kann ein Lesevorgang abgeschlossen werden
- Da ein Schreibvorgang schon dann abgeschlossen werden kann, wenn ihn beliebige 3 Replikate übernommen haben, lässt sich mit festem Erasure Code nur ein 1+2-Code verwenden
- 1+2 entspricht drei vollständigen Dateikopien
- Mit einer rein direkten Anwendung gibt es also keine Speichereinsparung
- RS-Paxos geht bei der Anwendung von Erasure Codes auf Paxos davon aus, dass ein Vorteil nur besteht, wenn die Überlappung zweier Quoren größer als 1 Replikat ist
- Wenn bei 7 Replikaten zum Beispiel sowohl fürs Lesen als auch Schreiben mindestens 5 nötig sind, können 2 Ausfälle toleriert und zugleich ein 3+2-Code eingesetzt werden
- Allgemein ist bei N Replikaten und gewünschter Ausfalltoleranz f mit festem Erasure Coding bestenfalls (N-2f)+f möglich
- HRaft passt die Kodierung auch bei einfachem Mehrheitsquorum an die Zahl verfügbarer Replikate an
- Sind alle 5 verfügbar: 3+2
- Sind 4 verfügbar: 2+2
- Sind 3 verfügbar: 1+2
- Dieser adaptive Ansatz bietet Verbesserungspotenzial, bringt aber auch operative Einschränkungen mit sich
- Jeder Schreibvorgang schätzt die Zahl der aktuell verfügbaren Replikate optimistisch
- Bestätigt ein Replikat einen Schreibvorgang unerwartet nicht, muss der Schreibvorgang neu kodiert und an alle Replikate erneut gesendet werden
- Damit die Verfügbarkeit selbst nach zwei Ausfällen im 1+2-Modus nicht wegen fehlendem Speicherplatz oder Durchsatz verloren geht, muss eine Replikatkonfiguration provisioniert werden, die vollständige Werte speichern kann
- Wenn Ausfälle selten sind und schnell behoben werden, kann das adaptive Encoding von HRaft deutliche Verbesserungen bringen
Bibliotheken und Anwendungsbeispiele
- Für Erasure-Coding-Berechnungen gibt es mit Jerasure eine ausgereifte Standardbibliothek
- Auf aktuellen Intel-Prozessoren ist die Intel Intelligent Storage Acceleration Library eine SIMD-optimierte Bibliothek, die in Benchmarks regelmäßig weit oben liegt
- In Python lässt sich über pyeclib auf Erasure-Coding-Implementierungen zugreifen
- Das Beispiel verwendet den Treiber
liberasurecode_rs_vand - Jedem Fragment werden vorne Metadaten zur Positionsidentifikation vorangestellt
- Zudem gibt es einige zusätzliche Bytes
- Das Beispiel verwendet den Treiber
- Die Beispielergebnisse von HRaft nach Zahl verfügbarer Replikate lauten wie folgt
- 3+2, Original 10000 Byte: 5 Fragmente, 3355 Byte pro Fragment, tatsächlich insgesamt 16775 Byte, Effizienz 59,61 %
- 2+2, Original 10000 Byte: 4 Fragmente, 5021 Byte pro Fragment, tatsächlich insgesamt 20084 Byte, Effizienz 49,79 %
- 1+2, Original 10000 Byte: 3 Fragmente, 10021 Byte pro Fragment, tatsächlich insgesamt 30063 Byte, Effizienz 33,26 %
- 1+2 Erasure Encoding entspricht drei vollständigen Datenkopien und ist damit gleichbedeutend damit, gar kein Erasure Encoding einzusetzen
Decoding-Kosten und Unterschiede zwischen Implementierungen
- Die Decoding-Leistung hängt davon ab, wie viele Datenfragmente rekonstruiert werden müssen
- Einen 3+2-Code aus 3 Datenfragmenten zu decodieren ist rechnerisch fast trivial
- Soll dieselbe Datei aus 2 Datenfragmenten und 1 Paritätsfragment decodiert werden, muss ein lineares Gleichungssystem per Gaussian elimination gelöst werden
- Je mehr Paritätsfragmente benötigt werden, desto höher ist der Rechenaufwand
- Wird Erasure Code in einem Quorum-System genutzt, können sich die CPU-Kosten je nach den konkret antwortenden Replikaten unterscheiden
- liberasurecode abstrahiert gängige Implementierungsbibliotheken für Erasure Coding, aber das bedeutet nicht, dass diese Implementierungen gleichwertig sind
- Nur weil zwei Codes beide 3+2 sind, heißt das nicht, dass sie mathematisch gleich aufgebaut sind
- liberasurecode fügt nicht nur lineare Algebra hinzu, sondern auch die für Einrichtung und Nutzung des Decoders nötigen Metadaten
- Diese Metadaten lassen sich nicht deaktivieren oder anpassen
- Bei direkter Nutzung von Jerasure oder ISA-L kann man nur mit den erasure-codierten Daten selbst arbeiten
- Allerdings muss über die API zu jedem Fragment angegeben werden, ob es das N-te Datenfragment oder ein Paritätsfragment ist; der Index muss also in irgendeiner Form als Metadatum erhalten bleiben
- Jerasure und ISA-L unterscheiden sich auch bei den Alignment-Anforderungen
- Jerasure wendet auf die erwartete lineare Algebra-Ausgabe eine Permutation an
- Jerasure kann keine ungeordneten Teilmengen oder Obermengen dessen lesen, was es kodiert hat
- ISA-L wendet keine Permutation an und kann daher ungeordnete Teilmengen oder Obermengen decodieren
- Weitere Implementierungen kommen ebenfalls infrage
- tahoe-lafs/zfec
- catid/cm256
- catid/longhair
- catid/leopard
- Wenn dies zum Flaschenhals wird, kann eine stärker auf den jeweiligen Anwendungsfall optimierte Bibliothek gefunden werden, aber ISA-L ist im Allgemeinen gut genug
Algorithmuswahl und mathematische Konstruktion
- In der Praxis kann ein Erasure Code problemlos wie eine magische Funktion behandelt werden, die 1 Datei in n Fragmente verwandelt und wieder rekonstruiert
- Die Konstruktion aus n Fragmenten basiert im Allgemeinen auf linearer Algebra über Galois-Feldern
- Um Erasure Codes produktiv einzusetzen, muss diese Mathematik nicht zwingend verstanden werden
- Die meisten MDS-Codes werden über Matrixmultiplikation berechnet
- Addition wird durch XOR ersetzt
- Multiplikation wird durch die teurere Multiplikation über GF(256) ersetzt
- Für Spezialfälle mit 1 bis 3 Paritätsfragmenten gibt es XOR-only-Algorithmen statt Reed-Solomon
- m=1: ein einzelnes Paritätsfragment als XOR aller Datenfragmente
- m=2: entspricht RAID-6; genannt werden Liberation codes, HDP codes, EVENODD und X-Codes
- m=3: ist mit STAR coding möglich
- Im allgemeinen Fall werden Varianten der Reed-Solomon-Familie verwendet
- Es kommen Vandermonde- oder Cauchy-Matrixkonstruktionen zum Einsatz
- Ziel ist, dass der obere k×k-Block eine Einheitsmatrix bildet, damit jedes Datenfragment erhalten bleibt und auch nach dem Löschen von m Zeilen noch eine Inverse existiert
- Das Encoding besteht in der Multiplikation mit dieser Matrix, das Decoding im Entfernen der Zeilen, die den verlorenen Fragmenten entsprechen, und anschließendem Lösen des linearen Gleichungssystems
- Die von ISA-L verwendete Gaussian elimination ist die einfachste, aber auch langsamste Decoding-Methode
- Bei Cauchy-Matrizen sind Verbesserungen möglich; catid/cm256 nutzt dies
- Die derzeit schnellste Methode scheint in catid/leopard implementiert zu sein und verwendet Fast Fourier Transform für Encoding und Decoding
Schritte zur Implementierungsoptimierung
- Es gibt mehrere Stufen, um eine Erasure-Code-Implementierung für beliebige k+m-Konfigurationen zu beschleunigen
- Die erste Stufe ist eine Implementierung des Algorithmus in C, die auf automatische Vektorisierung durch den Compiler setzt
- Das ist am einfachsten und am portabelsten
- Wichtig sind der Einsatz von
restrictund architekturspezifische Compiler-Flags wie-march=native
- Die zweite Stufe abstrahiert Plattformspezifika über Vektorisierungsbibliotheken oder Compiler-Intrinsics
- google/highway
- xtensor-stack/xsimd
std::experimental::simd- GCC Vector Extensions builtins
- Das Herzstück von Encoding und Decoding sind Multiplikation und Addition im Galois-Feld
- Als optimierte Bibliotheken werden catid/gf256 und James Plank’s Fast Galois Field Arithmetic Library genannt
- Die dritte Stufe besteht darin, die Kernfunktionen für Encoding und Decoding direkt vektorisiert zu schreiben
- Das PARPAR-Projekt behandelt in fast-gf-multiplication und xor_depends work schnelle GF(256)-Operationen
- Zusammengefasst wird, dass XOR-only-GF-Multiplikation schneller ist als tabellenbasierte Multiplikation
- Darüber hinaus kann Code auf bestimmte k+m-Konfigurationen spezialisiert werden
- Es werden optimale Codiermatrizen und XOR-Schedules für ein bestimmtes GF-Polynom und eine bestimmte Encoding-Matrix gesucht
- Dabei werden Operationen, Speicher und Cache optimiert
- Optimale Instruktions-Schedules für bestimmte Architekturen können programmatisch gesucht werden
- Als zugehörige Implementierungen und Materialien werden yuezato/xorslp_ec, Thesys-lab/tvm-ec und "Fast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration Techniques" genannt
Materialien zum tieferen Einstieg
- Als Einstiege in die lineare Algebra hinter Erasure Coding sind die folgenden Links nützlich
- Für einen breiteren Deep Dive wird vorgeschlagen, mit James S. Plank’s publications zu beginnen
1 Kommentare
Meinungen auf Hacker News
Ich war überrascht, dass rateless Fountain Codes nicht erwähnt wurden. Wenn man solche Themen mag, dürfte der Luby Transform Code interessant sein: https://en.wikipedia.org/wiki/Luby_transform_code
Auch dieses Paper ist ein guter, ausführlicherer Überblick: https://switzernet.com/people/emin-gabrielyan/060112-capilla...
LT-Codes werden bei der in RFC6330 spezifizierten linearen RaptorQ-Codierung als äußerer Code verwendet: https://www.rfc-editor.org/rfc/rfc6330
Zweitens besteht der Algorithmus tatsächlich aus zwei Teilen: Der zweite, die Erzeugung der Reparaturblöcke, ist linear, aber der erste braucht kubische Zeit in Bezug auf die Anzahl der Nachrichten, die in einem Block zusammengefasst werden. Das entspricht im Wesentlichen der gaußschen Elimination für Matrizen.
Teile des Encodings und Decodings kann man zwar cachen, aber lineares Encoding bei RaptorQ ist im Grunde ein Marketing-Slogan.
Vor einiger Zeit hatte jemand einen netten Erasure-Code-Algorithmus vorgeschlagen, der nicht auf rotierende Platten, sondern auf Multipath-Networking setzt.
Ich glaube, das wurde Network Coding genannt; die Idee war, in einem Netzwerk mit mehreren Pfaden schneller an eine Datei zu kommen, indem man von einem Upstream einen Erasure Code aus zwei Teilen einer Datei oder aus zwei Dateien gemischt bekommt, statt beim Hauptserver auf die ganze Datei zu warten.
Ich vermute, dass hinter S3 und anderen Cloud-Storage-Systemen viel davon steckt, besonders bei Storage-Tiers mit seltenem Zugriff. Allerdings kenne ich die internen Systeme von AWS oder GCP nicht wirklich.
Nebenbei: Freenet nutzt zumindest FEC-codierte Dateien, sodass es flexibel ist, welche Fragmente man bekommt, und ein einzelnes verschwundenes Fragment nicht gleich die gesamte Datei kaputt macht.
Erasure Coding gibt es schon sehr lange. Erinnert sich noch jemand an PAR2-Dateien im Usenet? https://en.wikipedia.org/wiki/Parchive
Wenn man sich für Erasure Coding interessiert, lohnt es sich auch, größere mehrdimensionale Fälle zu betrachten. Dabei geht es nicht nur um Encoding über mehrere Festplatten hinweg, sondern auch um andere Failure Domains wie Racks, Räume, Rechenzentren und Regionen.
Ziel ist es, nicht nur den Ausfall gemeinsamer Komponenten, sondern auch größere Systemausfälle oder Partitionen zu überstehen. Ein guter Einstieg: https://chameleoncloud.org/blog/2023/12/12/design-considerat...
Wenn ein transozeanisches Glasfaserkabel nur 1 Tbps schafft, kann das Verschieben aller Daten mehr als 6 Monate dauern.
Ich frage mich, ob jemand Wirehair schon in einem Projekt eingesetzt hat: https://github.com/catid/wirehair
Ich frage mich, ob es gut genug definiert ist, um als Standardgrundlage für ein Projekt zur Archivierung großer Dateien und Datenwiederherstellung zu dienen, das ich seit fast zehn Jahren im Kopf habe. Auch wenn es kein offizieller Standard ist, würde ich gern wissen, ob man es wie einen De-facto-Standard verwenden kann.
Unter den Large-Block-Erasure-Codes, die ich bisher gefunden habe, ist es der einzige, der sowohl eine ideale oder nahezu ideale Algorithmus-Performance als auch eine API bietet. Daher ist es für meinen Anwendungsfall eine gute Black Box, anders als etwa RaptorQ, bei dem überall kleine Details durchsickern und die Komplexität und Starrheit des restlichen Stacks erhöhen.
Allerdings ist Wirehair keine Spezifikation, sondern die Implementierung einer Idee, und es wirkt auch wie eine experimentelle Implementierung. Es sieht zwar stabil aus, aber solange ich nicht selbst eine zweite Implementierung geschrieben habe oder es so breit eingesetzt wurde, dass die scharfen Kanten des Algorithmus sichtbar geworden sind, mache ich mir Sorgen, ob es sich leicht in eine vertrauenswürdige Spezifikation oder eine zweite Implementierung überführen lässt.
Allerdings könnte Qualcomm behaupten, dass es unter die RaptorQ-Patente fällt, weil es konzeptionell damit verwandt ist. Die frühesten dieser Patente dürften bald ablaufen oder bereits abgelaufen sein; die neueren File-Wrapper habe ich nicht geprüft. Qualcomm hat einige Zusagen gemacht, RaptorQ-Patente außerhalb von Funkanwendungen nicht durchzusetzen, aber ich erinnere mich nicht, ob das nur für konforme Implementierungen gilt.
Für den Einsatz im eigentlichen Bitcoin-Protokoll wäre eine Spezifikation nötig gewesen, daher habe ich mir einmal angesehen, was dafür erforderlich wäre. Ich und einige andere Bitcoin-Entwickler sind recht vertraut mit Zahlentheorie und Fehlerkorrekturcodes, aber diese Arbeit hat uns nicht besonders gereizt. In der Wirehair-Struktur gibt es ziemlich viele ad-hoc-Details, und bei unserer Veranlagung könnten wir beim Versuch, sie zu verbessern, in Fallen laufen.
Auf Bitcoin-Seite könnte das Interesse an einer breiteren Nutzung von Fountain Codes wieder aufkommen; wenn man also etwas wartet, schreibt vielleicht jemand eine Spezifikation.
Je nach genauem Anwendungsfall könnte auch https://github.com/catid/fecal interessant sein. Wenn die erwartete Zahl an Ausfällen sehr niedrig ist, kann es schneller sein als Wirehair.
Das im Artikel erwähnte Leopard ist kein Fountain Code, hat aber eine recht große Blockgröße. Aus Spezifikationssicht ist das ein Vorteil, weil es nur eine sehr schnelle Implementierung eines langweiligen Reed-Solomon-Codes ist; für die Spezifikation müsste man möglicherweise nur die Wahl des Felds und des Generators dokumentieren.
Genau. Das ist die Kerntechnik hinter den Erasure-Code-Pools von Ceph: https://docs.ceph.com/en/latest/rados/operations/erasure-cod...
Ganz ohne Preis ist das aber nicht. Die Codierungsparameter k, m kann man später nicht mehr ändern; man muss also sicher sein, dass diese Werte langfristig passen, oder von vorn anfangen.
Wegen dieser Unelastizität bleibt Replikation bei hochverfügbarer, fehlertoleranter Datenspeicherung weiterhin die dominierende Wahl.
Es verwendet einfach
--forceund hinterlässt ein beschädigtes Dateisystem.Wahrscheinlich ist das nur die Sorte Spaß, bei der es lustig gewesen wäre, wenn man dabei gewesen wäre — nur eben nicht, wenn ich es bin.
Stimmt es, dass ein Artefakt, das in einer Ausfallsituation erzeugt wurde, in der nur M von N verfügbar sind, anders codiert wird als eines, bei dem alle N verfügbar sind? Falls ja, sollte es wohl ein Bit-Flag geben, das „Neukodierung nötig, wenn N wiederhergestellt ist“ signalisiert.
Sonst bleiben Dateien zurück, deren Widerstandsfähigkeit bei beliebigen Verlusten innerhalb der N-Menge nicht besonders gut ist.
Jedes verteilte Storage-System braucht eine Art Bibliothekar, der Stripes überprüft und aufräumt, damit sie aus dem Risikozustand herauskommen.
Mir kommt auch Rabins Information Dispersal Algorithm in den Sinn. Er wird in diesem Paper beschrieben:
https://dl.acm.org/doi/10.1145/62044.62050
Ist das in der Praxis nur bei Read-only- oder sehr leseintensiven Workloads sinnvoll?