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

• US 10,116,736 B2
• Filed: 09/22/2015
• Issued: 10/30/2018
• Est. Priority Date: 09/22/2015
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Inventors: Guney, Ergin, Zheng, Yan
• Primary Examiner(s): Park, Jeong S
• Application Number:
  US14/861,726
• Publication Number:
  US 20170085634A1
• Time in Patent Office: 1,134 Days
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism

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.

Claims

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 of claim 11, wherein:

the database server of the second plurality of database servers becomes inaccessible when it is determined that a load of the database server of the second plurality of database servers becomes higher than a first threshold load.

13. The method of claim 12 further comprising:

forwarding an additional one of the second queries to the database server of the second plurality of database servers after the load of the database server of the second plurality of database servers becomes lower than a second threshold load.

14. The method of claim 7, wherein:

presenting the aggregated query result comprises placing the aggregated query result with markup language configured to display the aggregated query result on a web browser.

15. The method of claim 7, wherein:

presenting the aggregated query result comprises placing the aggregated query result with markup language configured to display the aggregated query result using a mobile app.

16. A method comprising:

processing a first instruction at a load balancer;

forwarding a processed first instruction from the load balancer to a first database server (1) assigned to a first server set and (2) hosting a first shard, the first shard having been split from a partition, and the partition having been split from a database;

forwarding the processed first instruction from the load balancer to a second database server (1) assigned to the first server set and (2) hosting a second shard different than the first shard hosted by the first database server, the second shard having been split from the partition of the database;

performing a first query on both the first database server and the second database server;

processing a second instruction at the load balancer;

forwarding a processed second instruction from the load balancer to a third database server (1) assigned to a second server set and (2) hosting a copy of the first shard;

forwarding the processed second instruction from the load balancer to a fourth database server (1) assigned to the second server set and (2) hosting a copy of the second shard;

performing a second query on both the third database server and the fourth database server;

receiving a first query result from the first database server;

receiving a second query result from the second database server;

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;

wherein;

the third database server is distinct from the first database server and chosen using a first predetermined order of a first plurality of database servers hosting the first shard, wherein the first plurality of database servers host the first shard or a copy thereof; and

the fourth database server is distinct from the second database server and chosen using a second predetermined order of a second plurality of database servers hosting the second shard, wherein the second plurality of database servers host the second shard or a copy thereof.

17. The method of claim 16, wherein:

presenting the aggregated query result comprises placing the aggregated query result with markup language configured to display the aggregated query result on a web browser; and

transmitting the aggregated query result and markup language to the requestor.