back-of-the-envelope-estimation
Back of the Envelope Estimation
- Back of the Envelope Estimation
Em uma entrevista de projeto de sistema, às vezes você é solicitado a estimar a capacidade do sistema ou os requisitos de desempenho usando uma estimativa aproximada. De acordo com Jeff Dean, pesquisador sênior do Google, “cálculos básicos são estimativas que você cria usando uma combinação de experimentos mentais e números de desempenho comuns para ter uma boa noção de quais projetos atenderão aos seus requisitos” [1].
Você precisa ter um bom senso dos fundamentos da escalabilidade para realizar estimativas completas com eficácia. Os seguintes conceitos devem ser bem compreendidos: potência de dois [2], números de latência que todo programador deve saber e números de disponibilidade.
Poder de dois
Embora o volume de dados possa se tornar enorme quando se lida com sistemas distribuídos, todos os cálculos se resumem ao básico. Para obter cálculos corretos, é fundamental conhecer a unidade de volume de dados usando a potência de 2. Um byte é uma sequência de 8 bits. Um caractere ASCII usa um byte de memória (8 bits). Abaixo está uma tabela explicando a unidade de volume de dados (Tabela 1).
| Poder | Valor aproximado | Nome completo | Nome curto |
|---|---|---|---|
| 10 | 1 mil | 1 quilobyte | 1KB |
| 20 | 1 milhão | 1 megabyte | 1MB |
| 30 | 1 bilião | 1 gigabyte | 1GB |
| 40 | 1 trilhão | 1 terabyte | 1 TB |
| 50 | 1 quatrilhão | 1 petabyte | 1PB |
Números de latência que todo programador deve saber
Dr. Dean, do Google, revela a duração das operações típicas de computador em 2010 [1]. Alguns números estão desatualizados à medida que os computadores se tornam mais rápidos e poderosos. No entanto, esses números ainda devem nos dar uma ideia da rapidez e lentidão das diferentes operações do computador.
| Nome da Operação | Tempo |
|---|---|
| Referência de cache L1 | 0,5ns |
| Previsão errada da filial | 5 ns |
| Referência de cache L2 | 7 ns |
| Bloqueio/desbloqueio mutex | 100 ns |
| Referência de memória principal | 100 ns |
| Compactar 1K bytes com Zippy | 10.000 ns = 10 µs |
| Envie 2K bytes em rede de 1 Gbps | 20.000 ns = 20 µs |
| Leia 1 MB sequencialmente da memória | 250.000 ns = 250 µs |
| Ida e volta dentro do mesmo datacenter | 500.000 ns = 500 µs |
| Busca de disco | 10.000.000 ns = 10 ms |
| Leia 1 MB sequencialmente da rede | 10.000.000 ns = 10 ms |
| Leia 1 MB sequencialmente do disco | 30.000.000 ns = 30 ms |
| Enviar pacote CA (Califórnia) ->Holanda->CA | 150.000.000 ns = 150 ms |
Notas
ns = nanossegundo, µs = microssegundo, ms = milissegundo
1 ns = 10 ^ -9 segundos
1 µs = 10 ^ -6 segundos = 1.000 ns
1 ms = 10 ^ -3 segundos = 1.000 µs = 1.000.000 ns
Um engenheiro de software do Google criou uma ferramenta para visualizar os números do Dr. Dean. A ferramenta também leva em consideração o fator tempo. As Figuras 2-1 mostram os números de latência visualizados em 2020 (fonte das figuras: material de referência [3]).
figura 1
Ao analisar os números da Figura 1, chegamos às seguintes conclusões:
- A memória é rápida, mas o disco é lento.
- Evite buscas de disco, se possível.
- Algoritmos de compressão simples são rápidos.
- Compacte os dados antes de enviá-los pela Internet, se possível.
- Os data centers geralmente estão em regiões diferentes e leva tempo para enviar dados entre eles.
Números de disponibilidade
Alta disponibilidade é a capacidade de um sistema permanecer continuamente operacional por um período de tempo desejavelmente longo. A alta disponibilidade é medida como uma porcentagem, sendo que 100% significa um serviço que tem 0 tempo de inatividade. A maioria dos serviços fica entre 99% e 100%.
Um acordo de nível de serviço (SLA) é um termo comumente usado para provedores de serviços. Este é um acordo entre você (o provedor de serviços) e seu cliente, e este acordo define formalmente o nível de tempo de atividade que seu serviço fornecerá. Os provedores de nuvem Amazon [4], Google [5] e Microsoft [6] definem seus SLAs em 99,9% ou mais. O tempo de atividade é tradicionalmente medido em noves. Quanto mais noves, melhor. Conforme mostrado na Tabela 3, o número de noves está correlacionado ao tempo de inatividade esperado do sistema.
| Disponibilidade % | Tempo de inatividade por dia | Tempo de inatividade por semana | Tempo de inatividade por mês | Tempo de inatividade por ano |
|---|---|---|---|---|
| 99% | 14h40 minutos | 1,68 horas | 7h31 | 3,65 dias |
| 99,99% | 8,64 segundos | 1,01 minutos | 4,38 minutos | 52,60 minutos |
| 99,999% | 864,00 | 6,05 segundos | 26,30 segundos | 5,26 minutos |
| 99,9999% | 86,40 milissegundos | 604,80 | 2,63 segundos | 31,56 segundos |
Exemplo: estimar QPS do Twitter e requisitos de armazenamento
Observe que os números a seguir são apenas para este exercício, pois não são números reais do Twitter.
Premissas:
- 300 milhões de usuários ativos mensais.
- 50% dos usuários usam o Twitter diariamente.
- Os usuários postam em média 2 tweets por dia.
- 10% dos tweets contêm mídia.
- Os dados são armazenados por 5 anos.
Estimativas:
Estimativa de consulta por segundo (QPS):
- Usuários ativos diários (DAU) = 300 milhões * 50% = 150 milhões
- QPS de tweets = 150 milhões * 2 tweets / 24 horas / 3.600 segundos = ~ 3.500
- Espiar QPS = 2 * QPS = ~7000
Estimaremos apenas o armazenamento de mídia aqui.
- Tamanho médio do tweet:
- tweet_id 64 bytes
- texto 140 bytes
- mídia 1 MB
- Armazenamento de mídia: 150 milhões * 2 * 10% * 1 MB = 30 TB por dia
- Armazenamento de mídia por 5 anos: 30 TB * 365 * 5 = ~55 PB
Pontas
A estimativa completa tem tudo a ver com o processo. Resolver o problema é mais importante do que obter resultados. Os entrevistadores podem testar suas habilidades de resolução de problemas. Aqui estão algumas dicas a seguir:
- Arredondamento e aproximação. É difícil realizar operações matemáticas complicadas durante a entrevista. Por exemplo, qual é o resultado de “99987/9.1”? Não há necessidade de gastar tempo valioso para resolver problemas matemáticos complicados. A precisão não é esperada. Use números redondos e aproximações a seu favor. A questão da divisão pode ser simplificada da seguinte forma: “100.000/10”.
- Anote suas suposições. É uma boa ideia anotar suas suposições para serem referenciadas posteriormente.
- Identifique suas unidades. Quando você escreve “5”, significa 5 KB ou 5 MB? Você pode se confundir com isso. Anote as unidades porque “5 MB” ajuda a eliminar a ambigüidade.
- Estimativas gerais comumente feitas: QPS, pico de QPS, armazenamento, cache, número de servidores, etc. Você pode praticar esses cálculos ao se preparar para uma entrevista. A prática leva à perfeição.
Parabéns por chegar até aqui! Agora dê um tapinha nas costas. Bom trabalho!
Materiais de referência
[1] J. Dean.Dica do Google Pro: use cálculos posteriores para escolher o melhor design:
[2] Cartilha de design de sistema:
https://github.com/donnemartin/system-design-primer
[3] Números de latência que todo programador deve saber:
https://colin-scott.github.io/personal_website/research/interactive_latency.html
[4] Acordo de nível de serviço da Amazon Compute:
https://aws.amazon.com/compute/sla/
[5] Contrato de nível de serviço (SLA) do Compute Engine:
https://cloud.google.com/compute/sla
[6] Resumo do SLA para serviços do Azure:
https://azure.microsoft.com/en-us/support/legal/sla/summary/
Clube do livro
Potência
Saber ler uma potência é uma tarefa importante. A leitura é sempre feita começando pelo número que está na base elevado ao número que está no expoente, como nos exemplos a seguir:
Exemplos:
a) 4³ → Quatro elevado a três, ou quatro elevado à terceira potência, ou quatro elevado ao cubo.
b) 34 → Três elevado a quatro, ou três elevado à quarta potência.
c) (-2)¹ → Menos dois elevado a um, ou menos dois elevado à primeira potência.
d) 8² → Oito elevado a dois, ou oito elevado à segunda potência, ou oito elevado ao quadrado.
As potências de expoente 2 podem ser chamadas também de potências elevadas ao quadrado, e as potências de grau 3 podem ser chamadas de potências elevadas ao cubo, como nos exemplos anteriores.
Cálculo de potências
Para encontrar o valor de uma potência, precisamos realizar as multiplicações como nos exemplos a seguir:
a) 3²= 3 · 3 = 9
b) 5³= 5·5·5 = 125
c) 106 = 10 · 10 · 10 · 10 · 10 · 10 = 1 000 000
Tipos de potência
Existem alguns tipos específicos de potência.
1º caso – Quando a base for diferente de zero, podemos afirmar que todo número elevado a zero é igual a 1.
Exemplos:
a) 100=1
b) 12930=1
c) (-32)0=1
d) 80=1
2º caso - Todo número elevado a 1 é ele mesmo.
Exemplos:
a) 9¹ = 9
b) 12¹ = 12
c) (-213)¹= - 213
d) 0¹ = 0
3º caso - 1 elevado a qualquer potência é igual a 1.
Exemplos:
a) 1²¹ = 1
b) 1³ = 1
c) 1500=1
4º caso - Base de uma potenciação negativa
Quando a base é negativa, separamos em dois casos: quando o expoente for ímpar, a potência será negativa; quando o expoente for par, a resposta será positiva.
Exemplos:
a) (-2)³ = (-2) · (-2) · (-2) = - 8 → Note que o expoente 3 é ímpar, logo a potência é negativa.
b) (-2)4= (-2) · (-2) · (-2) · (-2) = 16 → Note que o expoente 4 é par, por isso a potência é positiva.