Storage method and hierarchical padding structure for direct access storage device (DASD) data compression

• US 5,666,560 A
• Filed: 08/03/1995
• Issued: 09/09/1997
• Est. Priority Date: 08/03/1995
• Status: Expired due to Term

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Van Grinsven, Gene Steven, Stevens, John Douglas, Moertl, Daniel Frank, Walk, Bruce Marshall
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US08/510,804
• Time in Patent Office: 768 Days
• Field of Search: 395/439, 395/888, 395/821, 395/442, 395/427, 369/48, 369/124, 341/50, 360/71, 360/48
• US Class Current: 710/68
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 2212/401 Compressed data
• 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: G11B 20/10 Digital recording or reproducing

Abstract

A data compression storage method and data compression hierarchical padding structure are provided for a direct access storage device (DASD) using fixed block architecture (FBA). A minimum page allocation defining a minimum number of sectors allocated for each logical compressed data page is selected. The DASD is segmented into at least one compression group. Each compression group has a fixed logical size and includes a selected number of DASD compressed data pages with an initial page allocation of a number of sectors. The initial page allocation is greater than or equal to the minimum page allocation. A minimum number of compressed data regions is allocated within each compression group. A selected number of additional compressed data regions including a plurality of sectors for padding is allocated within each compression group. The plurality of padding sectors are distributed between the compression pages. An exception region is allocated within each compression group. Compressed data is written to a selected DASD compressed data page and typically updated in place. Compressed data is written and updated to the selected DASD compressed data page using sector borrowing of available free sectors from adjacent pages if needed.

Claims

1. A data compression hierarchical padding structure for a computer readable direct access storage device (DASD) using fixed block architecture (FBA) comprising:

storage, wherein said storage contains at least one compression group;

each compression group having a fixed logical size including a selected number of compressed data pages with an initial page allocation of a number of sectors;

each compression group having a selected minimum page allocation defining a minimum number of sectors allocated for each logical compressed data page; and

each compression group having a selected number of additional padding sectors;

said padding sectors being distributed to said selected number of compressed data pages.

2. A data compression hierarchical padding structure for a direct access storage device (DASD) as recited in claim 1 wherein each compression group includes a minimum number of compression regions and a selected number of additional padding compression regions providing said selected number of additional padding sectors.

3. A data compression hierarchical padding structure for a direct access storage device (DASD) as recited in claim 1 wherein said initial page allocation of said number of sectors is greater than or equal to said minimum page allocation.

4. A data compression hierarchical padding structure for a direct access storage device (DASD) as recited in claim 1 wherein each compression group includes at least one compression region defining an exception region for storing a compression group directory and updated compressed data which exceeds an original storage space for corresponding original compressed data.

5. A data compression hierarchical padding structure for a direct access storage device (DASD) as recited in claim 1 wherein compressed data pages have a logical size equal to a host system page size.

6. A method for storing compressed data in a direct access storage device (DASD) using fixed block architecture (FBA) comprising the computer executable steps of:

selecting a minimum page allocation to define a minimum number of sectors allocated for each logical compressed data page;

segmenting the DASD into at least one compression group;

each compression group having a fixed logical size and including a selected number of compressed data pages with an initial page allocation of a number of sectors;

said initial page allocation being greater than or equal to said minimum page allocation;

allocating a minimum number of compressed data regions within each compression group;

allocating a selected number of additional compressed data regions including a plurality of sectors for padding within each compression group;

distributing said plurality of padding sectors between said compressed data pages;

allocating an exception region within each compression group; and

writing compressed data and updated compressed data to a selected compressed data page.

7. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 6 wherein the step of writing compressed data and updated compressed data to said selected compressed data page includes the steps of:

comparing the size of the compressed data or updated compressed data with an allocated space for said selected compressed data page; and

when said allocated space is greater than or equal to the size of the compressed data or updated compressed data, writing the compressed data or updated compressed data within said allocated space.

8. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 7 further includes the step of:

when said allocated space is less than the size of the compressed data or updated compressed data, comparing the size of the compressed data or updated compressed data with said allocated space for said selected compressed data page combined with free sectors from adjacent pages.

9. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 8 further includes the step of:

when said allocated space combined with free sectors from adjacent pages is greater than or equal to the size of the compressed data or updated compressed data, writing the compressed data or updated compressed data within said allocated space combined with free sectors from adjacent pages.

10. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 9 further includes the step of:

when said allocated space combined with free sectors from adjacent pages is less than the size of the compressed data or updated compressed data, comparing the size of the compressed data or updated compressed data with available space in said exception region.

11. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 10 further includes the step of:

when said available space in said exception region is greater than or equal to the size of the compressed data or updated compressed data, writing the compressed data or updated compressed data within said available space in said exception region.

12. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 11 further includes the step of:

when said available space in said exception region is less than the size of the compressed data or updated compressed data;

reorganizing said compression group.

13. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 12 wherein the step of reorganizing said compression group includes the steps of:

identifying an amount of DASD physical space required for the compression group utilizing an original compression group directory and said selected minimum page allocation,

allocating a minimum number of compressed data regions within the compression group;

allocating a selected number of additional compressed data regions including a plurality of sectors for padding within the compression group;

distributing said plurality of padding sectors between said compressed data pages;

allocating an exception region within the compression group; and

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.

14. A method for storing compressed data in a direct access storage device (DASD) as recited in claim 13 further includes the steps of:

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

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

15. A method for storing compressed data in a direct access storage device (DASD) using fixed block architecture (FBA) comprising the computer executable steps of:

selecting a minimum page allocation to define a minimum number of sectors allocated for each logical compressed data page;

segmenting the DASD into at least one compression group;

each compression group having a fixed logical size;

allocating a selected number of compressed data pages with an initial page allocation of a number of sectors within each compression group;

said initial page allocation being greater than or equal to said minimum page allocation;

distributing a selected number of padding sectors to said selected number of compressed data pages; and

when writing compressed data to a selected compressed data page, dynamically using said padding sectors and available extra sectors from adjacent compressed data pages.

16. A computer program product for use in a computer system having a processor, and a direct access storage device (DASD) using fixed block architecture (FBA), the computer program product comprising:

a computer readable recording medium;

means, recorded on the recording medium, for selecting a minimum page allocation to define a minimum number of sectors allocated for each logical compressed data page;

means, recorded on the recording medium, for segmenting the DASD into at least one compression group;

each compression group having a fixed logical size and including a selected number of compressed dam pages with an initial page allocation of a number of sectors; and

having a selected number of additional padding sectors;

said padding sectors being distributed to said selected number of compressed data pages; and

means, recorded on the recording medium, for writing compressed data and updated compressed data to a selected compressed data page.

17. A computer program product as recited in claim 16 wherein said means, recorded on the recording medium, for writing compressed data and updated compressed data to said selected compressed data page include;

means for comparing the size of the compressed data or updated compressed data to be written with an allocated space for said selected compressed data page; and

means, responsive to said allocated space being greater than or equal to the size of the compressed data or updated compressed data, for writing the compressed data or updated compressed data within said allocated space.

18. A computer program product as recited in claim 17 further includes;

means, responsive to said allocated space being less than the size of the compressed data or updated compressed data, for identifying free sectors from adjacent pages and for comparing the size of the compressed data or updated compressed data with said allocated space for said selected compressed data page combined with free sectors from adjacent pages.

19. A computer program product as recited in claim 18 further includes;

means, responsive to said allocated space combined with free sectors from adjacent pages being greater than or equal to the size of the compressed data or updated compressed data, for writing the compressed data or updated compressed data within said allocated space combined with free sectors from adjacent pages.

20. A computer readable storage device, comprising:

storage, wherein said storage contains at least one compression group;

each compression group having a fixed logical size including a selected number of compressed data pages with an initial page allocation of a number of sectors;

each compression group having a selected minimum page allocation defining a minimum number of sectors allocated for each logical compressed data page; and

each compression group having a selected number of additional padding sectors;

said padding sectors being distributed to said selected number of compressed data pages.

21. The storage device as recited in claim 20, wherein each compression group further comprises a minimum number of compression regions and a selected number of additional padding compression regions providing said selected number of additional padding sectors.

22. A storage device as recited in claim 20, wherein said initial page allocation of said number of sectors is greater than or equal to said minimum page allocation.

23. A storage device as recited in claim 20, wherein each compression group further comprises at least one compression region defining an exception region for storing a compression group directory and updated compressed data which exceeds an original storage space for corresponding original compressed data.

24. A storage device as recited in claim 20, wherein compressed data pages have a logical size equal to a host system page size.