Description:
Distributed Hash Tables (DHTs) are useful tools for building large scale distributed systems. DHTs provide a hash-table-like interface to map a key to its responsible node among the current set of participating nodes. Many techniques have been developed to reduce DHT lookup latency: proximity routing, parallel lookups, complete routing state, aggressive routing table stabilization and others. While all techniques reduce latency, none is free and they all use bandwidth. Evaluations based solely on latency improvements can be misleading as some techniques consume more bandwidth than others. Ultimately, we are interested in the relative efficiencies with which different techniques use each extra bit of communication to reduce lookup latency. We develop a performance vs. cost framework (PVC) to compare these efficiencies. Our study of existing DHTs shows that a fixed routing table size is the main obstacle to efficient bandwidth use. The need to adjust routing table size motivates our design for a new DHT, Accordion. Bigger routing tables result in lower lookup hop-counts. Smaller routing tables can be refreshed more often to avoid timeouts due to stale routing entries that point to crashed nodes. Accordion allows users to explicitly specify a desired bandwidth budget. The goal of Accordion is to choose a routing table size that minimizes lookup latency, balancing the need for both low lookup hop-count and low timeout probability. Accordion employs a unique design for managing routing tables. Nodes learn new neighbors opportunistically through normal lookup traffic and active exploration. Large bandwidth budgets lead to high learning rates. Nodes evict neighbors that are likely dead by estimating the liveness probability of neighbors based on past statistics of node lifetimes. Short node lifetimes lead to high eviction rates. The routing table size is determined by the equilibrium of the neighbor acquisition and eviction processes.
Speaker(s):
Jinyang Li, Ph.D. student, MIT
|
