Deduplication processing method, and storage device

Patent metadata

Field	Value
Publication number	US-10712945-B2
Application number	US-201816030244-A
Country	US
Kind code	B2
Filing date	Jul 9, 2018
Priority date	Oct 14, 2016
Publication date	Jul 14, 2020
Grant date	Jul 14, 2020

Abstract

A deduplication processing method is provided. A storage device includes a plurality of memories and each memory includes at least one physical block. Parameter information of an initial memory representing any one of the plurality of memories in the storage device is obtained. The parameter information includes at least one of a weight of the at least one physical block in the initial memory or a space usage of the initial memory, and the weight of the at least one physical block corresponding to a next write time point of the at least one physical block. A deduplication weight of the initial memory according to the parameter information of the initial memory is obtained. A target memory having a largest deduplication weight from initial memories is selected and deduplication processing on the at least one physical block of the target memory is performed.

First claim

What is claimed is:

1. A deduplication processing method, comprising:
obtaining, by at least one processor of a storage device, parameter information of an initial memory representing any one of a plurality of memories in the storage device, each memory comprising at least one physical block, the parameter information comprising at least one of a weight of the at least one physical block in the initial memory or a space usage of the initial memory, and the weight of the at least one physical block corresponding to a next write time point of the at least one physical block;
obtaining, by the at least one processor of the storage device, a deduplication weight of the initial memory according to the parameter information of the initial memory; and
selecting, by the at least one processor of the storage device, a target memory having a largest deduplication weight from initial memories and performing deduplication processing on the at least one physical block of the target memory.

2. The method according to claim 1 , wherein the obtaining the parameter information comprises:
for each physical block in the initial memory, obtaining a first time difference of a physical block, the first time difference being a time difference that is between adjacent write time points of the physical block and that is estimated according to historical write time points;
when a write request for the physical block is detected, obtaining, as a corrected time difference, a time difference between a first write time point at which the write request is detected and a previous write time point of the physical block;
obtaining, as a second time difference, an average value of the first time difference and the corrected time difference; and
obtaining a second write time point based on a sum of the first write time point and the second time difference, and obtaining a weight of the physical block according to the second write time point.

3. The method according to claim 1 , further comprising:
for each physical block in the initial memory, forming, by the at least one processor of the storage device, a first-level queue entry including a weight and a physical address of a physical block, and adding the first-level queue entry to a first-level queue of the initial memory, the first-level queue being included in the parameter information; and
arranging, by the at least one processor of the storage device, first-level queue entries corresponding to physical blocks in the initial memory according to weights in the first-level queue.

4. The method according to claim 3 , wherein the selecting comprises:
for each initial memory, forming a second-level queue entry including the deduplication weight and the first-level queue of the initial memory, and adding the second-level queue entry to a second-level queue;
arranging second-level queue entries corresponding to the initial memories according to deduplication weights in the second-level queue; and
extracting a second-level queue entry having the largest deduplication weight from the second-level queue, and determining the target memory corresponding to the second-level queue entry having the largest deduplication weight.

5. The method according to claim 4 , wherein the forming the second-level queue entry comprises:
replacing a physical address of each first-level queue entry in the first-level queue with a corresponding logic address according to an address mapping table, to obtain a mapped first-level queue entry, and forming a mapped first-level queue by using the mapped first-level queue entry, the address mapping table comprising a mapping relationship between the physical address and the corresponding logic address; and
forming the second-level queue entry based on the deduplication weight and the mapped first-level queue of the initial memory.

6. The method according to claim 5 , wherein the performing comprises:
extracting a mapped first-level queue entry having a largest weight from the second-level queue entry having the largest deduplication weight; and
performing the deduplication processing on the at least one physical block corresponding to the logic address in the mapped first-level queue entry having the largest weight.

7. The method according to claim 1 , wherein the parameter information comprises the space usage, and the obtaining the deduplication weight comprises:
obtaining the deduplication weight of the initial memory according to the space usage, the deduplication weight comprising binary values corresponding to the space usage.

8. The method according to claim 1 , wherein the parameter information comprises the weight of the at least one physical block, and the obtaining the deduplication weight comprises:
obtaining the deduplication weight of the initial memory according to a smallest weight in the weight of the at least one physical block, the deduplication weight comprising binary values corresponding to the smallest weight.

9. The method according to claim 1 , wherein the parameter information of the target memory comprises weights of N physical blocks (N being a positive integer), and the performing comprises:
selecting a first physical block having a largest weight from the N physical blocks and performing the deduplication processing on the first physical block; and
subsequently selecting a second physical block having the largest weight from remaining N−1 physical blocks and performing the deduplication processing on the second physical block.

10. The method according to claim 1 , further comprising:
determining, by the at least one processor of the storage device, whether a current time point is a preset transmission time point; and
determining, by the at least one processor of the storage device, the parameter information based on the weight of the at least one physical block when the current time point is the preset transmission time point.

11. The method according to claim 1 , further comprising:
determining, by the at least one processor of the storage device, whether the space usage of any initial memory is greater than a threshold; and
determining, by the at least one processor of the storage device, the parameter information based on the space usage when the space usage of the initial memory is greater than the threshold.

12. The method according to claim 11 , further comprising:
obtaining, by the at least one processor of the storage device, a largest variation in the space usage of the initial memories;
obtaining, by the at least one processor of the storage device, a difference between a first preset space usage and the largest variation; and
determining, by the at least one processor of the storage device, the threshold based on a smaller value between the difference and a second preset space usage, the second preset space usage being less than the first preset space usage.

13. A storage device, comprising a plurality of memories, each memory comprising at least one physical block, the storage device comprising:
at least one memory configured to store program code; and
at least one processor configured to access the at least one memory and operate according to the program code, the program code comprising:
first obtaining code configured to cause the at least one processor to obtain parameter information of an initial memory representing any one of the plurality of memories, the parameter information comprising at least one of a weight of the at least one physical block in the initial memory or a space usage of the initial memory, and the weight of the at least one physical block corresponding to a next write time point of the at least one physical block;
second

Assignees

• Tencent Tech Shenzhen Co Ltd

Inventors

• Wu Chentao
• Huang Xiaosong
• Xiao Lei
• Chen Wei

Classifications

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F16/1752

  based on file chunks · CPC title

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0607

  by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device · CPC title

• G06F12/10

  Address translation · CPC title