Reducing occupancy of digital storage devices

• US 8,327,061 B2
• Filed: 09/28/2010
• Issued: 12/04/2012
• Est. Priority Date: 12/22/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boldy, Manfred, Sander, Peter, Stamm-Wilbrandt, Hermann
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): Cygiel, Gary W
• Application Number:
  US12/892,468
• Publication Number:
  US 20110082998A1
• Time in Patent Office: 798 Days
• Field of Search: 707/664, 709/247
• US Class Current: 711/100
• 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:

a computer 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;

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

the computer 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 the computer-readable, tangible storage device and a linked list of other first blocks having different bit patterns but equal fingerprint values, the linked list being one of one or more linked lists wherein respective linked lists correspond to respective fingerprint values;

the computer 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, the reference information for the respective first blocks including respective fingerprint values for the first blocks based on respective bit patterns for the first blocks and the linked list of other first blocks having different bit patterns but equal fingerprint values,

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

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

2. The method as recited in claim 1, wherein the reference information stored in the reference area comprises at least one reference table containing at least one entry for each block, at least one fingerprint table containing fingerprint value 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 equal fingerprint values.

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

4. The method as recited in claim 2, wherein each of the 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 2, wherein the fingerprint table contains, for each fingerprint value, a unique identifier of a first block stored in the block storage area corresponding to the fingerprint value.

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

8. 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.

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

10. The method as recited in claim 1, wherein storage device 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 a further step of:

the computer updating the number of physical blocks on a periodic time basis.

12. A computer system for managing digital data storage in a digital storage device, the computer system comprising:

one or more processors, one or more computer-readable memories, one or more computer-readable, tangible storage devices, and program instructions stored on at least one of the one or more storage devices for execution by at least one of the one or more processors via at least one of the one or more memories, the program instructions comprising;

program instructions to configure the one or more processors to segment a computer-readable, tangible storage device into a reference area and a block storage area and to segment the block storage area into storage blocks of a common length;

program instructions to configure the one or more processors to store data information in respective storage blocks of the block storage area;

program instructions to configure the one or more processors to generate 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 the computer-readable, tangible storage device and a linked list of other first blocks having different bit patterns but equal fingerprint values, the linked list being one of one or more linked lists wherein respective linked lists correspond to respective fingerprint values;

program instructions to configuring said one or more processors to store 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, the reference information for the respective first blocks including respective fingerprint values for the first blocks based on respective bit patterns for the first blocks and the linked list of other first blocks having different bit patterns but equal fingerprint values,

program instructions to configure the one or more processors to determine a bit pattern of a subsequent block and a fingerprint value in accordance with the bit pattern of the subsequent block and checking the bit pattern of the subsequent block for being identical to a bit pattern of any of the first blocks previously stored at any location in the block storage area and identified in the linked list as having a fingerprint value equal to a fingerprint value of the subsequent block, and

program instructions to configure the one or more processors to store the subsequent block and corresponding reference information in the block storage area and the reference area, respectively, of the computer-readable, tangible storage device if the bit pattern of the subsequent block is different from the bit pattern of all previously stored first blocks having the same fingerprint value and to store the subsequent block in the storage device as a reference referring to the corresponding first block without storage of the bit pattern of the subsequent block in the block storage area of the computer-readable, tangible storage device if the bit pattern of the second block is identical to any first block having the same fingerprint value.

13. The system as recited in claim 12, wherein the reference information stored in the 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 equal fingerprint values.

14. The system as recited in claim 13, wherein the entries of the reference table are numbered consecutively.

15. The system as recited in claim 13, wherein each of the 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 system 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 system as recited in claim 13, wherein the fingerprint table contains, for each fingerprint value, a unique identifier of a first block stored in the block storage area corresponding to the fingerprint value.

18. The system as recited in claim 13, wherein the chain table contains, for a particular block, its preceding block in the linkage table having equal fingerprint value, its successive block in the linkage table having equal fingerprint value, a reference count, and its fingerprint value.

19. The system as recited in claim 12, further including instructions for configuring the one or more processors 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.

20. The system as recited in claim 19, wherein the reference counter identifies how many times its associated first block is referred to in the reference area.

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

22. A computer program product for reducing data occupancy of a storage device, the computer program product comprising

one or more computer-readable, tangible storage devices and program instructions stored on at least one of the one or more storage devices, the program instructions comprising:

program instructions to segment at least one computer-readable, tangible storage device into a reference area and a block storage area and to segment the block storage area into storage blocks of a common length;

program instructions to store data information in respective storage blocks of the block storage area;

program instructions to generate 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 the computer-readable, tangible storage device and a linked list of other first blocks having different bit patterns but equal fingerprint values, the linked list being one of one or more linked lists wherein respective linked lists correspond to respective fingerprint values;

program instructions to store 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, the reference information for the respective first blocks including respective fingerprint values for the first blocks based on respective bit patterns for the first blocks and the linked list of other first blocks having different bit patterns but equal fingerprint values,

program instructions to determine a bit pattern of a subsequent block and a fingerprint value in accordance with the bit pattern of the subsequent block and checking the bit pattern of the subsequent block for being identical to a bit pattern of any of the first blocks previously stored at any location in the block storage area and identified in the linked list as having a fingerprint value equal to a fingerprint value of the subsequent block, and

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