4 / 4 Hot Partitions & The Celebrity Problem

Two Of A Hundred

A request-routing tier has 100 workers and 10,000 tenants.

Today it uses plain sharding: 50 shards of 2 workers, every tenant pinned to one shard. You switch to shuffle sharding, giving each tenant a random pair of workers drawn from all 100, so there are

(1002)=4950\binom{100}{2} = 4950

possible assignments.

One tenant sends a request that wedges both of the workers it is assigned to. Which line describes the effect on the other tenants?

A

About 0.02%0.02% lose both and no one else notices, because a tenant holding one healthy worker is unaffected by definition

B

About 1/4950≈0.02%1/4950 \approx 0.02% lose both workers, but 1−(982)/(1002)≈4%1 - \binom{98}{2}/\binom{100}{2} \approx 4% lose at least one of the two, and those tenants only stay healthy if the client retries onto the survivor

C

About 2 percent lose both workers, the same as plain sharding, because a pair of workers is still shared with 2 percent of the fleet

D

About 4%4% lose both workers, since that is the chance a tenant's assignment intersects the wedged pair