Share
Embed
Erasure Coding — Was ist das eigentlich genau?
Überblick/Einführung zu Erasure Coding.
Wolfgang Stief
November 27, 2018
Transcript
18 slides
-
Boston Webinar Erasure Coding — Was ist das eigentlich genau?
Wolfgang Stief Senior Consultant -
§ Ganz ohne Mathematik geht es nicht Historie, Grundlagen, Begriffe
§ Einsatzgebiete und Grenzen des Erasure Coding Rechenbeispiele und das Repair Problem § Anwendungen und Literaturhinweise Agenda -
§ Kodierungstheorie, fehlertolerante Codes Gebiet der Zahlentheorie (Mathematik) 1960 Coding
Theory Reed Solomon, Berlekamp-Massey (CD, DVD, digitale Datenübertragung) 1990 RAID-6 (Evenodd, RDP, X-Code) ➛ Storage LDPC-Codes (Tornado, Raptor, LT) ➛ Netzwerk 2000 EC in Computernetzwerken zur Datenübertragung Regenerating Codes 2010 Non-MDS Codes (Cloud, Recovery) Woher kommt Erasure Coding? -
Grundlagen Aufgabe: Daten so auf Storage Nodes verteilen, dass bei
Ausfall von einzelnen Knoten alle Daten noch benutzbar bzw. rekonstruierbar sind. Daten Storage Nodes -
Grundlagen Aufgabe: Daten so auf Storage Nodes verteilen, dass bei
Ausfall von einzelnen Knoten alle Daten noch benutzbar bzw. rekonstruierbar sind. Daten Storage Nodes -
Von k, n und m (I) Wie beschreibt man n
Disks mit k gleich großen Datenbrocken + Codierung, um einen Plattenausfall zu überleben? k gleich große Stücke Daten insgesamt n Disks / Storage Nodes -
Von k, n und m (II) — Horizontal Codes Horizontal
Erasure Code: k Data Nodes/Disks, m Coding od. Parity Nodes/Disks. Coding/parity ist auf getrennten Nodes/Disks. k gleich große Stücke Daten insgesamt n Disks / Storage Nodes n = k + m m coding disks -
Von k, n und m (III) — Vertical Codes Vertical
Erasure Code: Code und Parity-Information liegen gemeinsam auf einem Node/einer Disk. k gleich große Stücke Daten insgesamt n Disks / Storage Nodes -
Von k, n und m (IV) — Erasure Codes Plattenausfall
➛ Daten auf ausgefallenen Platten werden unbrauchbar bzw. korrupt. Dieser Fehlerzustand heißt „erasure“➛ Erasure Coding k gleich große Stücke Daten insgesamt n Disks / Storage Nodes n = k + m m coding disks -
Von k, n und m (V) — MDS Kann der
angewendete EC Algorithmus den Ausfall von m Platten rekonstruieren, ist das ein Maximum Distance Separable Code (MDS). k gleich große Stücke Daten insgesamt n Disks / Storage Nodes n = k + m m coding disks -
§ EC(n,k), RS(n,k) n ➛ Gesamtzahl der Nodes/Platten k ➛
Anzahl der Datennodes/-platten m ➛ Anzahl der Paritynodes/-platten (m=n-k) § Beispiel: EC(8,5) 5 Datenplatten, 3 Parityplatten MDS = 3 (n-k) Overhead = 8/5 (1,6) (n/k) Notation k n m -
§ Anforderung: hohe Redundanz bei vertretbarem Overhead - mehrfache Replikation
braucht viel Plattenplatz ➛ großer Overhead § robuste Skalierung über viele Nodes (Performance) - RAID-5 oder RAID-6 mit >20 Platten ➛ unzuverlässig, hohe Rebuild-Zeiten - RAID-5: m=1; RAID-6: m=2 - große Storage-Cluster (m>10) § häufig bei Object Storage, eher selten (noch?) bei Block Storage § nicht sinnvoll: sehr viele sehr kleine Files ➛ Overhead wird zu groß Virtualisierung/Cloud: Container, Images, >50MB Wann ist Erasure Coding sinnvoll? -
§ 10 Datenplatten, 3x Replikation (typ. OpenStack Swift oder Ceph)
Rechenbeispiel OpenStack Swift Replica 10 Disks, 3x Replikat ➛ 30 Disks insgesamt. Ausfall der 3 „richtigen“ Disks macht Storage irreparabel korrupt Erasure Code (30,10) 10 Datendisks (k), 20 Paritydisk (m) MDS-Code: Ausfall 20 beliebige Platten, Storage bleibt funktionsfähig. Overhead: 30/10 = 3 (!) Ziel: 1,2 ... 1,5 (einfacher für größere k) Ausfall 3 Platten = EC(13,10) Overhead: 13/10 = 1,3 -
Aber! Repair Problem (I) § EC(4,2) - Evenodd Algorithmus -
MDS (Maximum Distance Separable) § Ausfall A1/A2 A1+A2+B2 A2+B1 A2+B2 A1+B1 B1 B2 A1 A2 -
Aber! Repair Problem (II) § je nach Algorithmus müssen mehrere
bis viele Chunks bewegt werden - innerhalb Storage-System tolerierbar - in Cloud ➛ Netzwerklast § Ziel: Optimum aus (n,k) und EC- Algorithmus § im Einzelfall „secret sauce“ des Herstellers A1+A2+B2 A2+B1 A2+B2 A1+B1 B1 B2 A1 A2 A1➛? A2➛? B2 A2+B2 A1+A2+B2 -
§ SUSE Enterprise Storage § teutoStack (OpenStack Swift) § vScaler
/ Quobyte § Nyriad NSULATE § … Wo läuft‘s? -
§ Erasure Coding ist ein mathematisches Verfahren, um Daten mit
Redundanz zu versehen. § Erasure Coding bringt hohe Redundanz bei vergleichsweise geringem Platz- Overhead. § EC(20,16) bedeutet, dass 16 Daten-Chunks auf 20 Speicher-Chunks verteilt werden. Es können bis zu 4 Speicher-Chunks gleichzeitig ausfallen, ohne dass Daten korrumpieren. § Die Reparatur per Erasure Coding kann CPU-intensiv sein und vergleichsweise hohe I/O-Last bzw. Netzwerklast erzeugen. Was Sie von heute mitnehmen sollten