# RAFT Consensus Implementation A complete implementation of the RAFT consensus algorithm in Go with gRPC communication. ## Features ### 1. Leader Election (RequestVote RPC) - Randomized election timeouts to prevent split votes - Term-based voting with log comparison - Automatic election when heartbeats timeout - Conflict resolution for multiple candidates ### 2. Log Replication (AppendEntries RPC) - Heartbeat mechanism for leader authority - Log consistency checks with prevLogIndex/prevLogTerm - Automatic log synchronization for lagging followers - Commit index advancement with majority quorum ### 3. Key-Value Store - Simple in-memory key-value database - Commands: SET, GET, DELETE - Applied after log entries are committed ### 4. Fault Tolerance - **Leader Failure**: New election triggered automatically - **Member Failure**: Cluster continues with quorum - **Network Partition**: Majority group maintains consistency ## Project Structure ``` . ├── proto/ │ └── raft.proto # gRPC protocol definition ├── raft/ │ ├── node.go # Core RAFT node implementation │ ├── election.go # Leader election logic │ ├── replication.go # Log replication logic │ └── handlers.go # gRPC handlers ├── cmd/ │ ├── node/main.go # Node executable │ └── client/main.go # Client CLI ├── scripts/ │ ├── start_cluster.sh # Start 5-node cluster │ ├── stop_cluster.sh # Stop cluster │ └── test_scenarios.sh # Test scenarios ├── Makefile └── README.md ``` ## Prerequisites - Go 1.21+ - Protocol Buffers compiler (protoc) - gRPC Go plugins ### Install Protocol Buffers ```bash # macOS brew install protobuf # Install Go plugins go install google.golang.org/protobuf/cmd/protoc-gen-go@latest go install google.golang.org/grpc/cmd/protoc-gen-go-grpc@latest # Add to PATH export PATH="$PATH:$(go env GOPATH)/bin" ``` ## Quick Start ### 1. Build the Project ```bash # Download dependencies and build make deps make build ``` ### 2. Start the Cluster ```bash # Start 5-node cluster in background make run-cluster # Or use the script ./scripts/start_cluster.sh ``` ### 3. Connect with Client ```bash make client ``` ### 4. Basic Operations ``` > status # View cluster status > set mykey myvalue # Set a key-value > get mykey # Get value > delete mykey # Delete key ``` ### 5. Stop the Cluster ```bash make stop-cluster ``` ## Client Commands | Command | Description | |---------|-------------| | `get ` | Get value for key | | `set ` | Set key to value | | `delete ` | Delete key | | `status` | Show all nodes status | | `status ` | Show specific node status | | `partition ` | Partition node from addresses | | `heal ` | Restore node connections | | `quit` | Exit client | ## Testing Scenarios ### Test 1: Leader Election 1. Start the cluster 2. Check status to see elected leader 3. Leader marked with `*` in status ``` > status [node1] follower term=1 commit=0 log=1 [node2] *leader term=1 commit=0 log=1 [node3] follower term=1 commit=0 log=1 [node4] follower term=1 commit=0 log=1 [node5] follower term=1 commit=0 log=1 ``` ### Test 2: Leader Failure 1. Find the current leader with `status` 2. Kill the leader process (Ctrl+C or kill) 3. Wait 1-2 seconds 4. Run `status` - new leader should be elected ```bash # In one terminal make run-node1 # If node1 is leader # Press Ctrl+C to kill # In client > status # New leader elected ``` ### Test 3: Log Replication 1. Set some values 2. Check that all nodes have the same log length ``` > set key1 value1 [localhost:5002] SET key1 = value1 (committed) > status # All nodes should show same log length and commit index ``` ### Test 4: Network Partition Simulate network partition using the `partition` command: ``` # Partition node1 and node2 from the majority > partition localhost:5001 localhost:5003,localhost:5004,localhost:5005 > partition localhost:5002 localhost:5003,localhost:5004,localhost:5005 # Also partition from the minority's perspective > partition localhost:5003 localhost:5001,localhost:5002 > partition localhost:5004 localhost:5001,localhost:5002 > partition localhost:5005 localhost:5001,localhost:5002 > status # Majority (node3,4,5) will elect leader # Minority (node1,2) cannot achieve quorum # Heal partitions > heal localhost:5001 > heal localhost:5002 > heal localhost:5003 > heal localhost:5004 > heal localhost:5005 ``` ### Test 5: Member Recovery 1. Write data to cluster 2. Kill a follower node 3. Write more data 4. Restart the killed node 5. Check log synchronization ```bash # Write initial data > set data1 initial # Kill node5 (assuming it's a follower) # In another terminal: pkill -f "node5" # Write more data > set data2 afterfailure # Restart node5 make run-node5 # Check all nodes have same logs > status ``` ## Quorum Analysis For a cluster of N nodes: - **Quorum size**: (N/2) + 1 = majority - **Failure tolerance**: (N-1)/2 nodes | Cluster Size | Quorum | Max Failures | |-------------|--------|--------------| | 3 nodes | 2 | 1 | | 5 nodes | 3 | 2 | | 7 nodes | 4 | 3 | ### Why 5 Nodes? With 5 nodes: - Quorum = 3 nodes - Can tolerate 2 node failures - Network partition: 3-node majority can continue operating ## Architecture ### Node States 1. **Follower**: Passive, responds to RPCs 2. **Candidate**: Actively seeking election 3. **Leader**: Handles all client requests, replicates logs ### RPC Types 1. **RequestVote**: Leader election 2. **AppendEntries**: Log replication & heartbeat 3. **ClientRequest**: Key-value operations 4. **Partition/Heal**: Network simulation ### Timers - **Election Timeout**: 150-300ms (randomized) - **Heartbeat Interval**: 50ms ## Configuration Node configuration in `raft/node.go`: ```go ElectionTimeoutMin: 150 * time.Millisecond ElectionTimeoutMax: 300 * time.Millisecond HeartbeatInterval: 50 * time.Millisecond ``` ## Logs View logs in `logs/` directory: ```bash # View specific node log tail -f logs/node1.log # View all logs make follow-logs ``` ## Makefile Commands ```bash make deps # Download dependencies make proto # Generate protobuf code make build # Build binaries make run-cluster # Start 5-node cluster make stop-cluster # Stop cluster make client # Run client CLI make logs # View recent logs make follow-logs # Follow logs in real-time make clean # Remove build artifacts make help # Show help ``` ## Implementation Details ### Election Safety - Only one leader per term - Candidates only win with majority votes - Voters check log up-to-date-ness before voting ### Log Matching - If two entries have same index and term, they store same command - If two entries have same index and term, logs are identical in all preceding entries ### Leader Completeness - If a log entry is committed in a given term, it will be present in the logs of leaders for all higher terms ## References - [Raft Paper](https://raft.github.io/raft.pdf) - [Raft Visualization](https://raft.github.io/) - [gRPC Go](https://grpc.io/docs/languages/go/) # RAFT