DKVS: A Distributed Key-Value Store in C

Contributors

• @Krut007
• @Jakub-Kliment

Features

• Distributed Architecture: The key-value store can be distributed across multiple servers, forming a ring.
• Consistent Hashing: Keys are distributed across the servers using a consistent hashing algorithm, ensuring a balanced load and minimal data redistribution when servers are added or removed.
• Quorum-based Consistency: The system uses a quorum mechanism to ensure data consistency across replicas.
• UDP-based Networking: Communication between clients and servers, and between servers themselves, is handled using UDP.
• Client-Server Model: A client application can connect to the DKVS cluster to perform operations.
• Rich Command Set: The client supports a variety of commands, including:
  • put <key> <value>: Store a key-value pair.
  • get <key>: Retrieve the value for a given key.
  • find <string>: Find keys that contain the given string.
  • cat <key>: Retrieve the value for a key, similar to get.
  • substr <string>: Find values that contain the given string.
• Custom Hash Table: The core data storage on each server is a custom-built hash table with chaining for collision resolution.

Prerequisites

Before building, ensure you have the following dependencies installed:

• clang
• make
• OpenSSL development libraries (e.g., libssl-dev on Debian/Ubuntu)
• Python (for running end-to-end tests)

How to Build

The project uses make for building the executables.

1. Navigate to the source directory:

   cd src

2. Run make:

   make

This will generate the executables in the src directory:

• dkvs-server: The server application.
• dkvs-client: The client application.
• dkvs-dump-ring: A utility to display the server ring.

How to Run

1. Configure the Servers

Create a servers.txt file in the root project directory. This file defines the servers in the ring. Each line should contain the IP address, port number, and weight of a server(number of node per server).

Example servers.txt:

127.0.0.1 1234 1
127.0.0.1 1235 2
127.0.0.1 1236 3

2. Start the Servers

For each server defined in servers.txt, start a dkvs-server instance from the src directory in a separate terminal.

# In terminal 1
./src/dkvs-server 127.0.0.1 1234

# In terminal 2
./src/dkvs-server 127.0.0.1 1235

# In terminal 3
./src/dkvs-server 127.0.0.1 1236

3. Use the Client

You can now use the dkvs-client to interact with the distributed key-value store. Run the client from the root directory, ensuring the servers.txt file is present.

Store a value:

./src/dkvs-client put -- mykey "my value"

Retrieve a value:

./src/dkvs-client get -- mykey

4. Dump the Ring (Optional)

The dkvs-dump-ring utility can be used to inspect the current state and topology of the distributed hash ring. It displays information about each node, including its SHA-1 hash and address, and can retrieve diagnostic information from each running server.

To run the dkvs-dump-ring utility, navigate to the src directory and execute:

./src/dkvs-dump-ring

This command will print details about the configured servers and any information they return.

Testing

The project includes a suite of unit and end-to-end tests. To run all tests, navigate to the src directory and run:

make check