US Patent 10346217 Best-effort key affinity workload sharding

Devices and processes may perform best-effort key affinity workload sharding. Requests including keys are received at a key based workload manager that applies a consistent sharding algorithm to the keys to select a shard to process the request. For selected shards that are associated with a heavy workload various techniques are performed to iterate though a selection of shards until another shard without a heavy workload is selected. For example, techniques are provided such that for a given request a different shard is selected for each iteration, and shards are selected in the same order for repeated requests with the same key. For keys associated with heavy workloads, shards may be reserved solely for that key. If the techniques fail to find a shard without a heavy workload, a fallback provision may select the shard with the least amount of workload, even if that workload is considered heavy.