Storage device and storage area management method for reducing garbage collection processing

When a real area is allocated to a write destination virtual area in a virtual volume, a storage device determines whether or not a size of compressed new data is larger than a size of the allocated real area. In a case where the determination result is true, the storage device determines whether or not there is one or more real areas having a size equal to or larger than the size of the compressed new data and including a garbage area that is a real area serving as garbage. In a case where the determination result is true, the storage device selects one or more real areas including the garbage area, allocates, instead of the allocated real area, the selected one or more real areas to the write destination virtual area, and manages the allocated real area as a garbage area.

TECHNICAL FIELD

The present invention relates generally to storage area management.

BACKGROUND ART

A storage device, which allocates a real area (logical storage area) from a pool (real area group) to a write destination virtual area (logical address range) in a virtual volume (logical address space) and writes data in the real area, has been known. The data written in the real area is written in a physical storage area allocated to the real area. If the real area is allocated to the write destination virtual area, the storage device performs overwriting write processing, that is, overwrites new data (data to be written this time) over old data (data to be written last time).

However, in a case where the storage device compresses the data and stores in the real area, data size is changed due to compression, and the size of the compressed new data (new data after compression) may be larger than the size of the compressed old data (old data after compression) in the overwriting write processing. In this case, the compressed old data cannot be overwritten in the area stored with the compressed old data. Therefore, the storage device allocates, instead of the allocated real area, a larger real area from the pool to the write destination virtual area, and writes the compressed new data in the larger real area. The allocated real area (the real area where the compressed old data is stored) becomes garbage and is managed as an invalid real area. In the storage device, garbage capacity is not managed as free capacity, and new data is not written in the garbage. Patent Document 1 discloses a technique of enabling the garbage to be free capacity by executing garbage collection processing (hereinafter referred to as GC processing) when a certain amount of garbage is accumulated.

PRIOR ART LITERATURE

Patent Literature

SUMMARY OF INVENTION

Technical Problem

The GC processing requires overhead. When the size of the compressed new data is equal to or smaller than the size of the allocated real area, the compressed new data can be overwritten to the allocated real area, thereby avoiding generation of garbage. However, the generation of garbage cannot be reliably avoided since the size of the new data after compression is determined by attributes of the new data and a compression method (for example, compression algorithm).

Solution to Problem

When a real area is allocated to a write destination virtual area in a virtual volume, a storage device determines whether or not a size of the compressed new data is larger than a size of the allocated real area. In a case where the determination result is true, the storage device determines whether or not there is one or more real areas having a size equal to or larger than the size of the compressed new data and including a garbage area that is a real area serving as garbage. In a case where the determination result is true, the storage device selects the one or more real areas including the garbage area, allocates, instead of the allocated real area, the selected one or more real areas to the write destination virtual area, and manages the allocated real area as a garbage area.

Advantageous Effect

The data is compressed and then stored in the real area, and even in a case where the size of the compressed new data exceeds the size of the allocated real area, a possibility of increasing the garbage area can be reduced.

DESCRIPTION OF EMBODIMENTS

Embodiments will be described below with reference to the drawings. However, the present embodiment is merely an example used to realize the invention, and does not limit technical scope of the invention. In the drawings, the same reference numerals denote the same configurations.

In the following description, although various information may be described in an expression “aaa table” or “aaa queue”, the various information may also be expressed by a data structure other than a table or a queue. The “aaa table” or “aaa queue” may be referred to as “aaa information” to indicate that the information does not depend on the data structure.

In the following description, an “interface unit” may include one or more interface devices, specifically, at least one of a user interface unit and a communication interface unit. The user interface unit may include at least one I/O device of one or more I/O devices (for example, an input device (such as a keyboard and a pointing device) and an output device (such as a display device) and a display computer. The communication interface unit may include one or more communication interface devices. One or more communication interface devices may be one or more communication interface devices of the same type (for example, one or more network interface cards (NIC)), or two or more communication interface devices of different types (for example, the NIC and a host bus adapter (HBA)).

In the following description, a “storage unit” includes one or more memories. At least one memory of the storage unit may be a volatile memory. The storage unit is mainly used during a processing by a processor unit.

In the following description, the “processor unit” includes one or more processors. At least one processor is a typical microprocessor such as a central processing unit (CPU). The one or more processors may be single-core or multi-core. A processor may include a hardware circuit that performs a part or all of the processing. The processor unit may include a hardware circuit (for example, a field-programmable gate array (FPGA) or an application specific integrated circuit (ASIC)) that performs a part or all of the processing.

In the following description, “PDEV” refers to a physical storage device, and typically may be a nonvolatile storage device (for example, an auxiliary storage device). The PDEV may be, for example, a hard disk drive (HDD) or a solid state drive (SSD). Different types of PDEVs may be mixed in a storage system.

In the following description, “RAID” is an abbreviation for redundant array of independent (or inexpensive) disks.

In the following description, “RAID group” may be a group that includes a plurality of PDEVs and stores data according to an associated RAID level (RAID configuration), or may be a group that includes a plurality of physical storage areas and stores data according to the associated RAID level (RAID configuration).

In the following description, although numbers are used as identification information of elements, other types of identification information can also be used instead of or in addition to the numbers.

In the following description, in a case of describing the same type of elements without distinction, a common part may be used in reference numerals, and in a case of distinguishing and describing the same type of elements, reference numerals of the elements (including branch numbers) may be used.

In the description of the following embodiments, although an example of the storage device is the storage system having one or more PDEVs, a PDEV can also be adopted as an example of the storage device. When the storage device is a PDEV (for example, a flash memory device), the storage device includes one or more physical storage media (for example, flash memory chips) and a controller used to control I/O for the one or more physical storage media. Each of the PDEV and the physical storage media is an example of a physical storage resource.

First Embodiment

As will be described in detail below with reference toFIG. 2, a storage system30includes one or more PDEVs34and a controller31that controls data input/output (I/O) for the one or more PDEVs34. The controller31is configured to compress and decompress data.

As shown inFIG. 14, the controller31manages one or more pools600. The pool600is a logical storage space. At least a part of the pool600may be based on at least a part of a plurality of PDEVs34, and at least a part of the pool600may be based on a storage area provided by a storage system (not shown) external to the storage system30. The pool600includes a plurality of sub-pool pages (logical storage areas)641having different sizes.

The controller31provides a virtual volume501(logical address space) to a higher hierarchy device such as a host computer10. As shown inFIG. 14, sub-pool pages61-1,61-2and61-3are respectively allocated to virtual pages (logical address ranges)52-1,52-2and52-3in a virtual volume501, and compressed old data A, B and C are respectively stored in the sub-pool pages61-1,61-2, and61-3.

In this situation, as shown inFIG. 14, it is assumed that the controller31receives a write request of new data D with the virtual page52-1as a write destination. The controller31compresses the new data D, and determines whether or not the size of the compressed new data D is equal to or smaller than the size of the sub-pool page61-1(or the size of compressed old data A stored in the sub-pool page61-1) allocated to the write destination virtual page52-1. If the determination result is true, as shown inFIG. 14, the controller31overwrites the compressed new data D in the allocated sub-pool page61-1.

In the above-described situation, as shown inFIG. 15, it is assumed that the controller31receives a write request of new data E with the virtual page52-1as the write destination. The controller31compresses the new data E, and determines whether or not the size of the compressed new data E is equal to or smaller than the size of the sub-pool page61-1(or the size of the compressed old data A stored in the sub-pool page61-1) allocated to the write destination virtual page52-1. If the determination result is false, as shown inFIG. 15, the controller31allocates, instead of the sub-pool page61-1, a sub-pool page61-4having a larger size to the write destination virtual page52-1, and writes the compressed new data E in the sub-pool page61-4. As a result, the sub-pool page61-1becomes garbage.

In this way, the garbage is generated in the pool600. In the present embodiment, a total amount of the garbage in the pool600is suppressed as follows, and as a result, load of a garbage collection processing (GC processing) can be reduced.

For example, in the situation shown inFIG. 15, that is, in a situation where the sub-pool page61-1exists as the garbage, the controller31receives a write request of new data F with the virtual page52-3as the write destination, as shown inFIG. 1. The controller31compresses the new data F, and performs a first determination that whether or not the size of the compressed new data F is equal to or smaller than the size of the sub-pool page61-3(or the size of compressed old data C stored in the sub-pool page61-3) allocated to the write destination virtual page52-3. If the result of the first determination is false, the controller31performs a second determination that whether or not the size of the compressed new data F is equal to or smaller than any garbage (here, the sub-pool page61-1) (or the size of the compressed data in the garbage). If the result of the second determination is true, as shown inFIG. 1, the controller31allocates, instead of the sub-pool page61-3, the garbage sub-pool page61-1to the write destination virtual page52-3, and writes the compressed new data F in the allocated sub-pool page61-1. As a result, although the sub-pool page61-3becomes garbage, an increase in the number of garbage can be avoided. That is, according to the present embodiment, performance of the storage system30can be expected to be improved since garbage is used as the write destination of the compressed new data to be overwritten (in other words, since garbage can be reused without performing the GC process in which performance is degraded due to overhead.

According to a comparative example shown inFIG. 16, the second determination is not performed. That is, in a case where the result of the first determination is false, instead of the sub-pool page61-3, a sub-pool page61-5having a larger size is allocated to the write destination virtual page52-3, and the compressed new data F is written in the sub-pool page61-5. As a result, in addition to the sub-pool page61-1, the sub-pool page61-3becomes garbage. That is, the number of garbage is increased.

The present embodiment will be described in detail below.

FIG. 2shows a configuration example of a computer system according to the present embodiment.

A computer system1includes at least one host computer10(such as a general-purpose large-scale computer, a device including a server and a general-purpose hardware component, or a general-purpose server), at least one management device20(such as a management computer, a device including a server and a general-purpose hardware component, or a general-purpose server) and the storage system30to which these are connected.

The host computer10accesses a logical storage resource (for example, a logical address space) of the storage system30. The management device20manages configuration of storage areas of the storage system30. The storage system30stores data in the storage areas based on the one or more PDEVs34. At least one of the host computer10and the management device20may be plural.

The storage system30includes the plurality of PDEVs34and the controller31. The controller31includes at least one cache memory32and at least one shared memory33externally. At least one of the cache memory32, the shared memory33and the controller31may be redundant. In addition, hardware configuration inside the controller31may also be redundant.

The controller31controls storage of data to the storage areas based on the PDEVs34. The cache memory32temporarily stores data to be read and written from and in the PDEVs34. The shared memory33stores configuration information related to the controller31and the PDEVs34.

The PDEV34may be any physical storage device, and may be, for example, an HDD or an SSD.

The controller31includes a host adapter310, a network adapter320, a nonvolatile memory (NVMe)330, a memory350, a storage adapter370, a shared memory adapter380, a compression/decompression circuit (C/D)390and a processor360connected thereto. At least one of the host adapter310, the network adapter320, the storage adapter370and the shared memory adapter380is an example of an interface unit. At least one of the nonvolatile memory330, the memory350, the cache memory32and the shared memory33is an example of a storage unit. The processor360is an example of a processor unit.

The host adapter310transmits and receives data to and from the host computer10via storage area network (SAN)121. The network adapter320transmits and receives data necessary for system management (for example, management information) to and from the host computer10or the management device20via network108(for example, local area network (LAN)).

The nonvolatile memory330is configured by, for example, a hard disk or a flash memory, and stores programs to be operated on the controller31, configuration information and the like.

The memory350may be a volatile memory such as a random access memory (RAM), and stores programs, data and the like.

The processor360reads a program stored in the nonvolatile memory330into the memory350, and executes a processing defined by the program.

The storage adapter370transmits and receives data to and from the PDEVs34and the cache memory32. The shared memory adapter380transmits and receives data to and from the shared memory33.

The compression/decompression circuit390is a hardware circuit, and outputs input data after compression or decompression. At least one of the compression and decompression may be performed by the processor360executing a computer program instead of the hardware circuit.

An external storage system (not shown) may be connected from the network adapter320(or another adapter which is not shown) via the network121(or another network). At least a part of storage areas provided from the external storage system may be storage areas of at least a part of the above-described pool600.

The management device20may not be connected.

The storage system30may be a computer system including one or more physical computers (for example, general-purpose computers). At least one physical computer may execute a virtual computer (for example, a virtual machine (VM)) or a software-defined anything (SDx). As the SDx, for example, a software defined storage (SDS) (virtual storage system) or a software-defined data center (SDDC) can be adopted. In this case, the host computer10may be a virtual computer executed in the computer system.

FIG. 3shows an example of programs and management information stored in the storage system30.

The programs and the management information are stored in the memory350, for example. The programs are executed by the processor360. The programs include, for example, an I/O processing program352and a pool management program354. The management information includes, for example, a virtual volume table510, a pool management table610and a pool volume table660. At least a part of operation of the controller31is controlled by the processor360executing the I/O processing program352and the pool management program354.

The I/O processing program352is a program used to perform a processing related to I/O such as storing compressed data in a page. The pool management program354is a program used to perform a processing related to pool management such as page selection. The virtual volume table510is a table that holds information on a virtual volume. The pool management table610is a table that holds information on the pool600. The pool volume table660is a table that holds information on a pool volume. These programs and tables may be stored in the nonvolatile memory330, in which case the programs and tables are loaded into the memory350.

FIG. 4shows a configuration example of the virtual volume table510.

The virtual volume table510includes entries for each virtual page. Each entry stores information including a virtual volume #511, a virtual page #512, a size after compression513, a pool #514, a sub-pool #515and a sub-pool page #516. Hereinafter, one virtual page (a “target virtual page” in the description ofFIG. 4) is taken as an example.

The virtual volume #511is a number used to identify a virtual volume including the target virtual page. The virtual page #512is a number used to identify the target virtual page. The size after compression513indicates a size of compressed data obtained by data to be written being compressed by the compression/decompression circuit390. An appropriate sub-pool in the pool600(described below) can be selected with reference to the size after compression513. The pool #514is a number used to identify a pool including a sub-pool page allocated to the target virtual page. The sub-pool #515is a number used to identify a sub-pool including a sub-pool page allocated to the target virtual page. The sub-pool page #516is a number used to identify the sub-pool page allocated to the target virtual page. If the sub-pool page is not allocated to the virtual page, the value of the size after compression513, the pool #514, the sub-pool #515and the sub-pool page #516are values indicating that there is no data (for example, “N/A”).

Although not shown, the virtual volume table510may have information indicating whether or not each virtual volume corresponds to compression. Accordingly, a processing can be distinctively performed based on whether a virtual volume unit corresponds to the compression function. For a virtual volume that does not correspond to compression, the controller31may write data to a sub-pool page (real page) without compressing the data.

FIG. 5shows a configuration example of the pool management table610.

The storage system30includes one or more pools, and at least one pool includes a plurality of sub-pools having different sub-pool page sizes. Each sub-pool is a set of a plurality of sub-pool pages having the same sub-pool page size. The pool management table610includes entries for each sub-pool. Each entry stores information including a pool #611, a sub-pool #612, a sub-pool page size613, a use pointer (pointer to a use page queue)614and an unused pointer (a pointer to an unused page queue)615. Hereinafter, one sub-pool (a “target sub-pool” in the description ofFIG. 5) is taken as an example.

The pool #611is a number used to identify a pool including a target sub-pool. The sub-pool #612is a number used to identify the target sub-pool. The sub-pool page size613indicates the size (length) of a sub-pool page in the target sub-pool.

For each sub-pool, a plurality of sub-pool pages is managed using queues in the present embodiment. The use pointer614indicates a head address of a queue620(hereinafter referred to as a use queue) that manages use sub-pool pages (a sub-pool page allocated to any of the virtual pages) in the target sub-pool. The unused pointer615indicates a head address of a queue630(hereinafter referred to as an unused queue) that manages unused sub-pool pages (a sub-pool page that is not allocated to any of the virtual pages) in the target sub-pool. The use queue620and the unused queue630are used to manage the sub-pool pages (real pages), and management using queues is adopted in the present embodiment. However, the management may also be performed by a method not using a queue.

The use queue620includes entries for each use sub-pool page. Each entry stores information including a sub-pool page #621, a pool volume #622and a real page #623. Hereinafter, one use sub-pool page (a “target use sub-pool page” in the description ofFIG. 5) will be taken as an example. The sub-pool page #621is a number used to identify the target use sub-pool page. The pool volume #622is a number used to identify a pool volume having a real page associated with the target use sub-pool page. The real page #623is a number used to identify the real page associated with (mapped to) the target use sub-pool page.

The unused queue630includes entries for each unused sub-pool page. Each entry stores information including a sub-pool page #631, a pool volume #632, a real page #633and a garbage flag634. Hereinafter, one use sub-pool page (a “target unused sub-pool page” in the description ofFIG. 5) will be taken as an example. The sub-pool page #631is a number used to identify the target unused sub-pool page. The pool volume #632is a number used to identify a pool volume having a real page associated with the target unused sub-pool page. The real page #623is a number used to identify the real page associated with (mapped to) the target unused sub-pool page. The garbage flag634indicates whether or not the target unused sub-pool page is garbage. The target unused sub-pool page that is not garbage, is a free sub-pool page. By performing the GC processing, the controller31updates the garbage flag634corresponding to the unused sub-pool page which is garbage from “garbage” (a value that means garbage) to “-” (a value that means free).

FIG. 6shows a configuration example of the pool volume table660.

The pool volume table660includes entries for each real pool. Each entry stores information including a pool volume #661, a real page #662, a real page size663and a physical address664. Hereinafter, one real page (a “target real page” in the description ofFIG. 6) is taken as an example.

The pool volume #661is a number used to identify a pool volume having a target real page. The real page #662is a number used to identify the target real page. The real page size663indicates the size of the target real page. The size of the target real page and the size of the sub-pool page associated with the target real page are typically the same. The physical address664indicates an address of a physical storage area (for example, an address of a logical address space provided by the PDEVs34) associated with (mapped to) the target real page.

FIG. 7shows an example of storage hierarchies in the storage system30. Hereinafter, the storage areas will be described in order from a lower layer.

The plurality of PDEVs34configures a RAID group301. A stripe column307spans the plurality of PDEVs34.

A virtual device303which is a virtual storage resource based on the RAID group301is provided with a higher hierarchy than the RAID group301. By dividing the virtual device303(storage space), a plurality of logical devices306are formed in the virtual device303. The virtual device303may be one logical device306. Hereinafter, the logical device will be described as a logical volume.

The pool600is provided with a higher hierarchy than the virtual device303. The pool600includes a plurality of sub-pools601(for example, n sub-pools601-1to601-n). Each sub-pool601has a plurality of sub-pool pages61. The length (size) of the sub-pool page61is defined for each sub-pool601. The lengths of all sub-pool pages in one sub-pool601are the same.

The sub-pool pages641are associated with real pages651of a plurality of pool volumes650. A combination of the sub-pool page61and the real page651(or the sub-pool page61) may be an example of a real area. The pool volume650is associated with any logical volume. The pool volume650is not associated with a target device specified by the host computer10that serves as a higher hierarchy device since the pool volume650is an offline volume. The pool volume650includes a plurality of real pages651. In the example ofFIG. 7, the real page651and the stripe column307correspond to each other in a one-to-one way. Data stored in the real page651is stored in the stripe column307corresponding to the real page651. One real page651may also correspond to a plurality of stripe columns307.

The virtual volume501is a logical address space provided to the host computer10, that is, an online volume. The virtual volume501includes a plurality of virtual pages52. The unused sub-pool page61(garbage or free sub-pool page) in the sub-pool601of the pool600is allocated to the virtual page52which is the write destination not allocated with a sub-pool page61.

A target device316is provided with a higher hierarchy than the virtual volume501. One or more target devices316are associated with a communication port314of a certain communication interface device. The virtual volume501is associated with the target device316.

FIG. 8shows a first example of the relationship between the pool600and the pool volume650.

The pool volume650includes the real pages651all having the same size. The sub-pool601and the pool volume651correspond to each other in a one-to-one manner.

FIG. 9shows a second example of the relationship between the pool600and the pool volume650.

The pool volume650includes a plurality of real pages having different sizes. The sub-pool601and the pool volume651correspond in a many-to-many manner.

FIG. 10is a flowchart of a write processing performed when a write request is received.

In the write request, write destination information including a virtual volume identification number (for example, a logical unit number (LUN)) and a logical address range (for example, a logical block address (LBA) and a data length) is specified. The controller31specifies a write destination virtual page according to the write destination information (S410). The controller31refers to the virtual volume table510and determines whether or not a sub-pool page is allocated to the write destination virtual page (S420).

If the determination result is false in S420(S420: NO), the controller31performs S540, that is, performs the following.

(S420-1) The controller31compresses data to be written (data according to the write request) by the compression/decompression circuit390.

(S420-2) The controller31stores the compressed data (data after compression by the compression/decompression circuit390) in the cache memory32.

(S420-3) The controller31refers to the pool management table610and specifies a free sub-pool page having a size equal to or larger than the size of the compressed data. The size of the specified free sub-pool page may be the smallest size among the sizes equal to or larger than the size of the compressed data, for example.

(S420-4) If there is a difference between the size of the compressed data and the size of the specified free sub-pool page, the controller31adds zero data corresponding to the difference (an example of data for padding) to the compressed data, thereby generating the compressed data for writing on the cache memory32.

(S420-5) The controller31allocates the specified free sub-pool page to the write destination virtual page (for example, transmits information of the sub-pool page from the unused queue630to the use queue620). As a result, the sub-pool page becomes a use sub-pool page.

(S420-6) The controller31writes the compressed data for writing on the cache memory32to the allocated sub-pool page at any timing after completion of the write request is returned to the host computer10(or before the completion is returned). At this time, the controller31refers to the pool management table610and the pool volume table660, and writes the compressed data in a physical address corresponding to the sub-pool page.

If the determination result is true in S420(S420: YES), the controller31performs an overwriting write processing including S430to S460.

Specifically, the controller31performs the following steps in S430.

(S430-1) The controller31refers to the pool volume table660, reads compressed old data from the sub-pool page allocated to the write destination virtual page (hereinafter, “allocated sub-pool page” in the description ofFIG. 10) to the cache memory32, and decompresses the read compressed old data by the compression/decompression circuit390to obtain old data on the cache memory32.

(S430-2) The controller31overwrites new data (data to be written according to the write request) over the old data in the cache memory32.

(S430-3) The controller31compresses the new data by the compression/decompression circuit390to obtain the compressed new data on the cache memory32.

Next, the controller31determines whether or not the size of the compressed new data exceeds the size of the allocated sub-pool page (or the size of the compressed old data) in S440.

If the determination result is false in S440(S440: NO), the controller31performs the following steps in S450.

(S450-1) The controller31refers to the pool management table610and specifies a free sub-pool page having a size equal to or larger than the size of the compressed new data. The size of the specified free sub-pool page may be the smallest size among the sizes equal to or larger than the size of the compressed new data, for example.

(S450-2) If there is a difference between the size of the compressed new data and the size of the specified free sub-pool page, the controller31adds zero data corresponding to the difference (an example of data for padding) to the compressed new data, thereby generating the compressed new data for writing on the cache memory32.

(S450-3) The controller31allocates the specified free sub-pool page to the write destination virtual page instead of the allocated sub-pool page. Specifically, for example, the controller31transmits the information of the sub-pool page from the unused queue630to the use queue620, transmits information of the allocated sub-pool page from the use queue620to the unused queue630, and sets the garbage flag634corresponding to the allocated sub-pool page to “garbage”. As a result, the sub-pool page becomes a use sub-pool page, and the allocated sub-pool page becomes garbage.

(S450-4) The controller31writes the compressed new data for writing on the cache memory32to the allocated sub-pool page at any timing after the completion of the write request is returned to the host computer10(or before the completion is returned).

If the determination result is true in S440(S440: YES), the controller31performs the following steps in S460.

(S460-1) The controller31performs a sub-pool page selection processing.

(S460-2) If there is a difference between the size of the compressed new data and the size of the sub-pool page (garbage or free sub-pool page) selected in the sub-pool page selection processing, the controller31adds zero data corresponding to the difference (an example of padding data) to the compressed new data, thereby generating compressed new data for writing on the cache memory32.

(S460-3) When the selected sub-pool page is a free sub-pool page, the controller31performs the same processing as in (S450-3) and (S450-4).

(S460-4) When the selected sub-pool page is garbage, the controller31performs the following processing. That is, the controller31allocates the selected sub-pool page which is garbage to the write destination virtual page instead of the allocated sub-pool page. Specifically, for example, the controller31transmits the information of the sub-pool page (garbage) from the unused queue630to the use queue620, transmits the information of the allocated sub-pool page from the use queue620to the unused queue630, and sets the garbage flag634corresponding to the allocated sub-pool page to “garbage”. As a result, the garbage becomes a use sub-pool page, and the allocated sub-pool page becomes garbage. Thereafter, the controller31performs the same processing as in (S450-4).

FIG. 11is a flowchart of the sub-pool page selection processing according to the present embodiment.

The controller31refers to the pool management table610and selects a sub-pool from the pool600(S461). Here, for example, a sub-pool including a sub-pool page having the smallest size is selected from sub-pools including sub-pool pages having a size equal to or larger than the size of the compressed new data.

The controller31refers to the pool management table610and determines whether or not there is garbage in the sub-pool selected in S461(S462).

If the determination result is true in S462(S462: YES), the controller31selects any garbage from the sub-pool selected in S461(S463).

If the determination result is false in S462(S462: NO), the controller31determines whether or not there is a sub-pool unselected in S461and including a sub-pool page having a size equal to or larger than the size of the compressed new data (S464). If the determination result is true in S464(S464: YES), S461is performed. If the determination result is false in S464(S464: NO), the controller31selects a free sub-pool page from the sub-pool initially selected in step S461(for example, the sub-pool including a sub-pool page having the smallest size among the sizes equal to or larger than the size of the compressed new data) (S465).

According to the present embodiment, the controller31compresses the data and then writes the compressed data in the sub-pool page, and even in a case where the size of the compressed new data exceeds the size of the allocated sub-pool page, the garbage can be reused (the garbage can be selected as a sub-pool page to be allocated to the write destination virtual page), so that a possibility of increasing the garbage can be reduced. Further, the garbage having a size closest to the size of the compressed new data is reused, so that capacity efficiency can be prevented from decreasing.

Second Embodiment

A second embodiment will be described. In this case, points different from the first embodiment will be mainly described, and description of common points with the first embodiment will be omitted or simplified (the same for the third and subsequent embodiments).

FIG. 12is a flowchart of a sub-pool page selection processing according to the second embodiment.

The sub-pool page selection processing of the write destination according to the second embodiment is different from the first embodiment in that S464is not performed. That is, if the determination result is false in S462(S462: NO), the controller31selects a free sub-pool page from the sub-pool selected in S461(S465).

According to the second embodiment, although a possibility of reusing the garbage is reused compared to the first embodiment, the possibility of increasing the garbage can be reduced. In other words, since the free sub-pool page is selected if there is no garbage having the smallest size among the sizes equal to or larger than the size of the compressed new data, capacity efficiency is preferably avoided from decreasing as compared with the first embodiment.

Third Embodiment

FIG. 13is a flowchart of a sub-pool page selection processing according to a third embodiment.

The controller31refers to the pool management table610and determines whether or not a total pool use amount exceeds a threshold value (S610). The “total pool use amount” is total pool use capacity or a total pool use ratio. The “total pool use capacity” is total capacity of the use sub-pool page. The “total pool use ratio” is a ratio of the total pool use capacity to pool capacity.

If the determination result is true in S610(S610: YES), the controller31performs the sub-pool page selection processing shown inFIG. 11orFIG. 12(S620).

If the determination result is false in S610(S610: NO), the controller31refers to the pool management table610, selects a sub-pool (for example, a sub-pool including a sub-pool page having the smallest size among the sizes equal to or larger than the compressed new data or more) from the pool600, and selects a free sub-pool page from the selected sub-pool (S630).

If the free sub-pool page is sufficient, it is considered that there is no problem even though garbage is not selected. In other words, it is considered that a situation should be avoided in which a sub-pool page able to be allocated is exhausted due to the increase in garbage when the GC processing is not carried out despite actual existence of free capacity. When garbage is little in the pool, the garbage having a size close to the size of the compressed new data may not be found. In such a case, the following problems, for example, are considered in attempting to reuse the garbage.

(x) A processing of searching the garbage leads to an increase in processing cost.

(y) IfFIG. 11is performed, in addition to (x), wasted areas may increase in the sub-pool page since garbage having a large size may be unnecessarily reused.

According to the third embodiment, the capacity efficiency can be increased while reducing overhead since the garbage is reused when a certain amount of garbage that serves as candidate is accumulated. The “total pool use amount” can also be read as “total garbage amount”. The “total garbage amount” is total garbage capacity or a garbage ratio. The “total garbage capacity” is total capacity of the garbage. The “garbage ratio” is a ratio of the total garbage capacity to the pool capacity.

Fourth Embodiment

In a fourth embodiment, a garbage queue is prepared instead of the unused queue630. The garbage queue is a queue of garbage information. One garbage queue may be prepared for each sub-pool page size, and may also be prepared for all sub-pool page sizes, or for each sub-pool page size range.

Although certain embodiments have been described, these embodiments are examples used to describe the invention, and are not intended to limit the scope of the invention. The invention can be implemented in various other forms.

For example, two or more embodiments may be combined.

For example, a plurality of sub-pool pages may be allocated to one virtual page, and the compressed new data may be written into the plurality of sub-pool pages. For example, the controller31may select a plurality of sub-pool pages such that a total size thereof is equal to or larger than the size of the compressed new data, and allocate the selected sub-pool pages to the write destination virtual page. The plurality of sub-pool pages may be a plurality of garbage, a plurality of free sub-pool pages or a combination of one or more garbage and one or more sub-pool pages.

REFERENCE SIGN LIST