Uber - High-Throughput Rate Limiter

Dados da empresa e da vaga

• Empresa: Uber Technologies, Inc.
• Sede: São Francisco, Califórnia, EUA (com polos globais em Seattle, Amsterdã, São Paulo e Hyderabad)
• Perfil da vaga: Senior Software Engineer — Core Platform & Dispatching Infrastructure
• Modelo de trabalho: Remoto internacional ou híbrido
• Faixa salarial estimada da vaga:
  • Sênior nos EUA (L5): $175.000 a $220.000 (Base) / $280.000 a $380.000+ USD/ano (Total Comp com RSUs na NYSE: UBER)
  • Sênior Internacional Remoto (LATAM/Europa): $85.000 a $135.000 USD/ano (B2B Contractor / EOR)
• Stack principal do time: Go, Java, Apache Kafka, Cassandra, Redis, Docker, Kubernetes, Jaeger, Prometheus, M3DB

---

Contexto do desafio técnico

A Uber é amplamente reconhecida na comunidade global de Go pelo seu guia oficial de estilo (Uber Go Style Guide) e por manter pacotes essenciais de infraestrutura de alta velocidade (como o logger estruturado zap e a biblioteca de limitação de vazão ratelimit).

Em entrevistas técnicas para o time de plataforma da Uber, os avaliadores focam em concorrência pesada, segurança de memória (thread-safety), latência sub-microssegundo e prevenção de vazamentos de recursos.

Este desafio clássico de live coding ou take-home exige que o candidato projete e implemente um Rate Limiter Concorrente Multi-Inquilino (Multi-Tenant) em Go do zero, sem o uso de bibliotecas de terceiros, capaz de proteger APIs centrais de despacho e cobrança contra rajadas descontroladas de tráfego.

---

Requisitos funcionais e de negócio

1. Algoritmo de limitação uniforme ou de balde: O limitador deve controlar a vazão de requisições de acordo com uma política de cota (ex.: 100 requisições por segundo por cliente).
   • Se o cliente exceder a cota permitida dentro da janela temporal, o limitador deve rejeitar a operação imediatamente (retornando false ou um erro ErrRateLimitExceeded) ou bloquear o chamador até o próximo intervalo permitido (comportamento de Leaky Bucket).
2. Suporte a Múltiplos Clientes (Multi-Tenant):
   • O limitador deve operar dinamicamente por chave identificadora (como endereço IP, client_id ou token de motorista/passageiro).
   • Cada cliente possui seu próprio estado de consumo e relógio de taxa.
3. Mecanismo ativo de descarte de memória (Memory Eviction / Janitor):
   • A grande armadilha do teste: Se um milhão de clientes distintos fizerem uma única requisição em um dia, armazenar cada limitador em um map global sem expiração causará um vazamento de memória contínuo (memory leak).
   • O candidato deve implementar uma rotina em segundo plano (janitor goroutine) ou uma política de remoção baseada em tempo ocioso (LRU ou TTL) para limpar chaves inativas sem interromper as operações concorrentes de leitura e escrita.
4. Controle de encerramento gracioso (Graceful Shutdown):
   • O rate limiter deve aceitar um context.Context para encerrar adequadamente as goroutines de limpeza em segundo plano quando o servidor for desligado.

---

Requisitos não-funcionais e critérios de engenharia

1. Zero condições de corrida (Race Detector):
   • O código deve passar com 100% de sucesso sob o detector de condições de corrida do compilador:

     go test -race -v ./...

2. Latência de decisão sub-microssegundo:
   • Como o rate limiter é executado no caminho crítico de cada requisição HTTP/gRPC, cada verificação (Allow(key)) deve demorar menos de 1 microssegundo em média e não pode gerar alocações frequentes no Heap.
3. Uso de primitivas adequadas:
   • Os avaliadores da Uber verificam se o candidato utilizou sync.RWMutex, sync.Map ou primitivas atômicas (sync/atomic) em vez de canais excessivos para proteção de memória compartilhada.

---

Exemplo de implementação idiomática em Go

package ratelimit

import (
	"context"
	"sync"
	"time"
)

type clientBucket struct {
	lastSeen   time.Time
	tokens     float64
	maxTokens  float64
	refillRate float64 // tokens por segundo
	mu         sync.Mutex
}

func (b *clientBucket) allow(now time.Time) bool {
	b.mu.Lock()
	defer b.mu.Unlock()

	// Recarrega tokens proporcionalmente ao tempo decorrido
	elapsed := now.Sub(b.lastSeen).Seconds()
	b.lastSeen = now
	b.tokens += elapsed * b.refillRate
	if b.tokens > b.maxTokens {
		b.tokens = b.maxTokens
	}

	if b.tokens >= 1.0 {
		b.tokens -= 1.0
		return true
	}

	return false
}

type MultiTenantLimiter struct {
	mu           sync.RWMutex
	clients      map[string]*clientBucket
	rate         float64 // tokens/s
	capacity     float64
	idleTTL      time.Duration
}

func NewMultiTenantLimiter(ctx context.Context, rate, capacity float64, idleTTL, cleanupInterval time.Duration) *MultiTenantLimiter {
	limiter := &MultiTenantLimiter{
		clients:  make(map[string]*clientBucket),
		rate:     rate,
		capacity: capacity,
		idleTTL:  idleTTL,
	}

	// Goroutine zeladora (Janitor) para prevenir vazamento de memória
	go limiter.startJanitor(ctx, cleanupInterval)

	return limiter
}

func (m *MultiTenantLimiter) Allow(clientID string) bool {
	now := time.Now()

	m.mu.RLock()
	bucket, exists := m.clients[clientID]
	m.mu.RUnlock()

	if !exists {
		m.mu.Lock()
		// Double-check após adquirir o lock de escrita
		bucket, exists = m.clients[clientID]
		if !exists {
			bucket = &clientBucket{
				lastSeen:   now,
				tokens:     m.capacity,
				maxTokens:  m.capacity,
				refillRate: m.rate,
			}
			m.clients[clientID] = bucket
		}
		m.mu.Unlock()
	}

	return bucket.allow(now)
}

func (m *MultiTenantLimiter) startJanitor(ctx context.Context, interval time.Duration) {
	ticker := time.NewTicker(interval)
	defer ticker.Stop()

	for {
		select {
		case <-ctx.Done():
			return
		case <-ticker.C:
			m.cleanup()
		}
	}
}

func (m *MultiTenantLimiter) cleanup() {
	now := time.Now()
	m.mu.Lock()
	defer m.mu.Unlock()

	for id, bucket := range m.clients {
		bucket.mu.Lock()
		isIdle := now.Sub(bucket.lastSeen) > m.idleTTL
		bucket.mu.Unlock()

		if isIdle {
			delete(m.clients, id)
		}
	}
}

---

O que os avaliadores da Uber buscam

1. Bloqueio granular (Lock Granularity): No código acima, o mapa global é protegido com sync.RWMutex apenas para localizar o cliente. A atualização do saldo de fichas ocorre no mutex individual do cliente (bucket.mu). Isso impede que o tráfego do cliente A bloqueie as requisições do cliente B.
2. Double-Checked Locking: Ao inserir uma nova chave no mapa, a verificação se a chave existe é repetida após adquirir a trava de escrita para evitar condições de corrida entre leituras e escritas simultâneas.
3. Gerenciamento de tempo monotônico: Em Go, time.Now() inclui uma leitura do relógio monotônico que previne bugs caso o relógio do sistema operacional seja ajustado por NTP durante a execução.
4. Testes de carga com b.ReportAllocs(): Provar que a função Allow() opera com 0 allocs/op em regime estável de clientes já cadastrados.