Shuffle sharding

A bad client is one that causes servers to suffer.

Examples include:

• Creating a flood of requests, far exceeding typical client behavior.
• Sending expensive requests that consume excessive resources.
• Generating poisonous requests that crash servers due to code bugs.

This does not require malicious intent.

A bad client could be:

• A popular service experiencing sudden traffic spikes.
• A service running a load test.
• A new client with an unobserved request pattern.

The reason for the client’s behavior is irrelevant.

What matters is that the server suffers.

This can trigger a chain reaction, leading to full service shutdown.

We have previously discussed:

• Load balancing
• Rate limiting

These mechanisms protect servers.

But only to a limited extent.

Distributed systems evolve over time.

Changes include:

• Adding new features
• Fixing bugs
• Updating software dependencies
• Changing hardware profiles
• Applying security patches

Each change alters system capacity.

Load balancers and rate limiters configured a year ago

May no longer provide adequate protection.

Shuffle sharding is a resilience technique based on the bulkhead pattern.

We run a service on eight servers.

In a classic setup:

• Each server handles requests from any client.
• A load balancer distributes traffic evenly.

This setup provides efficiency and redundancy.

If one server fails, the load balancer removes it.

Remaining servers continue processing requests.

A bad client enters the system.

It may cause servers to fail one by one.

Each failure impacts all clients.

Result: 100% of clients are affected.

Bulkheads divide resources into fixed-size groups.

Groups are isolated from each other.

We divide the server fleet into four shards.

Each shard contains two servers.

Now, each client’s requests are processed only by its own shard.

This is a familiar concept.

It uses partitioning.

Bulkheads and partitioning share the same core idea: splitting the whole into parts.

Key distinction:

• Bulkhead pattern: focused on availability.
• Partitioning: focused on scalability.

Bonus benefits of partitioning include improved performance and availability.

With sharding in place:

• A bad client only affects its own shard.
• At most, two servers are impacted.

Other shards remain operational.

This reduces the blast radius.

Previously, 100% of clients were affected.

Now, only 25% of clients are impacted.

Still, 25% of good clients are affected.

These clients are unlucky.

They are assigned to the same shard as the bad client.

The service remains unavailable to them.

This is a significant limitation.

We now need to address how to protect all good clients.

The next step is to explore how to improve this further.

The current setup reduces impact but does not eliminate it.

The system still suffers from client-specific failures.

The next section will introduce how to extend this protection.

Shuffle sharding is not a complete solution.

It is a foundational step toward greater resilience.

It enables better isolation.

But full protection requires additional design.

We must now consider how to distribute clients across shards more effectively.

This will be the focus of the next part.

The core challenge is assigning clients to shards effectively.

A simple example: 8 clients with IDs 1 to 8.

Use the modulo function: hash(client_id) % number_of_shards.

This assigns clients to shards based on their ID.

Result: client 1 ends up in shard 4.

If shard 4 fails, client 1 is impacted.

This creates a 25% blast radius — a single shard failure affects 25% of clients.

Assign clients randomly to servers.

Example: clients 1, 4, and 7 end up on the same server.

If that server fails, clients 4 and 7 are affected.

But servers 6 and 8 remain healthy.

They can now serve requests from clients 4 and 7.

This demonstrates shuffle-sharding.

Sharding: splitting the cluster into independent groups.

Shuffling: distributing clients so that no two clients share a shard.

Goal: if any two clients are on the same shard, there exists another shard where they are not.

• It's impossible to isolate every client from every other.

• Overlap is inevitable.

• Some clients will share servers.

• These shared clients can impact each other.

• However, the probability of impact decreases as shard size grows.

• More servers in the cluster reduce overlap risk.

• More servers per shard reduce the chance of shared client impact.

Clients must handle server failures.

They should use short timeouts.

They should retry failed requests.

Retries are likely to route to healthy servers.

This increases the chance of serving requests from unaffected servers.

A smart routing component is needed.

It must know all server locations.

It must detect failed servers quickly.

It must redirect requests to healthy servers.

This routing logic can be built into client libraries.

Or it can be implemented as a dedicated router.

• Stateless assignment:

  • Does not track past assignments.
  • Simple to implement.
  • Less control over overlaps.

• Stateful assignment:

  • Uses a data store to record existing shard assignments.
  • For each new client, checks all current shards.
  • Selects the next shard that minimizes overlap.
  • Provides stronger guarantees about client distribution.