Implement Distributed Cache with Consistent Hashing - Caches

                      TASK
                    

Implementation

Distribute cache entries across multiple cache nodes using consistent hashing. This scales cache capacity beyond a single node while maintaining efficient key lookup.

Implement:

Consistent hash ring for cache nodes
Key routing to appropriate node
Handling node join/leave with minimal key redistribution
Client library that routes requests automatically

Sample Test Cases

Hash key to nodeTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","cache1","cache2","cache3"]}}
{"src":"c1","dest":"n1","body":{"type":"hash_key","msg_id":2,"key":"mykey","ring_size":64}}

Expected Output

{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"n1","dest":"c1","body":{"type":"hash_key_ok","in_reply_to":2,"msg_id":1,"key":"mykey","node":"cache2","ring_position":42}}

Hints

Hint 1▾

Hash keys to determine cache node

Hint 2▾

Use consistent hashing for stability

Hint 3▾

Handle node additions and removals gracefully

Hint 4▾

Store all keys locally on the coordinator node - in single-node testing the proxy target does not exist

Resources

Consistent Hashing Paper

Original consistent hashing paper

                      OVERVIEW
                    

Theoretical Hub

Distributed Caching

A single cache server has limited memory. Distributed caching shards data across multiple servers. Each key goes to a specific server based on its hash. This scales linearly with nodes.

Consistent Hashing

Regular modulo hashing (key % N) redistributes most keys when N changes. Consistent hashing minimizes redistribution: adding/removing a node only affects keys between it and its neighbor on the ring.

Virtual Nodes

With few physical nodes, the ring may be unbalanced. Virtual nodes map each physical server to many ring positions, improving distribution. Most production systems use 100-200 virtual nodes per server.

Key Concepts

consistent hashingpartitioninghorizontal scaling

main.py

python

#!/usr/bin/env python3
import sys
import json
import hashlib
class ConsistentHashRing:
    def __init__(self, replicas=100):
        self.replicas = replicas
        self.ring = {}  # hash -> node
        self.sorted_keys = []
        self.nodes = set()
    
    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_node(self, node):
        # TODO: Add node with virtual nodes to ring
        pass
    
    def remove_node(self, node):
        # TODO: Remove node and its virtual nodes
        pass
    
    def get_node(self, key):
        # TODO: Find node responsible for key
        pass
class DistributedCache:
    def __init__(self, nodes):
        self.ring = ConsistentHashRing()
        self.caches = {}  # node -> local cache dict
        for node in nodes:
            self.ring.add_node(node)
            self.caches[node] = {}
    
    def get(self, key):
        # TODO: Route to correct node and get
        pass
    
    def set(self, key, value):