Distributed Balanced Tables: Not Making a Hash of it all
Prasanna Ganesan, Mayank Bawa · 2003
DHTs implement a distributed dictionary, supporting key insertion, deletion and lookup. They use hashing to (a) enable efficient dictionary operations, and (b) achieve storage balance across the participant nodes. Hashing can be inappropriate for both problems, as it (a) destroys data ordering, thus making sequential key access and range queries expensive, and (b) fails to provide storage balance when keys are not unique. We propose generaliz-ing DHTs to create Distributed Balanced Tables (DBTs), which eliminate the above two problems. To solve prob-lem (a), we discuss how DHT routing structures can be adapted for use in DBTs, while preserving the costs of the standard dictionary operations and supporting effi-cient range queries. To solve problem (b), we describe an efficient algorithm that guarantees storage balance, even against an adversarial insertion and deletion of keys.