METHOD FOR DE-DUPLICATING DATA AND APPARATUS THEREFOR

• US 20140258655A1
• Filed: 03/07/2014
• Published: 09/11/2014
• Est. Priority Date: 03/07/2013
• Status: Active Grant

• Current Assignee: Postech Academy-Industry Foundation
• Original Assignee: Postech Academy-Industry Foundation
• Inventors: Park, Chan Ik, Park, Se Jin
• Granted Patent: US 9,851,917 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0628 making use of a particular technique
• CPC Class Codes: G06F 3/0632 by initialisation or re-initialisation of storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0668 adopting a particular infrastructure
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Disclosed are a method for data de-duplication and an apparatus for the same. The method may comprise obtaining access property of data based on input request or output request for the data, determining de-duplication unit of the data based on the access property, and performing de-duplication on the data based on the de-duplication unit. Thus, data de-duplication rate may be determined adaptively based on input/output characteristics of data. Also, data de-duplication may be performed based on the determined data de-duplication rate so as to provide low input/output latency.

Claims

1. A method for data de-duplication, performed in an apparatus for data de-duplication, comprising:

obtaining access property of data based on input request or output request for the data;

determining de-duplication unit of the data based on the access property; and

performing de-duplication on the data based on the de-duplication unit.

2. The method of claim 1, wherein the access property includes at least one of access time on the data, modification time on the data, a number of sequential accesses on the data, and a number of random accesses on the data.

3. The method of claim 2, wherein the obtaining access property comprises:

obtaining the access time and the modification time based on time information of the input request when the input request is received; and

obtaining the number of sequential accesses on the data or the number of random accesses on the data based on continuity of the input request.

4. The method of claim 2, wherein the obtaining access property comprises:

obtaining the access time based on time information of the output request when the output request is received; and

obtaining the number of sequential accesses on the data or the number of random accesses on the data based on continuity of the output request.

5. The method of claim 2, wherein the determining de-duplication unit of the data comprises:

calculating a first difference between a current access time on the data and a previous modification time on the data;

determining a fourth de-duplication unit having a lowest de-duplication probability as the de-duplication unit of the data when the first difference is equal to or less than a predefined first threshold;

calculating a second difference between the current access time on the data and the previous access time on the data when the first difference is in excess of the first threshold;

determining a first de-duplication unit having a highest de-duplication probability as the de-duplication unit of the data when the second difference is in excess of a predefined second threshold;

determining a second de-duplication unit having a lower de-duplication probability than the first de-duplication unit as the de-duplication unit of the data when the second difference is equal to or less than the second threshold and the number of random accesses on the data is equal to and more than the number of sequential accesses on the data; and

determining a third de-duplication unit having a lower probability of being de-duplicated than the second de-duplication unit as the de-duplication unit of the data when the second difference is equal to or less than the second threshold and the number of random accesses on the data is less than the number of sequential accesses on the data.

7. The method of claim 1, wherein the performing de-duplication on the data comprises:

generating at least one data block of the data based on the de-duplication unit;

generating unique identifier for the at least one data block;

determining whether the unique identifier is in an index table or not;

removing a data block corresponding to the unique identifier when the unique identifier is in the index table; and

storing the unique identifier and the data block corresponding to the unique identifier when the unique identifier is not in the index table.

8. The method of claim 7, wherein the unique identifier is generated using a hash algorithm.

9. The method of claim 1, wherein the de-duplication unit is classified into at least one de-duplication units each of which has different de-duplication probability.

6. The method of claim 6, wherein de-duplication is not performed for the fourth de-duplication unit.

10. An apparatus for data de-duplication, comprising:

a processing part configured to obtain access property of data based on input request or output request for the data, determine de-duplication unit of the data based on the access property, and perform de-duplication on the data based on the de-duplication unit; and

a storage part configured to store information which is processed or has been processed in the processing part.

11. The apparatus of the claim 10, wherein the access property includes at least one of access time on the data, modification time on the data, a number of sequential accesses on the data, and a number of random accesses on the data.

12. The apparatus of the claim 11, wherein the processing part is further configured to obtain the access time and the modification time based on time information of the input request when the input request is received, and obtain the number of sequential accesses on the data or the number of random accesses on the data based on continuity of the input request.

13. The apparatus of the claim 11, wherein the processing part is further configured to obtain the access time based on time information of the output request when the output request is received, and obtain the number of sequential accesses on the data or the number of random accesses on the data based on continuity of the output request.

14. The apparatus of the claim 11, wherein the processing part is further configured to calculate a first difference between a current access time on the data and a previous access time on the data, determine a fourth de-duplication unit having a lowest de-duplication probability as the de-duplication unit of the data when the first difference is equal to or less than a predefined first threshold, calculate a second difference between the current access time on the data and the previous access time on the data when the first difference is in excess of the first threshold, determine a first de-duplication unit having a highest de-duplication probability as the de-duplication unit of the data when the second difference is in excess of a predefined second threshold, determine a second de-duplication unit having a lower de-duplication probability than the first de-duplication unit as the de-duplication unit of the data when the second difference is equal to or less than the second threshold and the number of random accesses on the data is equal to and more than the number of sequential accesses on the data, and determine a third de-duplication unit having a lower de-duplication probability than the second de-duplication unit as the de-duplication unit of the data when the second difference is equal to or less than the second threshold and the number of random accesses on the data is less than the number of sequential accesses on the data.

15. The apparatus of the claim 14, wherein de-duplication is not performed for the fourth de-duplication unit.

16. The apparatus of the claim 10, wherein the processing part is further configured to generate at least one data block of the data based on the de-duplication unit, generate unique identifier for the at least one data block, determine whether the unique identifier is in an index table or not, remove a data block corresponding to the unique identifier when the unique identifier is in the index table, and store the unique identifier and the data block corresponding to the unique identifier when the unique identifier is not in the index table.

17. The apparatus of the claim 16, wherein the unique identifier is generated using a hash algorithm.

18. The apparatus of the claim 10, wherein the de-duplication unit is classified into at least one de-duplication units each of which has different de-duplication probability.