PARALLEL FILE SYSTEM PROCESSING

• US 20110196899A1
• Filed: 02/11/2010
• Published: 08/11/2011
• Est. Priority Date: 02/11/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Hughes, Jeffrey Douglas, Smith, Sean MacQueen, Lemar, Eric Michael, Petersen, Kalen Albert
• Granted Patent: US 9,058,334 B2
• Time in Patent Office: Days
• US Class Current: 707/809
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06

Abstract

A treewalk for splitting a file directory is disclosed for parallel execution of work items over a filesystem. The given work item is assigned to a worker. Thereafter, a request is sent to split the file directory to share a portion of the file directory with another worker. The worker examines the file directory for a next splittable directory entry key after a current in-progress location within a key space for the file directory. If no key is detected, the file directory is identified as unsplittable. If an entry is detected, the key space is progressively searched for a next entry between a next available directory entry key and an upper boundary. The worker identifies the file directory as splittable if the next available entry is found, providing a range of entries within the file directory for which parallel execution of the work item.

Claims

1. A network device, comprising:

a transceiver to send and receive data over a network; and

a processor configured to include at least one worker thereon that is operative to perform actions, comprising;

receiving a work item to be performed on entries within a file directory;

performing the work item on at least one of the entries within the file directory, progress of performance of the work item being indicated by a pointer location within a key space for the file directory; and

in response to receiving a request to split the file directory, performing actions, including;

indicating that the file directory is splittable, if a directory entry is located within a neighborhood of the pointer location and if a directory entry is located within a neighborhood of a midpoint within the key space; and

or

indicating that the file directory is unsplittable, if the directory entry is unlocatable within the neighborhood of the midpoint and the midpoint is located before the location of the pointer.

2. The network device of claim 1, wherein if the file directory is splittable, providing a location of the midpoint and an upper boundary within the key space as a range of entries within the file directory that is splittable to another worker.

3. The network device of claim 1, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the pointer location, searching for a subdirectory entry after the pointer location;

if the subdirectory entry is located after the pointer location, employing the located subdirectory to determine another pointer location within the subdirectory; and

if the subdirectory entry is unlocatable after the pointer location, indicating that the file directory is unsplittable.

4. The network device of claim 1, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the midpoint, then;

if the midpoint is before the pointer location within the key space, indicating that the file directory is unsplittable; and

if the midpoint is after the pointer location within the key space, then;

setting an upper boundary for the file directory within the key space as the midpoint;

determining a new midpoint based on the setting of the upper boundary; and

indicating the splittability of the file directory using the new midpoint.

5. The network device of claim 1, wherein the worker is configured to checkpoint progress in the file directory at least by writing out information about the pointer location to a shared recovery directory.

6. The network device of claim 1, wherein coordination of the worker and another worker is performed by a coordinator operating on the network device or another network device, the coordinator employing queues to track a state of the worker and the other worker.

7. A system of managing changes to entries within a file directory, comprising:

a coordinator operating within a processor, that performs actions, including assigning a work item to be performed over entries within the file directory; and

a first worker operating within the processor or another processor and performing actions, including;

receiving the assigned work item;

performing the work item on at least one of the entries within the file directory, progress of performance of the work item being indicated by a pointer location within a key space for the file directory; and

in response to receiving a request to split the file directory, performing actions, including;

indicating that the file directory is splittable, if a directory entry is located within a neighborhood of the pointer location and if a directory entry is located within a neighborhood of a midpoint within the key space;

or

indicating that the file directory is unsplittable, if the directory entry is unlocatable within the neighborhood of the midpoint and the midpoint is located before the location of the pointer.

8. The system of claim 7, wherein the coordinator performs actions, further comprising:

determining a number of available workers within an idle queue of workers, wherein a second worker is included within the idle queue;

selecting the first worker from a splittable queue of workers, if within a defined time period a split request is nonexistent for the first worker;

sending the request to the selected first worker to split the file directory to share at least a portion of the file directory with a second worker;

receiving from the selected first worker that the file directory is splittable and a range of the file directory to be sent to the second worker; and

providing to the second worker the range of the file directory that is split from the selected first worker.

9. The system of claim 7, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the pointer location, searching for a subdirectory entry after the pointer location;

if the subdirectory entry is located after the pointer location, then employing the located subdirectory for determining another pointer location within the subdirectory; and

if the subdirectory entry is unlocatable after the pointer location, indicating that the file directory is unsplittable.

10. The system of claim 7, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the midpoint, then;

if the midpoint is before the pointer location within the key space, indicating that the file directory is unsplittable; and

if the midpoint is after the pointer location within the key space, then;

setting an upper boundary for the file directory within the key space as the midpoint;

determining a new midpoint based on the setting of the upper boundary; and

indicating the splittability of the file directory using the new midpoint.

11. The system of claim 7, wherein the system comprises a plurality of network devices, each network device being configured to operate as a peer node within a cluster system to provide distributed storage for the file directory.

12. The system of claim 7, wherein the coordinator performs actions to distribute work items over a plurality of workers using state information about each worker in the plurality of workers.

13. The system of claim 7, wherein the coordinator performs actions, further comprising:

if the first worker is determined to have disconnected communications with the coordinator for at least a defined time, then moving at least one work item assigned to the disconnected first worker to a recovery queue; and

if assigning at least one work item to another worker, examining the recovery queue for at least one work item available to be assigned to the other worker.

14. A method for managing changes to entries within a file directory with a computing device that enables actions, comprising:

receiving a work item to be performed on entries within a file directory;

performing the work item on at least one of the entries within the file directory, progress of performance of the work item being indicated by a pointer location within a key space for the file directory; and

in response to receiving a request to split the file directory, performing actions, including;

if a directory entry is located within a neighborhood of the pointer location and if a directory entry is located within a neighborhood of a midpoint within the key space, indicating that the file directory is splittable; and

if the directory entry is unlocatable within the neighborhood of the midpoint and the midpoint is located before the location of the pointer, indicating that the file directory is unsplittable.

15. The method of claim 14, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the pointer location, searching for a subdirectory entry after the pointer location;

if the subdirectory entry is located after the pointer location, then employing the located subdirectory for determining another pointer location within the subdirectory; and

if the subdirectory entry is unlocatable after the pointer location, indicating that the file directory is unsplittable.

16. The method of claim 14, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the midpoint, then;

if the midpoint is before the pointer location, indicating that the file directory is unsplittable; and

if the midpoint is after the pointer location within the key space, then;

setting an upper boundary for the file directory within the key space as the midpoint;

determining a new midpoint based on the setting of the upper boundary; and

indicating the splittability of the file directory using the new midpoint.

17. The method of claim 14, wherein the actions further comprising:

requesting a split request to be received such that a worker is moved higher in priority within a splittable queue of workers than another worker within the splittable queue.

18. The method of claim 14, wherein if the file directory is splittable, enabling a coordinator operating on at least one of the computing device and another computing device performs actions to send another work item including a range of directory entries to a worker on at least one of the computing device and the other computing device.

19. The method of claim 14, wherein receiving a request to split the file directory is based on sending a request for a split based in part on at least one of a type and a size of content within the file directory.

20. The method of claim 14, wherein receiving the work item to be performed further comprises receiving the work item by a worker within an idle queue, and the worker receives the request to split the file directory while in a splittable queue, wherein the idle queue and splittable queue are managed by a coordinator operating on at least one of the computing device and another computing device.

21. The method of claim 14, further comprising a coordinator that enables actions to distribute work items over a plurality of workers using state information about each worker in the plurality of workers.

22. The method of claim 14, further comprising a coordinator that enables actions, comprising:

if a first worker is determined to have disconnected communications with the coordinator for at least a defined time, then moving at least one work item assigned to the disconnected first worker to a recovery queue; and

if assigning at least one work item to a second worker, examining the recovery queue for at least one work item available to be assigned to the second worker.

23. A processor-readable storage medium that includes data, wherein the execution of the data on a computing device enable actions, comprising:

receiving a work item to be performed on entries within a file directory;

performing the work item on at least one of the entries within the file directory, progress of performance of the work item being indicated by a pointer location within a key space for the file directory; and

in response to receiving a request to split the file directory, performing actions, including;

if a directory entry is located within a neighborhood of the pointer location and if a directory entry is located within a neighborhood of a midpoint within the key space, indicating that the file directory is splittable; and

if the directory entry is unlocatable within the neighborhood of the midpoint and the midpoint is located before the location of the pointer, indicating that the file directory is unsplittable.

24. The processor-readable storage medium of claim 23, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the pointer location, searching for a subdirectory entry after the pointer location;

if the subdirectory entry is located after the pointer location, then employing the located subdirectory for determining another pointer location within the subdirectory; and

if the subdirectory entry is unlocatable after the pointer location, indicating that the file directory is unsplittable.

25. The processor-readable storage medium of claim 23, wherein determining if the file directory is splittable further comprises:

if the directory entry is unlocatable within the neighborhood of the midpoint, then;

if the midpoint is before the pointer location, indicating that the file directory is unsplittable; and

if the midpoint is after the pointer location within the key space, then;

setting an upper boundary for the file directory within the key space as the midpoint;

determining a new midpoint based on the setting of the upper boundary; and

indicating the splittability of the file directory using the new midpoint.

26. The processor-readable storage medium of claim 23, wherein if the file directory is splittable, a coordinator operating on at least one of the computing device and another computing device performs actions to send another work item including a range of directory entries to a worker on at least one of the computing device and the other computing device.

27. The processor-readable storage medium of claim 23, wherein receiving a request to split the file directory is based on sending a request for a split based in part on at least one of a type and a size of content within the file directory.

28. The processor-readable storage medium of claim 23, wherein the actions further comprising:

requesting a split request to be received such that a worker is moved higher in priority within a splittable queue of workers than another worker within the splittable queue.

29. The processor-readable storage medium of claim 23, wherein receiving the work item to be performed further comprises receiving the work item by a worker within an idle queue, and the worker receives the request to split the file directory while in a splittable queue, wherein the idle queue and splittable queue are managed by a coordinator operating on at least one of the computing device and another computing device.