Route a Query to the Correct Shard

Problem Given a sharding scheme (key ranges, or a hash of the key), implement routing so a single-key query goes to the correct shard, and a scatter-gather that fans a cross-shard query out to all relevant shards and merges the partial results.

Input / Output

• Input: a key (or query) and the shard map (range boundaries or hash config).
• Output: the target shard for a point query; the merged result for a cross-shard query.

Constraints

• Must handle resharding boundaries — a key's home shard may move as shards split or merge.
• Cross-shard queries must aggregate correctly (sums, top-k, ordering) across partial results.

Example

• Range map [0,1000)->s0, [1000,2000)->s1: key 1500 routes to s1. A range query 500..1500 scatters to s0 and s1 and gathers both.