Infinite versioning by automatic coalescing

Patent metadata

Field	Value
Publication number	US-10303667-B2
Application number	US-201615006256-A
Country	US
Kind code	B2
Filing date	Jan 26, 2016
Priority date	Jan 26, 2015
Publication date	May 28, 2019
Grant date	May 28, 2019

Abstract

Embodiments disclosed herein provide systems, methods, and computer readable media for infinite versioning by automatic coalescing. In a particular embodiment, a method provides determining an age range for a plurality of data versions stored in a secondary data repository and identifying first data versions of the plurality of data versions that are within the age range. The method further provides determining a compaction ratio for the first data versions and compacting the first data versions based on the compaction ratio.

First claim

What is claimed is:

1. A method of infinitely versioning data by automatic coalescing, the method comprising: determining one or more age ranges for a plurality of data versions stored in a secondary data repository, wherein the one or more age ranges are determined based on a capacity of the secondary data repository relative to the plurality of data versions stored in the secondary data repository, each data version storing a set of changes made to a set of data items since a previous data version; for a first age range of the one or more age ranges:
determining first data versions of the plurality of data versions that are within the first age range;
determining a first compaction ratio defining a number of data versions to be compacted into one single data version based on the first age range;
compacting the first data versions to one or more first compacted data versions, each first compacted data version including non-overwritten changes included in the number of data versions of the first data versions;
storing the one or more first compacted data versions; and removing the first data versions.

2. The method of claim 1 , wherein compacting the first data versions to one or more first compacted data versions comprises generating a list of logical block address ranges for the one or more first compacted data versions, each logical block address mapping to a physical location in the secondary data repository.

3. The method of claim 1 , wherein compacting the first data versions based on the first compaction ratio comprises:
grouping the first data versions into one or more sequential data version groups each including the number of data versions of the first data versions; and
for each sequential data version group: removing overwritten changes of the number of data versions.

4. The method of claim 1 , further comprising determining a second compaction ratio for a second age range of the one or more age ranges, wherein the second age range is older than the first age range and the second compaction ratio is greater than the first compaction ratio.

5. The method of claim 1 , wherein the data items are stored in a primary data repository separate from the secondary data repository.

6. The method of claim 1 , further comprising determining second data versions that are within a second age range, wherein the second age range is older than the first age range and the second data versions are more than the first data versions.

7. A non-transitory computer readable storage medium having instructions stored thereon for infinitely versioning data by automatic coalescing, the instructions, when executed by a data compaction system, direct the data compaction system to: determine one or more age ranges for a plurality of data versions stored in a secondary data repository, wherein the one or more age ranges are determined based on a capacity of the secondary data repository relative to the plurality of data versions stored in the secondary data repository, each data version storing a set of changes made to a set of data items since a previous data version; for a first age range of the one or more age ranges: determine first data versions of the plurality of data versions that are within the first age range; determine a first compaction ratio defining a number of data versions to be compacted into one single data version based on the first age range; compact the first data versions to one or more first compacted data versions, each first compacted data version including non-overwritten changes included in the number of data versions of the first data versions; store the one or more first compacted data versions; and remove the first data versions.

8. The non-transitory computer readable storage medium of claim 7 , wherein the instructions configured to direct the data compaction system to compact the first data versions to one or more first compacted data versions comprise instructions configured to cause the data compaction system to generate a list of logical block address ranges for the one or more first compacted data versions, each logical block address mapping to a physical location in the secondary data repository.

9. The non-transitory computer readable storage medium of claim 7 , wherein the instructions that direct the data compaction system to compact the first data versions based on the first compaction ratio comprise instructions that direct the data compaction system to:
group the first data versions into one or more sequential data version groups each including the number of data versions of the first data versions; and
for each sequential data version group: remove overwritten changes of the number of data versions.

10. The non-transitory computer readable storage medium of claim 7 , wherein the instructions are further configured to direct the data compaction system to determine a second compaction ratio for a second age range of the one or more age ranges, and wherein the second age range is older than the first age range and the second compaction ratio is greater than the first compaction ratio.

11. The non-transitory computer readable storage medium of claim 7 , wherein the data items are stored in a primary data repository separate from the secondary data repository.

12. The non-transitory computer readable storage medium of claim 7 , wherein the instructions are further configured to direct the data compaction system to determine second data versions that are within a second age range, and wherein the second age range is older than the first age range and the second data versions are more than the first data versions.

13. A data compaction system for infinitely versioning data by automatic coalescing, the data compaction system comprising: a computer processor; and one or more non-transitory computer readable storage media storing program instructions to be executed by the computer processor and configured to cause the computer processor to: determine one or more age ranges for a plurality of data versions stored in a secondary data repository, wherein the one or more age ranges are determined based on a capacity of the secondary data repository relative to the plurality of data versions stored in the secondary data repository, each data version storing a set of changes made to a set of data items since a previous data version; for a first age range of the one or more age ranges: determine first data versions of the plurality of data versions that are within the first age range; determine a first compaction ratio defining a number of data versions to be compacted into one single data version based on the first age range; compact the first data versions to one or more first compacted data versions, each first compacted data version including non-overwritten changes included in the number of data versions of the first data versions; store the one or more first compacted data versions; and remove the first data versions.

14. The data compaction system of claim 13 , wherein the program instructions configured to cause the processor to compact the first data versions to one or more first compacted data versions comprise program instructions configured to cause the processor to generate a list of logical block address ranges for the one or more first compacted data versions, each logical block address mapping to a physical location in the secondary data repository.

15. The data compaction system of claim 13 , wherein the program instructions configured to cause the processor to compact the first data versions based on the compaction ratio include program instructions configured to cause the processor to:
group the first

Assignees

• Rubrik Inc

Inventors

• Thakur Tarun
• Zhou Pin
• Sarkar Prasenjit

Classifications

• G06F16/219 Primary

  Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477) · CPC title