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

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.

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.