Requirements

Functional Requirements:

• Criar uma URL curta para uma determinada URL longa.
• Retornar a URL longa associada a uma determinada URL curta.

Non-Functional Requirements:

• Disponibilidade acima de consistência → Queremos que o serviço priorize disponibilidade em vez de consistência.
• Baixa latência → Queremos que nosso Tiny URL adicione o mínimo de overhead possível na requisição.
• Disponível em múltiplas regiões do mundo → O serviço deve estar disponível em diferentes regiões geográficas.

Capacity estimation

• Teremos cerca de 100 leituras por segundo e até 1 escrita por segundo.
• Se tivermos 1 escrita por segundo, para codificar uma URL provavelmente precisaríamos de 8 bytes de dados. Considerando que há aproximadamente 10 × 10⁵ segundos em um dia, teríamos cerca de 8 × 10⁵ bytes de dados por dia, o que dá aproximadamente 800 MB de dados por dia.
• Com 100 leituras por segundo, não conseguiríamos manter tudo em apenas um host; provavelmente precisaríamos escalar além disso.

API Design

Queremos ter dois tipos de APIs:

1. API de redirecionamento (GET)

Uma API que atende requisições GET, onde a URL seria algo como co.me/url-link-short

Essa API redirecionaria o solicitante para o recurso real e, em caso de sucesso, retornaria 302 (redirecionado). Em caso de falha, poderíamos retornar algo como 404.

2. API para criação/encurtamento de URL

API que permitiria que o usuário encurtasse sua URL através de um portal UI.

Também poderíamos permitir que o usuário especifique a própria URL curta, que internamente seria traduzida para um hash, facilitando localizar o nó onde o link está armazenado.

Também podemos querer garantir que os links codificados não sejam maliciosos ou não apontem para a dark web ou recursos proibidos. Se um usuário tentar codificar algo desse tipo, podemos negar a requisição no fluxo da API de criação.

Database design

The most perfect database choice for this would be a simple (persistent) key-value store. Since key-value stores are usually NoSQL, we don't have to worry about scaling issues too much.

High-Level Design

Vamos precisar de um design em que o cliente primeiro acesse o load balancer, que redirecionará a requisição para o application server apropriado com base no algoritmo Round Robin (RR), que é stateless.

O application server primeiro verificaria se a URL está presente no cache em memória (o que saberíamos com base no ID do servidor de cache, determinado pelo daemon cliente de cache rodando no application server, que usa consistent hashing para decidir qual servidor de cache consultar). O cache utiliza política LRU.

Se houver cache hit, retornamos a resposta imediatamente. Caso contrário, verificamos o banco de dados (key-value store). Um banco NoSQL conseguiria rotear a requisição para a partição correta e retornar o resultado. Se não estiver presente, retornamos 404.

De forma geral, está tudo bem se, logo após o recurso ser adicionado, levar algum tempo até que ele seja totalmente propagado para todas as réplicas (consistência eventual é aceitável). No entanto, queremos manter durabilidade (garantir que não perderemos a requisição de escrita) e baixa latência (fazer o redirecionamento o mais rápido possível, < 20 ms).

O fluxo de escrita é semelhante, mas com alguns detalhes explicados a seguir.

Detailed Component Design

Eu gostaria que o banco de dados replicasse de forma síncrona dentro do datacenter e de forma assíncrona fora do datacenter. Conflitos de versão não são uma grande preocupação, já que nosso software não possui muitos problemas potenciais de duplicidade (observe que uma URL pode ser mapeada para duas URLs encurtadas sem problemas).

A única preocupação aqui é o gerador distribuído de IDs únicos. Para isso, podemos usar algo como um algoritmo de hash que receberia algo como /Facebook/com/post-id/1231 e retornaria aH102. Precisaríamos garantir que duas strings diferentes não gerem o mesmo hash para o mesmo recurso, caso contrário teríamos um problema.

Para evitar isso, toda vez que gerarmos um hash, verificaríamos se esse hash já está presente no banco de dados e mapeado para outro recurso.