US20110029809A1 - Method and apparatus for distributed storage integrity processing - Google Patents

Abstract

A distributed storage integrity system in a dispersed storage network includes a scanning agent and a control unit. The scanning agent identifies an encoded data slice that requires rebuilding, wherein the encoded data slice is one of a plurality of encoded data slices generated from a data segment using an error encoding dispersal function. The control unit retrieves at least a number T of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function. The control unit is operable to reconstruct the data segment from at least the number T of the encoded data slices and generate a rebuilt encoded data slice from the reconstructed data segment. The scanning agent is located in a storage unit and the control unit is located in the storage unit or in a storage integrity processing unit, a dispersed storage processing unit or a dispersed storage managing unit.

Description

CROSS-REFERENCE TO RELATED PATENTS
• This US patent application claims priority under 35 U.S.C. §119 to a provisionally filed patent application entitled, “DISPERSED STORAGE NETWORK DATA REBUILDING,” having a provisional filing date of Jul. 30, 2009, and a provisional Ser. No. of 61/230,034.
• This US patent application claims priority under 35 U.S.C. §120 as a continuation in part application to U.S. patent application Ser. No. 12/716,106, entitled, “METHOD AND APPARATUS FOR REBUILDING DATA IN A DISPERSED DATA STORAGE NETWORK,” and having a filing date of Mar. 2, 2010.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
• Not Applicable
INCORPORATION-BY-REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC
• Not Applicable
BACKGROUND OF THE INVENTION
• 1. Technical Field of the Invention
• This invention relates generally to computing systems and more particularly to data storage within such computing systems.
• 2. Description of Related Art
• Computing systems are known to communicate, process, and store data. Such computing systems range from wireless smart phones to data centers that support millions of web searches, stock trades, or on-line purchases every day. Computing processing is known to manipulate data from one form into another. For instance, raw picture data from an image sensor may be compressed and/or manipulated in accordance with a picture compression standard to produce a standardized compressed picture that can be saved or shared with others.
• With continued advances in computing processing speed and communication speed, computers manipulate real time media from voice to streaming high definition video. As such, general-purpose information appliances are replacing purpose-built communications devices (e.g., a telephone). For example, smart phones can support telephony communications but they are also capable of text messaging and accessing the internet to perform functions including email, web browsing, remote applications access, and media communications (e.g., telephony voice, image transfer, music files, video files, real time video streaming. etc.).
• Each type of computing system is constructed, and hence operates, in accordance with one or more communication, processing, and storage standards. As a result of standardization and with advances in technology, more and more information content is being converted into digital formats. For example, more digital cameras are now being sold than film cameras, thus producing more digital pictures. As another example, web-based programming is becoming an alternative to over the air television broadcasts and/or cable broadcasts. As further examples, papers, books, video entertainment, home video, etc. are now being stored digitally which increases the demand on the storage function of computing systems.
• A typical computer storage function includes one or more memory devices aligned with the needs of the various operational aspects of the computer system's processing and communication functions. Generally, the immediacy of access dictates what type of memory device is used. For example, random access memory (RAM) memory can be accessed in any random order with a constant response time, thus it is typically used for cache memory and main memory. By contrast, memory device technologies that require physical movement such as magnetic disks, tapes, and optical discs, have a variable response time as the physical movement can take longer than the data transfer, thus are typically used for secondary memory (e.g., hard drive, backup memory, etc.).
• Computer system storage standards include, but are not limited to, network file system (NFS), flash file system (FFS), disk file system (DFS), small computer system interface (SCSI), internet small computer system interface (iSCSI), file transfer protocol (FTP), and web-based distributed authoring and versioning (WebDAV). Such standards specify the data storage format (e.g., files, data objects, data blocks, directories, etc.) and interface between the computer system's processing function and the memory devices. Typically a memory controller provides the interface function between the processing function and the memory devices and will have to change as new storage systems are developed.
• Despite the standardization of the computer system and its memory, memory devices fail; especially commercial grade memory devices that utilize technologies incorporating physical movement (e.g., a disc drive). For example, it is fairly common for a disc drive to routinely suffer from bit level corruption and to completely fail after three years of use. One solution is to a higher-grade disc drive, which adds significant cost to the computing system.
• Another solution is to utilize multiple levels of redundant disc drives to replicate the data into two or more copies. One such redundant drive approach is called redundant array of independent discs (RAID). In a RAID device, a RAID controller adds parity data to the original data before storing it across the array. The parity data is calculated from the original data such that the failure of one or more discs will not result in the loss of the original data. For example,RAID 5 uses three discs to protect data from the failure of a single disc. The parity data, and associated redundancy overhead data, reduces the storage capacity of three independent discs by one third (e.g., n−1=capacity).RAID 6 can recover from a loss of two discs and requires a minimum of four discs with a storage capacity of n−2.
• While RAID addresses the memory device failure issue, it is not without its own failures issues that affect its effectiveness, efficiency and security. For instance, as more discs are added to the array, the probability of a disc failure increases, which increases the demand for maintenance. For example, when a disc fails, it needs to be manually replaced before another disc fails and the data stored in the RAID device is lost. To reduce the risk of data loss, data on a RAID device is typically copied on to one or more other RAID devices. While this addresses the loss of data issue, it raises a security issue since multiple copies of data are available, which increases the chances of unauthorized access. Further, as the amount of data being stored grows, the overhead of RAID devices becomes a non-trivial efficiency issue.
• Therefore, a need exists for a data storage solution that provides more reliable storage of data, minimizes adverse affects of multiple memory elements failures, provides improved security, is adaptable to a wide variety of storage system standards, and/or is compatible with computing and communications systems.
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS
• FIG. 1 is a schematic block diagram of an embodiment of a computing system for dispersed storage in accordance with the invention;
• FIG. 2 is a schematic block diagram of an embodiment of a computing core in accordance with the invention;
• FIG. 3 is a schematic block diagram of an embodiment of a storage integrity processing unit in accordance with the invention;
• FIG. 4 is a schematic block diagram of an embodiment of a grid module in accordance with the invention;
• FIG. 5 is a diagram of an example embodiment of error coded data slice creation in accordance with the invention;
• FIG. 6 is a diagram of an example embodiment of a distributed storage (DS) processing unit in accordance with the invention;
• FIG. 7 is a schematic block diagram of an embodiment of a file system hierarchy in accordance with the invention;
• FIG. 8 is a schematic block diagram of an embodiment of a method for data rebuilding in accordance with the present invention;
• FIG. 9 is a logic flow diagram of an embodiment of a method for data rebuilding in accordance with the present invention;
• FIG. 10 is a logic flow diagram of another embodiment of a method for data rebuilding in accordance with the present invention;
• FIG. 11 is a logic flow diagram of another embodiment of a method for data rebuilding in accordance with the present invention;
• FIG. 12 is a logic flow diagram of another embodiment of a method for data rebuilding in accordance with the present invention;
• FIG. 13 is a schematic block diagram of another embodiment of a grid module in accordance with the invention;
• FIG. 14 is a logic flow diagram of another embodiment for data rebuilding in accordance with the present invention;
• FIG. 15 is a schematic block diagram of an embodiment of a control unit in accordance with the invention;
• FIG. 16 is a logic flow diagram of an embodiment of a method for scanning in accordance with the present invention;
• FIG. 17 is a logic flow diagram of another embodiment of a method for scanning in accordance with the present invention;
• FIG. 18 is a logic flow diagram of another embodiment of a method for scanning in accordance with the present invention;
• FIG. 19 is a logic flow diagram of another embodiment of a method for scanning in accordance with the present invention;
• FIG. 20 is a logic flow diagram of another embodiment for data rebuilding in accordance with the present invention;
• FIG. 21 is a logic flow diagram of another embodiment for data rebuilding in accordance with the present invention;
• FIG. 22ais a schematic block diagram of another embodiment of a distributed control unit in accordance with the invention;
• FIG. 22bis a schematic block diagram of another embodiment of a distributed control unit in accordance with the invention;
• FIG. 23 is a schematic block diagram of another embodiment of a distributed storage network in accordance with the invention;
• FIG. 24 is a diagram of an embodiment of a distributed storage memory mapping in accordance with the invention;
• FIG. 25 is a schematic block diagram of another embodiment of a distributed storage network in accordance with the invention;
• FIG. 26 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 27 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 28 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 29 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 30 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 31 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention;
• FIG. 32 is a schematic block diagram of another embodiment of data rebuilding in accordance with the invention; and
• FIG. 33 is a logic flow diagram of another embodiment for data rebuilding in accordance with the present invention.
DETAILED DESCRIPTION OF THE INVENTION
• FIG. 1 is a schematic block diagram of acomputing system10 for dispersed storage that includes one or more of a first type ofuser devices12, one or more of a second type of user device14, at least one distributed storage (DS)processing unit16, at least oneDS managing unit18, at least one storageintegrity processing unit20, and a distributed storage network (DSN)memory22 coupled via anetwork24. Thenetwork24 may include one or more wireless and/or wire lined communication systems; one or more private intranet systems and/or public internet systems; and/or one or more local area networks (LAN) and/or wide area networks (WAN).
• TheDSN memory22 includes a plurality ofDS storage units36 for storing data of in thecomputing system10. Each of theDS storage units36 includes a processing module and memory and may be located at geographically different sites (e.g., one in Chicago, one in Milwaukee, etc.). The processing module may be a single processing device or a plurality of processing devices. Such a processing device may be a microprocessor, micro-controller, digital signal processor, microcomputer, central processing unit, field programmable gate array, programmable logic device, state machine, logic circuitry, analog circuitry, digital circuitry, and/or any device that manipulates signals (analog and/or digital) based on hard coding of the circuitry and/or operational instructions. The processing module may have an associated memory and/or memory element, which may be a single memory device, a plurality of memory devices, and/or embedded circuitry of the processing module. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, cache memory, and/or any device that stores digital information. Note that if the processing module includes more than one processing device, the processing devices may be centrally located (e.g., directly coupled together via a wired and/or wireless bus structure) or may be distributedly located (e.g., cloud computing via indirect coupling via a local area network and/or a wide area network). Further note that when the processing module implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory and/or memory element storing the corresponding operational instructions may be embedded within, or external to, the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry. Still further note that, the memory element stores, and the processing module executes, hard coded and/or operational instructions corresponding to at least some of the steps and/or functions illustrated inFIGS. 1-24.
• Each of theuser devices12,14, theDS processing unit16, theDS managing unit18, and the storageintegrity processing unit20 may be a portable computing device (e.g., a social networking device, a gaming device, a cell phone, a smart phone, a personal digital assistant, a digital music player, a digital video player, a laptop computer, a handheld computer, a video game controller, and/or any other portable device that includes a computing core) and/or a fixed computing device (e.g., a personal computer, 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). Such a portable or fixed computing device includes acomputing core26 and one ormore interfaces30,32, and/or33. An embodiment of thecomputing core26 will be described with reference toFIG. 2.
• With respect to the interfaces, each of theinterfaces30,32, and33 includes software and/or hardware to support one or more communication links via thenetwork24 and/or directly. For example, interfaces30 support a communication link (wired, wireless, direct, via a LAN, via thenetwork24, etc.) between the first type of user device14 and theDS processing unit16. As another example,DSN interface32 supports a plurality of communication links via thenetwork24 between theDSN memory22 and theDS processing unit16, the first type ofuser device12, and/or the storageintegrity processing unit20. As yet another example,interface33 supports a communication link between theDS managing unit18 and any one of the other devices and/orunits12,14,16,20, and/or22 via thenetwork24.
• In general, thecomputing system10 supports three primary functions: distributed network data storage management, distributed data storage and retrieval, and data storage integrity verification. In accordance with these three primary functions, data can be distributedly stored in a plurality of physically different locations and subsequently retrieved in a reliable and secure manner despite failures of individual storage devices, failures of network equipment, the duration of storage, the amount of data being stored, unauthorized attempts to access the data, etc.
• TheDS managing unit18 performs the distributed network data storage management functions, which include establishing distributed data storage parameters, performing network operations, performing network administration, and/or performing network maintenance. TheDS managing unit18 establishes the distributed data storage parameters (e.g., allocation of virtual DSN memory space, distributed storage parameters, security parameters, billing information, user profile information, etc.) for one or more of the user devices12-14 (e.g., established for individual devices, established for a user group of devices, established for public access by the user devices, etc.). For example, theDS managing unit18 coordinates the creation of a vault (e.g., a virtual memory block) within theDSN memory22 for a user device (for a group of devices, or for public access). TheDS managing unit18 also determines the distributed data storage parameters for the vault. In particular, theDS managing unit18 determines a number of slices (e.g., the number that a data segment of a data file and/or data block is partitioned into for distributed storage) and a threshold value (e.g., the minimum number of slices required to reconstruct the data segment).
• As another example, theDS managing module18 may create and store locally or within theDSN memory22 user profile information. The user profile information includes one or more of authentication information, permissions, and/or the security parameters. The security parameters may include one or more of encryption/decryption scheme, one or more encryption keys, key generation scheme, and data encoding/decoding scheme.
• As yet another example, theDS managing unit18 may create billing information for a particular user, user group, vault access, public vault access, etc. For instance, theDS managing unit18 may track the number of times user accesses a private vault and/or public vaults, which can be used to generate a per-access bill. In another instance, theDS managing unit18 tracks the amount of data stored and/or retrieved by a user device and/or a user group, which can be used to generate a per-data-amount bill.
• TheDS managing unit18 also performs network operations, network administration, and/or network maintenance. As at least part of performing the network operations and/or administration, theDS managing unit18 monitors performance of the devices and/or units of thesystem10 for potential failures, determines the devices and/or unit's activation status, determines the devices' and/or units' loading, and any other system level operation that affects the performance level of thesystem10. For example, theDS managing unit18 may receive and aggregate network management alarms, alerts, errors, status information, performance information, and messages from the devices12-14 and/or theDS processing unit16, storageintegrity processing unit20 andDSN memory22. For example, theDS managing unit18 may receive a simple network management protocol (SNMP) message regarding the status of theDS processing unit16.
• TheDS managing unit18 performs the network maintenance by identifying equipment within thecomputing system10 that needs replacing, upgrading, repairing, and/or expanding. For example, theDS managing unit18 may determine that theDSN memory22 requires moreDS storage units36 or that one or more of theDS storage units36 needs updating.
• The second primary function of distributed data storage and retrieval function involves a user device12-14. For instance, when a second type of user device14 has adata file38 and/or data block40 to store in theDSN memory22, it sends the data file38 and/or data block40 to theDS processing unit16 via itsinterface30. As will be described in greater detail with reference toFIG. 2, theinterface30 functions to mimic a conventional operating system (OS) file system interface (e.g., network file system (NFS), flash file system (FFS), disk file system (DFS), file transfer protocol (FTP), web-based distributed authoring and versioning (WebDAV), etc.) and/or a block memory interface (e.g., small computer system interface (SCSI), internet small computer system interface (iSCSI), etc.). In addition, theinterface30 may attach a user identification code (ID) to the data file38 and/or data block40.
• TheDS processing unit16 receives the data file38 and/or data block40 via itsinterface30 and performs a distributed storage (DS) process thereon. TheDS processing34 begins by partitioning the data file38 and/or data block40 into one or more data segments, which is represented as Y data segments. For example, theDS processing34 may partition the data file38 and/or data block40 into a fixed byte size segment (e.g., 21 to 2n bytes, where n=>2) or a variable byte size segment (e.g., change byte size from segment to segment, or from groups of segments to groups of segments, etc.).
• For each of the Y data segments, theDS processing34 error encodes (e.g., forward error correction (FEC), information dispersal algorithm, erasure coding, or error correction coding) and slices (or slices then error encodes) the data segment into a plurality of error coded (EC) data slices42-48, which is represented as X slices per data segment. The number of slices (X) per data segment, which corresponds to a number of pillars n, is set in accordance with the distributed data storage parameters and the error coding scheme. For example, if a Reed-Solomon (or other FEC scheme) is used in an X/T system, then a data segment Y is divided into X slices, where T number of slices is needed to reconstruct the original data segment (i.e., T is the threshold). As a few specific examples, the X/T factor may be 5/3; 6/4; 8/6; 8/5; 16/10.
• For each data slice42-48, theDS processing unit16 creates a unique slice name and appends it to the corresponding slice42-48. The slice name includes universal DSN memory addressing routing information (e.g., virtual memory addresses in the DSN memory22) and user-specific information (e.g., user ID, file name, data block identifier, etc.).
• TheDS processing unit16 transmits the plurality of EC data slices42-48 to a plurality ofDS units36 of theDSN memory22 via theDSN interface32 and thenetwork24. TheDSN interface32 formats each of the slices for transmission via thenetwork24. For example, theDSN interface32 may utilize an internet protocol (e.g., TCP/IP, etc.) to packetize the slices42-48 for transmission via thenetwork24.
• The number ofDS units36 receiving the slices42-48 is dependent on the distributed data storage parameters established by theDS managing unit18. For example, theDS managing unit18 may indicate that each slice is to be stored in a differentDS storage unit36. As another example, theDS managing unit18 may indicate that like slice numbers of different data segments are to be stored in the sameDS storage unit36. For example, the first slice of each of the data segments is to be stored in a firstDS storage unit36, the second slice of each of the data segments is to be stored in a secondDS storage unit36, etc. In this manner, the data is encoded and distributedly stored at physically diverse locations to improve data storage integrity and security. Further examples of encoding the data segments will be provided with reference to one or more ofFIGS. 2-24.
• EachDS storage unit36 that receives a slice42-48 for storage translates the virtual DSN memory address of the slice into a local physical address for storage. Accordingly, eachDS storage unit36 maintains a virtual to physical memory mapping to assist in the storage and retrieval of data.
• The first type ofuser device12 performs a similar function to store data in theDSN memory22 with the exception that it includesDS processing34. As such, theuser device12 encodes and slices the data file38 and/or data block40 for storage. Theuser device12 then transmits theslices35 to theDSN memory22 via itsDSN interface32 and thenetwork24.
• For a second type of user device14 to retrieve a data file or data block from memory, it issues a read command via itsinterface30 to theDS processing unit16. TheDS processing unit16 performs theDS processing34 to identify theDS storage units36 storing the slices of the data file38 and/or data block40 based on the read command. TheDS processing unit16 may also communicate with theDS managing unit18 to verify that the user device14 is authorized to access the requested data.
• When the user device is authorized to access the requested data, theDS processing unit16 issues slice read commands to at least a threshold number of theDS storage units36 storing the requested data (e.g., to at least 10 DS units for a 16/10 error coding scheme). Each of theDS storage units36 receiving the slice read command, verifies the command, accesses its virtual to physical memory mapping, retrieves the requested slice, or slices, and transmits it to theDS processing unit16.
• Once theDS processing unit16 has received a threshold number T of slices for a data segment, it performs an error decoding function and de-slicing to reconstruct the data segment. When Y number of data segments have been reconstructed, theDS processing unit16 provides the data file38 and/or data block40 to the user device14. Note that the first type ofuser device12 performs a similar process to retrieve adata file38 and/or data block40.
• The storageintegrity processing unit20 performs the third primary function of data storage integrity verification. In one instance, the storageintegrity processing unit20 periodically retrievesslices45 of a data file or data block of auser device12,14 to verify that one or more slices has not been corrupted or lost (e.g., aDS storage unit36 failed). The retrieval process mimics the read process previously described. In another instance, the storageintegrity processing unit20 periodically retrieves integrity data of theslices45 from the appropriateDS storage units36. The storageintegrity processing unit20 interprets the integrity data to determine if one or more of the slices has a data error or inconsistency (e.g., is corrupted, out-of-date, missing, etc.).
• If the storageintegrity processing unit20 determines that one or more slices has an associated error, it rebuilds the corrupted or lost slice(s) in accordance with the error coding scheme. The storageintegrity processing unit20 stores the rebuilt slice, or slices, in the appropriate DS storage unit(s)36 in a manner that mimics the write process previously described.
• While theDS processing unit16, theDS managing unit18, and the storageintegrity processing unit20 are shown as separate units, they may be functional units within one or more other components of thecomputing system10. For example, the storageintegrity processing unit20 may be a distributed function contained with two or more of theDS units36; may be a single unit within one of theDS units36; may be within theDS managing unit18; may be distributed within user devices (e.g., user devices12) to verify the data of the corresponding user; and/or may be within theDS processing unit16.
• FIG. 2 is a schematic block diagram of an embodiment of acomputing core26 that includes aprocessing module50, amemory controller52,main memory54, a videographics processing unit55, an input/output (IO)controller56, a peripheral component interconnect (PCI)interface58, at least one IOdevice interface module62, a read only memory (ROM) basic input output system (BIOS)64, and one or more memory interface modules. The memory interface module(s) includes one or more of a universal serial bus (USB) interface module66, a host bus adapter (HBA)interface module68, anetwork interface module70, aflash interface module72, a harddrive interface module74, and aDSN interface module76. Note theDSN interface module76 and/or thenetwork interface module70 may function as theinterface30 of the user device14 ofFIG. 1. Further note that the IOdevice interface module62 and/or the memory interface modules may be collectively or individually referred to as IO ports.
• Theprocessing module50 may be a single processing device or a plurality of processing devices. Such a processing device may be a microprocessor, micro-controller, digital signal processor, microcomputer, central processing unit, field programmable gate array, programmable logic device, state machine, logic circuitry, analog circuitry, digital circuitry, and/or any device that manipulates signals (analog and/or digital) based on hard coding of the circuitry and/or operational instructions. The processing module may have an associated memory and/or memory element, which may be a single memory device, a plurality of memory devices, and/or embedded circuitry of the processing module. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, cache memory, and/or any device that stores digital information. Note that if the processing module includes more than one processing device, the processing devices may be centrally located (e.g., directly coupled together via a wired and/or wireless bus structure) or may be distributedly located (e.g., cloud computing via indirect coupling via a local area network and/or a wide area network). Further note that when the processing module implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory and/or memory element storing the corresponding operational instructions may be embedded within, or external to, the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry. Still further note that, the memory element stores, and the processing module executes, hard coded and/or operational instructions corresponding to at least some of the steps and/or functions illustrated inFIGS. 1-24.
• FIG. 3 is a schematic block diagram of an embodiment of a storageintegrity processing unit20 that includes aprocessing module50 incomputing core26 andDSnet interface32. Theprocessing module50 is configured to implement agrid module84. TheDSnet interface32 couples theprocessing module50 to a plurality ofDS storage units36 at one or more sites. In this example, six DS storage units (storing pillar0-pillar5) are located at three different sites; pillars0-1 are located atsite1, pillars2-3 are located atsite2, and pillars4-5 are located atsite3.
• In an example of operation, thegrid module84 receives integrity data regarding one or more pluralities of EC data slices from theDS storage units36. TheDS storage units36 may provide the integrity data in response to a scan request from thegrid module84 and/or at predetermined intervals. In this example, a plurality of data slices corresponds to a data segment. Note that the data segment may be of a fixed size (e.g., 1 MByte) or of a variable size and it may represent an entire, or portion of, adata file38 or data object40.
• Thegrid module84 evaluates the received integrity data, which may include a cyclic redundancy check (CRC), hash value, etc. of the naming information and/or of the data slices. When the evaluation of the received integrity data yields unfavorable results (e.g., one or more of the integrity data is not as expected; one of the slices names does not match the other slices names because update version is different; the naming information for one of the slices was not received; and/or the CRC of the naming information was not as expected), the integrity module requests naming information of one or more pluralities of data slices from the plurality ofDS storage units36. Note that the naming information includes at least a portion of a slice name, wherein the slice name includes a source name (which is described with reference to one or more subsequent figures). After receiving the naming information, thegrid module84 evaluates it to identify at least one data slice of the one or more of pluralities of data slices having an associated error (e.g., corrupt naming information, missing slice, out-of-date slice, etc.) to generate an identified data slice for rebuilding. In another embodiment, thegrid module84 receives a plurality of data slices from theDS storage units36 and evaluates the data slices to identify whether one or more of plurality of data slices has an associated error.
• Thegrid module84 rebuilds the identified data slice(s) having the associated data error. For instance, thegrid module84 may retrieve error coded data slices from the DS storage units and rebuild error coded data slices therefrom. Rebuilding of slices will be discussed in greater detail with reference toFIGS. 4 and 5.
• FIG. 4 is a schematic block diagram of an embodiment of agrid module84 that includes acontrol unit86, apre-data manipulator88, anencoder90, aslicer92, apost-data manipulator94, a pre-data de-manipulator96, a de-slicer98, adecoder100, and apost-data de-manipulator102. In another embodiment, thecontrol unit86 is partially or completely external to thegrid module84. For example, thecontrol unit86 may be part of the computing core at a remote location, part of auser device12,14, part of theDS managing unit18 or distributed amongst one or moreDS storage units36.
• Thecontrol unit86 assists and/or controls the other elements of thegrid module84 to determine operational parameters, such as the types of pre-data and post-data manipulation/de-manipulation to be applied to an incoming/outgoing data segments104, if any, the type of error encoding/decoding to apply to the (encoded)data segments106, and the slicing/de-slicing function. In addition, thecontrol unit86 may further create and maintain a DS storage memory mapping, status ofDS storage units36, performance history ofDS storage units36, capability ofDS storage units36, prioritization information for DS storage unit usage, and rebuilding criteria (e.g., when to rebuild, when to gather integrity information, etc.). Thecontrol unit86 may determine the operational parameters by combining parameters of the associated vault with other parameters, which will be discussed below.
• In an example of operation, thepre-data manipulator88 receives adata segment104 and a write instruction from an authorizeduser device12,14. Thecontrol unit86 or gateway module may assist thepre-data manipulator88 to determine the vault for the authorized user and thedata segment104. When enabled, thepre-data manipulator88 determines if pre-manipulation of thedata segment104 is required, and if so, what type of pre-manipulation. The determination may be based on one or more factors including a computing system-wide predetermination, a table lookup, vault parameters associated with the user identification, the type of data, security requirements, available DSN memory, performance requirements, and/or other metadata.
• Thepre-data manipulator88 manipulates thedata segment104 in accordance with the manipulation determination, which includes one or more of compression (e.g., Lempel-Ziv-Welch, Huffman, Golomb, fractal, wavelet, etc.), signatures (e.g., Digital Signature Algorithm (DSA), Elliptic Curve DSA, Secure Hash Algorithm, etc.), watermarking, tagging, encryption (e.g., Data Encryption Standard, Advanced Encryption Standard, etc.), adding metadata (e.g., time/date stamping, user information, file type, etc.), cyclic redundancy check (e.g., CRC32), and/or other manipulations to enhance the value of thedata segment104. Note that thepre-data de-manipulator102 performs the complementary functions of thepre-data manipulator88 when data is retrieved from theDSN memory22. Note that thepre-data manipulator88 and pre-data de-manipulator102 are bypassed when data is recovered and reconstructed in the rebuild path.
• Theencoder90 receives thedata segment104 from thepre-data manipulator88 and encodes thedata segment104 using a forward error correction (FEC) encoding algorithm to produce the encodeddata segment106. Theencoder90 determines what type of encoding algorithm to use based on factors including predetermination in the vault for this user and/ordata segment104, a time based algorithm, user directed, DS managing unit directed, as a function of the data type, as a function of the data segment metadata, and/or any other factor to determine algorithm type. Theencoder90 may utilize a different encoding algorithm for eachdata segment104, or the same encoding algorithm for alldata segments104, or some other combination. Theencoder90 may determine the encoding algorithm type to be one of Golay, Multidimensional parity, Reed-Solomon, Hamming, Bose Ray Chauduri Hocquenghem (BCH), Cauchy-Reed-Solomon, or any other FEC encoder. The encodeddata segment106 is of greater size than thedata segment104 by the overhead rate of the encoding algorithm. The encodeddata segment106 is d(X/T), where d is size of thedata segment104, X is the width n or number of slices, and T is the threshold or minimum number of slices to enable reconstruction of thedata segment104.
• The corresponding decoding process performed bydecoder98 can accurately recover the data segment provided it receives a threshold number T or more slices. For example, if X=16 and T=10, then thedata segment104 will be recoverable, even if 6 EC data slices per segment are corrupted or missing. Note that thedecoder98 performs the complementary functions of theencoder90 when data is retrieved from theDSN memory22.
• Theslicer92 receives the encodeddata segment106 from theencoder90 and transforms the encodeddata segment106 into EC data slices108 in accordance with the slicing parameter from the vault for this user and/ordata segment104. In one embodiment,data segments104 are packed one for one into a data slice. In this instance, it is possible to correct many data slices with this method if the error patterns are substantially manifested as individual bit errors. In another example of this instance, entire slices may be lost and henceentire data segments104 may not be recoverable. In another embodiment, adata segment104 is dispersed across many data slices (e.g., X wide pillars) to lessen the impact on a givendata segment104 when an entire data slice is lost. Less data per segment is lost, when a data slice is lost, as thedata segment104 is dispersed across more slices. The slicing is discussed in greater detail with reference toFIG. 5. Note that the de-slicer100 performs the complementary functions of theslicer92 when data is retrieved from theDSN memory22.
• Thepost-data manipulator94 receives EC data slices108 from theslicer92. Thepost-data manipulator94 determines if post-manipulation of the EC data slices108 is required, and if so, what type of post-manipulation. The determination may be driven by one or more factors including a computing system-wide predetermination, parameters in the vault for this user, a table lookup, the user identification, the type of data, security requirements, available DSN memory, performance requirements, and/or other metadata. Thepost-data manipulator94 manipulates the EC data slices108 in accordance with the manipulation determination. The manipulation may include one or more of slice level compression, signatures, encryption, CRC, addressing, watermarking, tagging, adding metadata, and/or other manipulation to improve the effectiveness of the computing system. Thepost-data manipulator94 passes the resulting EC data slices for storage in theDSN memory22. Note that the post-data de-manipulator96 performs the complementary functions of thepost-data manipulator94 when data is retrieved from theDSN memory22.
• In an example of operation, thegrid module84 performs a rebuild operation for an identified data slice with an associated error. The identified data slice is one of a number X of data slices generated from a data segment. Thegrid module84 retrieves at least a threshold number T of the X data slices of the data segment. Thegrid module84 may retrieve vault parameters based on a vault identifier contained in the slice name, wherein the vault parameters include information regarding the type of post-data manipulation, the slicing/de-slicing function, and the encoding/decoding function. Based on these parameters, the retrieved EC data slices112 shown inFIG. 4 are post-data de-manipulated and then are de-sliced to generate encodeddata segment116. The encodeddata segment116 is decoded to produce areconstructed data segment118. The reconstructeddata segment118 is then encoded and sliced to generate a rebuilt data slice corresponding to the identified data slice.
• FIG. 5 is a diagram of an example embodiment of error coded data slice creation wherein theslicer92 creates four EC data slices from a thirty-two bit encoded data segment. Theslicer92 disperses the bits from the encoded data segment across the EC data slices wrapping around from the last slice to the first slice over and over (i.e., interleaves the bits among the slices). Each EC data slice, for this data segment, is stored on a differentDS storage unit36. In this example, encodeddata segment bits0,4,8,12,16,20,24, and28 form EC data slice1; encodeddata segment bits1,5,9,13,17,25, and29 form EC data slice2; encodeddata segment bits2,6,10,14,18,22,26, and30 form EC data slice3; and encodeddata segment bits3,7,11,15,19,23,27, and31 form EC data slice4. In a 4/3 system (a width of 4 pillars and a read threshold of 3), one EC data slice can be lost and the data segment can still be accurately recovered. Note that more slices produce a larger distance between consecutive encoded data segment bits of a slice, which improves the error resiliency.
• FIG. 6 is a schematic block diagram of an embodiment ofDS processing module34 ofuser device12 and/or of theDS processing unit16. TheDS processing module34 includes agateway module120, anaccess module122, agrid module84, astorage module124, and a bypass/feedback path126. TheDS processing module34 may also include aninterface32 and theDSnet interface34 or theinterfaces32 and34 may be part ofuser12,14 or of theDS processing unit16.
• In an example of storing data, thegateway module120 of theDS processing module34 receives anincoming data object132 with anobject name130 and user ID128 (e.g., a data file, a data block, an EC data slice, etc.), authenticates the user associated with the data object, obtains user information of the authenticated user, and assigns asource name134 to the data object132 in accordance with the user information. Thegateway module120 determines thesource name134 based on the vault identifier and the data object132. For example, thesource name134 may contain a data name (block number or a file number), the vault generation number, a reserved field, and a vault identifier. The data name may be randomly assigned but is associated with the user data object.
• To authenticate the user, thegateway module120 verifies the user ID128 with theDS managing unit18 and/or another authenticating unit. If the user ID128 is verified, thegateway module120 retrieves the user information from theDS managing unit18, theuser device12,14 and/or the other authenticating unit based on the user ID.
• The user information includes a vault identifier, operational parameters, and user attributes (e.g., user data, billing information, etc.). A vault identifier identifies a vault, which is a virtual memory space that maps to a set ofDS storage units36. For example, vault1 (i.e.,user1's DSN memory space) includes eight DS storage units (X=8 wide) and vault2 (i.e.,user2's DSN memory space) includes sixteen DS storage units (X=16 wide). The operational parameters may include an error coding algorithm, the width n (number of pillars X or slices per segment for this vault), a read threshold T, an encryption algorithm, a slicing parameter, a compression algorithm, an integrity check method, caching settings, parallelism settings, and/or other parameters that may be used to access the DSN memory layer.
• Thegateway module120 may utilize the bypass/feedback path126 to transfer an incoming EC data slice to anotherDS storage unit36 when theDS processing module34 determines that the EC data should be transferred.
• Theaccess module122 receives the data object132 and creates a series ofdata segments1 through Y therefrom. The number of segments Y may be chosen or random based on a selected segment size and the size of the data object. For example, if the number of segments is chosen to be a fixed number, then the size of the segments varies as a function of the size of the data object. For instance, if the data object is an image file of 4,194,304 eight bit bytes (e.g., 33,554,432 bits) and the number of segments Y=131,072, then each segment is 256 bits or 32 bytes. As another example, if segment sized is fixed, then the number of segments Y varies based on the size of data object. For instance, if the data object is an image file of 4,194,304 bytes and the fixed size of each segment is 4,096 bytes, the then number of segments Y=1,024. Note that each segment is associated with the source name.
• Thegrid module84, as previously discussed, may pre-manipulate (e.g., compression, encryption, cyclic redundancy check (CRC), etc.) the data segment before creating X error coded data slices for each data segment. Thegrid module84 creates XY error coded data slices for the Y data segments of the data object. Thegrid module84 adds forward error correction bits to the data segment bits in accordance with an error coding algorithm (e.g., Reed-Solomon, Convolution encoding, Trellis encoding, etc.) to produce an encoded data segment. Thegrid module84 determines the slice name and attaches the unique slice name to each EC data slice.
• The number of pillars, or slices X per data segment (e.g., X=16) is chosen as a function of the error coding objectives. TheDS processing module34 may utilize different error coding parameters for EC data slices based on guidance from one or more of a user vault (e.g., stored parameters for this user), a command from theDS managing unit18 or other system element, priority of the EC data slice, type of data in the EC data slice, and/or retrieval speed requirements. A read threshold T (e.g., T=10) of the error coding algorithm is the minimum number of error-free error coded data slices required to be able to reconstruct a data segment. TheDS processing unit34 can compensate for X−T (e.g., 16−10=6) missing, out-of-date, and/or corrupted error coded data slices per data segment.
• Thegrid module84 receives eachdata segment1−Y and, for each data segment generates X number of error coded (EC) slices using an error coding function. Thegrid module84 also determines theDS storage units36 for storing the EC data slices based on a dispersed storage memory mapping associated with the user's vault and/orDS storage unit36 attributes, which include availability, self-selection, performance history, link speed, link latency, ownership, available DSN memory, domain, cost, a prioritization scheme, a centralized selection message from another source, a lookup table, data ownership, and/or any other factor to optimize the operation of the computing system. Aslice name136 is then appended to the EC data slices. For example, theslice name134 may contain universal routing information, vault specific information, slice index, vault identifier, vault generation number, a reserved field, and a vault identifier.
• Thestorage module124 may perform integrity checks on the EC data slices and then transmit the EC data slices1 through X of eachsegment1 through Y to theDS storage units36. TheDS storage units36 may store the EC data slices and locally keep a table to convert virtual DSN addresses into physical storage addresses. In an embodiment, the number ofDS storage units36 is equal to or greater than the number of pillars (slices X per segment) so that no more than one error coded data slice of the same data segment is stored on the sameDS storage unit36. Further note that EC data slices of the same pillar number but of different segments (e.g., EC data slice1 ofdata segment1 and EC data slice1 of data segment2) may be stored on the same or differentDS storage units36.
• In an example of a read operation, theuser device12 or14 sends a read request to theDS processing module34, which authenticates the request. When the request is authentic, theDS processing module34 sends a read message to each of theDS storage units36 storing slices of the data object being read. The slices are received via theDSnet interface34 and processed by thestorage module124, which performs a parity check and provides the slices to thegrid module84. Thegrid module84 de-slices and decodes the slices of a data segment to reconstruct the data segment. Theaccess module122 reconstructs the data object from the data segments and thegateway module120 formats the data object for transmission to the user device.
• FIG. 7 is a schematic block diagram of an embodiment of a file system hierarchy including a plurality of user virtual memories, a segment andslice directory140, a virtual dispersed storage network (DSN) address to physical location table142, and a physical dispersed storage network (DSN)memory146. The file system hierarchy may be utilized to translate the user virtual memory system to thephysical DSN memory146 by translating the user virtual memory address into a virtual dispersed storage network (DSN)address space148 and then to thephysical DSN memory146. The segment andslice directory140 includes the virtualDSN address space148 and thephysical DSN memory146 includes a plurality of DS storage units36 (e.g., A, C, D, and F). In an example, where there are four pillars, there are four slices (X=4) created for each of the Y data segments. Pillars can be allocated to more than one DS storage unit, but a given DS storage unit is not generally assigned to store more than one pillar from a given user (or vault) to improve system robustness (e.g., avoiding loss of multiple slices as a result of a single DS storage unit failure).
• In an embodiment, one of the plurality of user virtual memories152a-nutilizes a native OS file system to access the segment andslice directory140 by including source name information in requests such as read, write, delete, list, etc. A source name vault identifier and a file/block name may index into the segment andslice directory140 to determine the virtualDSN address space148. A unique virtual vault is associated with each user (e.g., an individual, a group of individuals, a business entity, a group of business entities, etc.) and may contain user attributes (e.g., user identification, billing data, etc.), operational parameters, and a list of the DS storage units that may be utilized to support the user. One or more vaults may be established from the same set of DS storage units in different combinations. A vault identifier is utilized to distinguish between vaults. For example, vault #1 (for user1) may utilize DS storage units A, C, D, and F (X=4 wide) while vault #2 (user2) may utilize DS storage units A−H (X=8 wide) (note that DS units B, E, G, and H are not shown).
• In an example, the total virtualDSN address space148 is defined by a forty-eight byte identifier thus creating 25648 possible slice names. The virtualDSN address space148 accommodates addressing of EC data slices corresponding to segments of data objects (e.g., data file, blocks, streams) over various generations and vaults. The slice name is a virtual DSN address and remains the same even as different DS storage units are added or deleted from thephysical DSN memory146.
• A user has a range of virtual DSN addresses assigned to their vault, user virtual memory152a-n. For instance, the virtual DSN addresses typically do not change over the operational lifespan of the system for the user. In another instance, the virtualDSN address space148 is dynamically altered from time to time to provide such benefits as improved security and expansion, retraction, and/or capability. A virtualDSN address space148 security algorithm may alter the virtualDSN address space148 according to one or more of a command (e.g., from the DS managing unit18), a schedule, a detected security breach, or any other trigger. The virtual DSN address may also be encrypted in use thus requiring encryption and decryption steps whenever the virtual DSN address is used.
• The vault and file name index used to access the virtualDSN address space148 and to create the slice names (virtual DSN addresses) may also be used as an index to access the virtual DSN address to physical location table142. For example, the virtual DSN address to physical location table142 is sorted by vaults and pillars so that subsequent addresses are organized by pillar of the file segments that have EC data slices with the same slice identifier and hence are typically stored at the same DS storage unit (e.g., slices having a first pillar identifier are stored in DS storage unit A). The output of the access to the virtual DSN address to physical location table142 is the DS storage unit identifiers.
• The slice names may be used as the virtual index to the memory system of each DS storage unit to gain access the physical location of the EC data slices. In this instance, the DS storage unit maintains a local table correlating slice names (virtual DSN address) to the addresses of the physical media internal to the DS storage unit. For example,user number1 has a vault identified operational parameter of four pillars andpillar0 is mapped to DS storage unit A,pillar1 is mapped to DS storage unit C,pillar2 is mapped to DS storage unit D, andpillar3 is mapped to DS storage unit F.
• FIG. 8 is a schematic block diagram of another embodiment of a storageintegrity processing unit20 that includesprocessing module50 andDSnet interface32. Theprocessing module50implements grid module84. To detect for slices having a data inconsistency, thegrid module84 scans EC data slices stored atDS storage units36. For example, thegrid module84 may scan six pillars of EC data slices forsegments1 to Y of a data object.
• In an embodiment, thegrid module84 detects three major types of data errors: slice failure, storage unit failure, and site failure. For a slice failure (illustrated at DS storage unit2), thegrid module84 rebuilds the slice. For a DS storage unit failure (illustrated at DS storage unit3), thegrid module84 rebuilds the slices stored within the DS storage unit and stores the rebuilt slices in an available DS storage unit. For a site failure where one or more DS storage units operate (illustrated atsite3 whereDS storage units5 and6 may be offline), thegrid module84 rebuilds the data slices stored at the site and stores the rebuilt slices at an available site.
• In an embodiment, depending on a type of error, the decision to rebuild may be delayed until after a predetermined period of time. The predetermined time period is based on an estimate for correcting the type of error. In another embodiment, depending on the number X of data slices from the data segment that are recoverable, the rebuilding may be immediately performed rather than delayed for the predetermined time period. For example, the rebuilding of data slices atsite3 would begin without waiting a predetermined time period since the site contains two of the six pillars in a 6/4 system and any further loss of slices at another site would render the data segment unrecoverable.
• FIG. 9 is a logic flow diagram of an embodiment of amethod200 for data rebuilding in response to a type of error. Instep202,grid module84 detects an error associated with an EC data slice. In an embodiment, thegrid module84 periodically scans EC data slices to detect data errors regarding a data object. Thegrid module84 receives integrity data regarding one or more pluralities of EC data slices from theDS storage units36. TheDS storage units36 may provide the integrity data in response to a request from the integrity module85 and/or at predetermined intervals. In another embodiment, thegrid module84 detects a storage unit failure or site failure. Thegrid module84 may receive a status update from the storage units or sites or from theDS managing unit18 or may determine a status from responses or lack thereof from theDS storage units36 or sites.
• Next thegrid module84 identifies the data slice for rebuilding instep204. In an embodiment, thegrid module84 requests naming information of one or more pluralities of data slices from the plurality ofDS storage units36. For a storage unit failure or site failure, thegrid module84 requests naming information fromDS processing unit15,user device12,14 orDS managing unit18. The naming information includes at least a portion of a slice name. After receiving the naming information, thegrid module84 evaluates it to identify the data slice with an associated error (e.g., corrupt naming information, missing slice, out-of-date slice, etc.) to generate an identified data slice for rebuilding. Thegrid module84 then rebuilds the identified data slice in response to a type of error instep206. The rebuilding of the data slices in accordance with the type of error is discussed further with respect toFIGS. 10-12.
• FIG. 10 is a logic flow diagram of an embodiment of amethod210 for data rebuilding in response to a type of error. An address range of encoded data slices is scanned instep212 and one or more errors are detected that are associated with the data slices, instep214. Instep216, it is determined whether the type of error is temporary. For example, a storage unit or site failure may be temporary, e.g. due to a network connectivity problem, software problem or power outage. In an embodiment, when the type of error is temporary, a predetermined time period lapses prior to rebuilding to determine whether the failure is corrected.
• In another embodiment, when the type of error is temporary, an availability of the other data slices from the data segment is determined instep218. In an embodiment, the number X of EC data slices stored for a data segment is compared with a number A of available data slices for the data segment instep220. Assuming a minimum threshold number T of EC data slices are required to rebuild a data segment, when the difference between the number of slices X and available slices A (X−A) compares favorably to the threshold number T (e.g. X−A is greater than T), then the data segment may still be rebuilt in case one or more additional data slices become unavailable. Thus, waiting to rebuild until after a predetermined time period is performed. However, when the difference between the number of slices X and available slices A does not compare favorably (e.g. X−A is equal to T), then rebuilding is performed as shown instep222 rather than delayed for the predetermined time period. In another embodiment, an availability of the other data slices from the data segment is determined by comparing a number E of data slices with an associated error from the data segment. Depending on the number X of data slices in comparison to the number E of unrecoverable data slices (e.g. E<X−T), the rebuilding is performed rather than delayed for the predetermined time period.
• The predetermined time period may vary depending on the type of error and estimated time to correct the type of error. For example, for a storage unit or site failure, a network connectivity error may be provided a shorter predetermined time period than a power outage.
• After or during the predetermined time period, the availability of the identified data slice is re-evaluated to determine whether the associated error has been corrected instep226. When the associated error is corrected, the scan continues for other errors instep230. When the error is not corrected after the predetermined time period, the identified data slice is rebuilt. In another embodiment, the process returns to step218 to determine availability of the other X data slices for the data segment. The process may continue to wait one or more predetermined time periods before rebuilding as long as sufficient data slices are available for recovery of the data segment in the event of an additional failure.
• FIG. 11 is a logic flow diagram of another embodiment of amethod240 for data rebuilding in response to a type of error when the type of error is a slice error. The slice error may involve just one slice or a plurality of data slices, e.g. the same pillar slices for more than one data segment. Instep242, an error is detected associated with an encoded data slice that is determined to be a slice error instep244. The slice error may result from a corrupted data, from a missing slice, or from a version update error (e.g., failed to successfully store a more recent version). When the slice error includes data corruption instep246, the corrupted slice is rebuilt from at least a threshold number T of the other X slices of the data segment and the rebuilt slice is restored on the same DS storage unit or another available DS storage unit.
• When the slice error is not a result of a corrupted slice, the method continues to step250 where it is determined whether a data slice is missing. For example, when less than the number X of expected data slices are found for a data segment, it is determined that one or more data slices are missing. When a data slice is missing, the method continues atstep252 where it is determined whether the missing slice is a temporary type of error. The determination is based on whether the error temporarily prevents retrieval of the data slice, e.g., a DS storage unit is temporarily down for updates or repair or network is temporarily down to the DS storage unit, rather than permanently prevents recovery of the data slice, e.g. data slice is not saved or erased due to failures. When the missing slice is a temporary condition, a predetermined period of time is set to resolve the error instep252. After or during the predetermined time period, it is determined whether the error is resolved instep254. For example, the missing data slice is now available because, e.g. the DS storage unit returns online or network connectivity issues are resolved. When the missing error is corrected within the predetermined period of time, the process is complete for this particular slice error as shown instep256. However, when the predetermined period of time expires prior to the error being resolved or the error is not a temporary type of error, the method proceeds to step258 in which thegrid module84 rebuilds the missing slice and re-stores it on the same DS storage unit or another available DS storage unit.
• When the slice error is not a missing slice, the method continues to step260 wherein thegrid module84 determines whether the slice includes a version update error. The determination may be made, e.g., by comparing the version of other slices for the same segment or by accessing the user vault to determine a version for the slice name. When the slice has a correct version, the method repeats atstep244. When the slice error includes a version update error, the method continues atstep262 where thegrid module84 rebuilds the slice and re-stores it on the same or another available DS storage unit.
• FIG. 12 is a logic flow diagram of another embodiment of amethod280 for data rebuilding in response to a type of error when the type of error is detected at a pillar level. Instep282, an error is detected associated with an encoded data slice that is determined to be at a pillar level instep284. The pillar data error may be a result of either or both of a DS storage unit failure or a site failure. Instep286, thegrid module84 determines whether a DS storage unit failure has occurred. A DS storage unit failure is indicated by, e.g., corruption errors in a plurality of data slices stored at aDS storage unit36, no response by a DS storage unit36 (e.g., powered off, network down, maintenance mode), a scheduled DS storage unit outage, and/or numerous missing EC data slices. TheDS managing unit18 may schedule DS storage unit outages from time to time to test the rebuilding process or to have certain data slices stored at a DS storage units rebuilt and stored at another DS storage unit, e.g. to upgrade to a new storage unit.
• When a storage unit failure is detected instep286, it is determined whether the DS storage unit failure is a temporary type of error instep288. The determination is based, e.g., on a maintenance indicator (e.g., the DS storage unit is temporarily down for updates or repair), or a network connectivity indicator (e.g., the network is temporarily down to the DS storage unit) or status update from theDS storage unit36 orDS managing unit18. When the site failure is a temporary type of error, the process delays a predetermined amount of time instep290 prior to rebuilding. When the error is not corrected after the predetermined amount of time or the error is not temporary, thegrid module84 rebuilds the data slices stored on the failed storage unit and restores the slices on another availableDS storage unit36 instep294 at the same site or a different site. When the storage unit failure is corrected within the predetermined period of time, the process is complete for this particular slice error as shown instep296.
• Continuing atstep298, the process detects whether a site failure has occurred. In some instances, a storage unit failure is due to a site failure. The determination of a site failure is indicated, e.g., by a maintenance indicator (e.g., DS storage units at a site are temporarily down for updates or repair), a network connectivity indicator (e.g., the network is temporarily down to the site), or a scheduled site outage or status update or nonresponsive storage units at a site (e.g., natural disaster). TheDS managing unit18 may schedule DS site outages from time to time to test the rebuilding process or to have data slices stored at a site rebuilt and stored at another site, e.g. to optimize where data slices are stored or to relocate a storage center.
• When a site failure occurs, the process continues to step288 to determine whether the site failure is a temporary condition. The determination may be based on the maintenance indicator (e.g., the DS storage unit is temporarily down for updates or repair), the network connectivity indicator (e.g., the network is temporarily down to the DS storage unit), or the scheduled site outage. When the error is not temporary or the site failure is not corrected after a predetermined time period, the data slices stored onDS storage units36 at the site are rebuilt and stored on one or more availableDS storage units36 at another site. When no storage unit or site failure has occurred, the method repeats atstep284.
• FIG. 13 is a schematic block diagram of another embodiment ofgrid module84 for rebuilding one or more data slices. Thegrid module84 includes arebuild module302 andcontrol unit74. Thecontrol unit74 identifies data slices for rebuilding while therebuild module302 rebuilds the identified data slices. Thecontrol unit74 may also coordinate functions and sequencing of activities of therebuild module302, includingencoder90,slicer92,post-data manipulator94, post-data de-manipulator96,de-slicer98, anddecoder100.
• In an example of operation,pillar2 slices are missing from a group of six pillars. Thecontrol unit74 retrieves data slices from the companion pillars and provides the recovered data slices304 to therebuild module302. At least a threshold T of data slices (e.g., T=read threshold) from other pillars must be retrieved to rebuild thepillar2 data slices. The post-data de-manipulator96 performs any required de-manipulation (e.g., CRC) as described in more detail with reference toFIG. 4 to generate post datade-manipulated slices306 though in an embodiment, therebuild module302 does not perform data de-manipulation or manipulation on the data slices. The de-slicer98 de-slices post datade-manipulated slices306 with the missing slice filled with any combination of zeros and ones to generate encodeddata segment308. Thedecoder100 decodes encodeddata segment308 utilizing the decoding algorithm specified for this vault and data type to generatereconstructed data segment310.
• Encoder90 encodes the reconstructeddata segment310 to producere-encoded data segment312 based on the encoding algorithm specified for this vault. Theslicer92 slices there-encoded data segment312 to produce pre-data manipulated data slices314. Theslicer92 may reproduce all of the slices or just the slice for the missing pillar. Thepost-data manipulator94 manipulates (e.g., CRC) the data slices to produce the rebuilt data slices316 corresponding to the identified missing data slices. Thegrid module84 stores the reconstructed slice in the appropriate DS storage unit according to the virtual DSN address to physical DS storage table.
• In another example of operation, therebuild module302 receives the recovered data slices302 and the de-slicer98 deslices the data slices to generate encodeddata segment308. The encodeddata segment308 is then transmitted to theslicer92 which reslices it and generates the rebuilt data slices316. Therebuild module302 does not perform data de-manipulation or manipulation on the data slices. In addition, therebuild module302 does not perform decoding and encoding on the encodeddata segment308 in this embodiment.
• FIG. 14 is a logic flow diagram of an embodiment of amethod340 for rebuilding a data slice generated from a data segment. An identification of an encoded data slice for rebuilding is received by therebuild module84 instep342. Thegrid module84 retrieves at least a threshold T of data slices needed to reconstruct the data segment instep344. Thegrid module84 reconstructs the data segment instep346 and generates a rebuilt encoded data slice from the reconstructed data segment instep348.
• FIG. 15 is a schematic block diagram of an embodiment of acontrol unit74 of thegrid module84. Thecontrol unit74 includes one ormore scanning agents350, arebuild queue352, arebuild agent354, aslice queue356 and aslice agent358. For efficient rebuild scanning, the number of scanning agents varies depending on the size of the virtualDSN addressing space148. For instance, if theDSN addressing space148 is relatively small, then asingle scanning agent350 may be sufficient to communicate with theDS storage units36 to identify slices that need rebuilding. As theDSN addressing space148 increases, it may be more efficient to divide theDSN addressing space148 among two or more of thescanning agents350. Then ascanning agent350 communicates withDS storage units36 associated with its range of theDSN addressing space148.
• In an example of operation, ascanning agent350 communicates with one or moreDS storage units36 associated with its portion of theDSN addressing space148 to receive integrity data or slices for scanning. When thescanning agent350 detects an error in a data slice, it stores the slice name or other identification of the identifieddata slice360 with an associated error into therebuild queue352. Therebuild agent354 retrieves slice names from therebuild queue354 to initiate the rebuilding process by therebuild module302. The rebuild agent162 receives the rebuiltdata slice316 and stores the rebuiltdata slice316 or an identification thereof into theslice queue356. Theslice agent358 retrieves the rebuilt data slices from theslice queue356 and stores them to an availableDS storage unit36.
• The scanning function of thescanning agents350 may be centralized or may be distributed among other system elements (e.g., to reduce network traffic) including one or more of the storageintegrity processing unit20, theDS storage units36, theDS managing unit18, theDS processing unit16, or theuser device12,14 as described further herein. The operation of scanningagents350 is further described with respect toFIGS. 16-19.
• FIG. 16 is a logic flow diagram of an embodiment of amethod380 for scanning an encoded data slice. Instep382,scanning agent350 receives a scanning address range assignment which includes an address range of one or more pillars within a vault from one or more of theDS processing unit16, theDS managing unit18, the storageintegrity processing unit20, and/or theDS storage units36. In another embodiment, thegrid module84 may determine to scan DS storage units based on a lookup into the virtual DSN address to physical location table142 and/or based on a virtual address range assignment for thegrid module84. The determination of the scanning address range assignment will be discussed in more detail with reference toFIG. 24. Instep384, the scanning agent determines an encoded data slice has an associated error type. In an embodiment, the scanning agent determines multiple pillars have an associated error, e.g. missing an entire segment of slices or even all the slices for that pillar. Thescanning agent350 identifies the data slices with errors instep386 and stores identification, e.g. the slice names, of the slices with associated errors in therebuild queue352 instep388.
• FIG. 17 is a logic flow diagram of another embodiment of amethod390 for determining a missing data slice error during a scan of data slices. Instep392, thescanning agent350 scans an address range of one or more pillars within a vault. Instep394, thescanning agent350 determines whether a data slice is missing. For example, thescanning agent350 may request theDS storage units36 to provide a list of slice names within an address range. The request may include a starting slice name (DSN virtual address) and a count of slice names to include in the list (count may be zero or greater). Thescanning agent350 receives a slice name list for slices that should be stored within the address range and compares the slice name list with the list of slices received from theDS storage units36. In another example, thescanning agent350 checks sequential slice names for a data segment and determines whether one of the sequential slices is not present at a pillar. The determination may also be based on a comparison of data slices that should be present in one pillar based on the slice names present in the companion pillars. Instep396, thescanning agent350 identifies the missing data slices and places the slice names or other identification of the data slices in therebuild queue352 so that they may be subsequently rebuilt and re-stored. The scan continues instep398 when no errors are detected.
• FIG. 18 is a logic flow diagram of another embodiment of amethod400 for determining a data corruption error during a scan of data slices. Instep402, thescanning agent350 scans an address range of one or more pillars within a vault. As part of the scanning, the scanning agent checks integrity data stored for each of a plurality of data slices in the address range instep404. In an embodiment, when a data slice is initially stored, theDS storage units36 also store integrity data for each EC data slice. The integrity data may be a CRC, a hash, a parity check or other data validity function for a data slice. For example, theDS storage units36 append a CRC to each EC data slice when the slice is initially stored. The integrity data may be calculated as well from overhead included in the data slice, such as the slice name and version information. Thescanning agent350 then recalculates the integrity data and compares it to the stored integrity data. Thescanning agent350 determines whether the integrity data comparison matches. When the data verification fails, thescanning agent350 determines that a data corruption error has occurred instep406. Instep408, thescanning agent350 identifies the data slices with data corruption and places the slice names or other identification of the data slices in therebuild queue352 so that they may be subsequently rebuilt and re-stored. The scan continues instep410 when no errors are detected.
• FIG. 19 is a logic flow diagram of another embodiment of amethod420 for determining a version update error during a scan of data slices. Instep422, thescanning agent350 scans an address range of one or more pillars within a vault and determines a version for a data slice in the address range instep424. Instep426, thescanning agent350 determines whether the data slice is an appropriate version based on the user vault or version number from the other slices for the data segment. The determination may be made, e.g., by comparing the version of other slices for the same segment or by accessing the user vault to determine a version for the slice name. When the data slice does not have a current version instep428, thescanning agent350 identifies the data slice and places the slice names or other identification of the data slices in therebuild queue352 so that the data slice may be subsequently rebuilt and re-stored. The scan continues instep430 when no errors are detected.
• FIG. 20 is a logic flow diagram of an embodiment of amethod440 of operation of therebuild agent354. Therebuild agent354 selects a data slice from therebuild queue352 for rebuilding instep442. Therebuild agent354 selects the data slice in a first in first out (FIFO) order or an order based on a prioritization algorithm instep446. The prioritization algorithm may operate to speed the recovery of key missing data slices and/or may be based on a priority indicator for the data object, a priority indicator for the user, a priority indicator for the data object type (e.g., always recover banking records ahead of home video), slice age (e.g., which is the most outdated), and/or any other priority indicator to provide timely recovery of the most crucial and/or valuable data. In an embodiment, therebuild agent354 retrieves at least a threshold number T of data slices from the data segment needed to rebuild the data slice instep448. Therebuild module302 rebuilds the data slice using the at least T data slices. Therebuild agent354 receives the rebuilt data slice instep448 and stores the rebuilt data slice or an identification thereof into theslice queue356 instep450.
• FIG. 21 is a logic flow diagram of an embodiment of amethod460 of operation of theslice agent358. Instep462, theslice agent358 selects a rebuilt data slices from theslice queue356 for storage to an availableDS storage unit36. The order in which theslice agent358 selects rebuiltslices316 may be a first in first out (FIFO) order or an order based on a prioritization algorithm. The prioritization algorithm may operate to speed the recovery of key missing data slices and/or may be based on a priority indicator for the data object, a priority indicator for the user, a priority indicator for the data object type (e.g., always recover banking records ahead of home video), slice age (e.g., which is the most outdated), and/or any other priority indicator to provide timely recovery of the most crucial and/or valuable data. Instep466, theslice agent358 determines one of theDS storage units36 for storing the rebuilt encoded data slice and determines whether theDS storage unit36 is available instep468. When it is not available, the process continues to step466 to determine anotherDS storage unit36 is available. In another embodiment, theslice agent358 requeues the slice in theslice queue356. When the DS storage unit is available, theslice agent358 determines whether the rebuilt data slice is the appropriate version based on the user vault or version number from the other slices for the data segment instep470. When the version is not current, theslice agent358 re-queues the slice name in therebuild queue352 instep472 so that therebuild agent354 will rebuild the data slice with the appropriate version. When the version is current, theslice agent358 stores the data slice in the available DS storage unit instep474.
• In an embodiment, thecontrol unit74 may be partially or completely external to thegrid module84. For example, thecontrol unit74 may be part of acomputing core26 at a remote location, part of auser device12,14, part of theDS managing unit18, or distributed amongst one or moreDS storage units36 as described further herein. For example, the scanning function may be centralized or it may be distributed amongst system elements including one or more of theDS storage units36, theDS managing unit18, theDS processing unit34, or theuser devices12,14.
• FIG. 22ais a schematic block diagram of an embodiment of a distributedcontrol unit74. In this embodiment, aDS storage unit36 includes one ormore scanning agents350 and arebuild queue352. Acentralized control unit74 is located in a storageintegrity processing unit20 or other unit such asDS managing unit18. In an example of operation, the one ormore scanning agents350 implemented inDS storage unit36 are assigned a scanning address range. The scanning address range may include data slices stored on theDS storage unit36 as well as data slices stored at otherDS storage units36. When thescanning agent350 inDS storage unit36 detects an error, thescanning agent350 places the slice name or other identification of the data slice inrebuild queue352 in theDS storage unit36. In an embodiment, therebuild agent354 in the storageintegrity processing unit20 accesses the rebuild queue in theDS storage unit36 to select data slices for rebuilding. In another embodiment, therebuild queue352 is implemented in the storageintegrity processing unit20, and the scanning agent in theDS storage unit36 stores the slice name with an associated error in therebuild queue352 in the storageintegrity processing unit20.
• In an embodiment, thegrid module84, including therebuild module302 andcontrol unit74, may be distributed, in whole or in part, among the storageintegrity processing unit20, theDS managing unit18, theuser devices12,14 or distributed amongst one or moreDS storage units36. For example, the scanning function of thecontrol unit74 may be centralized or it may be distributed amongst other system elements. Similarly, the rebuild function of thegrid module84 may be centralized or it may be distributed amongst other system elements, such as the storageintegrity processing unit20, aDS processing unit16 andDS managing unit18. In another embodiment, thegrid module84, including therebuild module302 and thecontrol unit74 are located in one or more of the plurality ofDS storage units36.
• FIG. 22bis a schematic block diagram of another embodiment of a distributedcontrol unit74. In this embodiment, a plurality ofDS storage units36 include aconsistency agent480. Theconsistency agent480 scans the locally stored data slices, recalculates integrity data for the local data slices and compares integrity data stored for the data slices with the recalculated integrity data. Thus, theconsistency agents480 perform checks on locally stored data slices to determine data corruption errors, as described with respect toFIG. 18. When aconsistency agent480 in aDS storage unit36 detects an error, theconsistency agent480 places the slice name or other identification of the data slice inrebuild queue352 in the storageintegrity processing unit20. In another embodiment, theconsistency agent480 transmits the identification of the data slice to thescanning agent350 in the storageintegrity processing unit20 for storing in therebuild queue352. In an embodiment, thescanning agent350 in the storageintegrity processing unit20 performs scans across multipleDS storage units36 to determine missing slice errors (as described with respect toFIG. 18) and version update errors (as described with respect toFIG. 19) while theconsistency agents480 in theDS storage units36 perform scans to determine data corruption errors on locally stored data slices.
• FIG. 23 illustrates a schematic block diagram of an embodiment of a distributedgrid module84. In this example, the scanning function, control functions and rebuild function of thegrid module84 are distributed amongst one or more of theDS storage units36 and the storageintegrity processing unit20. Atsite1,DS storage unit1 includes ascanning agent350 while atsite2 bothDS storage unit3 and4 include aconsistency agent480. Insite3,DS storage unit5 includes acontrol unit74 whileDS storage unit6 includes agrid module84 with both arebuild module302 and acontrol unit74 functions.
• In an example of operation,DS storage units1,2,3,4,5,6 share at least one common address range in a virtual DSN address space for a companion set of pillars of at least one common vault.DS storage unit1 is assigned to scan a particular subset of the common address range for data errors in data slices stored locally and acrossDS storage units2,3,4,5,6.DS storage unit1 issues a scan request for integrity data over LAN toDS storage unit2 at the same site and overnetwork24 to the otherDS storage units3,4,5,6. WhenDS storage unit1 receives the scan responses fromDS storage units2,3,4,5,6, thescanning agent350 determines whether data errors are present based on the responses. The errors may include one or more of corrupted slices, missing slices, DS storage unit failures, and/or site failures.
• When data errors are detected by scanningagent350 inDS storage unit1, a slice name or other identification of data slices with associated errors is transmitted to thegrid module84 in the storageintegrity processing unit20 for rebuilding. In another embodiment, theDS storage unit1 transmits a slice name or other identification of data slices with associated errors togrid module84 inDS storage unit6 for rebuilding. In another embodiment,DS storage unit1 includes arebuild queue352 and stores a slice name or other identification of data slices with associated errors in itsrebuild queue352. Arebuild agent354 ingrid module84 at storageintegrity processing unit20 or atDS storage unit6 access the rebuild queue in theDS storage unit36 to select data slices for rebuilding.
• When the scanning function of agrid module84 is distributed amongst the DS storage units, scanning of data slices can be distributed as well. For example, each DS storage unit with a scanning function can be assigned a portion of an address range to distribute the processing load. In another example, thescanning agent350 in theDS storage units36 perform scans across multipleDS storage units36 to determine missing slice errors (as described with respect toFIG. 18) and version update errors (as described with respect toFIG. 19) whileconsistency agents480 in theDS storage units36 perform scans to determine data corruption errors on locally stored data slices.
• FIG. 24 is a schematic block diagram of an embodiment of distributed scanning address range assignments. A dispersed storage memory mapping is shown that specifies virtual DSN address ranges0-8 by pillar mapped to physical DS storage units A,B,C,D,E,F,G,H,I,J,K,L,M that store information for those address ranges. In this example, the address ranges0-8 include the virtual DSN addresses assigned to a vault λ. The individual addresses within each address range may specify a unique file identifier within that vault. The letter designation in each pillar signifies the physicalDS storage unit36 that is assigned to store data slices for those address ranges. For example, DS storage unit A is responsible for storing data slices corresponding topillar0 for DSN addresses ranges0-4 and DS storage unit J is responsible for storing data slices corresponding topillar0 for DSN addresses ranges5-8. Pillars0-5 for the same address range will contain the EC data slices for stored data segments. For example, DS storage units A, B, D, E, F, and H store data slices with anaddress range0 corresponding to pillars0-5 for the same data segments.
• The memory mapping specifies scanning address range assignments by companion sets of pillars within the same address ranges. The scanning process foraddress range0 may include scans of pillar0-5 slices in DS storage units A, B, D, E, F, and H since they form the companion pillars for the same data segments. For example, DS storage unit A is assigned to scanaddress range0 in DS storage units A, B, D, E, F, and H and DS storage unit J is assigned to scanaddress range6 in DS storage units J, C, K, L, G and I. In another embodiment, it is also possible to consolidate some of the scanning ranges. For example, DS storage unit D may scan address ranges3 and4 as one range across DS storage units A, C, D, L, G, and H instead of sharing part of that task with DS storage unit L. In a similar way, DS storage unit M may scan address ranges7 and8 as one range across DS storage units J, C, K, L, M, and I instead of sharing part of that task with DS storage unit K.
• The scanning address range assignments may be predetermined and static or may be altered from time to time as a function of one or more of new DS storage unit additions, storage growth, a load sharing algorithm, an algorithm to exercise the scanning responsibilities, a new network configuration, a new plurality of DS storage unit clusters at one site, and/or other changes that may affect scanning efficiency and effectiveness.
• Various examples have described a centralized approach to rebuilding a data slice wherein at least a threshold number T of data slices needed to rebuild the data slice are transmitted to a rebuild function at one location, e.g. agrid module84 at storageintegrity processing module20. This centralized approach requires network bandwidth from eachDS storage unit36 transmitting one of the at least threshold number T of data slices, even when some of theDS storage units36 are located at the same site. In another embodiment, the slice rebuilding process includes a de-centralized approach whereinDS storage units36 that store one of the at least threshold number T of data slices each sequentially compute a portion of the data needed to produce the rebuilt data slice. The de-centralized approach is discussed in more detail with reference toFIGS. 25-33.
• FIG. 25 is a schematic block diagram of an embodiment of a dispersedstorage system500 with de-centralized slice rebuilding. The dispersedstorage system500 includes a plurality ofDS storage units36 at a plurality of sites. In this example,DS storage units1 and2 are atsite1,DS storage units3 and4 are atsite2, andDS storage units5 and6 are atsite3. Each of theDS storage units36 include a partialrebuild grid module502. The partialrebuild grid module502 includes apost data demanipulator96,partial decoder504 andpartial encoder506. In an embodiment, the partialrebuild grid module502 also includes functionality to reconstruct a data segment from at least a threshold number T of data slices in a centralized rebuilding process.
• In the partial rebuilding process, a data slice is rebuilt by combining slice partials generated from at least a threshold number T of data slices in any order (e.g., adding the slice partials individually or adding in one or more subsets). In an example of operation, a slice failure atDS storage unit3 is identified by partialrebuild grid module3 and the slice name or other identification of the data slice with an associated error is determined for the identified data slice. When the identified data slice is selected for rebuilding, thegrid module3 determines at least a threshold number T of data slices from the same data segment needed to rebuild the identified data slice.
• In the example,DS storage unit1 stores one of the threshold number T of data slices, i.e. EC data slice1_0.DS storage unit1 retrieves EC data slice1_0 and post-data de-manipulator96 performs any required data de-manipulation on EC data slice1_0. The partial decoder performs a decode function on EC data slice1_0 to generate a partially decoded portion of the data segment. The partial encoder encodes the partially decoded portion of the data segment to produce a partially encoded portion of the data segment, e.g. slice partial (SP1). The partial decode and partial encode steps involve finite field arithmetic for the error control scheme and will be discussed in greater detail with reference toFIGS. 28-31.DS storage unit2 also performs a partial decode step followed by a partial encode step to produce slice partial SP2 from the second slice EC data slice1_1. The slice partial SP1 is combined with slice partial SP2 to produce first summation S12. The summation of slice partials includes, for example, typical arithmetic addition, a finite field summation operation, and/or a bit-wise exclusive-OR logical operation.
• SimilarlyDS storage unit5 performs a partial decode step followed by a partial encode step to produce slice partial SP5 from the EC data slice1_4, andDS storage unit6 performs a partial decode step followed by a partial encode step to produce a slice partial (SP6) from the EC data slice1_5. The slice partial SP5 is combined with slice partial SP6 to produce second summation S56.DS storage unit4 performs a partial decode step followed by a partial encode step to produce a slice partial (SP4) from the EC data slice1_3. SP4 is then combined with first summation S12, second summation S56 to generate apartial slice sum510. The rebuilt EC data slice1_2 is then generated from thepartial slice sum510. For example, post data manipulation may need to be performed onpartial slice sum510 to generate the rebuilt EC data slice1_2.
• The slice partials in the partial rebuilding process may be combined in any order to generate the partial slice sum. For example, inFIG. 25 at a first level, SP1 and SP2 may be combined and SP5 and SP6 may be combined before those two combinations are combined with SP4. In another example, the combination of SP1 and SP2 fromsite1 may be sent tosite3 where the SP1 and SP2 combination is combined with the combination of SP5 and SP6. The combination of SP1,2,5,6 is sent tosite2 where that combination is combined with SP4 to produce the rebuilt EC data slice1_2.
• The sequencing of combining the slice partials in the partial rebuilding process may be determined by the storageintegrity processing unit20,DS managing unit18, one of theDS storage units36 and/orDS processing34. The determination may be based on where the failure occurred, the network topology, the loading level of the DS storage units, which DS storage units are clustered together at the same sites sharing the common LAN, and/or any other factor to improve the efficiency of the recovery. Two sequencing approaches include a ring sequencing and a star sequencing. A ring sequencing begins with one site that generates slice partials and passes the results to the next site until the site with the error receives the results of the other sites. In a star sequencing, each site generates slice partials and passes the results to the site with the error. The star sequencing and ring sequencing are described in greater detail with reference toFIGS. 26 and 27.
• FIG. 26 is a schematic block diagram of another embodiment of a dispersed storage system for partial rebuilding using star sequencing. A plurality ofDS storage units36 each include a partialrebuild grid module502. LANs530 coupleDS storage units36 located at the same site whileWAN540 couplesDS storage units36 at different sites.WAN540 is included for example as a part ofnetwork24 inFIG. 1.
• In this example, star sequencing for slice rebuilding is shown.DS storage unit1 receives partial SP2 fromDS storage unit2 over theLAN530aand combines slice partial SP2 with slice partial SP1 to generate first summation SP12. TheDS storage unit1 transmits the first summation SP12 toDS storage unit3.DS storage unit5 receives slice partial SP6 fromDS storage unit6 overLAN530cand combines slice partial SP6 with slice partial SP5 to generate second summation SP56.DS storage unit3 receives second summation SP56 fromDS storage unit5.DS storage unit3 receives slice partial SP4 overLAN530bfrom
• DS storage unit4.DS storage unit3 combines first summation SP12 and second summation SP56 and slice partial SP4 to generate the rebuilt data slice. The rebuilt data slice is restored onDS storage unit3 or another available storage unit.
• FIG. 27 is a schematic block diagram of another embodiment of a dispersed storage system for partial rebuilding using ring sequencing. In the example,DS storage unit1 receives slice partial SP2 fromDS storage unit2 overLAN530aand combines slice partial SP2 with partial SP1 to produce summation SP12.DS storage unit1 sends the first summation SP12 toDS storage unit5.DS storage unit5 receives slice partial SP6 fromDS storage unit6 overLAN530cand combines slice partial SP6 with slice partial SP5 and summation SP12 to produce summation SP1256.DS storage unit3 receives summation SP1256 fromDS storage unit5 and also receives slice partial SP4 overLAN530bfromDS storage unit4.DS storage unit3 combines summation SP1256 with slice partial SP4 to generate the rebuilt data slice.
• When slice partials are combined at a site over a LAN530, the partial rebuilding process requires less transmissions over theWAN540 from the centralized rebuilding method. Though a ring sequence and a star sequence are described with respect to the partial rebuilding process, other sequences, such as a combination of a ring and star sequence, may also be implemented.
• FIGS. 28 through 31 illustrate an embodiment for the partial rebuilding process. In the example inFIGS. 28-31, a missing encoded data slice frompillar3 is rebuilt utilizing a star approach similar to the example inFIG. 26. In the example, a data segment is separated into a X pillars wherein X=6 and the threshold number T equals 4 pillars such that at least four data slices of the six data slices are needed to rebuild a missing slice. The example will illustrate utilizing a data slice frompillars1,2,4, and5 to reconstruct themissing pillar3 data slice.
• FIG. 28 illustrates a schematic block diagram of an embodiment of the partial rebuilding process atDS storage unit1.DS storage unit1 receives a partial rebuild request that requests partial rebuilding of an identified data slice S3 with an associated error, e.g. themissing pillar3 data slice. The rebuild request may identify the encoded data slice S1 stored atDS storage unit1 from the same data segment and the identified data slice S3 with an associated error. The encoded data slice S1 is one of at least T required data slices needed to reconstruct the data segment. The post-data de-manipulator96 performs any required data de-manipulation on the slice51. In addition, in an embodiment, adeslicer98 reorders the data bits, if necessary, to generate a portion of encodeddata segment550.
• The partial rebuilding process includes generating a matrix A, matrix A′ and matrix S′ by thepartial decoder504 andpartial encoder506 inDS storage unit1. Matrix A is generated by preferably first recreating approximately the same matrix used to derive the initial data slices from the data segment. For example, in an embodiment, matrix A is deterministically constructed using a special type of matrix called a Vandermond matrix. In a Vandermond matrix, each row is unique and linearly independent. Other types of matrices may also be used which have unique and linearly independent rows. The matrix A will have a number of rows equal to the number X of pillars and the number of columns equal to the threshold number T of required data slices needed to reconstruct the data segment. The X×T matrix A is thus generated to be approximately the same as the matrix used to derive the original data slices.
• To generate A′, certain rows are deleted from matrix A to generate a square matrix. For example, only a threshold number T of slices is needed to regenerate the data segment. So a number of rows equal to X−T are deleted to generate a square T×T matrix with T number of rows and T number of columns. In an embodiment, one of the X−T rows that are deleted includes the row corresponding to the missing slice. Once the T×T matrix is created, the inverse of this square matrix is calculated to generate the T×T matrix A′.
• To generate vector S′, the encodeddata segment550 is placed as a first element, corresponding to slice1, to generate an X×1 vector. Then, the same rows deleted in matrix A to generate matrix A′ are also deleted to generate a T×1 vector S′. In the example provided inFIGS. 28-31, the rows deleted in matrix A and vector S′ arerow3 corresponding to the missing slice and the last row corresponding to slice6. For graphical illustration, theserows3 and6 are shown as blank in matrix A′ and vector S′ inFIGS. 28-31. To more clearly show the calculations, symbolic letters are inserted into matrix A′ rather than the calculated elements for the inverse matrix.
• In the next step, the portion of the encodeddata segment550 is received by thepartial decoder504. The partial decoder508 multiplies T×T matrix A′ with T×1 vector S′ to generate a portion of decodeddata segment552, vector d=aS1, bS1, dS1, eS1. Thepartial encoder506 multiplies only a row of matrix A corresponding to the missing slice with vector d. In this example,row3 corresponding to missingslice3 of matrix A is multiplied with vector d to generate encoded slice partial554 for missingpillar3 frompillar1, e.g. SP3,1=9aS1+10bS1+11dS1+12eS1.
• FIG. 29 a schematic block diagram of an embodiment of the partial rebuilding process atDS storage unit2.DS storage unit2 generates an encoded slice partial SP3,2 frompillar2, slice S2 which is one of at least the number T required data slices needed to reconstruct the data segment.DS storage unit2 receives a partial rebuild request that requests partial rebuilding of an identified data slice S3 with an associated error, e.g. themissing pillar3 data slice. The rebuild request may identify the encoded data slice S2 and the identified data slice S3 with an associated error. The post-data de-manipulator96 performs any required data de-manipulation on the slice S2. In addition, in an embodiment, adeslicer98 reorders the data bits, if necessary, to generate a portion of encodeddata segment550. The encodeddata segment550 is placed as a second element, corresponding to slice2, in an X×1 vector and then row3 corresponding to the missing slice and the last row corresponding to slice6 are deleted to generate T×1 vector S′.
• As explained above, matrix A and matrix A′ are generated by thepartial decoder504 andpartial encoder506 inDS storage unit2. The partial decoder508 multiplies T×T matrix A′ with T×1 vector S′ to generate a portion of decodeddata segment552, vector d=gS2, hS2, jS2, kS2. Thepartial encoder506 multiplies only a row of matrix A corresponding to the missing slice with vector d. In this example,row3 corresponding to missingslice3 of matrix A is multiplied with vector d to generate encoded slice partial554 for missingpillar3 frompillar2, e.g. SP3,2=9gS2+10hS2+11jS2+12kS2.
• In this example, one of the DS storage units atsite1, such asDS storage unit1 or2, combines SP3,1 and SP3,2 to generate the summation SP3,1+SP3,2. The DS storage unit then transmits the summation SP3,1+SP3,2 tosite2. In another embodiment, the slice partials can be combined with other slice partials in other sequences and orders until the threshold number T of slice partials have been summed to generate the rebuilt data slice.
• FIG. 30 a schematic block diagram of an embodiment of the partial rebuilding process atDS storage unit5.DS storage unit5 generates an encoded slice partial SP3,5 frompillar5, slice S5 which is one of at least the number T required data slices needed to reconstruct the data segment.DS storage unit5 receives a partial rebuild request that requests partial rebuilding of an identified data slice S3 with an associated error, e.g. themissing pillar3 data slice. The rebuild request may identify the encoded data slice S5 and the identified data slice S3 with an associated error. The post-data de-manipulator96 performs any required data de-manipulation on the slice S5. In addition, in an embodiment, adeslicer98 reorders the data bits, if necessary, to generate a portion of encodeddata segment550. The encodeddata segment550 is placed as a fifth element, corresponding to slice5, in an X×1 vector and then row3 corresponding to the missing slice and the last row corresponding to slice6 are deleted to generate T×1 vector S′.
• As explained above, matrix A and matrix A′ are generated by thepartial decoder504 andpartial encoder506 inDS storage unit5. The partial decoder508 multiplies T×T matrix A′ with T×1 vector S′ to generate a portion of decodeddata segment552, vector d=sS5, tS5, vS5, wS5. Thepartial encoder506 multiplies only a row of matrix A corresponding to the missing slice with vector d. In this example,row3 corresponding to missingslice3 of matrix A is multiplied with vector d to generate encoded slice partial554 for missingpillar3 frompillar5, e.g. SP3,5=9sS5+10tS5+11vS5+12wS5.DS storage unit5 transmits partial result SP3,5 tosite2.
• FIG. 31 a schematic block diagram of an embodiment of the partial rebuilding process atDS storage unit4.DS storage unit4 generates an encoded slice partial SP3,4 frompillar4, slice S4 which is one of at least the number T required data slices needed to reconstruct the data segment.DS storage unit4 receives a partial rebuild request that requests partial rebuilding of an identified data slice S3 with an associated error, e.g. themissing pillar3 data slice. The rebuild request may identify the encoded data slice S4 and the identified data slice S3 with an associated error. The post-data de-manipulator96 performs any required data de-manipulation on the slice S4. In addition, in an embodiment, adeslicer98 reorders the data bits, if necessary, to generate a portion of encodeddata segment550. The encodeddata segment550 is placed as a fourth element, corresponding to slice4, in an X×1 vector and then row3 corresponding to the missing slice and the last row corresponding to slice6 are deleted to generate T×1 vector S′.
• As explained above, matrix A and matrix A′ are generated by thepartial decoder504 andpartial encoder506 inDS storage unit5. The partial decoder508 multiplies T×T matrix A′ with T×1 vector S′ to generate a portion of decodeddata segment552, vector d=mS4, nS4, pS4, qS4. Thepartial encoder506 multiplies only a row of matrix A corresponding to the missing slice with vector d. In this example,row3 corresponding to missingslice3 of matrix A is multiplied with vector d to generate encoded slice partial554 for missingpillar3 frompillar4, as SP3,4=9mS4+10nS4+11pS4+12qS4.
• DS storage unit3 receives the results and adds summation SP3,1+SP3,2 (from site1) with slice partial SP3,5 (from site3) with slice partial SP3,4 (from site2) to generate the rebuilt slice S3 forpillar3.DS storage unit3 stores the rebuilt slice S3 inDS storage unit3 or another available storage unit. WhenDS storage unit3 is not available, another DS storage unit or storageintegrity processing unit20 may receive the results and generate the rebuilt slice S3 forpillar3.
• The example of the partial rebuilding process inFIGS. 28-31 requires two WAN transmissions (e.g., SP3,1+SP3,2 fromsite1 and SP3,5 from site3). A centralized rebuilding approach in this example would require four WAN transmissions to transmit four of the threshold number T of data slices from remote DS storage units to storageintegrity processing unit20 and then another WAN transmission to send the rebuilt data slice from the storageintegrity processing unit20 to theDS storage unit36 for a total of five WAN transmission. As such, the partial rebuilding approach described herein decreases the number of WAN transmissions lowering the network bandwidth utilization compared to a centralized rebuilding approach.
• FIG. 32 illustrates a logic flow diagram of an embodiment of amethod560 for a partial rebuilding. An encoded data slice is identified for rebuilding at aDS storage unit36 instep562. The identified data slice is one of X data slices generated from a data segment using an error encoding dispersal function. TheDS storage unit36 receives one or more sums of at least a threshold number T of encoded slice partials instep564. The encoded slice partials are generated from a corresponding one of a plurality of the encoded data slices. TheDS storage unit36 then generates the rebuilt encoded data slice corresponding to the identified data slice from the one or more sums of at least the number T of encoded slice partials instep566.
• FIG. 33 illustrates a logic flow diagram of another embodiment of amethod580 for partial rebuilding. Instep582, aDS storage unit36 receives a partial rebuild request from anotherDS storage unit36 or in another embodiment from storageintegrity processing unit20 orDS managing unit18 oruser device12,14 that includes for example, an identification of an identified data slice for rebuilding. The request may also include an identification of an encoded data slice stored at theDS storage unit36 from the same data segment, wherein the encoded data slice is one of a threshold number T of data slices required to reconstruct the data segment. TheDS storage unit36 generates a slice partial from the one of a threshold number T of data slices required to reconstruct the data segment instep584. TheDS storage unit36 then transmits the slice partial to the requesting unit or other identified destination instep586.
• As may be used herein, the terms “substantially” and “approximately” provides an industry-accepted tolerance for its corresponding term and/or relativity between items. Such an industry-accepted tolerance ranges from less than one percent to fifty percent and corresponds to, but is not limited to, component values, integrated circuit process variations, temperature variations, rise and fall times, and/or thermal noise. Such relativity between items ranges from a difference of a few percent to magnitude differences. As may also be used herein, the term(s) “coupled to” and/or “coupling” and/or includes direct coupling between items and/or indirect coupling between items via an intervening item (e.g., an item includes, but is not limited to, a component, an element, a circuit, and/or a module) where, for indirect coupling, the intervening item does not modify the information of a signal but may adjust its current level, voltage level, and/or power level. As may further be used herein, inferred coupling (i.e., where one element is coupled to another element by inference) includes direct and indirect coupling between two items in the same manner as “coupled to”. As may even further be used herein, the term “operable to” indicates that an item includes one or more of power connections, input(s), output(s), etc., to perform one or more its corresponding functions and may further include inferred coupling to one or more other items. As may still further be used herein, the term “associated with”, includes direct and/or indirect coupling of separate items and/or one item being embedded within another item. 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 thatsignal1 has a greater magnitude thansignal2, a favorable comparison may be achieved when the magnitude ofsignal1 is greater than that ofsignal2 or when the magnitude ofsignal2 is less than that ofsignal1.
• The present invention has also been described above with the aid of method steps illustrating the performance of specified functions and relationships thereof. The boundaries and sequence of these functional building blocks and method steps have been arbitrarily defined herein for convenience of description. Alternate boundaries and sequences can be defined so long as the specified functions and relationships are appropriately performed. Any such alternate boundaries or sequences are thus within the scope and spirit of the claimed invention.
• The present invention has been described above with the aid of functional building blocks illustrating the performance of certain significant functions. The boundaries of these functional building blocks have been arbitrarily defined for convenience of description. Alternate boundaries could be defined as long as the certain significant functions are appropriately performed. Similarly, flow diagram blocks may also have been arbitrarily defined herein to illustrate certain significant functionality. To the extent used, the flow diagram block boundaries and sequence could have been defined otherwise and still perform the certain significant functionality. Such alternate definitions of both functional building blocks and flow diagram blocks and sequences are thus within the scope and spirit of the claimed invention. One of average skill in the art will also recognize that the functional building blocks, and other illustrative blocks, modules and components herein, can be implemented as illustrated or by discrete components, application specific integrated circuits, processors executing appropriate software and the like or any combination thereof.

Claims (20)

What is claimed is:

1. A storage integrity processing unit in a dispersed storage network, comprises:

a network interface for interfacing with a plurality of storage units in the distributed storage network; and

a grid module including:

a rebuild agent operably coupled to:

receive an identification of an identified data slice that requires rebuilding from a corresponding one of the plurality of storage units, wherein the identified data slice is one of a plurality of encoded data slices generated from a data segment using an error encoding dispersal function; and

retrieve at least a number T of the plurality of encoded data slices from the plurality of storage units, wherein the number T corresponds to a number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function; and

a rebuild module operably coupled to reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment using the error encoding dispersal function.

2. The storage integrity processing unit ofclaim 1 further comprising:

a rebuild queue operably coupled to store the identification of the identified data slice that requires rebuilding; and

wherein the rebuild agent is further operably coupled to select the identified data slice for rebuilding from the rebuild queue based on one of: a prioritization algorithm and a first in first out (FIFO) order.

3. The storage integrity processing unit ofclaim 1 further comprising:

a slice queue operably coupled to store the rebuilt encoded data slice; and

a slice agent operably coupled to select the rebuilt encoded data slice for storage from the slice queue based on one of: a prioritization algorithm and a first in first out (FIFO) order.

4. The storage integrity processing unit ofclaim 3, wherein the slice agent is further operably coupled to:

determine whether the corresponding one of the plurality of storage units is available for storage of the reconstructed data slice; and

when the corresponding one of the plurality of storage units is available, assign the rebuilt encoded data slice for storage to the corresponding one of the plurality of storage units.

5. The storage integrity processing unit ofclaim 3, wherein the slice agent is further operably coupled to:

determine whether the rebuilt encoded data slice is an appropriate version; and

when the rebuilt data slice is an appropriate version, assign the reconstructed data slice for storage to the corresponding one of the plurality of storage units.

6. The storage integrity processing unit ofclaim 1, wherein the rebuild agent is further operably coupled to:

request the plurality of storage units to scan an address range of encoded data slices, wherein the identified data slice has an address within the address range.

7. The storage integrity processing unit ofclaim 1, wherein the rebuild module comprises:

a de-slicer module that receives at least the number T of the plurality of encoded data slices and generates an encoded data segment;

a decoder module that decodes the encoded data segment based on the error encoding dispersal function to produce a reconstructed data segment;

an encoder module that receives the reconstructed data segment and generates a re-encoded data segment based on the error coding dispersal function; and

a slicer module that generates a second plurality of encoded data slices from the re-encoded data segment, wherein the second plurality of encoded data slices includes a rebuilt encoded data slice corresponding to the identified data slice.

8. A first storage unit in a dispersed storage network, comprises:

a network interface for interfacing with at least one of: a storage integrity processing unit and one or more of a plurality of additional storage units; and

a scanning agent operably coupled to:

identify an encoded data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of encoded data slices generated from a data segment using an error encoding dispersal function and wherein the plurality of encoded data slices is stored in the first storage unit and the plurality of additional storage units;

transmit, via the network interface, an identification of the identified data slice to the storage integrity processing unit; and

receive, via the network interface, a reconstructed data slice corresponding to the identified data slice.

9. The storage unit ofclaim 8, wherein the scanning agent is further operably coupled to:

receive a request to scan an address range of encoded data slices, wherein the identified data slice has an address in the address range; and

scan the address range of encoded data slices to determine that the identified data slice requires rebuilding.

10. The storage unit ofclaim 8, wherein the scanning agent is further operably coupled to:

calculate a checksum using a hash function for the identified data slice; and

determine that the identified data slice has a corrupted data slice error based on the checksum.

11. The storage unit ofclaim 8, wherein the scanning agent is further operably coupled to:

determine a slice address for the identified data slice from a physical address table;

determine that the identified data slice is not present at the slice address; and

determine that the identified data slice has a missing slice error.

12. The storage unit ofclaim 8, wherein the scanning agent is further operably coupled to:

determine a current version number for the data segment;

compare a version number for the identified data slice with the current version number; and

when the version number is not the current version number, determine the identified data slice has a version update error.

13. A first storage unit in a dispersed storage network, comprises:

a network interface for interfacing with a plurality of additional storage units in the distributed storage network; and

a grid module operably coupled to:

identify an encoded data slice of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein the plurality of encoded data slices are generated from a data segment using an error encoding dispersal function;

retrieve at least a number T of the plurality of encoded data slices from the plurality of additional storage units, wherein the number T corresponds to a number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function;

reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment.

14. The first storage unit ofclaim 13, wherein the grid module is further operably coupled to:

transmit a request message to at least a number T of the plurality of additional storage units, wherein the request message identifies corresponding ones of the plurality of encoded data slices.

15. The first storage unit ofclaim 13, wherein the grid module is further operably coupled to:

scan an address range of encoded data slices, wherein the address range corresponds to encoded data slices stored at the first storage unit; and

identify the encoded data slice that requires rebuilding to produce the identified data slice.

16. The first storage unit ofclaim 13, wherein the grid module is further operably coupled to:

scan an address range of encoded data slices, wherein the plurality of encoded data slices has addresses within the address range and are assigned for storage in the plurality of additional storage units;

identify the encoded data slice that requires rebuilding to produce an identified data slice.

17. The first storage unit ofclaim 13, wherein the grid module is further operably coupled to:

generate an encoded data segment from at least the number T of the plurality of encoded data slices;

decode the encoded data segment based on the error encoding dispersal function to produce a reconstructed data segment;

generate a re-encoded data segment from the reconstructed data segment based on the error coding dispersal function; and

generate a second plurality of encoded data slices from the re-encoded data segment, wherein the second plurality of encoded data slices includes a rebuilt encoded data slice corresponding to the identified data slice.

18. A distributed storage integrity system in a dispersed storage network comprising:

a scanning agent operably coupled to identify an encoded data slice of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein the plurality of encoded data slices are generated from a data segment using an error encoding dispersal function;

a control unit operably coupled to:

retrieve at least a number T of the plurality of encoded data slices from the plurality of additional storage units, wherein the number T corresponds to a number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function;

reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment.

19. The system ofclaim 18, wherein the scanning agent is located in a storage unit and the control unit is located in one of: a storage integrity processing unit, a dispersed storage processing unit and a dispersed storage managing unit.

20. The system ofclaim 18, wherein the scanning agent and the control unit are located in one of a plurality of storage units.

Images