Projetar um Encurtador de URL para 10.000 Requisições por Segundo

Projeto do sistema: encurtador de URL escalável

Suposições

1. Picos de tráfego de redirecionamento em 10.000 solicitações por segundo. Uma proporção nominal de 100:1 entre leitura e gravação implica aproximadamente 100 criações por segundo nesse pico.

2. Trinta bilhões de links em cinco anos exigem aproximadamente 190 criações por segundo em média, portanto, o armazenamento e o caminho de gravação serão provisionados para pelo menos 1.000 criações por segundo para conciliar esse número e absorver rajadas.

3. Links são imutáveis por padrão. Se a exclusão ou edição de destino for suportada posteriormente, ela usará versionamento explícito e invalidação de cache.

4. Análises básicas podem ser eventualmente consistentes e podem perder um número muito pequeno de eventos durante falhas catastróficas. A correção do redirecionamento não depende de análises.

5. Respostas de redirecionamento usam HTTP 302 ou 307 em vez de redirecionamentos permanentes 301, preservando o controle operacional e melhorando a visibilidade das análises.

6. O serviço é executado ativo-a-ativo em pelo menos três regiões geográficas e usa um banco de dados de links replicado globalmente.

7. Arquitetura de alto nível

Os componentes são DNS global ou roteamento Anycast, balanceadores de carga regionais, serviços de redirecionamento sem estado, serviços de criação sem estado, caches locais em memória, caches distribuídos regionais, um banco de dados de links particionado, um fluxo de eventos durável e processadores e armazenamento de análises.

Caminho de criação

1. Um cliente envia a URL longa e um alias personalizado opcional para a região saudável mais próxima.
2. A API autentica ou limita a taxa do chamador, valida a sintaxe da URL, limita o comprimento da URL, permite apenas esquemas suportados como HTTP e HTTPS e verifica aliases reservados.
3. Para um link gerado automaticamente, o serviço cria um código criptograficamente aleatório. Para um alias personalizado, ele normaliza o alias de acordo com uma política documentada, sensível ou insensível a maiúsculas e minúsculas.
4. O serviço de criação executa uma inserção condicional no banco de dados autoritativo: insere apenas se o código ou alias ainda não existir.
5. Em uma colisão aleatória, ele gera outro código e tenta novamente. Em uma colisão de alias personalizado, ele retorna HTTP 409 sem alterar silenciosamente o alias solicitado.
6. Após o banco de dados confirmar a gravação, o serviço insere o novo mapeamento no cache regional local e transmite uma mensagem de preenchimento ou invalidação de cache para outras regiões.
7. Ele retorna a URL curta. Uma chave de idempotência de solicitação pode mapear solicitações repetidas do cliente para o mesmo resultado.

A gravação é confirmada apenas após um quórum ou commit de consenso. Isso adiciona latência de gravação entre zonas e, dependendo da configuração do banco de dados, entre regiões, mas cria uma garantia de exclusividade global autoritativa. A criação é muito menos sensível à latência do que o tráfego de redirecionamento.

Caminho de redirecionamento

1. O roteamento global envia a solicitação para a região saudável mais próxima.
2. O serviço de redirecionamento valida e extrai o código.
3. Ele verifica um pequeno cache em memória. Se ausente, ele verifica o cache distribuído regional.
4. Em uma falha de cache, ele executa uma consulta pontual em uma réplica local do banco de dados usando o código como chave primária.
5. Se encontrado e ativo, ele preenche ambos os níveis de cache, emite assincronamente um evento de clique e retorna imediatamente uma resposta 302 ou 307 contendo o destino.
6. Se ausente, retorna 404. Resultados negativos são cacheados apenas brevemente.

O caminho de redirecionamento não tem operação de análise síncrona e nenhum salto de rede entre regiões em condições normais. Serviços sem estado escalam horizontalmente atrás de balanceadores de carga regionais.

2. Geração e exclusividade de código curto

Um espaço base62 de sete caracteres contém 62^7, aproximadamente 3,52 trilhões, de valores e pode tecnicamente conter 30 bilhões de links. No entanto, com 30 bilhões de links armazenados, cerca de 0,85% desse namespace é ocupado. Um scanner aleatório em massa descobriria, portanto, aproximadamente um link válido a cada 117 tentativas, o que não atende ao requisito de que os códigos sejam difíceis de adivinhar em massa.

O código padrão usará, portanto, 11 caracteres base62 seguros para URL gerados a partir de uma fonte aleatória criptograficamente segura. Isso fornece aproximadamente 65,5 bits e 5,2 × 10^19 possibilidades. Com 30 bilhões de links ativos, uma tentativa aleatória tem sucesso com probabilidade de cerca de 5,8 × 10^-10. Limitação de taxa e detecção de abuso restringem ainda mais a enumeração. A contrapartida é um link quatro caracteres mais longo. Aliases de sete caracteres ainda podem ser permitidos quando explicitamente escolhidos pelos usuários, mas eles não recebem a mesma garantia de não enumerabilidade.

A geração aleatória evita expor a ordem de criação e distribui as chaves uniformemente. Uma inserção condicional de chave primária é a autoridade final de exclusividade. Colisões de aniversário em todo o histórico completo são esperadas em um sistema aleatório, mas apenas colisões de candidatos simultâneas importam operacionalmente: cada inserção tentada é verificada e retentada. Na ocupação planejada do espaço de 11 caracteres, as retentativas são efetivamente inexistentes.

Uma alternativa seria criptografar ou aplicar uma permutação com chave a um número de sequência. Isso garante entradas geradas exclusivas, mas requer gerenciamento do ciclo de vida da chave e alocação de sequência. A geração aleatória mais inserção condicional é mais simples, remove a alocação centralizada de ID e é suficientemente eficiente nesse tamanho de namespace.

Aliases personalizados compartilham o mesmo namespace de chave primária que os códigos gerados. A normalização de alias ocorre antes da inserção, e uma inserção condicional globalmente consistente decide o vencedor de solicitações concorrentes. Caminhos reservados como saúde, API, admin e estático são rejeitados. Se os aliases não diferenciam maiúsculas de minúsculas, a forma normalizada em minúsculas é a chave, enquanto a forma de exibição solicitada pode ser armazenada separadamente.

3. Modelo de dados e banco de dados

Os campos do registro de link autoritativo são:

código: chave primária
long_url: URL de destino
created_at: timestamp
owner_id: identificador de conta opcional
status: ativo, desativado ou excluído
ttl_or_expiry: opcional
version: valor monotonicamente crescente para invalidação de cache
custom_alias: booleano

As contagens de cliques não são atualizadas neste registro a cada redirecionamento, pois isso transformaria links populares em hotspots de gravação.

O armazenamento de links é um banco de dados de chave-valor distribuído e particionado otimizado para acesso por chave primária, como DynamoDB, Bigtable, Cassandra com consistência cuidadosamente gerenciada ou um sistema interno equivalente. Para gravações condicionais globalmente exclusivas, a implementação selecionada deve fornecer criação condicional linearizável para uma chave, nativamente ou por meio de líderes de consenso por shard. Junções relacionais e varreduras de intervalo não são necessárias no caminho de redirecionamento.

A chave de partição primária é um hash do código completo. A distribuição de hash evita hotspots cronológicos e espalha uniformemente códigos gerados e aliases personalizados. O keyspace lógico é dividido em milhares de shards virtuais, que são realocados à medida que os nós são adicionados. Cada shard tem pelo menos três réplicas entre zonas de disponibilidade, com réplicas adicionais entre regiões.

Estimativa de capacidade

Suponha uma URL média de 400 bytes e aproximadamente 200 bytes para chaves, metadados, codificação, índices e sobrecarga do mecanismo de armazenamento. Com cerca de 600 bytes por registro, 30 bilhões de registros exigem cerca de 18 TB de dados lógicos. Permitindo URLs mais longas, sobrecarga de compactação, marcadores de exclusão e margem operacional, orce 30 TB lógicos. Três réplicas duráveis exigem aproximadamente 90 TB, e backups, bem como cópias entre regiões, podem elevar a alocação da frota para cerca de 150–250 TB. Isso está bem dentro da faixa pretendida de bancos de dados de chave-valor particionados horizontalmente, mas é inadequado para uma única instância de banco de dados convencional.

A 10.000 redirecionamentos por segundo, mesmo uma falha completa de cache gera apenas 10.000 leituras pontuais aleatórias por segundo. O banco de dados é provisionado para pelo menos 20.000–30.000 leituras por segundo por região de serviço durante failover e pelo menos 1.000 criações condicionais por segundo. A capacidade é governada mais pelo tamanho do conjunto de dados, replicação e reserva de failover do que pelo throughput normal de solicitação.

Análises usam armazenamento separado. Um processador de fluxo grava contagens por código e por bucket de tempo em um banco de dados de chave-valor ou colunar de análises com um modelo como código mais dia ou hora como chave e contagem como valor. Um total compacto pode ser mantido assincronamente. Manter análises separadas evita que contadores de links populares contentionem com consultas de redirecionamento.

4. Estratégia de cache

Cada processo de redirecionamento tem um cache em memória LRU limitado ou TinyLFU para os mapeamentos mais acessados. Um cluster regional compatível com Redis ou Memcached forma o segundo nível. Valores cacheados incluem destino, status, expiração e versão do registro.

Um alvo representativo é uma taxa de acerto de cache regional de 95–99%. A popularidade de URL semelhante à Lei de Zipf geralmente torna isso viável, mesmo que o corpus total seja muito grande. O cache armazena objetos quentes, não todos os 30 bilhões de links. Por exemplo, 100 milhões de entradas a aproximadamente 600 bytes cada consomem cerca de 60 GB antes da sobrecarga do cache e talvez 100–150 GB na prática, distribuídos por um cluster de cache regional.

Mapeamentos são imutáveis por padrão, portanto, entradas positivas podem ter um TTL longo, como 6–24 horas com jitter. Se a edição, desativação ou exclusão for suportada, a gravação autoritativa é confirmada primeiro e, em seguida, publica uma invalidação contendo o código e a nova versão para todas as regiões. TTLs mais curtos limitam o tempo de serviço de dados desatualizados se uma invalidação for perdida. Operações de desativação sensíveis à segurança também podem colocar uma pequena lista global de bloqueio em cada processo de redirecionamento.

Resultados negativos são cacheados por aproximadamente 5–30 segundos para resistir a varreduras repetidas. O caminho de criação invalida entradas de cache negativas após reivindicar com sucesso um código. O TTL negativo curto limita uma corrida na qual outra região cachead brevemente uma falha antes que a replicação ou invalidação chegue.

Em uma falha de cache, o serviço de redirecionamento lê a réplica do banco de dados regional e preenche ambos os níveis de cache. A coalescência de solicitações garante que falhas concorrentes para um código recém-popular emitam uma solicitação de banco de dados em vez de milhares. O jitter de TTL evita expiração sincronizada. O banco de dados é dimensionado para suportar toda a carga de 10.000 solicitações por segundo se o cache distribuído falhar, aceitando latência um pouco maior enquanto permanece funcional.

A contrapartida de TTLs de cache longos é a potencial desatualização após edições. Imutabilidade, invalidações versionadas e TTLs limitados tornam essa contrapartida explícita. A correção do redirecionamento para links recém-criados pode ser melhorada preenchendo síncronamente a região de criação e roteando uma leitura imediata para essa região quando necessário.

5. Escalabilidade e latência

Serviços de redirecionamento são sem estado e escalam horizontalmente com base em solicitações por segundo, CPU e latência p99. Se uma instância processa com segurança 1.000 solicitações por segundo, cada região pode executar pelo menos 15–20 instâncias para uma carga de failover regional de 10.000 solicitações por segundo, mais margem para implantação e falha de zona. O dimensionamento real é estabelecido por meio de testes de carga.

Um orçamento normal de latência de acerto de cache é de aproximadamente 2–5 ms para balanceamento de carga e trabalho de aplicação, 1–3 ms para uma consulta em memória ou 2–8 ms para uma consulta de cache distribuído regional, e alguns milissegundos para construir a resposta. Um orçamento de falha de cache aloca aproximadamente 10–25 ms para uma consulta pontual local em banco de dados replicado. Esses orçamentos deixam espaço para manter o p99 do lado do servidor de origem abaixo de 50 ms.

Timeouts estritos por salto evitam que um cache ou réplica danificado consuma todo o orçamento de latência. O acesso ao cache pode ser limitado a aproximadamente 8 ms e o acesso ao banco de dados a aproximadamente 25–30 ms, com retentativas apenas quando houver orçamento suficiente. Leituras apressadas para uma segunda réplica local podem ser usadas para o percentil mais lento, mas elas são atrasadas e limitadas em taxa para evitar dobrar a carga normal.

Chaves são particionadas por hash entre shards virtuais. Códigos gerados aleatoriamente equilibram o tráfego, enquanto um link individual excepcionalmente quente é absorvido por caches em memória e regionais. Se uma chave quente atinge o banco de dados, a coalescência de solicitações e leituras replicadas evitam que um nó de armazenamento se torne o gargalo.

Autoscaling mantém capacidade suficiente para uma perda completa de zona de disponibilidade e pelo menos uma região recebendo tráfego redirecionado de um par falho. Regiões operam abaixo de aproximadamente 50–60% da capacidade de pico. A contrapartida é um custo ocioso mais alto em troca do objetivo de disponibilidade de 99,99%.

6. Confiabilidade e tratamento de falhas

Meta de disponibilidade

Uma meta mensal de 99,99% permite cerca de 4,4 minutos de indisponibilidade em um mês de 30 dias. Nenhum cache de nó único, instância de aplicação, zona de disponibilidade ou região pode ser necessário para redirecionamentos.

Falha de instância de aplicação ou zona

Verificações de integridade removem instâncias com falha e balanceadores de carga distribuem solicitações entre pelo menos três zonas. Serviços usam implantações contínuas ou canário, esvaziamento de conexão e rollback automatizado. A capacidade regional sobrevive à perda de uma zona.

Falha de nó ou cluster de cache

Nós de cache são particionados e replicados dentro de uma região. Se um nó individual falhar, sua réplica assume. Se todo o cache estiver indisponível, os serviços de redirecionamento usam disjuntores, pulam chamadas de cache e consultam o banco de dados diretamente. A capacidade do banco de dados e os pools de conexão de aplicação são explicitamente provisionados para este modo. O controle de admissão protege o banco de dados contra tráfego de scanner ilimitado.

Falha de nó do banco de dados

Cada shard é replicado entre zonas usando quórum ou consenso. Um líder falho é substituído automaticamente; leituras usam outra réplica local saudável. Criações condicionais permanecem indisponíveis para um shard durante a breve eleição em vez de arriscar propriedade duplicada. Redirecionamentos podem continuar de réplicas e caches. Isso favorece a correção para criação enquanto preserva a disponibilidade de leitura.

Falha de região

Roteamento global baseado em integridade remove a região com falha e envia tráfego para a região saudável mais próxima. Cada região de serviço tem uma cópia replicada dos dados do link e infraestrutura independente de redirecionamento, cache e ingestão de eventos. A taxa de acerto de cache será inicialmente menor após o failover, portanto, regiões de standby mantêm caches aquecidos para links globalmente quentes e capacidade de banco de dados/leitura suficiente para o surto de cache frio.

Para códigos gerados, a replicação global pode ser assíncrona após uma inserção autoritativa com suporte de consenso se a arquitetura do banco de dados rotear cada chave para um shard de origem. Para aliases personalizados, a inserção condicional autoritativa deve permanecer globalmente serializada. Se um link recém-criado não atingiu uma região sobrevivente antes de uma perda catastrófica, o serviço pode retornar brevemente um erro retentável em vez de um mapeamento incorreto. Replicação síncrona mais forte entre regiões reduz essa janela de ponto de recuperação, mas aumenta a latência de criação. A configuração preferida confirma a criação de links entre réplicas em pelo menos duas regiões, pois as gravações são de volume relativamente baixo.

Backups e corrupção

O banco de dados usa checksums, recuperação de ponto no tempo, snapshots imutáveis e procedimentos de restauração testados regularmente. Exclusões usam marcadores de exclusão e um período de retenção em vez de remoção física imediata. Backups protegem contra corrupção lógica, mas não fazem parte do failover normal de redirecionamento.

Comportamento de sobrecarga

Limites de taxa se aplicam por origem, conta e padrão de escaneamento de código suspeito. Tráfego de criação e análise tem prioridade menor que redirecionamentos. Descarte de carga rejeita solicitações de criação abusivas ou excessivas antes que a capacidade de redirecionamento seja afetada. Disjuntores, filas limitadas e prazos evitam falhas em cascata.

7. Análise de cliques

Após selecionar o destino do redirecionamento, o serviço cria um evento compacto contendo um ID de evento, código, timestamp, região e, opcionalmente, campos de referenciador ou user-agent grosseiros. Ele coloca o evento em um buffer assíncrono local limitado e retorna o redirecionamento sem esperar pela confirmação da análise.

Um coletor regional agrupa eventos em um fluxo replicado durável como Kafka, Pulsar ou Kinesis. Processadores de fluxo agregam eventos por código e bucket de tempo, e então gravam incrementos em lotes no armazenamento de análise. A compactação periódica produz contagens totais de cliques. Dashboards e APIs leem o armazenamento de análise, nunca a tabela de redirecionamento autoritativa.

IDs de evento permitem deduplicação downstream quando coletores tentam novamente. Particionar o fluxo diretamente por código concentraria um link viral em uma partição, portanto, a chave de ingestão pode ser código mais um stripe aleatório. Processadores primeiro agregam contadores com stripe e depois os mesclam. Isso permite que a análise de links quentes escale horizontalmente.

Um buffer assíncrono puramente em memória pode perder eventos se um processo de redirecionamento travar. Se uma durabilidade mais forte for necessária, cada host ou sidecar pode anexar lotes a um log local de escrita antecipada antes de encaminhá-los, mas as respostas de redirecionamento ainda não devem esperar pelo fluxo central. A contrapartida aceita para análises básicas é a consistência eventual e uma subcontagem pequena e medida durante falhas graves em troca de preservar a latência e a disponibilidade de redirecionamento.

Resultado

O caminho de redirecionamento normal é uma consulta de cache local seguida, apenas em caso de falha, por uma consulta de banco de dados de chave-valor particionado local. Códigos aleatórios de 11 caracteres evitam exposição sequencial e tornam adivinhações em massa bem-sucedidas impraticáveis. Inserções condicionais fornecem exclusividade, particionamento de hash suporta o corpus de 30 bilhões de registros, serviço regional ativo-a-ativo remove pontos únicos de falha regionais e análise assíncrona com stripe mantém as gravações de contador totalmente fora do caminho crítico de latência.

Design de Sistema: Encurtador de URL (10K RPS)

Premissas:

• Estamos a projetar inicialmente para uma única região, sendo multi-região uma melhoria futura.
• O foco principal está no caminho de redirecionamento devido à proporção de leitura:escrita de 100:1.
• Aliases personalizados são uma funcionalidade secundária e podem tolerar latência ligeiramente maior ou indisponibilidade ocasional em comparação com redirecionamentos padrão.
• As análises de cliques não são estritamente em tempo real e podem ter um pequeno atraso.

1. Arquitetura de Alto Nível e Fluxo de Requisições

Caminho de Escrita (Criar Link Curto):

1. API Gateway: Recebe a requisição POST com a URL longa e o alias personalizado opcional.
2. Load Balancer: Distribui requisições de escrita para as instâncias da API do Serviço de Encurtamento de URL (US).
3. API US (Serviço de Escrita):
   • Valida a URL de entrada.
   • Gera um código curto (ver Secção 2).
   • Se um alias personalizado for fornecido, tenta reservá-lo primeiro (ver Secção 2).
   • Persiste o mapeamento (short_code -> original_url, custom_alias -> short_code) no armazenamento de dados.
   • Retorna a URL curta gerada ao cliente.

Caminho de Leitura (Redirecionamento):

1. API Gateway: Recebe a requisição GET para uma URL curta.
2. Load Balancer: Distribui requisições de leitura para as instâncias da API US.
3. API US (Serviço de Leitura):
   • Extrai o código curto do caminho da URL.
   • Consulta ao Cache: Verifica num cache distribuído (por exemplo, Redis Cluster) pelo código curto.
     • Cache Hit: Se encontrado, recupera a URL original e retorna uma resposta de redirecionamento HTTP 301/302.
     • Cache Miss: Se não encontrado, consulta o armazenamento de dados primário.
   • Consulta ao Armazenamento de Dados: Consulta o armazenamento de dados primário pela URL original associada ao código curto.
   • Atualização do Cache: Se encontrado no armazenamento de dados, a URL original é adicionada ao cache para requisições futuras.
   • Redirecionamento: Retorna uma resposta de redirecionamento HTTP 301/302 com a URL original.
   • Tratamento de Erros: Se não encontrado, retorna 404 Not Found.
4. Análises de Cliques (Assíncronas): Um serviço ou mecanismo separado (ver Secção 7) regista eventos de clique de forma assíncrona.

Trade-offs:

• Separação de Responsabilidades: Separar serviços de leitura e escrita permite escalonamento e otimização independentes. O caminho de leitura é otimizado para baixa latência e alto throughput.
• API Gateway/Load Balancer: Introduz um ponto único de falha se não for configurado para alta disponibilidade, mas é essencial para escalar e gerir tráfego.
• Penalidade de Cache Miss: Um cache miss incorre em latência maior devido à consulta ao armazenamento de dados, mas isto é mitigado por um cache grande e uma alta taxa de acertos.

2. Estratégia de Geração de Código Curto

Estratégia: Codificação Base62 com um Contador/Gerador de ID.

1. Geração de ID: Usaremos um serviço distribuído de geração de IDs (por exemplo, semelhante ao Snowflake ou um serviço dedicado usando ZooKeeper/etcd) para gerar inteiros únicos, monotonamente crescentes, de 64 bits. Isto garante unicidade e evita colisões na origem.
   • Trade-off: Requer um serviço de geração de IDs altamente disponível e performante. Se falhar, novos links curtos não podem ser criados.
2. Codificação Base62: Cada ID inteiro de 64 bits gerado é convertido numa string Base62 (0-9, a-z, A-Z). Um ID de 64 bits pode representar até 2^64 valores únicos. Os primeiros 6 caracteres podem representar ~68 mil milhões de valores únicos (62^6), e 7 caracteres podem representar ~4,1 biliões (62^7). Para 30 mil milhões de links ao longo de 5 anos, 7 caracteres são suficientes e fornecem amplo espaço para crescimento.
   • Trade-off: A codificação Base62 é ligeiramente mais complexa do que hashing simples, mas fornece URLs mais curtas e evita previsibilidade em comparação com IDs sequenciais.
3. Aliases Personalizados:
   • Quando um utilizador solicita um alias personalizado (por exemplo, /my-link), o serviço de escrita verifica primeiro se o alias já está ocupado numa tabela/índice dedicado no armazenamento de dados (por exemplo, tabela custom_aliases que mapeia alias -> short_code).
   • Se o alias estiver disponível, é reservado e associado ao código curto recém-gerado.
   • Se o alias estiver ocupado, a API retorna um erro ao utilizador.
   • Tratamento de Colisões: A geração de ID e a codificação Base62 garantem unicidade para códigos curtos gerados. Aliases personalizados são tratados através de uma operação separada, atómica, de verificar-e-definir no armazenamento de dados para prevenir colisões.
   • Trade-off: Consultas de alias personalizado adicionam uma pequena sobrecarga ao caminho de escrita. A disponibilidade de aliases personalizados não é garantida.

Garantia de Unicidade: Alcançada pelo gerador distribuído de IDs. Cada ID é único, e a sua representação Base62 também será única.

Não previsível: IDs codificados em Base62 não são sequenciais e não revelam a ordem de criação nem o número total de links. São efetivamente strings com aparência aleatória.

3. Modelo de Dados e Armazenamento(s) de Dados

Escolha de Armazenamento de Dados: Um armazenamento distribuído NoSQL chave-valor (por exemplo, Cassandra, DynamoDB, ou uma BD relacional particionada como Vitess) para o mapeamento primário de links, e um sistema separado para análises.

Armazenamento de Dados Primário (Mapeamento de Links):

• Esquema:

  • Tabela/coleção links:
    • short_code (Chave Primária, String, por exemplo, "aBcDeFg")
    • original_url (String)
    • created_at (Timestamp)
    • user_id (Opcional, para propriedade/gestão)
  • Tabela/coleção custom_aliases:
    • alias (Chave Primária, String, por exemplo, "my-link")
    • short_code (String, Chave Estrangeira para links.short_code)

• Justificação do Tipo de Armazenamento de Dados: Um armazenamento distribuído NoSQL chave-valor é escolhido pela sua alta disponibilidade, escalabilidade horizontal e excelente desempenho de leitura para consultas por chave, o que é crítico para o caminho de redirecionamento. Pode lidar com a escala massiva de 30 mil milhões de entradas.

• Estimativa de Capacidade/Armazenamento:

  • Tabela Links: 30 mil milhões de entradas.
    • short_code: ~7 bytes (Base62, 7 caracteres)
    • original_url: Média de 100 bytes (pode variar significativamente, assumindo a média)
    • created_at, user_id: ~10 bytes
    • Total por entrada: ~117 bytes. Vamos arredondar para 150 bytes para overhead e replicação.
    • Armazenamento total: 30 mil milhões * 150 bytes = 4,5 * 10^12 bytes = 4,5 TB.
  • Tabela Custom Aliases: Assumir que 10% dos links têm aliases personalizados (3 mil milhões).
    • alias: Média de 15 bytes (mais curto do que URLs longas).
    • short_code: ~7 bytes.
    • Total por entrada: ~22 bytes. Arredondar para 50 bytes para overhead.
    • Armazenamento total: 3 mil milhões * 50 bytes = 150 * 10^9 bytes = 0,15 TB.
  • Armazenamento Primário Total: ~4,65 TB. Isto é gerível para sistemas NoSQL distribuídos.

• Particionamento/Sharding: O armazenamento de dados será particionado por short_code (para a tabela links) e alias (para a tabela custom_aliases). Isto permite uma distribuição uniforme de dados e carga entre nós.

Trade-offs:

• NoSQL vs. SQL: Um armazenamento NoSQL é preferido pela flexibilidade de esquema e escalonamento horizontal. Uma BD relacional poderia funcionar, mas exigiria uma gestão de sharding mais complexa (por exemplo, Vitess).
• Redundância de Dados: Armazenamentos NoSQL normalmente replicam dados para disponibilidade, aumentando os requisitos de armazenamento, mas melhorando a tolerância a falhas.
• Tabela de Aliases Personalizados: Uma tabela separada é usada para verificar eficientemente a disponibilidade de aliases sem varrer a tabela principal links, o que seria ineficiente.

4. Estratégia de Cache

Estratégia: Cache Distribuído em Memória (por exemplo, Redis Cluster, Memcached).

• O que Armazenar em Cache: Mapeamentos short_code para original_url frequentemente acedidos.
• Chave de Cache: short_code (por exemplo, "aBcDeFg")
• Valor de Cache: original_url (por exemplo, "https://www.verylongurl.com/...")
• Tamanho do Cache: Dimensionado para conter uma parte significativa dos links quentes. Dado 10K RPS e proporção 100:1, esperamos milhões de links ativos por segundo. Um cache que contenha 1-5 milhões de entradas deve fornecer uma alta taxa de acertos para links quentes.
• Invalidação de Cache:
  • Nenhuma invalidação explícita necessária para links padrão: Uma vez criados, os links são imutáveis. O mapeamento não muda.
  • Para aliases personalizados: Se um alias personalizado for alterado (normalmente não permitido, mas se fosse), o mapeamento antigo short_code -> original_url permaneceria no cache. No entanto, a prática padrão é que aliases personalizados sejam únicos e permanentes uma vez definidos. Se um link for apagado (não é uma funcionalidade comum para encurtadores de URL), então a entrada seria removida do cache.
• Tratamento de Cache Miss:
  1. Num cache miss, a API US (Serviço de Leitura) consulta o armazenamento de dados primário pela original_url usando o short_code.
  2. Se encontrada no armazenamento de dados, a original_url é escrita de volta no cache com um Time-To-Live (TTL) (por exemplo, 24-48 horas) antes de ser retornada ao cliente.
  3. Se não encontrada no armazenamento de dados, um 404 é retornado, e nenhuma entrada é adicionada ao cache.

Trade-offs:

• Desatualização do Cache: Cache baseado em TTL significa que há uma pequena janela em que um link pode ser atualizado (se atualizações fossem permitidas) e o cache ficaria desatualizado. No entanto, para links imutáveis, isto não é um problema.
• Disponibilidade do Cache: O cache é um componente crítico. Se falhar, a latência aumenta significativamente devido a consultas ao armazenamento de dados, mas o serviço permanece disponível (embora mais lento).
• Custo: Caches grandes em memória podem ser caros.

5. Estratégia de Escalonamento

Escalonamento do Caminho de Leitura (Redirecionamentos):

• Servidores de API Stateless: As instâncias da API US que lidam com redirecionamentos são stateless. Isto permite-nos escalá-las horizontalmente de forma praticamente ilimitada atrás de um load balancer.
• Cache Distribuído: Um cache distribuído particionado e replicado (como Redis Cluster) pode lidar com milhões de QPS e fornece baixa latência. É concebido para escalonamento horizontal.
• Escalonamento do Armazenamento de Dados: O armazenamento de dados distribuído NoSQL escolhido (Cassandra, DynamoDB) é concebido para escalonamento horizontal. Podemos adicionar mais nós para aumentar throughput e capacidade.
• Load Balancers: Load balancers em várias camadas (API Gateway, serviço-para-serviço interno) distribuem o tráfego uniformemente.

Particionamento/Sharding de Dados:

• Sharding do Armazenamento de Dados: Como mencionado na Secção 3, o armazenamento de dados primário é particionado por short_code (ou por um hash dele) para a tabela links e por alias para a tabela custom_aliases. Isto distribui os dados e a carga de leitura/escrita por vários nós.
• Sharding do Cache: O cache distribuído é inerentemente particionado, distribuindo chaves pelos seus nós.
• Serviço de Geração de ID: Este serviço também deve ser escalável, potencialmente usando várias instâncias coordenadas por ZooKeeper/etcd ou por um protocolo de consenso distribuído.

Trade-offs:

• Complexidade: Sharding e sistemas distribuídos adicionam complexidade operacional significativa.
• Hotspots: Embora o sharding ajude, links extremamente populares ainda podem criar hotspots em shards específicos do cache ou partições do armazenamento de dados. Estratégias como hashing consistente ou balanceamento de carga mais avançado podem mitigar isto.

6. Confiabilidade e Tratamento de Falhas

Meta de Disponibilidade (99,99%): Requer redundância em todas as camadas.

• Falha de Nó do Armazenamento de Dados:
  • Estratégia: Os dados são replicados por vários nós (por exemplo, 3-5 réplicas) e potencialmente por zonas de disponibilidade dentro de uma região.
  • Tratamento: O cluster de armazenamento de dados lida automaticamente com falhas de nós promovendo uma réplica e continuando a servir requisições. Leituras e escritas podem experimentar um breve pico de latência durante o failover, mas o serviço permanece disponível.
  • Trade-off: Aumento dos custos de armazenamento devido à replicação.
• Falha de Nó de Cache:
  • Estratégia: Caches distribuídos como Redis Cluster são concebidos com replicação e sharding. Se um nó falhar, as suas réplicas podem assumir, ou os dados podem ser rebalanceados.
  • Tratamento: Cache misses aumentarão temporariamente à medida que o cache se reconstrói ou faz failover. O sistema recorrerá ao armazenamento de dados, levando a latência maior, mas disponibilidade contínua.
  • Trade-off: Degradação temporária de desempenho em caso de falha do cache.
• Falha de Servidor de API:
  • Estratégia: Executar várias instâncias dos servidores stateless da API US atrás de load balancers.
  • Tratamento: Load balancers detetam instâncias não saudáveis e deixam de enviar tráfego para elas. O tráfego é automaticamente encaminhado para instâncias saudáveis.
  • Trade-off: Requer balanceamento de carga e health checking robustos.
• Falha de Região:
  • Estratégia: Implementar o serviço em múltiplas Availability Zones (AZs) dentro de uma região. Para maior disponibilidade, pode ser implementada uma configuração multi-região active-active ou active-passive.
  • Tratamento: Se uma AZ falhar, o tráfego é encaminhado para AZs saudáveis. Se uma região inteira falhar, o tráfego é encaminhado para uma região secundária (requer balanceamento de carga global e replicação de dados).
  • Trade-off: Aumento significativo de complexidade e custo para implementações multi-região.

Cumprir a Meta de Disponibilidade: Redundância, failover automatizado e degradação graciosa (recorrer ao armazenamento de dados em caso de cache miss) são fundamentais. Monitorização e alertas são cruciais para detetar e responder rapidamente a falhas.

7. Recolha de Análises de Cliques

Estratégia: Processamento assíncrono para evitar impactar o caminho crítico de redirecionamento.

1. Geração de Evento: Quando ocorre um redirecionamento (após a URL original ser recuperada e antes de a resposta de redirecionamento ser enviada), a API US (Serviço de Leitura) publica um evento leve