STORAGE DEVICE AND DEDUPLICATION METHOD

• US 20110035541A1
• Filed: 10/15/2010
• Published: 02/10/2011
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: TANAKA, Katsuya, MIZUNO, Makio, NAKAMURA, Shuji
• Granted Patent: US 8,156,279 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

This storage device performs deduplication of eliminating duplicated data by storing a logical address of one or more corresponding logical unit memory areas in a prescribed management information storage area of a physical unit memory area defined in the storage area provided by the flash memory chip, and executes a reclamation process of managing a use degree as the total number of the logical addresses used stored in the management information storage area and a duplication degree as the number of valid logical addresses corresponding to the physical unit memory area for each of the physical unit memory areas, and returning the physical unit memory area to an unused status when the difference of the use degree and the duplication degree exceeds a default value in the physical unit memory area.

Claims

1. A flash memory controller for use in a flash memory module,

wherein the flash memory module includes at least one flash memory chip for providing a storage area, wherein the storage area includes a physical unit memory area, and wherein the physical unit memory area includes a prescribed management information storage area,

wherein the flash memory controller controls reading and writing of data from and into the at least one flash memory chip,

wherein the flash memory controller performs deduplication processing by storing logical addresses of one or more corresponding logical unit memory areas in the prescribed management information storage area, wherein the one or more logical unit memory areas are associated with the physical unit memory area, and

wherein the flash memory controller executes a reclamation process that includes

managing a use degree as the total number of the logical addresses stored in the prescribed management information storage area and a duplication degree as the number of valid logical addresses stored in the prescribed management information storage area, and

returning the physical unit memory area to an unused status when a difference of the use degree and the duplication degree exceeds a prescribed value in the physical unit memory area.

2. The flash memory controller of claim 1,

wherein the physical unit memory area is a unit for collectively erasing data;

and

wherein the flash memory controller performs the deduplication processing with the physical unit memory area as the unit.

3. The flash memory controller of claim 1,

wherein the flash memory controller overwrites a logical address that was invalidated among the logical addresses stored in the management information storage area with 0.

4. The flash memory controller of claim 1,

wherein, when the number of the physical unit memory areas storing identical data is X, the total number of valid logical addresses stored in the management information storage area of the physical unit memory area storing the identical data is Y, and the maximum number of the logical addresses that can be stored in the management information storage area is n, and the value calculated with the following formula:

X−

int(Y/n)−

1

is equal or greater than a prescribed value, the flash memory controller eliminates duplicated data by copying the identical data to unused physical unit memory areas in a number calculated with the following formula;

int(Y/n)+1.

5. The flash memory controller of claim 1, wherein the flash memory controller eliminates duplicated data by

selecting a first physical unit memory area with the largest unused management information storage area for the logical address and

selecting a second physical unit memory area with the smallest unused management information storage area for the logical address and the smallest number of valid logical addresses stored in the management information storage area among a plurality of the physical unit memory areas storing identical data, and

copying valid logical addresses stored in the management information storage area of the second physical unit memory area to an unused area of the management information storage area of the first physical unit memory area when the number of unused management information storage areas for the logical address of the first physical unit memory area is equal or greater than the number of the valid logical addresses stored in the management information storage area of the second physical unit memory area.

6. The flash memory controller of claim 1,

wherein the physical unit memory area is a sub block configured from at least one page as a unit for reading and writing data in a physical block as a unit for collectively erasing data.

7. A flash memory controller for use in a flash memory module in a storage device,

wherein the flash memory module includes at least one flash memory chip for providing a storage area, wherein the storage area includes a physical unit memory area, and wherein the physical unit memory area includes a prescribed management information storage area, and

wherein the storage device includes a storage controller for controlling the reading and writing of data from and into the flash memory module and for partitioning data in the flash memory module in a prescribed unit,

wherein the flash memory controller

performs deduplication processing to data of a data size that is equal or less than the prescribed unit, wherein the deduplication processing includes storing logical addresses of one or more corresponding logical unit memory areas in the prescribed management information storage area, wherein the one or more logical unit memory areas are associated with the physical unit memory area, and

executes a reclamation process that includes

managing a use degree as the total number of the logical addresses stored in the prescribed management information storage area and

managing a duplication degree as the number of valid logical addresses corresponding to the physical unit memory area for the physical unit memory area, and

returning the physical unit memory area to an unused status when a difference of the use degree and the duplication degree exceeds a default value in the physical unit memory area.

8. The flash memory controller of claim 7, wherein the flash memory controller receives a command from the storage controller to perform the deduplication processing.

9. The flash memory controller of claim 8, wherein the availability of execution of the deduplication processing can be set for the storage area.

10. A method for use in a flash memory controller in a flash memory module,

wherein the flash memory module includes at least one flash memory chip for providing a storage area, wherein the storage area includes a physical unit memory area, and wherein the physical unit memory area includes a prescribed management information storage area,

wherein the method comprises:

a first step of the flash memory controller performing deduplication processing by storing logical addresses of one or more corresponding logical unit memory areas in the prescribed management information storage area, wherein the one or more logical unit memory areas are associated with the physical unit memory area; and

a second step of the flash memory controller executing a reclamation process that includes;

managing a use degree as the total number of the logical addresses used stored in the prescribed management information storage area;

managing a duplication degree as the number of valid logical addresses stored in the prescribed management information storage area; and

returning the physical unit memory area to an unused status when a difference of the use degree and the duplication degree exceeds a prescribed value in the physical unit memory area.

11. The method of claim 10,

wherein the physical unit memory area is a unit for collectively erasing data;

and

wherein the deduplication processing is performed with the physical unit memory area as the unit.

12. The method of claim 10,

wherein, at the second step, a logical address that was invalidated among the logical addresses stored in the management information storage area is overwritten with 0.

13. The method of claim 10,

wherein, at the first step, when the number of the physical unit memory areas storing identical data is X, the total number of valid logical addresses stored in the management information storage area of the physical unit memory area storing the identical data is Y, and the maximum number of the logical addresses that can be stored in the management information storage area is n, and the value calculated with the following formula:

X−

int(Y/n)−

1

is equal or greater than a prescribed value, duplicated data is eliminated by copying the identical data to unused physical unit memory areas in a number calculated with the following formula;

int(Y/n)+1.

14. The method of claim 10, wherein, at the second step, duplicated data is eliminated by

selecting a first physical unit memory area with the largest unused management information storage area for the logical address, selecting a second physical unit memory area with the smallest unused management information storage area for the logical address and the smallest number of valid logical addresses stored in the management information storage area among a plurality of the physical unit memory areas storing identical data, and

copying valid logical addresses stored in the management information storage area of the second physical unit memory area to an unused area of the management information storage area of the first physical unit memory area when the number of unused management information storage areas for the logical address of the first physical unit memory area is equal or greater than the number of the valid logical addresses stored in the management information storage area of the second physical unit memory area.

15. The method of claim 10,

wherein the physical unit memory area is a sub block configured from at least one page as a unit for reading and writing data in a physical block as a unit for collectively erasing data.

16. A method for use in a flash memory controller in a flash memory module in a storage device,

wherein the flash memory module includes at least one flash memory chip for providing a storage area, wherein the storage area includes a physical unit memory area, and wherein the physical unit memory area includes a prescribed management information storage area, and

wherein the storage device includes a storage controller for controlling the reading and writing of data from and into the flash memory module and for partitioning data in the flash memory module in a prescribed unit, wherein the method comprises:

the flash memory controller performing deduplication processing to data of a data size that is equal or less than the prescribed unit, wherein the deduplication processing includes storing logical addresses of one or more corresponding logical unit memory areas in the prescribed management information storage area, wherein the one or more logical unit memory areas are associated with the physical unit memory area;

the flash memory controller performing a reclamation process that includes;

managing a use degree as the total number of the logical addresses stored in the prescribed management information storage area;

managing a duplication degree as the number of valid logical addresses corresponding to the physical unit memory area for the physical unit memory area; and

returning the physical unit memory area to an unused status when a difference of the use degree and the duplication degree exceeds a default value in the physical unit memory area.

17. The method of claim 16, further comprising:

the flash memory controller receiving a command from the storage controller to perform the deduplication processing.

18. The method of claim 17, wherein the availability of execution of the deduplication processing can be set for the storage area.