H.3.4 Systems and Software
Refine
Document Type
- Master's Thesis (2)
- ZIB-Report (2)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
- Peer-to-Peer (2)
- range queries (2)
- Bereichsabfragen (1)
- Distributed Hash Table (DHT) (1)
- Dubletten (1)
- Gossiping (1)
- Lastverteilung (1)
- Load Balancing (1)
- Metasuchmaschine (1)
- Verteilte Hashtabelle (DHT) (1)
Institute
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%.
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.
We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.
\\{\bf Zusammenfassung: }Diese Diplomarbeit beschreibt ein verteiltes Bibliotheks-Informationssystem für bibliographische Datenbanken im Internet. Der Name des Systems ist ZACK. Der Benutzer kann mit ZACK in einer oder mehreren bibliographischen Datenbanken nach einem Dokument suchen und die Treffer in die eigene lokale Datenbank übernehmen. Mit der Übernahme der Datensätze aus einer fremden Datenbank wird die Erfassung neuer Dokumente wesentlich erleichtert, da die Eigenkatalogisierung auf ein Minimum beschränkt werden kann. Es wird doppelte Arbeit vermieden, und die Datensätze haben eine gleichbleibend hohe Qualität. Bei der verteilten Suche mit ZACK wird parallel in mehreren Datenbanken gesucht. Dubletten werden als solche erkannt. Dem Benutzer wird eine übersichtliche Kurztrefferliste ohne doppelte Einträge angeboten. Er kann dann selbst entscheiden, aus welcher Datenbank er die Datensätze übernimmt. Die verteilte Suche hat in der Praxis eine deutlich bessere Trefferquote gebracht als die Suche in nur einer Datenbank. Dabei bleibt die Antwortzeit in einem für den Benutzer akzeptablen Rahmen. Die Kurztrefferliste wird durch die Dublettenkontrolle kürzer und übersichtlicher. English Title: A Distributed Library Information System on the Basis of the Z39.50 Protocol This diploma thesis desribes a distributed library information system for bibliographic databases in the Internet. The name of the system is ZACK. With ZACK the user is able to search for a particular document in several databases and to include the matches in his/her own local database. The inclusion of data records from an external database makes the capture of new documents much easier, as internal cataloging is reduced to a minimum. Double work is eliminated and a continuously high quality of data record is ensured. The distributed search by means of ZACK is carried out in several databases in parallel. Duplicates are recognized; and a short list of matches without double entries is offered. The user can then decide for himself from which database to include data records. In practice, a distributed search has produced far better results than the search in one particular database. Response times are within an acceptable limit for the user. The short list of hits is made clearer and more concise by the duplicate check. The diploma thesis is also available in PDF, HTML, and ASCII format: http://wolfram.schneider.org/lv/diplom/ .