This repository showcases my implementations of distributed systems concepts in Go, based on the renowned MIT 6.5840 / UBC CPSC 416 course. Each lab explores a core concept in distributed systems, including MapReduce, Raft consensus, and sharded key-value stores.

All code is written in Go and tested on Linux (Ubuntu/WSL).
Labs are self-contained and runnable with provided scripts.

Ensure you have Go 1.17+ installed.
Install instructions: https://golang.org/doc/install

Check with:

go version

git clone https://github.com/ritikk7/Distributed-Key-Value-Store.git
cd Distributed-Key-Value-Store

From the project root:

cd src/main
bash build.sh

Or manually:

cd src/main
go build ../mrapps/wc.go         # Plugin for word count
go build ../mrapps/indexer.go    # Plugin for indexer
go build mrcoordinator.go
go build mrworker.go
go build mrsequential.go

cd src/main

# Clean old outputs
rm -f mr-out* mr-tmp/*

# Run the coordinator (input split files: pg-*.txt)
go run mrcoordinator.go ../pg-*.txt &

# Run workers in parallel
go run mrworker.go ../mrapps/wc.go &
go run mrworker.go ../mrapps/wc.go &

When finished, combine the output:

cat mr-out-* | sort > result.txt
head result.txt

bash test-mr.sh

Expected output:

*** Starting wc test.
--- wc test: PASS
*** Starting indexer test.
--- indexer test: PASS
...
*** PASSED ALL TESTS

Lab 2 consists of implementing the Raft consensus algorithm in four parts:

Implements Raft's election protocol using randomized timeouts and heartbeats. Ensures:

• Only one leader at a time
• Leader steps down on term mismatch
• Peers vote once per term

go test -run 2A

Extends Raft to replicate client commands and commit them once stored on a majority of servers.

• Handles mismatched logs
• Applies committed entries via applyCh
• Implements Start() to initiate replication

go test -run 2B

Supports crash recovery by:

• Serializing Raft state via labgob
• Saving/restoring state via Persister
• Ensuring leaders/peers survive restarts

go test -run 2C

Supports truncating the log:

• Implements Snapshot(index, snapshot []byte)
• Discards old log entries
• Sends/install snapshots to lagging peers
• Persists snapshots and resumes from them on restart

go test -run 2D

You can also run:

for i in {1..10}; do go test -run 2D; done

Each part builds on the last — it's recommended to test each with -race enabled:

go test -race -run 2A

In Lab 3, a fault-tolerant, linearizable key/value store is built atop your Raft implementation. Clients interact through a Clerk object, and each server uses Raft to ensure consistent replication.

Implements:

• Basic Get/Put/Append RPCs
• Coordination via Raft log entries
• Client retries and duplicate request detection

go test -run 3A

Includes tests like:

• One client
• Many clients
• Partitions and failures
• Duplicate RPC handling

Adds:

• Log size threshold tracking via maxraftstate
• Snapshot() integration with Raft
• Log compaction and fast recovery from persisted state

go test -run 3B

Tests include restarts, unreliable networks, partitions, and snapshot correctness.

Lab 4 builds on Lab 3 by supporting dynamic sharding across multiple replica groups.

Implements a centralized controller using Raft that:

• Tracks shard-to-group assignments
• Handles Join, Leave, Move, and Query RPCs
• Rebalances shards evenly with minimal movement

cd src/shardctrler
go test

Extends kvraft to dynamically migrate shards between groups:

• Periodically polls the shard controller for config changes
• Transfers shard data between groups via RPC
• Rejects requests for unowned shards with ErrWrongGroup
• Ensures linearizability even during reconfiguration

cd src/shardkv
go test

Tests cover:

• Static and dynamic shard assignment
• Concurrent client operations
• Restarts, unreliable networks, partitions
• Correct migration and deletion of shard state

See /docs for detailed instructions and explanations for each lab:

• Lab 1: MapReduce
• Lab 2: Raft Consensus
• Lab 3: Key/Value Service
• Lab 4: Sharded KV Store

This project is for educational and demonstration purposes only. It is based on public materials from MIT 6.5840 and UBC CPSC 416, with all implementation written independently.