Storing data and associated metadata in a dispersed storage network

A method begins by a processing module generating metadata for a data object. The method continues by a first disperse storage error encoding the metadata to produce a set of metadata slices. The method continues by partitioning the data to produce a plurality of data segments. The method continues by a second disperse storage error encoding the plurality of data segments to produce a plurality of sets of encoded data slices. The method continues by applying a distributed agreement protocol function to a data object identifier for the data object to produce ranked scoring information with regards to a plurality of storage sets. The method continues by selecting a storage set of the plurality of storage sets based on the ranked scoring information. The method continues by facilitating storage of the set of metadata slices and the plurality of sets of encoded data slices in the selected storage set.

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

Large distributed storage sets may incur delay when retrieving, for example video. Reducing these delays can improve immediacy of stored data access and subsequent interaction with the retrieved data (e.g., playback of the video).

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-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.

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 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.

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 an embodiment of metadata dispersed storage. Embedded Objects are metadata objects which have the entirety of the content of the object stored together within metadata in the same segment (data source). They save one RTT (round trip time-time for a small packet to travel from client to server and back; also known as response time) and one IO (input/output), and hence are especially useful for storing small objects. Traditionally, embedded objects have been reserved only for small objects, since all metadata was stored in a deterministic location in generation 0. Since a DAP (distributed agreement protocol) adds expandability to generation 0, there is no longer a reason to not store all objects as embedded objects, and so all objects, regardless of size, may be stored with the metadata object containing some part of the object data. This can amortize the time to first byte (TTFB), since some fixed quantity of data (e.g., 250 KB) of the object may be contained in the metadata itself. Further, by making the amount of data kept in the metadata header small, it further reduces the RTT for very small objects (e.g., not having to read an entire 4 MB segment before accessing the first byte).

To further maximize IO capability, the first segment may not use the same IDA (information dispersal algorithm) threshold, but may use a reduced threshold, or even a threshold of “1”, such that reads of small objects or of metadata consume only one IOP (Input/Output Operations Per Second) rather than an IDA (information dispersal algorithms) threshold number of IOPs across the DSN memory. This strategy thereby minimizes TTFB for small objects because an embedded metadata segment is smaller, it minimizes TTFB by not requiring two round trips to access the content for larger objects, and increases IOPS for accessing single-segment small objects by using a reduced threshold.

FIG. 9includes the distributed storage and task (DST) processing unit16ofFIG. 1, the network24ofFIG. 1, and at least two storage sets 1-2. Alternatively, the DSN may include more than two storage sets. The DST processing unit16includes a processing module84, a dispersed storage (DS) error encoding 1, a grouping selector114, a DS error encoding 2, and a data partition110. Each storage set includes a set of DST execution (EX) units 1-n. Each DST execution unit may be implemented utilizing the DST execution unit36ofFIG. 1. Hereafter, each DST execution unit may be interchangeably referred to as a storage unit and a storage set may be interchangeably referred to as a set of storage units. The DSN functions to store data and metadata associated with the data in at least one storage set of the at least two storage sets 1-2.

An example of operation of the storing of the data and the metadata, the processing module84generates metadata 1 (e.g., a data object size, access rights, a data type indicator, etc.) for a received data object 1.

The data partitioning110partitions the received data object 1 to produce data segments 1-S in accordance with a data segmentation approach (e.g., text and size, segment size ramping up, segment size ramping down), where a first segment includes fewer bytes than remaining segments (to keep the metadata slices small after the merge below).

For each remaining data segment, the DS error encoding 2 dispersed storage error encodes the remaining data segments to produce a set encoded data slices (DSLC) 1-n utilizing second parameters (e.g., 16/10 encoding). That is, the DS error encoding 2 dispersed storage error encodes each data segment to produce a set of encoded data slices 1-n (DSLC 1-n), of a plurality of S sets of encoded data slices, utilizing second dispersal parameters (e.g., IDA width of 16 and a decode threshold number of 10).

The grouping selector114facilitates storage of the set of metadata slices and the remaining sets of encoded data slices in the storage set. The grouping selector114obtains ranked scoring information 1 from a decentralized agreement module (not shown) for each of the at least two storage sets 1-2 based on an identifier (e.g., a source name) of the data object 1. For example, for each storage set, the decentralized agreement module performs a distributed agreement protocol function on the identifier of the data object 1 using the identifier of the storage set and a weighting factor associated with the storage set to produce a score of a plurality of scores of the ranked scoring information 1.

Having obtained the rank scoring information 1, the grouping selector114selects a storage set of the at least two storage sets 1-2 based on the rank scoring information 1. For example, the grouping selector114selects a storage set associated with a highest score the plurality of scores. For instance, the grouping selector114selects the storage set 1 when the storage set 1 is associated with the highest score of the plurality of scores.

Having selected the storage set, the grouping selector114facilitates storage of the set of metadata slices and the plurality of sets of encoded data slices in the selected storage set. For example, the grouping selector114sends, via the network24, the set of metadata slices 1-n (MSLC1-n) to the DST execution units 1-n for storage, sends, via the network24, a first set of encoded data slices (e.g., DSLC1-1, DSCL 2-1, etc. through DSLC n−1) to the DST execution units 1-n for storage, sends, via the network24, a second set of encoded data slices (e.g., DSLC1-2, DSCL 2-2, etc. through DSLC n−2) to the DST execution units 1-n for storage, etc.

As shown inFIG. 9A, subsequent accessing of any one of the metadata slices reproduces the metadata and at least a first portion of the data object. Having the metadata and first portion of the data can be very valuable, especially when the data is video and the 1st portion can start an output video stream while the rest is read from the DSN. Therefore, instead of typical 16/10 coding this embodiment uses 1/1 coding on the metadata/slice 1 (encoder & decoder #1) so the video streaming output can start as soon as a first metadata slice is received. Retrieval is performed in reverse of operations and steps as shown inFIGS. 9 and 9B.

FIG. 9Bis a flowchart illustrating an example of metadata dispersed storage. In particular, a method is presented for use in conjunction with one or more functions and features described in conjunction withFIGS. 1-9A, and alsoFIG. 9B. The method begins at step900where a processing module (e.g., of a distributed storage and task (DST) processing unit) of a computing device of one or more computing devices of a dispersed storage network generates metadata for a data object. The generating includes analyzing one or more of the data object and a data object identifier of the data object to produce the metadata. The method continues at the step902where the processing module dispersed storage error encodes the metadata to produce a set of metadata slices. For example, the processing module dispersed storage error encodes the metadata utilizing first dispersal parameters to produce the set of metadata slices.

The method continues at step904, where the processing module partitions the data to produce a plurality of data segments. For the example, the processing module partitions the data in accordance with a data segmentation approach to produce the plurality of data segments. The method continues at step906where the processing module dispersed storage error encodes the plurality of data segments to produce a plurality of sets of encoded data slices. For example, the processing module dispersed storage error encodes each data segment utilizing second dispersal parameters to produce a set of encoded data slices of the plurality of sets of encoded data slices.

The method continues at step908where the processing module applies a distributed agreement protocol function to the data object identifier for the data object to produce ranked scoring information with regards to a plurality of storage sets. For example, for each storage set, the processing module performs the distributed agreement protocol function on the data object identifier using an identifier of the storage set and a weighting factor associated with the storage set to produce a score of a plurality of scores of the rank scoring information.

The method continues at step910where the processing module selects a storage set of the plurality of storage sets based on the ranked scoring information. For example, the processing module identifies a storage set associated with a highest score of the plurality of scores. The method continues at step912where the processing module facilitates storage of the set of metadata slices and the plurality of sets of encoded data slices in the selected storage set. For example, for each storage unit of the selected storage set, the processing module issues a write slice request to the storage unit, where the write slice request includes and associated metadata slice of the set of metadata slices and a plurality of associated encoded data slices of each set of encoded data slices (e.g., of a common pillar associated with the storage unit).

The method described above in conjunction with the computing device and the storage units can alternatively be performed by other modules of the dispersed storage network or by other devices. For example, any combination of a first module, a second module, a third module, a fourth module, etc. of the computing device 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.