Papers
Workload isolation using shuffle-sharding
Colm MacCárthaigh · Amazon Builders' Library (online article, published December 5, 2019), 2019
The problem: hosting DNS at the domain apex and surviving DDoS
The article starts from the beginning of Amazon Route 53. AWS customers wanted to use S3, CloudFront, and Elastic Load Balancing at the root of the domain (such as "amazon.com"), and not only at names like "www.amazon.com". Because of an old decision in the DNS protocol, the CNAME, which allows delegating part of a domain to another provider, does not work at the root. So AWS would have to host customers' DNS and return the current set of IP addresses of those services, which cannot be fixed by hand because they grow all the time. The biggest challenge for any DNS provider, according to the author, is distributed denial-of-service (DDoS) attacks: DNS runs over UDP, which makes requests spoofable across much of the internet, and being critical infrastructure it is an attractive target. Responding with enormous amounts of capacity does not scale, since each added server costs thousands of dollars, while the attacker adds fake clients for pennies using botnets. Traffic scrubbing appliances, the state of the art at the time, would cost tens of millions of dollars to cover all domains and would delay the schedule by months, so they were not even seriously considered. The need was to spend resources defending only the domains actually under attack, delivering a DNS with 100% availability with few resources. The invention was shuffle sharding.
Without sharding and with regular sharding: efficiency versus blast radius
Imagine a horizontally scalable service with eight workers, which could be servers, queues, or databases. Without sharding, all of them serve any request. This is great for efficiency and redundancy: if one worker fails, the other seven absorb the work, so little spare capacity is needed. The problem arises when a failure can be triggered by a particular type of request or by a flood of them, as in a DDoS. The problem takes down the first worker hit and then spreads in a cascade, because the remaining workers take over the load and fall too. The blast radius becomes "everything and everyone": the whole service goes down and every customer is affected. With regular sharding, the fleet is divided into four shards of two workers and resources, such as customer domains, are split among them. There is still redundancy, but with only two workers per shard you need to keep more idle capacity to absorb failures; in exchange, the blast radius drops considerably. According to the author, the blast radius is reduced by the number of shards: if a customer has a problem, their shard may be affected, along with all the other customers on that shard, but that represents a quarter of the service, that is, 25% impact instead of 100%. The trade-off, therefore, is efficiency (more spare capacity) for a smaller blast radius.
Shuffle sharding: virtual shards with combinations of workers
In shuffle sharding, virtual shards of two workers each are created, and each client (or whatever one wants to isolate) is assigned to one of them. In the example with eight workers and eight clients, the client "rainbow" lands on workers one and four; that combination is its shuffle shard. The client "rose" also uses worker one, but its other worker is eight. If rainbow has a problem, such as a poison request or a flood of requests, the impact hits its virtual shard but does not fully hit any other shuffle shard: at most one worker of another shuffle shard is affected. If the requesters are fault tolerant and work around the problem, for example with retries, the service continues uninterrupted for the others: rose is served by worker eight and sunflower by worker six, even though each shares a worker with rainbow. With eight workers there are 28 unique combinations of two workers, that is, 28 possible shuffle shards. If there are hundreds of clients or more, each assigned to a shuffle shard, the scope of impact of a problem is only 1/28, versus 1/4 in regular sharding with four shards, which is seven times better. The author emphasizes that the numbers improve exponentially with more workers and clients, unlike most scaling challenges. With enough workers, there can be more shuffle shards than clients, and each client can be isolated.
Shuffle sharding in Route 53 and refinements
In Route 53, capacity was organized into 2048 virtual name servers. They are virtual because they do not correspond to the physical servers that host the service and can be moved around to manage capacity. Each customer domain gets a shuffle shard of four of these virtual servers. With these numbers, the article cites 730 billion possible shuffle shards, so many that every domain can have a unique shard. The author goes further: it is guaranteed that no domain shares more than two virtual servers with any other. If a domain is the target of a DDoS, its four virtual servers receive a traffic spike, but no other domain notices. Moreover, the attacked customer can be identified and isolated onto capacity dedicated to attacks. AWS also developed its own traffic-scrubbing layer, AWS Shield, but the author states that shuffle sharding makes an enormous difference in keeping the experience of customers as a whole continuous during attacks. In the conclusion, the text says the technique has been incorporated into many other systems and cites a refinement, recursive shuffle sharding, in which items are partitioned across multiple layers, isolating customer from customer. Shuffle sharding itself is described as very adaptable and as a clever way of arranging existing resources, generally at no additional cost. Route 53's open source library Infima provides implementations for assigning and organizing resources.
See the ideas at work
Practice the designs that use this paper in the System Design school.