US20170123848A1

US20170123848A1 - Multi-task processing in a distributed storage network

Info

Publication number: US20170123848A1
Application number: US15/334,848
Authority: US
Inventors: Franco V. Borich; Bart R. Cilfone; Greg R. Dhuse; Adam M. Gray; Scott M. Horan; Ravi V. Khadiwala; Mingyu Li; Tyler K. Reid; Jason K. Resch; Daniel J. Scholl; Rohan P. Shah; Ilya Volvovski
Original assignee: International Business Machines Corp
Current assignee: Pure Storage Inc
Priority date: 2015-10-30
Filing date: 2016-10-26
Publication date: 2017-05-04
Also published as: US20170123976A1; US10656998B2; US20190065312A1; US10176044B2; US20190026183A1; US10430277B2; US10467095B2; US10133631B2; US20170123907A1; US20190050290A1; US20170126804A1; US20170126805A1; US20170123916A1; US10169147B2; US9959169B2; US20170123948A1; US20170123922A1; US10599519B2; US10365968B2; US20170123911A1

Abstract

A method includes temporarily storing, by a computing device tasks in a task queue to produce queued tasks. The method further includes identifying a task of the queued tasks for execution. The method further includes partitioning the task into a plurality of partial tasks. The method further includes sending partial task execution requests to at least some of the set of storage units. The method further includes transferring the task from the task queue to a task in process index and establishing an expiration time. When a partial task of the plurality of partial tasks has not been completed prior to the expiration time, the method further includes transferring the task from the task in process index to the task queue indicating that the task was not completed prior to the expiration time and re-queuing execution of at least a portion of the task.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

The present U.S. Utility Patent Application claims priority pursuant to 35 U.S.C. §119(e) to U.S. Provisional Application No. 62/248,636, entitled “SECURELY STORING DATA IN A DISPERSED STORAGE NETWORK”, filed Oct. 30, 2015, which is hereby incorporated herein by reference in its entirety and made part of the present U.S. Utility Patent Application for all purposes.

STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

Not Applicable.

INCORPORATION-BY-REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC

Not Applicable.

BACKGROUND OF THE INVENTION

Technical Field of the Invention
This invention relates generally to computer networks and more particularly to dispersing error encoded data.
Description of Related Art
Computing devices are known to communicate data, process data, and/or store data. Such computing devices range from wireless smart phones, laptops, tablets, personal computers (PC), work stations, and video game devices, to data centers that support millions of web searches, stock trades, or on-line purchases every day. In general, a computing device includes a central processing unit (CPU), a memory system, user input/output interfaces, peripheral device interfaces, and an interconnecting bus structure.
As is further known, a computer may effectively extend its CPU by using “cloud computing” to perform one or more computing functions (e.g., a service, an application, an algorithm, an arithmetic logic function, etc.) on behalf of the computer. Further, for large services, applications, and/or functions, cloud computing may be performed by multiple cloud computing resources in a distributed manner to improve the response time for completion of the service, application, and/or function. For example, Hadoop is an open source software framework that supports distributed applications enabling application execution by thousands of computers.
In addition to cloud computing, a computer may use “cloud storage” as part of its memory system. As is known, cloud storage enables a user, via its computer, to store files, applications, etc. on an Internet storage system. The Internet storage system may include a RAID (redundant array of independent disks) system and/or a dispersed storage system that uses an error correction scheme to encode data for storage.
Still further, a cloud computing system may be integrated with cloud storage. In this manner, data stored in the cloud storage is processed by the cloud computing system. This allows for high-speed multi-parallel processing of tasks on data, which requires a higher level of management to coordinate such processing.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S)

FIG. 1 is a schematic block diagram of an embodiment of a dispersed or distributed storage network (DSN) in accordance with the present invention;

FIG. 2 is a schematic block diagram of an embodiment of a computing core in accordance with the present invention;

FIG. 3 is a schematic block diagram of an example of dispersed storage error encoding of data in accordance with the present invention;

FIG. 4 is a schematic block diagram of a generic example of an error encoding function in accordance with the present invention;

FIG. 5 is a schematic block diagram of a specific example of an error encoding function in accordance with the present invention;

FIG. 6 is a schematic block diagram of an example of a slice name of an encoded data slice (EDS) in accordance with the present invention;

FIG. 7 is a schematic block diagram of an example of dispersed storage error decoding of data in accordance with the present invention;

FIG. 8 is a schematic block diagram of a generic example of an error decoding function in accordance with the present invention;

FIG. 9 is a schematic block diagram of an embodiment of DSN supporting multi-task processing in accordance with the present invention;

FIG. 10 is a schematic block diagram of another embodiment of DSN supporting multi-task processing in accordance with the present invention;

FIG. 11 is a logic diagram of an example of a method for coordinating multi-task processing in a DSN in accordance with the present invention;

FIG. 12 is a schematic block diagram of another embodiment of DSN supporting multi-task processing in accordance with the present invention;

FIG. 13 is a schematic block diagram of an example of a hierarchical coordination of multi-task processing in accordance with the present invention;

FIG. 14 is a schematic block diagram of another example of a hierarchical coordination of multi-task processing in accordance with the present invention;

FIG. 15 is a schematic block diagram of an example of a partial task index node structure in accordance with the present invention;

FIGS. 16-20 are schematic block diagrams of another example of a hierarchical coordination of multi-task processing in accordance with the present invention;

FIG. 21 is a logic diagram of another example of a method for coordinating multi-task processing in a DSN in accordance with the present invention; and

FIG. 22 is a logic diagram of an example of a method for coordinating multi-task processing in a DSN in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1 is a schematic block diagram of an embodiment of a dispersed, or distributed, storage network (DSN) 10 that includes a plurality of computing devices 12-16, a managing unit 18, an integrity processing unit 20, and a DSN memory 22. The components of the DSN 10 are coupled to a network 24, which may include one or more wireless and/or wire lined communication systems; one or more non-public intranet systems and/or public internet systems; and/or one or more local area networks (LAN) and/or wide area networks (WAN).
The DSN memory 22 includes a plurality of storage units 36 that may be located at geographically different sites (e.g., one in Chicago, one in Milwaukee, etc.), at a common site, or a combination thereof. For example, if the DSN memory 22 includes eight storage units 36, each storage unit is located at a different site. As another example, if the DSN memory 22 includes eight storage units 36, all eight storage units are located at the same site. As yet another example, if the DSN memory 22 includes eight storage units 36, a first pair of storage units are at a first common site, a second pair of storage units are at a second common site, a third pair of storage units are at a third common site, and a fourth pair of storage units are at a fourth common site. Note that a DSN memory 22 may include more or less than eight storage units 36. Further note that each storage unit 36 includes a computing core (as shown in FIG. 2, or components thereof) and a plurality of memory devices for storing dispersed error encoded data.
Each of the computing devices 12-16, the managing unit 18, and the integrity processing unit 20 include a computing core 26, which includes network interfaces 30-33. Computing devices 12-16 may each be a portable computing device and/or a fixed computing device. A portable computing device may be a social networking device, a gaming device, a cell phone, a smart phone, a digital assistant, a digital music player, a digital video player, a laptop computer, a handheld computer, a tablet, a video game controller, and/or any other portable device that includes a computing core. A fixed computing device may be a computer (PC), a computer server, a cable set-top box, a satellite receiver, a television set, a printer, a fax machine, home entertainment equipment, a video game console, and/or any type of home or office computing equipment. Note that each of the managing unit 18 and the integrity processing unit 20 may be separate computing devices, may be a common computing device, and/or may be integrated into one or more of the computing devices 12-16 and/or into one or more of the storage units 36.
Each interface 30, 32, and 33 includes software and hardware to support one or more communication links via the network 24 indirectly and/or directly. For example, interface 30 supports a communication link (e.g., wired, wireless, direct, via a LAN, via the network 24, etc.) between computing devices 14 and 16. As another example, interface 32 supports communication links (e.g., a wired connection, a wireless connection, a LAN connection, and/or any other type of connection to/from the network 24) between computing devices 12 and 16 and the DSN memory 22. As yet another example, interface 33 supports a communication link for each of the managing unit 18 and the integrity processing unit 20 to the network 24.
Computing devices 12 and 16 include a dispersed storage (DS) client module 34, which enables the computing device to dispersed storage error encode and decode data (e.g., data 40) as subsequently described with reference to one or more of FIGS. 3-8. In this example embodiment, computing device 16 functions as a dispersed storage processing agent for computing device 14. In this role, computing device 16 dispersed storage error encodes and decodes data on behalf of computing device 14. With the use of dispersed storage error encoding and decoding, the DSN 10 is tolerant of a significant number of storage unit failures (the number of failures is based on parameters of the dispersed storage error encoding function) without loss of data and without the need for a redundant or backup copies of the data. Further, the DSN 10 stores data for an indefinite period of time without data loss and in a secure manner (e.g., the system is very resistant to unauthorized attempts at accessing the data).
In operation, the managing unit 18 performs DS management services. For example, the managing unit 18 establishes distributed data storage parameters (e.g., vault creation, distributed storage parameters, security parameters, billing information, user profile information, etc.) for computing devices 12-14 individually or as part of a group of user devices. As a specific example, the managing unit 18 coordinates creation of a vault (e.g., a virtual memory block associated with a portion of an overall namespace of the DSN) within the DSN memory 22 for a user device, a group of devices, or for public access and establishes per vault dispersed storage (DS) error encoding parameters for a vault. The managing unit 18 facilitates storage of DS error encoding parameters for each vault by updating registry information of the DSN 10, where the registry information may be stored in the DSN memory 22, a computing device 12-16, the managing unit 18, and/or the integrity processing unit 20.
The managing unit 18 creates and stores user profile information (e.g., an access control list (ACL)) in local memory and/or within memory of the DSN memory 22. The user profile information includes authentication information, permissions, and/or the security parameters. The security parameters may include encryption/decryption scheme, one or more encryption keys, key generation scheme, and/or data encoding/decoding scheme.
The managing unit 18 creates billing information for a particular user, a user group, a vault access, public vault access, etc. For instance, the managing unit 18 tracks the number of times a user accesses a non-public vault and/or public vaults, which can be used to generate a per-access billing information. In another instance, the managing unit 18 tracks the amount of data stored and/or retrieved by a user device and/or a user group, which can be used to generate a per-data-amount billing information.
As another example, the managing unit 18 performs network operations, network administration, and/or network maintenance. Network operations includes authenticating user data allocation requests (e.g., read and/or write requests), managing creation of vaults, establishing authentication credentials for user devices, adding/deleting components (e.g., user devices, storage units, and/or computing devices with a DS client module 34) to/from the DSN 10, and/or establishing authentication credentials for the storage units 36. Network administration includes monitoring devices and/or units for failures, maintaining vault information, determining device and/or unit activation status, determining device and/or unit loading, and/or determining any other system level operation that affects the performance level of the DSN 10. Network maintenance includes facilitating replacing, upgrading, repairing, and/or expanding a device and/or unit of the DSN 10.
The integrity processing unit 20 performs rebuilding of ‘bad’ or missing encoded data slices. At a high level, the integrity processing unit 20 performs rebuilding by periodically attempting to retrieve/list encoded data slices, and/or slice names of the encoded data slices, from the DSN memory 22. For retrieved encoded slices, they are checked for errors due to data corruption, outdated version, etc. If a slice includes an error, it is flagged as a ‘bad’ slice. For encoded data slices that were not received and/or not listed, they are flagged as missing slices. Bad and/or missing slices are subsequently rebuilt using other retrieved encoded data slices that are deemed to be good slices to produce rebuilt slices. The rebuilt slices are stored in the DSN memory 22.
FIG. 2 is a schematic block diagram of an embodiment of a computing core 26 that includes a processing module 50, a memory controller 52, main memory 54, a video graphics processing unit 55, an input/output (IO) controller 56, a peripheral component interconnect (PCI) interface 58, an 10 interface module 60, at least one 10 device interface module 62, a read only memory (ROM) basic input output system (BIOS) 64, and one or more memory interface modules. The one or more memory interface module(s) includes one or more of a universal serial bus (USB) interface module 66, a host bus adapter (HBA) interface module 68, a network interface module 70, a flash interface module 72, a hard drive interface module 74, and a DSN interface module 76.
The DSN interface module 76 functions to mimic a conventional operating system (OS) file system interface (e.g., network file system (NFS), flash file system (FFS), disk file system (DFS), file transfer protocol (FTP), web-based distributed authoring and versioning (WebDAV), etc.) and/or a block memory interface (e.g., small computer system interface (SCSI), internet small computer system interface (iSCSI), etc.). The DSN interface module 76 and/or the network interface module 70 may function as one or more of the interface 30-33 of FIG. 1. Note that the IO device interface module 62 and/or the memory interface modules 66-76 may be collectively or individually referred to as IO ports.
FIG. 3 is a schematic block diagram of an example of dispersed storage error encoding of data. When a computing device 12 or 16 has data to store it disperse storage error encodes the data in accordance with a dispersed storage error encoding process based on dispersed storage error encoding parameters. The dispersed storage error encoding parameters include an encoding function (e.g., information dispersal algorithm, Reed-Solomon, Cauchy Reed-Solomon, systematic encoding, non-systematic encoding, on-line codes, etc.), a data segmenting protocol (e.g., data segment size, fixed, variable, etc.), and per data segment encoding values. The per data segment encoding values include a total, or pillar width, number (T) of encoded data slices per encoding of a data segment (i.e., in a set of encoded data slices); a decode threshold number (D) of encoded data slices of a set of encoded data slices that are needed to recover the data segment; a read threshold number (R) of encoded data slices to indicate a number of encoded data slices per set to be read from storage for decoding of the data segment; and/or a write threshold number (W) to indicate a number of encoded data slices per set that must be accurately stored before the encoded data segment is deemed to have been properly stored. The dispersed storage error encoding parameters may further include slicing information (e.g., the number of encoded data slices that will be created for each data segment) and/or slice security information (e.g., per encoded data slice encryption, compression, integrity checksum, etc.).
In the present example, Cauchy Reed-Solomon has been selected as the encoding function (a generic example is shown in FIG. 4 and a specific example is shown in FIG. 5); the data segmenting protocol is to divide the data object into fixed sized data segments; and the per data segment encoding values include: a pillar width of 5, a decode threshold of 3, a read threshold of 4, and a write threshold of 4. In accordance with the data segmenting protocol, the computing device 12 or 16 divides the data (e.g., a file (e.g., text, video, audio, etc.), a data object, or other data arrangement) into a plurality of fixed sized data segments (e.g., 1 through Y of a fixed size in range of Kilo-bytes to Tera-bytes or more). The number of data segments created is dependent of the size of the data and the data segmenting protocol.
The computing device 12 or 16 then disperse storage error encodes a data segment using the selected encoding function (e.g., Cauchy Reed-Solomon) to produce a set of encoded data slices. FIG. 4 illustrates a generic Cauchy Reed-Solomon encoding function, which includes an encoding matrix (EM), a data matrix (DM), and a coded matrix (CM). The size of the encoding matrix (EM) is dependent on the pillar width number (T) and the decode threshold number (D) of selected per data segment encoding values. To produce the data matrix (DM), the data segment is divided into a plurality of data blocks and the data blocks are arranged into D number of rows with Z data blocks per row. Note that Z is a function of the number of data blocks created from the data segment and the decode threshold number (D). The coded matrix is produced by matrix multiplying the data matrix by the encoding matrix.
FIG. 5 illustrates a specific example of Cauchy Reed-Solomon encoding with a pillar number (T) of five and decode threshold number of three. In this example, a first data segment is divided into twelve data blocks (D1-D12). The coded matrix includes five rows of coded data blocks, where the first row of X11-X14 corresponds to a first encoded data slice (EDS 1_1), the second row of X21-X24 corresponds to a second encoded data slice (EDS 2_1), the third row of X31-X34 corresponds to a third encoded data slice (EDS 3 1), the fourth row of X41-X44 corresponds to a fourth encoded data slice (EDS 4_1), and the fifth row of X51-X54 corresponds to a fifth encoded data slice (EDS 5_1). Note that the second number of the EDS designation corresponds to the data segment number.
Returning to the discussion of FIG. 3, the computing device also creates a slice name (SN) for each encoded data slice (EDS) in the set of encoded data slices. A typical format for a slice name 80 is shown in FIG. 6. As shown, the slice name (SN) 80 includes a pillar number of the encoded data slice (e.g., one of 1-T), a data segment number (e.g., one of 1-Y), a vault identifier (ID), a data object identifier (ID), and may further include revision level information of the encoded data slices. The slice name functions as, at least part of, a DSN address for the encoded data slice for storage and retrieval from the DSN memory 22.
As a result of encoding, the computing device 12 or 16 produces a plurality of sets of encoded data slices, which are provided with their respective slice names to the storage units for storage. As shown, the first set of encoded data slices includes EDS 1_1 through EDS 5_1 and the first set of slice names includes SN 1_1 through SN 5_1 and the last set of encoded data slices includes EDS 1_Y through EDS 5_Y and the last set of slice names includes SN 1_Y through SN 5_Y.
FIG. 7 is a schematic block diagram of an example of dispersed storage error decoding of a data object that was dispersed storage error encoded and stored in the example of FIG. 4. In this example, the computing device 12 or 16 retrieves from the storage units at least the decode threshold number of encoded data slices per data segment. As a specific example, the computing device retrieves a read threshold number of encoded data slices.
To recover a data segment from a decode threshold number of encoded data slices, the computing device uses a decoding function as shown in FIG. 8. As shown, the decoding function is essentially an inverse of the encoding function of FIG. 4. The coded matrix includes a decode threshold number of rows (e.g., three in this example) and the decoding matrix in an inversion of the encoding matrix that includes the corresponding rows of the coded matrix. For example, if the coded matrix includes rows 1, 2, and 4, the encoding matrix is reduced to rows 1, 2, and 4, and then inverted to produce the decoding matrix.
FIG. 9 illustrates steps of an example of operation of the processing of the tasks where a DST processing unit (e.g., a storage unit with a partial task execution unit) obtains a task from a task queue, where the task queue is implemented as a dispersed hierarchical network of index nodes stored as sets of task slices in the storage set 90. For instance, the task may include a plurality of subtasks to facilitate transfer of a data object stored in the DSN from one set of storage units to another set of storage units. The obtaining includes traversing a dispersed hierarchical index within the storage set to locate an index node that includes a next task entry, where each task entry includes one or more of a completion time index key, a task identifier (ID), and a task descriptor.
The obtaining includes one or more of identifying a completion time index key that is associated with an earliest time compared to a present time (e.g., least amount of time remaining for completion of the task), receiving task slices, and decoding the task slices to produce the next task entry. For example, DST processing unit 1 traverses the dispersed hierarchical network to locate the index node that includes the next task entry, receives, via the network 24, task slices A1-An, and decodes the received task slices A1-An to produce the index node that includes a task A next task entry. As another example, DST processing unit 2 traverses the dispersed hierarchical network to locate another index node that includes another next task entry, receives, via the network 24, task slices B1-Bn, and decodes the received task slices B1-Bn to produce the other index node that includes a task B next task entry. As yet another example, DST processing unit 3 traverses the dispersed hierarchical network to locate yet another index node that includes it another next task entry, receives, via the network 24, task slices C1-Cn, and decodes the received task slices C1-Cn to produce yet another index node that includes a task C next task entry.
Having obtained the task from the task queue, the DST processing unit initiates deletion of the task from the task queue. The initiating includes issuing delete task slice requests to the storage set and receiving delete task slice responses confirming deletion of slices associated with the task, when the index node of the dispersed article index includes one entry for the task to be deleted. For example, the DST processing unit 1 issues, via the network 24, delete task slices A1-An to the storage set, DST processing unit 2 issues, via the network 24, delete task slices B1-Bn to the storage set, and DST processing unit 3 issues, via the network 24, delete task slices C1-Cn to the storage set.
When the task has been successfully deleted from the task queue, the DST processing unit initiates execution of the task. The initiating includes one or more of receiving an indication of a favorable deletion of the task from the task queue (e.g., interpret received delete slice task responses to confirm favorable deletion including no conflict with another DST processing unit train to initiate execution of a common task) and beginning execution of one or more sub tasks associated with the task. For example, DST processing unit 1 initiates execution of task A, the DST processing unit 2 initiates execution of task B, and DST processing unit 3 initiates execution of task C.
Having initiated execution of the task (e.g., facilitating transfer of encoded data slices associated with storage of the data in the first set of storage units to the second set of storage units), the DST processing unit facilitates storage of a leased task entry in a leased task queue indicating that the DST processing unit has initiated execution of the task and that the other DST processing units need not attempt to initiate execution of the same task. The facilitating includes one or more of generating the leased task entry (e.g., including an expiration time index key, a task ID, the task descriptor, an identifier of the DST processing unit), encoding the leased task entry to produce lease slices, and sending the lease slices to the storage set for storage. For example, the DST processing unit 1 generates a leased task entry A, dispersed storage error encodes the leased task entry A to produce lease slices A1-An, and sends, via the network 24, the lease slices A1-An to the storage set for storage; the DST processing unit 2 generates a leased task entry B, dispersed storage error encodes the leased task entry B to produce lease slices B1-Bn, and sends, via the network 24, the lease slices B1-Bn to the storage set for storage; and the DST processing unit 3 generates a leased task entry C, dispersed storage error encodes the leased task entry C to produce lease slices C1-Cn, and sends, via the network 24, the lease slices C1-Cn to the storage set for storage.
FIG. 10 illustrates further steps of the example of operation of the processing of the tasks. When detecting that the task will not complete before the expiration time, the DST processing unit updates the leased task entry in the leased task queue. The updating includes one or more of modifying the expiration time (e.g., extend) to produce an updated leased task entry, re-encoding the updated leased task entry to produce updated lease slices, and sending the updated lease slices to the storage set 90 for storage. For example, the DST processing unit 1 detects that the task A will not complete before the expiration time (e.g., by determining that executed subtasks of the task A will take too long), modifies the leased task entry to extend the expiration time beyond an estimated time for completion (e.g., more time to execute the unexecuted subtasks), dispersed storage error encodes the updated leased task entry to produce updated lease slices A1-An, and sends, via the network 24, the updated lease slices A1-An to the storage set for storage.
When completing the task before the expiration time (e.g., detection of successful transfer of the data from the first set of storage units to the second set of storage units), the DST processing unit facilitates deletion of the leased task entry in the leased task queue. The deletion includes issuing delete lease slice messages to the storage set. For example, the DST processing unit 3 detects that the task C has completed before the expiration time, generates delete lease slice messages C1-Cn, and sends, via the network 24, the fleet lease slice messages C1-Cn to the storage set.
When the time has expired prior to completion of execution of the task, the restored task unit detects that the task was not completed before the expiration time. The detecting includes one or more of receiving lease slices, decoding the received lease slices to reproduce the leased task entry, comparing expiration time index key to a real time value, and indicating that the task is not completed before the expiration time when the comparison is unfavorable (e.g., the real time value is greater than the expiration time of the expiration time index key). For example, the restore task unit receives, via the network 24, lease slices B1-Bn from the storage set, dispersed storage error decodes the received lease slices B1-Bn, and indicates that the task B has not completed before the expiration time when the real time is greater than the expiration time of the expiration time index key (e.g., the DST processing unit 2 has failed thus impeding completion of the task B).
When the restore task unit detects that the task was not completed before the expiration time, the restore task unit re-generates the task entry associated with the help task based on the leased task entry. For example, the restored task unit re-generates the task entry B to include a new completion time index key, the task ID, and the task descriptor. Having re-generated the task entry, the restore task unit stores the regenerated task entry in the task queue (e.g., to facilitate subsequent re-initiation of the task to transfer the data from the first set of storage units the second set of storage units). For example, the restore task unit dispersed storage error encodes the regenerated task entry B to produce task slices B1-Bn and sends, via the network 24, the task slices B1-Bn to the storage set for storage. Having stored the regenerated task entry, the restore task unit deletes the leased task entry from the leased task queue. For example, the restored task unit issues, via the network 24, delete lease slices B1-Bn messages to the storage set.
FIG. 11 is a flowchart illustrating an example of processing tasks for execution. The method includes step 100 where a processing unit obtains a task from a task queue. For example, the processing unit traverses a dispersed hierarchical index within a set of storage units of a dispersed storage network (DSN) to locate a next task entry, identifies an index key associated with a soonest completion time, receives task slices from the set of storage units, and dispersed storage error decodes the received task slices to produce the next task entry. The method continues at step 102 where the processing unit initiates deletion of the task from the task queue. For example, the processing unit issues delete task slice requests to the set of storage units and receives delete task slice responses.
When the task has been deleted from the task queue without conflict, the processing unit initiates execution of the task at step 104. For example, the processing unit receives an indication of a favorable deletion of the task entry (e.g., interpret received delete task slice responses) and begins execution of one or more sub tasks associated with the task. The method continues at step 106 where the processing unit facilitates storage of a leased task entry in a leased task queue. For example, the processing unit generates the leased task entry (e.g., to include an expiration time index key, task identifier, test descriptor, an identifier of the processing unit executing the task), dispersed storage error encodes the lease task entry to produce lease slices, and sends the lease slices to the set of storage units for storage.
When detecting, by at least one of the processing unit and a restore task unit, that the task will not complete execution prior to an expiration time associated with the expiration time index key, the method branches where the restore task unit generates a task entry for the task queue. When detecting, by the at least one of the processing unit and the restore task unit, that the task will not complete before an expiration time, the method branches to step 108 where the at least one of the processing unit and the restore task unit updates the leased task entry in the leased task queue to extend the expiration time. For example, the processing unit updates the expiration time (e.g., to extend), re-encodes the updated lease task entry to produce updated lease slices, and sends the updated lease slices to the set of storage units for storage. When the processing unit completes the task before the expiration time, the method branches to step 110 where the processing unit deletes leased task entry in the lease task queue. For example, the processing unit issues delete lease slice messages to the set of storage units.
When detecting that the task is not completed before the expiration time, the restored task unit re-generates a task entry for the task queue at step 112. The detecting includes the restore task unit receiving the lease slices, dispersed storage error decoding the received lease slices to reproduce the leased task entry, comparing the expiration time index key to a real time value, and indicating that the task has not completed before the expiration time when the comparison is unfavorable (e.g., real time is greater than the expiration time). The generating includes the restore task unit generating a new completion time index key and generating the task entry to include the new completion time index key, the task ID, and the task descriptor.
The method continues at step 114 where the restore task unit stores the task entry in the task queue. For example, the restore task unit dispersed storage error encodes the regenerated task entry to produce task slices and sends the task slices to the set of storage units for storage. The method continues at step 116 where the restore task unit deletes the leased task entry from the least task queue. For example, the restore task unit issues delete lease slice messages to the set of storage units.
FIG. 12 is a schematic block diagram of another embodiment of DSN 10 supporting multi-task processing. In this embodiment, a computing device 12 or 16 is processing a task 120 on desired data 122 to produce a result 124. The task 120 includes one or more of a variety of functions. For example, a task is a simple function (e.g., a mathematical function, a logic function, an identify function, a find function, a search engine function, a replace function, etc.), a complex function (e.g., compression, human and/or computer language translation, text-to-voice conversion, voice-to-text conversion, etc.), multiple simple and/or complex functions, one or more algorithms, one or more applications, etc. As another example, the task includes DSN functions such as read, write, delete, list, rebuild, etc. The desired data 122 includes one or more data objects, or portions thereof, where a data object includes a video file, a text file, an audio file, an image, an email, a text message, personal profile, credit information, a graphics, etc. As a specific example, the desired data 122 is emails sent on a specific day, the task 120 is finding emails of the desired data 122 that reference a particular word or phrase (e.g., law suit, sue, lawyers, etc.) and the result 124 is the culmination of the emails meeting the search criteria of the task 120.
To process the task 120, the computing device partitions the task into a set of partial tasks 126, which are sent to the storage units of a set of storage units. In this example, the set of storage units includes five storage units. The computing device partitions the task into the set of partial tasks 126 knowing how the desired data is divided and stored in the storage units. For example, the desired data is dispersed storage error encoded into a plurality of sets of encoded data slices using an encoding matrix having a unity matrix component (e.g., with reference to FIG. 5, coefficients a-i of the encoding matrix form the unity matrix). As such, a first encoded data slice of a set of encoded data slices includes a first set of data elements (e.g., with reference to FIG. 5, data elements D1-D4 of a data segment), which is stored by a first storage unit. Accordingly, a first partial task will be sent to the first storage unit regarding a first set of data elements of the data segments of the data object.
Each of the storage units includes a DSN interface 132, memory 134, a memory controller 136, and a partial task execution unit 138. The DSN interface 132 is a network (e.g., wide area and/or local area) interface or port enabling communication via network 24. The memory 134 includes a plurality of memory devices, where a memory device includes one or more of a solid state memory, a hard drive, magnetic tape, etc. The memory controller 136 is a conventional memory controller to control data access (reads, writes, etc.) to data stored, or to be stored, in the memory 134. The partial task execution unit 138 includes a computing core (e.g., as shown in FIG. 2) or portions thereof.
Each storage unit receives its partial task and partial data access request (e.g., read, write, identify, etc.). The memory controller 136 coordinates access to the appropriate partial data to/from the memory 134 (e.g., first encoded data slices of sets of encoded data slices). The partial task execution unit 138 receives the partial data and the partial task, which it executes to produce a partial result. Continuing with the email example, storage unit 1 receives the first partial task for execution on first partial data (e.g., emails sent or received on the specific day from/by persons with a last name beginning with A-E); storage unit 2 receives the second partial task for execution on second partial data (e.g., emails sent or received on the specific day from/by persons with a last name beginning with G-K); and so on.
Storage unit 1 compiles a list of emails having the search word or phrase; storage unit 2 does the same; and so on by the other storage units. Each storage unit sends its partial result to the computing device, which compiles the partial results to produce the result 124. Note that each storage unit independently processes its partial task on its partial data, which, from storage unit to storage unit, may vary in processing time. For example, one storage unit may perform its partial task on its partial data faster than another storage unit. Further, the set of storage units typically process a plurality of tasks at any given time. Thus, with different processing speeds, the processing of the partial tasks of the plurality of tasks is occurring at different times, with different processing efficiencies, and with different delays.
FIG. 13 is a schematic block diagram of an example of a hierarchical coordination of processing a plurality of tasks. This example includes three levels of hierarchical processing (e.g., a first DSN level 140, a second (set of storage units [SU]) level 142, and a third (SU) level 144, but may include more or less levels. The first level, which may be tracked by a managing unit, a computing unit, integrity unit, or other unit of the DSN, includes a DSN level task queue, a DSN level “task in process” queue (or leased task queue), and DSN index information. For each set of storage units of the second level 142, a managing unit, one of the storage units, a computing device, etc., manages a set of SU task queue, a set of SU “task in process” queue, and set of SU index information. Each storage unit in a set of SUs manages its own task queue, “task in process” queue, and index information.
The DSN task queue stores tasks that have been requested by devices of the DSN for execution within the DSN but have not yet been started. When a task in the DSN task queue is being processed, it is transferred to the DSN “task in process” queue. The device managing the DSN task queue and the DSN “task in process” queue, utilizes the index information (which will be described in greater detail with reference to FIG. 15) to identify which set of storage units is to process the particular task. The device sends the task to the device managing the set of SU task queue, which stores the task therein. Each storage unit storage unit stores its corresponding partial task in its task queue. As tasks and partial tasks are started, they are transferred to the “task in process” queue. If a task is not fully completed in a given time frame (e.g., one or more partial tasks was not completed), the task and at least some of the partial tasks are moved back to the task queue (indicating that it was not completed and is being re-queued). If the task is successfully completed, the task and the partial tasks are deleted from the “task in process” queue (indicating that it was successfully completed).
FIG. 14 is a schematic block diagram of another example of a hierarchical coordination of multi-task processing of four tasks by a set of storage units with task execution units (TEU). Each of the four tasks is divided into five partial tasks. The fifth partial task of each task is further divided into two partial sub-tasks. For example, task 1 is divided in partial task 1_1, partial task 1_2, partial task 1_3, partial task 1_4, and partial task 1_5. The fifth partial task 1_5 is further divided into two partial sub-tasks partial task 1_5_1 and partial task 1_5_2. As another example, task 2 is divided in partial task 2_1, partial task 2_2, partial task 2_3, partial task 2_4, and partial task 2_5. The fifth partial task 2_5 is further divided into two partial sub-tasks partial task 2_5_1 and partial task 2_5_2. This may occur when storage unit 5 determines that it cannot process the corresponding partial task(s) efficiently, the data assigned to it has been further divided and storage in two or more other storage units, etc.
Storage unit 1 receives the first partial tasks 1_1, 2_1, 3_1, and 4_1; storage unit 2 receives the second partial tasks 1_2, 2_2, 3_2, and 4_2; and so on. Storage unit 5_1 receives the first partial sub-tasks of the fifth partial tasks (e.g., 1_5_1, 2_5_1, 3_5_1, and 4_5_1) and storage unit 5_2 receives the second partial sub-tasks of the fifth partial tasks (e.g., 1_5_2, 2_5_2, 3_5_2, and 4_5_2). Each storage unit includes a task queue, a “task in process” queue, and may further includes a partial task (PT) index node structure 146 (which includes the index information) to process their corresponding partial tasks.
FIG. 15 is a schematic block diagram of an example of a partial task index node structure 146 is used at one or more levels of the hierarchical structure to determine which set of storage units are to perform a task and which storage units in the set of storage units are to perform the corresponding partial tasks. In this example, the PT index node structure 146 includes a PT index node information section 148, an optional PT sibling node information section 150, and an option child node information section 150.
The PT index node information section 148 includes information for the corresponding device (e.g., DSN level device, set of SU level device, SU level, or sub-SU level) to determine whether it is responsible for a task, a partial task, or a partial sub-task. If it is not responsible, it uses the other sections (e.g., sibling and/or child) to find the device that is responsible. In this example, the PT index node information section 148 includes a PT name field 154 (e.g., name of the device, name of the tasks, partial tasks, and/or partial sub-tasks, etc.), a PT execution type field 156 (e.g., list of functions the device can perform, which may be further categorized based on the name of the tasks), and a PT expiration key field 158 (e.g., a given time frame for completion of the task, partial task, and/or partial sub-task).
The PT sibling node information section 150 includes a PT sibling name field 160 (e.g., name and/or DSN address of a sibling device), a PT minimum index key field 162, and a PT execution traits field 164. The PT minimum index key field includes the pillar number(s) of partial tasks and/or partial sub-tasks that the sibling device can process (e.g., storage unit 2, as a sibling to storage unit 1, is responsible for pillar number 2 partial tasks). The PT execution traits field 164 includes a list of what partial task and/or partial sub-tasks the sibling device can process (e.g., word or phrase search, math function, etc.).
The PT children node information section 152 includes a section for each child (e.g., storage unit five has two children nodes storage units 5_1 and 5_2). Each PT child node information section 166-168 includes a PT child name field 170 (e.g., name and/or DSN address of a child device), a PT child minimum index key field 172, and a PT child execution traits field 174. The PT child minimum index key field 172 includes sub-pillar number(s) of partial tasks and/or partial sub-tasks that the child device can process (e.g., storage unit 5_1, as a child to storage unit 5, is responsible for sub-pillar number 5_1 partial sub-tasks). The PT child execution traits field 174 includes a list of what partial task and/or partial sub-tasks the sibling device can process (e.g., word or phrase search, math function, etc.).
FIGS. 16-20 are schematic block diagrams of another example of a hierarchical coordination of multi-task processing of the four tasks of FIG. 14. FIG. 16 shows the four tasks having been issued but not yet started. Accordingly, at the set of SU level, the tasks are listed in the task queue and the “task in process” queue is empty. Each task is divided into a set of partial tasks and the first partial task of each task is further divided into first and second partial sub-tasks. Each storage unit stores it corresponding partial tasks and/or partial sub-tasks in their respective task queues and their corresponding “task in process” queues are empty. As an example, storage unit 2 includes partial tasks 1_2, 2_2, 3_2, and 4_2 in its partial task queue 2 and its “partial task in process” queue is empty.
In FIG. 17, the processing of task 1 has been initiated with a given expiration time. At each level, the expiration time is recorded in the index node structure 146, or other storage location. In addition, the task, partial task, and partial sub-tasks are moved from the task queue to the “task in process” queue. For example, storage unit 4 has moved partial task 1_4 from its partial task queue to its “partial task in process” queue.
In FIG. 18, all but storage unit 2 have completed their respective partial tasks and partial sub-tasks. Note that the light grey for partial tasks 1_1, 1_3, 1_4, and 1_5 indicates that these partial tasks have been completed and the corresponding partial results have been sent to the requesting computing device. For task 1, if the expiration time has not expired, then storage unit 2 has time to complete its partial task. If storage unit 2 finishes its partial task before the time expires, it deletes partial task 1_2 from its “partial task in process” queue and the device managing the queues at the set of SU levels deletes task 1 from the “task in process” queue. The deletion of the task and partial tasks from the “task in process” queues indicate that the task has been successfully completed. An example of this is shown in FIG. 20.
If the second storage unit cannot complete its partial task 1_2 before the time expires, it can request an extension of time before the time expires, it can send a notice that it cannot complete its partial task, or it can let the time expire. If the time expires as shown in FIG. 19, the second storage unit transfers the partial task 1_2 back to its partial task queue. In addition, the device managing the set of SU level queues transfers task 1 back to the task queue, indicating that it needs to be executed. The other storage units (e.g., 1, 3, 4, 5-1, and 5-2) may keep their partial results and send them again when task 1 is reactivated. As another example, the other storage units re-enter their corresponding partial tasks and partial sub-tasks into their respective task queues. As yet another example, with task 1 is reactivated, the device managing the set of SU queues only activates storage unit 2 to perform its partial task 1_2 and use the previous partial results of the other storage units.
With reference again to FIG. 18, it further shows that task 2 has been activated for processing. At each level, the task 2, partial tasks, and partial sub-tasks are transferred from the task queue to the “task in process” queue. Subsequent processing of task 2 will be done in a similar manner as task 1.
FIG. 21 is a logic diagram of another example of a method for coordinating multi-task processing in a DSN. The method includes step 180 where a computing device temporarily stores tasks in a task queue. The method further includes step 182 where the computing device identifies a task of the queued tasks for execution. Note that the task corresponds to performing a particular function on data, which is partitioned into a set of partial data elements. Further note that multiple tasks may be selected at a given time or in a time overlapping manner (e.g., one is not completed before another is started). Still further note that the task is identified by one or more of utilizing a first in first out approach; utilizing a task requester based priority scheme (e.g., higher priority requesters first); utilizing a task priority based scheme (e.g., higher priority tasks first); utilizing a resource balancing selection scheme (e.g., selecting tasks based on processing resource requirements and processing time requirements); and utilizing a conflict avoidance scheme (e.g., avoid concurrent performance of tasks on the same data).
The method further includes step 184 where the computing device partitions the task into partial tasks. The method continues at step 186 where the computing device sends partial task execution requests to at least some of the set of storage units (e.g., to a decode threshold number of storage units). The method continues at step 188 where the computing device transfers the task from the task queue to a task in process index and establishing an expiration time.
The method continues at step 190 where a determination is made as to whether the time has expired. If not, the method continues at step 192 where the computing device determines whether it has received a request for extension of time from a storage unit. If not, the method repeats at step 190. If a request for extension of time is received, the method continues at step 194 where the computing device extends the time and sends an updated expiration time to the storage unit(s). The method continues at step 190.
When the time expires the method continues at step 196 where the computing device determiners whether at least one partial task was not completed. When a partial task has not been completed prior to the expiration time, the method continues at step 198 where the computing device transfers the task from the task in process index to the task queue indicating that the task was not completed prior to the expiration time and re-queuing execution of at least a portion of the task. If all partial tasks were completed, the method continues at step 200 where the computing device deletes the task from the task in process index indicating that the task has been successfully completed.
FIG. 22 is a logic diagram of an example of a method for coordinating multi-task processing in a DSN. The method includes step 210 where a first storage unit temporarily stores a plurality of first partial tasks corresponding to a first partial task of each the plurality of tasks in a first storage unit task queue. The method continues at step 212 where the first storage unit receives a request to perform a first partial task of the task on the first partial data element. The method continues at step 214 where the first storage unit transfers the first partial task from the first storage unit task queue to a first storage unit task in process index.
The method continues at step 216 where the first storage unit determines whether it has capacity to complete performance of the first partial task prior to conclusion of the expiration time. If yes, the method continues at step 218 where the first storage unit performs the first partial task on the first partial data element to produce a first partial result. The method continues at step 220 where the first storage unit sends the first partial result for the first partial task of the task to the computing device. The method continues at step 222 where the first storage unit deletes the first partial task from the first storage unit task in process index.
When the first storage unit determines that it does not have the capacity to complete performance of the first partial task prior to conclusion of the expiration time, the method continues at step 224 where the first storage unit whether it can start performance of the first partial task prior to conclusion of the expiration time. If yes, the method continues at step 226 where it sends a request to extend the expiration time.
If the first storage unit cannot start prior to the conclusion of the expiration time, the method continues at step 228 where the first storage unit sends a notice that it cannot start prior to expiration of time or it just lets the time expire. The method continues at step 230 where the first storage unit transfers the partial task back to its task queue.
It is noted that terminologies as may be used herein such as bit stream, stream, signal sequence, etc. (or their equivalents) have been used interchangeably to describe digital information whose content corresponds to any of a number of desired types (e.g., data, video, speech, audio, etc. any of which may generally be referred to as ‘data’).
As may be used herein, the terms “substantially” and “approximately” provides an industry-accepted tolerance for its corresponding term and/or relativity between items. Such an industry-accepted tolerance ranges from less than one percent to fifty percent and corresponds to, but is not limited to, component values, integrated circuit process variations, temperature variations, rise and fall times, and/or thermal noise. Such relativity between items ranges from a difference of a few percent to magnitude differences. As may also be used herein, the term(s) “configured to”, “operably coupled to”, “coupled to”, and/or “coupling” includes direct coupling between items and/or indirect coupling between items via an intervening item (e.g., an item includes, but is not limited to, a component, an element, a circuit, and/or a module) where, for an example of indirect coupling, the intervening item does not modify the information of a signal but may adjust its current level, voltage level, and/or power level. As may further be used herein, inferred coupling (i.e., where one element is coupled to another element by inference) includes direct and indirect coupling between two items in the same manner as “coupled to”. As may even further be used herein, the term “configured to”, “operable to”, “coupled to”, or “operably coupled to” indicates that an item includes one or more of power connections, input(s), output(s), etc., to perform, when activated, one or more its corresponding functions and may further include inferred coupling to one or more other items. As may still further be used herein, the term “associated with”, includes direct and/or indirect coupling of separate items and/or one item being embedded within another item.
As may be used herein, the term “compares favorably”, indicates that a comparison between two or more items, signals, etc., provides a desired relationship. For example, when the desired relationship is that signal 1 has a greater magnitude than signal 2, a favorable comparison may be achieved when the magnitude of signal 1 is greater than that of signal 2 or when the magnitude of signal 2 is less than that of signal 1. As may be used herein, the term “compares unfavorably”, indicates that a comparison between two or more items, signals, etc., fails to provide the desired relationship.
As may also be used herein, the terms “processing module”, “processing circuit”, “processor”, and/or “processing unit” may be a single processing device or a plurality of processing devices. Such a processing device may be a microprocessor, micro-controller, digital signal processor, microcomputer, central processing unit, field programmable gate array, programmable logic device, state machine, logic circuitry, analog circuitry, digital circuitry, and/or any device that manipulates signals (analog and/or digital) based on hard coding of the circuitry and/or operational instructions. The processing module, module, processing circuit, and/or processing unit may be, or further include, memory and/or an integrated memory element, which may be a single memory device, a plurality of memory devices, and/or embedded circuitry of another processing module, module, processing circuit, and/or processing unit. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, cache memory, and/or any device that stores digital information. Note that if the processing module, module, processing circuit, and/or processing unit includes more than one processing device, the processing devices may be centrally located (e.g., directly coupled together via a wired and/or wireless bus structure) or may be distributedly located (e.g., cloud computing via indirect coupling via a local area network and/or a wide area network). Further note that if the processing module, module, processing circuit, and/or processing unit implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory and/or memory element storing the corresponding operational instructions may be embedded within, or external to, the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry. Still further note that, the memory element may store, and the processing module, module, processing circuit, and/or processing unit executes, hard coded and/or operational instructions corresponding to at least some of the steps and/or functions illustrated in one or more of the Figures. Such a memory device or memory element can be included in an article of manufacture.
One or more embodiments have been described above with the aid of method steps illustrating the performance of specified functions and relationships thereof. The boundaries and sequence of these functional building blocks and method steps have been arbitrarily defined herein for convenience of description. Alternate boundaries and sequences can be defined so long as the specified functions and relationships are appropriately performed. Any such alternate boundaries or sequences are thus within the scope and spirit of the claims. Further, the boundaries of these functional building blocks have been arbitrarily defined for convenience of description. Alternate boundaries could be defined as long as the certain significant functions are appropriately performed. Similarly, flow diagram blocks may also have been arbitrarily defined herein to illustrate certain significant functionality.
To the extent used, the flow diagram block boundaries and sequence could have been defined otherwise and still perform the certain significant functionality. Such alternate definitions of both functional building blocks and flow diagram blocks and sequences are thus within the scope and spirit of the claims. One of average skill in the art will also recognize that the functional building blocks, and other illustrative blocks, modules and components herein, can be implemented as illustrated or by discrete components, application specific integrated circuits, processors executing appropriate software and the like or any combination thereof.
In addition, a flow diagram may include a “start” and/or “continue” indication. The “start” and “continue” indications reflect that the steps presented can optionally be incorporated in or otherwise used in conjunction with other routines. In this context, “start” indicates the beginning of the first step presented and may be preceded by other activities not specifically shown. Further, the “continue” indication reflects that the steps presented may be performed multiple times and/or may be succeeded by other activities not specifically shown. Further, while a flow diagram indicates a particular ordering of steps, other orderings are likewise possible provided that the principles of causality are maintained.
The one or more embodiments are used herein to illustrate one or more aspects, one or more features, one or more concepts, and/or one or more examples. A physical embodiment of an apparatus, an article of manufacture, a machine, and/or of a process may include one or more of the aspects, features, concepts, examples, etc. described with reference to one or more of the embodiments discussed herein. Further, from figure to figure, the embodiments may incorporate the same or similarly named functions, steps, modules, etc. that may use the same or different reference numbers and, as such, the functions, steps, modules, etc. may be the same or similar functions, steps, modules, etc. or different ones.
Unless specifically stated to the contra, signals to, from, and/or between elements in a figure of any of the figures presented herein may be analog or digital, continuous time or discrete time, and single-ended or differential. For instance, if a signal path is shown as a single-ended path, it also represents a differential signal path. Similarly, if a signal path is shown as a differential path, it also represents a single-ended signal path. While one or more particular architectures are described herein, other architectures can likewise be implemented that use one or more data buses not expressly shown, direct connectivity between elements, and/or indirect coupling between other elements as recognized by one of average skill in the art.
The term “module” is used in the description of one or more of the embodiments. A module implements one or more functions via a device such as a processor or other processing device or other hardware that may include or operate in association with a memory that stores operational instructions. A module may operate independently and/or in conjunction with software and/or firmware. As also used herein, a module may contain one or more sub-modules, each of which may be one or more modules.
As may further be used herein, a computer readable memory includes one or more memory elements. A memory element may be a separate memory device, multiple memory devices, or a set of memory locations within a memory device. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, cache memory, and/or any device that stores digital information. The memory device may be in a form a solid state memory, a hard drive memory, cloud memory, thumb drive, server memory, computing device memory, and/or other physical medium for storing digital information.
While particular combinations of various functions and features of the one or more embodiments have been expressly described herein, other combinations of these features and functions are likewise possible. The present disclosure is not limited by the particular examples disclosed herein and expressly incorporates these other combinations.

Claims

What is claimed is:

1. A method comprises:

temporarily storing, by a computing device of a dispersed storage network (DSN), a plurality of tasks in a task queue to produce queued tasks;

identifying, by the computing device, a task of the queued tasks for execution, wherein the task corresponds to performing a particular function on data, wherein the data is partitioned into a set of partial data elements, wherein a first partial data element of the set of partial data elements is storage in a first storage unit of a set of storage units of the DSN, wherein the first storage unit includes a task execution module;

partitioning, by the computing device, the task into a plurality of partial tasks;

sending, by the computing device, partial task execution requests to at least some of the set of storage units, wherein a first one of the partial task execution requests is sent to the first storage unit and includes a first partial task of the set of the plurality of partial tasks and a data access request regarding the first partial data element;

transferring, by the computing device, the task from the task queue to a task in process index and establishing an expiration time; and

when a partial task of the plurality of partial tasks has not been completed prior to the expiration time, transferring, by the computing device, the task from the task in process index to the task queue indicating that the task was not completed prior to the expiration time and re-queuing execution of at least a portion of the task.

2. The method of claim 1, wherein the identifying the task comprises one of:

utilizing a first in first out approach;

utilizing a task requester based priority scheme;

utilizing a task priority based scheme;

utilizing a resource balancing selection scheme; and

utilizing a conflict avoidance scheme.

3. The method of claim 1 further comprises:

the data is partitioned is partitioned to the set of partial data elements in accordance with a dispersed storage error encoding using an encoded matrix that includes a unity matrix component, wherein a data segment of the data is encoded into a set of encoded data slices.

4. The method of claim 1 further comprises:

when each of the plurality of partial tasks has been completed prior to the expiration time, deleting, by the computing device, the task from the task in process index indicating that the task has been successfully completed.

5. The method of claim 1 further comprises:

prior to conclusion of the expiration time, receiving a request from one of the least some of the set of storage units, wherein the request is an indication the one of the least some of the set of storage units is processing a corresponding one of the plurality of partial tasks but requires addition time beyond the expiration time to complete;

changing the expiration time to a new expiration time; and

sending the new expiration time to the one of the least some of the set of storage units.

6. The method of claim 1 further comprises:

temporarily storing, by the first storage unit, a plurality of first partial tasks corresponding to a first partial task of each the plurality of tasks in a first storage unit task queue to produce queued first partial tasks;

receiving, by the first storage unit, a request to perform a first partial task of the task on the first partial data element;

transferring, by the first storage unit, the first partial task from the first storage unit task queue to a first storage unit task in process index;

determining, by the storage unit, whether the first storage unit has capacity to at least start performing of the first partial task of the task on the first partial data element prior to conclusion of the expiration time;

when the first storage unit has capacity to complete performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time, performing, by the first storage unit, the first partial task of the task on the first partial data element to produce a first partial result;

sending, by the first storage unit, the first partial result for the first partial task of the task to the computing device; and

deleting, by the first storage unit, the first partial task from the first storage unit task in process index.

7. The method of claim 6 further comprises:

determining, by the first storage unit, that the first storage unit cannot complete performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time; and

prior to the conclusion of the expiration time, sending, by the first storage unit, a request to the computing device for an extension of the expiration time.

8. The method of claim 6 further comprises:

determining, by the first storage unit, that the first storage unit cannot commence performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time; and

prior to the conclusion of the expiration time, sending, by the first storage unit, a notice to the computing device regarding the non-commencement of the performance of the first partial task of the task on the first partial data element.

9. The method of claim 6 further comprises:

determining, by the first storage unit, that the first storage unit cannot commence performance of the first partial task of the task on the first partial data element prior to the conclusion of the expiration time; and

allowing, by the first storage unit, the conclusion of the expiration time without notice to the computing device.

10. A computer readable memory comprises:

a first memory element that stores operational instructions that, when executed by a computing device of a dispersed storage network (DSN), causes the computing device to:

temporarily store a plurality of tasks in a task queue to produce queued tasks;

a second memory element that stores operational instructions that, when executed by the computing device, causes the computing device to:

identify a task of the queued tasks for execution, wherein the task corresponds to performing a particular function on data, wherein the data is partitioned into a set of partial data elements, wherein a first partial data element of the set of partial data elements is storage in a first storage unit of a set of storage units of the DSN, wherein the first storage unit includes a task execution module;

partition the task into a plurality of partial tasks;

send partial task execution requests to at least some of the set of storage units, wherein a first one of the partial task execution requests is sent to the first storage unit and includes a first partial task of the set of the plurality of partial tasks and a data access request regarding the first partial data element; and

transfer the task from the task queue to a task in process index and establishing an expiration time; and

a third memory element that stores operational instructions that, when executed by the computing device, causes the computing device to:

when a partial task of the plurality of partial tasks has not been completed prior to the expiration time, transfer the task from the task in process index to the task queue indicating that the task was not completed prior to the expiration time and re-queuing execution of at least a portion of the task.

11. The computer readable memory of claim 10, wherein the identifying the task comprises one of:

utilizing a first in first out approach;

utilizing a task requester based priority scheme;

utilizing a task priority based scheme;

utilizing a resource balancing selection scheme; and

utilizing a conflict avoidance scheme.

12. The computer readable memory of claim 10 further comprises:

13. The computer readable memory of claim 10 further comprises:

a fourth memory element that stores operational instructions that, when executed by the computing device, causes the computing device to:

when each of the plurality of partial tasks has been completed prior to the expiration time, delete the task from the task in process index indicating that the task has been successfully completed.

14. The computer readable memory of claim 10 further comprises:

prior to conclusion of the expiration time, receive a request from one of the least some of the set of storage units, wherein the request is an indication the one of the least some of the set of storage units is processing a corresponding one of the plurality of partial tasks but requires addition time beyond the expiration time to complete;

change the expiration time to a new expiration time; and

send the new expiration time to the one of the least some of the set of storage units.

15. The computer readable memory of claim 10 further comprises:

a fourth memory element that stores operational instructions that, when executed by the first storage unit, causes the first storage unit to:

temporarily store a plurality of first partial tasks corresponding to a first partial task of each the plurality of tasks in a first storage unit task queue to produce queued first partial tasks;

receive a request to perform a first partial task of the task on the first partial data element;

transfer the first partial task from the first storage unit task queue to a first storage unit task in process index;

determine whether the first storage unit has capacity to at least start performing of the first partial task of the task on the first partial data element prior to conclusion of the expiration time;

when the first storage unit has capacity to complete performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time, perform the first partial task of the task on the first partial data element to produce a first partial result;

send the first partial result for the first partial task of the task to the computing device; and

delete the first partial task from the first storage unit task in process index.

16. The computer readable memory of claim 15 further comprises:

a fifth memory element that stores operational instructions that, when executed by the first storage unit, causes the first storage unit to:

determine that the first storage unit cannot complete performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time; and

prior to the conclusion of the expiration time, send a request to the computing device for an extension of the expiration time.

17. The computer readable memory of claim 15 further comprises:

determine that the first storage unit cannot commence performance of the first partial task of the task on the first partial data element prior to conclusion of the expiration time; and

prior to the conclusion of the expiration time, send a notice to the computing device regarding the non-commencement of the performance of the first partial task of the task on the first partial data element.

18. The computer readable memory of claim 15 further comprises:

determine that the first storage unit cannot commence performance of the first partial task of the task on the first partial data element prior to the conclusion of the expiration time; and

allow the conclusion of the expiration time without notice to the computing device.