Projete um Serviço de Encurtamento de URL

A. Estratégia de Geração de URL Curta

1. Escolha baseada em requisitos

• Novas gravações: 100M/mês ≈ 3,3M/dia ≈ 38,6 gravações/segundo em média.
• Leituras na proporção 100:1 ≈ 3,3B/mês ≈ 1.270 leituras/segundo em média, com pico provavelmente 10–50x maior.
• Precisamos de IDs compactos, globalmente únicos e com consulta muito rápida.

2. Abordagem de geração de código
   Eu usaria um serviço de geração de ID determinístico mais codificação Base62.

Fluxo:

• Um ID numérico globalmente único é gerado.
• Esse inteiro é codificado em Base62 usando os caracteres [0-9a-zA-Z].
• Exemplo: 125 -> "21" em Base62.

Por que essa abordagem:

• Nenhum risco de colisão se os IDs forem únicos.
• Muito rápido de gerar.
• Fácil de operar em comparação com a verificação de colisão de código aleatório.
• Crescimento previsível do comprimento do código.

3. Projeto do gerador de ID
   Opção preferida:

• Usar um gerador de ID de 64 bits no estilo Snowflake ou um alocador de intervalos centralizado.
• Os campos de ID podem incluir timestamp + ID da máquina + sequência, ou podemos alocar intervalos monotonicamente crescentes para os servidores de aplicativos.

Duas boas implementações:

• IDs estilo Snowflake: descentralizados, alto rendimento, baixa coordenação.
• Alocação de intervalos de um armazenamento de metadados: cada nó de gravação aluga um bloco de IDs, por exemplo, 1M de IDs por vez.

Prefiro a alocação de intervalos pela simplicidade, pois o rendimento de gravação é modesto. Cada servidor de gravação pode gerar IDs localmente a partir de seu intervalo alugado, evitando uma dependência central quente.

4. Esquema de codificação e comprimento esperado
   Capacidade Base62:

• 62^6 ≈ 56,8B
• 62^7 ≈ 3,52T

Links totais em 5 anos:

• 100M/mês * 60 meses = 6B links

Portanto, 6 caracteres Base62 não são suficientes para margem de longo prazo se os IDs forem usados densamente globalmente, mas 7 caracteres são mais do que suficientes.

Comprimento esperado:

• Comece com 6 caracteres para o início do ciclo de vida, se desejado.
• Na prática, padronize em 7 caracteres para manter a implementação simples e evitar mudanças de comprimento nas expectativas do usuário.

5. Tratamento de colisão
   Com IDs únicos determinísticos:

• Nenhuma colisão no nível do código.
• Restrição de exclusividade do banco de dados no short_code fornece uma rede de segurança final.
• Se um duplicado muito raro for observado devido a um bug de software ou configuração incorreta de ID, regenere a partir de um novo ID e alerte.

6. Estratégia de exaustão

• Base62 de 7 caracteres oferece 3,52 trilhões de combinações, muito além dos 6B necessários em 5 anos.
• Se a escala futura crescer substancialmente, suporte códigos de 8 caracteres sem problemas.
• O serviço de redirecionamento deve tratar o comprimento do código como variável, portanto, não há problema de migração.

7. Aliases personalizados opcionais
   Se o produto suportar aliases definidos pelo usuário:

• Armazene na mesma tabela de mapeamento com exclusividade imposta.
• Reserve palavras bloqueadas e termos abusivos.
• Aplique limites de taxa mais rigorosos, pois aliases personalizados são um ponto de contenção.

B. Armazenamento de Dados

1. Escolha do banco de dados primário
   Use um armazenamento de chave-valor distribuído e altamente disponível para o mapeamento de URL, como:

• DynamoDB / Bigtable / Cassandra

Por quê:

• O padrão de acesso primário é uma simples consulta por chave usando short_code.
• Necessidade de escalabilidade horizontal, alta disponibilidade e leituras multi-réplica.
• Gravações são modestas, leituras são dominantes.
• O acesso chave-valor é ideal para latência de redirecionamento inferior a 50ms.

Eu escolheria um armazenamento do tipo DynamoDB ou Cassandra conceitualmente:

• Particione por hash do short_code.
• Replique entre zonas de disponibilidade.
• Ajuste para leituras de ponto de baixa latência.

2. Armazenamentos secundários

• Banco de dados relacional para metadados do plano de controle, faturamento, usuários, domínios, políticas.
• Armazenamento de objetos + data lake para análise/logs de cliques.
• Armazenamento de pesquisa/índice opcional se os administradores precisarem consultar por criador, data, tags, etc.

3. Projeto do esquema
   Tabela de mapeamento primária:

• short_code (PK)
• destination_url
• created_at
• expires_at (nulo)
• owner_id (nulo)
• status (ativo, desativado, excluído)
• redirect_type (301/302)
• checksum ou hash normalizado_url (opcional)
• ponteiro de metadados (opcional)

Tabela de dedup opcional se o produto desejar que a mesma URL longa retorne a mesma URL curta por locatário:

• dedup_key = hash(tenant_id + canonicalized_url)
• short_code
  Isso é opcional; muitos encurtadores de URL não deduplicam globalmente porque a semântica difere por usuário, campanha ou necessidades de análise.

4. Estimativa de armazenamento em 5 anos
   Links totais:

• 6B registros

Estimativa aproximada por registro:

• short_code: ~8 bytes de equivalente bruto
• destination_url: assume média de 200 bytes
• timestamps/status/flags: ~24 bytes
• sobrecarga de replicação/versionamento/índice: substancial em sistemas reais
• sobrecarga do motor de armazenamento: assume um total efetivo de ~350–500 bytes por registro no banco de dados primário

Usando 400 bytes/registro:

• 6B * 400 bytes = 2,4 TB de dados lógicos brutos

Com fator de replicação 3:

• 7,2 TB

Adicionar índices, sobrecarga de compactação, marcadores de exclusão, metadados, margem operacional:

• Planejar 10–15 TB de armazenamento primário em 5 anos

Logs de análise/cliques são muito maiores que os mapeamentos.
A 100 leituras por gravação:

• 600B redirecionamentos em 5 anos
  Se cada evento de log de clique tivesse em média apenas 100 bytes compactados, isso seria ~60 TB compactados, provavelmente muito mais com campos mais ricos. Portanto, os logs devem ir para armazenamento de objetos barato, não para o banco de dados de serviço.

5. Estratégia de particionamento/sharding
   Sharding da tabela primária:

• Chave de partição: short_code ou hash(short_code)
• Distribuição uniforme porque os IDs são codificados a partir de IDs numéricos bem distribuídos ou IDs de intervalo misturados apropriadamente

Nota importante:

• IDs puramente sequenciais podem criar partições quentes em alguns bancos de dados se a localidade da chave for importante.
• Para evitar isso, faça uma das seguintes opções:
  1. Hash do short_code para posicionamento da partição, ou
  2. Use IDs com entropia suficiente nos bits inferiores, ou
  3. Prefira bits de shard antes da codificação Base62

Eu particionaria explicitamente por hash no short_code para garantir distribuição uniforme.

C. Arquitetura do Caminho de Leitura

1. Visão geral do caminho de leitura
   Fluxo da solicitação:

• Usuário acessa https://sho.rt/abc1234
• DNS roteia para a borda/CDN mais próxima
• CDN encaminha para o serviço de redirecionamento regional se não for um acerto de cache
• Serviço de redirecionamento verifica o cache na memória/Redis
• Em caso de falha de cache, lê do armazenamento KV distribuído
• Retorna HTTP 301/302 com cabeçalho Location
• Emite assincronamente o evento de clique para o pipeline de análise

2. Atendendo à latência p95 < 50ms
   O caminho de redirecionamento deve ser extremamente leve.

Exemplo de orçamento de latência:

• Roteamento de borda/CDN: pequeno, geograficamente local
• Processamento do aplicativo: 1–3ms
• Acerto de cache Redis/na memória: 1–5ms
• Caminho de falha do banco de dados dentro da região: 5–15ms típico
• O p95 total abaixo de 50ms é alcançável com serviço regional e cache agressivo

3. Camadas de cache
   Camada 1: Cache de CDN/borda

• Armazena em cache as respostas de redirecionamento para links quentes na borda.
• Muito eficaz porque muitos links curtos populares são acessados repetidamente.
• Use cabeçalhos cache-control com TTL, por exemplo, minutos a horas, dependendo da mutabilidade.
• Se os links puderem ser desativados rapidamente, escolha TTL mais curto ou suporte de purga.

Camada 2: Cache local do aplicativo

• Cada nó de redirecionamento mantém um cache LRU de mapeamentos quentes.
• Latência ultrabaixa, evita o salto de rede para o Redis.
• Bom para os códigos mais solicitados.

Camada 3: Cache distribuído (Redis/Memcached)

• Cache compartilhado para a frota regional.
• Armazena short_code -> destination_url, status, tipo de redirecionamento.
• TTL pode ser longo para links imutáveis; mais curto para links mutáveis/controlados por administrador.

4. Estratégia de replicação para leituras

• Réplicas Multi-AZ dentro de cada região.
• Serve leituras de réplicas de armazenamento da região local.
• Ativo-ativo entre várias regiões para tráfego global.
• Use geo-DNS ou Anycast para rotear para a região saudável mais próxima.

5. Estratégia de população de cache

• Leitura direta na falha: o aplicativo busca do banco de dados, popula o Redis e o cache local.
• Cache negativo para códigos inexistentes/desativados com TTL curto para absorver ataques e tempestades de digitação.
• Pré-aqueça o cache para links em tendência, se conhecidos por análise.

6. Semântica de redirecionamento

• 302 por padrão se o destino puder mudar ou se as políticas de análise/rastreamento exigirem flexibilidade.
• 301 para links permanentes onde clientes e CDNs podem armazenar em cache agressivamente.
• A decisão do produto pode expor ambas as opções.

7. Tratamento de abuso no caminho de leitura

• Limite de taxa por IP / ASN / token para solicitações de alta taxa suspeitas.
• WAF e filtros de bot na CDN.
• Proteja a origem contra varredura de short-code por força bruta.

D. Arquitetura do Caminho de Gravação

1. Visão geral do caminho de gravação
   Fluxo da solicitação:

• Cliente envia URL longa e metadados opcionais/alias personalizado.
• Gateway de API autentica e limita a taxa.
• Validação e normalização de URL ocorrem na camada de aplicativo sem estado.
• O aplicativo obtém/gera o short code.
• Persiste o mapeamento no armazenamento KV primário.
• Popula caches de forma assíncrona ou síncrona para disponibilidade imediata.
• Emite evento de criação para a fila para análise, verificação de abuso e indexação downstream.

2. Capacidade
   100M/mês não é alto para sistemas modernos:

• Média de ~39 gravações/segundo
• Mesmo um estouro de 100x são apenas alguns milhares de gravações/segundo

Portanto, os principais objetivos são confiabilidade, idempotência e simplicidade operacional, em vez de rendimento de gravação extremo.

3. Etapas de validação

• Validar sintaxe da URL.
• Impor protocolos permitidos, geralmente apenas http/https.
• Verificação opcional de navegação segura ou malware assíncrona; se o risco for encontrado, desative o link.
• Canonicalizar a URL para lógica de dedup opcional.

4. Filas e trabalho assíncrono
   Use uma fila ou log durável como Kafka/SQS/PubSub para efeitos colaterais:

• Evento de análise para criação de novo link
• Detecção de abuso/golpe/phishing
• Aquecimento de cache
• Indexação de pesquisa
• Pipeline de notificação/auditoria

O caminho crítico deve incluir apenas o necessário para criar o mapeamento e retornar a URL encurtada.

5. Modelo de consistência
   Para a resposta de criação, use consistência write-after-create para o novo short code:

• Assim que a API retornar sucesso, o redirecionamento deve funcionar imediatamente.

Como:

• Persistir o mapeamento para quórum/líder no banco de dados primário antes de reconhecer.
• Opcionalmente, gravar diretamente no Redis após o commit do banco de dados.
• O caminho de redirecionamento volta ao banco de dados em caso de falha de cache, portanto, o atraso na propagação do cache não quebra a correção.

6. Idempotência
   Suporte a chaves de idempotência para clientes de API para evitar links duplicados durante novas tentativas.

• Armazene request_id -> short_code por um TTL limitado em um armazenamento rápido.
• Especialmente útil para cenários de retentativa de rede/móvel.

7. Limitação de taxa

• Cotas por usuário/chave de API para controlar abusos.
• Limites mais fortes em solicitações de alias personalizados.
• Salvaguardas globais para evitar amplificação de gravação induzida por ataques.

E. Confiabilidade e Tolerância a Falhas

1. Alvo de disponibilidade: 99,9%
   99,9% de tempo de atividade permite cerca de 43,8 minutos de inatividade/mês. Isso é alcançável com implantação multi-AZ e failover regional.

2. Tratamento de falhas
   Falha de nó:

• Nós de aplicativo sem estado atrás de balanceadores de carga; substitua instâncias não saudáveis automaticamente.
• Caches locais são descartáveis.
• Redis implantado como cluster/modo sentinel de alta disponibilidade.

Falha de AZ:

• Camada de aplicativo implantada em pelo menos 3 AZs.
• Banco de dados primário replicado entre AZs.
• Balanceador de carga remove a AZ não saudável.

Interrupção regional/DC:

• Serviço de leitura ativo-ativo entre várias regiões.
• Dados replicados entre regiões de forma assíncrona ou quase síncrona, dependendo das capacidades do banco de dados.
• Gerenciador de DNS/tráfego faz failover dos usuários para a região saudável.

3. Durabilidade dos dados

• Fator de replicação do banco de dados primário 3 entre AZs.
• Snapshots/backups periódicos para armazenamento de objetos.
• Arquivamento de WAL/log de commit, se suportado.
• Cópias de backup entre regiões para recuperação de desastres.

4. Estratégia de backup e recuperação

• Snapshots completos diários mais backups incrementais.
• Recuperação point-in-time para exclusão/corrupção acidental.
• Exercícios de restauração regulares em staging para verificar RTO/RPO.
• Retenção de backup alinhada com o requisito de acessibilidade de 5 anos e necessidades de conformidade.

Objetivos razoáveis:

• RPO: minutos a 1 hora, dependendo do modelo de replicação entre regiões
• RTO: menos de 1 hora para failover regional, mais tempo para reconstrução completa do armazenamento, mas isso deve ser raro

5. Estratégia de invalidação de cache
   Se os links forem em sua maioria imutáveis, o cache é simples.
   Para links mutáveis (desativar/alterar destino/expiração):

• Atualize o banco de dados primeiro.
• Publique evento de invalidação.
• Remova a chave do Redis e as entradas do cache local.
• Limpe o cache da CDN se o cache de borda for usado para esse código.
• Use TTL limitado para que o cache desatualizado se auto-cure, mesmo que a invalidação falhe.

6. Proteção contra corrupção de dados e abuso

• Restrições de exclusividade do banco de dados no short_code.
• Checksums/campos de versão para registros.
• Logs de auditoria para ações administrativas.
• Estado de exclusão lógica ou desativado em vez de exclusão física, sempre que possível.
• Ferramentas de escaneamento e desativação de malware/phishing.

F. Principais Compromissos

1. Geração de ID determinística vs códigos curtos aleatórios
   Opções:

• IDs determinísticos sequenciais/baseados em intervalos: simples, sem colisões, compactos, rápidos.
• Códigos aleatórios: menos previsíveis/enumeráveis, mas exigem verificação de colisão e mais complexidade.

Escolha:

• Eu escolho IDs determinísticos codificados em Base62.

Por quê:

• Mais simples, mais rápido e operacionalmente mais seguro para esta escala.
• Sem colisões sem loops de retentativa.
• Melhor ajuste porque o rendimento é modesto e o principal desafio é a latência de leitura.

Custo:

• Os códigos podem ser mais enumeráveis/previsíveis.
  Mitigação:
• Limitação de taxa, detecção de bots, aliases opcionais mais longos/não sequenciais para links sensíveis.

2. Consistência mais forte na criação vs consistência eventual em todos os lugares
   Opções:

• A consistência eventual poderia reduzir a latência de gravação e simplificar as gravações multirregionais.
• O reconhecimento forte após a gravação durável garante que um short URL retornado funcione imediatamente.

Escolha:

• Consistência forte para o caminho de criação de link único dentro de uma região de origem; consistência eventual para caches secundários e propagação entre regiões.

Por quê:

• Melhor experiência do usuário: assim que a API retornar, o redirecionamento deve ser bem-sucedido.
• O volume de gravação é baixo o suficiente para não precisarmos relaxar a consistência na gravação crítica.

3. Cache agressivo na borda vs invalidação rápida
   Opções:

• TTLs longos de CDN maximizam o desempenho de leitura e reduzem o custo de origem.
• TTLs curtos tornam as operações de desativação/atualização mais rápidas.

Escolha:

• TTL moderado com purga explícita para links mutáveis/gerenciados por administrador; TTL mais longo para links imutáveis.

Por quê:

• A maioria dos URLs encurtados são efetivamente imutáveis, portanto, o cache oferece grandes benefícios de latência e custo.
• Mas as desativações de abuso exigem invalidação razoavelmente rápida.

4. Simplicidade vs riqueza de análise no caminho de redirecionamento
   Opções:

• Registro de cliques síncrono fornece garantias de análise imediatas, mas adiciona latência e acoplamento de falhas.
• Emissão de eventos assíncrona mantém os redirecionamentos rápidos, mas a análise pode atrasar ou perder pequenas quantidades durante falhas.

Escolha:

• Análise assíncrona.

Por quê:

• O SLA rígido do produto é a latência de redirecionamento e a disponibilidade, não a análise em tempo real sem perdas.
• O caminho de redirecionamento nunca deve bloquear em sistemas de log downstream.

Resumo da arquitetura

• Geração de short code: IDs únicos de 64 bits baseados em intervalo alugado ou estilo Snowflake codificados em Base62, códigos padrão de 7 caracteres.
• Armazenamento primário: banco de dados KV distribuído, particionado por hash por short_code, RF=3, multi-AZ.
• Caminho de leitura: CDN + cache local + Redis + fallback de KV store; leituras ativo-ativas multirregionais.
• Caminho de gravação: API sem estado + gravação de DB durável + fila assíncrona para efeitos colaterais; idempotência e limites de taxa.
• Confiabilidade: multi-AZ, replicação entre regiões, backups, eventos de invalidação de cache, failover de DNS.
• Este projeto suporta confortavelmente 100M novos URLs/mês, proporção de leitura de 100:1, retenção de 5 anos, 99,9% de tempo de atividade e redirecionamentos <50ms p95.

Design of a URL Shortening Service

This document outlines the design for a URL shortening service capable of handling 100 million new URLs per month, a 100:1 read-to-write ratio, 5-year data retention, 99.9% uptime, and redirect latency under 50ms at the 95th percentile.

A. Short URL Generation Strategy

Encoding Scheme: We will use Base62 encoding (0-9, a-z, A-Z). This scheme is URL-safe and provides a compact representation for unique identifiers.

Expected URL Length: Over 5 years, the service needs to support 100 million URLs/month * 12 months/year * 5 years = 6 billion unique URLs. A 6-character Base62 string provides 62^6 = 56,800,235,584 possible unique keys, which is more than sufficient for 6 billion URLs. We will start with 6 characters and have the flexibility to extend to 7 characters (62^7 ≈ 352 billion keys) if the key space ever approaches exhaustion.

Generation Method: We will employ a Key Generation Service (KGS). This service will be responsible for generating unique, monotonically increasing numeric IDs. These IDs will then be Base62 encoded to produce the short URL codes. The KGS can use a distributed ID generation algorithm (e.g., a modified Snowflake ID generator or a dedicated service that increments a counter and pre-allocates blocks of IDs to multiple KGS instances to avoid contention). This approach guarantees uniqueness and avoids collisions by design, eliminating the need for database lookups during key generation.

Collision Handling: With the KGS generating unique numeric IDs, collisions are inherently avoided. Each generated ID is unique, and its Base62 encoding will also be unique. If a random generation strategy were chosen, collision handling would involve checking the database for existence and regenerating upon collision, which adds latency and complexity.

Exhaustion of Key Space: As discussed, a 6-character Base62 key provides ample space for 6 billion URLs. Should the service grow beyond this, extending the key length to 7 characters would provide significantly more capacity. The KGS would be designed to handle this transition seamlessly by generating longer IDs when necessary.

B. Data Storage

Database Selection: For the core short_code to long_url mapping, we will use a distributed NoSQL key-value store like Apache Cassandra. Cassandra is highly scalable, fault-tolerant, and optimized for high-volume, low-latency reads and writes, making it ideal for our read-heavy workload. Its distributed nature and built-in replication capabilities ensure high availability and data durability.

Storage Estimation:

• Total URLs over 5 years: 6 billion.
• Each entry will store:
  • short_code: 6-7 characters (approx. 7 bytes)
  • long_url: Average 100 characters (approx. 100 bytes)
  • created_at: Timestamp (8 bytes)
  • expires_at: Timestamp (8 bytes, for 5-year retention)
  • click_count: Counter (8 bytes)
  • user_id (optional): e.g., 36 bytes for UUID
• Total per entry (conservative estimate, including overhead): ~150 bytes.
• Total raw storage: 6 billion URLs * 150 bytes/URL = 900 billion bytes = 0.9 TB.
• With a replication factor of 3 (common for Cassandra for high availability): 0.9 TB * 3 = 2.7 TB.

Schema Design (Cassandra):

CREATE TABLE short_urls (
    short_code text PRIMARY KEY,  -- Partition key for even distribution
    long_url text,
    created_at timestamp,
    expires_at timestamp,
    click_count counter,
    user_id text
);

Partitioning/Sharding Strategy: Cassandra inherently handles data partitioning and sharding based on the primary key (short_code). The Base62 short_code provides a good distribution of data across the cluster nodes, preventing hot spots and ensuring efficient data retrieval. We will configure Cassandra with a replication factor of 3 across multiple data centers or availability zones for fault tolerance and high availability.

C. Read Path Architecture

Throughput: With 100M writes/month and a 100:1 read-to-write ratio, we expect 10 billion reads/month, averaging approximately 3,858 reads/second. Peak loads could be 5-10x higher, reaching 20,000-40,000 reads/second.

Architecture Components:

1. Load Balancer (e.g., AWS ELB, Nginx): Distributes incoming HTTP requests for short URLs across multiple Redirect Service instances.
2. Distributed Cache (e.g., Redis Cluster): This is critical for meeting the latency and throughput requirements. The cache will store short_code to long_url mappings. Given the 100:1 read-to-write ratio, a very high cache hit rate (e.g., 95%+) is expected, significantly reducing the load on the database.
   • Cache Invalidation: Short URL mappings are generally immutable. Cache entries can have a very long TTL or be permanent. If a long_url ever needs to be updated (rare), an explicit cache invalidation would be triggered.
3. Redirect Service (Application Servers): A fleet of stateless application servers (e.g., running Go, Java, or Node.js) behind the load balancer.
   • Upon receiving a short URL request, the service first checks the Redis cache.
   • If a cache hit, it immediately issues an HTTP 301 (Permanent) or 302 (Temporary) redirect to the long_url.
   • If a cache miss, it queries the Cassandra database for the short_code.
   • Once retrieved from Cassandra, the mapping is stored in Redis for future requests, and then the redirect is issued.
   • Click counts are updated asynchronously (e.g., by sending messages to a Kafka queue for processing by a separate analytics service or by incrementing a counter in Cassandra directly, which supports atomic increments).
4. Database (Cassandra Cluster): Serves as the persistent storage for all URL mappings and handles cache misses. Its distributed nature and replication ensure high availability and low-latency data retrieval for the scale required.

Replication Strategies:

• Application Servers: Multiple instances deployed across different availability zones, managed by auto-scaling groups.
• Cache: Redis Cluster with master-replica configurations for each shard, ensuring high availability and data redundancy.
• Database: Cassandra's native multi-datacenter replication (e.g., 3x replication factor across at least two data centers) provides strong fault tolerance and disaster recovery capabilities.

D. Write Path Architecture

Throughput: 100 million new URLs per month translates to an average of ~38 writes/second. Peak loads might reach 300-400 writes/second.

Architecture Components:

1. Load Balancer: Distributes incoming requests for new URL shortenings to the Write Service instances.
2. Write Service (API Gateway/Application Servers):
   • Receives the long_url from the user.
   • Calls the Key Generation Service (KGS) to obtain a unique short_code.
   • Constructs the short_code to long_url mapping.
   • Publishes this mapping to a Message Queue (e.g., Apache Kafka). This decouples the write service from the database, provides buffering, and enhances reliability.
   • Returns the generated short_code to the user.
3. Key Generation Service (KGS): As described in Section A, this service generates unique numeric IDs and encodes them to Base62 short_codes. It can pre-generate blocks of keys to minimize latency during peak write times.
4. Worker Processes (Consumers): A pool of worker processes consumes messages from the Kafka queue.
   • For each message, the worker writes the short_code and long_url to the Cassandra database.
   • It then immediately writes the mapping to the Redis Cache to ensure the newly created short URL is instantly available for reads.
5. Database (Cassandra Cluster): Persistently stores the new URL mappings.

Consistency Considerations:

• For the short_code to long_url mapping, strong consistency is desired. By writing to Cassandra with appropriate consistency levels (e.g., QUORUM) and then immediately populating the cache, we ensure that once a short URL is returned to the user, it will correctly resolve.
• The use of a message queue provides eventual consistency for the persistence layer, but the immediate cache update ensures the read path is consistent for new URLs. If the cache update fails, the read path will eventually hit the database, which will be consistent.

E. Reliability and Fault Tolerance

Node Failures:

• Application Servers (Redirect & Write Services): Stateless and deployed in auto-scaling groups across multiple availability zones. Load balancers automatically route traffic away from failed instances, and new instances are launched to replace them.
• Distributed Cache (Redis Cluster): Configured with master-replica replication. If a master node fails, a replica is automatically promoted to master, minimizing downtime and data loss for cached items.
• Database (Cassandra Cluster): Designed for high availability with a replication factor of 3 across multiple nodes and data centers. If a node fails, its data is available on other replicas, and Cassandra automatically handles data repair and replacement of the failed node.
• Key Generation Service (KGS): Deployed with multiple instances behind a load balancer. The underlying distributed ID generation mechanism (e.g., using Zookeeper for coordination or a highly available counter) ensures that unique IDs can still be generated even if some KGS instances fail.
• Message Queue (Kafka): Deployed as a cluster with replication. If a broker fails, other brokers continue to operate, and data is replicated to ensure no message loss.

Data Center Outages: The entire system will be deployed across at least two geographically distinct data centers or multiple availability zones within a region. Load balancers will be configured for cross-zone/cross-region failover. Cassandra's multi-datacenter replication ensures data durability and availability even if an entire data center becomes unavailable.

Cache Invalidation: As short_code to long_url mappings are largely immutable, explicit cache invalidation is rarely needed. Cache entries can have a very long TTL. If a long_url ever needs to be updated (e.g., for legal reasons), the write service would update the database and then explicitly invalidate/update the corresponding entry in the Redis cache.

Backup and Recovery Strategy:

• Database: Regular, automated snapshots of the Cassandra cluster data will be taken and stored in a highly durable object storage service (e.g., AWS S3, Google Cloud Storage). These backups enable point-in-time recovery in case of data corruption or accidental deletion. Cassandra's incremental backups and commit logs can also be used for more granular recovery.
• Configuration: All infrastructure (Infrastructure as Code) and application configurations will be version-controlled (e.g., Git) and deployed using automated pipelines, allowing for quick restoration of service configurations.
• Monitoring and Alerting: Comprehensive monitoring (e.g., Prometheus, Grafana) will be in place to track system health, performance metrics, and error rates. Automated alerts will notify operations teams of any anomalies or failures, enabling rapid response and recovery.

F. Key Trade-offs

1. Consistency vs. Availability (for short_code to long_url mapping)

   • Trade-off Chosen: We prioritize strong consistency for the core short_code to long_url mapping, while allowing for eventual consistency for auxiliary data like click counts.
   • Explanation: The fundamental purpose of a URL shortener is to reliably redirect a short URL to its correct long URL. An inconsistent mapping (e.g., redirecting to the wrong URL or failing to redirect) would severely degrade user experience and break the service's core contract. Therefore, we ensure that once a short_code is created and returned to the user, it immediately resolves to the correct long_url. This is achieved by writing to Cassandra with strong consistency levels (e.g., QUORUM) and immediately populating the Redis cache. Availability is maintained through extensive replication and distributed architecture, ensuring the service remains operational even with strong consistency requirements for the critical path. Click counts, however, can tolerate slight delays in updates, making eventual consistency acceptable for this non-critical data.

2. Simplicity vs. Scalability/Performance (Key Generation Strategy)

   • Trade-off Chosen: We opted for a dedicated Key Generation Service (KGS) using a distributed counter and Base62 encoding, which is more complex, over a simpler approach of generating random Base62 strings and checking for collisions.
   • Explanation: While generating random strings and checking for collisions in the database is simpler to implement initially, it introduces several scalability and performance challenges. As the key space fills up, the probability of collisions increases, leading to more retries and higher latency on the write path. This read-before-write pattern can become a bottleneck under high write loads. The chosen KGS approach, while more complex to design and maintain (requiring a distributed ID generator), guarantees unique keys without collisions. It allows for pre-generation of key blocks, significantly reducing the latency of key acquisition for the write service. This upfront complexity is justified by the need for predictable, high-performance, and highly scalable key generation over the service's 5-year lifespan, ensuring the write path remains efficient and reliable as the system grows.