Show simple item record

2012-11-02Dissertation DOI: 10.18452/16621
Consistent key-based routing in decentralized and reconfigurable data services
dc.contributor.authorHoegqvist, Mikael
dc.date.accessioned2017-06-18T11:51:44Z
dc.date.available2017-06-18T11:51:44Z
dc.date.created2012-11-28
dc.date.issued2012-11-02
dc.identifier.urihttp://edoc.hu-berlin.de/18452/17273
dc.description.abstractSkalierbares schlüssel-basiertes Routing in verteilten Systemen ist eine Methode zur Weiterleitung von Nachrichten zu den für die Partition verantwortlichen Maschinen. Diese Technik findet Verwendung in Key-Value Speichersystemen, Content Distribution Networks oder auch beim Media Streaming. Einer der Gründe für die Verbreitung ist die Einfachheit der Routingabstraktion, bei welcher der Entwickler sich nicht um die Details des Gruppenmanagements oder Datenreplikation kümmern muss. Auf der anderen Seite sind die meisten schlüssel-basierten Routingverfahren optimistische Verfahren, bei denen der Datenzugriff keine strenge Konsistenz bietet. In dieser Arbeit präsentieren wir das System Recode mit dem schlüssel-basierten Routingabstraktion routecast, welches eine strengere Zugriffssemantik ermöglicht. Dabei garantiert routecast, dass Nachrichten eines bestimmten Schlüssels in der gleichen Reihenfolge an alle Replikate geliefert werden. Mit Hilfe dieser strengeren Garantien können auch Anwendungen wie Koordinations- oder Metadatendienste bzw. konsistente Speichersysteme das schlüssel-basierte Routing verwenden. Recode ist außerdem rekonfigurierbar bei Veränderungen der zur Verfügung stehenden Maschinen sowie bei Auslastungsänderung. Es ist ein komplett dezentralisiertes System und enthält damit keinen single-point of failure oder Systemengpass. Die drei Hauptbeiträge der Arbeit sind 1) die Abstraktion der Gruppenkommunikation unter Verwendung von Primary/Backup mit Leases für ein failover des Primary, 2) die Entwicklung und die Algorithmen der routcast-Primitive, 3) Mechanismen zur atomaren Rekonfiguration des dezentralen Schlüsselraumes. Um die Einfachheit unseres Ansatzes zu betonen, beschreiben wir außerdem drei verschiedene Anwendungen aufbauend auf Recode. Abschließend zeigen wir durch die Evaluation von Recode in einer Cluster-Umgebung die Leistungsfähigkeit.ger
dc.description.abstractScalable key-based routing in distributed systems, where a mes- sage is forwarded towards a machine responsible for a partition in a large key space, has been used in many services such as key-value stores, content distribution networks and media streaming. This success can mainly be attributed to the simplicity of the route ab- straction, a developer does not need to care about the mechanisms for membership management, load balancing or data replication. A limitation, however, is that most key-based routing solutions are best-effort, which means that only eventually consistent data access is possible. This thesis presents a system (Recode) with a key-based routing primitive called routecast which provides strong delivery semantics. More specifically, routecast guarantees that a message for a key is delivered in the same total order at a set of replicas. With stronger guarantees, applications such as coordination and metadata services as used in large storage systems or consistent key-value stores can use key-based routing. Additionally, Recode aims to be both re- configurable, to handle changes to the machines running the service and updates to the workload, and fully decentralized which means there is no single point of failure or bottleneck. We make three main contributions in this thesis: 1) a group com- munication abstraction using primary/backup with leases for pri- mary fail-over, 2) the design and algorithms of the routecast-primitive and, 3) mechanisms for atomic reconfiguration of a decentralized key space. Each part of the system is broken up into modules and presented with a specification and a set of algorithms. To validate the simplicity claim, we describe how to implement three different applications on top of Recode. Finally, we evaluate Recode in a cluster environment and show that the performance is competitive.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
dc.rightsNamensnennung - Keine kommerzielle Nutzung - Keine Bearbeitung
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/de/
dc.subjectKonsistenzger
dc.subjectVerteilte systemeger
dc.subjectGruppenkommunikationger
dc.subjectSchlüssel-basiertes Routingger
dc.subjectconsistencyeng
dc.subjectdistributed systemseng
dc.subjectgroup communicationeng
dc.subjectkey-based routingeng
dc.subject.ddc004 Informatik
dc.titleConsistent key-based routing in decentralized and reconfigurable data services
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-100206145
dc.identifier.doihttp://dx.doi.org/10.18452/16621
dc.identifier.alephidBV040596323
dc.date.accepted2012-06-04
dc.contributor.refereeReinefeld, Alexander
dc.contributor.refereeHaridi, Seif
dc.contributor.refereeSchiller, Jochen
dc.subject.dnb28 Informatik, Datenverarbeitung
dc.subject.rvkAN 95400
dc.subject.rvkST 200
local.edoc.pages136
local.edoc.type-nameDissertation
bua.departmentMathematisch-Naturwissenschaftliche Fakultät II

Show simple item record