Consistent deduplicated snapshot generation for a distributed database using optimistic deduplication

• US 10,706,070 B2
• Filed: 09/09/2016
• Issued: 07/07/2020
• Est. Priority Date: 09/09/2015
• Status: Active Grant

• Current Assignee: Rubrik, Inc.
• Original Assignee: Rubrik, Inc.
• Inventors: Kim, Hyo Jun, Lu, Maohua, Sarkar, Prasenjit, Zhou, Pin, Raghavan, Ajaykrishna
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/260,491
• Publication Number:
  US 20170068685A1
• Time in Patent Office: 1,397 Days
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• 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 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

Embodiments disclosed herein provide systems, methods, and computer readable media for generating a consistent deduplicated snapshot of a distributed database using optimistic deduplication. In a particular embodiment, a method provides, for each node of a plurality of nodes in the distributed database, deduplicating data items stored on the node that are owned by the node and generating a summary that describes a file in which the data items are located. The method further provides identifying from the summaries for each of the nodes whether mistakes occurred during deduplication and, upon identifying one or more mistakes, determining one or more corrections for the one or more mistakes. Also, the method provides generating a consistent deduplicated snapshot for the distributed database comprising the deduplicated data items from each node and the one or more corrections.

Claims

1. A method of generating a consistent deduplicated snapshot of a distributed database using optimistic deduplication, the method comprising:

for each node of a plurality of nodes in the distributed database,

deduplicating data items that are identified as being stored on the node and owned by the node, and

generating a summary for the node, the summary describing a file in which the data items that are identified as being stored on the node are located;

identifying from the summaries for each of the nodes whether one or more mistakes occurred during deduplication;

upon identifying the one or more mistakes, determining one or more corrections for the one or more mistakes; and

generating a consistent deduplicated snapshot for the distributed database comprising the deduplicated data items from each node and the one or more corrections.

2. The method of claim 1, wherein identifying the one or more mistakes comprises:

determining a quorum indicating a minimum amount of the plurality of nodes on which a particular data item is stored; and

using the summaries to determine whether data items of the plurality of data items meet the quorum.

3. The method of claim 2, wherein identifying the one or more mistakes further comprises:

for particular data items that do not meet the quorum, identifying the particular data items for inclusion in the one or more mistakes.

4. The method of claim 3, wherein determining the one or more corrections comprises:

for the particular data items, determining that the particular data items should be excluded from the deduplicated data items and creating a correction to exclude the particular data item from the deduplicated data items.

5. The method of claim 2, wherein identifying the one or more mistakes further comprises:

for particular data items that do meet the quorum and are not included in the deduplicated data items from each node, identifying the particular data items for inclusion in the one or more mistakes.

6. The method of claim 5, wherein determining the one or more corrections comprises:

for the particular data items, determining that the particular data items should be included in the deduplicated data items and creating a correction to include the particular data item in the deduplicated data items.

7. The method of claim 1, wherein generating the consistent deduplicated snapshot comprises:

applying the one or more corrections to the deduplicated data items before storing the consistent deduplicated snapshot.

8. The method of claim 1, wherein generating the consistent deduplicated snapshot comprises:

storing the one or more corrections in association with the deduplicated data items, wherein the one or more corrections are made to the deduplicated data items upon restoration to the deduplicated snapshot.

9. The method of claim 1, further comprising:

storing the consistent deduplicated snapshot to a version storage repository.

10. A system for generating a consistent deduplicated snapshot of a distributed database using optimistic deduplication, the system comprising:

one or more computer readable storage media;

a processing system operatively coupled with the one or more computer readable storage media; and

program instructions stored on the one or more computer readable storage media that, when read and executed by the processing system, direct the processing system to perform operations comprising;

for each node of a plurality of nodes in the distributed database,

deduplicating data items that are identified as being stored on the node and owned by the node and

generating a summary for the node, the summary describing a file in which the data items that are identified as being stored on the node are located;

identifying from the summaries for each of the nodes whether one or more mistakes occurred during deduplication;

upon identifying the one or more mistakes, determining one or more corrections for the one or more mistakes; and

generating a consistent deduplicated snapshot for the distributed database comprising the deduplicated data items from each node and the one or more corrections.

11. The system of claim 10, wherein the identifying the one or more mistakes includes the program instructions directing the processing system to perform operations comprising:

determining a quorum indicating a minimum amount of the plurality of nodes on which a particular data item is stored; and

determining whether data items of the plurality of data items meet the quorum based on the summaries.

12. The system of claim 11, wherein the identifying the one or more mistakes includes the program instructions further directing the processing system to perform operations comprising:

for particular data items that do not meet the quorum, identifying the particular data items for inclusion in the one or more mistakes.

13. The system of claim 12, wherein the determining the one or more corrections includes the program instructions directing the processing system to perform operations comprising:

for the particular data items, determining that the particular data items should be excluded from the deduplicated data items and creating a correction to exclude the particular data item from the deduplicated data items.

14. The system of claim 11, wherein the identifying the one or more mistakes includes the program instructions directing the processing system to perform operations comprising:

for particular data items that do meet the quorum and are not included in the deduplicated data items from each node, identifying the particular data items for inclusion in the one or more mistakes.

15. The system of claim 14, wherein the determining the one or more corrections includes the program instructions directing the processing system to perform operations comprising:

for the particular data items, determining that the particular data items should be included in the deduplicated data items and creating a correction to include each of the particular data items in the deduplicated data items.

16. The system of claim 10, wherein the generating the consistent deduplicated snapshot includes the program instructions directing the processing system to perform operations comprising:

applying the one or more corrections to the deduplicated data items before storing the consistent deduplicated snapshot.

17. The system of claim 10, wherein the generating the consistent deduplicated snapshot includes the program instructions directing the processing system to perform operations comprising:

storing the one or more corrections in association with the deduplicated data items, wherein the one or more corrections are made to the deduplicated data items upon restoration to the deduplicated snapshot.

18. The system of claim 10, wherein the program instructions further direct the processing system to perform operations comprising:

storing the consistent deduplicated snapshot to a version storage repository.