Method and apparatus for reading and writing committed data

• US 10,671,496 B2
• Filed: 05/25/2017
• Issued: 06/02/2020
• Est. Priority Date: 05/31/2016
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: MongoDB, Inc.
• Inventors: Horowitz, Eliot, Schwerin, Andrew Michalski, Stearn, Mathias Benjamin, Milkie, Eric Andrew
• Primary Examiner(s): Bowen, Richard L
• Application Number:
  US15/605,276
• Publication Number:
  US 20170344441A1
• Time in Patent Office: 1,104 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

According to some aspects, a database system comprising a processor configured to execute a plurality of system components is provided. The plurality of system components may include an interface component configured to receive a write commit command and provide a write commit confirmation, a snapshot component configured to generate a plurality of snapshots of data stored in a data storage node of a plurality of data storage nodes and identify a committed snapshot representative of data that has been replicated on a majority of the plurality of data storage nodes, and a command processing component configured to modify a data element based on the write commit command, determine whether the majority of the plurality of storage nodes have replicated the modification using the committed snapshot, and generate the write commit confirmation responsive to a determination that the majority of the plurality of data storage nodes have replicated the modification.

Claims

1. A database system comprising:

at least one processor configured to execute a plurality of system components, wherein the plurality of system components comprise;

an interface component configured to receive a write commit command and provide a write commit confirmation;

a snapshot component configured to generate a plurality of snapshots of data stored in a first data storage node of a plurality of data storage nodes and identify a first snapshot from the plurality of snapshots that is representative of data that has been replicated on a majority of the plurality of data storage nodes as a committed snapshot; and

a command processing component configured to;

determine whether the write commit command modifies at least one data element in the first data storage node; and

responsive to the write commit command modifying the at least one data element in the first data storage node,

modify the at least one data element in the first data storage node based on the write commit command;

determine whether the majority of the plurality of storage nodes have replicated the modification to the at least one data element using the committed snapshot; and

generate the write commit confirmation responsive to a determination that the majority of the plurality of data storage nodes have replicated the modification to the at least one data element;

wherein;

the interface component is further configured to receive a confirmation from a second data storage node of the plurality of data storage nodes that the second data storage node has replicated the modification to the at least one data element; and

the snapshot component is further configured to;

identify a second snapshot from the plurality of snapshots as the committed snapshot responsive to receipt of the confirmation from the second data storage node; and

remove the first snapshot from the plurality of snapshots responsive to identifying the second snapshot as the committed snapshot.

2. The system of claim 1, wherein the command processing component is further configured to generate the write commit confirmation responsive to the write commit command not modifying the at least one data element in the first data storage node.

3. The system of claim 1, wherein the command processing component is further configured to send a command to at least one data storage node in the plurality of data storage nodes to replicate the modification of the at least one data element in the first data storage node responsive to modifying the at least one data element in the first data storage node.

4. The system of claim 1, wherein the first data storage node stores an operation log comprising a plurality of database operations performed on the first data storage node and wherein the command processing component is further configured to determine whether at least one entry in the operation log has been replicated by the majority of data storage nodes in the plurality of data storage nodes using the committed snapshot responsive to the write commit command not modifying the at least one data element in the first data storage node.

5. The system of claim 4, wherein the command processing component is further configured to generate the write commit confirmation responsive to a determination that the majority of the plurality of data storage nodes replicated the at least one entry in the operation log.

6. The system of claim 4, wherein the at least one entry in the operation log comprises a newest entry in the operation log that occurred before receipt of the write commit command.

7. The system of claim 1, wherein the interface component is further configured to receive a write command and wherein the command processing component is further configured to write data to the first data storage node responsive to receipt of the write command.

8. The system of claim 1, further comprising a database including the plurality of data storage nodes and wherein the database follows an eventual consistency model.

9. The system of claim 8, wherein the first data storage node is a primary data storage node and a remainder of the data storage nodes of the plurality of data storage nodes are secondary data storage nodes.

10. The system of claim 8, wherein the first data storage node includes an operation log and a remainder of the data storage nodes of the plurality of data storage nodes are configured to retrieve the operation log and replicate operations in the operation log.

11. A method of performing operations in a computer database, comprising:

generating, by a snapshot component executed by at least one processor, a plurality of snapshots of data stored in a first data storage node of a plurality of data storage nodes;

identifying, by the snapshot component executed by the at least one processor, a first snapshot from the plurality of snapshots that is representative of data that has been replicated on a majority of the plurality of data storage nodes as a committed snapshot;

receiving, by an interface component executed by the at least one processor, a write commit command;

determining, by a command processing component executed by the at least one processor, whether the write commit command modifies at least one data element in the first data storage node;

responsive to the write commit command modifying the at least one data element in the first data storage node,

modifying the at least one data element in the first data storage node based on the write commit command;

determining whether the majority of the plurality of storage nodes have replicated the modification to the at least one data element using the committed snapshot; and

generating a write commit confirmation responsive to a determination that the majority of the plurality of data storage nodes have replicated the modification to the at least one data element;

providing, by the interface component, the write commit confirmation;

receiving, by the interface component, a confirmation from a second data storage node of the plurality of data storage nodes that the second data storage node has replicated the modification to the at least one data element;

identifying, by the snapshot component, a second snapshot from the plurality of snapshots as the committed snapshot responsive to receipt of the confirmation from the second data storage node; and

removing, by the snapshot component, the first snapshot from the plurality of snapshots responsive to identifying the second snapshot as the committed snapshot.

12. The method of claim 11, further comprising generating the write commit confirmation responsive to the write commit command not modifying the at least one data element in the first data storage node.

13. The method of claim 11, wherein the first data storage node stores an operation log comprising a plurality of operations performed on the first data storage node and wherein the method further comprises determining whether at least one entry in the operation log has been replicated by the majority of data storage nodes in the plurality of data storage nodes using the committed snapshot responsive to the write commit command not modifying the at least one data element in the first data storage node.

14. The method of claim 13, further comprising generating the write commit confirmation responsive to a determination that the majority of the plurality of data storage nodes replicated the at least one entry in the operation log.

15. A database system comprising:

a database configured to follow an eventual consistency model and comprising a primary data storage node storing an operation log and a plurality of secondary data storage nodes configured to retrieve the operation log from the primary data storage node and replicate operations in the operation log; and

at least one processor configured to execute a plurality of system components, wherein the plurality of system components comprise;

an interface component configured to receive a write commit command and provide a write commit confirmation;

a snapshot component configured to generate a plurality of snapshots of data stored in the primary data storage node, identify a first snapshot from the plurality of snapshots that is representative of data that has been replicated on a majority of the plurality of secondary data storage nodes as a committed snapshot; and

a command processing component configured to;

determine whether the write commit command modifies at least one document in the primary data storage node; and

responsive to the write commit command modifying the at least one document in the primary data storage node,

modify the at least one document in the primary data storage node;

determine whether the majority of the secondary storage nodes have replicated the modification to the at least one document in the primary data storage node using the committed snapshot; and

generate the write commit confirmation responsive to a determination that the majority of the secondary storage nodes replicated the modification to the at least one document;

wherein;

the interface component is further configured to receive a confirmation from a data storage node of the plurality of secondary data storage nodes that the data storage node has replicated the modification to the at least one document; and

the snapshot component is further configured to;

identify a second snapshot from the plurality of snapshots as the committed snapshot responsive to receipt of the confirmation from the data storage node; and

remove the first snapshot from the plurality of snapshots responsive to identifying the second snapshot as the committed snapshot.