Granted Patent B2

US 11,157,187 · App. 16/885,788 · Granted Oct 26, 2021

Inventors: Leihu Zhang (Beijing, CN); Chen Gong (Beijing, CN)

Assignee: EMC IP Holding Company LLC

G06F3/064G06F3/0608G06F3/0613G06F3/0653G06F3/0659G06F3/0673

Abstract

Claims (79)

1. A method for overwriting data, comprising:

comparing, based on a request for overwriting target data in a storage area to cover original data, a first compression ratio of the target data with a second compression ratio of the original data;

in accordance with a determination that the first compression ratio is larger than the second compression ratio, compressing the target data into a plurality of data fragments at the first compression ratio;

storing the plurality of data fragments in a plurality of overwriting segments in the storage area, the plurality of overwriting segments being previously used for storing corresponding fragments of the original data; and

storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments,

wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments comprises:

(1) determining candidate padding segments of the storage area;

(2) determining, from the determined candidate padding segments, the at least one free segment and the free sectors based on locations of sectors storing the plurality of data fragments in the overwriting segments; and

(3) storing the padding data fragments in at least one of the at least one free segment and the free sectors,

and wherein storing the padding data fragments in at least one of the at least one free segment and the free sectors comprises:

(1) determining a ratio of a number of the at least one free segment to a number of the candidate padding segments;

(2) comparing the ratio with a predetermined threshold; and

(3) in accordance with a determination that the ratio does not exceed the predetermined threshold, storing the padding data fragments in at least one of the at least one free segment and the free sectors.

2. The method of claim 1 , wherein determining candidate padding segments of the storage area comprises:

generating a first bitmap indicative of writability of a segment in the storage area;

determining, based on the first bitmap, an unwritable segment of the storage area; and

determining segments except for the unwritable segment of the storage area as the candidate padding segments.

3. The method of claim 1 , wherein determining the at least one free segment and the free sectors comprises:

generating a second bitmap indicative of overwritability of a sector in the candidate padding segments;

determining, based on the second bitmap, sectors where the data fragments are stored;

determining sectors except for the sectors where the data fragments are stored in the overwriting segments as the free sectors; and

determining segments except for the overwriting segments in the candidate padding segments as the at least one free segment.

4. The method of claim 1 , wherein the at least one free segment interleaved with the plurality of overwriting segments is positioned between a starting overwriting segment and an ending overwriting segment of the plurality of overwriting segments.

5. The method of claim 1 , wherein the storage area is divided into a plurality of segments based on a starting sector index and a segment length of the storage area.

6. The method of claim 1 , wherein the padding data fragments are different from the data fragments.

7. The method of claim 1 , wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments or free sectors in the plurality of overwriting segments comprises: storing the at least one padding data fragment in the at least one free segment between the starting overwriting segment and the ending overwriting segment of the plurality of overwriting segments and/or in the free sectors of the plurality of overwriting segments, such that the plurality of data fragments are continuous.

8. A device for storing data, comprising:

at least one processing unit;

at least one memory coupled to the at least one processing unit and having instructions to be executed by the at least one processing unit stored thereon, the instructions, when executed by the at least one processing unit, causing the device to perform acts comprising:

comparing, based on a request for overwriting target data in a storage area to cover original data, a first compression ratio of the target data with a second compression ratio of the original data;

in accordance with a determination that the first compression ratio is larger than the second compression ratio, compressing the target data into a plurality of data fragments at the first compression ratio;

storing the plurality of data fragments in a plurality of overwriting segments in the storage area, the plurality of overwriting segments being previously used for storing corresponding fragments of the original data; and

storing at least one padding data fragment in at least one free sector interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments,

wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments comprises:

(1) determining candidate padding segments of the storage area;

(2) determining, from the determined candidate padding segments, the at least one free segment and the free sectors based on locations of sectors storing the plurality of data fragments in the overwriting segments; and

(3) storing the padding data fragments in at least one of the at least one free segment and the free sectors,

and wherein storing the padding data fragments in at least one of the at least one free segment and the free sectors comprises:

(1) determining a ratio of a number of the at least one free segment to a number of the candidate padding segments;

(2) comparing the ratio with a predetermined threshold; and

(3) in accordance with a determination that the ratio does not exceed the predetermined threshold, storing the padding data fragments in at least one of the at least one free segment and the free sectors.

9. The device of claim 8 , wherein determining candidate padding segments of the storage area comprises:

generating a first bitmap indicative of writability of a segment in the storage area;

determining, based on the first bitmap, an unwritable segment of the storage area; and

determining segments except for the unwritable segment of the storage area as the candidate padding segments.

10. The device of claim 8 , wherein determining the at least one free segment and the free sectors comprises:

generating a second bitmap indicative of overwritability of a sector in the candidate padding segments;

determining, based on the second bitmap, sectors where the data fragments are stored;

determining sectors except for the sectors where the data fragments are stored in the overwriting segments as the free sectors; and

determining segments except for the overwriting segments in the candidate padding segments as the at least one free segment.

11. The device of claim 8 , wherein the at least one free segment interleaved with the plurality of overwriting segments is positioned between a starting overwriting segment and an ending overwriting segment of the plurality of overwriting segments.

12. The device of claim 8 , wherein the storage area is divided into a plurality of segments based on a starting sector index and a segment length of the storage area.

13. The device of claim 8 , wherein the padding data fragments are different from the data fragments.

14. The device of claim 8 , wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments or free sectors in the plurality of overwriting segments comprises: storing the at least one padding data fragment in the at least one free segment between the starting overwriting segment and the ending overwriting segment of the plurality of overwriting segments and/or in the free sectors of the plurality of overwriting segments, such that the plurality of data fragments are continuous.

15. A computer program product having a non-transitory computer readable medium which stores a set of instructions to overwrite data; the set of instructions, when carried out by computerized circuitry, causing the computerized circuitry to perform a method of:

comparing, based on a request for overwriting target data in a storage area to cover original data, a first compression ratio of the target data with a second compression ratio of the original data;

in accordance with a determination that the first compression ratio is larger than the second compression ratio, compressing the target data into a plurality of data fragments at the first compression ratio;

storing the plurality of data fragments in a plurality of overwriting segments in the storage area, the plurality of overwriting segments being previously used for storing corresponding fragments of the original data; and

storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments,

wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments and/or free sectors in the plurality of overwriting segments comprises:

(1) determining candidate padding segments of the storage area;

(2) determining, from the determined candidate padding segments, the at least one free segment and the free sectors based on locations of sectors storing the plurality of data fragments in the overwriting segments; and

(3) storing the padding data fragments in at least one of the at least one free segment and the free sectors,

and wherein storing the padding data fragments in at least one of the at least one free segment and the free sectors comprises:

(1) determining a ratio of a number of the at least one free segment to a number of the candidate padding segments;

(2) comparing the ratio with a predetermined threshold; and

(3) in accordance with a determination that the ratio does not exceed the predetermined threshold, storing the padding data fragments in at least one of the at least one free segment and the free sectors.

16. The computer program product of claim 15 , wherein determining candidate padding segments of the storage area comprises:

generating a first bitmap indicative of writability of a segment in the storage area;

determining, based on the first bitmap, an unwritable segment of the storage area; and

determining segments except for the unwritable segment of the storage area as the candidate padding segments.

17. The computer program product of claim 15 , wherein determining the at least one free segment and the free sectors comprises:

generating a second bitmap indicative of overwritability of a sector in the candidate padding segments;

determining, based on the second bitmap, sectors where the data fragments are stored;

determining sectors except for the sectors where the data fragments are stored in the overwriting segments as the free sectors; and

determining segments except for the overwriting segments in the candidate padding segments as the at least one free segment.

18. The computer program product of claim 15 , wherein the at least one free segment interleaved with the plurality of overwriting segments is positioned between a starting overwriting segment and an ending overwriting segment of the plurality of overwriting segments.

19. The computer program product of claim 15 , wherein the storage area is divided into a plurality of segments based on a starting sector index and a segment length of the storage area.

20. The computer program product of claim 15 , wherein storing at least one padding data fragment in at least one free segment interleaved with the plurality of overwriting segments or free sectors in the plurality of overwriting segments comprises: storing the at least one padding data fragment in the at least one free segment between the starting overwriting segment and the ending overwriting segment of the plurality of overwriting segments and/or in the free sectors of the plurality of overwriting segments, such that the plurality of data fragments are continuous.

Assignments (9)

Priority Claims (1)

Continuity (1)

Cited By (1)

US 12,487,747