REDUCING OCCUPANCY OF DIGITAL STORAGE DEVICES

• US 20110082998A1
• Filed: 09/28/2010
• Published: 04/07/2011
• Est. Priority Date: 12/22/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boldy, Manfred, Sander, Peter, Stamm-Wilbrandt, Hermann
• Granted Patent: US 8,327,061 B2
• Time in Patent Office: Days
• US Class Current: 711/173
• CPC Class Codes: G11B 20/12 Formatting, e.g. arrangement of data block or words on the record carriers within interface between computers and data recorders G06F3/06

Abstract

A digital data storage device physically stores blocks of identical data only once on its storage medium wherein a second or even further identical blocks are stored only as reference referring to the first block of these identical blocks. By this technique, storage of duplicate data is most effectively avoided on the lowest storage level of the disk storage device, even in cases where identical blocks are written by different operating Systems. In the preferred embodiment, the underlying storage medium (magnetic hard disk, optical disk, tape, or M-RAM) is segmented into two areas, the first area particularly comprising a relatively small block reference table and the remaining physical storage area for storing real blocks of information.

Claims

1. A method for managing digital data storage, the method comprising steps of:

segmenting a computer-readable, tangible storage device into a reference area and a block storage area and segmenting the block storage area into storage blocks of a common length storing data information in respective storage blocks of the block storage area;

generating respective reference information for the blocks of data, the reference information including respective fingerprint information based on bit patterns of respective first blocks stored on said computer-readable, tangible storage medium and a linked list of other first blocks having different bit patterns but equal fingerprint values;

storing the first blocks in the block storage area and the reference information in the reference area with reference information pointing to each corresponding first block, said reference information for the respective first blocks including respective fingerprint values for the first blocks based on respective bit pattern'"'"'s for said first blocks and said linked list of other first blocks having different bit patterns but equal fingerprint values,

determining a bit pattern of a subsequent block and a fingerprint value in accordance with said bit pattern of said subsequent block and checking said bit pattern of said subsequent block for being identical to a bit pattern of any of the first blocks previously stored at any location in said block storage area and having the same fingerprint value as said subsequent block, and

storing said subsequent block and corresponding reference information in said block storage area and said reference area, respectively, of the computer-readable, tangible storage device if the bit pattern of said subsequent block is different from the bit pattern of all previously stored first blocks having the same fingerprint value but is stored in said storage medium only as a reference referring to the corresponding first block if the bit pattern of said second block is identical to any first block having the same fingerprint value.

2. The method as recited in claim 1, wherein said reference information stored in said reference area comprises at least one reference table containing at least one entry for each block, at least one fingerprint table containing fingerprint information for each block and at least one chain table comprising a doubly linked list containing, for each block, at least information about blocks having same fingerprints.

3. The method as recited in claim 2, wherein the entries of said reference table are numbered consecutively.

4. The method as recited in claim 2, wherein each of said entries consists of at least one field containing a unique identifier for identifying a physical sector where the corresponding first block is stored in the block storage area.

5. The method as recited in claim 4, wherein the length of a reference field is defined as the maximum amount of required binary digits (bits) for physical sector IDs.

6. The method as recited in claim 1, wherein a reference counter is stored for each of the first blocks having a counter number counting a number of references to that first block in the reference area.

7. The method as recited in claim 6, wherein said reference counter identifies how many times its associated first block is referred to in the reference area.

8. The method as recited in claim 2, wherein said fingerprint table contains, for each fingerprint, a unique identifier of a first block stored in the block storage area corresponding to said fingerprint.

9. The method as recited in claim 2, wherein said chain table contains, for a particular block, its preceding block in the linkage table having same fingerprint, its successive block in the linkage table having same fingerprint, a reference count, and its fingerprint.

10. The method as recited in claim 1, wherein said storage medium is formatted so that the number of physical blocks equals the number of entries of the reference table.

11. The method as recited in claim 10, further comprising means to update the number of physical blocks on a periodic time basis.

12. A data storage architecture for managing digital data storage comprising:

a computer configured to provide

an arrangement for segmenting a computer-readable, tangible storage device into a reference area and a block storage area and segmenting the block storage area into storage blocks of a common length;

storing data information in respective storage blocks of the block storage area;

an arrangement for generating respective reference information for the blocks of data, the reference information including respective fingerprint information based on bit patterns of respective first blocks stored on said computer-readable, tangible storage medium and a linked list of other first blocks having different bit patterns but equal fingerprint values;

an arrangement for storing the first blocks in the block storage area and the reference information in the reference area with reference information pointing to each corresponding first block, said reference information for the respective first blocks including respective fingerprint values for the first blocks based on respective bit patterns for said first blocks and said linked list of other first blocks having different bit patterns but equal fingerprint values,

an arrangement for determining a bit pattern of a subsequent block and a fingerprint value in accordance with said bit pattern of said subsequent block and checking said bit pattern of said subsequent block for being identical to a bit pattern of any of the first blocks previously stored at any location in said block storage area and having the same fingerprint value as said subsequent block, and

an arrangement for storing said subsequent block and corresponding reference information in said block storage area and said reference area, respectively, of the computer-readable, tangible storage device if the bit pattern of said subsequent block is different from the bit pattern of all previously stored first blocks having the same fingerprint value but is stored in said storage medium only as a reference referring to the corresponding first block if the bit pattern of said second block is identical to any first block having the same fingerprint value.

13. The data storage architecture as recited in claim 12, wherein said reference information stored in said reference area comprises at least one reference table containing at least one entry for each block, at least one fingerprint table containing fingerprint information for each block and at least one chain table comprising a doubly linked list containing, for each block, at least information about blocks having same fingerprints.

14. The data storage architecture as recited in claim 13, wherein the entries of said reference table are numbered consecutively.

15. The data storage architecture as recited in claim 13, wherein each of said entries consists of at least one field containing a unique identifier for identifying a physical sector where the corresponding first block is stored in the block storage area.

16. The data storage architecture as recited in claim 15, wherein the length of a reference field is defined as the maximum amount of required binary digits (bits) for physical sector IDs.

17. The data storage architecture as recited in claim 12, wherein said computer is further configured to provide a reference counter stored for each of the first blocks having a counter number counting a number of references to that first block in the reference area.

18. The data storage architecture as recited in claim 17, wherein said reference counter identifies how many times its associated first block is referred to in the reference area.

19. The data storage architecture as recited in claim 13, wherein said fingerprint table contains, for each fingerprint, a unique identifier of a first block stored in the block storage area corresponding to said fingerprint.

20. The data storage architecture as recited in claim 13, wherein said chain table contains, for a particular block, its preceding block in the linkage table having same fingerprint, its successive block in the linkage table having same fingerprint, a reference count, and its fingerprint.

21. The data storage architecture as recited in claim 12, wherein said storage medium is formatted so that the number of physical blocks equals the number of entries of the reference table.

22. The method as recited in claim 21, further comprising means to update the number of physical blocks on a periodic time basis.