File folding technique

• US 7,072,910 B2
• Filed: 03/22/2002
• Issued: 07/04/2006
• Est. Priority Date: 03/22/2002
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Kahn, Andy C., Edwards, John K., Chen, Raymond C., Patel, Kayuri
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/104,694
• Publication Number:
  US 20030182317A1
• Time in Patent Office: 1,565 Days
• Field of Search: 707/100, 707/1, 707/202, 707/201, 707/204, 707/200, 707/203, 707/205
• US Class Current: 707/639
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A file folding technique reduces the number of duplicate data blocks of a file consumed on a storage device of a file server configured to generate a persistent image of its active file system at a point in time. According to the file folding technique, if “old” data blocks of the file are over-written with “new” data and that new data is identical to the data of the persistent file image, the old data blocks are “freed” and the file is directed to refer to the persistent image for its data. The invention reduces disk space consumption in a file server configured to generate persistent images of its active file system and, in particular, reduces overall persistent image disk usage.

Claims

1. A method for reducing duplicate data of a file stored on a storage device of a server having an active file system, the method comprising the steps of:

generating a persistent image of old data for the file in the active file system;

overwriting the old data of the file in the active file system with new data;

comparing contents of the data blocks for the active file system and persistent image on a block-by-block basis;

determining whether the new data is identical to the old data of the persistent image; and

if so, folding the new data of the file in the active file system into the old data of the persistent image.

2. The method of claim 1 wherein the step of determining comprises the steps of:

obtaining a full pathname of the file in the active file system;

constructing a corresponding filename to the file in the persistent image; and

loading inodes of the active file system and persistent image files into a memory of the server.

3. The method of claim 2 wherein the step of determining further comprises the steps of:

traversing inode buffer trees for both the active file system and the persistent image; and

loading indirect blocks of the active file system and the persistent image into the memory.

4. The method of claim 1 wherein the step of folding comprises the step of freeing the data block of the file in the active file system.

5. The method of claim 4 wherein the step of freeing comprises the step of updating a corresponding bit of an active map of the active file system to indicate that the block is not allocated.

6. The method of claim 4 wherein the step of folding further comprises the step of allocating a VBN of the data block in the persistent image.

7. The method of claim 6 wherein the step of allocating comprises the step of updating a bit of an active map corresponding to the data block in the persistent image to indicate that the block is being used.

8. The method of claim 6 wherein the step of folding further comprises the step of updating the file in the active file system to refer to the persistent image for data of the file.

9. A The method of claim 8 wherein the step of updating comprises the step of updating a block pointer of an inode of the file in the active file system to reference the VBN of the data block in the persistent image.

10. The method of claim 9 further comprising the step of marking the inode as dirty to ensure that it is written to the storage device.

11. A method for reducing duplicate data of a file stored on a storage device of a server having an active file system, the method comprising the steps of:

generating a persistent image of old data for the file in the active file system;

overwriting the old data of the file in the active file system with new data;

comparing a virtual block number (VBN) of each indirect block from the active file system with a VBN of a corresponding indirect block from the persistent image;

determining whether the VBNS are equal;

if the VBNS are equal, aborting further processing of the indirect blocks;

if the VBNS are not equal, comparing contents of the data blocks associated with the indirect blocks for the active file system and the indirect blocks for the persistent image, determining whether the new data is identical to the old data of the persistent image, and if the data is identical, folding the new data of the file in the active file system into the old data of the persistent image.

12. The method of claim 11 wherein the step of determining further comprises the steps of:

traversing inode buffer trees for both the active file system and the persistent image; and

loading data blocks of the active file system and the persistent image into the memory.

13. A system configured to reduce duplicate data of a file stored on a storage device of a storage system having an active file system, the system comprising:

a processor coupled to the storage device;

a memory coupled to the processor and having locations addressable by the processor; and

a storage operating system resident in the memory locations and executed by the processor to invoke storage operations in support of the file system, the storage operating system adapted to (i) generate a persistent image of old data for the file in the active file system, (ii) overwrite the old data of the file in the active file system with new data, and (iii) comparing contents of the data blocks for the active file system and persistent image on a block-by-block basis, (iv) determine whether the new data is identical to the old data of the persistent image, the operating system further folding the new data of the file in the active file system into the old data of the persistent image if the new and old data are identical.

14. The system of claim 13 wherein the storage system is a filer and wherein the storage device is a disk.

15. The system of claim 13 wherein the persistent image is a point-in-time representation of the storage system.

16. The system of claim 13 wherein the persistent image is a point-in-time representation of the active file system stored on the storage device or in other persistent memory and having a name or other identifier that distinguishes it from other persistent images taken at other points in time.

17. The system of claim 16 wherein the storage device is a disk.

18. Apparatus for reducing duplicate data of a file stored on a storage device of a server having an active file system, the apparatus comprising:

means for generating a persistent image of old data for the file in the active file system;

means for overwriting the old data of the file in the active file system with new, data;

means for comparing contents of the data blocks for the active file system and persistent image on a block-by-block basis

means for determining whether the new data is identical to the old data of the persistent image; and

if so, means for folding the new data of the file in the active file system into the old data of the persistent image.

19. A computer readable medium containing executable program instructions for reducing duplicate data of a file stored on a storage device of a server having an active file system, the executable program instructions comprising program instructions for:

generating a persistent image of old data for the file in the active file system;

overwriting the old data of the file in the active file system with new data;

comparing contents of the data blocks for the active file system and persistent image on a block-by-block basis

determining whether the new data is identical to the old data of the persistent image; and

if so, folding the new data of the file in the active file system into the old data of the persistent image.

20. A method for reducing duplicate data of a file stored on a storage device of a storage system having an active file system, the method comprising the steps of:

generating a persistent image of a file in the active file system;

comparing new data of the file written to the active file system to the data in the persistent image;

if the new data is identical to the data in the persistent image, directing the active file system to refer to the persistent image for data of the file, thereby reducing reference to duplicate data in the active file system;

otherwise, directing the active file system to refer to new data blocks in the active to file system.

21. The method of claim 20 wherein the step of comparing comprises the steps of:

obtaining a full pathname of the file in the active file system;

constructing a corresponding filename to the file in the persistent image;

loading inodes of the active file system and persistent image files into a memory.

22. The method of claim 20 wherein the step of comparing further comprises the steps of:

traversing inode buffer trees for both the active file system and the persistent image; and

loading indirect blocks of the active file system and the persistent image into the memory.

23. The method of claim 22 wherein the step of comparing further comprises the steps of:

comparing a virtual block number (VBN) of each indirect block from the active file system with a VBN of a corresponding indirect block from the persistent image;

determining whether the VBNs are equal;

if the VBNs are equal, aborting further processing of the indirect blocks;

if the VBNs are not equal, loading data blocks for the active file system and the persistent image into the memory.

24. The method of claim 20 further comprising the step of:

if the new data is identical to the data in the persistent image, freeing the data block of the file in the active file system.

25. The method of claim 24 wherein the step of freeing comprises the step of:

updating a corresponding bit of an active map of the active file system to indicate that the block is not allocated.

26. The method of claim 24 wherein the step of freeing further comprises the step of:

allocating a VBN of the data block in the persistent image.

27. The method of claim 26 wherein the step of allocating further comprises the step of:

updating a bit of an active map corresponding to the data block in the persistent image to indicate that the block is being used.

28. The method of claim 26 wherein the step of allocating further comprises the step of:

updating a block pointer of an inode of the file in the active file system to reference the VBN of the data block in the persistent image.

29. The method of claim 28 further comprising the step of:

marking the inode as dirty to ensure that it is written to the storage device.

30. A system configured to reduce duplicate data of a file stored on a storage device of a storage system having an active file system, the system comprising:

a processor coupled to the storage device;

a memory coupled to the processor and having locations addressable by the processor; and

a storage operating system resident in the memory locations and executed by the processor to invoke storage operations in support of the file system, the storage operating system adapted to (i) generate a persistent image of a file in the active file system, (ii) compare new data of the file written to the active file system to data in the persistent image, (iii) if the new data is identical to the data in the persistent image, direct the active file system to refer to the persistent image for the data of the file, thereby reducing reference to duplicate data in the active file system;

(iv) otherwise, direct the active file system to refer to new data blocks in the active file system.

31. Apparatus for reducing duplicate data of a file stored on a storage device of a storage system having an active file system, the apparatus comprising:

means for generating a persistent image of a file in the active file system;

means for comparing new data of the file written to the active file system to data in the persistent image;

means for directing the active file system to refer to the persistent image for the data of the file if the new data is identical to the data in the persistent image, thereby reducing reference to duplicate data in the active file system;

means for directing the active file system to refer to new data blocks in the active file system if the new data is not identical to the data in the persistent image.

32. A computer readable medium containing executable program instructions comprising:

executable program instructions for execution on a processor, the instructions adapted to (i) generate a persistent image of a file in the active file system, (ii) compare new data of the file written to the active file system to data in the persistent image, (iii) if the new data is identical to the data in the persistent image, direct the active file system to refer to the persistent image for the data of the file, thereby reducing reference to duplicate data in the active file system;

(iv) otherwise, direct the active file system to refer to new data blocks in the active file system.