A Distributed Key-Value Store Implementation and evaluation of two strategies for lookup in distributed databases

Abstract

This report describes the design, implementation and testing of a database; more speci - cally, a distributed, scalable key-value store able to handle many concurrent queries. A central issue when building this type of system is how to search for a speci c node in the distributed data space. Two di erent algorithms, solving this issue in di erent ways, have been imple- mented and compared against each other through benchmark testing. One of these algorithms is the Chord algorithm described by Stoica et al in 2001, the other an altered version which is referred to as FCN (Fully Connected Network) throughout this report. While they build upon the same general idea of how to distribute data over the available space, they di er greatly in the amount of connections between nodes in the network. The report also describes the testing environment used to test these algorithms against each other. Both the database and the testing environment were implemented in Erlang. Within the con nes of the tests, the database showed good signs of scalability and concurrent query handling. The tests also showed great di erences in query-per-second performance for the two algorithms, with FCN having a much higher throughput. Chord, on the other hand, adapted more quickly to changes in large networks. This was not measured empirically but concluded from simulation and analysis. It became clear that FCN was more well suited than Chord in an application where quick lookups are treasured and the network is relatively stable.