Efficient and low-cost fault tolerance for web-scale systems [Elektronische Ressource] / vorgelegt von Marco Serafini

Marco Serafini

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2010
• Nombre de lectures: 29
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

E cient and Low-Cost Fault Tolerance
for Web-Scale Systems
Vom Fachbereich Informatik der Technischen Universit at Darmstadt
genehmigte
Dissertation
zur Erlangung des akademischen Grades
eines Doktor rerum naturalium (Dr. rer. nat.)
vorgelegt von
Dott. Marco Sera ni
aus Arezzo, Italien
Referenten:
Prof. Neeraj Suri, Ph.D.
Prof. Rodrigo Rodrigues, Ph.D.
Datum der Einreichung: 17. Juni 2010
Datum der mundlic hen Prufung: 16. September 2010
Darmstadt 2010
D17iiSummary
Online Web-scale services are being increasingly used to handle critical per-
sonal information. The trend towards storing and managing such information on
the \cloud" is extending the need for dependable services to a growing range of Web
applications, from emailing, to calendars, storage of photos, or nance. This moti-
vates the increased adoption of fault-tolerant replication algorithms in Web-scale
systems, ranging from classic, strongly-consistent replication in systems such as
Chubby [Bur06] and ZooKeeper [HKJR10], to highly-available weakly-consistent
+ +replication as in Amazon’s Dynamo [DHJ 07] or Yahoo!’s PNUTS [CRS 08].
This thesis proposes novel algorithms to make fault-tolerant replication more
e cient, available and cost e ective. Although the proposed algorithms are
generic, their goals are motivated by ful lling two major needs of Web-scale sys-
tems. The rst need is tolerating worst-case failures, which are also called Byzan-
tine in the literature after the de nition of [LSP82a], in order to reliably han-
dle critical personal information. The second need is investigating proper weak
consistency semantics for systems that must maximize availability and minimize
performance costs and replication costs without relaxing consistency unnecessarily.
Byzantine-Fault Tolerance: There has been a recent burst of research on
Byzantine-Fault Tolerance (BFT) to make it have performance and replication
costs that are feasible and comparable to the fault-tolerance techniques already
in use today. BFT is typically achieved through state-machine replication, which
implements the abstraction of a single reliable server on top of multiple unreliable
replicas [Sch90]. This line of research ultimately aimed at showing the feasibility
+of this approach for Web-scale systems [CKL 09] to protect these critical systems
from catastrophic events such as [Das].
This thesis proposes novel algorithms to reduce the performance and replica-
tion costs of BFT. First, the thesis shows how to reduce the cost of BFT without
assuming trusted components. After the seminal PBFT algorithm [CL99], a num-
+ber of fast BFT algorithms, as for example [MA06; DGV04; KAD 07], have been
proposed. These papers show the existence of an inherent tradeo between optimal
redundancy and minimal latency in presence of faulty replicas. This is problematic
in Web-scale systems, where Byzantine faults are very rare but where unresponsive
(benign) replicas are commonplace. This thesis proposes a novel algorithm, called
Scrooge, which reduces the replication costs of fast BFT replication in presence of
unresponsive replicas. Scrooge shows that the additional costs needed
for being fast in presence of faulty replicas are only dependent on the number of
tolerated Byzantine faults, and not on the number of tolerated crashes. As an
implication of this result, Scrooge is optimally resilient when it is con gured to
tolerate one Byzantine fault and any number of crashes. Such a con guration is
quite common since Byzantine faults are relatively unlikely to happen.
This thesis then explores the advantages of using trusted components. It shows
that these can lead to signi cant latency and redundancy costs in practical asyn-
chronous systems [SS07]. This dispelled the belief that trusted components need
iiito be combined with synchronous links to achieve cost reductions, as hinted by
previous work [CNV04; Ver06] . This additional assumption makes previously pro-
posed algorithms unpractical in many settings, including Web-scale systems. In
three-tiered Web-scale systems, for example, one could just leverage the fact that
servers in the rst tier (the Web-servers) are typically more stable, standardized
and less prone to vulnerabilities than application servers. The HeterTrust proto-
col, which is presented in this thesis, uses trusted components without assuming
synchronous links. It protects data con dentiality using a number of replicas that
is linear in the number of tolerated faults and has a constant time complexity. This
is a signi cant improvement over existing approaches which do not rely on trusted
+component but entail quadratic redundancy costs and linear latency [YMV 03].
Furthermore, di erent from existing work on con dential BFT, HeterTrust uses
only symmetric-key cryptography instead of public-key signatures. HeterTrust
+features some interesting ideas related to speculation [KAD 07] and tolerance to
+denial-of-service attacks [ACKL08; CWA 09] that have been further developed by
work published immediately after [SS07]. In parallel to this thesis’ work, the use
of trusted components in asynchronous systems was also independently explored
in [CMSK07].
Weak consistency: Some replicated Web-scale applications cannot a ord
strong consistency guarantees such as Linearizability [HW90]. The reason is the
impossibility of implementing shared objects, as for example databases, that are
available in presence of partitions or asynchrony [GL02]. With few exceptions,
however, all these systems relax Linearizability even in periods when there are no
partitions nor asynchrony and no relaxation is needed to keep the system avail-
able. Since this relaxation is problematic for many applications, recent research
is focusing on stronger consistency guarantees which can be combined with high
availability.
This thesis introduces a novel consistency property, called Eventual Lineariz-
ability, which allows Linearizability to be violated only for nite windows of time.
This thesis also describes Aurora, an algorithm ensuring Linearizability in periods
when a single leader is present in the system. Aurora is gracefully degrading be-
cause it uses a single failure detector and obtains di erent properties based on the
actual strength of this failure detector, which is not known a priori. For Eventual
Linearizability, a S detector is needed. In periods of asynchrony when
links are untimely and no single leader is present, Aurora gracefully degrades to
+Eventual Consistency [FGL 96; Vog09] and Causal Consistency [Lam78]. For
these property, Aurora only relies on a strongly complete failure detectorC. In
order to complete strong operations, which must be always linearized, aP failure
detector is used. This is stronger than S, the weakest failure detector needed to
implement consensus [CHT96], and thus linearizable shared objects. This thesis
shows that there exists an inherent cost in combining Eventual Linearizability with
Linearizability.
ivKurzfassung
Web-basierte Online-Dienste beinhalten in zunehmendem Ma e die Verar-
beitung sensibler personenbezogener Daten. Die steigende Tendenz, solche Daten
in der \Cloud" zu speichern und zu verwalten, erh oht den Bedarf verl asslicher
Realisierungen dieser Funktionen fur eine steigende Anzahl Web-basierter An-
wendungen, wie etwa E-Mail, Kalender, Fotoalben oder Online-Banking. Dieser
Trend erkl art die zunehmende Verwendung fehlertoleranter Replikationsalgorith-
men bei der Implementierung Web-basierter Anwendungen. Die zur Anwen-
dung kommenden Implementierungen reichen von klassischer, stark konsisten-
ter Replikation in Systemen wie Chubby [Bur06] und ZooKeeper [HKJR10] hin
zu hochverfugbarer, schwach konsistenter Replikation, etwa in Amazons Dynamo
+ +[DHJ 07] oder Yahoo!s PNUTS [CRS 08].
Die vorliegende Arbeit stellt neuartige Algorithmen fur fehlertolerante Replika-
tion vor, mit dem Ziel die E zienz, Verfugbark eit und Wirtschaftlichkeit dieser
Mechanismen zu erh ohen. Wenngleich die vorgestellten Algorithmen allgemein
anwendbar sind, erfullen sie zwei Eigenschaften, die wesentlich durch den Einsatz
in Web-basierten Systemen motiviert sind. Die erste Eigenschaft ist die Toler-
anz von Worstcase-Fehlern, in der Literatur auch als \Byzantine" [LSP82a] beze-
ichnet, um eine zuverl assige Verarbeitung sensibler personenbezogener Daten zu
gew ahrleisten. Die zweite Eigenschaft ist die Entwicklung einer geeigneten Se-
mantik schwacher Konsistenz fur Systeme, fur die h ochstm ogliche Verfugbark eit
und geringstm oglicher Zusatzaufwand hinsichtlich Performanz und Replikation
sicherzustellen, Abschw achungen der Konsistenz aber weitgehend zu vermeiden
sind.
Toleranzvon\Byzantine"Fehlern: Die Toleranz von \Byzantine" Fehlern
(englisch Byzantine Fault Tolerance, BFT) wurde kurzlic h zum Gegenstand in-
tensivierter Forschung mit dem vordergrundigen Ziel, ihren implizierten Zusatza-
ufwand (bzgl. Performanz und erforderlicher Replikation) auf ein Ma zu re-
duzieren, das mit dem herk ommlicher Fehlertoleranzmechanismen vergleichbar ist.
BFT wird zumeist durch die Replikation von Zustandsautomaten erzielt, indem die
Illusion eines einzelnen zuverl assigen Servers durch die (fur den Nutzer transpar-
ente) Koordination mehrerer unzuverl assiger Server erzeugt wird [Sch90]. Als ul-
timatives Ziel dieser