Kurzbeschreibung
In parallelen Speichersystemen (RAID) werden einfache Paritätskodes eingesetzt um bei Ausfall einzelner Plattenspeicher die Nutzerdaten rekonstruieren zu können. Es existieren jedoch auch komplexere Algorithmen, die bei höherem Berechnungsaufwand eine bessere Datensicherheit bieten. Diese können nicht nur in lokalen sondern auch in verteilten Speichersystemen angewandt werden.
Zeit und Ort
Einführung und Themenvergabe (Folien): 20.04.2009, 11-13 Uhr, Raum RUD25 4.112
Das Seminar findet in drei Blöcken statt.
Block 1: Do. 14.05., 13-17 Uhr (ZIB, Wegbeschreibung), Seminarraum 2006 (Eingang Rundbau)
Block 2: Mi. 03.06., 13-17 Uhr (ZIB, Wegbeschreibung), Seminarraum 2006 (Eingang Rundbau)
Block 3: Do. 02.07., 13-17 Uhr (RUD 26, Raum 1'305)
Leistungsnachweis
Seminarschein Technische Informatik
Vortragsthemen
1. Motivation: Ausfälle in Speichersystemen
Wo und wie treten Fehler auf, welche Arten sind häufiger? Wie wird RAID allgemein eingesetzt? Was ist dabei das Problem?
Hard Disk Drives: The Good, The Bad and The Ugly
Disk failures in the real world: What does an
MTTF of 1000000 hours mean to you?
Failure trends in a large disk drive
population
2. RAID-Technologie (Martin Schumann)
Was ist RAID? Welche RAID-Levels gibt es? Eigenschaften bzgl. Fehlertoleranz und Performance.
A Case for Redundant Arrays of Inexpensive Disks (RAID)
Raid-High-Performance, Reliable Secondary Storage
3. XOR-Codes und EvenOdd
Redundante Datenblöcke können mit Hilfe von XOR-Verknüpfungen (Parität) zwischen Codewörtern gebildet werden. Diese Rechenoperation ist auf Mikroprozessoren meist direkt verfügbar und daher sehr effizient. Es gibt unterschiedliche Arten, die Parität über die Datenplatten zu berechnen. In diesen Artikeln werden zwei Varianten vorgestellt: mehrdimensionale XOR-Codes und der EvenOdd-Code.
Coding Techniques for handling failures in large disk arrays
EvenOdd: An optimal scheme for tolerating double disk failures in RAID architectures
Modified Low-Density MDS Array Codes for Tolerating Double Disk Failures in Disk Arrays
4. Erweiterte XOR-Codes (Gerd Wittchen)
Der EvenOdd-Code wurde für mehr als zwei Redundanzspeicher verallgemeinert. In diesem Abschnitt geht es um Codes, die auf EvenOdd aufbauen und drei oder mehr Fehler tolerieren.
MDS-Array-Codes with Independent Parity Symbols
On Lowest-Density MDS Codes
STAR: An Efficient Coding Scheme for Correcting Triple Storage Node Failures
5. Reed-Solomon-Codes (Stefan Keidel)
Verwendung von Reed-Solomon Codes in Plattenspeichersystemen. Spezielle Operationen
in Galois-Feld-Arithmetik.
Plank 97, A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems
Plank 03, Erratum
zu beachten
6. Cauchy Reed-Solomon
Cauchy Reed-Solomon ist die Übersetzung des klassischen RS-Verfahrens (basierend auf Galois-Feld Arithmetik) in ein Verfahren, was nur mit XOR Verknüpfungen der Bits arbeitet.
Blomer 95, An XOR-based Erasure-Resilient Coding Scheme
Plank 05, Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage Applications
7. LDPC-Codes (Stefan Curow)
LDPC codes (low-density parity check codes) sind besonders gut für die Verwendung in weit-verteilten Speichersystemen geeignet.
Plank 04, Small Parity-Check Erasure Codes - Exploration and Observations
Plank 03, A Practical Analysis of Low-Density Parity-Check Erasure Codes for Wide-Area Storage Applications
8. HoVer- und Weaver-Codes (Christoph Waschke)
HoVer- und Weaver-Codes erfüllen nicht mehr ganz die MDS-Eigenschaft (MDS: maximum distance separable; optimaler Code). Es ist interessant, welche Vorteile sie dennoch haben: Kodierungsperformance, Flexibilität, Art der verwendeten Operationen.
Haffner 05, HoVer Erasure Codes For Disk Arrays
Haffner 06, WEAVER Codes: Highly Fault Tolerant Erasure Codes for Storage Systems
Rao 06, Reliability for Networked Storage Nodes
9. MEL- minimal erasure list (Philipp Hussels)
Wylie 07, Determining fault tolerance of XOR-based erasure codes efficiently
Greenan 08, Reliability of flat XOR-based erasure codes on heterogeneous devices
10. Schnell Downloads mit Tornado-Codes (Bert Münnich)
Byers 99, Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads
Luby, 01, Efficient Erasure Correcting Codes
11. Liberation-Codes (Michael Fiedler)
Plank 07, A new MDS Erasure Code for RAID-6
12. Hochverfügbare Reed-Solomon Datenstruktur
LH*RS: A High-Availability Scalable Distributed Data Structure using Reed Solomon Codes
LH*g: A high-availability scalable distributed data structure by
recorded grouping
13. Erasure Codes für P2P-Systeme (Robert Maier)
Lacan 05, Content-Access QoS in Peer-to-Peer Networks Using a Fast MDS Erasure Code
Williams 07, Redundancy Management for P2P Storage
14. Vergleich von Erasure Codes mit Replikation für P2P-Systeme (Arite Lauschke)
High Availability in DHTs: Erasure Coding vs. Replication
Erasure Coding vs. Replication: A quantitative comparison
15. Secret Sharing (Giso Hegenbarth)
Shamir 79, Secret Sharing: How to share a secret
Rabin, Efficient Dispersal of Information for Security, Load Balancing and Fault tolerance
McEliece 81, On sharing secrets and Reed-Solomon codes
16. Zuverlässige Datenspeicherung in großen Speichersystemen
Reliability mechanisms for very large storage systems
Using Erasure Codes Efficiently for Storage in a Distributed System
A Decentralized Algorithm for Erasure-Coded Virtual Disks
Efficient byzantine-tolerant erasure-coded storage
17. Optionale Literatur
Hier sind weitere interessante Paper aufgelistet, die Sie abhängig vom Thema zur Vertiefung verwenden sollten. Weitere Paper gibt es online in bekannten Suchportalen wie Citeseer oder Google Schoolar:
Citeseer
Google Schoolar
On Optimizing XOR-based Codes for Fault-Tolerant Storage Applications
X-code: MDS array codes with optimal encoding
A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage
Networt Coding: Decentralized erasure codes for distributed networked storage