TY - THES A1 - Kruber, Nico T1 - DHT Load Balancing with Estimated Global Information N2 - One of the biggest impacts on the performance of a Distributed Hash Table (DHT), once established, is its ability to balance load among its nodes. DHTs supporting range queries for example suffer from a potentially huge skew in the distribution of their items since techniques such as consistent hashing can not be applied. Thus explicit load balancing schemes need to be deployed. Several such schemes have been developed and are part of recent research, most of them using only information locally available in order to scale to arbitrary systems. Gossiping techniques however allow the retrieval of fairly good estimates of global information with low overhead. Such information can then be added to existing load balancing algorithms that can use the additional knowledge to improve their performance. Within this thesis several schemes are developed that use global information like the average load and the standard deviation of the load among the nodes to primarily reduce the number of items an algorithm moves to achieve a certain balance. Two novel load balancing algorithms have then been equipped with implementations of those schemes and have been simulated on several scenarios. Most of these variants show better balance results and move far less items than the algorithms they are based on. The best of the developed algorithms achieves a 15-30% better balance and moves only about 50-70% of the number of items its underlying algorithm moves. This variation is also very robust to erroneous estimates and scales linearly with the system size and system load. Further experiments with self-tuning algorithms that set an algorithm’s parameter according to the system’s state show that even more improvements can be gained if additionally applied. Such a variant based on the algorithm described by Karger and Ruhl shows the same balance improvements of 15-30% as the variant above but reduces the number of item movements further to 40-65%. KW - Peer-to-Peer KW - Verteilte Hashtabelle (DHT) KW - Lastverteilung KW - Gossiping KW - Peer-to-Peer KW - Distributed Hash Table (DHT) KW - Load Balancing KW - Gossiping Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11514 ER - TY - GEN A1 - Moser, Monika A1 - Haridi, Seif A1 - Shafaat, Tallat A1 - Schütt, Thorsten A1 - Högqvist, Mikael A1 - Reinefeld, Alexander T1 - Transactional DHT Algorithms N2 - We present a framework for transactional data access on data stored in a DHT. It allows to atomically read and write items and to run distributed transactions consisting of a sequence of read and write operations on the items. Items are symmetrically replicated in order to achieve durability of data stored in the SON. To provide availability of items despite the unavailability of some replicas, operations on items are quorum-based. They make progress as long as a majority of replicas can be accessed. Our framework processes transactions optimistically with an atomic commit protocol that is based on Paxos atomic commit. We present algorithms for the whole framework with an event based notation. Additionally we discuss the problem of lookup inconsistencies and its implications on the one-copy serializability property of the transaction processing in our framework. T3 - ZIB-Report - 09-34 KW - Distributed System KW - DHT KW - Paxos KW - Algorithms KW - Storage Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11532 SN - 1438-0064 ER - TY - GEN A1 - Schintke, Florian A1 - Reinefeld, Alexander A1 - Haridi, Seif A1 - Schütt, Thorsten T1 - Enhanced Paxos Commit for Transactions on DHTs N2 - Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items. T3 - ZIB-Report - 09-28 KW - Paxos KW - Transaktionen KW - DHT KW - strenge Konsistenz KW - Paxos KW - transactions KW - DHT KW - strong consistency Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11448 SN - 1438-0064 ER - TY - THES A1 - Prollius, Christian von T1 - Ein Peer-to-Peer System mit Bereichsabfragen in PlanetLab T1 - A Peer-to-Peer System with Range Queries in PlanetLab N2 - Aktuelle Entwicklungen zeigen, dass Peer-to-Peer (P2P) Anwendungen wie Skype oder Bittorrent im Internet immer mehr an Bedeutung gewinnen. In den letzten Jahren hat es einen explosionsartigen Anstieg an Nutzern und Daten in solchen Netzen gegeben. Dabei stellt der eigentliche Dateitransfer zwischen zwei Rechnern kein großes Problem mehr dar und auch der Speicherbedarf für die große Menge an Daten kann durch die Weiterentwicklung der Hardware gut gedeckt werden. Das eigentliche Problem liegt vielmehr darin, den Rechner zu finden, der die gewünschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ungünstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen müssen, sind einerseits sehr anfällig gegenüber Angriffen und Ausfällen (Single Point of Failure)und kommen auch nicht mit der ständig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten Lösungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale Lösungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gelöst, jedoch haben sie starke Nachteile bei der Suche nach Keys. Bei einer Suche wird ein Broadcast verwendet (jeder schickt die Anfrage an jeden weiter) und damit ein enormer Netzwerkverkehr erzeugt. In "Why Gnutella Can't Scale. No, Really" wird erklärt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zusätzlich eine Lösung benötigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden können. Aus diesem Grund beschäftigt sich die folgende Arbeit mit einer völlig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endgeräte den Hauptteil des Dienstes selbst erbringen und damit jeder zusätzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit präsentiert Chord#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord# wurde ausgewählt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht möglich, da dieser eine Hashfunktion für die Keys verwendet und somit die Daten zwar gleichmäßig aber unsortiert auf die Teilnehmer verteilt. Es wird in dieser Arbeit gezeigt, dass mit Hilfe von Chord# auch ohne die Hashfunktion gute Ergebnisse erzielt werden. Außerdem können durch den Verzicht auf die Hashfunktion Bereichsabfragen ermöglicht werden. Dafür wird der Chord# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausführlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet. N2 - Recent developments show that peer-to-peer (p2p) applications, such as Skype or Bittorrent have become increasingly important in the internet. Over the last years there has been a rapid growth of both users and data in such networks. However, the actual file transfer between two peers is not really an issue anymore. The same holds true for data storage, since the new hardware grants users enough space to store their data. The real problem is finding the peers that possess the desired data. Client-server architectures like Napster have proven to be ineffective addressing that problem. One or few servers being responsible for many peers are vulnerable to attacks or failures (single point of failure). Additionally, they are unable to cope with the rapidly growing number of peers. Distributed hashtables (DHT) are a good approach to solve these problems, since they scale nicely with large numbers of peers and provide a high tolerance for errors. Other decentralized solutions like the p2p network Gnutella solved the problem of Single Point of Failure but show considerable disadvantages when searching for keys. The peers in Gnutella use a broadcast (sending the message to all peers they know)resulting in massive traffic. According to "Why Gnutella Can't Scale. No, Really.", each search using standard client settings yields 17MB traffc. This calls for a different solution, distributing keys and values to peers quickly and efficiently so they can be found fast. For that reason this thesis focuses on a fully distributed architecture using organized key placement. One major advantage of distributed architecture is the fact, that the peers do most of the work themselves. This way, new peers joining the network add resources to it. This thesis presents Chord#, a scalable, self-organizing and completely decentralized DHT. It has been chosen due to its capability to allow range queries. The regular Chord algorithm does not support range queries, because of the hashfunction it uses to evenly distribute the keys among the peers. This results in similar or logical coherent keys most likely not being close together in the network. This thesis shows Chord# achieving same results as Chord - regarding performance costs - without the hashfunction. In dropping the hashfunction this algorithm allows the use of range queries. The Chord# algorithm is implemented in Java (about 1500 lines of code) and thoroughly tested in the research network PlanetLab. The results are evaluated regarding performance, maintenance and scalability. KW - Peer-to-Peer KW - Bereichsabfragen KW - peer-to-peer KW - range queries Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11492 ER - TY - THES A1 - Plantikow, Stefan T1 - Transaktionen für verteilte Wikis auf strukturierten Overlay Netzwerken T1 - Transactions for Distributed Wikis on Structured Overlay Networks N2 - Die Diplomarbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewährleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenläufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen. N2 - The diploma thesis presents a transaction processing scheme for structured overlay networks and uses it to develop a distributed Wiki application based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. Such failures are masked by providing high availability of nodes. This in turn is achieved by constructing the overlay from replicated state machines (cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. The pseudocode of the relevant Wiki functions is presented and the different concurrency control techniques are evaluated in terms of message complexity. KW - Verteilte Transaktionen KW - Content Management Systeme KW - Strukturierte Overlay-Netzwerke KW - Konsistenz KW - Nebenläufigkeitskontrolle KW - distributed transactions KW - content management systems KW - structured overlay networks KW - consistency KW - concurrency control Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10176 ER - TY - THES A1 - Müller, Magnus T1 - Flexible Routing Tables in a Distributed Key-Value Store N2 - We present our implementation of Flexible Routing Tables (FRT) in the distributed key-value store Scalaris. Classic routing table generators like Chord structure routing tables by considering node identifiers only. Secondary requirements such as latency properties are considered after the general structure, eliminating potential performance gains. FRT aims to allow multiple requirements when creating routing tables. The concept is based on lazy routing table entries learning and filtering entries when a routing table is full. Entries are filtered such that the resulting table is best among all other possible tables where one node was filtered. FRT uses a total order to define which of the possible routing tables is best. We implemented two instances of FRT, namely FRT-Chord and grouped FRT-Chord (GFRT-Chord). We compare our implementation with the existing implementation of Chord in Scalaris and evaluate the advantages and disadvantages of more flexible routing schemes. KW - FRT KW - FRT-Chord KW - GFRT-Chord KW - Routing KW - DHT KW - Scalaris Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42742 ER - TY - JOUR A1 - Kruber, Nico A1 - Högqvist, Mikael A1 - Schütt, Thorsten T1 - The Benefits of Estimated Global Information in DHT Load Balancing JF - Cluster Computing and the Grid, IEEE International Symposium on Y1 - 2011 U6 - https://doi.org/10.1109/CCGrid.2011.11 VL - 0 SP - 382 EP - 391 PB - IEEE Computer Society CY - Los Alamitos, CA, USA ER - TY - THES A1 - Högqvist, Mikael T1 - Consistent Key-Based Routing in Decentralized and Reconfigurable Data Services Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:11-100206145 UR - http://edoc.hu-berlin.de/docviews/abstract.php?id=39763 ER - TY - JOUR A1 - Schintke, Florian T1 - XtreemFS & Scalaris JF - Science & Technology Y1 - 2013 IS - 6 SP - 54 EP - 55 PB - Pan European Networks ER - TY - THES A1 - Borgers, Philipp T1 - Erweiterung eines verteilten Key-Value-Stores (Riak) um einen räumlichen Index Y1 - 2012 ER - TY - THES A1 - Fischer, Jens T1 - Evaluating the Scalability of Scalaris Y1 - 2016 ER -