Optimization of efficiency and resilience to node failures of distributed hash tables

Artur Olszak

Abstract

In recent years, we observe a growing interest in large-scale distributed systems based on the distributed hash table algorithm (DHT). A DHT is a distributed system storing large amount of information in a way allowing efficient lookup for the information being stored. DHT systems are used to store key-value pairs, similarly to a hash table. However, the key-value pairs set is stored in a distributed manner and is shared among the nodes of the distributed hash table. Every node in the DHT maintains a list of references to other nodes in the system - a routing table. The routing table allows decreasing the distance left to the destination node in each lookup step (the distance between node identifiers, according to the chosen metric). The structure of the routing table, the choice of the metric defining logical distances between nodes, and the lookup algorithm have fundamental influence on the path lengths between nodes and the resilience of the system to node failures. The use of the one-dimensional model (placing the nodes logically on a ring) allows the nodes to maintain (in addition to neighbors providing efficient lookup) sets of “sequential neighbors” - certain numbers of neighbors that are the closest existing nodes in both directions on the ring. Such a model yields a very high level of resilience to node failures. This thesis presents a novel model of a distributed hash table based on a hierarchical hypercube geometry. The presented approach employs a variable multi-dimensional metric adopting the Steinhaus transform. It is shown that the new approach allows reaching a higher level of resilience to node failures, as well as a shorter average lookup path length than with the use of the sequential neighbors sets. The thesis describes the new DHT architecture and the processes of determining optimal solutions. Novel routing and lookup algorithms are discussed, as well as DHT resource management algorithms, routing table nodes selection algorithms, maintenance and recovery procedures, and solutions increasing security in the system. The work also presents the architecture of the implemented DHT library and the simulator that was used to evaluate the presented solutions. Individual design decisions are supported by results of extensive simulations and compared to the existing solutions.
Rodzaj dyplomuPraca doktorska
Autor Artur Olszak (WEiTI / II)
Artur Olszak
- Instytut Informatyki
Tytuł w języku polskimOptymalizacja wydajności i odporności na awarie węzłów rozproszonej tablicy mieszającej
Języken angielski
Jednostka dyplomującaWydział Elektroniki i Technik Informacyjnych (WEiTI)
Dyscyplina naukiinformatyka / dziedzina nauk technicznych / obszar nauk technicznych
Data rozpoczęcia26-02-2013
Data obrony20-10-2015
Data zakończenia 27-10-2015
Promotor Janusz Sosnowski (WEiTI / II)
Janusz Sosnowski
- Instytut Informatyki
Recenzenci wewnętrzni Tomasz Martyn (WEiTI / II)
Tomasz Martyn
- Instytut Informatyki
Recenzenci zewnętrzni Marek Tudruj
Marek Tudruj
-
Paginacja 146
Słowa kluczowe w języku polskimrozproszona tablica mieszająca, routing, wyszukiwanie, odpornosć
Słowa kluczowe w języku angielskimdistributed hash table, routing, lookup, resilience
Streszczenie w języku polskimW ostatnich latach wyjątkową popularność zyskały systemy oparte na algorytmie rozproszonej tablicy mieszającej (ang. distributed hash table - DHT). Rozproszona tablica mieszająca jest rozproszonym systemem przechowującym duże ilości informacji w sposób zapewniający ich efektywne wyszukiwanie. W systemach DHT przechowywane są pary klucz-wartość, podobnie do tablicy mieszającej, jednak zbiór par klucz-wartość przechowywany jest w sposób rozproszony i jest rozdzielony pomiędzy węzły rozproszonej tablicy mieszającej. Każdy węzeł przechowuje listę referencji do innych węzłów - tablicę routingu, utworzoną w taki sposób, aby w każdym kroku wyszukiwania istniała możliwość zmniejszenia pozostałej odległości do węzła docelowego (odległość między identyfikatorami węzłów, zgodnie z przyjętą metryką). Struktura tablicy routingu, przyjęta metryka oraz algorytm wyznaczania węzłów w kolejnych krokach wyszukiwania mają zasadniczy wpływ na długości tras pomiędzy węzłami oraz odporność systemu na awarie węzłów. Zastosowanie modelu jednowymiarowego (logiczne rozmieszczenie węzłów na pierścieniu) pozwala na przechowywanie przez węzły (poza referencjami zapewniającymi efektywne wyszukiwanie) tzw. zbiorów sekwencyjnych sąsiadów - pewnej ilości węzłów najbliższych do węzła w obu kierunkach na pierścieniu. Taki model zapewnia bardzo wysoki poziom odporności systemu na awarie węzłów. Rozprawa prezentuje innowacyjny model rozproszonej tablicy mieszającej opartej na strukturze hierarchicznego hipersześcianu. Zaproponowane rozwiązanie wykorzystuje zmienną wielowymiarową metrykę opartą na przekształceniu Steinhausa. Przedstawione podejście umożliwia osiągnięcie większej odporności na awarie węzłów oraz mniejszej średniej długości trasy niż przy zastosowaniu zbiorów sekwencyjnych sąsiadów. Praca przedstawia poszczególne elementy architektury systemu oraz procesy wyznaczania optymalnych rozwiązań. Omówione zostały i przeanalizowane innowacyjne algorytmy routingu, wyszukiwania, algorytmy zarządzania zasobami, algorytmy doboru węzłów do tablic routingu, utrzymania sieci oraz rozwiązania zwiększające poziom bezpieczeństwa. W pracy została również przedstawiona architektura zaimplementowanej biblioteki oraz wykorzystanego do badań symulatora. Poszczególne rozwiązania zostały poparte wynikami badań symulacyjnych i porównane z istniejącymi rozwiązaniami.
Klasyfikacja PKT4100
Klasyfikacja KBN28 Informatyka
Klasyfikacja europejska80-30
Plik pracy
olszak_doktorat.pdf 1.4 MB

Pobierz odnośnik do tego rekordu

Powrót