Distributed Data Store with a Designated Master to Ensure Consistency

• US 20100070473A1
• Filed: 09/11/2009
• Published: 03/18/2010
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds LLC
• Inventors: SWETT, Ian, Hillis, W. Daniel
• Granted Patent: US 8,275,804 B2
• Time in Patent Office: Days
• US Class Current: 707/622
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70

Abstract

One machine, i.e. computer, on a network, such as associated with a distributed database, e.g. a data store or a partition thereof, is designated as a master, which alone can issue system orderstamps for transactional operations, while other machines associated with the data store or partition thereof act as any of clients that submit transactions to the master, or as slaves that adhere to updates from the master. If a transactional operation on the distributed database is attempted on a client machine, and communication cannot be established with the master machine, the transaction fails. The distributed data store having such a master provides a method that decreases transaction time across the distributed database, and maintains consistent data between separate machines.

Claims

1. A method implemented across a data store that is distributed between one or more computers, comprising the steps of:

initiating a transactional operation on a selected one of the computers;

sending a request from the selected computer to a master computer to implement the transactional operation;

generating a system orderstamp at the master computer in response to the received request, wherein the orderstamp uniquely identifies the transactional operation;

communicating the system orderstamp from the master computer to the selected computer; and

completing the transactional operation at the selected computer upon receipt of the system orderstamp.

2. The method of claim 1, further comprising the step of:

designating one of the computers as the master computer.

3. The method of claim 2, wherein the designation of one of the computers as the master computer comprises any of a designation by a user, a designation by an external administrator, an automated designation, a designation based on system architecture, or a random designation.

4. The method of claim 1, wherein the master computer and the selected computer are the same computer.

5. The method of claim 1, further comprising the steps of:

propagating updated data from the master computer to at least one of the other computers, wherein the updated data reflects results of the transaction;

further propagating the updated data from at least one of the other computers to a slave computer; and

updating data at the slave computer in accordance with the results.

6. The method of claim 1, wherein upon failure to receive the system orderstamp at the selected computer, the transactional operation fails.

7. The method of claim 1, further comprising the step of:

processing a non-transactional operation at one of the computers without receiving a system orderstamp from the master computer.

8. The method of claim 7, wherein the step of processing the non-transactional operation comprises the issuance of a local orderstamp at the corresponding computer.

9. The method of claim 7, wherein the non-transactional operation takes place on a local data store upon receiving any of a local orderstamp or a temporary orderstamp issued by the computer that corresponds to the local data store.

10. The method of claim 1, wherein the orderstamp further comprises a timestamp.

11. The method of claim 10, wherein the timestamp represents the time that the transactional operation originated on the master computer.

12. The method of claim 1, wherein at least a portion of the data store resides on any of the master computer and other connected computers.

13. The method of claim 1, wherein the data store comprises at least two partitions, wherein each of the partitions has a designated master computer.

14. The method of claim 1, wherein the request sent from the selected computer comprises any of a local transaction identifier, an originating computer identifier, a request type identifier, or transaction information.

15. A system implemented across a data store that is distributed between one or more computers, comprising:

a transactional operation originating on a selected one of the computers;

a request sent from the selected computer to a master computer to implement the transactional operation;

a generation of a system orderstamp at the master computer in response to the received request, wherein the orderstamp uniquely identifies the transactional operation;

a communication of the orderstamp from the master computer to the selected computer; and

a completion of the transactional operation at the selected computer upon receipt of the orderstamp.

16. The system of claim 15, wherein the master computer and the selected computer are the same computer.

17. The system of claim 15, further comprising:

a non-transactional operation processed through one of the computers without a receipt of a system orderstamp from the master computer.

18. The system of claim 15, further comprising:

a transmission of updated data from the master computer to at least one of the other computers, wherein the updated data reflects results of the transaction;

a propagation of the updated data from at least one of the other computers to a slave computer; and

an update of a data store at the slave computer in accordance with the received updated data.

19. The system of claim 15, wherein upon a failure to receive the system orderstamp at the selected computer, the transactional operation fails.