System for maintaining consistency across a decentralized database cluster and method therefor

Patent metadata

Field	Value
Publication number	US-10268744-B2
Application number	US-201615010183-A
Country	US
Kind code	B2
Filing date	Jan 29, 2016
Priority date	Sep 22, 2015
Publication date	Apr 23, 2019
Grant date	Apr 23, 2019

Abstract

A system and method for maintaining consistency across a decentralized database cluster is presented. When a database server receives an index update message, it adds a message to a queue indicating it has received the message and watches an index update node. Once every server in the cluster has added a message to the queue or a timer has expired, it is known that every active database server has received the message. The update can be performed for each server and the changes committed simultaneously. In such a manner, all database servers in the cluster perform an update at approximately the same time. When a database server is unable to complete an update, it enters a fallen behind mode and performs updates more often, as configured in a configuration database. Other embodiments also are disclosed.

First claim

What is claimed is:

1. A system comprising:
a plurality of database servers each hosting a copy of a database, each database server comprising one or more processing modules and one or more non-transitory storage modules storing computing instructions configured to run on the one or more processing modules and perform acts of:
adding a node representing a database server to a list of active database servers;
receiving a checkpoint marker message with an associated checkpoint ID, wherein the checkpoint marker message and the associated checkpoint ID are embedded in a document update message;
determining when a checkpoint roll call node exists for the associated checkpoint ID;
when the checkpoint roll call node exists for the associated checkpoint ID, adding a database server node representing the database server to the checkpoint roll call node;
determining when a roll call has expired; and
after the roll call has expired and after the database server node is added to the checkpoint roll call node, committing an update to the database server.

2. The system of claim 1 , wherein:
determining when the checkpoint roll call node exists for the associated checkpoint ID further comprises:
creating the checkpoint roll call node when the checkpoint roll call node does not exist; and
creating a checkpoint flag node.

3. The system of claim 2 , wherein the computing instructions are further configured to perform an act of:
placing a watch on the checkpoint flag node.

4. The system of claim 3 , wherein:
determining when the roll call has expired further comprises:
comparing a checkpoint roll call node expiration time with a current time; and
updating the checkpoint flag node when the checkpoint roll call node expiration time is earlier than the current time.

5. The system of claim 1 , wherein the computing instructions are further configured to perform acts of:
pausing execution of database instructions after receiving the checkpoint marker message with the associated checkpoint ID; and
resuming the execution of the database instructions after committing the update to the database server.

6. The system of claim 1 , wherein the database contains a shard of a larger database.

7. The system of claim 1 , wherein the computing instructions are further configured to perform an act of:
removing the database server from the list of active database servers when the database server becomes inactive.

8. The system of claim 1 , wherein:
the database contains a shard of a larger database;
determining when the checkpoint roll call node exists for the associated checkpoint ID further comprises:
creating the checkpoint roll call node when the checkpoint roll call node does not exist; and
creating a checkpoint flag node;

determining when the roll call has expired further comprises:
comparing nodes belonging to the checkpoint roll call node to nodes belonging to the list of active database servers; and
updating the checkpoint flag node when there are no nodes missing from the checkpoint roll call node;

determining when the roll call has expired further comprises:
receiving a notification that the checkpoint flag node has been updated; and

the computing instructions are further configured to perform acts of:
pausing execution of instructions after receiving the checkpoint marker message with the associated checkpoint ID;
resuming the execution of the instructions after committing the update to the database server;
removing the database server from the list of active database servers when the database server becomes inactive; and
placing a watch on the checkpoint flag node.

9. The system of claim 1 , wherein:
the checkpoint marker message causes the database server to pause processing of other messages until after a roll call of the list of available database servers is completed.

10. A method comprising:
in a database server of a cluster of database servers:
adding a node representing the database server to a list of active database servers;
receiving a checkpoint marker message with an associated checkpoint ID, wherein the checkpoint marker message and the associated checkpoint ID are embedded in a document update message;
determining when a checkpoint roll call node exists for the associated checkpoint ID;
when the checkpoint roll call node exists for the associated checkpoint ID, adding a database server node representing the database server to the checkpoint roll call node;
determining when a roll call is complete; and
after the roll call has expired and after the database server node is added to the checkpoint roll call node, committing an update to the database server.

11. The method of claim 10 wherein:
determining when the checkpoint roll call node exists for the associated checkpoint ID further comprises:
creating the checkpoint roll call node when the checkpoint roll call node does not exist; and
creating a checkpoint flag node.

12. The method of claim 11 further comprising:
placing a watch on the checkpoint flag node.

13. The method of claim 12 , wherein:
determining when the roll call is complete further comprises:
comparing nodes belonging to the checkpoint roll call node to nodes belonging to the list of active database servers; and
updating the checkpoint flag node when there are no nodes missing from the checkpoint roll call node.

14. The method of claim 10 , wherein:
the checkpoint marker message causes the database server to pause processing of other messages until after a roll call of the list of available database servers is completed.

15. A method comprising:
receiving a first checkpoint marker message with an associated checkpoint ID, wherein the first checkpoint marker message and the associated checkpoint ID are embedded in a document update message;
determining when a checkpoint roll call node associated with the first checkpoint marker message is still active; and
when the checkpoint roll call node is not active:
removing a database server from a list of available servers; and
leaving a normal mode to enter a fallen behind mode.

16. The method of claim 15 further comprising:
detecting that the database server has caught up to a cluster of database servers; and
after the database server has caught up to the cluster of database servers, leaving the fallen behind mode to enter the normal mode.

17. The method of claim 16 , wherein:
entering the fallen behind mode comprises updating the database server at a higher rate than a rate in the normal mode.

18. The method of claim 17 , wherein:
updating the database server at the higher rate comprises accessing a configuration database to determine the higher rate.

19. The method of claim 18 , wherein:
the configuration database comprises information regarding a normal update rate for the normal mode, a fallen behind update rate for the fallen behind mode, and an update interval.

20. The method of claim 19 , wherein:
the configuration database further comprises a count of marker messages; and
the update interval is configured to indicate that an update is to occur when a calculation of count mod update interval is equal to zero.

21. The method of 15 , wherein:
the first checkpoint marker message comprises a timestamp indicating a time during which the first checkpoint marker message was completed; and
the method further comprises:
detecting that the database server has caught up to a cluster of database servers by:
comparing the timestamp w

Assignees

• Walmart Apollo Llc

Inventors

• Guney Ergin
• Zheng Yan

Classifications

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F9/4406

  Loading of operating system · CPC title

• G06F16/278

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

• G06Q30/0625

  by formulating product or service queries, e.g. using keywords or predefined options · CPC title

• G06F16/2471

  Distributed queries · CPC title