TASK
Implementation
Implement log compaction with snapshots:
- Periodically snapshot state machine state
- Record snapshot index and term
- Discard log entries before snapshot
- On recovery, restore from snapshot then replay log
- Send InstallSnapshot to followers that are too far behind
This prevents unbounded log growth.
Sample Test Cases
Create snapshotTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c0","dest":"n1","body":{"type":"seed_state","msg_id":2,"state":{"x":1,"y":2},"commit_index":5,"term":2}}
{"src":"c0","dest":"n1","body":{"type":"take_snapshot","msg_id":3,"up_to_index":5}}
Expected Output
{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c0","body":{"type":"seed_state_ok","in_reply_to":2,"msg_id":1}}
{"src":"n1","dest":"c0","body":{"type":"snapshot_ok","in_reply_to":3,"msg_id":2,"last_included_index":5,"last_included_term":2}}
Hints
Hint 1▾
Snapshot state machine periodically
Hint 2▾
Discard log entries before snapshot
Hint 3▾
Send snapshot to slow followers
Resources
OVERVIEW
Theoretical Hub
Log Compaction
The Raft log grows forever as commands arrive. Snapshots compress applied log entries into a compact state representation. Only the snapshot and subsequent log are needed for recovery.
InstallSnapshot RPC
When a follower is so far behind that leader discarded needed entries, send the snapshot instead. The follower replaces its state with the snapshot and resumes from there.
Key Concepts
snapshotlog compactionrecovery
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
33
34
35
36
#!/usr/bin/env python3
import sys
import json
import pickle
class Snapshotter:
def __init__(self, log, state_machine):
self.log = log
self.sm = state_machine
self.snapshot_index = 0
self.snapshot_term = 0
self.snapshot_data = None
def take_snapshot(self, up_to_index):
# TODO: Serialize state machine
# TODO: Record snapshot index/term
# TODO: Trim log
pass
def restore_snapshot(self, data, index, term):
# TODO: Restore state machine from snapshot
# TODO: Update log starting point
pass
def should_snapshot(self, threshold=10000):
# TODO: Check if log is too long
pass
class SnapshotSender:
def __init__(self, snapshotter):
self.snapshotter = snapshotter
def install_snapshot(self, follower):
# TODO: Send snapshot to follower
pass