TU Darmstadt / ULB / tuprints

Efficient and Low-Cost Fault Tolerance for Web-Scale Systems

Serafini, Marco :
Efficient and Low-Cost Fault Tolerance for Web-Scale Systems.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2010)

Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: Efficient and Low-Cost Fault Tolerance for Web-Scale Systems
Language: English

Online Web-scale services are being increasingly used to handle critical personal 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 finance. This motivates 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 efficient, available and cost effective. Although the proposed algorithms are generic, their goals are motivated by fulfilling two major needs of Web-scale systems. The first need is tolerating worst-case failures, which are also called Byzantine in the literature after the definition of [LSP82a], in order to reliably handle 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 replication 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 number of fast BFT algorithms, as for example [MA06; DGV04; KAD+07], have been proposed. These papers show the existence of an inherent tradeoff 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 replication 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 configured to tolerate one Byzantine fault and any number of crashes. Such a configuration 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 significant latency and redundancy costs in practical asynchronous systems [SS07]. This dispelled the belief that trusted components need to be combined with synchronous links to achieve cost reductions, as hinted by previous work [CNV04; Ver06] . This additional assumption makes previously proposed 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 first tier (the Web-servers) are typically more stable, standardized and less prone to vulnerabilities than application servers. The HeterTrust protocol, which is presented in this thesis, uses trusted components without assuming synchronous links. It protects data confidentiality using a number of replicas that is linear in the number of tolerated faults and has a constant time complexity. This is a significant improvement over existing approaches which do not rely on trusted component but entail quadratic redundancy costs and linear latency [YMV+03]. Furthermore, different from existing work on confidential 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 afford strong consistency guarantees such as Linearizability [HW90]. The reason is the impossibility of implementing shared ob jects, 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 available. 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 Linearizability, which allows Linearizability to be violated only for finite 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 graceful ly degrading because it uses a single failure detector and obtains different properties based on the actual strength of this failure detector, which is not known a priori. For Eventual Linearizability, a <>S failure 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 detector C . In order to complete strong operations, which must be always linearized, a <>P 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.

Alternative Abstract:
Alternative AbstractLanguage
Web-basierte Online-Dienste beinhalten in zunehmendem Maße die Verarbeitung sensibler personenbezogener Daten. Die steigende Tendenz, solche Daten in der “Cloud” zu speichern und zu verwalten, erh¨oht den Bedarf verlässlicher Realisierungen dieser Funktionen für eine steigende Anzahl Web-basierter Anwendungen, wie etwa E-Mail, Kalender, Fotoalben oder Online-Banking. Dieser Trend erklärt die zunehmende Verwendung fehlertoleranter Replikationsalgorithmen bei der Implementierung Web-basierter Anwendungen. Die zur Anwendung kommenden Implementierungen reichen von klassischer, stark konsistenter Replikation in Systemen wie Chubby [Bur06] und ZooKeeper [HKJR10] hin zu hochverfügbarer, schwach konsistenter Replikation, etwa in Amazons Dynamo [DHJ+07] oder Yahoo!s PNUTS [CRS+08]. Die vorliegende Arbeit stellt neuartige Algorithmen für fehlertolerante Replikation vor, mit dem Ziel die Effizienz, Verfügbarkeit und Wirtschaftlichkeit dieser Mechanismen zu erhöhen. Wenngleich die vorgestellten Algorithmen allgemein anwendbar sind, erfüllen sie zwei Eigenschaften, die wesentlich durch den Einsatz in Web-basierten Systemen motiviert sind. Die erste Eigenschaft ist die Toleranz von Worstcase-Fehlern, in der Literatur auch als “Byzantine” [LSP82a] bezeichnet, um eine zuverlässige Verarbeitung sensibler personenbezogener Daten zu gewährleisten. Die zweite Eigenschaft ist die Entwicklung einer geeigneten Semantik schwacher Konsistenz für Systeme, für die höchstmögliche Verfügbarkeit und geringstmöglicher Zusatzaufwand hinsichtlich Performanz und Replikation sicherzustellen, Abschwächungen der Konsistenz aber weitgehend zu vermeiden sind. Toleranz von “Byzantine” Fehlern: Die Toleranz von “Byzantine” Fehlern (englisch Byzantine Fault Tolerance, BFT) wurde kürzlich zum Gegenstand intensivierter Forschung mit dem vordergründigen Ziel, ihren implizierten Zusatzaufwand (bzgl. Performanz und erforderlicher Replikation) auf ein Maß zu reduzieren, das mit dem herkömmlicher Fehlertoleranzmechanismen vergleichbar ist. BFT wird zumeist durch die Replikation von Zustandsautomaten erzielt, indem die Illusion eines einzelnen zuverlässigen Servers durch die (für den Nutzer transparente) Koordination mehrerer unzuverlässiger Server erzeugt wird [Sch90]. Als ultimatives Ziel dieser Forschungsrichtung ist die Anwendbarkeit dieses Ansatzes für Web-basierte Systeme zu sehen [CKL+09], um die so implementierten kritischen Anwendungen vor folgenschwerem Fehlverhalten, wie es etwa in [Das] beschrieben ist, zu schützen. Die vorliegende Arbeit stellt neue Algorithmen vor, die den Performanz- und Replikationsaufwand von BFT reduzieren. Zunächst wird gezeigt, wie dieses Ziel ohne die Annahme vertrauenswürdiger Komponenten erreicht werden kann. Nach der Vorstellung des einflussreichen PBFT-Algorithmus [CL99] wurde eine Reihe schneller BFT-Algorithmen, wie zum Beispiel [MA06; DGV04; KAD+07] entwickelt. Diese Arbeiten zeigen unter der Annahme fehlerbehafteter Repliken einen inhärenten Kompromiss zwischen optimaler Redundanz und minimaler Latenz auf. In Web-basierten Systemen, in denen “Byzantine” Fehler nur selten, Ausfälle von Repliken hingegen häufig auftreten, stellt sich dieser unvermeidbare Kompromiss als problematisch heraus. Der in dieser Arbeit vorgestellte Algorithmus “Scrooge” reduziert den Replikationsaufwand schneller BFT-Replikation in Gegenwart nicht reagierender Repliken. Scrooge zeigt, dass der zusätzliche Replikationsaufwand zur Erzielung einer höheren Geschwindigkeit ausschließlich von der Anzahl der zu tolerierenden fehlerbehafteten Repliken abhängt und nicht von der Anzahl zu tolerierender Ausfälle. Als Konsequenz erzielt Scrooge optimale Robustheit für die Toleranz eines einzelnen “Byzantine”-Fehlers und einer beliebigen Anzahl von Ausfällen. Solche Szenarien sind charakteristisch für Web-basierte Systeme, in denen “Byzantine”-Fehler selten sind. Anschließend daran untersucht die vorliegende Arbeit potenzielle Vorteile der Verwendung vertrauenswürdiger Komponenten. Es wird gezeigt, dass diese zu einer signifikanten Reduktion der Latenz und durch Redundanz verursachten Kosten in anwendungstypischen asynchronen Systemen führen können [SS07]. Dies verwirft die These früherer Arbeiten [CNV04; Ver06], dass eine Kostenre- duktion durch vertrauenswürdige Komponenten zwingend die Verfügbarkeit synchroner Kommunikationskanäle erfordert. Diese zusätzliche Forderung nach Synchronität führt zu einer deutlichen Beschränkung möglicher Einsatzgebiete bestehender Lösungen, beispielsweise in Web-basierten Systemen. In dreistufig organisierten Web-basierten Systemen, zum Beispiel, kann man sich zunutze machen, dass Server in der ersten Ebene des Systems (die Webserver) üblicherweise standardisiert, stabiler und weniger fehleranfällig sind als beispielsweise Application- Server. Der “HeterTrust” Protokoll, der in dieser These eingeführt wird, erfordert eine zur Anzahl der zu tolerierenden Fehler lineare Anzahl von Repliken um die Vertraulichkeit von Daten sicher zu stellen, und hat konstante Komplexität. Dies ist eine Deutliche Verbesserung gegenüber bestehenden Ansätzen, die zwar keine vertrauenswürdigen Komponenten erfordern, aber quadratische Redundanzkosten und lineare Latenzen mit sich bringen [YMV+03]. Ebenfalls im Gegensatz zu anderen die Vertraulichkeit berücksichtigenden BFT-Ansätzen verwendet HeterTrust symmetrische Kryptoverfahren anstelle von Public-Key-Verfahren. HeterTrust beinhaltet einige interessante Ideen in den Bereichen der Spekulation [KAD+07] und der Toleranz von Denial-of-Service-Angriffen [ACKL08; CWA+09], deren Eigenschaften in weiteren Arbeiten untersucht und in unmittelbarer Folge von [SS07] publiziert wurden. In der selben Zeit wie der vorliegende Arbeit wurde die Verwendung vertrauenswürdiger Komponenten in asynchronen Systemen unabhängig in [CMSK07] untersucht. Schwache Konsistenz: Für einige Web-basierte Anwendungen ist die Zusicherung starker Konsistenzeigenschaften wie Linearisierbarkeit nicht möglich [HW90]. Die Ursache dafür liegt in der Unmöglichkeit einer Implementierung von “Shared Objects”, wie zum Beispiel Databases, in Fällen von Partitionierung oder Asynchronität [GL02]. Allerdings geben bis auf wenige Ausnahmen alle diese Systeme Linearisierbarkeit auch in Betriebsabschnitten auf, in denen weder Partitionierung, noch Asynchronität vorliegen. Da dieser Lockerung der Konsistenz für einige Anwendungen problematisch ist, konzentriert sich neuliche Forschung auf stärkere Konsistenzeigenschaften, die sich mit Hochverfügbarkeit kombinieren lassen. Die vorliegende Arbeit führt “Eventual Linearizability” als neue Konsistenzeigenschaft ein, die eine Verletzung der Linearisierbarkeit für endliche Zeitabschnitte gestattet. Sie beschreibt weiterhin Aurora, einen Algorithmus zur Sicherstellung von Linearisierbarkeit in Phasen, in denen ein einzelner Leader im System vorhanden ist. Die Leistungsfähigkeit von Aurora vermindert sich schrittweise im Falle sich verschlechternder Ausführungsbedingungen. Aurora verwendet einen einzelnen a priori nicht näher bestimmten Fehlerdetektor, von dessen Stärke aber Eigenschaften Auroras abhängen. “Eventual Linearizability” erfordert einen <>S Fehlerdetektor. In Phasen von Asynchronität, in denen die Pünktlichkeit von Nachrichten und die Präsenz eines einzelnen Leaders nicht gewährleistet werden kann, reduziert sich die von Aurora getroffene Zusicherung auf “Eventual Consistency” [FGL+96; Vog09] und “Causal Consistency” [Lam78]. Für diese Eigenschaften benötigt Aurora lediglich einen Fehlerdetektor C mit “Strongly Complete”-Eigenschaft. Für die Durchführung sogenannter “Strong Operations”, die “Linearizability” erfordern, wird ein <>P Fehlerdetektor verwendet. Dieser ist stärker als <>S, welches der schwächste Fehlerdetektor für die Implementierung von “Consensus” ist [CHT96] und somit auch “Linearizable Shared Objects”. Die vorliegende Arbeit zeigt, dass ein inhärenter Aufwand bei der Kombination von “Eventual Linearizability” und “Linearizability” existiert.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Fachbereich Informatik > Zuverlässige Eingebettete Softwaresysteme, Dependable, Embedded Systems & Software Group (DEEDS Group)
Fachbereich Informatik > Theoretische Informatik
Fachbereich Informatik > Algorithmik
Date Deposited: 23 Sep 2010 11:04
Last Modified: 07 Dec 2012 11:58
URN: urn:nbn:de:tuda-tuprints-22870
Referees: Suri, Prof. Neeraj and Rodrigues, Prof. Rodrigo
Refereed: 16 September 2010
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2287
["page:actions_header" not defined]
View Item View Item