2017-03-13 Assigned to INTERNATIONAL BUSINESS MACHINES CORPORATION reassignment INTERNATIONAL BUSINESS MACHINES CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: RESCH, JASON K., MCSHANE, NIALL J.
Methods for use in a dispersed storage network (DSN) to retrieve encoded data from memory device of an impaired storage unit. In various examples, a computing device of the DSN issues requests to a plurality of storage units, including the impaired storage unit, to recover at least a decode threshold number of encoded data slices of a set of encoded data slices. When the impaired storage unit determines that it is not able to quickly retrieve the requested data slice for provision to the computing device, the impaired storage unit promptly issues a quasi-error response instead. When the computing device receives less than the decode threshold number of encoded data slices and a quasi-error response, it may elect to issue another slice request(s) to another storage unit(s) and/or issue a continue request instructing the impaired storage unit to continue processing the request to recover the data slice stored therein.
This invention relates generally to computer networks, and more particularly to recovery of data from impaired storage units of a dispersed storage network.
FIG. 10 is a logic diagram illustrating an example of recovery of stored data in accordance with the present disclosure when retrieval is degraded.
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 storage (DS) error encoded data.
Each of the storage units 36 is operable to store DS error encoded data and/or to execute (e.g., in a distributed manner) maintenance tasks and/or data-related tasks. The tasks may be 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, maintenance tasks (e.g., rebuilding of data slices, updating hardware, rebooting software, restarting a particular software process, performing an upgrade, installing a software patch, loading a new software revision, performing an off-line test, prioritizing tasks associated with an online test, etc.), etc.
Each of the computing devices 12-16, the managing unit 18, integrity processing unit 20 and (in various embodiments) the storage units 36 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.
As another example, the managing unit 18 performs network operations, network administration, and/or network maintenance. Network operations includes authenticating user data allocation/access 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. Examples of load balancing, service differentiation and dynamic resource selection for data access operations are discussed in greater detail with reference to FIGS. 9-13.
To support data storage integrity verification within the DSN 10, the integrity processing unit 20 (and/or other devices in the DSN 10) may perform 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. Retrieved encoded slices are checked for errors due to data corruption, outdated versioning, etc. If a slice includes an error, it is flagged as a ‘bad’ or ‘corrupt’ slice. Encoded data slices that are not received and/or not listed may be flagged as missing slices. Bad and/or missing slices may be subsequently rebuilt using other retrieved encoded data slices that are deemed to be good slices in order to produce rebuilt slices. A multi-stage decoding process may be employed in certain circumstances to recover data even when the number of valid encoded data slices of a set of encoded data slices is less than a relevant decode threshold number. The rebuilt slices may then be written to DSN memory 22. Note that the integrity processing unit 20 may be a separate unit as shown, included in DSN memory 22, included in the computing device 16, and/or distributed among the storage units 36.
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 five, a decode threshold of three, a read threshold of four, and a write threshold of four. 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.
FIG. 5 illustrates a specific example of Cauchy Reed-Solomon encoding with a pillar width 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. In the illustrated example, the value X11=aD1+bD5+cD9, X12=aD2+bD6+cD10, . . . X53=mD3+nD7+oD11, and X54=mD4+nD8+oD12.
In order 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.
Typically, when memory is quarantined or in an otherwise impaired state, the storage unit holding that memory may respond to a data access request by returning an error rather than service the request. Alternatively, the storage unit may attempt to service the request but do so very slowly (due to the impaired memory). Such actions may effectively delay processing of the data access request. As described more fully below in conjunction with the novel examples of FIGS. 9 and 10, a “quasi-error” response is introduced for use when retrieving data from an impaired memory. Briefly, an impaired storage unit may immediately return a quasi-error response to a data access request (e.g., a read data or write data request) involving impaired memory (e.g., memory that is not able to produce an encoded date slice in a relatively timely manner due to network conditions, degraded memory, heavy load conditions, maintenance operations, quarantine, etc.). A computing device receiving the quasi-error response may elect to issue a new data access request to another storage unit(s) and/or may issue a “continue request” command to the impaired storage unit such that the storage unit continues to attempt to process the data access request, even if a there is high probability of continued delay or failure.
In another example, a storage unit issuing a “quasi-error” response to a data access request may be configured to continue processing the request by default. During continued processing of the request by the impaired storage unit, a computing device receiving the quasi-error may concurrently attempt to recover impacted data (e.g., a threshold number of encoded data slices) from other storage units. If sufficient data is recovered from the other storage units, or the computing device otherwise determines that continued processing of the original data access request is unnecessary or undesirable, the computing device may issue a “cancel request” command to the impaired storage unit to stop processing of the data access request.
Referring now to FIG. 9, a schematic block diagram of another embodiment of a DSN performing recovery of stored data from an impaired storage unit in accordance with the present disclosure is shown. The illustrated DSN includes the computing device 16 of FIG. 1, the network 24 of FIG. 1, and a storage unit set 82. The storage unit set 82 includes a set of storage units 82 a-82 h. Each storage unit may be implemented utilizing the storage unit 36 of FIG. 1, and each of the storage units includes a DS client module 34, a processing module and memory (not separately illustrated). Hereafter, the storage unit set may be interchangeably referred to as a set of storage units. The storage units of a storage set may be located at a same physical location (site) or located at multiple physical locations without departing from the technology as described herein. The DSN functions to recover stored data when data retrieval is degraded.
The storage unit set 82 may include a number of storage units in accordance with dispersal parameters of a dispersed storage error coding function, where a data segment of data is dispersed storage error coded in accordance with the dispersed storage error coding function utilizing the dispersal parameters to create a set of encoded data slices. For example, the storage unit set 82 includes storage units 82 a-82 h when a width of the dispersal parameters is 8. The dispersal parameters further include a decode threshold number, where a decode threshold number (e.g., 5 when the width is 8) of encoded data slices of the set of encoded data slices is a minimum number of encoded data slices typically required to recover the data segment. The data that is encoded into the DS error encoded data may be of any size and/or of any content. For example, the data may be one or more digital books, a copy of a company's emails, a large-scale Internet search, a video security file, one or more entertainment video files (e.g., television programs, movies, etc.), data files, and/or indexing and key information for use in dispersed storage operations.
In an example of operation of the recovering of the stored data, the computing device 16 issues a decode threshold number of slice requests to storage units of the storage unit set 82. Issuing the slice requests may include one or more of receiving a retrieve data request, selecting the storage units, generating the read slice requests, and sending, via the network 24, the generated read slice requests to the selected storage units. For example, the computing device 16 generates and sends, via the network 24, slice requests 84 a-84 e to the storage units 82 a-82 e.
Having sent the slice requests, the computing device 16 receives responses within a response timeframe, where the responses includes less than a decode threshold number of encoded data slices and at least one quasi-error response. For example, the computing device 16 receives read slice responses from storage units 82 a, 82 c, 82 d and 82 e that include encoded data slices 86 a, 86 c, 86 d and 86 e, respectively, and receives a quasi-error response 88 from the impaired storage unit 82 b when the storage unit 82 b has impaired memory and is unable to immediately (e.g., within a relatively short period of time in relation to a typical response time of the storage unit) send the encoded data slice 86 b to the computing device 16.
Having received the responses, the computing device 16 determines whether to utilize at least one other storage unit of the storage unit set (e.g., one of storage units 82 f-82 h). Such a determination may be based on one or more of: the number of error responses (e.g., quasi-error responses, slice unavailable responses); an estimated time to retrieve another encoded data slice; a timing requirement; and the number of other available storage units of the storage unit set. For example, the computing device 16 determines not to utilize another storage unit when receiving the quasi-error response with regards to the encoded data slice 86 b and the storage units 82 f-82 h are determined to be offline or unreachable via the network 24.
When not utilizing another storage unit, the computing device 16 in one example issues at least one continue request to a storage unit corresponding to at least one quasi-error response. For example, the computing device 16 issues, via the network 24, a continue request 90 to the storage unit 82 b with regards to the encoded data slice 86 b. In response, the storage unit 82 b continues to process the slice request (if not already doing so as described below) and proceeds to send, via the network 24, the encoded data slice 86 b to the computing device 16. When the storage unit 82 b is unable to retrieve the encoded data slice 86 b (e.g., after a threshold amount of time has elapsed), storage unit 82 b may send an error response to the computing device 16. When receiving the decode threshold number of encoded data slices, the computing device 16 disperse storage error decodes the decode threshold number of encoded data slices to reproduce a data segment of the data object of the retrieve data request.
Alternatively, or in addition to, the computing device 16 issues another slice request to another storage unit to produce the decode threshold number of encoded data slices. For example, the computing device 16 substantially simultaneously sends the continue request 90 to the storage unit 82 b and sends a slice request 84 f to the storage unit 82 f (or a storage unit of another set of storage units if copies of the relevant encoded data slices are stored elsewhere) with regards to retrieving the encoded data slice 86 f, receives at least one of the encoded data slice 86 b and the encoded data slice 86 f to complete the decode threshold number of encoded data slices, and disperse storage error decodes the decode threshold number of encoded data slices to reproduce the data segment. In another example, after issuing a quasi-error response, the storage units 82 a-82 h may be configured to automatically continue processing a data access request until a cancel request 92 is received or a final error response is issued (e.g., continued processing of slice request 84 b by storage unit 82 b is not contingent on receipt of continue request 90).
In another example of reading encoded data slices of a stored set of encoded data slices having a decode threshold number of 10 and a pillar width of 15, wherein 10 slice requests are issued to a set of 15 storage units and 9 data slices and 1 quasi-error response are received, a requesting device may determine to issue an additional slice request to one or more of the remaining 5 storage units. A continue request may also be issued to the impaired storage unit if it is not configured to automatically continue processing the slice relevant slice request, or a cancel request may be issued to stop processing of the slice request when an additional slice is available or likely to be available. If, however, the remaining 5 storage units are unavailable (e.g., offline), the requesting device will generally request continued processing of the slice request by the impaired storage unit (or refrain from issuing a cancel request) in an attempt to recover the decode threshold number of encoded data slices.
FIG. 10 is a logic diagram illustrating an example of recovery of stored data in accordance with the present disclosure when retrieval is degraded. The method includes step 100 where a processing module (e.g., of a computing device 16) issues at least a decode threshold number of slice requests to storage units of a storage unit set. For example, the processing module selects the storage units, generates the slice requests, and sends the slice requests to the selected storage units.
The method continues at step 102 where the processing module receives responses that include less than a decode threshold number of encoded data slices and at least one quasi-error response. The method continues at step 104 where the processing module determines whether to utilize another storage unit of the storage unit set. For example, the processing module determines not to utilize another storage unit when a calculated probability of recovering an incremental encoded data slice from the other storage unit is a calculated probability of recovering an encoded data slice from a storage unit associated with the at least one quasi-error response, or the calculated probability of recovering an encoded data slice from a storage unit associated with the at least one quasi-error response is lower than threshold value. Alternatively, the processing module determines not to utilize another storage unit when slice requests were initially issued to all storage units of a storage set.
When not utilizing another storage unit, the method continues at step 106 where the processing module issues at least one continue request to the storage unit corresponding to the at least one quasi-error response (or, alternatively, defers issuing a cancel request when the storage unit is configured to automatically continue processing a slice request after issuing a quasi-error). For example, the processing module identifies the storage unit, generates the continue request (e.g., to include a status code for the continue request and a slice name associated with encoded data slice), and sends the continue request to the identified storage unit. When receiving the decode threshold number of encoded data slices, the method continues at step 108 where the processing module dispersed storage error decodes the decode threshold number of encoded data slices to reproduce a data segment of a data object for retrieval.
The methods described above in conjunction with the computing device 16 and storage units can alternatively be performed by other modules (e.g., DS client modules 34) of a dispersed storage network or by other devices (e.g., managing unit 18 or integrity processing unit 20). Any combination of a first module, a second module, a third module, a fourth module, etc. of the computing devices and the storage units may perform the method described above. In addition, at least one memory section (e.g., a first memory section, a second memory section, a third memory section, a fourth memory section, a fifth memory section, a sixth memory section, etc. of a non-transitory computer readable storage medium) that stores operational instructions can, when executed by one or more processing modules of one or more computing devices and/or by the storage units of the dispersed storage network (DSN), cause the one or more computing devices and/or the storage units to perform any or all of the method steps described above.
issuing the continue request to the impaired storage unit or the additional slice request to the additional storage unit.
dispersed storage error decoding the decode threshold number of encoded data slices to recover the corresponding data segment.
a number of additional storage units of the set of storage units to which a slice request was not issued.
determining that a calculated probability of receiving an encoded data slice from the additional storage unit is greater than a calculated probability of receiving an encoded data slice from the impaired storage unit.
6. The method of claim 1, wherein the continue request, when issued, includes a status code and a slice name of an encoded data slice.
selecting the plurality of storage units based on the retrieve data request.
8. The method of claim 1, wherein determining to issue at least one of a continue request or an additional slice request includes determining to issue both the continue request and the additional slice request.
issue, via the network interface, the additional slice request to the additional storage unit.
dispersed storage error decode the decode threshold number of encoded data slices to recover the corresponding data segment.
issue, via the network interface, a cancel request to the impaired storage unit, the cancel request requesting discontinued processing of a slice request received by the impaired storage unit.
determining to issue, via the network interface, a continue request to the impaired storage unit, the continue request requesting continued processing of a slice request received by the impaired storage unit and corresponding to the quasi-error response.
in response to determining that the encoded data slice is not immediately available, send, via the network interface, a quasi-error response to the computing device.
in response to the continue request, continue processing of the slice request.
in response to the cancel request, discontinue processing of the slice request.
sending, via the network interface, an error response to the computing device.