EXPANDING A DISPERSED STORAGE NETWORK MEMORY BEYOND TWO LOCATIONS

A method for a dispersed storage network includes generating expansion encoded data slices for identified expansion storage units of an expanded set of storage units. The method continues by relocating at least some of the expanded set of storage units to at least one other existing storage site associated with at least one other storage target and at least one new storage site associated with at least one storage target of a desired plurality of storage targets and relocating at least some storage units of the at least one other existing storage site to the existing storage site and to the at least one new storage site, facilitating population of the relocated at least some storage units of the at least one other existing storage site with corresponding encoded data slices and synchronizing, on an ongoing basis, storage of common data in each storage target.

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

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 devices12&16and 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 DSTN 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 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. 9is a schematic block diagram of another embodiment of a dispersed storage network (DSN)10that includes two or more storage targets portrayed in a series of expansion steps, where another storage target is created for association with the two or more storage targets of a starting step. Each storage target includes a plurality of storage units. Each storage unit may be implemented utilizing the dispersed storage and task (DST) execution (EX) unit36(storage unit) ofFIG. 1.

The DSN is operable to migrate stored data to facilitate expansion of the two or more storage targets. In an example of operation of the migrating of the stored data, the starting step portrays a storage target 1 implemented at a site A and a storage target 2 implemented at a site B. The storage target 1 initially includes storage units A1-A24and the storage target 2 initially includes storage units B1-B24. Sets of encoded data slices may be generated in accordance with an information dispersal algorithm (IDA), where an IDA width number of encoded data slices included in each set of encoded data slices and a decode threshold number of encoded data slices are required to recover a data segment that was dispersed storage error encoded to produce the set of encoded data slices. For example, a decode threshold of 20 may be associated with each storage target when the IDA width of 24 is utilized. As such, 24 slices are stored in at least 24 storage units of the storage targets 1 and 2 and at least 20 slices are recovered from storage units of the storage targets 1 and 2 to recover a data segment.

In the example of operation of the migrating of the stored data to facilitate the expansion of the two storage targets to three storage targets, in a first step of the expansion steps, the storage units B1-B24are inactivated to be temporarily dormant within the storage target 2. Having inactivated the storage units of the storage target 2, an expanded IDA width is selected. The selecting may be based on one or more of a predetermination, a desired number of storage units per storage target after the expansion of the storage targets, or a number of storage units present prior to the first step of the expansion steps. For example, an IDA width of 36 is selected to expand the 48 storage units to 60 storage units, where 20 storage units are implemented at each of three sites A, B, and C and at least a decode threshold number (e.g., decode threshold unchanged) of storage units are implemented at each of the sites (e.g., 20). For instance, 60−48=12 new storage units are required to provide storage for 12 additional encoded data slices per set of encoded data slices.

Having selected the expanded IDA width, the 12 new storage units are added to the storage target 1 such that storage target 1 temporarily includes the expanded IDA width number of storage units (e.g., 36). Having implemented the new storage units, expansion encoded data slices 25-36 are generated for each set of stored encoded data slices 1-24 and stored in the 12 new storage units. For instance, a DST client module34ofFIG. 1recovers, for each data segment, at least a decode threshold number of encoded data slices from storage units A1-A24, dispersed storage error decodes the recovered encoded data slices to reproduce a data segment, dispersed storage error encodes the reproduced data segment using an expanded encoding matrix to produce the expansion encoded data slices 25-36 for storage in the new storage units A25-A36.

In a second step of the expansion, the storage units at storage target 1 (e.g., storage units A1-A36) are equally divided amongst the three storage targets at the three sites for redeployment. For example, storage units A13-A24are physically moved to site B and become part of storage target 2 as storage units B13-B24and new storage units A25-A36are physically moved to site C and become part of storage target 3 as storage units C25-C36. Encoded data slices 25-36 are still stored within the storage units C25-C36.

Having redeployed the storage units from the storage target 1, the storage units from the storage target 2 are evenly redeployed amongst the three storage targets. For example, eight storage units are deployed at each of the three sites. For instance, storage units B1-B8are redeployed to storage target 1 and renamed as storage units A33-A36and storage units A13-A16such that storage target 1 now includes 20 storage units A33-A16. Having redeployed the storage units, encoded data slices are copied from corresponding storage units of the other storage targets to populate the redeployed storage units with a corresponding encoded data slices. For example, encoded data slices 33-36 are copied from storage units C33-C36at storage target 3 to populate storage units A33-A36. In a similar fashion, 8 storage units from the original storage units B1-B24are redeployed and populated with encoded data slices at storage target 2 and at storage target

While moving the storage units of the non-expanded site, the DSN may utilize the expanded set of storage units as a temporary common storage target (e.g., storage units A1-A36). Once all storage units have been redeployed and repopulated with encoded data slices, the three storage targets may perform eventual consistency synchronization operations to maintain at least a decode threshold number of encoded data slices of the storage targets as a first priority and to maintain further encoded data slices of most recent revisions as a second priority.

FIG. 9Ais a flowchart illustrating an example of migrating stored data. In particular, a method is presented for use in conjunction with one or more functions and features described in conjunction withFIGS. 1-2, 3-8, and alsoFIG. 9.

The method begins or continues at step476where a processing module (e.g., of a distributed storage and task (DST) client module) generates expansion encoded data slices for identified expansion storage units of an expanded set of storage units, where the expanded set of storage units further includes a set of storage units associated with a first storage target of an existing site. For example, for each set of existing stored encoded data slices, the processing module recovers a decode threshold number of slices, dispersed storage error decodes the recovered slices to reproduce a data segment, dispersed storage error encodes the data segment with an expanded encoding matrix to produce the expansion encoded data slices, and facilitate storage of the expansion encoded data slices in the identified expansion storage units.

The method continues at step478where the processing module relocates at least some of the expanded set of storage units to at least one other existing site associated with at least one other storage target and at least one new site associated with at least one storage target of a desired plurality of storage targets. For example, the processing module selects at least some of the expanded set of storage units (e.g., equally divides amongst the desired plurality of storage targets) and indicates the selection for re-location keeping stored encoded data slices intact.

The method continues at step480where the processing module relocates at least some storage units of the at least one other existing site to the existing site and to the at least one new site. For example, the processing module selects at least some of the storage units and indicates the selection for relocation.

The method continues at step482where the processing module facilitates population of the relocated at least some storage units of the at least one other existing site with corresponding encoded data slices. For example, the processing module rebuilds encoded data slices based on decoding at least a decode threshold number of encoded data slices per set of encoded data slices. As another example, the processing module copies encoded data slices from corresponding storage units of the expanded set of storage units.

The method continues at step484where, on an ongoing basis, the processing module synchronizes storage of common data in each of the plurality of storage targets. For example, the processing module maintains same revisions of encoded data slices stored in storage units of the plurality of storage targets.

The method described above in conjunction with the processing module can alternatively be performed by other modules of the dispersed storage network or by other computing devices. In addition, at least one memory section (e.g., 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 of the dispersed storage network (DSN), cause the one or more computing devices to perform any or all of the method steps described above.

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.