Back to results
US 12,182,119 B2Granted
Redundancy and load balancing
AssigneeMicrosoft Technology Licensing, LLC
InventorsAlexander Ulrich Neubeck, Gregory Scott Orzell
Life of this patent
Estimating the term…
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.
Claims15
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.
9 more elements
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.
12 more elements
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.
9 more elements
Dependencies are inferred from the claim text.