System for dynamically varying traffic routing modes in a distributed cluster and method therefor

Patent metadata

Field	Value
Publication number	US-10116736-B2
Application number	US-201514861726-A
Country	US
Kind code	B2
Filing date	Sep 22, 2015
Priority date	Sep 22, 2015
Publication date	Oct 30, 2018
Grant date	Oct 30, 2018

Abstract

A system for dynamically varying traffic routing modes in a distributed database system is presented. A database system comprises a load balancer and a database partitioned into a first and second shard. Coupled to the load balancer are a first plurality of database servers and a second plurality of database servers. Each of the first plurality of database servers contains a copy of the first shard of the database. Each of the second plurality of database servers contains a copy of the second shard of the database. Each server in the first plurality of database servers sends queries to a server in the second plurality of database servers using a round-robin system in which servers in the second plurality of database servers take turns processing incoming queries, as a method of distributing load among the multiple servers. Other embodiments also are disclosed.

First claim

What is claimed is:

1. A system comprising:
a load balancer;
a database partitioned into at least a first shard of the database and a second shard of the database, the first shard of the database and the second shard of the database having been split from a partition of the database, and the partition of the database having been split from the database;
a first plurality of database servers coupled to the load balancer, each database server in the first plurality of database servers hosting a copy of the first shard of the database; and
a second plurality of database servers coupled to the load balancer, each database server in the second plurality of database servers hosting a copy of the second shard of the database; and
a centralized data store configured to maintain a list of (1) each database server in the first plurality of database servers and (2) each database server in the second plurality of database servers;
wherein:
the load balancer is configured to:
send incoming instructions to a database server selected from the first plurality of database servers or the second plurality of database servers, using load balancing techniques;
receive a first incoming instruction from a user, wherein the first incoming instruction comprises first queries of the first shard and second queries of the second shard;
process the first incoming instruction to extract the first queries of the first shard and the second queries of the second shard from the first incoming instruction;
forward the first queries of the first shard to the first plurality of database servers;
forward the second queries of the second shard to the second plurality of database servers;
receive a first query result from one database server of the first plurality of database servers;
receive a second query result from one database server of the second plurality of database servers;
aggregate the first query result and the second query result into an aggregated query result; and
present the aggregated query result to a requestor;

each database server in the first plurality of database servers is configured to send the first queries of the first shard of the database to a database server in the first plurality of database servers such that consecutive queries of the first queries of the first shard of the database are sent to different database servers of the first plurality of database servers; and
each database server in the second plurality of database servers is configured to send the second queries of the second shard of the database to a database server in the second plurality of database servers such that consecutive queries of the second queries of the second shard of the database are sent to different database servers of the second plurality of database servers.

2. The system of claim 1 , wherein:
when a first database server in the first plurality of database servers becomes inaccessible, the first database server in the first plurality of database servers that has become inaccessible is skipped when the load balancer forwards the first queries of the first shard to the first plurality of database servers; and
when a second database server in the second plurality of database servers becomes inaccessible, the second database server in the second plurality of database servers that has become inaccessible is skipped when the load balancer forwards the second queries of the second shard to the second plurality of database servers.

3. The system of claim 2 , wherein:
an inaccessible database server of at least one of the first plurality of database servers or the second plurality of database servers becomes inaccessible when it is determined that a load of the inaccessible database server becomes higher than a first threshold load.

4. The system of claim 1 , wherein:
present the aggregated query result comprises send the aggregated query result with markup language configured to display the aggregated query result as a web page.

5. The system of claim 1 , wherein:
present the aggregated query result comprises send the aggregated query result with markup language configured to display the aggregated query result using a mobile app.

6. The system of claim 1 , wherein the database is partitioned as a horizontal partition.

7. A method comprising:
receiving, at a load balancer, a first incoming instruction from a user, wherein the first incoming instruction comprises first queries of a first shard and second queries of a second shard;
processing, at the load balancer, the first incoming instruction to extract the first queries of the first shard and the second queries of the second shard from the first incoming instruction;
forwarding a first one of the first queries of the first shard from the load balancer to a first database server of a first plurality of database servers, wherein the first plurality of database servers hosts a first shard of a database, the first shard of the database having been split from a partition of the database, and the partition of the database having been split from the database;
forwarding a second one of the first queries of the first shard from the load balancer to a second database server of the first plurality of database servers such that consecutive queries of the first queries of the first shard of the database are sent to different database servers of the first plurality of database servers;
executing the first queries in both the first database server and the second database server to produce a first query result;
forwarding a first one of the second queries of the second shard from the load balancer to a third database server of a second plurality of database servers, wherein the second plurality of database servers hosts a second shard of the database, the second shard of the database having been split from the partition of the database;
forwarding a second one of the second queries of the second shard from the load balancer to a fourth database server of the second plurality of database servers, such that consecutive queries of the second queries of the second shard of the database are sent to different database servers of the second plurality of database servers;
executing the second queries in both the third database server and the fourth database server to produce a second query result;
aggregating the first query result with the second query result to form an aggregated query result; and
presenting the aggregated query result to a requestor.

8. The method of claim 7 , wherein forwarding the first one of the first queries of the first shard from the load balancer to the first database server comprises:
skipping a database server of the first plurality of database servers if when the database server of the first plurality of database servers becomes inaccessible.

9. The method of claim 8 , wherein:
the database server of the first plurality of database servers becomes inaccessible when a load of the database server of the first plurality of database servers becomes higher than a first threshold load.

10. The method of claim 9 further comprising:
forwarding an additional one of the first queries to the database server of the first plurality of database servers after the load of the database server of the first plurality of database servers becomes lower than a second threshold load.

11. The method of claim 7 , wherein forwarding the first one of the second queries of the second shard from the load balancer to the third database server comprises:
skipping a database server of the second plurality of database servers if when the database server of the second plurality of database servers becomes inaccessible.

12. The method

Assignees

• Wal Mart Stores Inc
• Walmart Apollo Llc

Inventors

• Guney Ergin
• Zheng Yan

Classifications

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L67/1017

  based on a round robin mechanism · CPC title

• H04L67/1004

  Server selection for load balancing · CPC title

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• G06F16/2471

  Distributed queries · CPC title