Implement Lease-Based Reads - The Store | Build Distributed Systems

                      TASK
                    

Implementation

Implement lease-based reads: the leader uses its active lease to serve reads without network round trips. Document the clock assumption required.

Request:  {"type": "lease_read", "msg_id": 1, "key": "x"}
Response: {"type": "lease_read_ok", "in_reply_to": 1, "value": "42", "lease_valid": true, "network_round_trips": 0}

Request:  {"type": "lease_read_config", "msg_id": 2, "lease_duration_ms": 3000, "election_timeout_ms": 5000, "max_clock_skew_ms": 500}
Response: {"type": "lease_read_config_ok", "in_reply_to": 2, "safe": true, "effective_lease_ms": 2500, "reason": "lease - clock_skew < election_timeout"}

Sample Test Cases

Lease read with zero round tripsTimeout: 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":"lease_read","msg_id":2,"key":"x"}}

Expected Output

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

Safe lease configurationTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"lease_read_config","msg_id":2,"lease_duration_ms":3000,"election_timeout_ms":5000,"max_clock_skew_ms":500}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "lease_read_config_ok", "in_reply_to": 2, "safe": true, "effective_lease_ms": 2500, "msg_id": 1}}

Hints

Hint 1▾

The leader uses its lease to serve reads without any network round trips

Hint 2▾

During the lease, the leader is guaranteed to still be leader

Hint 3▾

Lease duration must be shorter than election timeout to prevent stale reads

Hint 4▾

Assumption: bounded clock skew between nodes

Hint 5▾

If clocks drift too much, a stale leader may serve reads after a new leader is elected

Resources

CockroachDB - Follower Reads and Lease Reads

How CockroachDB implements lease-based reads for low latency

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

lease readsclock assumptionzero network round tripsstale read risk

main.py

python