ClusterRAID [Elektronische Ressource] : architecture and prototype of a distributed fault-tolerant mass storage system for clusters / vorgelegt von Arne Wiebalck

INAUGURAL - DISSERTATIONzurErlangung der Doktorw rdederNaturwissenschaftlich-Mathematischen Gesamtfakult tderRuprecht-Karls-Universit tHeidelbergvorgelegt vonDiplom Physiker Arne Wiebalckaus BremerhavenTag der m ndlichen Pr fung: 29. Juni 2005ClusterRAID: Architecture and Prototype of aDistributed Fault-TolerantMass Storage System for ClustersGutachter: Prof. Dr. Volker LindenstruthGutachter: Prof. Dr. Thomas LudwigClusterRAID: Architektur und Prototyp eines verteilten fehlertolerantenMassenspeicher-Systems f r ClusterIn den letzten Jahren haben sich Cluster aus Standard-Komponenten in vielen Bereichen als do-minante Architektur f r Hochleistungsrechner durchgesetzt. Wegen ihres besseren Preis-Leistungs-verh ltnisses haben diese Systeme, die typischerweise aus Standard-PCs oder Workstations und ei-nem Verbindungsnetzwerk aufgebaut sind, die traditionell verwendeten, integrierten Supercomputer-Architekturen verdr ngt. Aufgrund des zu beobachtenden Paradigmen-Wechsels von rein rechen-intensiven hin zu Eingabe/Ausgabe-intensiven Anwendungen werden die in Clustern verwendetenMassenspeichersysteme zu einer immer wichtigeren Komponente. Da sich bisher kein Standard f rdie Nutzung des verteilten Massenspeichers in Clustern durchsetzen konnte, ist vor allem der inh -renten Unzuverl ssigkeit der zugrundeliegenden Komponenten zuzuschreiben.
Publié le : samedi 1 janvier 2005
Lecture(s) : 18
Tags :
Source : ARCHIV.UB.UNI-HEIDELBERG.DE/VOLLTEXTSERVER/VOLLTEXTE/2005/5624/PDF/CLUSTERRAID_PHD_WIEBALCK.PDF
Nombre de pages : 173
Voir plus Voir moins

INAUGURAL - DISSERTATION
zur
Erlangung der Doktorw rde
der
Naturwissenschaftlich-Mathematischen Gesamtfakult t
der
Ruprecht-Karls-Universit t
Heidelberg
vorgelegt von
Diplom Physiker Arne Wiebalck
aus Bremerhaven
Tag der m ndlichen Pr fung: 29. Juni 2005ClusterRAID: Architecture and Prototype of a
Distributed Fault-Tolerant
Mass Storage System for Clusters
Gutachter: Prof. Dr. Volker Lindenstruth
Gutachter: Prof. Dr. Thomas LudwigClusterRAID: Architektur und Prototyp eines verteilten fehlertoleranten
Massenspeicher-Systems f r Cluster
In den letzten Jahren haben sich Cluster aus Standard-Komponenten in vielen Bereichen als do-
minante Architektur f r Hochleistungsrechner durchgesetzt. Wegen ihres besseren Preis-Leistungs-
verh ltnisses haben diese Systeme, die typischerweise aus Standard-PCs oder Workstations und ei-
nem Verbindungsnetzwerk aufgebaut sind, die traditionell verwendeten, integrierten Supercomputer-
Architekturen verdr ngt. Aufgrund des zu beobachtenden Paradigmen-Wechsels von rein rechen-
intensiven hin zu Eingabe/Ausgabe-intensiven Anwendungen werden die in Clustern verwendeten
Massenspeichersysteme zu einer immer wichtigeren Komponente. Da sich bisher kein Standard f r
die Nutzung des verteilten Massenspeichers in Clustern durchsetzen konnte, ist vor allem der inh -
renten Unzuverl ssigkeit der zugrundeliegenden Komponenten zuzuschreiben.
Die vorliegende Arbeit beschreibt die Architektur und eine Prototypen-Implementierung eines ver-
teilten, fehlertoleranten Massenspeichersystems f r Cluster. Die grundlegende Idee der Architektur
ist es, die lokale Festplatte eines Clusterknotens zuverl ssig zu machen, ohne dabei die Schnittstel-
le f r das Betriebssystem oder die Anwendung zu ver ndern. Hierbei werden fehler-korrigierende
Codes eingesetzt, die es erm glichen, die Anzahl der zu tolerierenden Fehler und somit die Zuver-
l ssigkeit des Gesamtsystems einzustellen. Das Anordnungsschema f r die Datenbl cke innerhalb
des Systems ber cksichtigt das Zugriffsverhalten einer ganzen Klasse von Applikationen und kann
so die erforderlichen Netzwerkzugriffe auf ein Minimum reduzieren. Gr ndliche Messungen und
Funktionstests des Prototypen, sowohl allein als auch im Zusammenwirken mit lokalen und verteil-
ten Dateisystemen, belegen die Validit t des Konzeptes.
ClusterRAID: Architecture and Prototype of a Distributed Fault-Tolerant Mass Storage
System for Clusters
During the past few years clusters built from commodity off-the-shelf (COTS) components have
emerged as the predominant supercomputer architecture. Typically comprising a collection of stan-
dard PCs or workstations and an interconnection network, they have replaced the traditionally used
integrated systems due to their better price/performance ratio. As paradigms shift from mere com-
puting intensive to I/O intensive applications, mass storage solutions for cluster installations become
a more and more crucial aspect of these systems. The inherent unreliability of the underlying com-
ponents is one of the reasons why no system has been established as a standard storage solution for
clusters yet.
This thesis sets out the architecture and prototype implementation of a novel distributed mass stor-
age system for commodity off-the-shelf clusters and addresses the issue of the unreliable constituent
components. The key concept of the presented system is the conversion of the local hard disk drive
of a cluster node into a reliable device while preserving the block device interface. By the deploy-
ment of sophisticated erasure-correcting codes, the system allows the adjustment of the number of
tolerable failures and thus the overall reliability. In addition, the applied data layout considers the
access behaviour of a broad range of applications and minimizes the number of required network
transactions. Extensive measurements and functionality tests of the prototype, both stand-alone and
in conjunction with local or distributed le systems, show the validity of the concept.Contents
1. Introduction 15
1.1. Commodity Components in Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.1. Hard Disk Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.2. Processors and Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.3. Networks and Busses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.4. Cluster Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2. Requirements in Science and Industry . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1. High Energy Physics Experiments . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.2. The Google Web Search Engine . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3. Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2. Distributed Storage for Clusters 21
2.1. SAN, NAS, and RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2. Networked File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1. NFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2. DAFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.3. MOSIX, MFS, and MOPI . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.4. PVFS and Lustre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.5. GPFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.6. Google File System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3. Integrated Mass Storage Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1. HPSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2. CASTOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.3. Storage Tank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4. Distributed Block Level Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1. NBD and ENBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.2. DRBD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.3. RAID-X OSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4.4. Petal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.5. Tertiary Disk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.6. DRAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5. Distributed RAID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6. The need for something different . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7Contents
3. ClusterRAID Architecture 47
3.1. Design Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Overview and Functionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3. Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4. Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5. Fault-tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.1. Basic de nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.2. Reliability Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5.3. The Reliability of the ClusterRAID . . . . . . . . . . . . . . . . . . . . . . 67
4. Error and Erasure Correcting Codes 73
4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2. Hamming Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3. BCH Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4. Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.5. Vandermonde-based Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . 83
4.6. Other Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5. ClusterRAID Implementation 87
5.1. Kernel Interfacing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.1. The Main Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2.2. The Codec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.3. The XOR Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.3. Functional Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.3.1. Read Requests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3.2. Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.3.3. Degraded Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.4. Additional Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.1. Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.2. Copy Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.4.3. Kernel Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.4.4. Private . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4.5. Check Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.5. Monitoring, Debugging, Control, and Con guration . . . . . . . . . . . . . . . . . 113
5.5.1. Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.5.2. Driver Control and Con guration . . . . . . . . . . . . . . . . . . . . . . . 115
5.5.3. ClusterRAID and Startup . . . . . . . . . . . . . . . . . . . . 116
6. Prototyping and Benchmarks 121
6.1. The Test Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.1.1. The Hard Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.1.2. The Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.1.3. The Network Block Device . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8Contents
6.2. ClusterRAID Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.2.1. Local Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.2.2. Remote Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2.3. System Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3. Functional Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.3.1. Online Repair and Node Replacement . . . . . . . . . . . . . . . . . . . . . 141
6.3.2. Stability and Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.3.3. ClusterRAID and MFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4. Implemented Optimizations and Possible Improvements . . . . . . . . . . . . . . . 146
6.4.1. Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.4.2. Hardware Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7. Conclusion and Outlook 151
A. Appendix 153
4A.1. The Galois Field GF(2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.2. A Production Quality Distributed RAID . . . . . . . . . . . . . . . . . . . . . . . . 153
A.3. The DWARW Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
A.4. The NetIO Network Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
A.5. MOSIX related Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Bibliography 159
9

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.