In-place data compression with small working memory

Patent metadata

Field	Value
Publication number	US-2018293028-A1
Application number	US-201715480302-A
Country	US
Kind code	A1
Filing date	Apr 5, 2017
Priority date	Apr 5, 2017
Publication date	Oct 11, 2018
Grant date	—

Abstract

Method and apparatus for performing in-place compression is provided. The in-place compression system transfers source data from a partition of a memory to a data buffer based on a read address. Compressed data is created by referencing the source data stored in the data buffer. The system writes the compressed data to the memory partition based on a write address. When the write address points at an address location that stores source data that has not been transferred to the data buffer, the system overwrites the compressed data stored in the memory partition with the source data stored in the data buffer.

First claim

What is claimed is:

1 . A computer-implemented method comprising:
transferring source data from a partition of a memory to a data buffer based on a read address; creating compressed data by referencing the source data stored in the data buffer; writing the compressed data to the memory partition based on a write address; overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points to an address location that stores source data that has not been transferred to the data buffer.

2 . The computer-implemented method of claim 1 , wherein the write address points to an address location that stores source data that has not been transferred to the data buffer when the write address and the read address are the same.

3 . The computer-implemented method of claim 1 , wherein the data buffer is equal in size to the memory partition.

4 . The computer-implemented method of claim 1 , further comprising:
generating a compression header prior to retrieving data from the memory partition; storing the compression header in an overflow buffer; transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

5 . The computer-implemented method of claim 4 , wherein a size of the overflow is based on a size of a compression header.

6 . The computer-implemented method of claim 4 , wherein the overflow buffer and the data buffer reside in a free area of the memory.

7 . The computer-implemented method of claim 1 , wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address; writing the compressed data at an overflow buffer instead of the memory partition when the write address is equal to the read address; and transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

8 . The computer-implemented method of claim 1 , further comprising overwriting the compressed data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio.

9 . The computer-implemented method of claim 8 , wherein the compression ratio is determined based on the read address and the write address.

10 . A computing device comprising:
a set of one or more processing units; and a storage device storing a set of instructions, wherein an execution of the set of instructions by the set of processing units configures the computing device to perform acts comprising: transferring source data from a partition of a memory to a data buffer based on a read address; creating compressed data by referencing the source data stored in the data buffer; writing the compressed data to the memory partition based on a write address; and overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points to an address location that stores source data that has not been transferred to the data buffer.

11 . The computing device of claim 10 , wherein the write address points to an address location that stores source data that has not been transferred to the data buffer when the write address and the read address are the same.

12 . The computing device of claim 10 , wherein the execution of the set of instructions further configures the computer device to perform acts comprising:
generating a compression header prior to retrieving data from the memory partition; storing the compression header in an overflow buffer; transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

13 . The computing device of claim 12 , wherein the overflow buffer and the data buffer reside in a free area of the memory.

14 . The computing device of claim 10 , wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address; writing the compressed data at an overflow buffer instead of the memory partition when the write address is equal to the read address; and transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

15 . The computing device of claim 14 , wherein the overflow buffer is smaller in size than the data buffer.

16 . The computing device of claim 10 , wherein the execution of the set of instructions further configures the computer device to perform acts comprising overwriting the compressed version of the data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio, wherein the compression ratio is determined based on the read address and the write address.

17 . A computer program product comprising:
one or more non-transitory computer-readable storage device and program instructions stored on at least one of the one or more non-transitory storage devices, the program instructions executable by a processor, the program instructions comprising sets of instructions for: transferring source data from a partition of a memory to a data buffer based on a read address; creating compressed data by referencing the source data stored in the data buffer; writing the compressed data to the memory partition based on a write address; and overwriting the compressed data stored in the memory partition with the source data stored in the data buffer when the write address points at an address location that stores source data that has not been transferred to the data buffer.

18 . The computer-implemented method of claim 17 , wherein writing the compressed data to the memory partition comprises:
writing the compressed data into the memory partition when the write address lags behind the read address; writing the compressed data at an overflow buffer and not the memory partition when the write address is equal to the read address; and transferring the data stored in the overflow buffer to the memory partition when the write address lags behind the read address.

19 . The computer-implemented method of claim 18 , further comprising:
generating a compression header prior to retrieving data from the memory partition; storing the compression header in an overflow buffer; transferring the compression header from the overflow buffer to the memory partition after enough source data has been transferred to the data buffer from the memory partition.

20 . The computer-implemented method of claim 17 , further comprising overwriting the compressed version of the data stored in the memory partition with the data stored in the data buffer when, upon completion of the compress data into the memory partition, a compression ratio between a size of the compressed data and a size of the source data of the memory partition is more than a threshold ratio, wherein the compression ratio is determi

Assignees

• IBM

Inventors

• Abali Bulent
• Blaner Bartholomew
• Crumley Paul G
• Franke Hubertus

Classifications

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0661 Primary

  Format or protocol conversion arrangements · CPC title

• H03M7/30 Primary

  Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction · CPC title

• H03M7/3091

  Data deduplication · CPC title