FRAGMENTATION CONTROL FOR PERFORMING DEDUPLICATION OPERATIONS

• US 20130226881A1
• Filed: 02/29/2012
• Published: 08/29/2013
• Est. Priority Date: 02/29/2012
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Sharma, Alok, Walwaiker, Sunil, Bharadwaj, Vaijayanti
• Granted Patent: US 9,026,503 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• 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/2272 Management thereof
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

The techniques introduced here provide for enabling deduplication operations for a file system without significantly affecting read performance of the file system due to fragmentation of the data sets in the file system. The techniques include determining, by a storage server that hosts the file system, a level of fragmentation that would be introduced to a data set stored in the file system as a result of performing a deduplication operation on the data set. The storage server then compares the level of fragmentation with a threshold value and determines whether to perform the deduplication operation based on a result of comparing the level of fragmentation with the threshold value. The threshold value represents an acceptable level of fragmentation in the data sets of the file system.

Claims

1. A method comprising:

calculating, by a storage server, a level of fragmentation that would be introduced to a data set stored by the storage server as a result of a deduplication operation on the data set; and

determining, by the storage server, whether to perform the deduplication operation based on a result of said calculating.

2. The method of claim 1 further comprising, comparing, by the storage server, the level of fragmentation with a threshold value to determine whether to perform the deduplication operation.

3. The method of claim 1, wherein determining the level of fragmentation includes:

calculating a number of read operations needed to access the data set after the deduplication operation;

calculating a number of read operations needed to access an ideal data set; and

calculating a fragmentation index representative of the level of fragmentation based on the number of read operations needed to access the data set after the deduplication and the number of read operations needed to access the ideal data set, wherein determining whether to perform the deduplication operation is based on the fragmentation index.

4. The method of claim 3, wherein the fragmentation index is a ratio of the number of read operations to access the data set after the deduplication operation and the number of read operations needed to access the ideal data set.

5. The method of claim 3, wherein calculating the number of read operations needed to access the data set after the deduplication operation includes:

determining an address of a donor block for each of a plurality of blocks in the data set that are to be shared in the deduplication operation;

creating an address list that includes an address for each of the blocks of the data set after the deduplication operation;

sorting the addresses in the address list in the order they occur on a storage device;

calculating, from the address list, the number of read operations needed to access the data set after the deduplication operation.

6. The method of claim 2, wherein the threshold value represents a maximum acceptable level of fragmentation for the data set.

7. The method of claim 2 further comprising, performing the deduplication operation in response to determining that the level of fragmentation is below the threshold value.

8. The method of claim 2 further comprising, not performing the deduplication operation in response to determining that the level of fragmentation is above the threshold value.

9. The method of claim 2, wherein the threshold value is set based on user input.

10. A method comprising:

calculating a fragmentation index representative of a level of fragmentation that would be introduced to a data set stored on a storage server as a result of performing a deduplication operation on the data set, wherein the fragmentation index is a ratio of a number of read operations needed to access the data set after the deduplication operation and a number of read operations needed to access an ideal data set;

comparing the fragmentation index with a threshold to determine whether to perform the deduplication operation; and

performing the deduplication operation based on a result of the comparing.

11. The method of claim 10 further comprising:

determining an address of a donor block for each of a plurality of blocks in the data set that are to be shared in the deduplication operation;

creating an address list that includes an address for each block of the data set after the deduplication operation;

sorting the addresses in the address list in the order they occur on a storage device;

calculating, from the address list, the number of read operations needed to access the data set after the deduplication operation.

12. The method of claim 10, wherein the threshold value represents a maximum acceptable level of fragmentation for the data set.

13. The method of claim 10 further comprising:

performing the deduplication operation in response to determining that the fragmentation index is below the threshold value.

14. The method of claim 10 further comprising:

not performing the deduplication operation in response to determining that the fragmentation index is above the threshold value.

15. The method of claim 10, wherein the threshold value is set based on user input.

16. A storage server comprising:

a processor;

a memory coupled with the processor, the memory storing instructions which when executed by the processor cause the processor to perform a plurality of operations, including;

calculating a level of fragmentation that would be introduced to a data set stored by the storage server as a result of a deduplication operation on the data set; and

determining whether to perform the deduplication operation based on a result of said calculating.

17. The storage server of claim 16, wherein the operations further include comparing the level of fragmentation with a threshold value to determine whether to perform the deduplication operation.

18. The storage server of claim 16, wherein determining the level of fragmentation includes:

calculating the number of read operations needed to access the data set after the deduplication operation;

calculating the number of read operations needed to access an ideal data set; and

calculating a fragmentation index representative of the level of fragmentation based on the number of read operations needed to access the data set after the deduplication and the number of read operations needed to access the ideal data set.

19. The storage server of claim 18, wherein the fragmentation index is a ratio of the number of read operations to access the data set after the deduplication operation and the number of read operations needed to access the ideal data set.

20. The storage system of claim 18, wherein calculating the number of read operations needed to access the data set after the deduplication operation includes:

determining an address of a donor block for each of a plurality of blocks in the data set that are to be shared in the deduplication operation;

creating an address list that includes an address for each block of the data set after the deduplication operation;

sorting the addresses in the address list in the order they occur on a storage device;

calculating, from the address list, the number of read operations needed to access the data set after the deduplication operation.

21. The storage system of claim 17, wherein the threshold value represents a maximum acceptable level of fragmentation for the data set.

22. The storage system of claim 17, wherein the operations further include:

performing the deduplication operation in response to determining that the level of fragmentation is below the threshold value.

23. The storage system of claim 17, wherein the operations further include:

not performing the deduplication operation in response to determining that the level of fragmentation is above the threshold value.

24. The storage server of claim 17, wherein the threshold value is set based on user input.