# US 12,182,119 B2 · Redundancy and load balancing

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,182,119 B2
- Document ID: US12182119B2
- Status: Granted
- Kind: B2
- Application number: 18/322,848
- Filed: 2023-05-24
- Published: 2024-11-28
- Granted: 2024-12-31
- Earliest claimed: 2023-05-24
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Alexander Ulrich Neubeck; Gregory Scott Orzell
- Web page: https://patentgrep.com/patent/US12182119B2

## CPC

- G06F 16/24542: {Plan optimisation}
- G06F 16/2272: {Management thereof}
- G06F 16/2471: {Distributed queries}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems are described which use load balancing to efficiently perform queries. Embodiments identify available nodes and divide an index into shards. Embodiments distribute the index across the nodes where each node has at least two distinct shards. Based on a target upper bound number of requests per node, and based on which shards exist at each node, embodiments identify a query routing policy which also includes accounting for node failure. Embodiments route a query based on the identified query routing policy.

## Claims

### Claim 1

A method, implemented at a computer system that includes a processor, comprising:
identifying n available search node computer systems;
dividing an index into m shards;
distributing the index across the n available search node computer systems, including distributing a distinct set of at least two shards of the m shards to each search node computer system;
receiving a query originating from a remote computer system;
identifying a query routing policy for routing the query, the query routing policy identifying how to route queries among the search node computer systems based on, a maximum flow algorithm that determines an upper bound concurrent query capacity of each shard, calculated as n*j/m, where j is a target upper bound number of concurrent queries for each search node computer system, and
which shards of the m shards exist at each search node computer system;
routing the query among the search node computer systems based on the query routing policy, including routing a plurality of query operations among the search node computer systems, each query operation targeted to at least one shard; and
after routing the query among the search node computer systems,
aggregating a query result from partial results of the plurality of query operations; and
returning the query result to the remote computer system.

### Claim 2 (depends on 1)

The method of claim 1, wherein m is at least n*2.

### Claim 3 (depends on 2)

The method of claim 2, wherein m is n*2.

### Claim 4 (depends on 1)

The method of claim 1, wherein identifying the query routing policy includes accounting for n-i nodes, where i is a positive integer to allow for failure.

### Claim 5 (depends on 1)

The method of claim 1, wherein the query routing policy is configured to favor returning the query result as a complete result over returning the query result as a partial result.

### Claim 6

A computer system comprising:
a hardware processor; and
a computer storage media that stores computer-executable instructions that are executable by the hardware processor to at least:
identify n available search node computer systems;
divide an index into m shards, where m is at least n*2;
distribute the index across the n available search node computer systems, including distributing a distinct set of at least two shards of the m shards to each search node computer system;
receive a query originating from a remote computer system;
identify a query routing policy for routing the query, the query routing policy identifying how to route queries among the search node computer systems based on, a maximum flow algorithm that determines an upper bound concurrent query capacity of each shard, calculated as n*j/m, where j is a target upper bound number of concurrent queries for each search node computer system, and
which shards of the m shards exist at each search node computer system;
route the query among the search node computer systems based on the query routing policy, including routing a plurality of query operations among the search node computer systems, each query operation targeted to at least one shard; and
after routing the query among the search node computer systems,
aggregate a query result from partial results of the plurality of query operations; and
return the query result to the remote computer system.

### Claim 7 (depends on 6)

The computer system of claim 6, wherein m is n*2.

### Claim 8 (depends on 6)

The computer system of claim 6, wherein the query routing policy includes accounting for n-i nodes, where i is a positive integer to allow for failure.

### Claim 9 (depends on 6)

The computer system of claim 6, wherein the query routing policy is configured to favor returning the query result as a complete result over returning the query result as a partial result.

### Claim 10 (depends on 6)

The system of claim 6, wherein m is at least n*2.

### Claim 11

A computer program product comprising a computer storage media that stores computer-executable instructions that are executable by a processor system to at least:
identify n available search node computer systems;
divide an index into m shards, where m is at least n*2;
distribute the index across the n available search node computer systems, including distributing a distinct set of at least two shards of the m shards to each search node computer system;
receive a query originating from a remote computer system;
identify a query routing policy for routing the query, the query routing policy identifying how to route queries among the search node computer systems based on, a maximum flow algorithm that determines an upper bound concurrent query capacity of each shard, calculated as n*j/m, where j is a target upper bound number of concurrent queries for each search node computer system, and
which shards of the m shards exist at each search node computer system;
route the query among the search node computer systems based on the query routing policy, including routing a plurality of query operations among the search node computer systems, each query operation targeted to at least one shard; and
after routing the query among the search node computer systems,
aggregate a query result from partial results of the plurality of query operations; and
return the query result to the remote computer system.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein m is at least n*2.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein m is n*2.

### Claim 14 (depends on 11)

The computer program product of claim 11, wherein the query routing policy includes accounting for n-i nodes, where i is a positive integer to allow for failure.

### Claim 15 (depends on 11)

The computer program product of claim 11, wherein the query routing policy is configured to favor returning the query result as a complete result over returning the query result as a partial result.