Data duplication detection system and method for controlling data duplication detection system

• US 9,239,844 B2
• Filed: 03/29/2013
• Issued: 01/19/2016
• Est. Priority Date: 03/29/2013
• Status: Expired due to Fees

• Current Assignee: Hitachi Information & Telecommunication Engineering, Ltd. (Hitachi, Ltd.), Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kishi, Masayuki
• Primary Examiner(s): MOSER, BRUCE M
• Application Number:
  US14/343,644
• Publication Number:
  US 20150220554A1
• Time in Patent Office: 1,026 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

Accurate and efficient detection of data duplication is implemented. A data duplication determination part (1A) of a storage system (1) temporarily stores in a pool (4) a target chunk data when a second management table (T2) indicates that the target chunk data, which is included in received data, has already been stored, and, in addition, when data (a fingerprint (FP)) for guaranteeing the identity of the target chunk data is not stored in a third management table (T3). The duplication determination part (1A), in a case where the second management table indicates that another target chunk data that differs from the target chunk is already stored, and, in addition, in a case where determination is made that the FP of the other target chunk data is stored in the third management table, makes a redetermination as to whether the chunk data stored in the pool has already been stored.

Claims

1. A data duplication detection system for detecting a duplication of data, the data duplication detection system comprising:

a data duplication determination part configured to determine whether each of a plurality of pieces of chunk data formed by dividing a received data is a duplicate of chunk data that has already been stored;

a storage part configured to store chunk data that has been determined not to be duplicative by the data duplication determination part;

a first management table configured to manage, for each piece of chunk data stored in the storage part, identity guarantee data that indicates a data identity, with the identity guarantee data being associated with storage-destination information that indicates a data storage destination;

a second management table created on the basis of the identity guarantee data for the each piece of chunk data stored in the storage part, the second management table being configured to indicate with prescribed reliability that a piece of chunk data is stored in the storage part, the prescribed reliability being a probability equal to greater than a probability threshold value, the threshold value calculated based on a number of prescribed hash functions used to determine hash values for the piece of chunk data and a number of bits of a bit string that indicates the hash values at positions of the bit string corresponding to the hash values; and

a third management table configured to manage a plurality of chunk data sets formed by grouping together the pieces of chunk data stored in the storage part, the third management table being configured to manage the identity guarantee data for prescribed chunk data that represents each of the plurality of chunk data sets,

wherein the data duplication determination part;

in a case where the second management table indicates that a target chunk data included in the received data is stored in the storage part, and, in addition, in a case where determination is made that the identity guarantee data for the target chunk data is not stored in the third management table, temporarily stores the target chunk data in a temporary storage part;

in a case where the second management table indicates that a second target chunk data that differs from the target chunk data is stored in the storage part, and, in addition, in a case where determination is made that the identity guarantee data for the second target chunk data is stored in the third management table, determines whether the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table;

in a case where determination is made that the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table, determines that the target chunk data stored in the temporary storage part is already stored in the storage part; and

in a case where determination is made that the identity guarantee data for the target chunk data stored in the temporary storage part is not stored in the first management table, determines that the target chunk data stored in the temporary storage part is not stored in the storage part.

2. A data duplication detection system according to claim 1, wherein the first management table is configured to manage the chunk data for one of the plurality of chunk data sets identified by a chunk data set identifier, and

the data duplication determination part, in a case where determination is made that the second target chunk data is stored in the third management table, determines whether the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table corresponding to the chunk data set to which the second target chunk data belongs, from among a plurality of first management tables corresponding to each of the plurality of chunk data sets identified by a corresponding chunk data set identifier.

3. A data duplication detection system according to claim 2, wherein the data duplication determination part, in a case where determination is made that the target chunk data stored in the temporary storage part is not stored in the storage part, stores the target chunk data in the storage part as new chunk data, and, in addition, updates the first management table, the second management table, and the third management table.

4. A data duplication detection system according to claim 3, wherein the data duplication determination part, in a case where the target chunk data that has been stored in the temporary storage part is stored in the storage part as the new chunk data, discards the target chunk data serving as the new chunk data stored in the temporary storage part to release a storage area in the temporary storage part.

5. A data duplication detection system according to claim 4, wherein the data duplication determination part stores in the storage part the target chunk data that has been stored in the temporary storage part as the new chunk data when the usage of the temporary storage part reaches a prescribed upper limit value.

6. A data duplication detection system according to claim 5, wherein the data duplication determination part is able to use a memory, the first management tables corresponding to each of the plurality of chunk data sets are stored in the storage part, and the first management table corresponding to the chunk data set to which the second target chunk data belongs is transferred from the storage part and stored in the memory.

7. A data duplication detection system according to claim 6, wherein the data duplication determination part:

when receiving data, first uses the first management table in the memory and determines whether identity guarantee data of the target chunk data included in the received data is stored in the storage part;

when determining that the identity guarantee data for the target chunk data is not stored in the first management table in the memory, determines whether the second management table indicates that the target chunk data is stored in the storage part;

when the second management table indicates that the target chunk data is stored in the storage part, determines whether the identity guarantee data for the target chunk data is stored in the third management table; and

when determining that the identity guarantee data for the target chunk data is not stored in the third management table, stores the target chunk data in the temporary storage part.

8. A data duplication detection system according to claim 1, comprising:

a computer apparatus communicably connected to a host computer and the storage part, and having a microprocessor and a memory,

wherein the data duplication determination part is realized by the microprocessor executing a prescribed data duplication determination program stored beforehand in the memory,

wherein the data duplication determination part comprises a first determination part, a second determination part, a third determination part, and a fourth determination part,

wherein the first determination part determines whether the identity guarantee data for the target chunk data included in the received data is stored in the first management table in the memory that is configured to manage the chunk data for one of the plurality of chunk data sets, and upon determining that the identity guarantee data is stored in the first management table in the memory, determines that the target chunk data is stored in the storage part,

the second determination part, when the first determination part has determined that the identity guarantee data for the target chunk data is not stored in the first management table in the memory, determines whether the second management table indicates that the target chunk data is stored in the storage part, and when determining that the target chunk data is new chunk data that is not stored in the storage part, stores the new chunk data in the storage part,

the third determination part, when the second management table indicates that the identity guarantee data for the target chunk data is stored in the storage part, determines whether the identity guarantee data for the target chunk data is stored in the third management table, and when determining that the identity guarantee data for the target chunk data is stored in the third management table, determines that the target chunk data is stored in the storage part, and upon determining that the identity guarantee data for the target chunk data is not stored in the third management table, stores the target chunk data in the temporary storage part, and

the fourth determination part, when the third determination part has determined that the identity guarantee data for a second target chunk data that differs from the target chunk is stored in the third management table, transfers and stores in the memory the first management table corresponding to the chunk data set to which the second target chunk data belongs, and determines whether the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table in the memory,

when the fourth determination part has determined that the identity guarantee data for the target chunk data is stored in the first management table in the memory, the data duplication determination part determines that the target chunk data stored in the temporary storage part is already stored in the storage part, and deletes the target chunk data from the temporary storage part,

when the fourth determination part has determined that the identity guarantee data for the target chunk data is not stored in the first management table in the memory, the data duplication determination part determines that the target chunk data stored in the temporary storage part is new chunk data that is not stored in the storage part, stores the new chunk data in the storage part, and

deletes the target chunk data from the temporary storage part, and when the temporary storage part usage reaches a prescribed upper limit value, the data duplication determination part stores the target chunk data stored in the temporary storage part in the storage part as the new chunk data.

9. A data duplication detection system according to claim 1, wherein,

the second management table indicates that a target chunk data included in the received data is stored in the storage part when each of the bits at the positions of the bit string corresponding to the hash values indicate the hash values for the target chunk data, and

the second management table indicates that a target chunk data included in the received data is not stored in the storage part when any of the bits at the positions of the bit string corresponding to the hash values do not indicate the hash values for the target chunk data.

10. A method for controlling a data duplication detection system for detecting a duplication of data, the data duplication detection system including:

a data duplication determination part configured to determine whether each of a plurality of pieces of chunk data formed by dividing a received data is a duplicate of chunk data that has already been stored;

a storage part configured to store chunk data that has been determined not to be duplicative by the data duplication determination part;

a first management table configured to manage, for each piece of chunk data stored in the storage part, identity guarantee data that indicates a data identity, with the identity guarantee data being associated with storage-destination information that indicates a data storage destination;

a second management table created on the basis of the identity guarantee data for the each piece of chunk data stored in the storage part, the second management table being configured to indicate with prescribed reliability that a piece of chunk data is stored in the storage part, the prescribed reliability being a probability equal to greater than a probability threshold value, the threshold value calculated based on a number of prescribed hash functions used to determine hash values for the piece of chunk data and a number of bits of a bit string that indicates the hash values at positions of the bit string corresponding to the hash values; and

a third management table configured to manage a plurality of chunk data sets formed by grouping together the pieces of chunk data stored in the storage part, the third management table being configured to manage the identity guarantee data for prescribed chunk data that represent each of the plurality of chunk data sets,

the data duplication detection system control method comprising;

operating the data duplication determination part;

in a case where the second management table indicates that a target chunk data included in the received data is stored in the storage part, and, in addition, in a case where determination is made that the identity guarantee data for the target chunk data is not stored in the third management table, to store the target chunk data in a temporary storage part for temporarily storing the target chunk data;

in a case where the second management table indicates that a second target chunk data that differs from the target chunk is stored in the storage part, and, in addition, in a case where determination is made that the identity guarantee data for the other second target chunk data is stored in the third management table, to determine whether the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table;

in a case where the identity guarantee data for the target chunk data stored in the temporary storage part is stored in the first management table, to determine that the target chunk data stored in the temporary storage part is already stored in the storage part; and

in a case where determination is made that the identity guarantee data for the target chunk data stored in the temporary storage part is not stored in the first management table, to determine that the target chunk data stored in the temporary storage part is not stored in the storage part.

11. A method for controlling a data duplication detection system according to claim 10, wherein the first management table is configured to manage the chunk data for one of the plurality of chunk data sets identified by a chunk data set identifier, and the data duplication determination part, when determining that the second target chunk data is stored in the third management table, determines whether the identity guarantee data for the target chunk data stored in the temporary storage part is stored in a first management table corresponding to the chunk data set to which the second target chunk data belongs, from among a plurality of first management tables corresponding to each of the plurality of chunk data sets identified by a corresponding chunk data set identifier.

12. A method for controlling a data duplication detection system according to claim 11, wherein the data duplication determination part, when determining that the target chunk data stored in the temporary storage part is not stored in the storage part, stores the target chunk data in the storage part as new chunk data, and, in addition, updates the first management table, the second management table, and the third management table.

13. A method for controlling a data duplication detection system according to claim 12, wherein the data duplication determination part, when storing in the storage part the target chunk data that had been stored in the temporary storage part as the new chunk data, discards the target chunk data serving as the new chunk data stored in the temporary storage part to release a storage area in the temporary storage part.

14. A method for controlling a data duplication detection system according to claim 13, wherein the data duplication determination part stores in the storage part the target chunk data that is stored in the temporary storage part as the new chunk data when the temporary storage part usage reaches a prescribed upper limit value.