Systems and methods for reading objects in a file system

• US 20090055399A1
• Filed: 08/21/2007
• Published: 02/26/2009
• Est. Priority Date: 08/21/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Passey, Aaron J., Lu, Qichu, Kirsch, Nicholas Montgomery
• Granted Patent: US 7,966,289 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files

Abstract

Embodiments of the disclosure relate generally to file systems. Specifically, certain embodiments include systems and methods for reading objects in a file system. In some embodiments, a first processing thread traverses a portion of a file system and represents file system objects in a data structure. A portion of the data and/or metadata associated with the represented objects may be prefetched to a memory. In some embodiments, a second processing thread consumes the objects represented in the queue. For example, in a file system backup embodiment, the second processing thread may transfer data and/or metadata associated with the objects to an archive target.

Claims

1. A method of traversing objects in a file system, comprising:

traversing a portion of the file system to identify an object to be read and to determine a size representative of the object;

determining whether to represent the object in a data structure based at least in part on one or more factors including the size representative of the object and a cumulative size of objects currently represented in the data structure; and

prefetching at least a portion of the objects currently represented in the data structure.

2. The method of claim 1, wherein the file system comprises a distributed file system.

3. The method of claim 1, wherein the objects comprise directories and files.

4. The method of claim 1, wherein the portion of the file system comprises a directory.

5. The method of claim 1, wherein traversing a portion of the file system comprises performing a depth-first traversal of a logical representation of the portion of the file system.

6. The method of claim 1, wherein the size representative of the file comprises a numerical count.

7. The method of claim 1, wherein the size representative of the file comprises an approximate amount of space allocated to the object.

8. The method of claim 7, wherein the approximate amount of space comprises an approximate space associated with data for the object.

9. The method of claim 8, wherein the approximate amount of space further comprises approximate space associated with metadata for the object.

10. The method of claim 1, wherein the cumulative size of objects comprises an approximate cumulative size of data associated with the objects.

11. The method of claim 10, wherein the cumulative size of objects further comprises a cumulative size of metadata associated with the objects.

12. The method of claim 1, wherein the cumulative size of objects comprises an approximate numerical count of the objects.

13. The method of claim 1, wherein the data structure comprises a queue.

14. The method of claim 1, wherein determining whether to represent the object in a data structure comprises comparing the cumulative size of the objects to a threshold.

15. The method of claim 14, wherein the threshold is adjustable.

16. The method of claim 14, wherein the threshold is dynamically adjustable.

17. The method of claim 1, wherein prefetching at least a portion of the objects comprises prefetching metadata associated with the objects.

18. The method of claim 1, wherein prefetching at least a portion of the objects comprises prefetching at least a portion of data associated with each of the objects.

19. The method of claim 18, wherein the prefetched portion of data comprises data at the beginning of the objects.

20. The method of claim 1, further comprising:

transferring the prefetched portion of the objects currently represented in the data structure to a memory.

21. The method of claim 20, wherein the memory comprises a cache.

22. The method of claim 20, further comprising:

updating the cumulative size of the objects currently represented in the data structure, the updating based at least in part on a size of objects transferred to the memory.

23. The method of claim 20, further comprising:

stopping the traversing if the cumulative size of objects currently represented in the data structure is greater than or equal to a first threshold.

24. The method of claim 23, further comprising:

restarting the traversing if the cumulative size or the updated cumulative size of objects currently represented in the data structure is less than or equal to a second threshold.

25. The method of claim 20, further comprising:

dropping at least some of the prefetched portion of the objects from the memory in response to a condition.

26. The method of claim 25, wherein the condition comprises successful transfer to an archive of a representation of at least some of the prefetched portion.

27. The method of claim 25, wherein the condition comprises use of at least some of the prefetched portion in a computer-implemented process.

28. The method of claim 1, further comprising:

using the prefetched portion of the objects currently represented in the data structure in a computer-implemented process.

29. The method of claim 28, wherein using comprises indexing the prefetched portion of the objects.

30. The method of claim 28, wherein using comprises searching the prefetched portion of the objects.

31. The method of claim 28, wherein using comprises calculating a hash based at least in part on the prefetched portion of the objects.

32. A computer-readable medium having stored thereon executable instructions that, when executed by a processor, cause the processor to perform a method for traversing objects in a file system, the method comprising:

traversing a portion of the file system to identify an object to be read and to determine a size representative of the object;

determining whether to represent the object in a data structure based at least in part on one or more factors including the size representative of the object and a cumulative size of objects currently represented in the data structure; and

prefetching at least a portion of the objects currently represented in the data structure.

33. A system for managing reading of a portion of a file system, the system comprising:

a storage device capable of accessing a file system;

a memory operably coupled to the storage device; and

a processing module operably coupled to the memory and the storage device, the processing module comprising a prefetch module, a working module, and a data structure capable of representing files in the file system,

wherein the prefetch module is configured to traverse data related to a portion of the file system and to represent a file in the data structure based at least in part on a size of the file and a cumulative size of files currently represented in the data structure, the prefetch module further configured to open the file and to prefetch at least a portion of the file; and

wherein the working module is configured to read the files represented in the data structure so as to transfer the files from the storage device to the memory.

34. The system of claim 33, wherein the file system comprises a distributed file system.

35. The system of claim 34, wherein the storage device comprises a node of the distributed file system.

36. The system of claim 33, wherein the memory comprises a cache.

37. The system of claim 33, wherein the data structure comprises a queue.

38. The system of claim 33, wherein the portion of the file system comprises a directory.

39. The system of claim 33, wherein the cumulative size of the files represented in the data structure comprises a numerical count of the represented files.

40. The system of claim 33, wherein the cumulative size of the files represented in the data structure comprises approximate cumulative space on the storage device that is associated with the files.

41. The system of claim 40, wherein the approximate cumulative space comprises approximate cumulative space of the files represented in the data structure that has not been transferred to the memory by the working module.

42. The system of claim 33, wherein the portion prefetched by the prefetch module comprises metadata associated with the file.

43. The system of claim 33, wherein the portion prefetched by the prefetch module comprises data associated with the file.

44. The system of claim 43, wherein the data comprises data at the beginning of the file.

45. The system of claim 33, wherein the prefetch module is further configured such that the traversed portion of the file system is selected to be sufficient for the cumulative size of files represented in the data structure to change by at least a predetermined amount.

46. The system of claim 33, wherein the working module is further configured to update the cumulative size of files represented in the data structure based at least in part on the size of the files transferred to the memory.