Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-08-31
2002-03-19
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S160000, C711S113000, C711S173000
Reexamination Certificate
active
06360300
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 and uncompressed data on a hard disk drive to increase storage capacity, 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 512k-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 and uncompressed data in a storage system. 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 disk partition having N slots for storing compressed data, and a second disk partition for storing uncompressed data. A portion of the N slots in the first partition include address pointers for pointing to locations in the second disk partition containing the uncompressed data.
In another aspect of the present invention, the method and system further include a memory buffer for caching data, wherein the buffer includes a first buffer partition for storing the uncompressed data, and a second buffer partition for storing the compressed data. This increases the total byte storage capacity of the buffer and can also increase system performance as more bytes can be transferred to and from the buffer. Once the first buffer partition reaches a first predetermined storage level, space is freed in the first buffer partition by moving a portion of the uncompressed data to the second disk partition Once the second buffer partition reaches a second predetermined storage level, space is freed in the second buffer partition by moving a portion of the compressed data to the first disk partition.
Accordingly, 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 20 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: 5617552 (1997-04-01), Garber et al.
patent: 5627995 (1997-05-01), Miller 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: 5721858 (1998-02-01), White et al.
patent: 5734892 (1998-03-01), Chu
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
“Automatic Data Compression Control for Hibernation,” IBM Technical Disclosure Bulletin, vol. 39, No. 04, Apr. 1996.
“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.
Corcoran Brian Jeffrey
Singh Shanker
Krall Noreen A.
Peugh Brian R.
Sawyer Law Group LLP
LandOfFree
System and method for storing compressed and uncompressed... 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 storing compressed and uncompressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for storing compressed and uncompressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2817511