AWS: cells and shuffle sharding (Builders' Library)

01 · CONTEXT

Why isolate customers instead of just scaling

Even knowing it is in a multi-tenant environment, the customer still wants the experience of a dedicated one. According to AWS, shuffle sharding became a central pattern for delivering cost-efficient multi-tenant services with a single-tenant experience, and the guidance on cell-based architecture seeks to reduce the effect of failures to a limited number of components. Both deal with the blast radius of a failure.

Shuffle sharding appears as the invention that met a need of Amazon Route 53. According to AWS, the biggest challenge for any DNS provider is handling DDoS attacks, and buying server capacity in large volume is a losing strategy. The need was to spend resources only on defending the domains that were actually under attack, and the invention that met it was shuffle sharding.

02 · BASELINE

The blast radius of a shared fleet

Without sharding, any worker has to handle any request. This is great for efficiency and redundancy, and little spare capacity is needed, because the other workers absorb the work of the one that fails.

1. Without sharding, any worker handles any request; if one fails, the others absorb its work.

2. A particular type of request, or a flood of requests, takes down the first worker it hits.

3. The remaining workers take over the load of the one that went down and the problem propagates through them.

4. The scope of impact becomes the whole service and all customers.

Regular sharding splits the fleet into shards. Because each shard has few workers, more idle capacity must be kept to absorb failures; in return, the scope of impact drops in proportion to the number of shards. In the AWS example, one shard represents a quarter of the service, and a 25 percent impact is much better than a 100 percent one.

03 · SHUFFLE SHARDING

Each customer, a combination of workers

In shuffle sharding, virtual shards of two workers are created, and each customer (or resource to isolate) is assigned to one of them. One customer's problem affects its virtual shard, but does not fully affect any other: at most one worker of another shard is hit.

1. Each customer is assigned to a combination of two workers, its shuffle shard; Rainbow uses alpha and beta.

2. The other customers get other combinations: Rose and Sunflower each share one worker with Rainbow, but none shares both.

3. Rainbow fires off a problematic request or a flood of requests, and the problem hits its virtual shard.

4. Rose and Sunflower keep being served by workers delta and gamma, as long as the client tolerates partial failure, for example with retries.

5. No other shard loses both workers: at most one worker of each other shard is affected.

The math explains the gain. With eight workers there are 28 combinations of two workers, that is, 28 possible shuffle shards; with many customers spread across them, the scope of impact of a problem is 1/28, seven times better than regular sharding.

The more workers and customers, the better: most scaling challenges get worse along these dimensions, but shuffle sharding becomes more effective. With enough workers there can be more shuffle shards than customers, and each customer can be isolated.

04 · AT SCALE

Shuffle sharding in Amazon Route 53

In Route 53, capacity is organized into 2048 virtual name servers, which do not correspond to physical servers and can be moved to manage capacity. Each customer domain gets a shuffle shard of four virtual servers, which gives 730 billion possible shuffle shards, and no domain shares more than two virtual servers with another.

If a domain suffers a DDoS attack, its four virtual servers see a traffic spike, but no other domain notices. Shuffle sharding also makes it possible to identify the target customer and isolate it in capacity dedicated to attacks.

05 · CELLS

Cells: isolating the entire workload

A cell-based architecture uses several isolated instances of the workload, each called a cell. Each cell is independent, shares no state with the others, and serves a subset of the requests. A routing layer distributes requests by the partition key, such as the customer ID, and presents a single endpoint to clients.

The idea comes from the concept of a ship's bulkhead (bulkhead), with watertight compartments, and in complex systems this pattern is often replicated to isolate failures. Cells contain failures that are hard to contain otherwise, such as failed deployments and corrupted requests or requests that trigger a specific failure mode (poison pill requests).

1. The client talks to a single endpoint; the cell router uses the partition key to decide which cell serves the request.

2. The request goes to cell A, a complete workload with its own service and database.

3. A bad software update, or a corrupted request, hits cell B: the effect stays confined to it and to the requests it processes.

4. The other cells share no state with B and keep serving their customers.

5. The control plane provisions cells and informs the router; if it becomes unavailable, what has already been provisioned keeps serving.

AWS works out the isolation math: with 10 cells serving 100 requests, when one cell fails, 90% of requests are not affected. It also notes that building cells does not necessarily require doubling or tripling the infrastructure; 30 hosts can remain the same 30 hosts, with a router and tasks grouped across cells.

There are three pieces. The router is the thinnest possible layer and only routes requests to the right cell; the cell is a complete workload; and the control plane handles administration, with APIs to provision, move, migrate, update, remove, deploy, and monitor cells. Once provisioned, the data plane does not depend on the control plane, which statistically is more likely to fail.

Because the router is shared across cells, it does not follow their compartmentalization; so it must be as simple and horizontally scalable as possible, with no complex business logic. As for the partition key, a good one is easy to access in most API calls, and you need to think about how to handle very large customers. Calls between cells should go back through the normal router.

06 · DECISIONS

Where to draw the cell boundary and when the cost is worth it

The cell boundary can follow availability zones in two ways. In Multi-AZ, cells are Multi-AZ or regionais. In Single-AZ, the service is divided along AZ boundaries.

AWS proposes a question to decide: is it better for 100% of customers to have a 5% failure rate or for 5% of customers to have a 100% failure rate? It sees benefit in applications where any unavailability has a large negative impact and in multi-tenant services where some tenants require their own cell, and warns that the architecture is not suitable for all workloads.

The price is real: more complexity from redundant infrastructure and components, high infrastructure and service costs, specialized operational tooling and practices, and the need to invest in a cell routing layer.