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

Erasure Coding in Theorie und Praxis

Erasure Coding in Theorie und Praxis

Insbesondere in verteilten Storage-Infrastrukturen, häufig auch unter dem Begriff Software-defined Storage subsummiert, spielt das Erasure Coding eine wichtige und wachsende Rolle bei Sicherheit und Integrität von Daten.

Der Vortag erläutert im ersten Teil ein paar Grundideen und Begriffe zu Erasure Coding und versucht dabei, möglichst ohne Mathematik auszukommen.

Der zweite Teil beschreibt beispielhaft derzeit ü̈bliche Implementierungen von Erasure Coding und zeigt dabei auch Grenzen und Fallstricke.

Wolfgang Stief

September 18, 2019
Tweet

More Decks by Wolfgang Stief

Other Decks in Technology

Transcript

  1. ❖open minded geek & engineer ❖Dipl.-Ing.
 Elektrische Energietechnik ❖selbständig (2011)

    – sys4 AG (2012) – speicherguide.de (2019)
 technisches Marketing, Erklärbär, Projektmanagement, Vorstand ❖Cray-Cyber.org
 #vintagecomputing ❖ @stiefkind / @SpeicherStief (Twitter)
 [email protected]
 https://www.linkedin.com/in/wstief/ $ whoami STIEF consult ING
  2. $ ls ❖Motivation – Warum überhaupt Erasure Coding? ❖Historie ❖Mathematik

    ❖Begriffe und Begriffsdefinition ❖Ein einfaches Beispiel ❖Grenzen des Erasure Coding ❖Wie schaut’s in der Praxis aus? ❖Zum Weiterlernen
  3. Motivation ❖Restorezeiten/Plattengrößen
 SATA 3.0 = 6 Gb/s – 20 TB

    HDDs
 SAS-3 = 12 Gb/s ❖Datenmengen
 VM-Images, Docker, unstrukturierte Daten in Unternehmen ❖Ausfallwahrscheinlichkeiten von Platten steigt
 block error rate == konstant
 WD Ultrastar DC HC500/300/200 = 1E15 für 2/8/14 TB
 Seagate Exos = 1E16 für 300/600/900 GB ❖Ausfall >2 Disks? ❖RAID-5/6 ist ungeeignet für NVMe/Flash ❖Flexibilität (Performance vs. Zuverlässigkeit)
  4. Historie ❖Kodierungstheorie, fehlertolerante Systeme, Zahlentheorie ❖1960: Reed-Solomon, Hamming, Berlekamp-Massey, Signalübertragung,

    CD/DVD ❖1990: RAID-6, Evenodd, RDP, LDPC
 Reliable Data Protocol (RFC 908, RFC 1151, Datenkommunikation)
 Low Density Parity Check Code (DVB-S2, IEEE 802.11n) ❖2000: EC @ Netzwerk, Regenerating Codes ❖2010: Non-MDS ❖2012: Locally Repairable Code (LRC)
  5. Mathematik ❖ Lineare Algebra, Gleichungssystem, Matrizen ❖ Ingenieurdenke
 n Unbekannte

    erfordern maximal n voneinander unabhängige Gleichungen. ❖ Erasure Coding
 Redundanz gewollt, deshalb für n Unbekannte >n Gleichungen erforderlich ❖ Ziel: Gleichungen so wählen, dass Redundanz gegeben ist aber Rechenaufwand und Datentransfer so gering wie möglich ist. ❖ Erasure Coding == Forward Error Correction [ 1 −3 2 −1 0 4 2 0 1 ] 1 = 3x1 + 2x2 − x3 −2 = 2x1 − 2x2 + 4x3 0 = − x1 + 4x2 − x3
  6. Mathematik We have studied the problem of (m, n; l,

    g) LRC codes and presented some simple constructions for the case l+g < n. The size of the field is q≥mn and in some cases (when in addition, g ≤ l + 1), q ≥ n. Mario Blaum – On Locally Recoverable (LRC) Codes (Dezember 2015)
 https://www.researchgate.net/publication/287854122_On_Locally_Recoverable_LRC_Codes
  7. Begriffe Aufgabe: Daten so auf Storage Nodes verteilen, dass bei

    Ausfall einzelner Knoten alle Daten noch benutzbar bzw. rekonstruierbar sind. Daten Storage Nodes
  8. Begriffe – k, n, m – EC(n,k) Finde eine Codierung

    so, dass k gleich große Stücke Daten mit m ebenso großen Stücken Redundanz angereichert und so insgesamt n gleich große Stücke Information verteilt werden müssen: EC(n,k) k gleich große Stücke Daten insgesamt n Disks / Storage Nodes
  9. Begriffe – MDS Maximum Distance Separable (MDS) Code:
 Der verwendete

    EC-Algorithmus kann den Ausfall von m Disks rekonstruieren. k gleich große Stücke Daten insgesamt n Disks / Storage Nodes n = k + m m coding disks
  10. Begriffe – Notation ❖EC(n,k)
 n ➛ Gesamtzahl der Chunks/Platten/Nodes
 k

    ➛ Anzahl der Daten-Chunks (Shards)
 m ➛ Anzahl Codierungs-Chunks (m=n-k) ❖Beispiel: EC(20,16)
 16 Daten-Chunks, 4 Coding-Chunks
 MDS = 4 (n-k)
 Overhead = 20/16 = 1,25 (n/k) k n m
  11. Ein einfaches Beispiel ❖ EC(4,2)
 2 Data Shards, 2 Coding

    Shards
 MDS = 2
 Overhead = 2 A1+A2 A2 A1 A1 A2 A A1+2A2 split code
  12. Repair Problem ❖ u. U. müssen viele (und große) Chunks

    bewegt werden
 ➛ tolerierbar innerhalb Storage-System
 ➛ Netzwerklast @ RZ/Cloud ❖ Ziel: Optimum aus (n,k) und EC- Algorithmus ❖ Erweiterung um LRC
 Locally Repairable Codes
 == Locally Decodable Codes A2+B1 A2+B2 A1+B1 B1 B2 A1 A2 A1➛? A2➛? B2 A2+B2 A1+A2+B2 A1+A2+B2
  13. Locally Repairable Code – LRC ❖Lokale Parity 
 nur gültig

    innerhalb des Nodes ❖Globale Parity
 für Erasures > lokal ❖Ausfall einer einzelnen Platte ist sehr viel wahrscheinlicher, als Ausfall mehrerer, verteilter Platten. ❖Lokale Reparatur braucht keine globale Bandbreite! LP2 LP3 LP1 D2 D4 D1 D3 LP4 D6 D8 D5 D7 GP1 GP2
  14. Erasure Coding pro/contra ✓ hohe Redundanz bei vertretbarem Aufwand
 mehrfache

    Replikation braucht vielfachen Platz ✓ robuste Skalierung über viele Nodes
 RAID funktioniert nur innerhalb eines Nodes ✓ Gut geeignet für Object Storage und Multimedia-Inhalte - Repair Problem - Nicht geeignet für kleine Dateien
 häufig Untergrenze für Filesize implementiert, darunter Replikation anstatt EC
  15. Implementierungen ❖Kommerziell vs. OpenSource
 As usual: kommerzielle Hersteller machen immer

    “secret sauce”, kaum Details einsehbar. ❖NetApp
 EC == RAID-6, NetApp StorageGRID 11.2 Manual
 https://library.netapp.com/ecm/ecm_download_file/ECMLP2848253 ❖Nyriad NSULATE
 High Parity Erasure Coding (max. 255 Parity Disks), Erasure Coding in GPU
 https://www.youtube.com/watch?v=BVji7uENZyU&t=2s ❖Scality RING
 EC immer auf 12 Disks, Verhältnis Data/Parity darin wählbar, default EC(12,9)
  16. Implementierungen ❖Hadoop HDFS
 EC by design
 Xorbas – LRC-Erweiterung für

    Hadoop (2013, u. a. Facebook) ❖Ceph
 Verschiedene Algorithmen mit individuell anpassbaren Settings
 https://docs.ceph.com/docs/mimic/rados/operations/erasure-code/ ❖DRBD
 Erasure coding. DRBD will be able to erasure code and distribute its data. This provides the same functionality as RAID5/6, but with an arbitrary number of parity nodes. The result is lower disk usage with similar redundancy characteristics.
 [DRBD-user] drbd-10.0.0a1 (Mailinglist, 2019-08-05)
 https://lists.linbit.com/pipermail/drbd-user/2019-August/025180.html ❖Quobyte, Rubrik, Backblaze, Datrium, Hedvig, RozoFS, …
  17. ???? ❖Google Compute Engine
 “Cloud Storage is designed for 99.999999999%

    (11 9's) annual durability, which is appropriate for even primary storage and business-critical applications. This high durability level is achieved through erasure coding that stores data pieces redundantly across multiple devices located in multiple availability zones.”
 https://cloud.google.com/storage/docs/faq ❖Amazon S3 ❖Microsoft Azure ❖DigitalOcean Implementierungen – Cloud
  18. Zum Weiterlernen ❖Erasure Codes for Large Scale Distributed Storage
 https://www.youtube.com/watch?v=TPZyW_CnXGQ

    ❖Erasure coding for data storage
 https://www.youtube.com/watch?v=3R6K7LnqLuk ❖Codierungstheorie
 Ralph-Hardo Schulz, Vieweg, 2003 ❖Fehlerkorrigierende Codes
 Olaf Manz, Springer, 2016 ❖Introduction to Error-Correcting Codes
 Michael Purser, Artech House, 1994 ❖Introduction to the Theory of Error-Correcting Codes
 Vera Pless, Wiley, 1998