Data compression method and structure for a direct access storage device

• US 5,623,701 A
• Filed: 06/06/1995
• Issued: 04/22/1997
• Est. Priority Date: 06/06/1995
• Status: Expired due to Term

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Walk, Bruce M., Bakke, Brian E., Moertl, Daniel F.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/468,712
• Time in Patent Office: 686 Days
• Field of Search: 395/888, 395/600, 395/404, 395/497.01, 395/497.02, 395/497.04, 364/715.02
• US Class Current: 710/68
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A data compression method and compression data structure are provided for a direct access storage device (DASD). The DASD is segmented into a plurality of compression groups. Each of the compression groups has a fixed logical size. A directory table is written within each of the compression groups. Each compression group has at least one compressed data region on which compressed data can be written and an exception region on which compressed data exceptions can be written. The compressed data exceptions include updated compressed data which exceeds an original storage space for corresponding original compressed data.

Claims

1. A method for storing compressed data in a direct access storage device (DASD) of the type including a fixed block architecture comprising the steps of:

segmenting the DASD into a plurality of compression groups;

each of said compression groups having a fixed logical size;

allocating at least one compressed data region and an exception region within each compression group;

writing and reading related compressed data to and from said at least one compressed data region of one of said plurality of compression groups;

writing and reading compressed data exceptions to and from said exception region;

said compressed data exceptions including updated compressed data which exceeds an original storage space for corresponding original compressed data; and

writing a corresponding directory table within said exception region for each of said compression groups.

2. A method for storing compressed data as recited in claim 1 wherein said step of writing related compressed data to said at least one compressed data region includes the steps of compressing data received from a host computer and identifying a compressed data length.

3. A method for storing compressed data as recited in claim 2 wherein said step of writing related compressed data to said at least one compressed data region includes the steps of identifying one of said compression groups utilizing a host logical block address for the data received from the host computer.

4. A method for storing compressed data as recited in claim 1 wherein said step of writing related compressed data to said at least one compressed data region includes the steps of calculating a DASD logical block address utilizing a compression group directory and said host logical block address, calculating a DASD number of blocks using said compression group directory and said identified compressed data length.

5. A method for storing compressed data as recited in claim 1 wherein said step of writing compressed data exceptions to said exception region includes the steps of:

compressing data received from a host computer and identifying a compressed data length;

identifying one of said compression groups utilizing a host logical block address for the data received from the host computer;

calculating a DASD exception region logical block address utilizing a compression group directory and said host logical block address, and

calculating a DASD exception region number of blocks using said compression group directory and said identified compressed data length.

6. A method for storing compressed data as recited in claim 1 further includes the steps of periodically performing a background sweep operation to correct fragmentation within an identified compression group, said fragmentation resulting from compressed data exceptions written to the exception region.

7. A method for storing compressed data as recited in claim 6 wherein said steps of performing a background sweep operation includes the steps of:

identifying an amount of DASD physical space required for the compression group utilizing an original compression group directory,

generating a new compression group directory with all compressed data of said identified compression group reordered in ascending host logical block address sequence with said exception region being empty in a new compression group;

utilizing said original compression group directory to gather all data in said identified compression group; and

utilizing said generated new compression group directory to store all data in said new compression group.

13. A direct access storage device as recited in claim 2 wherein said exception region contains said directory table.

8. A direct access storage device for storing a compression data structure, said compression data storage comprising:

a plurality of compression groups;

each of said compression groups having a fixed logical size;

a directory table written within each of said compression groups;

each compression group having at least one compressed data region on which compressed data can be written; and

each compression group having an exception region on which compressed data exceptions can be written;

said compressed data exceptions including updated compressed data which exceeds an original storage space for corresponding original compressed data.

9. A direct access storage device as recited in claim 8 wherein said compression group includes a plurality of compression pages.

10. A direct access storage device as recited in claim 8 wherein said compression pages have a logical size equal to a host system page size.

11. A direct access storage device as recited in claim 8 wherein each of said at least one compressed data region includes a fixed number of sectors.

12. A direct access storage device as recited in claim 9 wherein each of said at least one compressed data region includes a variable number of said compression pages.

14. A direct access storage device as recited in claim 8 wherein said compression group contains a variable number of said at least one compressed data regions.

15. A direct access storage device as recited in claim 9 wherein said compression pages span adjacent compression regions.

16. A direct access storage device as recited in claim 10 wherein said compression group size includes 1 MB with said compression page logical size and said host system page size of 4 KB.

17. A system for reading and writing compressed data comprising:

a host computer for providing and receiving data to a direct access storage device, said host computer including a direct access storage device storage management function and a logical directory for storing logical block addresses;

a storage controller coupled to said host computer for receiving and compressing data and writing compressed data to the direct access storage device and for reading and decompressing compressed data from the direct access storage device and providing the data to said host computer;

said direct access storage device including a plurality of compression groups;

each of said compression groups having a fixed logical size;

a directory table written within each of said compression groups;

each compression group having at least one compressed data region on which compressed data can be written; and

each compression group having an exception region on which compressed data exceptions can be written;

each of said compressed data exceptions including updated compressed data which exceeds an original storage space for corresponding original compressed data.

18. A system for reading and writing compressed data as recited in claim 17 wherein said storage controller includes a compression group directory cache and receives a logical block address from said host computer.

19. A system for reading and writing compressed data as recited in claim 18 wherein said storage controller includes compression management logic for identifying a logical block address within said direct access storage device utilizing said received host computer logical block address.

20. A system for reading and writing compressed data as recited in claim 17 further includes means for periodically performing a background sweep operation to correct fragmentation within an identified compression group, said fragmentation resulting from compressed data exceptions written to the exception region.