Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-08-31
2002-09-10
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S133000, C711S159000, C711S173000
Reexamination Certificate
active
06449689
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to storing data on a hard disk drive, and more particularly to system and method for organizing compressed data on a hard disk drive to increase storage density, while reducing complexity.
BACKGROUND OF THE INVENTION
Typically, hard disk drives (HDD) are formatted physically and logically. Physically, a disk is divided into many equal-sized regions, such as sectors (pie slices) and tracks (concentric circles), so that data can be recorded in a logical manner and accessed quickly by read/write heads that move back and for the over the disk as it spins. Logically, a disk is formatted according to the standards of a host operating system. In a personal computer (PC) for example, the operating system treats the HDD as a sequential list of 512-byte block addresses.
To increase the storage capacity of HDD's, data may be compressed before storage. Basic data compression can be inefficient, however, when the data compresses to a size smaller than the standard block size of the system because the unused portion of a block become unavailable for future storage and will go unused. Assume for example that a 512-byte data block compresses at a ratio of 2:1, yielding 256-bytes. Storing the 256-byte data block into a 512 k-byte logical block on a hard drive results 256-byte of wasted storage space.
A more complex and advanced compression scheme based on log structure array (LSA) is a concept often used in large, high-performance storage systems. LSA is capable of providing data management in direct access storage systems (DASD) where HDD's are organized as a redundant array of inexpensive disks (RAID). In such DASD systems, LSA is also used to manage compressed data using a log-structured file system (LSF). LSF attempts to provide improved disk performance by maintaining large free areas on the HDD in order to speed up writes to the disks. To manage the HDD's in such a manner, each HDD in the RAID is interfaced with a hard disk assembly (HDA) circuit board, which includes a HDD controller, a buffer memory, and the LSF compression support circuit.
In operation, the LSF compression support circuit allows for the use of storage space left over when compressed data is stored in a logical block. For example, assume that a 512-byte data block compresses at a ratio of 4:1, yielding 128-bytes, then the data would be stored in the first 128-bytes of a 512-byte hard disk block, leaving 384-bytes free. If a second 512-byte data block compresses at a ratio of 2:1, then the resulting 256-bytes is stored in the same data block, which now has 128-bytes free. If a third data block is to be stored that is larger than 128-bytes, then the first 128-bytes of the data would be stored in the remainder of the disk block, and the rest would be stored in an overflow location. Alternatively, LSF may attempt to free more space with the storage block by moving previously stored data to a different block or by deleting old, unused data during a complex background process.
A LSA algorithm can also handle compression for two or more disk or a RAID. Through hardware or software functionality, multiple physical disks are treated as one logical disk to prevent data loss in case of a single HDD crash. The parity bit for each data block, which is used for error recovery, is either stored on a separate drive or spread across many drives for different data blocks. LSA is used to manage both the compression of the data and the byte-parity error-recovery process, adding to its complexity.
Although the capacity of buffer memories and HDD's continues to increase, so does the requirement for storage as evidenced by the rise of digital imaging applications. Therefore, the need for efficient data compression to provide increased storage capacity will continue. However, today's storage intensive devices, such as digital cameras for example, continue to decrease in size and cannot accommodate traditional HDA circuit boards. It has been anticipated that this problem will be overcome by replacing traditional HDA circuit boards with a single chip that includes the HDD controller, a large capacity buffer memory, and a data compression/decompression engine. However, a scheme such as LSA is too complex to provide the necessary support for LSA on such a small scale.
Accordingly, what is needed is a simplified system and method for efficiently storing compressed data on a hard disk drive that can be implemented on a single chip HDD controller. The present invention addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides a system and method for organizing compressed data on a storage disk to increase storage density. The method and system include a compressor for compressing a data block into a compressed data block, wherein N represents a compression ratio. The storage disk includes a first storage partition having N slots for storing compressed data, and a second storage partition also having N slots for storing overflow data. Each of the N slots in the first partition includes at least one address pointer for pointing to locations in the second partition.
According to a further aspect of the system and method disclosed herein, if the compressed data block is less than or equal to 1/N of the data block size, then the compressed data block is stored in a first slot in the first storage partition. If the compressed data block is greater than 1/N of the data block size, then the first 1/N of the compressed data block is stored in the first slot in the first storage partition and a remainder of the compressed block is stored in one or more slots in the second storage partition. The address pointers in the first slot point to the one or more slots in the second storage partition.
The present invention provides improved storage efficiency over prior methods at the cost of adding a minimal complexity, which will be acceptable in future HDD's and can easily be integrated in a single chip HDD controller, due to anticipated advancements in support electronics in VLSI.
REFERENCES:
patent: 4607346 (1986-08-01), Hill
patent: 5210866 (1993-05-01), Milligan et al.
patent: 5237460 (1993-08-01), Miller et al.
patent: 5237675 (1993-08-01), Hannon, Jr.
patent: 5247638 (1993-09-01), O'Brien et al.
patent: 5247660 (1993-09-01), Ashcraft et al.
patent: 5406278 (1995-04-01), Graybill et al.
patent: 5438671 (1995-08-01), Miles
patent: 5490260 (1996-02-01), Miller et al.
patent: 5537588 (1996-07-01), Engelmann et al.
patent: 5640158 (1997-06-01), Okayama et al.
patent: 5649151 (1997-07-01), Chu et al.
patent: 5659755 (1997-08-01), Strohacker
patent: 5671390 (1997-09-01), Brady et al.
patent: 5721858 (1998-02-01), White et al.
patent: 5758050 (1998-05-01), Brady et al.
patent: 5778255 (1998-07-01), Clark et al.
patent: 5805086 (1998-09-01), Brown et al.
patent: 5838964 (1998-11-01), Gubser
Atari, “Atari Home Computer System: Operating System User's Manual”, (c) 1982, pp. 89-96.*
“Extendable Random Access Memory File System,”IBM Technical Disclosure Bulletin, vol. 38, No. 05, May 1995.
“High-Speed Data Transfer Utility,”IBM Technical Disclosure Bulletin, vol. 33, No. 12, May 1991.
“Automatic Data Compression Control for Hibernation,”IBM Technical Disclosure Bulletinvol. 39, No. 04, Apr. 1996.
Corcoran Brian Jeffrey
Hufferd John Lewis
Singh Shanker
Kim Matthew
Peugh Brian R.
Sawyer Law Group LLP
LandOfFree
System and method for efficiently storing compressed data on... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficiently storing compressed data on..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficiently storing compressed data on... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844552