Papers
Workload isolation using shuffle-sharding
Colm MacCárthaigh · Amazon Builders' Library (artigo online, publicado em 5 de dezembro de 2019), 2019
O problema: hospedar DNS na raiz do domínio e sobreviver a DDoS
O artigo parte do início do Amazon Route 53. Clientes da AWS queriam usar S3, CloudFront e Elastic Load Balancing na raiz do domínio (como "amazon.com"), e não apenas em nomes como "www.amazon.com". Por uma decisão antiga do protocolo DNS, o CNAME, que permite delegar parte de um domínio a outro provedor, não funciona na raiz. Por isso a AWS teria de hospedar o DNS dos clientes e devolver o conjunto atual de endereços IP desses serviços, que não podem ser fixados à mão porque crescem o tempo todo. O maior desafio de qualquer provedor de DNS, segundo o autor, são os ataques de negação de serviço distribuídos (DDoS): o DNS roda sobre UDP, o que torna as requisições falsificáveis em boa parte da internet, e por ser infraestrutura crítica ele é um alvo atraente. Responder com enormes volumes de capacidade não escala, pois cada servidor adicionado custa milhares de dólares, enquanto o atacante acrescenta clientes falsos por centavos usando botnets. Os equipamentos de limpeza de tráfego, o estado da arte na época, custariam dezenas de milhões de dólares para cobrir todos os domínios e atrasariam o cronograma em meses, então nem foram seriamente considerados. A necessidade era gastar recursos defendendo apenas os domínios realmente sob ataque, entregando um DNS com 100% de disponibilidade com poucos recursos. A invenção foi o shuffle sharding.
Sem sharding e com sharding comum: eficiência contra escopo de impacto
Imagine um serviço escalável horizontalmente com oito workers, que podem ser servidores, filas ou bancos. Sem sharding, todos atendem qualquer requisição. Isso é ótimo para eficiência e redundância: se um worker falha, os outros sete absorvem o trabalho, então pouca folga de capacidade é necessária. O problema surge quando uma falha pode ser disparada por um tipo particular de requisição ou por uma enxurrada delas, como num DDoS. O problema derruba o primeiro worker atingido e depois se propaga em cascata, porque os workers restantes assumem a carga e caem também. O escopo do impacto vira "tudo e todos": o serviço inteiro cai e todo cliente é afetado. Com sharding comum, a frota é dividida em quatro shards de dois workers e os recursos, como domínios de clientes, são repartidos entre eles. Ainda há redundância, mas com apenas dois workers por shard é preciso manter mais capacidade ociosa para absorver falhas; em troca, o escopo do impacto cai bastante. Segundo o autor, o escopo é reduzido pelo número de shards: se um cliente tem um problema, o shard dele pode ser afetado, junto com todos os outros clientes desse shard, mas isso representa um quarto do serviço, ou seja, 25% de impacto em vez de 100%. A troca, portanto, é eficiência (mais folga de capacidade) por um escopo de impacto menor.
Shuffle sharding: shards virtuais com combinações de workers
No shuffle sharding criam-se shards virtuais de dois workers cada, e cada cliente (ou o que se queira isolar) é atribuído a um deles. No exemplo com oito workers e oito clientes, o cliente "rainbow" fica nos workers um e quatro; essa combinação é o shuffle shard dele. O cliente "rose" também usa o worker um, mas o outro worker dele é o oito. Se o rainbow tem um problema, como uma requisição venenosa ou uma enxurrada de requisições, o impacto atinge o shard virtual dele, mas não atinge por completo nenhum outro shuffle shard: no máximo um worker de outro shuffle shard é afetado. Se os solicitantes toleram falhas e contornam o problema, por exemplo com retentativas, o serviço segue sem interrupção para os demais: o rose é atendido pelo worker oito e o sunflower pelo worker seis, embora cada um divida um worker com o rainbow. Com oito workers há 28 combinações únicas de dois workers, ou seja, 28 shuffle shards possíveis. Se houver centenas de clientes ou mais, cada um atribuído a um shuffle shard, o escopo do impacto de um problema é de apenas 1/28, contra 1/4 no sharding comum com quatro shards, ou seja, sete vezes melhor. O autor destaca que os números melhoram de forma exponencial com mais workers e clientes, ao contrário da maioria dos desafios de escala. Com workers suficientes, pode haver mais shuffle shards do que clientes, e cada cliente pode ficar isolado.
Shuffle sharding no Route 53 e refinamentos
No Route 53, a capacidade foi organizada em 2048 servidores de nomes virtuais. Eles são virtuais porque não correspondem aos servidores físicos que hospedam o serviço e podem ser movidos para gerenciar capacidade. Cada domínio de cliente recebe um shuffle shard de quatro desses servidores virtuais. Com esses números, o artigo fala em 730 bilhões de shuffle shards possíveis, tantos que cada domínio pode ter um shard único. O autor vai além: garante-se que nenhum domínio compartilhe mais de dois servidores virtuais com qualquer outro. Se um domínio é alvo de DDoS, os quatro servidores virtuais dele recebem um pico de tráfego, mas nenhum outro domínio percebe. Além disso, o cliente atacado pode ser identificado e isolado em capacidade dedicada a ataques. A AWS também desenvolveu uma camada própria de limpeza de tráfego, o AWS Shield, mas o autor afirma que o shuffle sharding faz uma diferença enorme para manter contínua a experiência do conjunto dos clientes durante os ataques. Na conclusão, o texto diz que a técnica foi incorporada a muitos outros sistemas e cita um refinamento, o shuffle sharding recursivo, em que os itens são particionados em várias camadas, isolando o cliente do cliente. O shuffle sharding em si é descrito como muito adaptável e como uma forma inteligente de arranjar recursos existentes, em geral sem custo adicional. A biblioteca open source Infima, do Route 53, traz implementações para atribuir e organizar recursos.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.