Distributed data store with a designated master to ensure consistency

• US 8,275,804 B2
• Filed: 09/11/2009
• Issued: 09/25/2012
• Est. Priority Date: 12/15/2004
• Status: Expired due to Fees

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds LLC
• Inventors: Swett, Ian, Hillis, W. Daniel
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US12/558,453
• Publication Number:
  US 20100070473A1
• Time in Patent Office: 1,110 Days
• Field of Search: 707600-831
• US Class Current: 707/802
• 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 network that is associated with one or more client machines, wherein the method comprises the steps of:

providing storage of data at a data store that is distributed between a plurality of computers, wherein at least one portion of the data is duplicated across at least two of the plurality of the computers;

sending a request to implement a transactional operation on the data store, wherein the transactional operation comprises an update of at least a portion of the data in the data store, and wherein the request is sent from a selected client machine to a master machine;

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

communicating the system orderstamp from the master machine to the selected client machine and to each of the plurality of computers at which the data to be updated in response to the requested transactional operation is stored; and

updating the data store in response to the requested transactional operation;

wherein the data remains consistent across the data store.

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

designating one of the client machines as the master machine.

3. The method of claim 2, wherein the designation of one of the client machines as the master machine 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 machine and the selected client machine are the same client machine.

5. The method of claim 1, wherein the step of updating the data store comprises the steps of:

propagating updated data from the master machine to any of the client machine or at least one of the plurality of computers, wherein the updated data reflects results of the requested transactional operation;

further propagating the updated data from either the client machine or the at least one of the plurality of computers to a slave computer, wherein the slave computer comprises one of the plurality of computers at which the data to be updated in response to the requested transactional operation is stored; and

updating data at the slave computer in accordance with the results of the requested transactional operation.

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

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

processing a non-transactional operation at one of the plurality of client machines without receiving a system orderstamp from the master machine.

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 client machine.

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 client machine 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 requested transactional operation originated on the master machine.

12. The method of claim 1, wherein at least a portion of the data store resides on any of the master machine or 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 machine.

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

15. The method of claim 1, wherein the requested transactional operation comprises any of an insert operation or a delete operation.

16. The method of claim 1, wherein if the orderstamp is not received at the selected client machine within a threshold time, the requested transactional operation is not allowed to proceed at the selected client machine.

17. A system implemented across a network that is associated with one or more client machines, wherein the system comprises:

a data store for storing data, wherein the data store is distributed between a plurality of computers, wherein at least one portion of the data is duplicated across at least two of the plurality of the computers;

a request to implement a transactional operation on the data store, wherein the transactional operation comprises an update of at least a portion of the data in the data store, and wherein the request is sent from a selected client machine to a master machine;

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

a communication of the orderstamp from the master machine to the selected client machine and to each of the plurality of computers at which the data to be updated in response to the requested transactional operation is stored; and

a mechanism for updating the data store in response to the requested transactional operation;

wherein the data remains consistent across the data store.

18. The system of claim 17, wherein the master machine and the selected client machine are the same client machine.

19. The system of claim 17, further comprising:

a non-transactional operation processed through one of the client machines without a receipt of a system orderstamp from the master machine.

20. The system of claim 17, wherein the mechanism for updating the data store comprises:

a transmission of updated data from the master machine to any of the client machine or at least one of the plurality of computers, wherein the updated data reflects results of the requested transactional operation;

a propagation of the updated data from either the client machine or the at least one of the plurality of computers to a slave computer, wherein the slave computer comprises one of the plurality of computers at which the data to be updated in response to the requested transactional operation is stored; and

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

21. The system of claim 17, wherein upon a failure to receive the system orderstamp at the selected client machine, the requested transactional operation fails.

22. The system of claim 17, wherein the requested transactional operation comprises any of an insert operation or a delete operation.

23. The system of claim 17, further comprising:

a threshold time;

wherein if the orderstamp is not received at the selected client machine within the threshold time, the requested transactional operation is not allowed to proceed at the selected client machine.