Method and apparatus for reading and writing committed data

• US 10,698,775 B2
• Filed: 05/25/2017
• Issued: 06/30/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): Pham, Hung Q
• Application Number:
  US15/605,141
• Publication Number:
  US 20170344290A1
• Time in Patent Office: 1,132 Days
• 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 is provided. The database system may include at least one processor configured to execute a plurality of system components. The plurality of system components may include an interface component configured to receive a read commit command and provide a result, 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 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 read the committed snapshot responsive to receipt of the read commit command and generate the result.

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 read commit command and provide a result;

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, wherein the first data storage node includes an operation log and a remainder of the plurality of data storage nodes are configured to retrieve the operation log and replicate operations in the operation log;

determine, based on responses from the plurality of the data storage nodes, a commit point in the operation log indicative of a latest committed operation in the operation log that has been performed by a majority of the plurality of the data storage nodes; and

determine, based on the commit point, a committed snapshot from the plurality of snapshots, wherein the committed snapshot is representative of committed operations that have been replicated on the majority of the plurality of data storage nodes, and the committed snapshot is a most recent snapshot of the plurality of snapshots that is associated with the latest committed operation; and

a command processing component configured to read the committed snapshot responsive to receipt of the read commit command and generate the result using the committed snapshot.

2. The system of claim 1, wherein each snapshot of the plurality of snapshots corresponds to data stored in the first storage node at a unique point in time.

3. The system of claim 1, wherein the interface component is further configured to receive at least one confirmation from at least one data storage node of the plurality of data storage nodes that the at least one data storage node has replicated one or more operations in the operation log.

4. The system of claim 3, wherein the snapshot component is further configured to identify a new committed snapshot responsive to receipt of the at least one confirmation from the at least one data storage node.

5. The system of claim 3, wherein the snapshot component is further configured to remove at least one snapshot from the plurality of snapshots responsive to receipt of the at least one confirmation from the at least one data storage node.

6. The system of claim 1, wherein the snapshot component is further configured to generate a new snapshot of the data stored in the first data storage node periodically.

7. The system of claim 1, wherein the snapshot component is further configured to periodically generate a new snapshot of the data stored in the first data storage node every 10 milliseconds.

8. The system of claim 1, wherein the interface component is further configured to receive a read command.

9. The system of claim 8, wherein the command processing component is further configured to read data stored in a second data storage node of the plurality of data storage nodes responsive to receiving the read command.

10. The system of claim 1, wherein the command processing component is configured to read the committed snapshot at least in part by identifying a data storage node from the plurality of data storage nodes that stores data consistent with committed snapshot and reading from the identified data storage node.

11. 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.

12. The system of claim 11, 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.

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

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

generating, by a snapshot component executed by the at least one processor, a plurality of snapshots of data stored in a first data storage node of a plurality of data storage nodes, wherein the first data storage node includes an operation log and a remainder of the plurality of data storage nodes are configured to retrieve the operation log and replicate operations in the operation log;

determining, based on responses from the plurality of the data storage nodes, a commit point in the operation log indicative of a latest committed operation in the operation log that has been performed by a majority of the plurality of the data storage nodes;

determining, by the snapshot component executed by the at least one processor, based on the commit point, a committed snapshot from the plurality of snapshots, wherein the committed snapshot is representative of committed operations that have been replicated on the majority of the plurality of data storage nodes, and the committed snapshot is a most recent snapshot of the plurality of snapshots that is associated with the latest committed operation;

reading, by a command processing component executed by the at least one processor, the committed snapshot responsive to receipt of the read commit command;

generating, by the command processing component, a result to the read commit command using the committed snapshot; and

providing, by the interface component, the result.

14. The method of claim 13, wherein each snapshot of the plurality of snapshots corresponds to the data stored in the first storage node of the plurality of data storage nodes at unique point in time.

15. The method of claim 13, further comprising receiving at least one confirmation from at least one data storage node of the plurality of data storage nodes that the at least one data storage node has replicated one or more operations in the operation log.

16. The method of claim 15, further comprising identifying a new committed snapshot from the plurality of snapshots responsive to receipt of the at least one confirmation from the at least one data storage node.

17. The method of claim 15, further comprising removing at least one snapshot from the plurality of snapshots responsive to receipt of the at least one confirmation from the at least one data storage node.

18. The method of claim 13, further comprising generating new snapshots of the data stored in the first data storage node periodically.

19. 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 coupled to the database and configured to execute a plurality of system components, wherein the plurality of system components comprise;

an interface component configured to receive a read commit command and provide a result;

a snapshot component configured to;

generate a plurality of snapshots of data stored in the primary data storage node where each snapshot corresponds to data stored in the first storage node at a unique point in time;

determine, based on responses from the plurality of secondary data storage nodes, a commit point in the operation log indicative of a latest committed operation in the operation log that has been performed by a majority of the secondary data storage nodes; and

determine, based on the commit point, a committed snapshot from the plurality of snapshots, wherein the committed snapshot is representative of committed operations that have been replicated on the majority of the plurality of secondary data storage nodes, and the committed snapshot is a most recent snapshot of the plurality of snapshots that is associated with the latest committed operation; and

a command processing component configured to read the committed snapshot responsive to receipt of the read commit command and generate the result using the committed snapshot.