Optimization and Technical Trade Offs Questions

from collections import defaultdict
from typing import Dict, Tuple

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        """
        capacity: max tokens per bucket
        refill_rate: tokens added per second
        """
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        # store key -> (tokens, last_timestamp)
        self.buckets: Dict[str, Tuple[float, float]] = {}

    def allow_request(self, key: str, timestamp: float) -> bool:
        tokens, last = self.buckets.get(key, (self.capacity, timestamp))
        # accumulate tokens since last timestamp
        elapsed = max(0.0, timestamp - last)
        tokens = min(self.capacity, tokens + elapsed * self.refill_rate)
        if tokens >= 1.0:
            tokens -= 1.0
            allowed = True
        else:
            allowed = False
        # update bucket state
        self.buckets[key] = (tokens, timestamp)
        return allowed

package lru

import (
	"container/list"
	"hash/fnv"
	"sync"
)

type entry struct {
	key   string
	value interface{}
	elem  *list.Element
}

type shard struct {
	sync.Mutex
	items    map[string]*entry
	lru      *list.List // front = most recent
	capacity int
}

type ShardedLRU struct {
	shards []*shard
	n      uint32
}

func NewShardedLRU(shardCount int, capacityPerShard int) *ShardedLRU {
	s := &ShardedLRU{n: uint32(shardCount), shards: make([]*shard, shardCount)}
	for i := range s.shards {
		s.shards[i] = &shard{
			items:    make(map[string]*entry),
			lru:      list.New(),
			capacity: capacityPerShard,
		}
	}
	return s
}

func (s *ShardedLRU) shardFor(key string) *shard {
	h := fnv.New32a()
	h.Write([]byte(key))
	return s.shards[h.Sum32()%s.n]
}

func (s *ShardedLRU) Get(key string) (interface{}, bool) {
	sh := s.shardFor(key)
	sh.Lock()
	defer sh.Unlock()
	if e, ok := sh.items[key]; ok {
		sh.lru.MoveToFront(e.elem)
		return e.value, true
	}
	return nil, false
}

func (s *ShardedLRU) Put(key string, value interface{}) {
	sh := s.shardFor(key)
	sh.Lock()
	defer sh.Unlock()
	if e, ok := sh.items[key]; ok {
		e.value = value
		sh.lru.MoveToFront(e.elem)
		return
	}
	ent := &entry{key: key, value: value}
	ent.elem = sh.lru.PushFront(ent)
	sh.items[key] = ent
	if sh.lru.Len() > sh.capacity {
		// evict least recent in this shard
		back := sh.lru.Back()
		if back != nil {
			le := back.Value.(*entry)
			delete(sh.items, le.key)
			sh.lru.Remove(back)
		}
	}
}