Source: https://patents.google.com/patent/US10073737B2/en
Timestamp: 2019-04-26 04:21:17+00:00

Document:
2017-08-28 Assigned to INTERNATIONAL BUSINESS MACHINES CORPORATION reassignment INTERNATIONAL BUSINESS MACHINES CORPORATION ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: RESCH, JASON K., GAJJAR, VIMALKUMAR P.
A method for execution by a dispersed storage and task (DST) client module includes obtaining a data identifier for slice location identification. A source name corresponding to the data identifier is identified. A plurality of data segments are identified based on the source name. A set of slice names are generated for each of the plurality of data segments. A set of DST execution units are identified based on the sets of slice names. A set of query requests are generated for each data segment for transmission to the set of DST execution units. Query responses are received from the set of DST execution units. A storage record is generated that includes storage location information of the query responses. Migration of at least some encoded data slices associated with the sets of slice names is facilitated when the storage record compares unfavorably to a storage record requirement.
The present U.S. Utility patent application claims priority pursuant to 35 U.S.C. § 120 as a continuation-in-part of U.S. Utility application Ser. No. 15/442,273, entitled “ROBUST RECEPTION OF DATA UTILIZING ENCODED DATA SLICES”, filed Feb. 24, 2017, which is a continuation of U.S. Utility application Ser. No. 13/959,262, entitled “ROBUST RECEPTION OF DATA UTILIZING ENCODED DATA SLICES”, filed Aug. 5, 2013, issued as U.S. Pat. No. 9,667,701 on May 30, 2017, which claims priority pursuant to 35 U.S.C. § 119(e) to U.S. Provisional Application No. 61/711,106, entitled “PRIORITIZING TASKS IN A DISTRIBUTED STORAGE AND TASK NETWORK”, filed Oct. 8, 2012, all of which are hereby incorporated herein by reference in their entirety and made part of the present U.S. Utility patent application for all purposes.
U.S. Utility application Ser. No. 13/959,262 also claims priority pursuant to 35 U.S.C. § 120 as a continuation-in-part of U.S. Utility application Ser. No. 12/816,126, entitled “ROBUST RECEPTION OF DATA UTILIZING ENCODED DATA SLICES”, filed Jun. 15, 2010, issued as U.S. Pat. No. 9,692,593 on Jun. 27, 2017, which claims priority pursuant to 35 U.S.C. § 119(e) to U.S. Provisional Application No. 61/256,411, entitled “DISTRIBUTED STORAGE NETWORK DATA PROCESSING”, filed Oct. 30, 2009.
U.S. Utility application Ser. No. 15/442,273 also claims priority pursuant to 35 U.S.C. § 120 as a continuation-in-part of U.S. Utility application Ser. No. 15/230,145, entitled “DISTRIBUTED STORAGE NETWORK AND METHOD FOR STORING AND RETRIEVING ENCRYPTION KEYS”, filed Aug. 5, 2016, which is a continuation of U.S. Utility application Ser. No. 14/292,727, entitled “DISTRIBUTED STORAGE NETWORK AND METHOD FOR STORING AND RETRIEVING ENCRYPTION KEYS”, filed May 30, 2014, issued as U.S. Pat. No. 9,413,529 on Aug. 9, 2016, which is a continuation-in-part of U.S. Utility application Ser. No. 13/736,848, entitled “DISTRIBUTED STORAGE NETWORK AND METHOD FOR ENCRYPTING AND DECRYPTING DATA USING HASH FUNCTIONS”, filed Jan. 8, 2013, issued as U.S. Pat. No. 9,009,491 on Apr. 14, 2015, which is a continuation of U.S. Utility application Ser. No. 12/814,467, entitled “DISTRIBUTED STORAGE NETWORK AND METHOD FOR ENCRYPTING AND DECRYPTING DATA USING HASH FUNCTIONS”, filed Jun. 13, 2010, issued as U.S. Pat. No. 8,351,600 on Jan. 8, 2013, which claims priority pursuant to 35 U.S.C. § 119(e) to U.S. Provisional Application No. 61/256,411, entitled “DISTRIBUTED STORAGE NETWORK DATA PROCESSING”, filed Oct. 30, 2009, all of which are hereby incorporated herein by reference in their entirety and made part of the present U.S. Utility patent application for all purposes.
FIG. 10 is a logic diagram of an example of a method of slice location identification in accordance with the present invention.
FIG. 9 is a schematic block diagram of another embodiment of a distributed computing system that includes a DS client module 34 of FIG. 1, the network 24 of FIG. 1, and a plurality of storage units 36 of FIG. 1. Some or all storage units 36 can utilized as DST execution units, operable to store dispersed error encoded data and/or to execute, in a distributed manner, one or more tasks on data as discussed herein. As used herein, storage units 36 will be interchangeably referred to as DST execution units. Each storage unit 36 of the plurality of storage units 36 can include a controller 952 and a plurality of memory devices 1-k. The plurality of memory devices function to store encoded data slices, and each storage unit 36 can include the same or different number of memory devices. Some or all of the memory devices can be implemented by utilizing main memory 54 of computing core 26 of FIG. 2, or another memory device that operable to store encoded data slices. The controller can be implemented by utilizing computing core 26 of FIG. 2, for example, by utilizing memory controller 52, and/or can be implemented by utilizing a processing device or other computing component that includes a processor operable to be utilized as a controller for storing encoded data slices in memory devices. While the DS client module 34 depicted in FIG. 9 communicates directly with the DST execution units via network 24, the DS client module 34 can be a DS client module of a computing device 12 or 16 of FIG. 1, or of another computing component of the DSN that communicates with the DST execution units. For example, a DS client module 34 of a computing device 16 can communicate with the DST execution units via network 24 by utilizing interface 32 of the computing device 16, as illustrated in FIG. 1. The DS client module can include a processor and memory, and, as illustrated in FIG. 1, can utilize some or all of the elements of computing core 26 of FIG. 2, such as the processing module 50 of FIG. 2 and/or the main memory 54 of FIG. 2. The dispersed storage client module 34 can be utilized as a dispersed storage and task (DST) client module, operable to enable the corresponding computing device to disperse storage error encode and decode data and/or to facilitate execution of one or more tasks on data in a dispersed manner, for example, by utilizing the DST execution units. The system functions to verify utilization of storage capacity of the plurality of DST execution units with regards to storage of encoded data slices.
The DS client module 34 can identify a file for storage analysis. The identifying can be based on one or more of receiving a request, a predetermination, a list, utilizing a round robin approach, identifying the file as a next file on a file list. The DS client module 34 generates a plurality of sets of slice names corresponding to a plurality of sets of encoded data slices stored in the plurality of DST execution units. The file is segmented to produce a plurality of segments. Each segment of the plurality of segments is encoded utilizing a dispersed storage error coding function to produce a set of encoded data slices. The generating of the plurality of sets of slice names can be based on one or more of a file identifier (ID) of the file, a vault ID corresponding to the file ID, and a registry lookup.
The DS client module 34 can identify a set of DST execution units of the plurality of DST execution units associated with storage of the plurality of sets of encoded data slices. The identifying can be based on one or more of receiving identifiers of the set of DST execution units, a registry lookup, and a distributed storage and task network (DSTN) virtual address to physical location table lookup.
For each DST execution unit of the set of DST execution units, the DS client module 34 can generate a plurality of query requests corresponding to the plurality of sets of encoded data slices. Each query request of the plurality of query requests includes a slice name corresponding to an encoded data slice of a set of encoded data slices stored in a memory device of the plurality of memory devices of the DST execution unit. The DS client module 34 outputs the query request to the DST execution unit, for example, by transmitting the query request via the network 24.
A corresponding controller of the DST execution unit can receive the query request and identifies the memory device of the plurality of memory devices that is utilized to store the encoded data slice. The DST execution unit generates a query response. The query response can include one or more of the slice name, storage location information which includes an identifier of the memory device, a length of time of storage indicator, a memory device age, and/or a memory device replacement schedule. The generating includes at least one of accessing a local table and retrieving information from the memory device. The DST execution unit can output the query response to the DS client module 34, for example, by transmitting the query response via the network 24.
For the set of encoded data slices, the DS client module 34 can receive a set of query responses from the set of DST execution units. The DS client module 34 facilitates a storage action based on the set of query responses. A first storage action can include generating a storage record that includes one or more of the file ID, a source name corresponding to the file ID, identity of the plurality of data segments, the plurality of sets of slice names, identity of the set of DST execution units, and/or the storage location information within each DST execution unit of the set of DST execution units. A second storage action can include migrating at least some encoded data slices of the plurality of sets of encoded data slices when the storage record compares unfavorably to a storage record requirement, which can include a desired storage record, for example, determined by the system or set by the system, a fixed storage record threshold, and/or a set of requirements. For example, the DS client module 34 can detect an imbalance based on the comparison and indicates to migrate the at least some encoded data slices. This method to verify storage utilization is discussed in greater detail with reference to FIG. 10.
In some embodiments, for a file already stored, the DS client module 34 can generate slice names, for example, based on a directory lookup of corresponding source names, for all segments. This can be used to identify the corresponding DST execution units. The DS client module 34 can generate query requests to verify storage and/or to retrieve identifiers of memory devices of the DST execution units utilized to store the slices.
In various embodiments, a processing system of a dispersed storage and task (DST) client module includes at least one processor and a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to obtain a data identifier for slice location identification. A source name corresponding to the data identifier is identified. A plurality of data segments are identified based on the source name. A set of slice names of a plurality of sets of slice names are generated for each of the plurality of data segments. A set of DST execution units are identified based on the plurality of sets of slice names. A set of query requests are generated for each of the plurality of data segments that includes a corresponding set of slice names of the plurality of sets of slice names. The set of query requests are transmitted to the set of DST execution units. A plurality of sets of query responses are received from the set of DST execution units. A storage record is generated that includes the data identifier, the source name, identity of the plurality of data segments, the plurality of sets of slice names, identity of the set of DST execution units, and/or storage location information of the plurality of sets of query responses. Migration of at least some encoded data slices associated with the plurality of sets of slice names is facilitated when the storage record compares unfavorably to a storage record requirement.
In various embodiments, obtaining the data identifier includes receiving the data identifier via a network, initiating a query, extracting the data identifier from an error message, and/or receiving a user request that includes the data identifier. In various embodiments, identifying the source name is based on a directory lookup utilizing the data identifier to extract the source name from a directory. In various embodiments, identifying the plurality of data segments includes extracting identities from a segment allocation table associated with the source name and/or extracting from a first retrieved data segment associated with the source name.
In various embodiments each slice name of each set of slice names of the plurality of sets of slice names includes the source name and a segment number in accordance with the plurality of data segments. In various embodiments, each slice name of each set of slice names of the plurality of sets of slice names includes a pillar index based on a vault affiliated with the plurality of data segments.
In various embodiments, identifying the set of DST execution units includes accessing a table that includes a mapping of slice names to a plurality of physical locations and further includes determining a set of physical locations of the plurality of physical locations for each set of slice names based on the table. The set of DST execution units are identified based on the set of physical locations corresponding to each set of slice names.
In various embodiments, information of the storage record is graphically displayed on a display device associated with the DST client module. In various embodiments, facilitating the migration includes identifying the at least some encoded data slices based on the comparison of the storage record to the storage record requirement. In various embodiments, the at least some encoded data slices are identified when a memory device identifier of the storage location information of the at least some encoded data slices is associated with an unfavorable reliability level.
FIG. 10 is a flowchart illustrating an example of verifying storage utilization. In particular, a method is presented for use in association with one or more functions and features described in conjunction with FIGS. 1-9, for execution by a dispersed storage (DS) client module, for example, being utilized as a DST client module, that includes a processor or via another processing system of a dispersed storage network that includes at least one processor and memory that stores instruction that configure the processor or processors to perform the steps described below.
The method begins with the step 1002 where a processing module (e.g., of a distributed storage (DS) client module) obtains a data identifier (ID) for slice location identification. The obtaining includes at least one of receiving the data identifier, for example, via the network, initiating a query, extracting the data identifier from an error message, and/or receiving a user request, for example, that includes the data identifier. The method continues at step 1004 where the processing module identifies a source name (e.g., a virtual distributed storage and task network (DSTN) address) corresponding to the data ID. The identifying may be based on a directory lookup utilizing the data ID to extract the source name from a directory of the dispersed storage network. The method continues at step 1006 where the processing module identifies a plurality of data segments based on the source name. The identifying includes at least one of extracting identities from a segment allocation table associated with the source name and extracting from a first retrieved data segment associated with the source name.
For each data segment of the plurality of data segments, the method continues at step 1008, where the processing module generates a set of slice names of a plurality of sets of slice names. Each slice name of the set of slice names includes the source name and a segment number in accordance with the plurality of data segments. Each slice name can further include a pillar index based on a vault affiliated with the data. The method continues at step 1010, where the processing module identified as a set of DST execution units based on the plurality of sets of slice names. The identifying includes accessing table mapping slice names to physical locations utilizing the set of slice names to determine the corresponding physical locations.
For each data segment of the plurality of data segments, the method continues at step 1012, where the processing module generates a set of query requests that includes a corresponding set of slice names of the plurality of sets of slice names and/or each request can include a memory identifier indicating where the corresponding slice is stored. For each data segment, the method continues at step 1014, where the processing module sends the set of query requests to the set of DST execution units, for example, via a network. The method continues at step 1016, where the processing module receives a plurality of sets of query requests, for example, via the network. The method continues at step 1018, where the processing module generates a storage record that includes the data identifier, the source name, identity of the plurality of data segments, the plurality of sets of slice names, identity of the set of DST execution units, and/or storage location information of the plurality of sets of query responses. Alternatively, or in addition, the processing module can graphically display information of the storage record.
The method continues at step 1020, where the processing module facilitates migration of at least some encoded data slices associated with the plurality sets of slice names when the storage record compares unfavorably to a storage record requirement, which can include a desired storage record, for example, determined by the system or set by the system, a fixed storage record threshold, and/or a set of requirements. The facilitating includes identifying the at least some encoded data slices based on the comparison. For example, a processing module identifies the at least some encoded data slices to migrate when a memory device identifier of the storage location information is associated with an unfavorable reliability level.
In various embodiments, a non-transitory computer readable storage medium includes at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to obtain a data identifier for slice location identification. A source name corresponding to the data identifier is identified. A plurality of data segments are identified based on the source name. A set of slice names of a plurality of sets of slice names are generated for each of the plurality of data segments. A set of DST execution units are identified based on the plurality of sets of slice names. A set of query requests are generated for each of the plurality of data segments that includes a corresponding set of slice names of the plurality of sets of slice names. The set of query requests are transmitted to the set of DST execution units. A plurality of sets of query responses are received from the set of DST execution units. A storage record is generated that includes the data identifier, the source name, identity of the plurality of data segments, the plurality of sets of slice names, identity of the set of DST execution units, and/or storage location information of the plurality of sets of query responses. Migration of at least some encoded data slices associated with the plurality of sets of slice names is facilitated when the storage record compares unfavorably to a storage record requirement.
wherein the at least some encoded data slices are identified when a memory device identifier of the storage location information of the at least some encoded data slices is associated with an unfavorable reliability level.
2. The method of claim 1, wherein obtaining the data identifier includes at least one of: receiving the data identifier via a network, initiating a query, extracting the data identifier from an error message, or receiving a user request that includes the data identifier.
3. The method of claim 1, wherein identifying the source name is based on a directory lookup utilizing the data identifier to extract the source name from a directory.
4. The method of claim 1, wherein identifying the plurality of data segments includes at least one of: extracting identities from a segment allocation table associated with the source name or extracting from a first retrieved data segment associated with the source name.
5. The method of claim 1, wherein each slice name of each set of slice names of the plurality of sets of slice names includes the source name and a segment number in accordance with the plurality of data segments.
6. The method of claim 1, wherein each slice name of each set of slice names of the plurality of sets of slice names includes a pillar index based on a vault affiliated with the plurality of data segments.
7. The method of claim 1, wherein identifying the set of DST execution units includes accessing a table that includes a mapping of slice names to a plurality of physical locations and further includes determining a set of physical locations of the plurality of physical locations for each set of slice names based on the table, and wherein the set of DST execution units are identified based on the set of physical locations corresponding to each set of slice names.
8. The method of claim 1, wherein information of the storage record is graphically displayed on a display device associated with the DST client module.
the at least some encoded data slices are identified when a memory device identifier of the storage location information of the at least some encoded data slices is associated with an unfavorable reliability level.
10. The processing system of claim 9, wherein obtaining the data identifier includes at least one of: receiving the data identifier via a network, initiating a query, extracting the data identifier from an error message, or receiving a user request that includes the data identifier.
11. The processing system of claim 9, wherein identifying the source name is based on a directory lookup utilizing the data identifier to extract the source name from a directory.
12. The processing system of claim 9, wherein identifying the plurality of data segments includes at least one of: extracting identities from a segment allocation table associated with the source name or extracting from a first retrieved data segment associated with the source name.
13. The processing system of claim 9, wherein each slice name of each set of slice names of the plurality of sets of slice names includes the source name and a segment number in accordance with the plurality of data segments.
14. The processing system of claim 9, wherein each slice name of each set of slice names of the plurality of sets of slice names includes a pillar index based on a vault affiliated with the plurality of data segments.
15. The processing system of claim 9, wherein identifying the set of DST execution units includes accessing a table that includes a mapping of slice names to a plurality of physical locations and further includes determining a set of physical locations of the plurality of physical locations for each set of slice names based on the table, and wherein the set of DST execution units are identified based on the set of physical locations corresponding to each set of slice names.
Yu et al., "A highly efficient, low delay architecture for transporting H.264 video over wireless channel", Image Communication 19 (2004), pp. 369-385, Elsevier Publishing.

References: § 120
 § 119
 Application No. 61
 § 120
 § 119
 Application No. 61
 § 120
 § 119
 Application No. 61