Method and system for efficient space management for single-instance-storage volumes
A method and system for efficient space management for single-instance-storage volumes is provided. A backup module storing data within a collection of containers according to access locality and retention time of the data, wherein the retention time defines an amount of time the data is stored within the collection of containers before deletion of the data, and the access locality comprises an order in which the data is to be accessed is further provided. A compaction module compacting the stored data by selecting at least two containers among the collection of containers, wherein the selection is performed using a predetermined criteria that includes access locality and retention time of the data is also provided. The compaction module distributes the data among the at least two containers. The compaction criteria creates an imbalance among the containers to create more empty, full, or nearly full containers.
1. A method comprising:
selecting, using one or more processors, at least two containers of a plurality of containers, wherein
the plurality of containers store a plurality of data segments,
the plurality of data segments are distributed among the plurality of containers such that each of the plurality of containers stores one or more data segments of the plurality of data segments,
the selecting is based, at least in part, on a criterion,
the criterion indicates access locality of the each of the plurality of data segments,
the plurality of data segments are configured to be accessed in a sequence, and
the access locality of each of the plurality of data segments comprises a probability that, when accessed in the sequence, the each of the plurality of data segments will be accessed together with at least another of the plurality of data segments; and
reallocating the plurality of data segments among the plurality of containers,
wherein
the reallocating comprises
moving at least one of the plurality of data segments from a first container of the at least two containers to a second container of the at least two containers.
2. The method of claim 1 , wherein
the criterion further indicates
a retention time for each of the plurality of data segments, and
the retention time defines an amount of time the each of the plurality of data segments is to be stored in the plurality of containers before the each of the plurality of data segments is to be deleted from the plurality of containers.
3. The method of claim 1 , wherein
the plurality of data segments are distributed among the plurality of containers such that a gap exists within at least one of the plurality of containers,
the gap is between a first data segment of the plurality of segments and a second data segment of the plurality of segments stored in the at least one of the plurality of containers, and
the reallocating operates to remove the gap.
4. The method of claim 1 , wherein after the reallocating,
the first container does not comprise any of the plurality of data segments.
5. The method of claim 1 , wherein prior to the reallocating,
the first container comprises a first amount of allocated space occupied by a first subset of the plurality of data segments and a first amount of allocated space not occupied by the first subset of the plurality of data segments;
the second container comprises a second amount of allocated space not occupied by a second subset of the plurality of data segments; and
the plurality of data segments comprises
the first subset and the second subset of the plurality of data segments.
6. The method of claim 5 , wherein prior to the reallocating,
the second amount of allocated space not occupied by the second subset of the plurality of data segments is greater than or equal to the first amount of allocated space occupied by the first subset of the plurality of data segments.
7. The method of claim 5 , wherein
the moving the at least one of the plurality of data segments from the first container to the second container comprises
moving the at least one of the plurality of data segments from the first amount of allocated space occupied by the first subset to the second amount of allocated space not occupied by the second subset.
8. The method of claim 1 , wherein
the plurality of data segments comprises
a first data segment, and
a second data segment,
the first and second data segments are stored in at least one of the plurality of containers,
the first data segment is received from a first data source,
the second data segment is received from a second data source,
a first metadata is associated with the first data segment,
a second metadata is associated with the second data segment, and
the first metadata references the second data segment to indicate that the second data segment is dependent on the first data segment.
9. The method of claim 8 , wherein
the first metadata identifies the first data source, and
the second metadata identifies the second data source.
10. The method of claim 8 , further comprising:
determining whether the retention time for the first data segment is expired, and
determining whether the first metadata comprises a reference to another data segment,
wherein, in response to determining that
the retention time for the first stored segment is expired, and
the first metadata references the second data segment,
the first data segment is not deleted.
11. A non-transitory computer program product comprising:
a plurality of instructions, comprising:
a first set of instructions, executable on a computer system, configured to select at least two containers of a plurality of containers, wherein
the plurality of containers a plurality of data segments,
the plurality of data segments are distributed among the plurality of containers such that each of the plurality of containers stores one or more data segments of the plurality of data segments,
the selection is based, at least in part on, a criterion,
the criterion indicates access locality of the each of the plurality of data segments,
the plurality of data segments are configured to be accessed in a sequence, and
the access locality of each of the plurality of data segments comprises a probability that, when accessed in the sequence, the each of the plurality of data segments will be accessed together with at least another of the plurality of data segments, and
a second set of instructions, executable on a computer system, configured to reallocate the plurality of data segments among plurality of containers,
wherein
the reallocation comprises
moving at least one of the plurality of data segments from a first container of the at least two containers to a second container of the at least two containers; and
a computer-readable storage medium, wherein the plurality of instructions are encoded in the computer-readable storage medium.
12. The non-transitory computer program product of claim 11 , wherein
the criterion further indicates
a retention time for each of the plurality of data segments, and
the retention time defines an amount of time the each of the plurality of data segments is to be stored in the plurality of containers before the each of the plurality of data segments is to be deleted from the plurality of containers.
13. The non-transitory computer program product of claim 11 , wherein
the plurality of data segments are distributed among the plurality of containers such that a gap exists within at least one of the plurality of containers,
the gap is between a first data segment of the plurality of segments and a second data segment of the plurality of segments stored in the at least one of the plurality of containers, and
the reallocation operates to remove the gap.
14. The non-transitory computer program product of claim 11 , wherein
after the reallocation, the first container does not comprise any of the plurality of data segments.
15. The non-transitory computer program product of claim 11 , wherein
the plurality of data segments comprises
a first data segment, and
a second data segment,
the first and second data segments are stored in at least one of the plurality of containers,
the first data segment is received from a first data source,
the second data segment is received from a second data source,
a first metadata is associated with the first data segment,
a second metadata is associated with the second data segment, and
the first metadata references the second data segment to indicate that the second data segment is dependent on the first data segment.
16. A system comprising:
one or more processors;
a storage, wherein
the storage stores a plurality of containers,
the plurality of containers store a plurality of data segments, and
the plurality of data segments are distributed among the plurality of containers such that each of the plurality of containers stores one or more data segments of the plurality of data segments; and
a compaction module executable by the one or more processors to:
select at least two containers of a plurality of containers, wherein
the compaction module performs the selection based, at least in part, on a criterion,
the criterion indicates access locality of the each of the plurality of data segments,
the plurality of data segments are configured to be accessed in a sequence, and
the access locality of each of the plurality of data segments comprises a probability that, when accessed in the sequence, the each of the plurality of data segments will be accessed together with at least another of the plurality of data segments, and
reallocate the plurality of data segments among plurality of containers, wherein
the compaction module performs the reallocation by moving at least one of the plurality of data segments from a first container of the at least two containers to a second container of the at least two containers.
17. The system of claim 16 , wherein
the criterion further indicates
a retention time for each of the plurality of data segments, and
the retention time defines an amount of time the each of the plurality of data segments is to be stored in the plurality of containers before the each of the plurality of data segments is to be deleted from the plurality of containers.
18. The system of claim 16 , wherein
the plurality of data segments are distributed among the plurality of containers such that a gap exists within at least one of the plurality of containers,
the gap is between a first data segment of the plurality of segments and a second data segment of the plurality of segments stored in the at least one of the plurality of containers, and
the reallocation operates to remove the gap.
19. The system of claim 16 , wherein
after the compaction module performs the reallocation, the first container does not comprise any of the plurality of data segments.
20. The system of claim 16 , wherein
the plurality of data segments comprises
a first data segment, and
a second data segment,
the first and second data segments are stored in at least one of the plurality of containers,
the first data segment is received from a first data source,
the second data segment is received from a second data source,
a first metadata is associated with the first data segment,
a second metadata is associated with the second data segment, and
the first metadata references the second data segment to indicate that the second data segment is dependent on the first data segment.