JP2010160544A - Cache memory system and method for controlling cache memory - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a cache memory system for improving data integrity, a cache hit ratio, and a flash efficiency, and to provide a method for controlling a cache memory. <P>SOLUTION: Data are temporarily written in an empty chunk, and only a chunk which has succeeded in data transfer is replaced with a data chunk on a cache. Also, an address and a valid data size on a storage device 30 are stored in a chunk header, so that a chunk whose data are partially valid is also made to exist on the cache. Further, a range in which the sequence of flash of the data to the storage device 30 is determined by sorting LBA (Logical Block Address) orders is limited. <P>COPYRIGHT: (C)2010,JPO&INPIT

Description

  The present invention relates to a cache memory system provided between a computer and a storage apparatus, and more particularly to a cache memory system that increases the access speed to a storage apparatus.

  As one of the measures for improving the processing speed of an application operating on a computer, the access speed of a storage device accessed by the computer is increased.

  As a device for increasing the access speed of storage, there is a storage device called a DRAM semiconductor disk device that can perform random address access using a DRAM as a storage medium at high speed. On the other hand, there is also a storage device that has a very high throughput (1 GB / s or more) for sequential address access. In recent years, there is a RAID device equipped with a flash memory type SSD.

  However, the capacity of DRAM semiconductor disk devices is limited, and in order to adapt to actual applications, data with high access frequency (hot data) and data with low access frequency (cold data) are analyzed and separated, and only hot data is stored. Is very troublesome, such as storing the data in a DRAM semiconductor disk device. For this reason, there were many cases where it was difficult to introduce. The flash memory type SSD has a very high random read access speed, but the random write access has the same performance as a magnetic disk. Therefore, it is not suitable as a storage device used in an application with many random writes.

  In addition, a storage device that realizes ultra-high-speed throughput is suitable for high-definition video editing applications, but is not very effective in speeding up applications for the enterprise market with many random accesses. Therefore, it has been proposed to provide a large-capacity cache memory system between a normal magnetic disk device or a flash SSD and a host computer for speeding up random write access, which is a weak point thereof. By providing this cache memory system, the execution processing speed of various applications can be increased.

FIG. 14 shows a configuration of a general cache memory system.
The cache memory system 120 of FIG. 14 is provided between the host server 110 and the storage apparatus 130 including source devices such as a plurality of hard disk apparatuses 131-1 to 131-l, and the host server 110 accesses the storage apparatus 130. Improve access speed.

  14 includes a control CPU 121 that controls the entire cache memory system 120, a SCSI interface 122 that is an interface for connecting to the host server 110, an I / O control unit 123 that controls the SCSI interface 122, and a storage apparatus. A SCSI interface 124 that is an interface for connecting to the I / O 130; an I / O control unit 124 that controls the SCSI interface 124; a cache memory 126 that stores and holds cache data; and a memory control unit 127 that controls the cache memory 126.

  The data requested to be read from the host server 110 to the storage device 130 is read from the source device such as the hard disk device 131 and transferred to the host server 110, and simultaneously stored in the cache memory 126 of the cache memory system 120. (Move in). When the data requested from the host server 110 exists on the cache memory 126, the cache memory system 120 transfers the data on the cache memory 126 directly to the host server 110 (read cache hit).

  Data written from the host server 110 to the storage device 130 is temporarily stored on the cache memory system 120 (move-in), and the write command from the host server 110 is terminated (write-back). The updated data on the cache memory 126 is written back to the storage apparatus 130 later (flash). If the data to be written at this time is data existing on the cache memory 126, the cache memory system 120 overwrites the existing data on the cache memory 126 and completes the write command (write cache hit). On the other hand, the cache memory system 120 sequentially synchronizes the updated data on the cache memory 126 with the source device of the storage apparatus 130 (flash).

  The cache memory system 120 needs to discard (purge) any cache data when the corresponding data does not exist in the cache and there is no free memory when the write data is temporarily stored in the cache memory 126. . If the selected cache data is not synchronized with the storage apparatus 130, flushing and purging must be performed simultaneously. If the data to be discarded has already been flushed, only purge is performed.

  In the cache memory system 120, if the control CPU 121 also realizes a RAID (Redundant Array of Industrial Disks) function, the cache memory system 120 and the storage device 130 become a so-called RAID device with a cache function.

  As a literature on this cache memory system, for example, in Non-Patent Document 1, as a cache data management method, the cache memory is managed in units of segments, and the segment size is changed according to the access size from the computer (host server) The method to do is disclosed.

  In the method of Non-Patent Document 1, the invalid area is reduced by data smaller than the segment size by adjusting the segment size. However, this Non-Patent Document 1 does not disclose a relief method for data in which LBA (Logical Block Address) starts in the middle of a segment boundary.

Non-Patent Document 2 proposes a new cache algorithm by measuring and comparing various cache algorithms.
This non-patent document 2 discloses a writing method in which data is written from the host server and written in the LBA order in order to efficiently flush the data to the source device.

"Optimizing Cache for Individual Workloads with the Hitachi Cache Partition Manager Feature", On Hitachi TagmaStore Adaptable Modular Storage and Workgroup Modular Storage, An Application Brief by Kevin Sampson, April 2006 "WOW: Wise Ordering for Writes-Combining Spatial and Temporal Locality in Non-Volatile Caches", Binny S. Gill and Dharmendra S. Modia, IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

The conventional cache memory system has the following problems.
1. Occurrence of junk data When the cache memory system receives a write command to data existing on the cache memory, the cache memory system overwrites the received data on the corresponding cache data on the cache memory (write cache hit ). At this time, data transfer may fail due to a parity error or transfer error.

  The conventional cache memory system control method has a problem that, when data transfer fails, junk data (meaningless data) is overwritten on the data in the cache.

FIG. 15 is a diagram illustrating a problem of occurrence of junk data.
When the write data from the host server is stored on the cache memory 126, the data is transferred to the cache memory by the memory control unit by DMA (Direct Memory Access), but a parity error or transfer error occurs during the DMA transfer. When this occurs, junk data remains on the cache memory 126.
2. Address boundary problem FIG. 16 shows a general cache data management system.

  Data on the cache memory 126 is managed in units of segments (hereinafter referred to as “chunks” in this specification). In this data management, data is read and written in units of addresses divided in units of chunk size in order from 0 address of the address (LBA) on the storage device. Each chunk 201 of the cache memory 126 is managed by the hash table 200.

  However, regardless of the chunk size on the cache memory 126, the host computer accesses across the chunk address boundary. In that case, only some data on a plurality of chunks is written.

  For example, in FIG. 16, data 202 is written across chunks 201-1 and 201-2, but the first half part is not updated in chunk 201-1 and the second half part is not updated in chunk 201-2. Therefore, in this case, there is a problem that the chunks 201-1 and 201-2 have half the invalid area.

  Non-Patent Document 1 shows a method of reducing the invalid area by changing the segment size. However, when the LBA address accessed by this non-patent document 1 does not start from a boundary address, Similarly, an invalid area occurs.

If there are many invalid areas, the cache capacity is not used effectively, and the cache hit rate decreases. Further, as a method of eliminating the invalid area, this problem can be avoided by taking a method in which a chunk in which only some data is valid is discarded. However, with this method, recently written data does not exist in the cache, so the cache hit rate decreases.
3. Problems in data flash efficiency In a cache memory system, if you want to store data in the cache memory (move-in), but there is no empty chunk in the cache memory, the chunk to be discarded based on LRU (Least Recently Used) etc. Select data and replace with new chunk data.

  At this time, if the selected chunk data is dirty data that has not yet been written (synchronized) to the storage device, until the selected dirty chunk data finishes writing (flushing) to the source device, The data in the cache memory cannot be replaced.

  On the other hand, in order to improve the performance of writing data from the cache memory system to the storage device, the dirty seek data is sorted in LBA order and then written to the storage device (flash) to reduce the storage device header seek time. Can improve write performance. However, there is no dependency between the LRU order used for chunk destruction in the cache memory system and the LBA order of the storage apparatus.

  FIG. 17 is a diagram illustrating a problem caused by this. In the figure, the shaded portion indicates dirty data, and (1) to (8) indicate the order in which the data in the cache memory is accessed from the host server, that is, the order based on the LRU.

  In FIG. 17, in accordance with the LRU order, the chunk data (1), the chunk data (2),. The oldest accessed data chunk (1) is discarded (purged) first. However, since the data chunk (1) is dirty data, it must be flushed to the storage device 130. Therefore, the chunk data (1) is loaded in the cache flush queue 302. However, in the LBA order, the chunk data (5) and the chunk (7) are younger addresses than the chunk data (1). Is loaded first. Accordingly, until the two chunk data (5) and (7) are first flushed to the storage apparatus 130, the flush of the chunk data (1) is waited, and a new cache data move-in is waited during that time. Therefore, there is a problem that it takes time to update the cache memory 126 (the latency time of the write command is long).

  In view of the above problems, an object of the present invention is to provide a cache memory system and a cache memory control method that improve data integrity, cache hit rate, and flash efficiency.

  A cache memory system according to the present invention is a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores data, and a cache memory that manages cache data in units of chunks; Among the chunks, a free chunk list for registering a chunk to which the cache data can be written, and data for writing data to the chunk registered in the free chunk list are transferred in response to a write request to the cache memory. And a data writing unit that removes the chunk to which the data has been transferred from the registration of the free chunk list after the transfer is completed.

  A second cache memory system of the present invention is a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores the data, and a cache that manages cache data in units of chunks. The apparatus includes a memory and a plurality of chunk headers corresponding to each of the chunks and storing information indicating the size of valid data in the corresponding chunk.

  A third cache memory system of the present invention is a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores the data, and a cache that manages cache data in units of chunks. A memory, a cache purge queue for registering the chunk to be purged according to a specific algorithm, and the chunk to be purged earlier than a specific range of the cache purge queue are registered in the order of the specific algorithm, and then The cache flush queue in which the chunks in the specific range are registered in the order in which writing to the storage device is earlier, and the data in the chunks in the order registered in the cache flush queue A flash controller to flush the storage device, characterized in that it comprises a.

  The present invention also includes a cache memory control method within its scope.

  According to the cache memory system of this embodiment, data integrity, cache hit rate, and flash efficiency can be improved.

It is a figure which shows the computer system on which the cache memory system of this embodiment is a premise. It is a figure which shows the data flow at the time of the computer in the computer system of this embodiment reading data from a storage apparatus. It is a figure which shows the data flow at the time of the computer in the computer system of embodiment writing data in a storage apparatus. It is a figure which shows management of the unused chunk by a free chunk list. It is a figure which shows the structure of a free chunk list | wrist. It is a figure which shows the management method of the chunk on a cache memory. It is a figure which shows the example of operation | movement of a cache memory system when the writing of data to cache memory fails. It is a flowchart which shows the operation | movement at the time of writing data in the cache memory of the cache memory system of this embodiment. It is a figure which shows the cache search method by a general 4 way association system. It is a figure which shows the structural example of the cache list | wrist used with the cache memory system of this embodiment. It is a figure explaining the writing of the data to the cache memory at the time of using the cache list | wrist of the structure of FIG. It is a figure explaining the flash method in the cache memory system of this embodiment. It is a flowchart which shows operation | movement of the cache memory system of this embodiment when dirty data on cache memory is flushed to a storage apparatus. 1 is a diagram illustrating a configuration of a general cache memory system. It is a figure which shows the generation | occurrence | production problem of junk data. It is a figure which shows a general cache data management system. It is a figure which shows the problem in efficiency improvement of a data flash.

An embodiment of the present invention will be described below with reference to the drawings.
FIG. 1 is a diagram showing a computer system on which the cache memory system of the present embodiment is a prerequisite.

  As shown in FIG. 1, the computer system 1 according to the present embodiment is configured between one or more computers 10-1 to 10-m on which an application program is running and one to a plurality of storage apparatuses 30-1 to 30-n. The cache memory system 20 is provided in the configuration. The cache memory system 20 functions as a cache memory when the computers 10-1 to 10-m access the storage devices 30-1 to 30-n.

The storage apparatuses 30-1 to 30-n may each have a RAID configuration.
The cache memory system 20 includes a control CPU 21, a SCSI interface 22, an I / O control unit 23, a SCSI interface 24, an I / O control unit 25, a cache memory 26, and a memory control unit 27.

  The control CPU 21 is a control unit that controls the entire cache memory system 20. The SCSI interface 22 is an interface for connecting to the host servers 10-1 to 10-m. The I / O control unit 23 is a control unit that controls connection with the host servers 10-1 to 10-m via the SCSI interface 122. The SCSI interface 24 is an interface for connecting to the storage apparatuses 30-1 to 30-n. The I / O control unit 25 is a control unit that controls connection with the storage apparatuses 30-1 to 30-n via the SCSI interface 24. The cache memory 26 is a memory that stores and holds cache data for the storage devices 30-1 to 30-n. The memory control unit 27 is a control unit that controls access to the cache memory 26.

Control of the cache memory by the cache memory system 20 of the present embodiment is realized by the control CPU 21 executing a program stored in its own memory.
The configuration of the cache memory system 20 is not a program execution type configuration in which the control CPU 21 executes a program as shown in FIG.

Next, FIG. 2 shows a data flow when the computer 10 in the computer system 1 of the present embodiment reads data from the storage device 30.
In the computer system 1 of this embodiment, when the computer 10 requests the storage device 30 to read data, if the data is not stored in the cache memory system 20, the requested data is as shown in a flow 31. The data is once stored in the cache memory 26 of the cache memory system 20, and then data is transferred from the cache memory system 20 to the computer 10 as shown in a flow 32. If the data requested by the computer 10 is already stored in the cache memory system 20, the data is read from the cache memory system 20 as in flow 32.

  Note that the flow of data at the time of reading from the storage device 30 in the computer system 1 of the present embodiment when the cache memory system 20 is not stored is not limited to this, and the computer 10 is not limited to the storage device. When data is read from 30, the data is stored in the cache memory system 20 as shown in the flow 31, and at the same time, the data is directly passed from the storage device 30 to the computer 10 as shown in the flow 33. good.

Next, a data flow when the computer 10 in the computer system 1 of the present embodiment writes data to the storage apparatus 30 will be described with reference to FIG.
As shown in FIG. 3, the computer 2 randomly writes to the storage device 30 during execution of the application program. The data at this time is once stored (move-in) in the cache memory system 20, sorted by a procedure described later, and then stored (flashed) in the storage device 30.

  Therefore, since all the data recently written by the computer 10 exists in the cache memory system 20, when the computer 10 reads the data, the data on the cache memory system 20 can be read at high speed.

Next, data writing to the cache memory system 20 of this embodiment will be described.
Data is written to the cache memory system 20 when the computer 10 tries to read data that is not in the cache memory system 20 from the storage device 30 and when the computer 10 writes data to the storage device 30. Is called.

  When data is written to the cache memory system 20, data transfer may fail and junk data may be generated due to a parity error or transfer error.

  In order to cope with this, the cache memory system 20 of the present embodiment includes a free chunk list that manages unused and writable chunks on the cache memory 126 in the cache memory system 20.

FIG. 4 is a diagram showing management of unused chunks by the free chunk list.
In the cache memory system 20 of the present embodiment, the area on the cache memory 26 is managed in units of chunks, and currently unused chunks are managed by the free chunk list 40.

  When a write command or a read command for data not on the cache memory 126 is received from the computer 10, the cache memory system 20 obtains the position information of the currently unused chunk from the chunks in the free chunk list 40 ((1) get). Free chunk). Then, the data from the computer 10 or the storage device 30 is DMA-transferred to the chunk at the position obtained in (1) ((2) DMA). After this data transfer is successful, this chunk and the corresponding chunk (data with the same LBA address) on the cache are replaced ((3) replacement). Return the chunk that became empty in (3) to the free chunk list ((4) put free chunk). When there is no corresponding LBA address chunk in (3), the oldest data chunk is replaced based on the LRU order.

  In the present embodiment, after data is transferred to an empty chunk, the occurrence of junk data is prevented by exchanging the chunk and a chunk that is valid in the cache.

FIG. 5 is a diagram showing the configuration of the free chunk list 40.
In FIG. 5, the free chunk list 40 includes pointer information 42 and chunk headers 42-1 to 42-o.

  The pointer information 41 is pointer information indicating the beginning (head) and the end (tail) of the chunk header 42 having a list structure. Since the free chunk list 40 has this pointer information, posting to the free chunk list 40 and extraction of a chunk header from the free chunk list can be performed at high speed. The chunk headers 42-1 to 42-o are data having a list structure having information on currently unused chunks on the cache memory 26. The chunk header 42 stores pointer information to the currently unused chunk 43 on the cache memory 26 as chunk information. Also, since the chunk headers 42-1 to 42-o have a list following, it is possible to add a new chunk header 43 or to delete the chunk header 42 of the chunk 43 that is in use at high speed.

FIG. 6 is a diagram showing how to manage the chunk 43 on the cache memory 26.
Whether the data in the chunk 43 on each cache memory 26 is valid data is managed by the chunk header 42. If the chunk header 42 is registered in the free chunk list 40, it means that the corresponding chunk 43 holds invalid data. If the chunk header 42 is registered in the cache list 44, the corresponding chunk 43 Means holding valid data.

  When writing data to the cache memory 26, first, the chunk header 42 is extracted from the head of the free chunk list 40 (get free chunk (S2 in FIG. 8)), and the free space in the cache memory 26 is determined from the chunk information of the chunk header 42. The position of the chunk 43 is recognized, and the data to be written in the chunk 43 is DMA-transferred (DMA transfer (S3 in FIG. 8)). Then, the chunk head 42 extracted from the free chunk list 40 is sent to the cache list 44 (put cache chunk (S4 in FIG. 8)). If there is a chunk with the same LBA address as the chunk header 42, it is replaced with that chunk, and if not, it is registered in the cache list 44 as it is (chunk replacement (S5 in FIG. 8)). Then, the chunk head 42 replaced with the cache list 44 is registered in the free chunk list 40 (put free chunk (S6 in FIG. 8)).

  As shown in FIG. 6, whether the data in each chunk 43 is valid as cache data or is free list chunk data, whether the chunk header 42 corresponding to the chunk 43 is registered in the free chunk list 40 or not. It can be determined depending on whether it is registered in the list 44. Therefore, each chunk 43 on the cache memory 26 can be managed while the chunk 43 holding data and the empty chunk 43 are mixed.

The free chunk list 40 and the cache list 44 may be built in a memory (not shown) in the control CPU 21 or may be built on the cache memory 26.
Next, a case where data writing to the cache memory 26 has failed will be described.

FIG. 7 is a diagram illustrating an operation example of the cache memory system 20 when data writing to the cache memory 26 fails.
When data is written to the cache memory 26, the chunk header 42 of the writable chunk 43 is extracted from the top of the free chunk list 40 (get free chunk (S2 in FIG. 6)), and the cache information is cached from the chunk information of the chunk header 42. The position of an empty chunk 43 in the memory 26 is recognized, and the data to be written in the chunk 43 is DMA-transferred (DMA transfer (S3 in FIG. 6)). If this DMA transfer fails and the chunk 43 is illegally written, the write command has failed, and the write to the host server 10 or storage device 30 that sent the write data to the cache memory system 20 has failed. Notify you. Then, the chunk header 42 of the chunk 43 that has failed to be written is re-registered in the free chunk list 40. The host server 10 or the storage 30 notified of the failure retransfers the data and succeeds in writing to the cache memory 26.

  Thereby, even if writing to the cache memory 26 fails and junk data is generated, the chunk 43 in which the junk data is written is registered in the free chunk list 40 as an empty chunk. Therefore, junk data does not remain as valid data on the cache memory 26.

  FIG. 8 is a flowchart showing an operation when data is written to the cache memory 26 of the cache memory system 20 of the present embodiment. The processing shown in FIG. 7 is realized by the control CPU 21 executing a program on a memory (not shown) in the control CPU 21.

  When the cache memory system 20 receives an access command to the storage apparatus 30 from the command reception waiting state, the cache memory system 20 determines whether or not the command writes to the cache memory 26. If the command from the computer 10 is a write command to the storage device 30 or a data read command not in the cache memory 26, the control CPU 21 determines that the received command is a write command to the cache memory 26 (step). S1). Then, the control CPU 21 acquires a writable chunk header 42 from the top of the free chunk list 40 as step S2. Next, the control CPU 21 transfers the received data from the chunk information of the chunk header 42 acquired in step S2 to the corresponding chunk 43 in the cache memory 26 as step S3.

  If the data transfer in step S3 fails (step S3, failure), the control CPU 21 re-registers the chunk header 42 acquired in step S2 in the free chunk list 40 as step S7.

  If the data transfer to the chunk 43 succeeds in step S3 (step S3, success), the control CPU 21 moves the chunk header 42 acquired in step S2 to the cache list 44 as step S4. In step S5, the control CPU 21 searches whether the chunk header 42 corresponding to the chunk 43 having the same LBA address as that of the chunk 43 is registered in the cache list 44. If registered, the control CPU 21 replaces the chunk header 42 with the new chunk header moved in step S4 as step S5. If not registered, the new chunk header moved in step S4 is registered in the cache list 44 as it is.

In step S6, the control CPU 21 registers the old chunk header 42 replaced in step S5 in the free chunk list 40, and then returns to the command reception waiting state.
Thus, in the cache memory system 20 of this embodiment, direct data transfer to the valid chunks 26 on the cache memory 26 is avoided. Then, data transfer is performed to the empty chunk 42 corresponding to the chunk header 42 acquired from the free chunk list 40, and only when the transfer is successful, the chunk header 42 is moved to the cache list 44 for valid data and data transfer. If it fails, the chunk header 42 is returned to the free chunk list 40. By this management method, even when data transfer fails, it is possible to prevent the original data existing in the chunk 42 on the corresponding cache from being destroyed.

Next, how to deal with the address boundary problem by the cache memory system 20 of this embodiment will be described.
First, search management using a hash table that is conventionally performed will be described.

FIG. 9 is a diagram showing a cache search method based on a general 4-way associative method.
In the example of FIG. 9, since 4 ways, the hash table 51 is 4 pieces, the chunk size is 16 KB (32 blocks, 1 block is 512 (B) bytes), the maximum LBA address is 65,536 (2 to the 16th power, 16 (b ) Bit), an example in which 64 chunks are managed in each hash table. In this case, since the total number of chunks is 64 × 4 = 256 and each chunk is 16K bytes, the cache system is 16KB × 256 = 4MB.

  Of the LBA address 54, bit 0 to bit 4 are equivalent to the chunk size (16 KB) and need not be referred to. 64 bits 5 to 9 of the LBA address 54 correspond to the chunk number. Bits 10 to 11 of the LBA address 54 correspond to hash table IDs (0 to 3). Bits 12 to 15 of the LBA address 54 are stored as the LBA address tag 52 in the hash table.

  In such a configuration, the LBA address bits of the corresponding cache data candidate are read by referring to each hash table 51 using bits 5 to 9 of the LBA address referenced from the host server. Then, this LBA address bit is compared with the requested LBA address, and if they match, it is recognized as a cache hit. When a cache hit occurs, the corresponding cache data can be identified from the segment ID and the hash table ID.

A cache search can be easily realized by having a hash table configured as shown in FIG. 9 and referring to this hash table.
Such a hash table reference method is effective when the capacity of the cache memory is very small. However, if the size of the cache memory is very large, the number of chunks becomes large, and the table size becomes very large. This increases the time for searching for the corresponding chunk information on the hash table.

Since the cache memory system 20 of the present embodiment is premised on the installation of the large-capacity cache memory 26, it is not efficient to adopt the hash table method.
Therefore, in the cache memory system 20 of the present embodiment, tree search such as B + tree search is applied.

FIG. 10 is a diagram showing a configuration example of the cache list 44 used in the cache memory system 20 of the present embodiment.
The cache list 44 of this embodiment has a B + tree structure as shown in FIG. By referring to this B + structure cache list 44, it is determined whether or not the access requested data exists in the cache memory 26 (cache hit or cache miss).

In the cache list 44 of FIG. 10, a chunk header (CH) 42 is provided at the end record of the B + tree.
In each chunk header 42, the next free chunk address (NEXT_CHUNK), start address (START_LBA), effective data length (N_LBA), and data address (DATA_ADDRESS) are recorded as chunk information.

  Among these pieces of chunk information, the address of the next free chunk (NEXT_CHUNK) is a pointer for the chunk headers 42 in the cache list 44 to have a list structure, and in the cache list 44 described with reference to FIG. Used to replace the chunk header 42. The start address (START_LBA) indicates an address (LBA address) in the storage device 30 of data (chunk data) in the chunk 43 corresponding to the chunk header 42. The effective data length (N_LBA) is information indicating how many blocks are valid data from the top of the data in the corresponding chunk 43. The data address (DATA_ADDRESS) is address information on the cache memory 26 of the chunk 43 corresponding to the chunk head 42.

FIG. 11 is a diagram for explaining the writing of data to the cache memory 26 when the cache list 44 configured as shown in FIG. 10 is used.
In FIG. 11, as an example of the case where the computer 10 receives a write command of an arbitrary size to an arbitrary address, a write command of write size 40 blocks (one block is 512 bytes) to the address 128 is issued from the computer 10 The case is shown as an example.

  At this time, in the cache memory system 20, if the size of the chunk 43 is 8 KB (16 blocks, one block is 512 B), three three chunk headers 42 are registered in the B + tree structure cache list 44, and the cache memory The data is transferred to the three chunks 43 on H.26.

  At this time, among the three chunks 43, chunks (1) and (2) use all areas to store data, but chunk (3) uses only 8 blocks. Therefore, the effective data length (N_LBA) in the chunk header 42 corresponding to the chunk (1) and the chunk (2) is 16 (block), but the effective data length (N_LBA) of the chunk (3) is 8 (block). Chunk (1) and chunk (2) use all chunk data, but chunk 3 indicates that the effective data length is not all chunk data.

  In this way, by holding the data start address (START_LBA) and the data valid length (N_LBA) of the chunk in the chunk header 42 corresponding to each chunk 43, data of an arbitrary length at an arbitrary address from the host server can be obtained. It can be held on the cache memory 26.

  In the case of the above-described example, only the data of chunk (3) is not valid, but the conventional method is invalid unless the address of the write command is at the head of the chunk 43 boundary. In contrast, in this method, an invalid area is generated only when the last chunk data is a fraction. Therefore, the usage efficiency of the cache memory 26 area can be improved compared to the conventional method.

Next, processing when data in the cache memory 26 is flashed back to the storage device 30 in the cache memory system 20 of this embodiment will be described.
Of the data on the cache memory 26. Selecting all the dirty data rewritten by the computer 10 and sorting them in the LBA order and then flashing them back to the storage device 30 can improve the efficiency of flashback from the seek time of the storage device 30 and the like. is known.

  However, at the same time, if there are not enough free chunks (Cache full) on the cache memory 26, it is necessary to urgently flush the purged chunks 43 in accordance with the LRU order. At this time, if the chunk 43 to be purged is already loaded in the flush target queue in the LBA order, execution of the received write command is made to wait until the flushing is completed.

  Therefore, since new data cannot be moved into the chunk 43 until the flushing is completed, the next command cannot be executed, so that there is a problem that the latency time of the command becomes long and the processing performance deteriorates. .

In the cache memory system 20 of the present embodiment, a lower limit value is provided to cope with this problem, and the method of determining the order of flushing is changed based on this lower limit value.
FIG. 12 is a diagram for explaining a flushing method in the cache memory system 20 of the present embodiment. In the figure, (1) to (10) indicate the order in which the data in the chunk 43 is accessed, and the netted chunk 43 is still purged to the storage apparatus 30 after the data is updated by the computer 10. A chunk 43 including dirty data that has not been processed is shown.

  The chunk 43 to be purged from the cache memory 25 has its chunk head 42 registered in the cache purge queue 61. Since this registration is performed in the order of the LRU order, (1), (2),... The chunk header 42 registered in the cache purge queue 61 has a list structure, and a pointer to the next chunk header 42 is stored as NEXT_LRU_CHUNK.

The cache purge queue 61 of this embodiment has a lower limit value A and an upper limit value B.
On the other hand, the chunk head 42 including the data to be flushed from the cache memory 26 to the storage device 30 has its chunk head 42 registered in the cache flush queue 62. Note that the chunk header 42 registered in the cache flush queue 62 also has a list structure, and a pointer to the next chunk header 42 is stored as NEXT_FLUSH_CHUNK.

  In the conventional method, registration in the cache flush queue 62 is performed by sorting in the order of LBA order. However, in the cache memory system 20 of this embodiment, chunks including dirty data older than the lower limit A value of the cache purge queue 61 are included. 43 are not sorted in the LBA order but are loaded in the cache flush queue 62 in the LRU order. Then, the chunks 43 including the dirty data in the range of the lower limit value A to the upper limit value B of the cache purge queue 61 are sorted in the LBA order and loaded on the cache flush queue 62.

  As a result, data in the chunk 43 that is considered to be purged soon can be preferentially flushed to the storage device 30. Further, the chunks 43 including other dirty data are sorted into the LBA order and flushed, thereby reducing the header seek time of the storage apparatus 30 and performing flushing efficiently.

  As described above, according to the cache memory system 20 of the present embodiment, it is possible to reduce the phenomenon of blocking the cache move-in while maintaining the high efficiency of flushing to the storage apparatus 30.

  Each chunk header 42 includes, as chunk information, the next chunk header address (NEXT_FREE_CHUNK) for the free chunk list 40 in addition to the NEXT_FLUSH_CHANK, NEXT_LRU_CHUNK, START_LBA, N_LBA, and DATA_ADDRESS described above. Using these pieces of information, the free chunk list 40, the cache purge queue 61, and the cache flush queue 62 described so far are realized simultaneously.

  FIG. 13 is a flowchart showing the operation of the cache memory system 20 when the dirty data on the cache memory 26 is flushed to the storage device 30. The processing in FIG. 5 is realized by the control CPU 21 executing a program on a memory in the control CPU 21.

  In the process shown in the figure, an interval time of x seconds is first provided in order to store dirty data to some extent for efficient flushing by sorting into LBA orders (step S11, NO).

  When x seconds have elapsed since the first write command was received (step S11, YES), the control CPU 21 first resets the pointer P of the cache purge queue 61 to 0 as step S12.

  When the cache purge queue 61 pointed to by the pointer P is the chunk head 42 of the dirty data chunk 43 (YES in step S13), the control CPU 21 cache flushes the chunk header 42 pointed to by the pointer P of the cache purge queue 61 in step S14. Post to queue 61. If the cache purge queue 61 pointed to by the pointer P is not the chunk head 42 of the dirty data chunk 43 (step S13, NO), the control CPU 21 skips step S14.

  Next, the control CPU 21 increments the pointer P by +1 (step S15). As a result, if the value of the pointer P does not exceed the lower limit A (step S16 <NO), the process returns to step S13, and the control CPU 21 confirms the next header of the cache purge queue 61 pointed to by the pointer P. To do.

  If the value of the pointer P exceeds the lower limit value A in step S16 (step S16, YES), the control CPU 21 determines the chunk header 42 between the lower limit value A and the upper limit value B of the cache purge queue 61 as step S17. Are rearranged into the LBA order (LAB order sort), the chunk header 42 is posted to the cache flush queue 62 in that order, and the process is returned to the beginning.

Data in the chunk 43 corresponding to the chunk header 42 posted to the cache flush queue 62 is sequentially flushed to the storage device 30.
As described above, according to the flush method to the storage apparatus 30 by the cache memory system 20 of the present embodiment, it becomes possible to adjust the chunk data that prioritizes the LRU order and the chunk data that is efficiently flushed by the LBA order. The processing is not repeated for the purge of chunks, and the speed of the flash can be increased.

  As described above, according to the cache memory system 20 of the present embodiment, it is possible to increase the speed of random access writing, which is a weak point of the storage device 30 using a magnetic disk or SSD (flash memory disk).

  In addition, the cache hit rate is improved, the data to be purged according to LRU is preferentially flushed, and the data by random address writing is rearranged in the order of the address order and efficiently written back to the storage device. Writing can be improved and system performance can be dramatically improved.

  Furthermore, since cache data need not be purged in advance for write data, the cache hit rate of read data is improved, and the large capacity storage device 30 is as if it is a DRAM-based ultrahigh-speed semiconductor disk device. It is possible to behave. Therefore, it is possible to process all patterns of data access from the computer 10 at high speed, reduce disk IO bottlenecks, and significantly reduce processing time for batch jobs of database applications that frequently generate random access. It can be made.

10, 110 Computer 20, 120 Cache memory system 21, 121 Control CPU
22, 24, 122, 124 SCSI interface 23, 25, 123, 125 I / O control unit 26, 126 Cache memory 27, 127 Memory control unit 30 Storage device 40 Free chunk list 41 Pointer information 42 Chunk header 43 Chunk 44 Cache list 61 Cache purge queue 62 Cache flush queue

Claims (9)

In a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores data,
A cache memory that manages cache data in units of chunks;
Among the chunks, a free chunk list for registering chunks to which the cache data can be written,
In response to a write request to the cache memory, data to be written is transferred to a chunk registered in the free chunk list, and after the transfer is completed, the chunk to which the data is transferred is registered in the free chunk list. A data writing unit to be removed from,
A cache memory system comprising: In a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores data,
A cache memory that manages cache data in units of chunks;
A plurality of chunk headers corresponding to each of the chunks, each storing information indicating the size of valid data in the corresponding chunk;
A cache memory system comprising:   The cache memory system according to claim 2, wherein the chunk header also stores address information indicating a position of the chunk corresponding to the chunk header in the storage device. The plurality of chunk headers store information indicating an address of the information in the corresponding chunk on the storage device and information indicating a position of the corresponding chunk in the cache memory, and a B + tree structure Have
The cache memory system according to claim 2, further comprising a control unit that performs a cache hit or cache miss determination on the plurality of chunk headers using a tree search algorithm. In a cache memory system that caches data stored in a storage device between a computer that performs data processing and a storage device that stores data,
A cache memory that manages cache data in units of chunks;
A cache purge queue that registers the chunks to be purged according to a specific algorithm;
The chunks to be purged earlier than the specific range of the cache purge queue are registered in the order of the specific algorithm, and then the order in which the chunks in the specific range are written to the storage device earlier The cache flush queue registered in
A flush controller that flushes the data in the chunk to the storage device in the order registered in the cache flush queue;
A cache memory system comprising:   The cache memory system according to claim 5, wherein the specific algorithm is an LRU (Least Recently Used) algorithm. In a cache memory control method for caching data stored in a storage device between a computer that performs data processing and a storage device that stores data,
Managing cache data in the cache memory in units of chunks;
Of the chunks, register a chunk that can write the cache data in a free chunk list,
In response to a write request to the cache memory, the data to be written is transferred to a chunk registered in the free chunk list, and after the transfer is completed, the chunk to which the data is transferred is registered in the free chunk list. A method for controlling a cache memory, characterized in that it is excluded from the above. In a cache memory control method for caching data stored in a storage device between a computer that performs data processing and a storage device that stores data,
Managing cache data in the cache memory in units of chunks;
A cache memory control method, wherein information indicating the size of valid data in a corresponding chunk is stored in a chunk header corresponding to each chunk. In a cache memory control method for caching data stored in a storage device between a computer that performs data processing and a storage device that stores data,
Managing cache data in the cache memory in units of chunks;
Register the chunk to be purged according to a specific algorithm in the cache purge queue,
Register the chunks to be purged earlier than a specific range of the cache purge queue in the cache flush queue in the order of the specific algorithm,
Subsequently, the chunks within the specific range are registered in the cache flush queue in the order in which writing to the storage device is accelerated,
Flushing the data in the chunk to the storage device in the order registered in the cache flush queue;
A cache memory control method.