TASK
Implementation
Implement linearizable reads:
Option 1: Log reads (simple but slow)
- Treat reads as log entries, wait for commit
Option 2: ReadIndex (Raft optimization)
- Record current commit index
- Confirm still leader (heartbeat round)
- Wait for commit index to be applied
- Execute read
Option 3: Lease (fast but clock-dependent)
Sample Test Cases
Read via log is linearizableTimeout: 5000ms
Input
{
"src": "c0",
"dest": "n1",
"body": {
"type": "init",
"msg_id": 1,
"node_id": "n1",
"node_ids": [
"n1"
]
}
}Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}Hints
Hint 1▾
Simple: reads also go through log
Hint 2▾
Optimized: confirm leadership before read
Hint 3▾
Lease-based: use time bounds
OVERVIEW
Theoretical Hub
The Stale Read Problem
A leader might be partitioned and not know it. If it serves reads from local state, it returns stale data. Linearizability requires that reads reflect all prior writes.
ReadIndex
Before serving a read, confirm you are still leader by getting acknowledgment from a majority. Then wait for the commit index at that moment to be applied. This ensures linearizability without logging reads.
Key Concepts
linearizable readsread indexlease
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/env python3
import sys
import json
import threading
import time
class LinearizableReader:
def __init__(self, raft, state_machine):
self.raft = raft
self.sm = state_machine
self.lock = threading.Lock()
def read_via_log(self, key):
# TODO: Submit read as log entry
pass
def read_via_index(self, key):
# TODO: Implement ReadIndex protocol
# 1. Get current commit index
# 2. Confirm still leader
# 3. Wait for apply
# 4. Execute read
pass
def _confirm_leadership(self):
# TODO: Get acks from majority
pass
def _wait_applied(self, index):
# TODO: Wait until lastApplied >= index
pass