Process for fast file system crawling to support incremental file system differencing

• US 8,078,653 B1
• Filed: 10/07/2008
• Issued: 12/13/2011
• Est. Priority Date: 10/07/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Bisson, Timothy C., Pasupathy, Shankar, Patel, Yuvraj
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Weinrich, Brian E
• Application Number:
  US12/247,174
• Time in Patent Office: 1,162 Days
• Field of Search: 707/829, 707/641
• US Class Current: 707/829
• CPC Class Codes: G06F 16/164 File meta data generation
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A network storage server implements a method to perform fast crawling of a hierarchical storage structure. The hierarchical storage structure contains data entities stored by a network storage server. The hierarchical storage structure can be recursively divided into a plurality of sections. A plurality of parallel-processing threads can be used to process the plurality of sections. Each thread selects and processes one of the plurality of sections at a time to generate a sorted list of metadata corresponding to the section of the hierarchical storage structure. The sorted lists generated by the plurality of threads are merged to a baseline list. The baseline list contains sorted metadata for entities managed by the hierarchical storage structure. The baseline list can then be outputted as a representation of the state of data stored by the network storage server.

Claims

1. A method of crawling a hierarchical storage structure of a data storage system, the method comprising:

recursively dividing the hierarchical storage structure into a plurality of sections, wherein the hierarchical storage structure contains data entities stored by the storage system;

maintaining a queue in the data storage system, the queue containing leads for the plurality of sections to be crawled for metadata;

associating each of the leads with one of a plurality of threads associated with a parallel-processing architecture of the data storage system;

parallel-processing the plurality of sections utilizing the plurality of threads to generate a plurality of sorted lists of metadata, wherein each of the plurality of sorted lists corresponds to a different one of the plurality of sections of the hierarchical storage structure, said parallel-processing the plurality of sections including;

identifying, by each thread, metadata associated with data entities contained in a section associated with the thread;

appending, by the thread, the metadata of each of the data entities as a metadata entry to a metadata list corresponding to the associated section, the metadata list stored in a memory buffer associated with the thread; and

sorting, by the thread, the metadata entries within the metadata list of the associated section based on a unique identifier associated with the metadata entry;

merging, by the threads associated with each of the plurality of sections, corresponding sorted lists of metadata to form a baseline list, wherein the baseline list contains sorted metadata for the data entities of the hierarchical storage structure; and

outputting a representation of the baseline list, as a result of the crawling, to indicate a state of the data entities stored by the storage system.

2. The method as recited in claim 1, further comprising:

generating a list of changes to the hierarchical storage structure by comparing the baseline list with a previous baseline list of the hierarchical storage structure, wherein the list of changes contains data entities of the hierarchical storage structure that have been updated between the baseline list and the previous baseline list.

3. The method as recited in claim 1, wherein the hierarchical storage structure is a file system, and the data entities contained in the hierarchical storage structure are files or directories of the file system.

4. The method as recited in claim 3, wherein the sorted metadata for the files contains inode numbers, full path names, and modification times.

5. The method as recited in claim 3, wherein said recursively dividing of the file system comprises recursively discovering subdirectories in the file system and dividing the file system based on the discovered subdirectories.

6. The method as recited in claim 5, wherein said recursively dividing of the file system further comprises recursively discovering additional subdirectories in the subdirectories and dividing the file system based on the discovered additional subdirectories.

7. The method as recited in claim 5, wherein said recursively dividing of the file system further comprises adding leads for the discovered additional subdirectories to a global queue, and the leads are accessed by a plurality of threads for further recursively dividing of the file system.

8. The method as recited in claim 1, further comprising:

instantiating a plurality of parallel-processing threads for the parallel-processing of the plurality of sections.

9. The method as recited in claim 8, wherein the merging of the sorted lists of metadata is performed by the plurality of parallel-processing threads.

10. The method as recited in claim 8, wherein the number of the plurality of parallel-processing threads is determined according to a memory size of a processing system divided by a memory buffer size used by each of the plurality of parallel-processing threads.

11. The method as recited in claim 1, wherein the method is embodied in a machine-readable storage medium as a set of instructions which, when executed by a processor, cause the processor to perform the method.

12. A method of crawling a network file system of a network storage server, the method comprising:

maintaining a queue in the network file system, wherein the network file system manages entities stored in the network storage server, and the queue contains leads for a plurality of sections of the network file system to be crawled for metadata;

associating each lead with one of a plurality of threads associated with a parallel-processing architecture of the network storage server;

processing the leads with a plurality of parallel-processing threads, wherein each of the plurality of threads selects one section from the plurality of sections at a time for processing;

selecting each lead from the queue, and for each lead;

assigning the lead to be processed by one of the threads of the plurality of the threads,

scanning, by the assigned thread, a section identified by the lead for entities contained in the section;

storing, by the assigned thread, metadata for each of the entities contained in the section to a memory buffer;

upon the memory buffer being full, sorting, by the assigned thread, metadata stored in the memory buffer and saving the sorted metadata to a sorted list, wherein the sorting is based on a unique identifier associated with the metadata; and

merging, by the threads associated with each of the leads, corresponding saved sorted lists to a baseline list, wherein the baseline list contains metadata for all entities of the network file system.

13. The method as recited in claim 12, further comprising:

recursively dividing entities managed by the network file system into the plurality of sections, wherein each of the plurality of sections is further recursively divided into a plurality of sub-sections, and leads for the plurality of sub-sections can be added to the queue.

14. The method as recited in claim 12, further comprising:

generating a list of updated entities in the network file system by detecting updates between the baseline list and a previously generated baseline list of the network file system.

15. The method as recited in claim 14, further comprising:

upon detecting an entry in the baseline list with multiple hard links, using full path of the entry to detect updates.

16. The method as recited in claim 12, wherein said selecting a lead from the queue further comprises:

obtaining a lock to the queue;

choosing a first lead as the selected lead from the queue;

removing the first lead from the queue; and

releasing the lock to the queue.

17. The method as recited in claim 12, wherein a plurality of threads parallel-performs the method.

18. The method as recited in claim 12, wherein said merging of the saved sorted lists is parallel-processed by a plurality of threads.

19. The method as recited in claim 12, wherein the method is embodied in a machine-readable medium as a set of instructions which, when executed by a processor, cause the processor to perform the method.

20. A system comprising:

a processor;

a network interface through which to communicate with a network file system; and

a memory coupled with the processor, the memory storing instructions which, when executed by the processor, cause the system to perform a process comprising;

recursively dividing data in the network file system into a plurality of sections, wherein the network file system contains data stored in a network storage server;

maintaining a queue in the data storage system, the queue containing leads for the plurality of sections to be crawled for metadata;

processing the leads with a plurality of parallel-processing threads, wherein each of the plurality of threads selects one section from the plurality of sections at a time for processing, said processing the plurality of sections including;

identifying, by a thread assigned to a particular section, metadata associated with data entities contained in the particular section;

appending, by the thread, the metadata of each of the data entities as a metadata entry to a metadata list corresponding to the particular section, the metadata list stored in a memory buffer associated with the thread; and

sorting, by the thread, the metadata entries within the metadata list of the particular section based on a unique identifier associated with the metadata entry; and

merging, by the threads associated with each of the plurality of sections, corresponding sorted lists of metadata generated by the plurality of threads to a baseline list, wherein the baseline list contains sorted metadata for the data in the network file system.

21. The system as recited in claim 20, wherein the process further comprising:

generating a list of changes to the network file system by comparing the baseline list with a previous baseline list of the network file system, wherein the list of changes contains entities in the network file system that have been updated since the previous baseline list was generated; and

indexing updated entities identified by the list of changes in the network file system.

22. The system as recited in claim 20, wherein said merging of the sorted lists is parallel-processed by the plurality of threads.