JPH07210324A - Storage device - Google Patents

Abstract

(57) [Summary] [Object] To provide a storage device capable of selecting an optimum data compression method in terms of compression rate and processing speed for each input data. A sector number estimation circuit 115, 121, 127 and timers 116, 122, 128 determine the number of data blocks (sectors) and processing time required for storing compressed data for each of a plurality of compression circuits, and calculate the compression circuit. The selecting unit 107 selects one circuit having the shortest processing time among the compression circuits having the minimum required number of data blocks. [Effect] When there are a plurality of data compression methods that minimize the number of data blocks, the fastest data compression method is selected from among them, so that the compression processing speed can be improved without impairing the capacity reduction effect of the data compression. it can.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a storage device, and more particularly to a disk control device having a compression function.

[0002]

2. Description of the Related Art Due to the recent expansion of online services in banks and securities, the amount of data stored in a secondary storage device such as a magnetic disk device tends to increase rapidly.
As a result, there is an increasing need to efficiently store data in the secondary storage device. As one of the solutions, a secondary storage device that stores data after compressing the data has been proposed and put into practical use. As a specific example, the disk array product Iceb of STK
erg is known.

Data compression is a data coding method for the purpose of reducing the capacity of data to be compressed. A plurality of data compression methods such as a run length method, an Erzet (LZ) method, and a Huffman method are known. Specific examples of using each data compression method will be described below.

Hitachi magnetic tape storage devices H-6485-1 and H-6481-1 are known as product examples in which data compression by the Run Length method is applied to a secondary storage device.
As a software tool for data compression, LZ
LHA (LHA), which uses a compression method that combines the Huffman method and the Huffman method, is known. LHA is freeware and is widely used by personal computer users. Data decompression method unique to each data compression method,
That is, there is a data decoding method for returning compressed data to uncompressed data. There is a compression rate as an index of data volume reduction due to compression, which is given by Equation 1.

[0005]

## EQU00001 ## (Compression rate) = (Data length before compression) / (Data length after compression) * 100 [%] (1) The compression rate differs depending on each data compression method and the compression target data. Utilizing this property, a method of selecting one from a plurality of data compression methods is disclosed in JP-A-4-241681 and JP-A-4-241681.
No. 4-223717. By using this method, it is possible to reduce the storage capacity of the compressed data as compared with the case of using the single data compression method.

In this method, a plurality of data compression methods are applied to one compression target data to measure the compression rate,
Select the data compression method that maximizes the compression rate. An identifier indicating the selected data compression method is added to the compressed data. When decompressing data, the identifier is referred to, and the decompressed data is decompressed using a data decompression method corresponding to the data compression method indicated by the identifier.

[0007]

In the above prior art, only the compression rate is focused on as the selection condition of the data compression method, and the processing speed of data compression / decompression is not taken into consideration. Regarding the compression rate and the processing speed for each data compression method, the processing speed is slower as the data compression method having a higher compression rate and faster as the data compression method having a lower compression rate.

On the other hand, in a secondary storage device, which is typified by a magnetic disk device and which inputs and outputs data in units of data blocks, data is divided and stored in fixed-length data blocks. The data block is a data unit corresponding to one sector (about 512 bytes) in the example of the magnetic disk device. If, as a result of the data division, surplus data of less than the data block length is generated, the secondary storage device needs to allocate another data block for storing the surplus data.

Therefore, when a plurality of data compression methods are used in the secondary storage device, the difference in the compressed data length between the respective data compression methods is absorbed in the data block length, and the data necessary for storing the compressed data is stored. The number of blocks may be equal. In this case, even if the data compression method with the highest compression rate is selected, there is a problem in that the time required for data compression / decompression processing to obtain a high compression rate is increased, and the data storage area is not saved. .

[0010]

In order to solve the above-mentioned problems, according to the present invention, data compression / decompression is performed by one or more different compression / decompression algorithms for a secondary storage device that inputs / outputs data in units of data blocks. A means for decompressing is provided, a part of the input data is compressed by the parallel operation of the respective data compression functions, and a means for estimating the number of data blocks necessary for storing the compressed data and measuring the compression time is provided. A means for selecting an optimum data compression method is provided based on the obtained required number of data blocks and the compression time. Further, means for compressing the remaining portion of the data to be compressed by the selected data compression method and storing it in the secondary storage device is provided.

[0011]

By selecting the optimum data compression method based on the number of data blocks required to store the compressed data and the compression processing time, the compression processing speed can be improved without impairing the capacity reduction effect of the data compression. It is possible.

[0012]

【Example】

(Embodiment 1) FIG. 1 shows a block diagram of embodiment 1 of the present invention. The storage device controller 102 is connected to the storage device 103 by the disk control circuit 110. The storage device 103 is composed of a plurality of disk drives 104. The disk drive 104 is called a sector 512
Input and output in units of byte data blocks. Further, the storage device control unit 102 uses the host interface circuit 105.
Is connected to the host processor 101. The host interface circuit 105 includes a data buffer 106, and is 4 KB between the host interface circuit 105 and the host processor 101.
Transfer data in units. The storage device control unit 102 includes a cache memory 109, a compression circuit selection unit 107, an expansion circuit selection unit 108, and three compression / expansion modules 111 and 1.
It is equipped with 17,123.

The compression / expansion module 111 is a compression circuit 1.
12, decompression circuit 113, compressed data output control unit 11
4, a sector number estimation circuit 115, a timer 116, an intermediate buffer 207, an intermediate buffer data counter 211, a sector number register 219, and a compression circuit monitor 209. Compression / expansion module 117 and compression / expansion module 12
3 has the same configuration as the compression / expansion module 111.

The compression / expansion algorithm of the compression / expansion module 111 has a compression processing speed of 20 MB / s Run Leng.
th method. The compression / expansion algorithm of the compression / expansion module 117 is the LZ method with a compression processing speed of 10 MB / s. The compression / expansion algorithm of the compression / expansion module 123 is an LZ-Huffman composite compression method with a compression processing speed of 4 MB / s. The Run Length method is the simplest and fastest compression algorithm among the above three compression algorithms, but the compression rate is the lowest. The LZ method is moderate in processing speed and compression ratio among the above three compression algorithms. The LZ-Huffman composite compression method is a method that combines two compression methods, the LZ method and the Huffman method, and has the highest compression rate of the above three compression algorithms, but the slowest processing speed.

Compression circuit selection unit 107, expansion circuit selection unit 1
Details of the configurations of the 08 and compression / expansion modules 111, 117, and 123 will be described later.

In the first embodiment, the sector length of the disk drive 104 is 512 bytes, the data transfer unit between the host processor 101 and the host interface circuit 105 is 4 KB, the number of different compression / expansion circuits is three, and the compression algorithm is Run Length method, LZ method, LZ-
The Huffman composite compression method was used, but it is clear that these configurations are variable.

When writing data, the host processor 10
1 to 4K bytes of write data is data buffer 10
6 is transferred. The host processor 101 also sends a write command to the host interface circuit 105. The host interface circuit 105 sends the compression processing start signal to the compression circuit selection unit 107 and each compression / expansion module 1.
Send to 11, 117, 123. The compression circuit selection unit 107 and each compression / expansion module 111, 117, 123 compress the write data in the data buffer 106 and transfer it to the cache memory 109. Details of operations of the compression circuit selection unit 107 and the compression / expansion modules 111, 117, and 123 will be described later. Next, the host interface circuit 1
05 sends a write signal to the disk control circuit 110.
The disk control circuit 110 writes the compressed data on the cache memory 109 to the disk drive 104.

When reading data, the host processor 10
1 is a read command for the host interface circuit 105
Send to. The host interface circuit 105 sends a read signal to the disk control circuit 110. The disk control circuit 110 reads data from the disk drive 104 and transfers it to the cache memory 109. Next, the host interface circuit 105 sends the decompression process start signal to the decompression circuit selection unit 108 and each compression / decompression module 111, 1.
Send to 17,123. Expansion circuit selection unit 108 and each compression
The decompression modules 111, 117, 123 decompress the read data on the cache memory 109 and transfer the decompressed data to the data buffer 106. Expansion circuit selection unit 108 and each compression
Details of the operations of the decompression modules 111, 117, 123 will be described later. The host interface circuit 105 transfers the read data on the data buffer 106 to the host processor 101.

FIG. 2 is a diagram showing the details of the sector number estimating circuit 115 constituting the compression / expansion module 111.
The sector number estimation circuit 115 is composed of arithmetic circuits 211 to 218 for calculating the number of sectors.

The host interface circuit 105 sends the compression start signal 204, which means the start of the compression process, to the compression circuit 112, the intermediate buffer data counter 211, and the timer 1.
Send to 16. Upon receiving the compression start signal 204, the compression circuit 112 receives the write data from the data buffer 106, compresses it, and transfers it to the intermediate buffer 207. The intermediate buffer data counter 211 that has received the compression start signal 204 is cleared to 0 and starts counting the post-compression data length on the intermediate buffer 207. The number of sectors required to store the compressed data is determined by the intermediate buffer data counter 21.
Based on the value of 1, it is calculated by the arithmetic circuits 211 to 218 and stored in the sector number register 219. Upon receiving the compression start signal 204, the timer 116 is cleared to 0 and the measurement of the compression processing time is started.

The estimation of the number of sectors and the measurement of the compression processing time are performed by
This is performed for the first 512 bytes of the 4 Kbytes of write data. The compression circuit monitor 209 uses the compression circuit 112.
The progress status of the compression process is monitored, and when the compression process up to 512 bytes is completed, the value of the timer 116 and the value of the sector number register 216 are sent to the compression circuit selection unit 107. The compression circuit 112 continues the compression process.

The number of sectors required to store the compressed data is
The data length after compression of the entire write data of 4 Kbytes,
It is obtained by dividing the sector size by 512 bytes. In the first embodiment, out of the compressed data length of 512 bytes, which is one-eighth of the 4 K-byte write data,
Estimate the number of sectors required to compress and store the entire data.
Therefore, the data length after compression is divided by 64 bytes, which is 1/8 of the sector size of 512 bytes. In the sector number estimation circuit 115, the intermediate buffer data counter 211
Quotient 215 and remainder 21 divided by the constant value 64 (212)
Ask for 4. If the remainder 214 is equal to the constant value 0 (213), the number of sectors required to store the compressed data is the quotient 215.
It is estimated that the quotient 215 is equal to, and the quotient 215 is selected by the data selector 218 and stored in the sector number register 219. If the remainder 214 is not equal to the constant value 0 (213), it is estimated that one sector is needed to store the remainder data, and the value 217 obtained by adding 1 to the quotient 215 is added to the data selector 2.
18 and stores it in the sector number register 219.

In data compression, the compression rate generally varies depending on the content of input data. If the compression ratio of the leading part of the input data is higher than the compression ratio of the remaining part, when the required number of sectors is estimated by the above means, the estimated value may be lower than the actual required number of sectors. Therefore, in the estimation of the required number of sectors, it is preferable to perform the calculation in consideration of the margin in which the fluctuation of the compression rate is taken into consideration. In the estimation of the required number of sectors in the first embodiment, it is easy to make a change to take the above margin into consideration. That is, the intermediate buffer data counter 2
A margin can be added to the estimated value of the required number of sectors by dividing the 11 value by a value (for example, 60) smaller than 64 bytes corresponding to 1/8 of the 512-byte sector size.

FIG. 3 is a diagram showing details of the compression circuit selection unit 107. The compression circuit selection unit 107 is the data selector 3
05, a compression header addition circuit 306, a required sector number comparison circuit 307, a compression processing time comparison circuit 308, and a selection signal transmission circuit 309.

The compression circuit selection unit 107 determines the compression processing time in the compression / expansion module having the minimum required number of sectors based on the required number of sectors and the compression processing time obtained for each compression / expansion module 111, 117, 123. Selects the shortest one and transfers the compressed data to the cache memory 109. However, if the minimum value of the required number of sectors is equal to or larger than the number of sectors required to store the data without compressing it, there is no point in compressing the data. In this case, data compression is not performed and the contents of the data buffer 106 of the host interface circuit 105 are directly transferred to the cache memory 109.

In the first embodiment, a 2-bit compression header is added to the head of the data transferred to the cache memory 109 as an identifier indicating which compression / expansion module has been used for compression or not. The compressed header value “0” indicates that the data is not compressed. The compressed header values “1”, “2”, and “3” represent the data after compression of the compression / expansion modules 111, 117, and 123, respectively.

FIG. 4 is a flow chart showing the process of the compression circuit selection unit 107. In all the compression / expansion modules 111, 117, 123, the processing of the compression circuit selection unit 107 is started when the compression of the first 512 bytes of the write data is completed. Processing step 402
At 1, the required sector number comparison circuit 1307 obtains the values of the sector number register 219, the sector number register 314, and the sector number register 319. The value of each sector number register represents the number of sectors required when the write data is compressed / stored using each compression / expansion module.

In processing step 403, it is determined whether or not the write data is compressed. Specifically, the required sector number comparison circuit 307 determines whether or not all the values in the respective sector number registers are a constant value 9 or more. The constant value 9 is the number of sectors when data is stored without compression. When data is stored without being compressed, 8 sectors are required to store 4 KB uncompressed data, and 1 sector is required to store 2 bits of the compressed header.

If the determination result of processing step 403 is false, processing step 40 for selecting a compression / expansion module.
Go to 4. In processing step 404, the required sector number comparison circuit 307 checks the minimum value of each sector number register and selects the compression / decompression module that minimizes the number of sectors required to store the compressed data. There are three 1-bit signal lines between the required sector number comparison circuit 307 and the compression processing time comparison circuit 308. Each signal line corresponds to each compression / expansion module. Only the signal line corresponding to the compression / expansion module with the minimum number of sectors is turned on. When there are a plurality of compression / expansion modules having the smallest and equal number of sectors, all signal lines corresponding to the corresponding compression / expansion modules are turned on.

In processing step 405, it is checked whether or not there are a plurality of compression / decompression modules having the minimum number of sectors. The compression processing time comparison circuit 308 checks the number of ON signal lines of the three signal lines from the required sector number comparison circuit 307. If the number of ON signal lines is only one, there is only one compression / expansion module that minimizes the number of sectors. The compression / expansion module corresponding to the signal line is selected, and the process proceeds to processing step 408. If there are a plurality of ON signal lines, there are a plurality of compression / decompression modules that minimize the number of sectors, and the process proceeds to processing step 406.

In processing step 406, timer 11
6, the values of the timer 122 and the timer 128 are acquired. The value of each timer represents the compression processing time when the first 512 bytes of the write data is compressed using each compression / expansion module. In the processing step 407, the compression processing time comparison circuit 308 outputs a plurality of compression / compression times with the minimum number of sectors.
Select one of the decompression modules that has the shortest compression processing time. There is one 2-bit signal line between the compression processing time comparison circuit 308 and the selection signal transmission circuit 309. A compression header value indicating the selected compression / expansion module is output to the signal line.

In the processing step 408, the selection signal transmission circuit 309 sends the selected compression / decompression module
Send a circuit selection signal. In processing step 409, the selection signal transmission circuit 309 prompts the compression header addition circuit 306 to transfer the compression header value corresponding to the selected compression / decompression module. The compression header adding circuit 306 transfers the compression header value corresponding to the selected compression / expansion module to the cache memory 109. Processing step 410
In the selection signal transmission circuit 309,
Data selector 3 after compressing data from decompression module
The selection is made by 06, the data is transferred to the cache memory 109, and the processing is ended.

If the judgment result of the processing step 403 is true, the write data is not compressed and the processing step 41 is executed.
Go to 1. All three signal lines between the required sector number comparison circuit 307 and the compression processing time comparison circuit 308 are turned off.
The compression processing time comparison circuit 308 sends a compression header value of “0” to the selection signal transmission circuit 309 when all three signal lines are off.
Is output. In processing step 411, the selection signal transmitting circuit 309 prompts the compressed header adding circuit 306 to transfer the compressed header value “0”. Compression header addition circuit 306
Transfers the compressed header value “0” to the cache memory 109. In processing step 412, the selection signal transmission circuit 309 selects the data in the data buffer 106 of the host interface circuit 105 by the data selector 305, transfers it to the cache memory 109, and ends the processing.

FIG. 5 is a diagram showing details of the compressed data output control unit 114. The post-compression data output control unit 114 includes a data output switching unit 512, a compression end flag 510, and an output data counter 511. Post-compression data output control unit 120, post-compression data output control unit 126
Has a configuration similar to that of the compressed data output control unit 114.

The host interface circuit 105 sends a compression start signal 204, which means the start of compression processing, to the data output switching unit 512, the compression circuit 112, the intermediate buffer data counter 509, the output data counter 511, and the compression end flag 510. . Upon receiving the compression start signal 204, the data output switching unit 512 sets the data selector 507 so that the output destination of the compression circuit 112 is the intermediate buffer 207. The compression circuit 112, which receives the compression start signal 204, compresses the write data in the data buffer 106 and transfers it to the intermediate buffer 207 until either the compression stop signal 514 is received from the data output switching unit 512 or the compression processing is completed. To do. Upon receiving the compression start signal 204, the intermediate buffer data counter 509 and the output data counter 511 are cleared to 0. The compression end flag 510 receiving the compression start signal 204 is reset and set when the compression end signal 506 is received from the compression circuit 112.

FIG. 6 is a flow chart showing the process of the compressed data output control section. Compression circuit selection unit 10
The data output switching unit 512 which receives the circuit selection signal 329 from step 7 checks in step 602 whether or not the compression end flag 510 is set. If it is not set, the process proceeds to the processing step 603, and the compression stop signal 514 is sent. In processing steps 604 to 607, the data selector 516 transfers the compressed data in the intermediate buffer 207 to the compression circuit selection unit 107. That is, until the values of the intermediate buffer data counter 509 and the output data counter 511 become equal, the intermediate buffer 207
The output data counter 511 is incremented while the data of 1 is transferred.

In processing step 608, it is checked again whether the compression end flag 510 is set. If it is set, the process is ended, and if it is not set, the process proceeds to the processing step 609, and the compression restart signal 515 is sent to the compression circuit 112. In processing step 610, the compression circuit 112, which has restarted the compression processing, compresses the write data in the data buffer 106, and the data selectors 507, 51
The compressed data is transferred to the compression circuit selection unit 107 through 6.

The post-compression data output control unit 120 and the post-compression data output control unit 126 are the post-compression data output control unit 11
The same operation as 4 is performed.

FIG. 7 is a diagram showing the details of the expansion circuit selection unit 108. The decompression circuit selection unit 108 includes a compression header read circuit 711 and two data selectors 709 and 710.

The host interface circuit 105 sends a decompression start signal 702 indicating the start of decompression processing to the decompression circuit 113, the decompression circuit 119, the decompression circuit 125, and the compression header read circuit 711. Expansion start signal 702
The compressed header read circuit 711 that received the data reads the compressed header from the cache memory 109 and checks the read value. When the compressed header value is “0”, the data is stored without being compressed, so the data selectors 709 and 710 expand the contents of the cache memory 109 into the decompression circuits 113, 119 and 1.
The data is transferred to the data buffer 106 without passing 25. When the compressed header value is “1”, “2”, or “3”, the data is compressed and stored, so the data selector 709,
Reference numeral 710 is an expansion circuit 1 for expanding the contents of the cache memory 109.
Data is transferred to the data buffer 106 through 13, 119 and 125.

FIG. 8 is a diagram showing the flow of write data in the embodiment. The head 512 bytes of 4 KB of write data on the data buffer 106 are compressed by the compression circuit 112,
The data is compressed by 118 and 124, and the compressed data is stored in the intermediate buffers 207, 809 and 810. The optimum compression circuit 118 is selected based on the required number of sectors and the compression time obtained from the compression result. Based on the selection result, the contents of the intermediate buffer 809 are transferred to the cache memory 109, the rest of the write data is also compressed by the compression circuit 118, and then transferred to the cache memory 109.

First, the 512 bytes 804 at the beginning of the data are compressed through the compression circuits 112, 118 and 124 and transferred to the intermediate buffers 207, 809 and 810. The 512-byte data 804 passed through the compression circuit 112 is 31
Compressed to 0 bytes of data 811, the intermediate buffer 20
Stored in 7. The compression processing time is 25.6 μs, and the number of sectors required to store the compressed data is 5. Compression circuit 1
The 512-byte data 804 passed through 18 is compressed into 250-byte data 813 and stored in the intermediate buffer 809. The compression processing time is 51.2 μs, and the number of sectors required to store the compressed data is 4. The 512-byte data 804 passing through the compression circuit 124 is compressed into 200-byte data 815 and stored in the intermediate buffer 810. The compression processing time is 128.0 μs, and the number of sectors required to store the compressed data is 4.

The compression circuits 112 and 118 compress the remaining data 803, and the compressed data 812 and 814 are stored in the intermediate buffers 207 and 809 until the compression circuit 124 having the slowest compression processing speed completes the compression of the first 512 bytes of the data. save. The compression circuit 112 compresses 2048 bytes out of the remaining 3584 bytes 803 and the compressed data 1
Store 230 bytes 812 in the intermediate buffer 112.
The compression circuit 118 compresses 768 bytes out of the remaining 3584 bytes 803, and the compressed data 380 bytes 8
14 is stored in the intermediate buffer 809.

In the compression circuit selection process, the compression time is 5 out of the compression circuits 118 and 124 having the minimum required number of 4 sectors.
The compression circuit 118 of 1.2 μs is selected. First, the compression header adding circuit 306 transfers the compression header “2” (818) to the cache memory 109. Then, 630 bytes (8 bytes) of the compressed data stored in the intermediate buffer 809 are stored.
13, 814) to the cache memory 109.
Next, the remaining 2 of the write data on the data buffer 106
816 (803) is compressed and transferred to the cache memory 109 to complete the compression process. The length of the compressed data 817 on the cache memory is 2040B in total, and the compressed data 817 including the compressed header 818 fits in 4 sectors.

(Embodiment 2) FIG. 9 shows a block diagram of Embodiment 2 of the present invention. Host interface circuit 105 of storage device controller 102, compression / expansion module 11
The configurations of 1, 117, 123, the compression circuit selection unit 107, the expansion circuit selection unit 108, and the cache memory 109 are the same as those in the first embodiment. The storage device controller 102 is connected to the storage device 103 by four disk control circuits 904, 905, 906 and 907. The disk control circuit 904 has a data drive 908, the disk control circuit 905 has a data drive 909, the disk control circuit 906 has a data drive 910, and the disk control circuit 907 has an EC.
A C (Error Correcting Code) drive 911 is connected.

When writing data, the required sector number calculation circuit 901 calculates the number of sectors required for storage from the compressed data length on the cache memory 109, and the data distribution circuit 90.
Inform 2 of the results. The data distribution circuit 902 divides the compressed data on the cache memory 109 into sector units, and the disk control circuits 904, 905, 906 and ECC
It is distributed to the generation circuit 903. The ECC generation circuit 903 generates an ECC from the data passed from the data distribution circuit 902 and transfers it to the disk control circuit 907. The disk control circuits 904, 905, 906 and 907 operate the data drives 908, 909, 910 and the ECC drive 911 in parallel to write the data on the disk control circuit to each disk drive at the same time.

When reading data, the disk control circuit 90
4, 905 and 906 are data drives 908 and 90
The data is read out from 9, 910 and the data combining circuit 91
Transfer to 2. The data combination circuit 912 combines the data divided and stored in each disk drive and transfers the combined data to the cache memory 109.

FIG. 10 is a diagram showing the flow of write data in the second embodiment. The flow of write data between the host processor 101 and the cache memory 109 is the same as that in the first embodiment, and will be omitted. There is compressed data on the cache memory 109, and as a result of calculating the required number of sectors, it has been found that an area of 5 sectors is required for storage.
The data distribution circuit 902 divides the compressed data into five data blocks 100 to 1005, and writes the data into each data drive twice. A group of data blocks simultaneously written is called an ECC group, and an ECC is generated for each ECC group.

First, the data blocks 1001 and 100
The ECC group 1008 composed of 2,1003 is written. The data distribution circuit 902 transfers the data block 1001 to the disk control circuit 904, the data block 1002 to the disk control circuit 905, and the data block 1003 to the disk control circuit 906 from the cache memory 109. Data block 1
001, 1002, 1003 are transferred to the ECC generation circuit 903. The ECC generation circuit 903 uses the data block 10
ECC 1006 is generated from 01, 1002, 1003 and transferred to the disk control circuit 907. Disk control circuit 904
Data block 1001 to the data drive 908,
The disk control circuit 905 writes the data block 1002 to the data drive 909, the disk control circuit 906 writes the data block 1003 to the data drive 910, and the disk control circuit 907 writes the ECC 1006 to the ECC drive 911.

Next, the ECC group 1009 consisting of the data blocks 1004 and 1005 is written.
The data distribution circuit 902 transfers the data block 1004 from the cache memory 109 to the disk control circuit 904.
The data block 1005 is transferred to the disk control circuit 905. Also, the data blocks 1004 and 1005 are transferred to the ECC generation circuit 903. ECC generation circuit 90
3 generates ECC 1007 from the data blocks 1004 and 1005 and transfers it to the disk control circuit 907. The disk control circuit 904 writes the data block 1004 to the data drive 908, the disk control circuit 905 writes the data block 1005 to the data drive 909, and the disk control circuit 907 writes the ECC1007 to the ECC drive 911.

In the second embodiment, since all disk drives operate simultaneously for data input / output to / from the storage device 103, the data drives of the ECC group 1009 are
Meaningless empty data 1010 is written in the sector 909.

In the second embodiment, the range of the number of sectors required to store the compressed data is 1-9. The maximum value 9 is the number of sectors when data is stored without compression. When the number of required sectors is 1 to 3, the data storage after compression is performed by one ECC group and one writing. When the required number of sectors is 4 to 6, data storage after compression is performed by writing twice in 2 ECC groups. When the required number of sectors is 7 to 9, data storage after compression is performed by writing 3 times in 3 ECC groups. In the second embodiment, even if a compression / decompression module that requires a smaller number of sectors for storing data after compression is selected, if the number of ECC groups required for storage is the same, the capacity reduction effect by data compression cannot be expected. Therefore, in the second embodiment, one of the compression / decompression modules that minimizes the number of ECC groups required to store the compressed data is selected, which has the shortest compression processing time.

FIG. 11 is a diagram showing an algorithm for selecting a compression circuit in the second embodiment. The compression circuit selection is performed by the compression circuit selection unit 303 as in the embodiment. In the processing step 1102, the sector number register 219 and the sector number register 31 are the same as the processing in the processing step 402.
4. Obtain the contents of the sector number register 319. The value of each sector number register represents the number of sectors required when the write data is compressed and stored in each compression / expansion module. In the processing step 1103, it is checked whether or not there is a compression / expansion module whose number of ECC groups required for storing the compressed data is 1. Specifically, the required sector number comparison circuit 307 checks whether there is a compression / decompression module having a required sector number of 3 or less. If it exists, go to processing step 1105. If it does not exist, processing step 1104.
Go to. In processing step 1104, it is checked whether or not there is a compression / expansion module having the number of ECC groups of 2 required for storing the compressed data. Specifically, the required sector number comparison circuit 307 checks whether there is a compression / decompression module having a required sector number of 6 or less. If it exists, go to processing step 1105, and if it does not exist, processing step 11
Proceed to 11. In processing steps 1005 to 1010, processing similar to processing steps 405 to 410 is performed. One of the compression / expansion modules that satisfies the conditions of the processing steps 1103 and 1104 is selected and the processing time is the shortest, and the data is transferred to the cache memory 109 after compression. In processing steps 1011 to 1012, processing step 411
The processing similar to the steps 412 to 412 is performed, and the data is transferred to the cache memory 109 without being compressed. (Embodiment 3) FIG. 12 is a block diagram of Embodiment 3 of the present invention. Since individual files, which are the constituent units of the file system 1201, are often composed of data of similar formats, the optimum compression method can be determined for each file. In the third embodiment, when writing the data block of the same file, the same compression circuit selection process as in the first or second embodiment is repeated a plurality of times, and as a result, the compression method with the largest number of times is selected as the optimum compression method for the file. To do.

The file system 1201 on the host processor 101 gives a block attribute 1202 to each data block read from or written to the storage device 104. The block attribute 1202 is a unique name or number for each file.
For the data blocks that make up the same file,
The same block attribute 1202 is given.

In the selection history table 1203, the past four most recent compression circuit selection results are recorded for each block attribute 1202. In writing data having the same block attribute, the same compression circuit selection processing as in the first or second embodiment is 4
Only once for each time, the selection result is the selection history table 12
It is recorded in 03. For the remaining three times, the compression / decompression module selected most frequently in the past four times is selected from the selection history recorded in the selection history table 1203, but the selection result is not recorded in the selection history table 1203.

In the first and second embodiments, since the compression / expansion module is selected based on the compression result of a very small part of the data,
It is susceptible to local fluctuations in the data format, and it is easy to make an error in selecting the compression / decompression module. Further, since it is necessary to wait until all the compression / decompression modules finish compressing the first 512 bytes, it takes time to select. In Example 3,
The compression / expansion module can be selected more accurately and at higher speed based on the selection results of the past four most recent times for the data of the same file.

FIG. 13 shows the compression circuit selection unit 10 of the third embodiment.
It is a figure showing the details of No. 7. The compression circuit selection unit 107 includes a selection history table interface circuit 1301. The selection history table interface circuit 1301 searches / updates the selection history table 1203. The selection signal transmission circuit 310 exchanges history information with the selection history table interface circuit 1301. Details of the delivery will be described later. Other configurations are similar to those of the first embodiment.

FIG. 14 is a flow chart showing the process of the compressed data selection circuit 304 of the third embodiment. In processing step 1401, it is checked whether the block attribute 1202 is registered in the selection history table 1203. The host interface circuit 105 passes the block attribute 1202 sent from the host processor 101 to the selection history table interface circuit 1301.
The selection history table interface circuit 1301 determines whether or not the entry of the block attribute 1202 already exists in the selection history table 1203.
Search for 3. If so, processing step 1402
If it does not exist, the process proceeds to processing step 1409.

In processing step 1402, the selection history table interface circuit 1301 reads the selection history 1205 from the selection history table 1203. Selection history 12
05 consists of four selection history records 1207. Each selection history record 1207 has 3 bits, and the selection history 12
05 has a total of 12 bits. The first 1 bit of the selection history record 1207 is a flag indicating whether or not the selection result is recorded in the selection history record 1207. The compressed header value is recorded as the selection result in the latter two bits. Selection history record 12 located on the left in the selection history 1205
As many as 07 selection results are recorded.

In the selection processing step 1403, the selection history table interface circuit 1301 checks the flag of the selection history record 1207 to check whether the number of selection results currently recorded is less than 4. If it is less than 4, processing proceeds to processing step 1410, and if it is 4, processing proceeds to processing step 1404.

In processing step 1404, the selection history table interface circuit 1301 reads the counter 1206 value from the selection history table 1203. counter
1206 is 2 bits and is incremented by 1 each time data is written having the same block attribute. When the maximum value of the counter 1206 is 3, the same compression circuit selection process as in the first or second embodiment is performed, and the value of the counter 1206 is reset to 0. When the counter 1206 is less than the maximum value 3, the selection history table interface circuit 1301 determines the selection history 1205.
Select the compression / decompression module based on the contents of. In processing step 1404, it is checked whether the counter 1206 value is equal to three. If they are equal, the process proceeds to step 1410, and if they are not equal, the process proceeds to step 1406.

At processing step 1406, the selection history table interface circuit 1301 selects the selection history 1205.
The compression / expansion module selected most is selected from the four compression header values recorded in. If there are multiple compression / decompression modules, select the newest one. The selection history table interface circuit 1301 sends the compression header value corresponding to the selected compression / decompression module to the selection signal transmission circuit 310. Processing step 140
7, the selection history table interface circuit 1
301 writes a value obtained by adding 1 to the read counter 1206 value to the selection history table 1203.

At processing step 1408, the selection signal transmitting circuit 310 causes the processing steps 408 to 412 or 1 to proceed.
The post-compression data transfer processing similar to 108 to 1112 is performed. In processing step 1409, the selection history table interface circuit 1301 causes the selection history table 12
03 with a new entry and unregistered block attribute 1202
To the entry. Four selection history records 120
The flag 7 is reset.

In processing step 1410, the selection history table interface circuit 1301 instructs the selection signal transmitting circuit 310 to process steps 402 to 407 or 11.
Prompt to perform the same compression circuit selection processing as 02 to 1107. In processing step 1411, the selection history table interface circuit 1301 sets the compression header value corresponding to the selected compression / decompression module to the selection history 120.
This is recorded in the selection history record 1207 at the left end in the item 5. Specifically, the left 9 bits of the 12-bit selection history 1205 are shifted to the right by 3 bits, the compressed header value is recorded in the leftmost leftmost 3-bit selection history record 1207, and the flag is set. As a result, the selection history record 1207 in the selection history 1205 becomes new from the left. In processing step 1412, the selection history table interface circuit 1301 resets the counter 1206 value to zero.

In the third embodiment, the selection history record 1207
Although the number is 4 and the maximum value of the counter 1206 is 3,
Obviously, these configurations are variable.

(Fourth Embodiment) FIG. 15 shows a block diagram of a fourth embodiment of the present invention. In the fourth embodiment, the length of the empty data block allocated for storing the compressed data is changed according to the compressed data length. As a result, it is possible to eliminate a wasteful area on the disk that occurs when a fixed-length data block is used. Further, since each empty data block is composed of physically consecutive sectors on the disk, the compressed data can be read and written at high speed.

Free data block management table 1510
Then, empty data blocks 1511, 15 of different lengths
12 and 1519 are managed. The free data block list 1501 is a free data block 151 consisting of one sector.
It is a list of 1. Free data block list 1502
Is a list of free data blocks 1512 consisting of two sectors adjacent to each other on the disk. The free data block management table 1510 has up to 9 similar free data block lists. The compression circuit selection unit 107 checks the status of the empty data block management table 1510 and selects the compression / expansion module in which the compressed data fits in the smallest empty data block currently available. If there are a plurality of compression / expansion modules, one of the compression / expansion modules having the shortest compression time is selected. If the compression / decompression module does not exist, the compression / decompression module that can store the compressed data in the larger available data block currently available is selected.

FIG. 16 shows the compression circuit selection unit 10 of the fourth embodiment.
It is a figure showing the details of No. 7. The compression circuit selection unit 107 includes an empty data block reference circuit 1601. The empty data block reference circuit 1601 searches the empty data block management table 1510 and notifies the required sector number comparison circuit 311 of the current status of the empty data block.

FIG. 17 is a flow chart showing the process of the compressed data selection circuit 304 of the fourth embodiment. The compression / decompression module selection is performed by the compression circuit selection unit 303 as in the first embodiment. In the processing step 1701, the contents of the sector number register 219, the sector number register 314, and the sector number register 319 are acquired as in the processing of the processing step 402. Each sector number register value compresses the write data in each compression / expansion module.
Indicates the number of sectors required when saved. Processing step 1
In step 702, the number of sectors i is set to 1 and processing step 1
Proceed to 703.

When the processing flow reaches A ', the process returns to the processing step 1702, 1 is added to the number of sectors i, and then the processing proceeds to the processing step 1703 again. In processing step 1702, the above processing is repeated until the number of sectors i reaches 8. If the processing flow reaches A ′ when the number of sectors i is 8, the process proceeds to processing step 1711. In processing step 1703, the empty data block reference circuit 1601 checks the empty data block list i of the data block management table 1510. The number of sectors i in the free data block list i
If there is a free data block of, processing step 17
04, if not present, return to processing step 1702.

In processing step 1704, the required sector number comparison circuit 311 checks whether or not there is a compression / expansion module in which the number of sectors required for storing the compressed data is i or less. If the compression / expansion module exists, the processing proceeds to processing step 1705, and if it does not exist, processing step 1702.
Return to. In processing steps 1705 to 1710, processing similar to processing steps 405 to 410 is performed. One circuit having the shortest processing time is selected from the compression / expansion modules satisfying the condition of processing step 1704, and the data is transferred to the cache memory 109 after compression. Processing step 1
In steps 711 to 1712, the same processing as that of processing steps 411 to 412 is performed, and the cache memory 1 is not compressed.
Transfer to 09.

[0072]

When there are a plurality of data compression methods that minimize the number of data blocks, the fastest data compression method is selected from among them, so that the compression processing speed is improved without impairing the capacity reduction effect of the data compression. be able to.

[Brief description of drawings]

FIG. 1 is a block diagram of a first embodiment of a storage device having a compression method selection function according to the present invention.

FIG. 2 is a block diagram of a sector number estimation circuit according to the first embodiment.

FIG. 3 is a block diagram of a compression circuit selection unit according to the first embodiment.

FIG. 4 is a flowchart of processing of a compression circuit selection unit according to the first embodiment.

FIG. 5 is a block diagram of a compressed data output control unit according to the first embodiment.

FIG. 6 is a flowchart of processing of a post-compression data output control unit according to the first embodiment.

FIG. 7 is a block diagram of a decompression circuit selection unit according to the first embodiment.

FIG. 8 is a block diagram showing the flow of write data according to the first embodiment.

FIG. 9 is a block diagram of a second embodiment of a storage device having a compression method selection function according to the present invention.

FIG. 10 is a block diagram showing the flow of write data according to the second embodiment.

FIG. 11 is a flowchart of processing of a compression circuit selection unit according to the second embodiment.

FIG. 12 is a block diagram of a storage device having a compression method selection function according to a third embodiment of the present invention.

FIG. 13 is a block diagram of a compression circuit selection unit according to the third embodiment.

FIG. 14 is a flowchart of processing of a compression circuit selection unit according to the third embodiment.

FIG. 15 is a block diagram of a fourth embodiment of a storage device having a compression method selection function according to the present invention.

FIG. 16 is a block diagram of a compression circuit selection unit according to the fourth embodiment.

FIG. 17 is a flowchart of processing of a compression circuit selection unit according to the fourth embodiment.

[Explanation of symbols]

101 ... Host processor, 102 ... Storage device control unit,
103 ... Storage device, 105 ... Host interface circuit, 107 ... Compression circuit selection unit, 108 ... Decompression circuit selection unit, 109 ... Cache memory, 112 ... Compression circuit, 1
13 ... Decompression circuit, 114 ... Compressed data output control unit, 1
15 ... Sector number estimation circuit, 116 ... Timer.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Yoshifumi Takamoto 1-280, Higashi Koigokubo, Kokubunji, Tokyo Inside the Central Research Laboratory, Hitachi, Ltd.

Claims (16)

[Claims] 1. A storage device for inputting and outputting data in fixed-length data block units, comprising one or more different data compression / decompression functions, and the number of data blocks required for storing compressed data for each input data. Select all the data compression / decompression functions that have the smallest number and the same number, and if the selected data compression / decompression function is the only one, compress the input data using the data compression / decompression function, save it, and then select When there are a plurality of data compression / decompression functions that have been compressed, the input data is compressed and stored using one of the data compression / decompression functions that has the shortest compression processing time. And storage device. 2. When the data length after compression of the entire input data can be estimated from the result of partially compressing the input data by several hundred bytes, 1 / n of the input data is several hundred bytes. Set a positive constant n such that the compressed data length of the input data 1 / n is 1 / n of the data block length.
A storage device that estimates the number of data blocks required to store the compressed data of the entire input data from the quotient divided by n. 3. The method according to claim 2, wherein when the number of data blocks is estimated, the divisor of the compressed data length of only the input data 1 / n is set to a value smaller than 1 / n of the data block length by several bytes. A storage device that adds a margin in consideration of the variation of the compression rate for each data. 4. The storage device according to claim 1, wherein when the number of data blocks required for storing the compressed data is equal to or larger than the number of data blocks required for storing the uncompressed data, the uncompressed data is stored in the storage device. 5. A storage device for inputting / outputting data in fixed-length data block units, comprising one or more different data compression / expansion functions, and the number of data blocks required to store compressed data for each input data. Select all data compression / decompression functions that are less than a certain number, and if the selected data compression / decompression function is the only one, compress the input data using the data compression / decompression function, save it, and then select If there are multiple data compression / decompression functions that have been compressed, the data compression / decompression function with the shortest compression processing time among the data compression / decompression functions
A storage device, which stores the input data after compressing the input data using one decompression function. 6. When the data length after compression of the entire input data can be estimated from the result of partially compressing the input data by several hundred bytes, 1 / n of the input data becomes several hundred bytes. Set a positive constant n such as
A storage device that estimates the number of data blocks required to store the compressed data of the entire input data from the quotient obtained by dividing the compressed data length of n by 1 / n of the data block length. 7. The method according to claim 6, wherein when estimating the number of data blocks, the divisor of the compressed data length of only the input data 1 / n is set to a value that is smaller than 1 / n of the data block length by several bytes. A storage device that adds a margin in consideration of the variation of the compression rate for each data. 8. The storage device according to claim 5, wherein when the number of data blocks required for storing the compressed data is equal to or larger than the number of data blocks required for storing the uncompressed data, the uncompressed data is stored in the storage device. 9. The same file according to claim 1, wherein data input / output is performed in fixed-length data block units, one or more different data compression / decompression functions and compression / decompression function selection means are provided. A history of past selection results is recorded for each, and when writing to the same file occurs,
A storage device that selects the most selected compression / expansion function in the past from the history of selection results. 10. When the data length after compression of the entire input data can be estimated from the result of partially compressing the input data by several hundred bytes, 1 / n of the input data becomes several hundred bytes. Set a positive constant n such as
Compressed data length of / n is 1 / n of data block length
A storage device that estimates the number of data blocks required to store the compressed data of the entire input data from the quotient divided by. 11. The method according to claim 10, wherein when estimating the number of data blocks, the divisor of the compressed data length of only the input data 1 / n is set to a value that is smaller than 1 / n of the data block length by several bytes. A storage device that adds a margin in consideration of the variation of the compression rate for each data. 12. The storage device according to claim 9, wherein when the number of data blocks required for storing the compressed data is equal to or larger than the number of data blocks required for storing the uncompressed data, the uncompressed data is stored in the storage device. 13. A storage device for inputting / outputting data in fixed-length data block units, comprising one or more different data compression / expansion functions, the number of empty data blocks of different lengths, and the existence position on the disk. And selecting all the data compression / decompression functions in which the data after compression fits in the smallest available data block currently available based on the management information, and if the selected data compression / decompression function is the only one,
The input data is compressed and saved using the data compression / expansion function, and when there are a plurality of selected data compression / expansion functions, the data compression with the shortest compression processing time among the data compression / expansion functions. After storing the input data after compressing it using the decompression function, and if the data compression / decompression function does not exist, select a data compression / decompression function that allows the compressed data to fit in a larger empty data block in order. Characteristic storage device. 14. When the data length after compression of the entire input data can be estimated from the result of partially compressing the input data by several hundred bytes, 1 / n of the input data becomes several hundred bytes. Set a positive constant n such that the compressed data length of the input data 1 / n is 1 / n of the data block length.
A storage device that estimates the number of data blocks required to store the compressed data of the entire input data from the quotient divided by n. 15. The method according to claim 14, wherein, when estimating the number of data blocks, the divisor of the compressed data length of the input data 1 / n is set to a value smaller than 1 / n of the data block length by several bytes. A storage device that adds a margin in consideration of the variation of the compression rate for each data. 16. The storage device according to claim 13, wherein when the number of data blocks required for storing the compressed data is equal to or larger than the number of data blocks required for storing the uncompressed data, the uncompressed data is stored in the storage device.