Efficient computation of only the required slices

Abstract

A method includes determining whether an encoded data slice (EDS) of “x” number of EDSs of a set of EDSs requires rebuilding, where the set of EDSs includes a pillar width number of EDSs, and the “x” number of EDSs is stored in “x” number of storage units of a pillar width number of storage units. When the encoded data slice requires rebuilding, the method continues by identifying one of a “z” number of EDSs to replace the encoded data slice, where the “z” number of EDSs are not currently stored in the set of storage units. The method continues by constructing the one of the “z” number of EDSs from a decode threshold number of EDSs of the “x” number of EDSs and sending the one of the “z” number of EDSs to a corresponding storage unit of the “z” number of storage units.

What is claimed is: 
     
         1 . A method for execution by a computing device within a dispersed storage network (DSN), the method comprises:
 determining whether an encoded data slice of “x” number of encoded data slices of a set of encoded data slices requires rebuilding, wherein:
 a data segment of a data object is dispersed storage error encoded to produce the set of encoded data slices, 
 the set of encoded data slices includes a pillar width number of encoded data slices, 
 the “x” number of encoded data slices is stored in “x” number of storage units of a pillar width number of storage units, 
 “x” is equal to or greater a write threshold number of encoded data slices of the set of encoded data slices and is less than the pillar width number, and 
 “z” number of encoded data slices corresponds to encoded data slices of the set of encoded data slices that are not currently stored in “z” number of storage units of the pillar width number of storage units, and 
 “z” is equal to the pillar width number minus “x”; and 
   when the encoded data slice requires rebuilding:
 identifying one of the “z” number of encoded data slices of the set of encoded data slices to replace the encoded data slice; 
 constructing the one of the “z” number of encoded data slices from a decode threshold number of encoded data slices of the “x” number of encoded data slices; and 
 sending the one of the “z” number of encoded data slices to a corresponding storage unit of the “z” number of storage units. 
   
     
     
         2 . The method of  claim 1 , wherein determining the “x” number comprises one or more of:
 receiving at least some favorable listing responses to a listing request for the set of encoded data slices, wherein a first favorable listing response of the at least some favorable listing response indicates a first storage unit the “x” number of storage units is storing a first encoded data slice of the “x” number of encoded data slices; 
 receiving the “x” number; and 
 obtaining the “x” number by performing a lookup in a lookup table. 
 
     
     
         3 . The method of  claim 2  further comprises:
 determining an additional encoded data slice of the set of encoded data slices is stored in another storage unit of the pillar width number of storage units, wherein a current “x” number of storage units does not include the other storage unit; and 
 updating the “x” number based on the additional encoded data slice. 
 
     
     
         4 . The method of  claim 1 , wherein the identifying one of the “z” number of encoded data slices comprises:
 identifying a storage unit of the “z” number of storage units that is mapped to store a respective encoded data slice of the “z” number of encoded data slices, wherein the identifying is based on one or more of: 
 determining the storage unit has been recently restored; 
 determining the storage unit has been recently upgraded; 
 determining the storage unit has not been used previously for the set of encoded data slices; and 
 determining the storage unit is within a performance range of other storage units in the “x” number of storage units; and 
 selecting the respective encoded data slice as the one of the “z” number of encoded data slices. 
 
     
     
         5 . The method of  claim 1 , wherein the constructing the one of the “z” number of encoded data slices comprises:
 retrieving the decode threshold number of encoded data slices; 
 dispersed storage error decoding the decode threshold number of encoded data slices to reconstruct the data segment; and 
 dispersed storage error encoding the reconstructed data segment to produce the one of the “z” number of encoded data slices. 
 
     
     
         6 . The method of  claim 5 , wherein the dispersed storage error encoding comprises:
 arranging the reconstructed data segment into a data matrix;   obtaining an encoding matrix;   selecting a row of the encoding matrix that corresponds to the one of the “z” number of encoded data slices; and   matrix multiplying the selected row of the encoding matrix with the data matrix to produce the one of the “z” number of encoded data slices.   
     
     
         7 . A computing device comprises:
 memory;   an interface; and   a processing module operable coupled to the interface and the memory, wherein the processing module is operable to:   determine whether an encoded data slice of “x” number of encoded data slices of a set of encoded data slices requires rebuilding, wherein:
 a data segment of a data object is dispersed storage error encoded to produce the set of encoded data slices, 
 the set of encoded data slices includes a pillar width number of encoded data slices, 
 the “x” number of encoded data slices is stored in “x” number of storage units of a pillar width number of storage units, 
 “x” is equal to or greater a write threshold number of encoded data slices of the set of encoded data slices and is less than the pillar width number, and 
 “z” number of encoded data slices corresponds to encoded data slices of the set of encoded data slices that are not currently stored in “z” number of storage units of the pillar width number of storage units, and 
 “z” is equal to the pillar width number minus “x”; and 
   when the encoded data slice requires rebuilding:
 identify one of the “z” number of encoded data slices of the set of encoded data slices to replace the encoded data slice; 
 construct the one of the “z” number of encoded data slices from a decode threshold number of encoded data slices of the “x” number of encoded data slices; and 
 send, via the interface, the one of the “z” number of encoded data slices to a corresponding storage unit of the “z” number of storage units. 
   
     
     
         8 . The computing device of  claim 7 , wherein the processing module is operable to determine the “x” number by one or more of:
 receiving, via the interface, at least some favorable listing responses to a listing request for the set of encoded data slices, wherein a first favorable listing response of the at least some favorable listing response indicates a first storage unit the “x” number of storage units is storing a first encoded data slice of the “x” number of encoded data slices; 
 receiving, via the interface, the “x” number; and 
 obtaining the “x” number by performing a lookup in a lookup table. 
 
     
     
         9 . The computing device of  claim 8 , wherein the processing module is further operable to:
 determining an additional encoded data slice of the set of encoded data slices is stored in another storage unit of the pillar width number of storage units, wherein a current “x” number of storage units does not include the other storage unit; and   updating the “x” number based on the additional encoded data slice.   
     
     
         10 . The computing device of  claim 7 , wherein the processing module is operable to identify the one of the “z” number of encoded data slices by:
 identifying a storage unit of the “z” number of storage units that is mapped to store a respective encoded data slice of the “z” number of encoded data slices, wherein the identifying is based on one or more of: 
 determining the storage unit has been recently restored; 
 determining the storage unit has been recently upgraded; 
 determining the storage unit has not been used previously for the set of encoded data slices; and 
 determining the storage unit is within a performance range of other storage units in the “x” number of storage units; and 
 selecting the respective encoded data slice as the one of the “z” number of encoded data slices. 
 
     
     
         11 . The computing device of  claim 7 , wherein the processing module is operable to construct the one of the “z” number of encoded data slices by:
 retrieving the decode threshold number of encoded data slices; 
 dispersed storage error decoding the decode threshold number of encoded data slices to reconstruct the data segment; and 
 dispersed storage error encoding the reconstructed data segment to produce the one of the “z” number of encoded data slices. 
 
     
     
         12 . The computing device of  claim 11 , wherein the processing modules is operable to perform the dispersed storage error encoding by:
 arranging the reconstructed data segment into a data matrix;   obtaining an encoding matrix;   selecting a row of the encoding matrix that corresponds to the one of the “z” number of encoded data slices; and   matrix multiplying the selected row of the encoding matrix with the data matrix to produce the one of the “z” number of encoded data slices.   
     
     
         13 . A computer readable storage device comprises:
 a first memory section for storing operational instructions that, when executed by a computing device of a dispersed storage network, causes the computing device to:   determine whether an encoded data slice of “x” number of encoded data slices of a set of encoded data slices requires rebuilding, wherein:
 a data segment of a data object is dispersed storage error encoded to produce the set of encoded data slices, 
 the set of encoded data slices includes a pillar width number of encoded data slices, 
 the “x” number of encoded data slices is stored in “x” number of storage units of a pillar width number of storage units, 
 “x” is equal to or greater a write threshold number of encoded data slices of the set of encoded data slices and is less than the pillar width number, and 
 “z” number of encoded data slices corresponds to encoded data slices of the set of encoded data slices that are not currently stored in “z” number of storage units of the pillar width number of storage units, and 
 “z” is equal to the pillar width number minus “x”; and 
   a second memory section for storing operational instructions that, when executed by the computing device, causes the computing device to:   when the encoded data slice requires rebuilding:
 identify one of the “z” number of encoded data slices of the set of encoded data slices to replace the encoded data slice; 
 construct the one of the “z” number of encoded data slices from a decode threshold number of encoded data slices of the “x” number of encoded data slices; and 
 send the one of the “z” number of encoded data slices to a corresponding storage unit of the “z” number of storage units. 
   
     
     
         14 . The computer readable storage device of  claim 13 , wherein the first memory section stores further operational instructions, that when executed by the computing device, causes the computing device to determine the “x” number by one or more of:
 receiving at least some favorable listing responses to a listing request for the set of encoded data slices, wherein a first favorable listing response of the at least some favorable listing response indicates a first storage unit the “x” number of storage units is storing a first encoded data slice of the “x” number of encoded data slices; 
 receiving the “x” number; and 
 obtaining the “x” number by performing a lookup in a lookup table. 
 
     
     
         15 . The computer readable storage device of  claim 14 , wherein the first memory section stores further operational instructions, that when executed by the computing device, causes the computing device to:
 determine an additional encoded data slice of the set of encoded data slices is stored in another storage unit of the pillar width number of storage units, wherein a current “x” number of storage units does not include the other storage unit; and   update the “x” number based on the additional encoded data slice.   
     
     
         16 . The computer readable storage device of  claim 13 , wherein the second memory section stores further operational instructions that, when executed by the computing device, causes the computing device to identify the one of the “z” number of encoded data slices by:
 identifying a storage unit of the “z” number of storage units that is mapped to store a respective encoded data slice of the “z” number of encoded data slices, wherein the identifying is based on one or more of:
 determining the storage unit has been recently restored; 
 determining the storage unit has been recently upgraded; 
 determining the storage unit has not been used previously for the set of encoded data slices; and 
 determining the storage unit is within a performance range of other storage units in the “x” number of storage units; and 
 
 selecting the respective encoded data slice as the one of the “z” number of encoded data slices. 
 
     
     
         17 . The computer readable storage device of  claim 13 , wherein the second memory section stores further operational instructions that, when executed by the computing device, causes the computing device to construct the one of the “z” number of encoded data slices by:
 retrieving the decode threshold number of encoded data slices; 
 dispersed storage error decoding the decode threshold number of encoded data slices to reconstruct the data segment; and 
 dispersed storage error encoding the reconstructed data segment to produce the one of the “z” number of encoded data slices. 
 
     
     
         18 . The computer readable storage device of  claim 17 , wherein the second memory section stores further operational instructions that, when executed by the computing device, causes the computing device to:
 arrange the reconstructed data segment into a data matrix;   obtain an encoding matrix;   select a row of the encoding matrix that corresponds to the one of the “z” number of encoded data slices; and   matrix multiply the selected row of the encoding matrix with the data matrix to produce the one of the “z” number of encoded data slices.