Method of storing data in distributed manner based on technique of predicting data compression ratio, and storage device and system using same

Patent metadata

Field	Value
Publication number	US-9606750-B2
Application number	US-201414446806-A
Country	US
Kind code	B2
Filing date	Jul 30, 2014
Priority date	Nov 25, 2013
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

Abstract

A method of storing data in a distributed manner based on data compression ratio prediction, and a mass storage device and system using the method are disclosed. The device includes a compression ratio predicting unit, a compressing unit, and a control unit. When an address and first unit sized data are received, the compression ratio predicting unit estimates the predicted compression ratio of the first unit sized data. The compressing unit generates compressed data. The control unit calculates the benefit of compression based on at least the estimated predicted compression ratio, stores the compressed data in a first storage area if the calculated benefit of compression is higher than a predetermined benefit threshold value, and stores the first unit sized data in the second storage area if the calculated benefit of compression is equal to or lower than the predetermined benefit threshold value.

First claim

What is claimed is:

1. A method of distributively storing data in a mass storage device having logically or physically defined first and second storage areas, based on data compression ratio prediction, the method comprising:
receiving an address and a first unit sized data, together with a write command, from a host device;
estimating a predicted compression ratio of the first unit sized data, based on a Shannon byte entropy;
calculating a benefit of compression, based on the predicted compression ratio;
comparing the calculated benefit of compression with a predetermined benefit threshold value, and
in response to the calculated benefit of compression being higher than the predetermined benefit threshold value, compressing the first unit sized data so as to store the compressed data in the first storage area, and
in response to the calculated benefit of compression being equal to or lower than the predetermined benefit threshold value, storing the first unit sized data in the second storage area;

wherein the predicted compression ratio is estimated using the following predicted compression ratio estimation formula:
C ( X )= H ( X ) c ;

wherein C(X) is a predicted compression ratio of sample data X,
c is a predicted compression index that is empirically given, based on a compression method, and
H(X) is the Shannon byte entropy of the sample data X, estimated using the following formula:

H
⁡

(
X
)

=

⁢

-

∑
i

⁢

P
⁡

(

x
i

)

⁢

log
b

⁢

P
⁡

(

x
i

)

=

⁢

-

∑
i

⁢

n
i

N

⁢

log
b

⁢

n
i

N

;

=

⁢

log
b

⁢
N

-

1
N

⁢

∑
i

⁢

n
i

⁢

log
b

⁢

n
i

wherein sample data X includes a data symbol x i ,
n i is the frequency of appearance of each data symbol x i in the sample data X,
N is an overall frequency of appearance of all of the data symbols in the sample data X, and
P(x i ) is the probability mass function of the data symbol x i .

2. A method of distributively storing data in a mass storage device having logically or physically defined first and second storage areas, based on data compression ratio prediction, the method comprising:
receiving an address and a first unit sized data, together with a write command, from a host device;
estimating a predicted compression ratio of the first unit sized data, based on a Shannon byte entropy;
calculating a benefit of compression, based on the predicted compression ratio;
comparing the calculated benefit of compression with a predetermined benefit threshold value, and
in response to the calculated benefit of compression being higher than the predetermined benefit threshold value, compressing the first unit sized data so as to store the compressed data in the first storage area, and
in response to the calculated benefit of compression being equal to or lower than the predetermined benefit threshold value, storing the first unit sized data in the second storage area;

wherein the predicted compression ratio is estimated using the following predicted compression ratio estimation formula:
C ( X )=2 H(x) 2 −1,

wherein C(X) is the predicted compression ratio of sample data X, and H(X) is the Shannon byte entropy of the sample data X.

3. The method of claim 1 , wherein the predicted compression ratio is estimated by referring to a look-up table that is constructed by mapping values of Shannon entropy to values of the predicted compression ratio based on actual compression ratio obtained using the compression method.

4. The method of claim 1 , wherein the benefit of compression is calculated, based on at least one of:
a remaining storage capacity of the first storage area, which is configured to store: compressed data, an

Assignees

• Univ Sungkyunkwan Res & Bus
• Res And Business Found Sungkyunkwan Univ

Inventors

• Seo Eui Seong
• Seo Bon Keun
• Kim Hyeon Hwa

Classifications

• G06F3/0685 Primary

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

• G06F3/0643

  Management of files · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/068

  Hybrid storage device · CPC title

• G06F3/064

  Management of blocks · CPC title