US 2026/0246831 A1 · LAYERED SHARDING

Abstract

Disclosed layered sharding for multi-tenant services outperforms current sharding techniques, to enhance the reliability and scalability of services. A sharding controller assigns clients and service instances to shards in each of multiple layers. Each layer can handle requests for any client, with assignments differing among the layers, at least for clients and may also for service instances. This minimize adverse effects on clients assigned to a shard with a noisy neighbor, because there are other layers (with a high probability) in which they are not sharing a shard with that noisy neighbor. As an example, with 40 service instances with 4 per shard, and shuffle sharding assignment with 40C4=91390 shards, the likelihood of a client sharing a shard with the same noisy neighbor in all layers is O(10−8) for two layers, dropping rapidly to O(10−17) for four layers.

Claims20

Dependent claims

A system comprising:

a processor;
and
a computer-readable medium storing instructions that are operative upon execution by the processor to:
assign, by a sharding controller, within each layer of a plurality of layers, two or more service instances of a plurality of service instances to each shard of a plurality of shards, wherein each layer of the plurality of layers has a separate plurality of shards;
assign, within each layer, each client of a plurality of clients to two or more shards of the plurality of shards within that layer, wherein assignments of clients to shards differs for each separate plurality of shards across the plurality of layers;
receive a first request from a first client of the plurality of clients;
based on at least receiving the first request, identify shards assigned to the first client;
and
based on at least the identification of the shards assigned to the first client, route the first request to a shard assigned to the first client.

6 more elements

A computer-implemented method comprising:

assigning, by a sharding controller, within each layer of a plurality of layers, two or more service instances of a plurality of service instances to each shard of a plurality of shards, wherein each layer of the plurality of layers has a separate plurality of shards;
assigning, within each layer, each client of a plurality of clients to two or more shards of the plurality of shards within that layer, wherein assignments of clients to shards differs for each separate plurality of shards across the plurality of layers;
receiving a first request from a first client of the plurality of clients;
based on at least receiving the first request, identifying shards assigned to the first client;
and
based on at least the identification of the shards assigned to the first client, routing the first request to a shard assigned to the first client.

3 more elements

A computer storage device having computer-executable instructions stored thereon, which, on execution by a computer, cause the computer to perform operations comprising:

assigning, by a sharding controller, within each layer of a plurality of layers, two or more service instances of a plurality of service instances to each shard of a plurality of shards, wherein each layer of the plurality of layers has a separate plurality of shards;
assigning, within each layer, each client of a plurality of clients to two or more shards of the plurality of shards within that layer, wherein assignments of clients to shards differs for each separate plurality of shards across the plurality of layers;
receiving a first request from a first client of the plurality of clients;
based on at least receiving the first request, identifying shards assigned to the first client;
and
based on at least the identification of the shards assigned to the first client, routing the first request to a shard assigned to the first client.

3 more elements

Dependencies are inferred from the claim text.

Layered sharding

Life of this patent

Layered sharding

Life of this patent

Abstract

Claims20