Implement the Raft Commitment Rule - The Consensus

Implementation

Implement the Raft commitment rule: an entry is committed when a majority of nodes have it in their log. The leader uses matchIndex[] to determine when this is true.

Request:  {"type": "check_commit", "msg_id": 1, "log_length": 5, "match_indices": {"n1": 5, "n2": 5, "n3": 3, "n4": 2, "n5": 1}, "current_term": 3}
Response: {"type": "check_commit_ok", "in_reply_to": 1, "new_commit_index": 5, "majority_count": 2, "quorum": 3, "committed": true}

Request:  {"type": "advance_commit", "msg_id": 2, "old_commit_index": 3, "match_indices": {"n1": 7, "n2": 5, "n3": 5, "n4": 3, "n5": 2}, "current_term": 3}
Response: {"type": "advance_commit_ok", "in_reply_to": 2, "new_commit_index": 5, "entries_committed": 2}

Sample Test Cases

Majority replication commits entryTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"check_commit","msg_id":2,"log_length":3,"match_indices":{"n1":3,"n2":3,"n3":1},"current_term":1}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

No majority means no commit advanceTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3","n4","n5"]}}
{"src":"c1","dest":"n1","body":{"type":"check_commit","msg_id":2,"log_length":5,"match_indices":{"n1":5,"n2":5,"n3":1,"n4":1,"n5":1},"current_term":2}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

An entry is committed when a majority of nodes have it in their log

Hint 2▾

The leader tracks matchIndex[] for each follower

Hint 3▾

commitIndex advances when a majority of matchIndex values >= a given index

Hint 4▾

Only entries from the current term can directly advance commitIndex

Hint 5▾

Entries from previous terms are committed indirectly

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts