Storage device and deduplication method

• US 7,818,495 B2
• Filed: 01/28/2008
• Issued: 10/19/2010
• Est. Priority Date: 09/28/2007
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Nakamura, Shuji, Mizuno, Makio, Tanaka, Katsuya
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Faal; Baboucarr
• Application Number:
  US12/010,602
• Publication Number:
  US 20090089483A1
• Time in Patent Office: 995 Days
• Field of Search: None
• 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 storage device equipped with one or more flash memory modules, wherein one or more said flash memory modules comprises:

at least one flash memory chip for providing a storage area; and

a controller for controlling the reading and writing of data from and into said at least one flash memory chip; and

wherein said controller 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 said storage area provided by said at least one flash memory chip, and executes a reclamation process of managing a use degree as the total number of said logical addresses stored in said prescribed management information storage area and a duplication degree as the number of valid logical addresses corresponding to said physical unit memory area for said physical unit memory area, and returns said physical unit memory area to an unused status when a difference of said use degree and said duplication degree exceeds a default value in said physical unit memory area.

2. The storage device according to claim 1,

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

and

wherein said controller reads and writes said storage area data provided by said flash memory chip and executes processing for said deduplication with said physical unit memory area as the unit.

3. The storage device according to claim 1,

wherein said controller overwrites said logical address that was invalidated among said logical addresses stored in said management information storage area with 0.

4. The storage device according to claim 1,

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

[Formula 1]

X−

int(Y/n)−

1 

 

(1)

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

[Formula 2]

int(Y/n)+1 

 

(2).

5. The storage device according to claim 1,

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

and

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

6. The storage device according to claim 1,

wherein said 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 storage device comprising a plurality of flash memory modules for providing a storage area, and a storage controller for controlling the reading and writing of data from and into said plurality of flash memory modules, wherein said storage controller reads and writes data from and into said plurality of flash memory modules by partitioning said data in a prescribed unit, and performs deduplication processing to data of a data size that is equal or greater than said prescribed unit for eliminating duplicated data to an extent across said plurality of flash memory modules;

and wherein said plurality of flash memory modules perform deduplication processing to data of a data size that is equal or less than said prescribed unit for each flash memory module;

and said controller 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 said storage area provided by said at least one flash memory module, and executes a reclamation process of managing a use degree as the total number of said logical addresses stored in said prescribed management information storage area and a duplication degree as the number of valid logical addresses corresponding to said physical unit memory area for said physical unit memory area, and returns said physical unit memory area to an unused status when a difference of said use degree and said duplication degree exceeds a default value in said physical unit memory area.

8. The storage device according to claim 7,

wherein said storage controller commands a processing unit of said deduplication processing in said flash memory module to said plurality of flash memory modules.

9. The storage device according to claim 8,

wherein the availability of execution of said deduplication processing to be executed by said storage controller or said flash memory module can be set for each storage area of a prescribed unit.

10. A deduplication method of eliminating duplication of data in a storage device equipped with one or more flash memory modules having at least one flash memory chip for providing a storage area, comprising:

a first step of performing deduplication processing 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 said storage area provided by said at least one flash memory chip, and managing a use degree as the total number of said logical addresses stored in said prescribed management information storage area and a duplication degree as the number of valid logical addresses corresponding to said physical unit memory area for each of said physical unit memory area; and

a second step of executing a reclamation process of returning said physical unit memory area to an unused status when a difference of said use degree and said duplication degree exceeds a default value in said physical unit memory area.

11. The deduplication method according to claim 10,

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

and

wherein a flash memory module reads and writes said storage area data provided by said flash memory chip and executes processing for said deduplication with said physical unit memory area as the unit.

12. The deduplication method according to claim 10,

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

13. The deduplication method according to claim 10,

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

[Formula 3]

X−

int(Y/n)−

1 

 

(3)

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

[Formula 4]

int(Y/n)+1 

 

(4).

14. The deduplication method according to claim 10,

wherein, at said second step, duplicated data is eliminated by selecting a first physical unit memory area with the largest unused management information storage area for said logical address and selecting a second physical unit memory area with the smallest unused management information storage area for said logical address and the smallest number of valid logical addresses stored in said management information storage area among a plurality of said physical unit memory areas storing identical data;

and

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

15. The deduplication method according to claim 10,

wherein said 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 deduplication method of eliminating duplication of data in a device comprising a plurality of flash memory modules for providing a storage area, and a storage controller for controlling the reading and writing of data from and into said plurality of flash memory modules, comprising:

a first step of said storage controller reading and writing data from and into said plurality of flash memory modules by partitioning said data in a prescribed unit, and performing deduplication processing to data of a data size that is equal or greater than said prescribed unit for eliminating duplicated data to an extent across said plurality of flash memory modules; and

a second step of said plurality of flash memory modules performing deduplication processing to data of a data size that is equal or less than said prescribed unit for each flash memory module;

wherein said controller 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 said storage area provided by said at least one flash memory module, and executes a reclamation process of managing a use degree as the total number of said logical addresses stored in said prescribed management information storage area and a duplication degree as the number of valid logical addresses corresponding to said physical unit memory area for said physical unit memory area, and returns said physical unit memory area to an unused status when a difference of said use degree and said duplication degree exceeds a default value in said physical unit memory area.

17. The deduplication method according to claim 16,

wherein, at said second step, a processing unit of said deduplication processing in said flash memory module is commanded to said plurality of flash memory modules by said storage controller.

18. The deduplication method according to claim 17,

wherein the availability of execution of said deduplication processing to be executed by said storage controller or said flash memory module can be set for each storage area of a prescribed unit.