SYSTEM AND METHOD FOR BUILDING A POINT-IN-TIME SNAPSHOT OF AN EVENTUALLY-CONSISTENT DATA STORE

• US 20130218840A1
• Filed: 02/17/2012
• Published: 08/22/2013
• Est. Priority Date: 02/17/2012
• Status: Active Grant

• Current Assignee: Netflix, Inc.
• Original Assignee: Charles Smith
• Inventors: Anand, Siddharth, SMITH, Charles, Magnusson, Jeffrey
• Granted Patent: US 9,613,104 B2
• Time in Patent Office: Days
• US Class Current: 707/639
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A method and system for building a point-in-time snapshot of an eventually-consistent data store. The data store includes key-value pairs stored on a plurality of storage nodes. In one embodiment, the data store is implemented as an Apache® Cassandra database running in the “cloud.” The data store includes a journaling mechanism that stores journals (i.e., inconsistent snapshots) of the data store on each node at various intervals. In Cassandra, these snapshots are sorted string tables that may be copied to a back-up storage location. A cluster of processing nodes may retrieve and resolve the inconsistent snapshots to generate a point-in-time snapshot of the data store corresponding to a lagging consistency point. In addition, the point-in-time snapshot may be updated as any new inconsistent snapshots are generated by the data store such that the lagging consistency point associated with the updated point-in-time snapshot is more recent.

Claims

1. A computer-implemented method for building a point-in-time snapshot of an eventually-consistent data store distributed among a plurality of nodes connected by a network, the method comprising:

receiving a plurality of inconsistent snapshots, wherein each inconsistent snapshot includes one or more rows of key-value pairs associated with the data store and reflects the contents of at least a portion of the data store stored on a particular node of the plurality of nodes; and

generating the point-in-time snapshot by resolving the rows of key-value pairs to remove any inconsistent values, wherein the point-in-time snapshot includes a subset of the key-value pairs included in the plurality of inconsistent snapshots.

2. The computer-implemented method of claim 1, wherein generating the point-in-time snapshot comprises:

dividing the rows of key-value pairs from the plurality of inconsistent snapshots into one or more processing tasks, wherein each processing task includes a different portion of the key-value pairs;

distributing each processing task to one of a plurality of processing nodes configured to perform a reduce operation;

receiving a number of results from the plurality of processing nodes corresponding to the number of distributed processing tasks; and

combining the number of results to generate the point-in-time snapshot.

3. The computer-implemented method of claim 2, wherein the rows of key-value pairs include a key value and one or more columns associated with the key value, each column being associated with a column identifier, a corresponding column value, and a timestamp value that represents a particular time at which the column was added to the data store.

4. The computer-implemented method of claim 3, wherein the reduce operation comprises performing a compaction operation configured to remove duplicate rows of key-value pairs from the processing task and generate a single row associated with each unique key value included in the processing task, wherein the single row includes one or more columns associated with the unique key value, each column in the single row being associated with a unique column identifier for that single row selected from the column in the processing task associated with the unique key value and unique column identifier as well as the most recent timestamp value.

5. The computer-implemented method of claim 2, wherein the plurality of processing nodes is implemented via the Apache®

Hadoop application framework.

6. The computer-implemented method of claim 2, wherein the data store is implemented via the Apache®

Cassandra database, which is configured to automatically generate the inconsistent snapshots at periodic intervals, and wherein each inconsistent snapshot comprises a sorted string table (SSTable).

7. The computer-implemented method of claim 1, further comprising converting the point-in-time snapshot to a JavaScript Object Notation (JSON) format.

8. The computer-implemented method of claim 1, further comprising:

receiving one or more additional inconsistent snapshots generated by the data store subsequent to generating the point-in-time snapshot; and

generating an updated point-in-time snapshot by resolving the rows of key-value pairs in the one or more additional inconsistent snapshots as well as the point-in-time snapshot to remove any inconsistent values.

9. A system for building a point-in-time snapshot of an eventually-consistent data store, comprising:

a plurality of nodes connected by a network and storing the data store; and

a processing node connected to the data store via the network and configured to;

receive a plurality of inconsistent snapshots, wherein each inconsistent snapshot includes one or more rows of key-value pairs associated with the data store and reflects the contents of at least a portion of the data store stored on a particular node of the plurality of nodes, and

generate the point-in-time snapshot by resolving the rows of key-value pairs to remove any inconsistent values, wherein the point-in-time snapshot includes a subset of the key-value pairs included in the plurality of inconsistent snapshots.

10. The system of claim 9, wherein generating the point-in-time snapshot comprises:

dividing the rows of key-value pairs from the plurality of inconsistent snapshots into one or more processing tasks, wherein each processing task includes a different portion of the key-value pairs;

distributing each processing task to one of a plurality of processing nodes configured to perform a reduce operation;

receiving a number of results from the plurality of processing nodes corresponding to the number of distributed processing tasks; and

combining the number of results to generate the point-in-time snapshot.

11. The system of claim 10, wherein the rows of key-value pairs include a key value and one or more columns associated with the key value, each column being associated with a column identifier, a corresponding column value, and a timestamp value that represents a particular time at which the column was added to the data store.

12. The system of claim 11, wherein the reduce operation comprises performing a compaction operation configured to remove duplicate rows of key-value pairs from the processing task and generate a single row associated with each unique key value included in the processing task, wherein the single row includes one or more columns associated with the unique key value, each column in the single row being associated with a unique column identifier for that single row selected from the column in the processing task associated with the unique key value and unique column identifier as well as the most recent timestamp value.

13. The system of claim 10, wherein the plurality of processing nodes is implemented via an Apache®

Hadoop application framework.

14. The system of claim 10, wherein the data store is implemented via an Apache®

Cassandra database, which is configured to automatically generate the inconsistent snapshots at periodic intervals, and wherein each inconsistent snapshot comprises a sorted string table (SSTable).

15. The system of claim 9, wherein the processing node is further configured to convert the point-in-time snapshot to a JavaScript Object Notation (JSON) format.

16. The system of claim 9, wherein the processing node is further configured to:

receive one or more additional inconsistent snapshots generated by the data store subsequent to generating the point-in-time snapshot;

generate an updated sorted table that includes each of the rows of key-value pairs from the one or more additional inconsistent snapshots and the point-in-time snapshot; and

generate an updated point-in-time snapshot by resolving the rows of key-value pairs in the updated sorted table to remove any inconsistent values.

17. A computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to perform an operation for building a point-in-time snapshot of an eventually-consistent data store, the operation comprising:

receiving a plurality of inconsistent snapshots, wherein each inconsistent snapshot includes one or more rows of key-value pairs associated with the data store and reflects the contents of at least a portion of the data store stored on a particular node of the plurality of nodes;

generating a sorted table including each row of key-value pairs from the plurality of inconsistent snapshots; and

generating the point-in-time snapshot by resolving the rows of key-value pairs in the sorted table to remove any inconsistent values, wherein the point-in-time snapshot includes a subset of the rows of key-value pairs included in the sorted table such that each unique key is associated with a single row that is selected from all rows in the sorted table associated with that particular key.

18. The computer-readable storage medium of claim 17, wherein generating the point-in-time snapshot comprises:

dividing the sorted table into one or more processing tasks, wherein each processing task includes a different portion of the rows of key-value pairs within the sorted table;

distributing each processing task to one of a plurality of processing nodes configured to perform a map operation;

receiving a number of results from the plurality of processing nodes corresponding to the number of distributed processing tasks; and

performing a reduce operation on the number of results to generate the point-in-time snapshot.

19. The computer-readable storage medium of claim 18, wherein the rows of key-value pairs include a key value and one or more columns associated with the key value, each column being associated with a column identifier, a corresponding column value, and a timestamp value that represents a particular time at which the column was added to the data store.

20. The computer-readable storage medium of claim 19, wherein the reduce operation comprises performing a compaction operation configured to remove duplicate rows of key-value pairs from the processing task and generate a single row associated with each unique key value included in the processing task, wherein the single row includes one or more columns associated with the unique key value, each column in the single row being associated with a unique column identifier for that single row selected from the column in the processing task associated with the unique key value and unique column identifier as well as the most recent timestamp value.