Expanding slice count in response to low-level failures

A method for execution by a computing device of a dispersed storage network (DSN). The method begins with identifying an encoded data slice for rebuilding, wherein a data segment of a data object is dispersed storage error encoded to produce a set of encoded data slices that is stored in a set of storage units of the DSN, wherein the set of encoded data slices includes the encoded data slice, wherein in a storage unit of the set of storage units includes a memory device that stores the encoded data slice. The method continues by identifying an issue with the memory device and by identifying sets of encoded data slices. The method continues by generating an additional encoded data slice for each of the sets of encoded data slices to produce a group of encoded data slices and storing the group of encoded data slices in memory of the DSN.

Not applicable.

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

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. With cloud storage systems, memory devices are known to fail, go offline, or otherwise be unavailable. Data stored within these memory devices may be temporarily unavailable or permanently damaged or lost.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1is a schematic block diagram of an embodiment of a dispersed, or distributed, storage network (DSN)10that includes a plurality of computing devices12-16, a managing unit18, an integrity processing unit20, and a DSN memory22. The components of the DSN10are coupled to a network24, 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).

Each of the computing devices12-16, the managing unit18, and the integrity processing unit20include a computing core26, which includes network interfaces30-33. Computing devices12-16may 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 unit18and the integrity processing unit20may be separate computing devices, may be a common computing device, and/or may be integrated into one or more of the computing devices12-16and/or into one or more of the storage units36.

Each interface30,32, and33includes software and hardware to support one or more communication links via the network24indirectly and/or directly. For example, interface30supports a communication link (e.g., wired, wireless, direct, via a LAN, via the network24, etc.) between computing devices14and16. As another example, interface32supports communication links (e.g., a wired connection, a wireless connection, a LAN connection, and/or any other type of connection to/from the network24) between computing devices12and16and the DSN memory22. As yet another example, interface33supports a communication link for each of the managing unit18and the integrity processing unit20to the network24.

As another example, the managing unit18performs 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 module34) to/from the DSN10, and/or establishing authentication credentials for the storage units36. 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 DSN10. Network maintenance includes facilitating replacing, upgrading, repairing, and/or expanding a device and/or unit of the DSN10.

The integrity processing unit20performs rebuilding of ‘bad’ or missing encoded data slices. At a high level, the integrity processing unit20performs rebuilding by periodically attempting to retrieve/list encoded data slices, and/or slice names of the encoded data slices, from the DSN memory22. 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 memory22.

In the present example, Cauchy Reed-Solomon has been selected as the encoding function (a generic example is shown inFIG. 4and a specific example is shown inFIG. 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 device12or16divides 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. 5illustrates 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-X14corresponds to a first encoded data slice (EDS1_1), the second row of X21-X24corresponds to a second encoded data slice (EDS2_1), the third row of X31-X34corresponds to a third encoded data slice (EDS3_1), the fourth row of X41-X44corresponds to a fourth encoded data slice (EDS4_1), and the fifth row of X51-X54corresponds to a fifth encoded data slice (EDS5_1). Note that the second number of the EDS designation corresponds to the data segment number.

As a result of encoding, the computing device12or16produces 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 EDS1_1through EDS5_1and the first set of slice names includes SN1_1through SN5_1and the last set of encoded data slices includes EDS1_Y through EDS5_Y and the last set of slice names includes SN1_Y through SN5_Y.

To recover a data segment from a decode threshold number of encoded data slices, the computing device uses a decoding function as shown inFIG. 8. As shown, the decoding function is essentially an inverse of the encoding function ofFIG. 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 rows1,2, and4, the encoding matrix is reduced to rows1,2, and4, and then inverted to produce the decoding matrix.

FIG. 9is a schematic block diagram of an example of identifying a memory device issue and generating additional encoded data slices to provide additional reliability. As illustrated, a set of storage units36(e.g., SU #1-n) stores sets of encoded data slices (e.g., EDS1_1-EDS n_1, EDS1_8-EDS n_8). Each storage unit36includes four memory devices90that initially each store two encoded data slices of a corresponding two of the sets of encoded data slices. For example, the first memory device90of a first storage unit (SU #136) stores a first encoded data slice of a first set (e.g., EDS1_1) and a first encoded data slice of a second set (e.g., EDS1_2). As another example, a second memory device of the second storage unit stores a second encoded data slice of a third set (e.g., EDS2_3) and a second encoded data slice of a fourth set (e.g., EDS2_4), and so on.

When encoded data slice EDS1_3is identified for rebuilding (e.g., corrupt, damaged, etc.), a computing device12or16identifies the memory device where the identified encoded data slice is stored (e.g., the second memory device90of SU #136) and checks whether the memory device has an issue (e.g., soft failure, flagged for replacing, exceeded an age limit, etc.). When a memory device has an issue, other encoded data slices stored therein are going to require rebuilding when the memory device fails. To avoid, or reduce the need for, future rebuilding of these encode data slices, additional encoded data slices are created and stored in a different memory location (e.g., a different storage unit).

For instance, the computing device generates one or more additional encoded data slices (EDSs) for each set of EDSs having an EDS stored in the memory device with the issue. As an example for a set of encoded data slices, the computing device adds another row to the encoding matrix (e.g., ofFIGS. 4 and 5) and matrix multiples the additional row of the encoding matrix with the data matrix to produce a new (i.e., additional) encoded data slice. In the present example, the computing device generates an additional encoded data slice (EDS n_4) to provide additional reliability for the set of encoded data slices that includes EDS1_4. The additional encoded data slice is stored in the fourth memory device of the nth storage unit. Note that the nth storage unit may be one of the storage units in the set of storage units or an extra storage unit, thus expanding the set of storage units by one. Further note that the encoded data slice identified for rebuilding is rebuilt using a rebuilding processing of reconstructing the data segment and re-encoding the reconstructed data segment. Still further note that the computing device may generate an additional encoded data slice (e.g., EDS n_3) for the set of encoded data slices including EDS1_3.

FIG. 10is a schematic block diagram of another example of identifying a memory device issue and generating additional encoded data slices to provide additional reliability. As shown, encoded data slice EDS1_5is identified for rebuilding. A computing device identifies the memory device (e.g., third memory device90), storage unit (e.g., SU#136) storing the identified encoded data slice, and an issue with the storage unit (e.g., soft failure, flagged for replacing, exceeding an age limit, etc.). The computing device then identifies sets of encoded data slices that have an encoded data slice of the sets of encoded data slices stored in the storage unit (e.g., EDS1_1-EDS n_1through EDS1_8-EDS n_8). The computing device then generates additional encoded data slices (e.g., EDS n+1_1-EDS n+1_8) to provide additional reliability for each of the sets of encoded data slices. The additional encoded data slices are stored in the memory devices of another storage unit (SU #n+136) thereby expanding the set of storage units.

FIG. 11is a schematic block diagram of an example of generating additional encoded data slices. As shown, a set of storage units initially include 6 storage units (e.g., SU#1-636) that initially store Y sets of encoded data slices (e.g., EDS1_1-EDS5_1through EDS1_Y-EDS5_Y). At a first time (e.g., t1), an encoded data slice EDS2_1, which is stored in a memory device of the second storage unit, is identified by a computing device for rebuilding. The computing device then identifies the second storage unit (e.g., SU#2) to have a memory issue. The computing device then generates additional encoded data slices (e.g., EDS6_1, EDS6_Y) to provide additional reliability for each of the sets of encoded data slices. As shown, the computing device then stores the additional encoded data slices (e.g., EDS6_1-EDS6_Y) in the sixth storage unit of the set of storage units.

At a second time (e.g., t2), an issue with the memory of the second storage unit is resolved and the encoded data slice in need of rebuilding has been rebuilt. At this point in time, the computing device determines whether to delete the additional encoded data slices (EDS6_1-EDS6_Y). If so, they are delated as shown. Otherwise, they remain the storage unit #6.

At a further time (e.g., tn), the computing device identifies encoded data slices EDS4_Y and EDS5_1for rebuilding and identifies storage units four and five to have a memory issue. The computing device generates additional encoded data slices (e.g., EDS6_1-EDS6_Y, EDS8_1-EDS8_Y) and then stores the additional encoded data slices in the sixth storage unit of the set of storage units and two other storage units (e.g., SU #n, SU #n+1). As such, the set of storage units are expanded to include storage units #1, #2, #3, #6, #n+1 and #n+2. Note the additional encoded data slices may be generated one or more times and may be stored in one or more storage units. For example, the group of encoded data slices EDS6_1through EDS6_Y may be generated and copied to form three groups of encoded data slices EDS6_1through EDS6_Y. Each one of the three groups are then stored in storage units SU #6, SU #n+1 and SU #n+2.

FIG. 12is a logic flow diagram of a method of identifying a memory device issue and generating additional encoded data slices. The method begins with step100, where a computing device identifies an encoded data slice for rebuilding. Note that a data segment of a data object is dispersed storage error encoded to produce a set of encoded data slices that is stored in a set of storage units of the DSN. Further note that the set of encoded data slices includes the encoded data slice for rebuilding and a storage unit of the set of storage units includes a plurality of memory devices. Still further note that the storage unit includes a memory device of the plurality of memory devices that stores the encoded data slice.

The method continues with step102, where the computing device determines if there is an issue (e.g., soft failure, flagged for replacing, exceeded an age limit, etc.) with the memory device. For example, the computing device determines (e.g., identifies) the issue by one or more of, receiving a message indicating the memory device has the issue, accessing a maintenance schedule that indicates the memory device is identified for replacement, and determining the storage unit is inaccessible.

When there is not an issue with the memory device, the method loops back to step100. When there is an issue with the memory device, the method continues to step104, where the computing device identifies sets of encoded data slices, of which a first encoded data slice of each of the sets of encoded data slices is stored in the memory device. For example, the computing device identifies the sets of encoded data slices by sending a list request to the storage unit regarding the group of encoded data slices, receiving a list of group of slice names for the group of encoded data slices, and interpreting the group of slices names to identify the sets of encoded data slices.

The method continues with step106, where the computing device generates at least one additional encoded data slice for each of the sets of encoded data slices to produce at least one group of encoded data slices. For example, the computing device generates the at least one additional encoded data slice for each of the sets of encoded data slices by determining a number of additional encoded data slices to generate for the each of the sets of encoded data slices. Note the number is based on a comparison of one or more of the write threshold number of the sets of encoded data slices, the read threshold number of the sets of encoded data slices, the decode threshold number of the sets of encoded data slices, and the pillar width number of the sets of encoded data slices.

The computing device may also determine the number by determining a cost associated with an expanded set of storage units, wherein the expanded set of storage units include at least one of the set of storage units and one or more other storage units. The cost associated with the expanded set of storage units includes on one or more of historical performance, bandwidth, and available storage. For example, the computing device may determine to generate a first number of additional encoded data slices when the cost is below a first cost threshold. As another example, the computing device may determine to generate a second number of additional encoded data slices when the cost is equal to or above the first cost threshold. Note the second number is less than the first number.

For example, assuming that each set of the sets of encoded data slices includes 4 stored encoded data slices after identifying the memory issue, the decode threshold is 4, the read/write threshold is 5 and the pillar width number is 8, the computing device generates two additional encoded data slices for each of the sets of encoded data slices (to bring each set to 6 stored encoded data slices), when the comparison of the available encoded data slices each of sets of encoded data slices with the decode threshold number indicates a first difference (e.g., 0), and the cost analysis supports the expansion. As another example, assuming that each set of the sets of encoded data slices includes 5 stored encoded data slices after identifying the memory issue, the decode threshold is 4, the read/write threshold is 5 and the pillar width number is 8, the computing device generates one additional encoded data slice for each of the sets of encoded data slices (now each set stores 6 encoded data slices), when the comparison of the available encoded data slices of each of sets of encoded data slices with the decode threshold indicates a second difference (e.g., 1), and the cost analysis supports the expansion.

The method continues with step108, where the computing device stores the group of encoded data slices in memory of the DSN. For example, the computing device stores the group of encoded data slices in one or more other memory devices of the plurality of memory devices of the storage unit. As another example, the computing device stores the group of encoded data slices in another storage unit, wherein the set of storage units is expanded to include the other storage unit.