Apparatus for compressing data in a dynamically mapped virtual data storage subsystem

• US 5,247,638 A
• Filed: 06/18/1990
• Issued: 09/21/1993
• Est. Priority Date: 06/18/1990
• Status: Expired due to Term

• Current Assignee: Storage Technologies Corporation (Oracle Corporation)
• Original Assignee: Storage Technologies Corporation (Oracle Corporation)
• Inventors: Buhlman, Craig A., Milligan, Charles A., O'Brien, John T., Rudeseal, George A.
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): WHITFIELD, MICHAEL
• Application Number:
  US07/540,219
• Time in Patent Office: 1,191 Days
• Field of Search: 395/425, 395/575, 341/87, 371/10.1, 371/8.1, 371/37.1
• US Class Current: 710/68
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• 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/1803 by redundancy in data representation
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

The use of a dynamically mapped virtual memory system permits the storage of data so that each data record occupies only the physical space required for the data. Furthermore, the data storage subsystem manages the allocation of physical space on the disk drives and does not rely on the file extent defined in the count key data format. Data compaction apparatus is provided to remove the gaps contained in the stream of count key data records received from the host processor. A data compression algorithm is then used to compress the received data into a compressed format for storage on the disk drives. It is the compacted, compressed data that is finally stored on the disk drives. Furthermore, any data record received from the host processor absent data in the user data field therein is simply listed in the virtual memory map as a null field occupying no physical space on the disk drives. The data storage control, through its mapping capability, stores the actual data in the minimum physical space required by overcoming the limitations imposed on large form factor disk drives by the use of count key data format data records. However, the data storage subsystem returns this stored data to the host processor in count key data format through a data record reformatting process once the stored compacted compressed data is staged to the cache memory for access by the host processor. The data storage subsystem is operationally independent of the host processor, yet performs as if it were a standard operationally dependent large form factor disk subsystem.

Claims

1. A dynamically mapped virtual memory system for storing count key data format data records, each of which includes a data field, for at least one data processor comprising:

a plurality of disk drives, a subset of said plurality of disk drives configured into at least two redundancy groups, each redundancy group consisting of n+m disk drives, where n and m are both positive integers, with n being greater than 1 and m being at least equal to 1;

means responsive to the receipt of a stream of count key data format data records from a data processor for compressing said data field contained in each data record in said received stream of data records using a predefined data compression process to create a compressed data record;

means for storing each said compressed data record;

means for generating m redundancy segments using a plurality of said compressed data records;

means for selecting one of said redundancy groups having available memory space for storing said compressed data records and said m redundancy segments and

means for writing said compressed data records and said m redundancy segments on said n+m disk drives in said selected one redundancy group.

2. The virtual memory system of claim 1 wherein said compressing means comprises:

means for dividing said data field of each data record in said received stream of data records into at least two sections of data;

means for compressing a section of data to form a compressed data section comprising;

means, responsive to a received data byte in said section of data, for determining whether said received data byte is identical to n data bytes last received prior to said received data byte, a last byte of a string or a string data byte in said sections of data;

means, responsive to said determining means, for assigning one of a plurality of run length reference values to a data byte that is identical to said n data bytes last received prior to said received data byte, where n is a positive integer >

2;

means, responsive to said determining means, for assigning one of a plurality of byte compression reference values to a data byte;

means, responsive to said determining means, for assigning one of a plurality of string compression reference values to a data byte that comprises said last byte of a data string; and

means for writing said run length, byte compression and string compression reference values successively received from said data section compressing means to said storing means to form said compressed data section.

3. The virtual memory system of claim 1 further comprising:

means, responsive to a last data byte contained in said data field, for appending a cyclic redundancy check value representative of a cyclic redundancy check of said data field to said compressed data record written in said storing means.

4. The virtual memory system of claim 1 wherein said compressing means comprises:

means, responsive to the receipt of a data record having an empty data field, for disabling said storing means from storing said data record having an empty data field.

5. The virtual memory system of claim 1 wherein said compressing means comprises:

means, responsive to the receipt of a count key data format data record, for deleting said count field from said received count key data format data record.

6. The virtual memory system of claim 5 further comprising:

means, responsive to the receipt of said count key data format data record, for excerpting the key field from said received count key data format data record; and

means for storing said excerpted key field and an associated pointer indicative of the location of said excerpted key field in available memory space in said selected one redundancy group.

7. The virtual memory system of claim 2, wherein said compressing means further comprises:

means for writing said at least two sections of data directly into a buffer;

means responsive to said buffer storing a last byte of a section of data, for calculating a byte length of said run length, byte compression and string compression reference values written in said storing means representative of said section of data; and

means, responsive to said calculated byte length exceeding a byte length of said section of data, for expunging said run length, byte compression and string compression reference values written in said storing means representative of said section of data; and

means, responsive to said expunging means, for substituting in said storing means said section of data stored in said buffer for said run length, byte compression and string compression reference values.

8. The virtual memory system of claim 1 further comprising:

means, responsive to said compressing means producing a compressed representation of the bytes of said data field in a data record, for decompressing said compressed representation of the data bytes of said at a field in said data record;

means, responsive to said decompressing means, for generating a first cyclic redundancy check value representative of a cyclic redundancy check of said compressed and decompressed data field;

means for generating a second cyclic redundancy check value representative of a cyclic redundancy check of said data field in said received data record; and

means for comparing said first cyclic redundancy check value with said second cyclic redundancy check value to identify errors in said compressed data record.

9. The virtual memory system of claim 2 wherein said string reference value assignment means comprises:

means for comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes in said section of data that have been assigned a string reference value; and

means, responsive to said received string of data bytes failing to match said table entries, for assigning a previously unassigned string reference value to said received string.

10. In a dynamically mapped virtual disk memory system containing a plurality of disk drives, a subset of said plurality of said disk drives configured into a plurality of redundancy groups, each redundancy group consisting of n+m disk drives, where n and m are both positive integers, with n being greater than 1 and m being at least equal to 1, and a cache memory connected to and interconnecting a host processor and said plurality of disk drives, a method of storing count key data format data records, each of which includes a data field, for said host processor comprising the steps of:

compressing, in response to the receipt of a stream of count key data format data records from said host processor, said data field contained in each data record in said received stream of data records using a predefined data compression process to create a compressed data record;

storing each said compressed data record in said cache memory;

generating m redundancy segments using a plurality of said compressed data records;

selecting one of said redundancy groups having available memory space for storing said plurality of compressed data records and said m redundancy segments; and

writing said plurality of compressed data records and said m redundancy segments on said n+m disk drives in said selected one redundancy group.

11. The method of claim 10 wherein said step of compressing comprises:

dividing said data field of each data record in said received stream of data records into at least two sections of data;

compressing a section of data to form a compressed data section comprising;

determining, in response to a received data byte in said section of data, whether said received data byte is identical to n data bytes last received prior to said received data byte, a last byte of a string or a single data byte in said section of data;

assigning one of a plurality of run length reference values to a data byte that is identical to said n data bytes last received prior to said received data byte, where n is an integer >

2;

assigning one of a plurality of byte compression reference values to a data byte;

assigning one of a plurality of string compression reference values to a data byte that comprises said last byte of a data string; and

writing said run length, byte compression and string compression reference values successively received from said data section compressing step to said cache memory to form said compressed data section.

12. The method of claim 10 further comprising:

appending, in response to a last data byte contained in said data field, a cyclic redundancy check value representative of a cyclic redundancy check of said data field to said compressed data record written in said cache memory.

13. The method of claim 10 wherein said step of compressing further comprises:

disabling said step of storing in response to the receipt of a count key data format data record having an empty data field.

14. The method of claim 10 wherein said step of compressing comprises:

deleting, in response to a received count key data format data record, said count field from said received count key data format data record.

15. The method of claim 14 further comprising:

excerpting the key field from said received count key data format data record; and

storing said excerpted key field and an associated pointer indicative of the location of excerpted key field in said available memory space in said selected one redundancy group.

16. The method of claim 10, wherein said step of compressing includes dividing said received data record into at least two sections for data compression expansion detection, said method further comprising:

writing a received data record directly into a buffer;

calculating, in response to storing a last byte of a section of data in said cache memory, a byte length of said run length, byte compression and string compression reference values written to said cache memory representative of said section of data;

expunging, in response to said calculated byte length exceeding a byte length of said section of data, said run length, byte compression and string compression reference values written in said cache memory representative of said one section of data; and

substituting in said cache memory said section of data for said run length, byte compression and string compression reference values.

17. A dynamically mapped virtual disk memory system for storing count key data format data records, each of which includes a data field, for at least one data processor comprising:

a plurality of disk drives, a subset of said plurality of said disk drives configured into at least two redundancy groups, each redundancy group consisting of n+m disk drives, where n and m are both positive integers, with n being greater than 1 and m being at least equal to 1;

means, responsive to the receipt of a stream of count key data format data records from a data processor, for compressing said data fields contained in each data record in said received stream of data records using a predefined data compression process to create a compressed data record;

cache memory means for storing each said compressed data record;

means, responsive to the storage of n segments of compressed data records in said cache memory means, for generating m redundancy segments using said n stored segments of compressed data records;

means for selecting one of said redundancy groups having available memory space for storing said n segments of compressed data records and said m redundancy segments; and

means for writing said n segments of compressed data records and said m redundancy segments on said n+m disk drives in said selected on redundancy group.

18. The disk memory system of claim 17 wherein said compressing means comprises:

means for dividing said data field of a received count key data format data record into at least two sections of data;

means for compressing said section of data to form a compressed data section comprising;

means, responsive to a received data byte in said section of data, for determining whether said received data byte is identical to n data bytes last received prior to said received data byte, a last byte of a string or a single data byte in said one section of data;

means, responsive to said determining means, for assigning one of a plurality of run length reference values to a data byte that is identical to said n data bytes last received prior to said received data byte, where n is an integer >

2;

means, responsive to said determining means, for assigning one of a plurality of byte compression reference values to a data byte;

means, responsive to said determining means, for assigning one of a plurality of string compression reference values to a data byte that comprises said last byte of a data string; and

means for writing said run length, byte compression and string compression reference values successively received from said data section compressing means to said cache memory means to form said compressed data section.

19. The disk memory system of claim 17 further comprising:

means, responsive to a last data byte of said data field, for appending a cyclic redundancy check value representative of a cyclic redundancy check of said at a field to said compressed data record written in said cache memory means.

20. The disk memory system of claim 17 wherein said compressing means comprises:

means, responsive to the receipt of a count key data format data record having an empty data field, for disabling said storing means for said received data record.

21. The disk memory system of claim 17 wherein said compressing means comprises:

means, responsive to a received count key data format data record, for deleting said count field from said received count key data format data record.

22. The disk memory system of claim 21 further comprising:

means, responsive to the receipt of said count key data format data record, for excerpting the key field from said received count key data format data record; and

means for storing said excerpted key field and an associated pointer indicative of the location of said excerpted key field in available memory space in said selected one redundancy group.

23. The disk memory system of claim 17, wherein said compressing means divides said received data record into at least two sections for data compression expansion detection, further comprising:

means for writing a received section of data directly into a buffer memory means;

means responsive to said buffer memory means storing a last byte of a section of data for calculating a byte length of said run length, byte compression and string compression reference values written to said buffer memory means representative of said section of data;

means responsive to said calculated byte length exceeding a byte length of said section of data for expunging said run length, byte compression and string compression reference values written in said cache memory means representative of said section of data; and

means, responsive to said expunging means for substituting in said cache memory means said section of data for said run length, byte compression and string compression reference values.

24. The disk memory system of claim 17 further comprising:

means, responsive to said compressing means producing a compressed representative of said data fields contained in a data record, for decompressing said compressed representation; and

means, responsive to said decompressing means, for comparing said decompressed compressed data fields of said data record with said data fields contained in said data record to identify errors in said compressed data fields of said data record.

25. The disk memory system of claim 18 wherein said string reference value assignment means comprises:

means for comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes in said section of data that have been assigned a string reference value; and

means, responsive to said received string of data bytes failing to match said table entries for assigning a previously unassigned string reference value to said received string.

26. A dynamically mapped virtual memory data storage subsystem for storing count key data format data records, each of which includes a data field, for at least one data processor which transmits a stream of said data records in said stream of data records to said data storage subsystem, comprising:

a plurality of disk drives for storing data thereon;

means, responsive to the receipt of a stream of count key data format data records from a data processor, for compressing each data record in said stream of data records using a predefined data compression process to create a compressed data record;

means for translating a virtual address received from said data processor and associated with said compressed data record into a logic address indicative of a physical memory location on said disk drives for the storage of said compressed data record; and

means for writing said compressed data record into said physical memory location on said disk drives.

27. The data storage subsystem of claim 26 wherein said compressing means comprises:

means for dividing said data field of each data record in said received stream of data records into at least two sections of data;

means for compressing a section of data to form a compressed data section comprising;

means, responsive to a received data byte in said section of data, for determining whether said data byte is identical to n data bytes last received prior to said received data byte, a last byte of a string or a single data byte in said section of data;

means, responsive to said determining means, for assigning one of a plurality of run length reference values to a data byte that is identical to said n data bytes last received prior to said received data byte, where n is an integer >

2;

means, responsive to said determining means, for assigning one of a plurality of byte compression reference values to a data byte;

means, responsive to said determining means, for assigning one of a plurality of byte compression reference values to a data byte;

means, responsive to said determining means, for assigning one of a plurality of string compression reference values to a data byte that comprises said last byte of a data string; and

means for writing each of said run length, byte compression and string compression reference values successively received from said data section compressing means into a buffer memory to form said compressed data section.

28. The data storage subsystem of claim 26 further including:

means, responsive to a last data byte of said data field, for appending a cyclic redundancy check value representative of a cyclic redundancy check of said data field to said compressed data record.

29. The data storage subsystem of claim 26 wherein said compressing means further comprises:

means for expunging gaps in said received count key data format data record prior to said writing means storing said data record on said disk drives.

30. The data storage subsystem of claim 26 wherein said compressing means comprises:

means, responsive to a received count key data format data record, for deleting said count field from said received count key data format data record.

31. The data storage subsystem of claim 26 wherein said compressing means comprises:

means, responsive to the receipt of a count key data format data record, for excerpting the key field from said received count key data format data record; and

means for storing said excerpted key field and an associated pointer indicative of the location of said excerpted key field in available memory space in said physical memory location.

32. The data storage subsystem of claim 26, wherein said compressing means divides said received data record into at least two sections for data compression expansion detection, said apparatus further comprising:

means for writing a section of data directly into a buffer memory;

means, responsive to a last byte of a section of data written into said buffer memory, for calculating a byte length of said compressed data written to said storing means; and

means, responsive to said calculated byte length exceeding a byte length of said received data record, for expunging said compressed section of data written on to said storing means and replacing it with the section of data from said buffer memory.

33. The data storage subsystem of claim 26 further comprising:

means, responsive to said compressing means producing a compressed representation of the data bytes of said data field in a received data record, for decompressing said compressed representation of the data bytes of said data field in a received data record;

means, responsive to said decompressing means, for generating a first cyclic redundancy check value representative of a cyclic redundancy check of said compressed and decompressed data field;

means for generating a second cyclic redundancy check value representative of a cyclic redundancy check of said data field in said data record; and

means for comparing said first generated cyclic redundancy check value with said second generated cyclic redundancy check value to identify errors in said compressed data section of said data record.

34. The data storage subsystem of claim 27 wherein said string reference value assignment means comprises:

means for comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes in said section of data that have been assigned a string reference value; and

means, responsive to said received string of data bytes failing to match said table entries, for assigning a previously unassigned string reference value to said received string.

35. A method of storing data in a dynamically mapped virtual memory data storage subsystem having a plurality of disk drives for storing count key data format data records, each of which includes a data field, for at least one data processor which transmits a stream of said data records and a virtual address associated with each data recording said stream of data records transmitted to said data storage subsystem, comprising the steps of:

compressing, in response to the receipt of said stream of count key data format data records from a data processor, each data record in said received stream of data records using a predefined data compression process to create a compresses data record;

translating said virtual address associated with said compressed data record into a logical address indicative of a physical memory location on said disk drives for the storage of said compressed data record; and

storing said compressed data record in said physical memory location.

36. The method of claim 35 wherein said step of compressing comprises:

dividing said data field of each data record in said received stream of data records into at least two sections of data;

compressing a section of data in said data record comprising;

determining, in response to a received data byte in said section of data, whether said received data byte is identical to n data bytes last received prior to said received data byte, a last byte of a string or a single data byte in said section of data;

assigning one of a plurality of run length reference values to a data byte that is identical to n data bytes last received prior to said received data byte, where n is an integer >

2;

assigning one of a plurality of byte compression reference values to a data byte;

assigning one of a plurality of string compression reference values to a data byte that comprises a last byte of a data string; and

writing each of said run length, byte compression and string compression reference values successively compressed into a buffer memory to form said compressed data.

37. The method of claim 35 further comprising:

appending, in response to a last data byte of said data field, a cyclic redundancy check value representative of a cyclic redundancy check of said data field to said compressed data record.

38. The method of claim 36 wherein said step of compressing comprises:

expunging gaps in said received count key data format data record prior to storing said sections of said received data record in said physical memory location.

39. The method of claim 35 wherein said step of compressing comprises:

deleting said count field from said count key data format data record.

40. The method of claim 35 wherein said step of compressing comprises:

excerpting the key field from said received count key data format data record; and

storing said excerpted key field and an associated pointer indicative of the location of said excerpted key field in available memory space in said physical memory location.

41. The method of claim 35, wherein said compressing means divides said received count key data format data record into at least two sections for data detection, said method further comprising:

writing said received count key data format data record directly into a buffer memory;

calculating, in response to a last byte of data written into said buffer memory, a byte length of said compressed data;

expunging, in response to calculated said byte length exceeding a byte length of said received count key data format count key data format data record written in said buffer memory.

42. The method of claim 35 further comprising:

decompressing, in response to said step of compressing, said compressed representation of the data bytes of said data field in a received count key data format data record;

generating a first cyclic redundancy check value representative of a cyclic redundancy check of said compressed and decompressed data field;

generating a second cyclic redundancy check value representative of a cyclic redundancy check of said data field in said received data record; and

comparing said first generated cyclic redundancy check value with said second generated cyclic redundancy check value to identify errors in said compressed count key data format data record.

43. The method of claim 36 wherein said string reference value assignment comprises:

comparing a received string of data bytes with a table containing entries representative of previously received strings of data bytes in said section of data that have been assigned a string reference value; and

assigning, in response to said received string of data bytes failing to match said table entries, a previously unassigned string reference value to said received string.