Memory compression for computer systems

• US 20030229761A1
• Filed: 06/10/2002
• Published: 12/11/2003
• Est. Priority Date: 06/10/2002
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kumar, Rajendra, Roy, Sumit, Basu, Sujoy
• Granted Patent: US 6,857,047 B2
• Time in Patent Office: Days
• US Class Current: 711/134
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/311 In host system
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer system is provided including a processor, a persistent storage device, and a main memory connected to the processor and the persistent storage device. The main memory includes a compressed cache for storing data retrieved from the persistent storage device after compression and an operating system. The operating system includes a plurality of interconnected software modules for accessing the persistent storage device and a filter driver interconnected between two of the plurality of software modules for managing memory capacity of the compressed cache and the buffer cache.

Claims

1. A method for memory operation in a computer system, comprising:

determining when compressed data is present in non-persistent memory and;

decompressing the compressed data as decompressed data, and

providing the decompressed data from the non-persistent memory for processing; and

determining when the compressed data is not present in the non-persistent memory and;

providing uncompressed data from the persistent memory for processing.

2. The method as claimed in claim 1 comprising:

determining when the compressed data is not present in the non-persistent memory and;

compressing the uncompressed data from the persistent memory to form new compressed data and

storing the new compressed data in the non-persistent memory.

3. The method as claimed in claim 1 comprising:

determining when the compressed data is not present in the non-persistent memory and, during an idle period of the computer system;

compressing the uncompressed data from the persistent memory to form new compressed data,

allocating a bucket having a variable size related to the size of the new compressed data, and

storing the new compressed data in the bucket in the non-persistent memory.

4. The method as claimed in claim 1 comprising:

providing uncompressed data in a memory selected from a group consisting of a processor cache, virtual memory, and a combination thereof;

determining when the compressed data is not present in the non-persistent memory with a write allocation policy in effect and;

compressing the uncompressed data from the memory to form new compressed data,

allocating a bucket having a variable size related to the size of the new compressed data, and

storing the new compressed data in the bucket in the non-persistent memory.

5. The method as claimed in claim 1 comprising:

determining when the compressed data is present in the non-persistent memory with a write invalidate policy in effect and;

freeing the compressed data in the non-persistent memory.

6. A method for memory operation in a computer system, comprising:

determining when compressed data is present in compressed cache and;

identifying buckets occupied by the compressed data and compression algorithm used to compress the compressed data,

maintaining an identity of the buckets, a range of the compressed data, and the compression algorithm used,

decompressing the compressed data as decompressed data, and providing the decompressed data from the compressed cache for processing; and

determining when the compressed data is not present in the compressed cache and;

providing uncompressed data from the persistent memory for processing.

7. The method as claimed in claim 6 comprising:

determining when the compressed data is not present in the compressed cache and;

selecting a compression algorithm after receiving the uncompressed data from the persistent memory,

predicting a size of the uncompressed data as new compressed data, and

processing the uncompressed data based on the predicted size by processing from a group consisting of compressing the uncompressed data to form the new compressed data and storing the new compressed data in a compressed cache, storing the uncompressed data in the compressed cache without compression, storing the uncompressed data in a buffer cache without compression, and a combination thereof.

8. The method as claimed in claim 6 comprising:

determining when the compressed data is not present in the compressed cache and selecting a compression algorithm after receiving the uncompressed data from the persistent memory,

predicting a size of the uncompressed data as new compressed data based on the compression algorithm, and

processing the uncompressed data during an idle period of the computer system based on the predicted size by processing from a group consisting of compressing the uncompressed data to form the new compressed data and storing the new compressed data in a compressed cache, storing the uncompressed data in the compressed cache without compression, storing the uncompressed data in a buffer cache without compression, and a combination thereof.

9. The method as claimed in claim 6 comprising:

determining when the compressed data is not present in the compressed cache with a write allocation policy in effect and;

selecting a compression algorithm appropriate for the uncompressed data,

compressing the uncompressed data,

allocating buckets in the compressed cache based on a size of the compressed data, and

storing the compressed data in the allocated buckets; and

determining when the compressed data is not present in the compressed cache with a write allocation policy not in effect.

10. The method as claimed in claim 6 comprising:

determining when the compressed data is present in the compressed cache with a write invalidate policy in effect and;

freeing the compressed data in a bucket in the compressed cache; and

determining when the compressed data is present in the compressed cache with the write invalidate policy not in effect and;

decompressing the compressed data contained in the bucket in the compressed cache to form uncompressed data,

writing the uncompressed data into a decompression buffer,

compressing the decompressed data to form new compressed data,

allocating or freeing buckets based on a difference in length of the new compressed data and the compressed data, and

storing the new compressed data in the bucket in the compressed cache.

11. A computer system comprising:

a processor;

a persistent storage device;

a main memory connected to the processor and the persistent storage device, the main memory including;

a compressed cache for storing data retrieved from the persistent storage device after compression; and

an operating system including;

a plurality of software modules for accessing the persistent storage device, the plurality of software modules interconnected, and

a filter driver for managing memory capacity of the compressed cache, the filter driver interconnected between two of the plurality of software modules.

12. The computer system as claimed in claim 11 including:

an interface connected to the filter driver for transparently conducting operations between the two of the plurality of the software modules.

13. The computer system as claimed in claim 11 wherein:

the main memory includes a buffer cache connected to the compressed cache for storing data retrieved from the persistent storage device without compression.

14. The computer system as claimed in claim 11 wherein the plurality of software modules includes:

a system call interface module;

a file system module connected to the system call interface module;

a logical volume manager module connected to the file system module; and

a device driver module connected to the logical volume manager module.

15. The computer system as claimed in claim 11 wherein:

the filter driver is configured to cause the operating system to allocate memory capacity between the compressed cache and the buffer cache.

16. The computer system as claimed in claim 11 wherein the compressed cache includes:

a first plurality of buckets, each of the first plurality of buckets includes a memory space of m bytes; and

a second plurality of buckets, each of the second plurality of buckets includes a memory space of n bytes wherein m and n are integers and m is not equal to n.

17. The computer system as claimed in claim 15 wherein:

the filter driver is configured to free the first plurality of buckets and the second plurality of buckets based on a free-up policy.

18. A computer system comprising:

a processor;

a persistent storage device;

a main memory connected to the processor and the persistent storage device, the main memory including;

a compressed cache for storing uncompressed data retrieved from the persistent storage device as compressed data, and

a buffer cache connected to the compressed cache for storing uncompressed data retrieved from the persistent storage device as uncompressed data; and

an operating system including;

a plurality of software modules for accessing the persistent storage device, the plurality of software modules being organized in a multi-layer structure, and

a filter driver for managing memory capacity of the compressed cache, the filter driver interconnected between two of the plurality of software modules.

19. The computer system as claimed in claim 18 including:

an interface connected to the filter driver for transparently conducting operations between the two of the plurality of the software modules for the filter driver.

20. The computer system as claimed in claim 18 wherein:

the main memory includes a virtual memory for storing computer programs during execution by the operating system.

21. The computer system as claimed in claim 18 wherein the plurality of software modules includes:

a system call interface module;

a file system module connected to the system call interface module;

a logical volume manager module connected to the file system module; and

a device driver module connected to the logical volume manager module.

22. The computer system as claimed in claim 18 wherein:

the filter driver is configured to cause the operating system to allocate additional memory capacity for the compressed cache from the buffer cache and to return unneeded memory capacity to the buffer cache.

23. The computer system as claimed in claim 18 wherein the compressed cache includes:

a first plurality of buckets, each of the first plurality of buckets includes a memory space of m bytes; and

a second plurality of buckets, each of the second plurality of buckets includes a memory space of n bytes wherein m and n are integers and m is not equal to n.

24. The computer system as claimed in claim 23 wherein:

the filter driver is configured to free up the first plurality of buckets and the second plurality of buckets based on policies selected from a group consisting of least-recently-used, least-frequently-used, and a combination thereof.