Benchmark Gossip KV Store Performance - The Gossiper

                      TASK
                    

Implementation

Benchmark your gossip KV store to measure real-world performance characteristics:

Convergence time: How long until all replicas have the same value?
Message overhead: How many gossip messages per write operation?
Consistency violations: How often does a read return stale data?

Implement a bench_write that tracks timing:

Request:  {"type": "bench_write", "msg_id": 1, "key": "x", "value": "v1"}
Response: {"type": "bench_write_ok", "in_reply_to": 1, "write_id": 1}

And a bench_report endpoint:

Request:  {"type": "bench_report", "msg_id": 2}
Response: {"type": "bench_report_ok", "in_reply_to": 2,
           "total_writes": 10, "total_gossip_msgs": 45,
           "msgs_per_write": 4.5, "keys_stored": 5}

Sample Test Cases

Bench write returns write_idTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"bench_write","msg_id":2,"key":"x","value":"v1"}}

Expected Output

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

Bench report with zero writesTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"bench_report","msg_id":2}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "bench_report_ok", "total_writes": 0, "total_gossip_msgs": 0, "msgs_per_write": 0, "keys_stored": 0, "in_reply_to": 2, "msg_id": 1}}

Hints

Hint 1▾

Track total messages exchanged for gossip sync

Hint 2▾

Measure time from write to full convergence (all replicas agree)

Hint 3▾

Count consistency violations: reads that return stale data

Hint 4▾

Compare metrics under normal vs partition conditions

Hint 5▾

Expose metrics via a bench_stats endpoint

Resources

Maelstrom Broadcast Workload

Maelstrom broadcast workload specification

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

benchmarkingconvergence timemessage overheadconsistency

main.py

python

#!/usr/bin/env python3
import sys
import json
import time
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.store = {}
        self.total_writes = 0
        self.total_gossip_msgs = 0
        self.write_counter = 0
    def send(self, dest, body):
        body["msg_id"] = self.next_msg_id
        self.next_msg_id += 1
        print(json.dumps({"src": self.node_id, "dest": dest, "body": body}), 
        flush=True)
    def reply(self, req, body):
        body["in_reply_to"] = req["body"]["msg_id"]
        self.send(req["src"], body)
def main():
    node = Node()
    for line in sys.stdin:
        line = line.strip()
        if not line: continue
        msg = json.loads(line)
        body = msg["body"]
        t = body["type"]
        if t == "init":
            node.node_id = body["node_id"]
            node.node_ids = body["node_ids"]
            node.reply(msg, {"type": "init_ok"})
        elif t == "bench_write":
            node.total_writes += 1
            node.write_counter += 1
            ts = time.time()
            node.store[body["key"]] = {"value": body["value"], "ts": ts}