Reducing occupancy of digital storage devices

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.

1 . A digital data storage device storing information on a storage medium segmented into blocks, wherein said storage medium is segmented into two areas, wherein the first area comprises reference means and the remaining area of the storage medium is used for storing said information and wherein a second or further block being identical with a first block on block level is stored only as reference referring to the first block.  
   
   
       2 . A digital data storage device according to  claim 1 , comprising 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 containing, for each block, at least information about blocks having same fingerprints.  
   
   
       3 . A digital data storage device according to  claim 2 , wherein the entries of said reference table are numbered consecutively.  
   
   
       4 . A digital data storage device according to  claim 2 , wherein each of said entries consists of at least one field containing a unique identifier for identifying the physical sector where the real block is stored in the remaining physical storage area.  
   
   
       5 . A digital data storage device according to  claim 4 , wherein the length of a reference field is defined as the maximum amount of required binary digits (bits) for real sector IDs.  
   
   
       6 . A digital data storage device according to  claim 1 , wherein a real block stored in said remaining area of the storage medium comprises a reference counter for counting the number of references to that real block.  
   
   
       7 . A digital data storage device according to  claim 6 , wherein said reference counter is used to identify how many times a block is referred to.  
   
   
       8 . A digital data storage device according to  claim 2 , wherein said fingerprint table contains, for each fingerprint, the first unique identifier of a block corresponding to said fingerprint.  
   
   
       9 . A digital data storage device according to  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, its reference count, and its fingerprint.  
   
   
       10 . A digital data storage device according to  claim 1 , wherein said storage medium is formatted so that the number of real blocks equals the number of entries of the reference table.  
   
   
       11 . A digital data storage device according to  claim 10 , wherein the number of real blocks is adapted on a periodic time basis.  
   
   
       12 . A digital data storage device according to  claim 1 , wherein a particular area of said storage medium is reserved for the reference table and thus can not be occupied by real (user) data wherein these real data is only stored in a real sector wherein occupation of the real sector advantageously can move from outer tracks to inner tracks of the storage medium.  
   
   
       13 . A digital data storage device according to  claim 1 , wherein said reference means is stored outside the storage medium of the storage device, preferably in a Random-Access-Memory (RAM) being part of the storage device or a virtual RAM disk storage being part of the main storage of an underlying computer system.  
   
   
       14 . A digital data storage device according to  claim 13 , further comprising a fail-over means for storing the reference table entries in a non-volatile storage, preferably an Electrically Erasable Programmable Read-Only Memory (EEPROM).