Optimize for High-Throughput ID Generation - The Identifier

                      TASK
                    

Implementation

Optimize your ID generator for maximum throughput. Real systems like Twitter generate millions of IDs per second. Your implementation should handle high concurrency without becoming a bottleneck.

Optimization strategies:

Minimize lock contention in multi-threaded scenarios
Use atomic operations where possible
Consider pre-generating IDs in batches
Profile and measure your throughput

Target: Handle 10,000+ ID generations per second on a single node.

Sample Test Cases

Generate single 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":"generate","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":"generate_ok","in_reply_to":2,"msg_id":1,"id":"n1-0"}}

Hints

Hint 1▾

Minimize lock contention

Hint 2▾

Consider lock-free approaches

Hint 3▾

Batch ID generation if possible

Resources

Python Threading Best Practices

Python documentation on threading primitives

Go Atomic Operations

Go documentation on atomic operations for lock-free programming

                      OVERVIEW
                    

Theoretical Hub

Throughput Optimization

ID generation is often on the critical path. Every database insert, every message, every event needs an ID. Even small inefficiencies multiply across millions of operations.

Bottleneck Analysis

def generate_id():
    with lock:           # ← Contention point
        timestamp = now()
        sequence += 1
        return id

Every concurrent request must acquire the same lock, serializing all ID generation.

Optimization Techniques

Technique	Benefit	Complexity
Separate locks for msg_id and id_gen	Reduces contention	Low
Atomic counters	Lock-free increment	Medium
Pre-allocated ID ranges	Batch amortization	High

Go's Advantage

Go's sync/atomic package provides lock-free primitives:

import "sync/atomic"

var counter int64

func getNext() int64 {
    return atomic.AddInt64(&counter, 1)
}

This is significantly faster than mutex-based approaches under high contention.

Key Concepts

performancethroughputoptimization

main.py

python

#!/usr/bin/env python3
import sys
import json
import time
import threading
from concurrent.futures import ThreadPoolExecutor
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.last_timestamp = 0
        self.sequence = 0
        self.lock = threading.Lock()
        self.output_lock = threading.Lock()
    
    def send(self, dest, body):
        with self.lock:
            body["msg_id"] = self.next_msg_id
            self.next_msg_id += 1
        message = {"src": self.node_id, "dest": dest, "body": body}
        with self.output_lock:
            print(json.dumps(message), flush=True)
    
    def reply(self, request, body):
        body["in_reply_to"] = request["body"]["msg_id"]
        self.send(request["src"], body)
    
    def generate_id(self):
        # TODO: Optimize for high throughput
        with self.lock:
            timestamp = int(time.time() * 1000)
            if timestamp == self.last_timestamp:
                self.sequence += 1
            else:
                self.sequence = 0
                self.last_timestamp = timestamp
            node_num = int(self.node_id[1:]) if self.node_id else 0
            return (timestamp << 22) | (node_num << 12) | (self.sequence & 