Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Erasure Coding — Was ist das eigentlich genau?

Erasure Coding — Was ist das eigentlich genau?

Überblick/Einführung zu Erasure Coding.

Wolfgang Stief

November 27, 2018
Tweet

More Decks by Wolfgang Stief

Other Decks in Technology

Transcript

  1. § Ganz ohne Mathematik geht es nicht Historie, Grundlagen, Begriffe

    § Einsatzgebiete und Grenzen des Erasure Coding Rechenbeispiele und das Repair Problem § Anwendungen und Literaturhinweise Agenda
  2. § 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?
  3. Grundlagen Aufgabe: Daten so auf Storage Nodes verteilen, dass bei

    Ausfall von einzelnen Knoten alle Daten noch benutzbar bzw. rekonstruierbar sind. Daten Storage Nodes
  4. Grundlagen Aufgabe: Daten so auf Storage Nodes verteilen, dass bei

    Ausfall von einzelnen Knoten alle Daten noch benutzbar bzw. rekonstruierbar sind. Daten Storage Nodes
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. § 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
  11. § 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?
  12. § 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
  13. 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
  14. 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
  15. § SUSE Enterprise Storage § teutoStack (OpenStack Swift) § vScaler

    / Quobyte § Nyriad NSULATE § … Wo läuft‘s?
  16. § 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