US20160062832A1 - Wide spreading data storage architecture - Google Patents

Abstract

Technology is disclosed for a data storage architecture for providing enhanced storage resiliency for a data object. The data storage architecture can be implemented in a single-tier configuration and/or a multi-tier configuration. In the single-tier configuration, a data object is encoded, e.g., based on an erasure coding method, to generate many data fragments, which are stored across many storage devices. In the multi-tier configuration, a data object is encoded, e.g., based on an erasure coding method, to generate many data segments, which are sent to one or more tiers of storage nodes. Each of the storage nodes further encodes the data segment to generate many data fragments representing the data segment, which are stored across many storage devices associated with the storage node. The I/O operations for rebuilding the data in case of device failures is spread across many storage devices, which minimizes the wear of a given storage device.

Description

TECHNICAL FIELD
• Several of the disclosed embodiments relate to data storage, and more particularly, to data storage architecture for enhanced storage resiliency.
BACKGROUND
• Commercial enterprises (e.g., companies) and others gather, store, and analyze an increasing amount of data. The trend now is to store and archive almost all data before making a decision on whether or not to analyze the stored data. Although the per unit cost associated with storing data has declined over time, the total costs for storage has increased for many companies because of the volumes of stored data. Hence, it is important for companies to find cost-effective ways to manage their data storage environments for storing and managing large quantities of data. There are several problems with traditional approaches to capacity storage. Most traditional storage systems have difficulty scaling to support billions of values, which is far small than the trillions of objects that customers are storing today.
• Traditional data protection mechanisms, e.g., RAID, are increasingly ineffective in petabyte-scale systems as a result of: larger drive capacities (without commensurate increases in throughput), larger deployment sizes (mean time between faults is reduced) and lower quality drives. The trends from the hard drive vendors are making traditional RAID increasingly difficult to implement, and are requiring complex techniques, e.g., triple parity, declustering. Some of the storage device trends that push away from traditional data protection mechanisms include: increasing drive sizes, lower I/O limits on drives, varying latency (which can slow I/O), varying capacity (within a given model/drive line, which can increase inefficiency of traditional RAID, lower drive reliability (increased failure rates, and more intense workload-triggered failures). Thus, the traditional data protection mechanisms are ill-suited for the emerging capacity storage market needs.
• Further, the current data storage systems have complex data protection mechanisms, which typically involve performing a significant amount of I/O on the storage devices in order to provide a specified storage resiliency. This intensive I/O for protection purposes together with the I/O performed for providing data access to the customers wears the storage device much faster and therefore, decreases the lifespan of the device rapidly. In order to maintain the same storage resiliency, the storage devices may have to be replaced with new ones regularly, which can drive up the storage costs.
• In an object based storage system, certain meta-data, e.g., object size, creation date, owner, etc., are maintained for each object. In most of the current object storage systems, this metadata is kept in a database separate from the object data. Typically, this database is maintained in one or more different servers, e.g., meta-data servers. Ensuring that the objects themselves are consistent with the metadata in the metadata server is a difficult problem. The metadata servers themselves can become a bottleneck in the storage system, since they have to deal with updates every time an object is created, modified, or accessed. Typically, there is more than one meta-data server in order to address this bottleneck, but also to make sure that the meta-data is durable (not lost). The more such meta-data servers there are, the bigger the problem to keep them consistent with one another as well as the objects themselves.
BRIEF DESCRIPTION OF THE DRAWINGS
• FIG. 1A is a perspective plan view of a storage shelf and components therein, consistent with various embodiments.
• FIG. 1B is a perspective view of a storage rack of storage shelves, consistent with various embodiments.
• FIG. 2 is a block diagram of a storage shelf, in accordance with various embodiments.
• FIG. 3 is a block diagram illustrating an environment in which a data storage architecture can be implemented, consistent with various embodiments.
• FIG. 4 is a block diagram of a storage system implementing wide spreading storage architecture, consistent with various embodiments.
• FIG. 5 is a block diagram for storing metadata of a data object with the data object in a storage system ofFIG. 4, consistent with various embodiments.
• FIG. 6 is a flow diagram of a process of storing data to an object-based storage system using the wide spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 7 is a flow diagram of a process of reading data from an object-based storage system using the wide spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 8 is a flow diagram of a process of rebuilding data fragments of a data object in the wide spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 9 is a flow diagram of a process of storing metadata of a data object with the data object in the wide spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 10 is a flow diagram of a process of processing metadata and data fragments of a data object in the wide spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 11 is a block diagram of a storage system implementing hierarchical spreading storage architecture, consistent with various embodiments.
• FIG. 12 is a block diagram for storing metadata of a data object with the data object in a storage system ofFIG. 11, consistent with various embodiments.
• FIG. 13 is a flow diagram of a process of storing data to an object-based storage system using the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 14 is a flow diagram of a process of reading data from an object-based storage system using the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 15 is a flow diagram of a process of rebuilding data fragments of a data object in the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 16 is a flow diagram of a process of rebuilding data segments of a data object in the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 17 is a flow diagram of a process of deferred rebuilding of data segments of a data object in the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 18 is a flow diagram of a process of processing metadata and data fragments of a data object in the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology.
• FIG. 19 is a block diagram of a computer system as may be used to implement features of some embodiments of the disclosed technology.
DETAILED DESCRIPTION
• Technology is related to a data storage architecture for providing enhanced storage resiliency. Storage resiliency or data durability can be defined as a resistance to loss of one or more storage devices storing a portion of a data object or as a resistance to loss of one or more portions of the data object. The data storage architecture can be implemented in a single-tier configuration (also referred to as “wide spreading storage architecture”) and/or a multi-tier configuration (also referred to as “hierarchical spreading storage architecture”). In either of the architecture, additional redundant portions of the data object are generated and stored across a number of storage devices, e.g., to provide storage resiliency for the data object. In some embodiments, the number of redundant portions generated depends on a specified storage resiliency. In some embodiments, the redundant portions are generated by encoding the data object based on an erasure coding method. The encoding of the data object generates a number of data object fragments, which include redundant fragments. The encoded data fragments are stored across various storage devices.
• In the single-tier configuration of the data storage architecture, a storage system includes a number of storage devices, for example, hundreds or thousands of storage devices. A data object can be split into a number of fragments and stored across the storage devices. In some embodiments, the data object is encoded based on an erasure coding method to generate a number of fragments. The fragments are distributed across the storage devices. In some embodiments, the storage resiliency of the data object depends on a storage layout of the fragments. For example, if most of the fragments are stored on the same storage device or storage devices in a same storage shelf, the storage resiliency can be lower, as loss of the storage device or the storage shelf can result in higher probability of data loss. In another example, spreading the fragments widely across a large number of storage devices or storage shelves can have a better storage resiliency.
• The number of encoded data fragments generated depends on a specified storage resiliency. In some embodiments, a ratio of the total number of fragments “n” generated to a minimum number of fragments “k” required for reconstructing the object is a function of the specified storage resiliency. For example, if n/k is 130%, then the storage resiliency is 30%. That is, the storage system can tolerate or resist loss of 30% of the data fragments without losing the data object. If the number of storage devices is more than n, the storage system can tolerate or resist loss of up to n of storage devices without losing the data. To obtain a storage resiliency of 30%, the storage system generates 30% redundant fragments for the purposes of data protection. For example, if the minimum number of fragments, k, is “1000,” then the total number of fragments generated, n, is “1300”, and the same system above would be able to tolerate “300” storage devices failing before data can be lost. This illustrates the importance to data protection of having a large n. The n data fragments are then spread widely across the storage devices. The storage resiliency can also be represented in the form of equation, n=k+m, where “k” is the original amount of data fragments or the minimum number of data fragments required to regenerate or rebuild the data object, and variable “m” stands for the extra or redundant fragments that are added to provide protection from failures. The variable “n” is the total number of fragments created after the encoding process. The data object can be reconstructed, e.g., in response to a request from a client system, by obtaining at least k encoded data fragments and decoding those to regenerate the data object.
• In some embodiments, such storage resiliency can also be provided to metadata of the data object. The metadata of the data object can be stored with the data object and spread across various storage devices. This eliminates the need to store the metadata of the data objects in a separate repository from that of the data objects.
• The single-tier storage architecture provides a number of benefits over existing architectures, e.g., RAID storage architecture. For example, in the single-tier architecture a write and/or read is spread across a large number of storage devices as opposed to a small set of storage devices in RAID. The writes and reads of the data fragments can be performed in parallel across the storage devices. Additionally, the number of reads performed on the storage devices can be further minimized as only a subset of the total number of data fragments is required to be read for regenerating the data object, thereby increasing a lifespan of the storage devices and lowering latency of access.
• Further, the number of read-write operations performed on a particular storage device to regenerate the data fragments due to loss of one or more storage devices is minimized as the reads and writes are spread across the storage devices. For example, if a set of data fragments are lost due to failure of a storage device, the set of data fragments can be reconstructed by obtaining at least k data fragments from the remaining of the storage devices and generating the replacement data fragments as a function of the obtained data fragments. In some embodiments, the k data fragments are obtained from a first set of storage devices and the replacement data fragments are stored on a different set of storage devices, which distributes the read/write operations across different set of storage devices, thereby minimizing the read-write operations on a particular storage device and increasing the lifespan of the particular storage device.
• Additionally, in the single-storage architecture, the mean-time-to-repair, which is how quickly the failed drive has to be repaired and the data stored in the failed drive to be reconstructed in order to provide a certain storage resiliency, is lower than that of current storage systems, e.g., RAID. Continuing with the above example of 30% storage resiliency with m equal to “300”, the storage system can withstand loss of up to “300” drives. So the repair process can defer operation until a high percentage of those drives have failed. Similarly, the mean time between failure, which is a statistical measure of the time until a failure occurs, in the single-tier storage architecture is higher than that of current storage systems, e.g., RAID. For example, as described above since the storage system distributes the read/write operations across different sets of storage devices, the read-write operations on a particular storage device is minimized, which increases the lifespan of the particular storage device.
• In the multi-tier configuration of the data storage architecture, the storage system includes a number of storage computer nodes which are each associated with a set of storage devices. The storage system encodes a data object into a number of data segments and distributes them to a number of storage computer nodes. Each of the storage computer nodes further encodes the data segment into a number of fragments and stores the fragments across storage devices associated with the storage computer node. For example, the storage system can encode the data object into “16” segments and send each of the “16” segments to different storage computer nodes. Each of the storage computer nodes can encode, independent of the other storage computer nodes, the segment into “16” fragments and store them across a set of storage devices associated with the storage computer node. The storage system can distribute the segments to a selected set of storage computer nodes and store the fragments at a selected set of storage devices based on a storage layout of the data object. The storage layout can be specified by a user, e.g., an administrator of the storage system, or calculated automatically based on operational characteristics of the storage system, e.g., capacity, load, wear, age and health.
• The storage resiliency in multi-tier configuration of the data storage architecture is distributed between the tiers. For example, if storage resiliency in two level storage architecture is 30%, then the first tier of storage computer nodes could offer 15% storage resiliency, with the second tier of storage devices offering 15% storage resiliency. In some embodiments, this can mean that the storage system can generate 15% extra segments and 15% extra fragments for protection purposes.
• In some embodiments, such storage resiliency can also be provided to metadata of the data object. The metadata of the data object can be stored with the data object and spread across various storage devices, which eliminates the need to store the metadata of the data objects in a separate repository from that of the data objects. For example, the metadata can be prefixed to the segments and/or fragments and stored across various storage devices.
• One of the advantages of multi-tier storage architecture is localized data regeneration process. For example, if a storage device of a particular storage computer node fails, a fragment of a particular segment stored on the failed storage device can be regenerated using other fragments of the segment stored at other storage devices of the storage computer node. The storage system may not have to obtain fragments from other storage computer nodes. After the replacement fragment is generated, it can be stored at one of the remaining storage devices of the storage computer node. The reads and writes are restricted to the storage devices of a particular storage computer node. By restricting the reads and writes to the local storage devices of a storage computer node, the data traffic in the network, e.g., between storage computer nodes, is minimized, as is the amount of data that must be read from storage devices.
• The storage system can store the data object across two or more tiers. For example, the storage system can have two tiers of storage computer nodes, where a first tier storage computer node can be associated with a number of second tier storage computer nodes and each of the second tier storage computer nodes can be associated with a set of storage devices. The data object is split into number of segments and the segments are sent to first tier storage computer nodes, where each first tier storage computer node splits the corresponding data segment into a number of fragments and distributes the fragments to a number of second tier storage computer nodes. Each of the second tier computer storage nodes splits the data fragment to a number of sub-fragments and stores the sub-fragments across a set of storage devices associated with the second tier storage computer node.
• The storage devices of the storage system can be organized as storage shelves and storage racks, where each storage rack includes a number of storage shelves and each storage shelf includes a number of storage devices. The storage racks/shelves/devices can be distributed across various geographical locations.
Environment
• FIG. 1A is a perspective plan view of astorage shelf100 and components therein, consistent with various embodiments. Thestorage shelf100 includes an enclosure shell102 (partially shown) that encloses and protects multipledata storage devices104. Thedata storage devices104 may be hard drives, solid-state drives, flash drives, tape drives, or any combination thereof. It is noted that the term “enclose” does not necessarily require sealing the enclosure and does not necessarily require enveloping all sides of the enclosure.
• Thestorage shelf100 further includescontrol circuitry106 that manages the power supply of thestorage shelf100, the data access to and from thedata storage devices104, and other storage operations to thedata storage devices104. Thecontrol circuitry106 may implement each of its functions as a single component or a combination of separate components.
• As shown, thestorage shelf100 is adapted as a rectangular prism that sits on anelongated surface108 of the rectangular prism. Each of thedata storage devices104 may be stacked within thestorage shelf100. For example, thedata storage devices104 can stack on top of one another into columns. Thecontrol circuitry106 can stack on top of one or more of thedata storage devices104 and one or more of thedata storage devices104 can also stack on top of thecontrol circuitry106.
• In various embodiments, theenclosure shell102 encloses thedata storage devices104 without providing window openings to access individual data storage devices or individual columns of data storage devices. In these embodiments, each of thestorage shelves100 is disposable such that after a specified number of thedata storage devices104 fail, the entire cartridge can be replaced as a whole instead of replacing individual failed data storage devices. Alternatively, thestorage shelf100 may be replaced after a specified time, e.g., corresponding to an expected lifetime.
• The illustrated stacking of thedata storage devices104 in thestorage shelf100 enables a higher density of standard disk drives (e.g., 3.5 inch disk drives) in a standard shelf (e.g., a 19 inch width rack shelf). Eachstorage shelf100 can store ten of the standard disk drives. In the cases that thedata storage devices104 are disk drives, the storage shelf100A can hold the disk drives “flat” such that the spinning disks are parallel to the gravitational field.
• Thestorage shelf100 may include ahandle110 on one end of theenclosure shell102 and a data connection port112 (not shown) on the other end. Thehandle110 is attached on an outer surface of theenclosure shell102 to facilitate carrying of thestorage shelf100. Theenclosure shell102 exposes thehandle110 on its front surface. For example, thehandle110 may be a retractable handle that retracts to fit next to the front surface when not in use.
• FIG. 1B is a perspective view of astorage rack150 of storage shelves, consistent with various embodiments. The storage shelves may be instances of thestorage shelf100 illustrated inFIG. 1A. Thestorage rack150, as illustrated, includes a tray structure152 (e.g., a rack shelf) securing four instances of thestorage shelf100. Thetray structure152 can be a standard 2U 19″ deep rack mount. Thestorage rack150 may include a stack oftray structures152, each securely attached to a set ofrails162.Management devices164 may be placed at the top shelves of therack150. For example, themanagement devices164 may include network switches, power regulators, front-end storage appliances, or any combination thereof.
• FIG. 2 is a block diagram of astorage shelf200, in accordance with various embodiments. In some embodiments, thestorage shelf200 is thestorage shelf100 ofFIG. 1A. Thestorage shelf200 includes aprocessor202, anoperational memory206, aboot flash208, adata communication port210, a power management module212, storage interfaces214, anddata storage devices216.
• Theprocessor202 can be a microprocessor, a controller, an application specific integrated circuit, a field programmable gate array, or any combination thereof. Theboot flash208 is a memory device storing anoperating system218. Theprocessor202 can load theoperating system218 into theoperational memory206 and run theoperating system218. A data access application programming interface (API)service220 can execute on this operating system to provide data access over a network to thedata storage devices216 for clients (e.g., devices, applications, or systems).
• Thedata communication port210 enables thestorage shelf200 to connect with the network. For example, thedata communication port210 can be a Power-over-Ethernet module that connects to an Ethernet cable to both establish a network connection with the network and power thestorage shelf200.
• In various embodiments, thestorage shelf200 only turns on a subset (hereinafter the “active set”) ofdata storage devices216 at a time. The active set can be a single data storage device or more than one data storage devices. The dataaccess API service220 can determine the membership of the active set depending on client requests received through the network. A client can either specifically request access to a data storage device or request a data range for the dataaccess API service220 to determine which data storage device stores the data range.
• The power management module212 provides electronic circuitry to switch on and off components of thestorage shelf200, e.g., to activate only one subset of the data storage devices at a time. The power management module212 can receive instructions from the data processing module202 (e.g., as part of the data access API service220) to provide power to the designated active set, including a subset of the storage interfaces214 that enables data access to the active set. Once power is supplied to the designated active set, thestorage controller222 can facilitate communicate between thedata processing module202 through thestorage interface214 to the data storage devices.
• FIG. 3 is a block diagram illustrating an environment in which the data storage architecture can be implemented, consistent with various embodiments. Theenvironment300 includes a number of storage devices, e.g.,storage device304, which are organized as a number ofstorage shelves306a-n(collectively referred to as “storage subsystem306”). In some embodiments, each of the storage shelves in thestorage subsystem306 can be similar to thestorage shelf100 ofFIG. 1A and each of the storage devices, including thestorage device304, can be similar to thedata storage devices104 or thedata storage devices216 ofFIG. 2. Further, thestorage shelves306a-ncan be part of one or more storage racks, e.g.,storage rack150. Thestorage subsystem306 can be spread across various geographical locations.
• Theenvironment300 includes one or more front-end subsystem310 that facilitates storing and/or retrieving data from thestorage subsystem306. The front-end subsystem310 processes the read/write requests from clients312a-c(collectively referred to as “clients312”). In some embodiments, thestorage subsystem306 is implemented as an object storage system, which manages data as data objects. The front-end subsystem310 stores the data received from the clients as data objects in thestorage subsystem306. The front-end subsystem310 can receive the data from the clients as data objects or in other formats. If the front-end subsystem310 receives the data in other formats, it can convert the data into data objects before storing the data in thestorage subsystem306. In some embodiments, the front-end subsystem310 also stores the metadata of the data with the data objects.
• Theenvironment300 supports both single-tier configuration and multi-tier configuration of the data storage architecture. In the single-tier storage architecture, the front-end subsystem310 encodes the data object, e.g., received from a client, to generate a number of data fragments and stores the data fragments across one or more of the storage devices of thestorage subsystem306. In some embodiments, the front-end subsystem encodes the data object based on an erasure coding method. In some embodiments, an erasure coding method encodes the data object to generate n fragments. The n fragments include some redundant fragments which are generated for storage resiliency/data protection purpose. The erasure coding requires at least k out of n fragments to generate the data object. In some embodiments, the ratio of n to k indicates a storage resiliency of the data object.
• In the multi-tier storage configuration, theenvironment300 includes one or more tiers of hierarchical storage nodes, e.g., hierarchical storage nodes314-318. Each of the hierarchical storage nodes314-318 can be associated with a set of storage devices. For example, thehierarchical storage node314 is associated with storage devices fromstorage shelves306aand306b, thehierarchical storage node316 is associated with storage devices fromstorage shelf306c, and thehierarchical storage node318 is associated with storage devices fromstorage shelves306dand306e.
• In the multi-tier storage configuration, the front-end subsystem310 encodes the data object, e.g., based on erasure coding, to generate a number of data segments and distributes them to a number of hierarchical storage nodes, e.g., hierarchical storage nodes314-318. Each of the hierarchical storage nodes314-318 further splits the data segment into a number of fragments and stores the fragments across storage devices associated with the hierarchical storage node. For example, the front-end subsystem310 can split the data object into “3” segments and send each of the “3” segments to different hierarchical storage nodes314-318. Each of the hierarchical storage nodes314-318, e.g.,hierarchical storage nodes314 can split, independent of the other hierarchical storage nodes, the segment into “16” fragments and store them across a set of associated storage devices, e.g., storage devices fromstorage shelves306aand306b. The segments and fragments are distributed to a selected set of hierarchical storage nodes and storage devices, respectively, based on a storage layout of the data object. The storage layout can be specified by a user, e.g., an administrator of the storage system, or calculated automatically based on operational characteristics of the storage system, such as capacity, load, wear, age and health.
• When a client system, e.g.,client312a, requests to access the data object, a front-end subsystem310 determines the storage layout of the data segments, requests the identified hierarchical storage nodes, e.g., one or more of the hierarchical storage nodes314-318, to obtain the fragments of a segment from the storage devices and decode them to generate the segment, and decodes the segments to generate the data object. The front-end subsystem310 returns the data object to theclient312a. In some embodiments, the front-end subsystem310 obtains at least the minimum number of segments required to regenerate the data object and the hierarchical storage nodes obtain at least the minimum number of fragments required to regenerate the data segment.
• In some embodiments, both the single-tier configuration and multi-tier configuration of the data storage architecture can be implemented in the same storage system as illustrated in theenvironment300. Further, in some embodiments, one of the two configurations is automatically and/or dynamically chosen for performing the read/write operations. A particular configuration can be selected based on a number of factors, e.g., type of data to be written, a client from whom the data is received, included metadata, etc. In some embodiments, the front-end subsystem310 is configured to select the particular configuration based on the above factors.
• FIG. 4 is a block diagram ofstorage system400 implementing wide spreading storage architecture, consistent with various embodiments. In some embodiments, thestorage system400 can be implemented in theenvironment300 ofFIG. 3. Thestorage system400 includes the front-end subsystem310 that facilitates data storage and retrieval from thestorage subsystem306. The front-end subsystem310 can be one or more computer systems (e.g., thecomputing device1800 ofFIG. 18), having either a shared nothing architecture or a shared database architecture, connected to thestorage subsystems306 over a network (e.g., a global network or a local network). The front-end subsystem310 can be on a separate rack from thestorage subsystem306, or can be combined with thehierarchical storage node314 orstorage shelf306.
• The front-end subsystem310 includes aprotocol interfaces module406. The protocol interfacesmodule406 defines one or more functional interfaces that applications and devices use to store, retrieve, update, and delete data elements from thestorage system400. For example, theprotocol interfaces module406 can implement a Cloud Data Management Interface (CDMI), a Simple Storage Service (S3) interface, or both. The front-end subsystem310 includes astaging area408. Thestaging area408 is a memory space implemented by one or more data storage devices within or accessible to the front-end subsystem310. For example, thestaging area408 can be implemented by solid-state drives, hard disks, volatile memory, or any combination thereof. Thestaging area408 can maintain anobject namespace410 to facilitate client interactions through theprotocol interfaces module406. Theobject namespace410 manages a set of data container identifiers, e.g., object identifiers of data received from clients of the front-end subsystem310. Thestaging area408 also maintains afragment namespace412 corresponding to theobject namespace410. Thefragment namespace412 manages a set of fragment identifiers, each corresponding to a data fragment stored in thestorage subsystem306. Thestaging area408 can store amapping structure414 that stores associations between the data container identifiers of theobject namespace410 and the fragment identifiers of thefragment namespace412.
• In some embodiments, the front-end subsystem310 can be implemented as a distributed computing network including multiple computing nodes (e.g., computer servers). Each computing node can include an instance of thestaging area408. The namespaces (e.g., theobject namespace410 and the fragment namespace412) of eachstaging area408 can be implemented either as a share-nothing database or a shared database.
• Thestaging area408 can also serve as a temporary cache to process payload data from a write request received at theprotocol interfaces module406. Therequest module416 receives read/write requests from the clients of thestorage system400. The front-end subsystem310 processes an incoming write request by performing a number of storage efficiency processes on the payload data of the write request prior to sending the payload data into persistent storage in thestorage subsystem306. In some embodiments, the storage efficiency processes include deduplication, compression, fragmentation, erasure coding and fragment encryption of the payload data.
• Thestorage processing module430 performs the deduplication process on the payload data, which removes duplicate data portions from the payload data. Thestorage processing module430 can use a number of deduplication techniques for deduplicating the payload data. Thestorage processing module430 can compress the payload data, e.g., to reduce the storage space occupied by the payload data. The storage processing module can implement one or more compression algorithms for compressing the payload data.
• The encode/decode module418 fragments the payload data into a number of fragments, which includes redundant fragments for the purpose of data protection. In some embodiments, the encode/decode module418 performs the encoding based on one or more erasure coding techniques. In some embodiments, erasure coding is a method of data protection in which payload data is broken into fragments, expanded and encoded with redundant data fragments. For example, payload data can be broken into k fragments and erasure coded data to generate n fragments, where n>k, such that the payload data can be recovered from a subset of the n, e.g., at least k fragments.
• Thestorage processing module430 can further encrypt the data fragments using one or more encryption techniques to generate encrypted data fragments. In some embodiments, thestorage processing module430 encrypts the fragments for data security purposes.
• Note that the order of execution of storage efficiency processes is not restricted to the order described above. Alternative embodiments may perform these storage efficiency processes in a different order, and some processes may be removed, moved, added, subdivided, combined, and/or modified to provide alternatives or sub combinations.
• Thestorage layout module420 determines the storage layout of the data fragments. The storage layout identifies one or more of the storage racks, storage shelves of a rack and storage devices of a storage shelf the data fragments have to be stored in. In some embodiments, thestorage layout module420 determines the optimal layout of fragments to meet the service level object (SLO) promised to the client and/or to maximize storage resiliency, and sends the fragments to the selected storage devices of thestorage subsystem306 for storage. In some embodiments, a best storage layout stores each of the data fragments in a different storage device of thestorage subsystem306 to provide the best storage resiliency. In some embodiments, a worst storage layout stores all of the data fragments in the same storage device of thestorage subsystem306. Typically, thestorage layout module420 is configured to distribute the fragments across the storage devices as widely as possible, that is, to store distinct fragments on distinct storage devices.
• In some embodiments, thestorage layout module420 selects the storage devices on a random basis. In some embodiments, thestorage layout module420 selects the storage devices on a random weighted basis. Thestorage layout module420 can weigh the storage devices based on a number of factors, e.g., available storage capacity, a write latency of the storage device, a read latency of the storage device, a type of the storage device. For example, thestorage layout module420 can randomly select the storage devices from a set of storage devices that have at least some specified percentage of storage capacity free. In some embodiments, the random weighted basis attempts to store the data fragments evenly across the available storage devices. For example, one type of weighting is to decrease the weight if there are already a specified number of fragments stored on the storage device. In some embodiments, the random weighted basis randomly identifies the storage devices at which the encoded data fragments are to be stored as a function of decreasing the risk of data loss. For example, if a particular geographical region is prone to higher number of device failures, then the storage devices in that geographical region may be weighted less so that a lower number of fragments are written to the storage devices in that geographical region.
• In some embodiments, thestorage layout module420 can select the storage devices based on parameters defined by a user, e.g., metadata, a client of thestorage system400, and/or an administrator of thestorage system400.
• The following paragraphs describe additional details of writing data to thestorage subsystem306 in wide spreading storage architecture.
• When a client, e.g.,client312a, sends a write request to thestorage system400, therequest module416 receives the request and extracts the data object to be written from the request. Thestorage processing module430 performs a number of processes on the data object, e.g., as described above. The encode/decode module418 encodes the data to generate n fragments. The encode/decode module418 can use an erasure coding method, e.g., Reed-Solomon, FEC code, Fountain code, Raptor code, Tornado code.
• InFIG. 4, the encode/decode module418 splits the data object405 into n fragments, F₁to F_N. Thestorage layout module420 determines the storage layout of the fragments and spreads the fragments, F₁to F_Nacross the storage devices of thestorage subsystem306. For example, thestorage layout module420 determines that the fragments, F₁to F₉₉have to be sent to the storage devices of “storage shelf1,” fragments, F₁₀₀to F₁₉₉to the storage devices of “storage shelf2,” and fragments, F₂₀₀to F_Nto the storage devices of “storage shelf N.” In some embodiments, thestorage layout module420 also determines the storage devices of the storage shelves where the fragments have to be stored. After thestorage layout module420 determines the storage layout, thetransceiver module432 transmits the data fragments to the corresponding storage shelves, which store the data fragments at the storage devices. In some embodiments, the fragments can be written to the different storage devices in parallel.
• The number of fragments generated by the encode/decode module418 depends on the required storage resiliency. The storage resiliency offered can be represented as n=k+m, where variable “k” is the original amount of data fragments or the minimum number of data fragments required to regenerate or rebuild the data object, and variable “m” stands for the extra or redundant fragments that are added to provide protection from failures. The variable “n” is the total number of fragments created after the encoding process.
• Typically, in the wide spreading data storage architecture, the width to which the data object is split is wider, and the degree to which the data fragments are spread across the storage devices is wider, e.g., compared to current storage architecture such as RAID. For example, the number of fragments to which the data object is split into can be in hundreds and the number of storage devices across which the hundreds of fragments are spread across can be in the thousands to tens of thousands.
• In some embodiments, a ratio of “n” to “k” indicates the storage resiliency provided for the data object. For example, if n/k is 130%, then the storage resiliency is 30%. That is, the storage system can tolerate or resist loss of 30% of the data fragments without losing the data object. If the number of storage devices is more than n, the storage system can tolerate or resist loss of up to n of storage devices without losing the data. For example, if the minimum number of fragments, k, is “1000,” then the total number of fragments generated, n, is “1300.”, and the same system above would be able to tolerate “300” storage devices failing before data can be lost. This illustrates the importance to data protection of having a large n. To obtain a storage resiliency of 30%, the storage system generates 30% redundant fragments for the purposes of data protection. For example, if the minimum number of fragments, k, is “1000,” then “m” is “300” and n is “1300.” The n data fragments are then spread widely across “4000” storage devices.
• The object identifier of the data object and the fragment identifiers of the fragments are stored in thestaging area408 at theobject namespace410 and thefragment namespace412, respectively. Further, a mapping of the object identifier to the fragment identifiers can be stored in themapping structure414 of thestaging area408.
• When a read request arrives at thestorage system400 from theclient312afor the data object, the data object can be reconstructed by obtaining at least k number of the F_Ndata fragments and decoding them to regenerate the data object. Thetransceiver module432 obtains the storage layout of the fragments from thestorage layout module420 and obtains the data fragments from the identified storage devices of thestorage subsystem306. Thestorage layout module420 can use themapping structure414 to obtain the fragment identifiers of the data object and then determine the storage devices at which the corresponding fragments are stored.
• Thetransceiver module432 can obtain from k to n number of fragments. For example, thetransceiver module432 can stop fetching the fragments after obtaining the first k fragments. In another example, thetransceiver module432 can fetch all the n fragments but use only the first k fragments for regenerating the data object.
• Further, thetransceiver module432 can preferentially select a subset of the storage devices identified by thestorage layout module420 to obtain the fragments from. Thetransceiver module432 selects a storage device based on a number of factors, e.g., read latency of storage device, type of the storage device, number of pending read requests ahead of the current read request in a read request queue of the storage device, how far away the storage device is. Accordingly, thetransceiver module432 may not even read some of the storage devices that contain the data fragments of the data object, thereby minimizing read/write operation on the storage device. In some embodiments, thetransceiver module432 can obtain the fragments from different storage devices in parallel.
• After obtaining the data fragments, the encode/decode module418 decodes the data fragments, e.g., based on the erasure coding used to encode the data object, to generate the data object. In some embodiments, thestorage processing module430 may perform additional processes on the decoded object before returning the data object to theclient312a. For example, thestorage processing module430 can perform decompression and de-deduplication on the decoded data object if the data object was deduplicated and compressed.
• The wide spreading storage architecture provides a robust storage resiliency to the data stored in thestorage subsystem306. The wide spreading storage architecture also provides an efficient way to rebuild the data fragments in case of storage device failures. When a storage device fails, the data fragments stored at the storage device may be lost. When afailure detection module424 detects a failure or impending failure of a storage device, thefailure detection module424 requests theregeneration module428 to evacuate readable fragments or rebuild unreadable or lost data fragments to compensate for the ones that are no longer reliably stored. Theregeneration module428 facilitates rebuilding of new data fragments of a data object using the remaining data fragments of the data object stored at other storage devices. For example, if a storage device in “storage shelf2” storing the data fragments F₄-F₁₀fails, theregeneration module428 can rebuild up to new six data fragments and writes the new data fragments to any of the remaining set of storage devices. In some embodiments, theregeneration module428 rebuilds the data fragments using sufficient number of the remaining data fragments F₁-F₃and F₁₁-F_N. Theregeneration module428 can use the encoding method used to generate the initial fragments to generate the new replacement fragments.
• The failed storage device can store data fragments of one or more data objects. The fragment/segment identification module422 can determine the fragments stored on the storage device that failed, e.g., using the storage layout. Theregeneration module428 can rebuild the data fragments of all the data objects whose fragments are lost or for only a set of data objects that have lost the data fragments. For example, theregeneration module428 can rebuild the data fragments of a data object whose current storage resiliency is lesser than a specified threshold for minimum storage resiliency. The current storage resiliency is determined as a function of the remaining of “n” number of fragments and “k.” For example, if the specified threshold for minimum storage resiliency of a data object is 10% and the current storage resiliency is less than 10%, then the data fragments can be rebuilt for the data object. Further, theregeneration module428 can start rebuilding the data fragments of the data object whose current storage resiliency is lesser than the specified threshold instantaneously, e.g., in response to the failure of the storage device. Theregeneration module428 can rebuild the data fragments of other data objects whose current storage resiliency exceeds the specified threshold at a later time. In some embodiments, theregeneration module428 executes the rebuilding process as a background process of the front-end subsystem310. In some embodiments, a user, e.g., administrator of thestorage system400 can manually execute the rebuilding process.
• The wide spreading storage architecture can resist higher number of storage device failures than that of current storage systems, e.g., RAID storage system. For example, if thestorage system400 offers a storage resiliency of 30% and has a k of 1000, then thestorage system400 can resist a failure of “300” storage devices before the data is lost. So if one or more storage devices are lost, or even if an entire storage shelf/storage rack is lost, there may not be much impact on the storage resiliency. This provides a number of advantages. First, the rebuilding process may not have to be started immediately; it can be done at a later time. The storage resiliency of the lost data fragments can be repaired over time, e.g., when the work load (data read-write operations) on thestorage system400 is below a threshold, or when the current storage resiliency drops below the specified threshold, e.g., when the current storage resiliency is less than 10%—which means thestorage system400 can only tolerate failure of “200” more storage devices. That is, the wide spreading storage architecture offers a high mean time to repair, e.g., compared to RAID storage architecture.
• Second, the wide spreading storage architecture separates the rebuilding of data fragments from replacement of the failed storage devices. That is, thestorage system400 may not have to wait until the failed storage devices are replaced to rebuild the data fragments. The rebuilding process reads the data fragments of the data object from the remaining storage devices, generates new data fragments as a function of the data fragments obtained from the other storage devices, and writes the new data fragments on one or more of the remaining storage devices. Accordingly, in the wide spreading storage architecture, thestorage system400 does not have to wait for the failed storage device to be replaced to rebuild the data fragments, unlike current storage architectures, e.g., RAID storage architecture without hot spares, where a failed storage device may have to be replaced immediately upon failure.
• However, if the failed storage device is replaced immediately upon failure, thestorage system400 can use the replacement storage device as additional capacity, e.g., to store new data. Further, the replacement storage device can be of different storage capacity and/or type from that of the failed storage device.
• The wide spreading storage architecture also minimizes the number of read-write operations required per storage device for rebuilding the data fragments of a particular data object. Theregeneration module428 obtains the remaining data fragments of the particular data object from other storage devices of thestorage subsystem306. Since the data fragments are spread over a number of storage devices, the number of read operations performed for the rebuilding process is spread across many storage devices and therefore, the number of read operations performed on a particular storage device is limited. Further, in some embodiments, theregeneration module428 obtains less than the remaining number of fragments, e.g., k fragments of the remaining fragments, to rebuild the lost data fragments, which further minimizes the read operations performed on the storage devices. By minimizing the read operations on a given storage device, the wear of the storage device is minimized and the lifespan of the storage device is therefore, increased. Further, as rebuild can be deferred and performed after many failures have occurred, rebuild operations are minimized compared to architectures were rebuilds are initiated for each failure operation.
• Furthermore, after rebuilding the new data fragments, the new data fragments are written to a set of storage devices. In some embodiments, the set of storage devices to which the data is written is different from the set of storage devices from which the data fragments are read to rebuild the data fragments. Accordingly, the read-write operations performed on any given storage device is minimized, which minimizes the wear of the storage device and therefore, increases the lifespan of the storage device.
• As described above, the wide spreading storage architecture provides optimum storage resiliency to data stored in the storage devices of thestorage subsystem306 while minimizing the wear of the storage devices.
• The wide spreading storage architecture can also be used to store metadata of the data object.FIG. 5 is a block diagram500 for storing metadata of a data object with the data object in astorage system400 ofFIG. 4, consistent with various embodiments. The wide spreading storage architecture can provide the same storage resiliency to the metadata of a data object that is provided to the data object. Examples of metadata can include, object ID, object size, object owner, creation time, created by, modified by, etc. The metadata can also include client-specified metadata, e.g., author of an object, name of entity, etc. Typically, current storage architectures store metadata separate from the data object. The wide spreading storage architecture enables storing the metadata with data object, thereby eliminating the need to have a separate database for the metadata, the need to have specific infrastructure to ensure the metadata is consistent with the data, etc.
• When a write request is received, the payload data in the write request is analyzed to obtain themetadata510 and the data portion, e.g., data object405. The data object405 is then encoded, e.g., using encode/decode module418 as described with reference toFIG. 4, to generate a number of fragments505. Themetadata510 is combined with some or each of the fragments505, e.g., concatenated or prefixed to each of the fragments505, to generatecomposite fragments515. The composite fragments515 can then be stored in thestorage subsystem306 by spreading them across a number of storage devices, e.g., similar to storing the data fragments as described with reference toFIG. 4. In some embodiments, themetadata510 can be a subset of the metadata of the data object405.
• In some embodiments, by including themetadata510 with the data object, the possibility of inconsistency between themetadata510 and the data object405 is eliminated. Further, since themetadata510 is attached to the fragments505, thecomposite fragments515 can be moved across locations/storage devices without having to update themetadata510 and without risking the consistency between themetadata510 and the data object405.
• Another benefit of storing themetadata510 with the data object405 is that since a separate database and/or metadata server is not needed to maintain themetadata510, the read and write operations are relatively faster since no separate read/write is required to read/write themetadata510. In some embodiments, metadata retrieval is also simplified since a method call that is used for retrieving the data object405 can be modified to use retrieve themetadata510, which can simplify a number of functions performed related to themetadata510.
• FIG. 6 is a flow diagram of aprocess600 of storing data to an object-based storage system using wide spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess600 may be implemented inenvironment300 ofFIG. 3, and using thestorage system400 ofFIG. 4. Theprocess600 begins atblock605, and atblock610, arequest module416 of thefrontend subsystem310 receives a write request including payload data. In some embodiments, the payload data includes data portion and metadata of the data. If the data portion is not in a format suitable for storing in an object storage system, e.g.,storage subsystem306, thefrontend subsystem310 converts the data portion to the suitable format, e.g., as the data object.
• Atblock615, the encode/decode module418 encodes the data object to generate a number of encoded data fragments, e.g., encoded data fragments F1-FN. In some embodiments, the encode/decode module418 encodes the data object based on an erasure coding technique. The number of encoded data fragments generated can be expressed as a function, e.g., n=k+m, where variable “k” is the original amount of data fragments or the minimum number of data fragments required to regenerate or rebuild the data object, and variable “m” is the number of extra or redundant fragments added to provide protection from storage device failures. The variable “n” is the total number of fragments created after the encoding process.
• After the encoded data fragments are generated, a mapping of the object identifier of the data object and fragment identifiers of the encoded data fragments are stored in themapping structure414.
• In some embodiments, apart from encoding the data object to generate the fragments, various other processes may be performed on the data object, e.g., deduplication, compression, encryption. One or more of these processes can be performed by the storage processing module.
• Atblock620, thestorage layout module420 determines a storage layout for storing the encoded data fragments across a number of storage devices, e.g., storage devices ofstorage subsystem306. In some embodiments, thestorage layout module420 is configured to spread the encoded data fragments across as many storage devices as possible, e.g., to provide better storage resiliency to the data object. That is, thestorage layout module420 attempts to identify different storage devices for storing different encoded data fragments. In some embodiments, thestorage layout module420 selects the storage devices on a random basis. In some embodiments, thestorage layout module420 selects the storage devices on a random weighted basis.
• Atblock625, thetransceiver module432 transmits the encoded data fragments to the identified storage devices. For example, thetransceiver module432 can transmit the encoded data fragments to the storage shelves and/or the storage racks which contain the storage devices.
• Atblock630, the storage shelves and/or the storage racks store the encoded data fragments at the identified storage devices, and theprocess600 returns. In some embodiments, the front-end subsystem310 also stores the metadata of the data object with the data object. Additional details with respect to the process of storing the metadata are described at least with reference toFIGS. 9 and 10.
• FIG. 7 is a flow diagram of aprocess700 of reading data from an object-based storage system using wide spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess700 may be implemented inenvironment300 ofFIG. 3, and using thestorage system400 ofFIG. 4. Theprocess700 begins atblock705, and atblock710, arequest module416 of thefrontend subsystem310 receives a read request, e.g., from aclient system312a, for obtaining a data object. In some embodiments, the read request includes an object identifier of the data object.
• Atblock715, the fragment/segment identification module422, determines the encoded data fragments of the data object using the object identifier. In some embodiments, a mapping of the object identifier and the fragment identifiers of the encoded data fragments are stored in themapping structure414.
• Atblock720, thestorage layout module420 determines the storage layout of the encoded data fragments using the mapping obtained from the mapping structure. The storage layout can include identification information of the storage devices where each of the encoded data fragments is stored. In some embodiments, the storage layout information can also include identification information of the storage racks and/or storage shelves of the storage devices where the encoded data fragments are stored.
• Atblock725, thetransceiver module432 obtains sufficient number of the encoded data fragments required to generate the data object from the identified storage devices. In some embodiments, the sufficient number of encoded data fragments is k number of the encoded data fragments. In some embodiments, thetransceiver module432 can obtain k to n number of fragments. For example, thetransceiver module432 can stop fetching the fragments after obtaining the first k fragments. In another example, thetransceiver module432 can fetch all the n fragments but use only the first k fragments for regenerating the data object.
• Further, thetransceiver module432 can preferentially select a subset of the identified storage devices to obtain the fragments from. Thetransceiver module432 can select a storage device based on a number of factors, e.g., read latency of a storage device, type of the storage device, number of pending read requests ahead of the current read request in a read request queue of the storage device, a geographical location of the storage device. In some embodiments, thetransceiver module432 can obtain the fragments from different storage devices in parallel.
• After obtaining the encoded data fragments, atblock730, the encode/decode module418 decodes the encoded data fragments, e.g., based on the erasure coding method used to encode the data object, to generate the data object.
• Atblock735, thetransceiver module432 transmits the data object in response to the read request, e.g., to theclient system312a, and theprocess700 returns. In some embodiments, additional processes may be performed before decoding the data fragments. For example, thestorage processing module430 can decrypt the encoded data fragments if they were encrypted before being stored. In some embodiments, additional processes may be performed on the decoded data object before returning the data object to theclient312a. For example, thestorage processing module430 can perform decompression and de-deduplication on the decoded data object if the data object was deduplicated and compressed.
• FIG. 8 is a flow diagram of aprocess800 of rebuilding data fragments of a data object in wide spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess800 may be implemented inenvironment300 ofFIG. 3, and using thestorage system400 ofFIG. 4. In some embodiments, the data fragments stored in thestorage subsystem306 may be lost due to a failure of a storage device. Theprocess800 begins atblock805, and atblock810, afailure detection module424 of thefrontend subsystem310 detects a failure of a storage device, e.g.,storage device304. In some embodiments, the failure can be one or more of the storage device being not accessible, the storage device being physically damaged, etc.
• Atblock815, the fragment/segment identification module422 identifies the encoded data fragments that were stored at the storage device. For example, the fragment/segment identification module422 can refer to thestorage layout module420 to determine the fragments stored at the storage device that has failed. Further, the fragment/segment identification module422 identifies the one or more data objects corresponding to the identified encoded data fragments. For example, the fragment/segment identification module422 can refer to themapping structure414 to determine the data objects associated with the identified encoded data fragments.
• Atblock820, theregeneration module428 rebuilds some or all of the encoded data fragments that was stored at the storage device that failed. In some embodiments, rebuilding the data fragments include performing the method described in association with blocks821-824 for each of the identified data objects. Atblock821, theregeneration module428 computes the current storage resiliency of the data object. In some embodiments, storage resiliency is defined as a resistance to loss of one or more storage devices storing a portion of a data object or resistance to loss of one or more portions of the data object. In some embodiments, a current storage resiliency of a data object is determined as a function of the number of fragments remaining out of “n” fragments and “k.” For example, if n is “130,” k is “100,” then the number of redundant fragments, m is “30,” and therefore, the storage resiliency can be calculated as 30% (100*m/k). Note that the storage resiliency can be calculated using other functions and based on several other parameters.
• Thestorage system400 may guarantee a storage resiliency range to the clients of the storage system, for example, a minimum storage resiliency and a maximum storage resiliency. In some embodiments, the storage resiliency range is part of the SLO guaranteed to the clients. In some embodiments, thestorage system400 may not rebuild the lost data fragments until the current storage resiliency of the data object drops below the minimum storage resiliency.
• Atdetermination block822, theregeneration module428 determines if the current storage resiliency of the data object is less than the minimum storage resiliency. Continuing with the above example of a storage resiliency of 30%, if the minimum storage resiliency is 10%, then thestorage system400 can withstand loss of “20” data fragments, in which case m is “10.”
• Responsive to a determination that the current storage resiliency of the data object is not less than the minimum storage resiliency, theprocess800 returns. On the other hand, responsive to a determination that the current storage resiliency is less than the minimum storage resiliency, atblock823, thetransceiver module432 obtains sufficient number of fragments of the data object from remaining of the storage devices. Thetransceiver module432 may use the storage layout to identify the storage devices that store the data fragments of the data object. In some embodiments, thetransceiver module432 can obtain the minimum number of fragments required to rebuild the data fragments.
• Atblock824, theregeneration module428 regenerates the data fragments as a function of the obtained data fragments and stores the regenerated data fragments in at least a subset of the remaining storage devices. In some embodiments, theregeneration module428 regenerates as many data fragments as required to meet a specified storage resiliency, which can be up to the maximum storage resiliency. In some embodiments, regenerating the data fragments as a function of the obtained data fragments includes encoding the obtained data fragments to generate the new/replacement/additional data fragments. In some embodiments, regenerating the data fragments as a function of the obtained data fragments includes decoding the obtained data fragments to generate the data object and encoding the generated data object to generate the specified number of data fragments.
• FIG. 9 is a flow diagram of aprocess900 of storing metadata of a data object with the data object in wide spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess900 may be implemented inenvironment300 ofFIG. 3, and using thestorage system400 ofFIG. 4. Theprocess900 begins atblock905, and atblock910, arequest module416 of thefrontend subsystem310 receives a write request including payload data. In some embodiments, the payload data includes data portion and metadata of the data. If the data portion is not in a format suitable for storing in an object storage system, e.g.,storage subsystem306, thefrontend subsystem310 converts the data portion to the suitable format, e.g., as the data object.
• Atblock915, themetadata processing module426 analyzes the payload data to obtain the metadata of the data object, e.g.,metadata510 ofFIG. 5. Examples of metadata can include, object ID, object size, object owner, creation time, created by, modified by, etc. The metadata can also include client-specified metadata, e.g., author of an object, name of entity, etc.
• Atblock920, the encode/decode module418 encodes the data object to generate a number of encoded data pieces, e.g., segments and/or fragments. In some embodiments, the encode/decode module418 encodes the data object as described at least with reference toFIGS. 4-6.
• Atblock925, after the encoded data pieces are generated, themetadata processing module426 processes the encoded data pieces and the metadata for storage across a number of storage devices, e.g., storage devices of thestorage subsystem306, and theprocess900 returns. Additional details with respect to the method of processing the metadata are described at least with reference toFIG. 10.
• FIG. 10 is a flow diagram of aprocess1000 of processing metadata and data fragments of a data object in wide spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1000 may be implemented inenvironment300 ofFIG. 3, and using thestorage system400 ofFIG. 4. In some embodiments, theprocess1000 implements the method ofblock925 ofFIG. 9. The data piece generated in theprocess900 ofFIG. 9, e.g., inblock920, can be considered as a data fragment in the wide spreading storage architecture. Theprocess1000 begins atblock1005, and atblock1010, themetadata processing module426 combines each of the data fragments of the data object with the metadata, e.g.,metadata510, to generate composite encoded data fragments, e.g., composite encoded data fragments515. In some embodiments, combining the metadata with each of the fragments includes concatenating or prefixing the metadata to each of the fragments.
• After the composite fragments are generated, atblock1015, thetransceiver module432 transmits the composite fragments to thestorage subsystem306 for storing across a number of storage devices, e.g., similar to storing the data fragments as described at least with reference to blocks620-630 ofFIG. 6, and theprocess1000 returns. Prior to transmitting the composite fragments to thestorage subsystem306, thestorage layout module420 determines a storage layout for storing the composite data fragments across the number of storage devices, e.g., similar to determining the storage layout for storing the data fragments as described at least with reference toFIG. 4 and block620 ofFIG. 6. Thetransceiver module432 then transmits the composite data fragments to the identified storage devices.
• FIG. 11 is a block diagram ofstorage system1100 implementing hierarchical spreading storage architecture, consistent with various embodiments. In some embodiments, thestorage system1100 can be implemented in theenvironment300 ofFIG. 3. Further, in some embodiments, thestorage system1100 includes at least some of the characteristics, behavior/functionalities of thestorage system400 ofFIG. 4. In some embodiments, the wide spreading storage architecture ofstorage system400 can also be implemented in thestorage system1100. Thestorage system1100 includes the front-end subsystem310 and a tier of hierarchical storage nodes, e.g., hierarchical storage nodes314-318 that facilitate data storage and retrieval from thestorage subsystem306, which includesstorage shelves306a-n. The hierarchical storage nodes can be implemented in a similar configuration to that of the front-end subsystem310. For example, a hierarchical storage node can include the modules/components of the front-end subsystem310 depicted inFIG. 3. Note that althoughFIG. 11 depicts one tier of hierarchical storage nodes, the hierarchical spreading storage architecture can have more than one tier of hierarchical storage nodes.
• Each of the hierarchical storage nodes314-318 can be associated with a set of storage devices. For example, thehierarchical storage node314 is associated with storage devices fromstorage shelves306aand306b, thehierarchical storage node316 is associated with storage devices fromstorage shelf306c, and thehierarchical storage node318 is associated with storage devices fromstorage shelves306dand306e. In some embodiments, the hierarchical storage nodes are spread across various geographical locations. In other embodiments, the hierarchical storage nodes are integrated into each storage shelf.
• The following paragraphs describe additional details of writing data to thestorage subsystem306 in hierarchical spreading storage architecture.
• When a client, e.g.,client312a, sends a write request to thestorage system1100, therequest module416 receives the request and extracts the data object to be written from the request. The encode/decode module418 encodes the data object to generate a number of segments, e.g., “S1,” “S2,” and “S3”. In some embodiments, the encode/decode module418 can use wide spreading, or an erasure coding method directly, e.g., Reed-Solomon, FEC coding, Fountain code, Raptor code, Tornado code, to generate the segments. In some embodiments, the number of segments generated is a function of the number of hierarchical storage nodes.
• Thetransceiver module432 distributes the data segments to a number of hierarchical storage nodes, e.g., hierarchical storage nodes314-318. Thestorage layout module420 determines the storage layout of the segments, that is, the hierarchical storage nodes to which the segments have to be distributed, and thetransceiver module432 spreads the segments to the identified the hierarchical storage nodes. In some embodiments, thestorage layout module420 is configured to select different hierarchical storage nodes for different segments, e.g., to maximize storage resiliency of the data object. However, in some embodiments, more than one segment may be transmitted to a hierarchical storage node. In some embodiments, thestorage layout module420 determines the hierarchical storage nodes to which the segments have to be distributed on a random basis. The storage layout can also be specified by a user, e.g., an administrator of thestorage system1100. InFIG. 11, the segment, “S1” is sent to thehierarchical storage node314, the segment “S2” is sent to thehierarchical storage node316 and the segment “S3” is sent to thehierarchical storage node318. In some embodiments, the segments are transmitted to the hierarchical storage nodes in parallel.
• The number of segments generated by the encode/decode module418 can also depend on the required storage resiliency. The storage resiliency offered can be represented as n′=k′+m′, where variable K is the original amount of data segments or the minimum number of data segments required to rebuild the data object, and variable m′ stands for the extra or redundant segments added to provide protection from failures, e.g., failures of hierarchical storage nodes and/or storage devices associated with hierarchical storage nodes. The variable n′ is the total number of segments created after the encoding process.
• The segment identifiers of the data object may be stored in thefragment namespace412. Themapping structure414 can store a mapping of the object identifier of the data object to the segment identifiers of the segments of the data object.
• In some embodiments, prior to encoding the data object, thestorage processing module430 can perform a number of storage efficiency processes on the data object, e.g., as described at least with reference toFIG. 4.
• Each of the hierarchical storage nodes314-318 can encode, independent of the other hierarchical storage nodes, the segment, e.g., based on an erasure coding method, to generate a number of fragments of the segment. In some embodiments, the hierarchical storage node encodes the segment using an encode/decode module similar to the encode/decode module418. InFIG. 11, the segments “S1,” “S2,” and “S3,” are each encoded to generate eight fragments F1-F8. Each of the hierarchical storage node stores the fragments, F1 to F8, across the storage devices of thestorage subsystem306. In some embodiments, the techniques involved in encoding a data segment to generate the fragments of a segment and storing the fragments across the storage devices is similar to the techniques involved in encoding a data object to generate the fragments of the data object and storing the fragments across the storage devices in wide spreading storage architecture, e.g., as described at least with reference toFIGS. 4 and 6.
• For storing the fragments across a set of storage devices, the hierarchical storage node determines a storage layout of the fragments. The storage layout identifies one or more of the storage racks, storage shelves of a rack and storage devices of a storage shelf the data fragments have to be stored in. In some embodiments, the hierarchical storage node determines the storage layout of the fragments using a storage layout module similar to thestorage layout module420. After the storage layout is determined, the hierarchical storage node stores the fragments in the identified storage devices. In some embodiments, the hierarchical storage node writes the fragments to the different storage devices in parallel. In the hierarchical spreading storage architecture, the writes are more efficient than current storage systems. For example, in addition to writing the fragments of a particular segment in parallel, all the hierarchical storage nodes can write the fragments of their corresponding segments in parallel.
• The hierarchical storage node stores the segment identifier of the data segment and the fragment identifiers of the fragments of the data segment in a staging area similar to thestaging area408. Further, the hierarchical storage node stores a mapping of the segment identifier of a segment to the fragment identifiers of the segment in a mapping structure similar to themapping structure414.
• In the hierarchical spreading storage architecture, the storage resiliency provided for a data object is split across the tiers of a storage system. For example, if the storage resiliency offered for a data object by thestorage system1100 is 30%, then the first tier—hierarchical storage node314-318 provides 15% of the storage resiliency and the second tier—storage devices provided the other 15%. The amount of storage resiliencies provided by each of the tiers can be configurable. However, the sum of storage resiliencies offered by the tiers may not exceed the total storage resiliency offered by thestorage system1100.
• Referring to the read requests, when a read request arrives at thestorage system1100 from theclient312afor a particular data object, the data object can be reconstructed by obtaining at least k′ number of the n′data segments and decoding them to regenerate the data object. Thetransceiver module432 obtains the storage layout of the segments from thestorage layout module420 and obtains the data segments from the identified hierarchical storage nodes. Thestorage layout module420 can obtain the segment identifiers of the segments of the data object from themapping structure414 and then determine from the storage layout the hierarchical storage nodes at which the corresponding segments are stored.
• After the hierarchical storage nodes are identified, thetransceiver module432 requests the hierarchical storage nodes to return the data segments of the data object. Thetransceiver module432 can obtain k′ to n′ number of segments for generating the data object. For example, thetransceiver module432 can stop fetching the segments after obtaining the first k′segments. In another example, thetransceiver module432 can fetch all the n′ segments but use only the first k′segments for regenerating the data object. Further, thetransceiver module432 can preferentially select a subset of identified the hierarchical storage nodes to obtain the segments from. Thetransceiver module432 selects a hierarchical storage node based on a number of factors, e.g., a latency of the hierarchical storage node, a workload of the hierarchical storage node, a geographical location of the storage device. In some embodiments, thetransceiver module432 can obtain the segments from different storage nodes in parallel.
• When a particular hierarchical storage node receives a request from the front-end subsystem310 for a data segment, the hierarchical storage node obtains the fragments of the data segment from the storage devices associated with the hierarchical storage node. The hierarchical storage node determines the storage layout of the fragments and obtains a sufficient number of the data fragments, e.g., the minimum number data fragments required to generate the data segment, from the identified storage devices.
• Further, the hierarchical storage node can preferentially select a subset of the storage devices to obtain the fragments from. The hierarchical storage node selects a storage device based on a number of factors, e.g., read latency of storage device, type of the storage device, number of pending read requests ahead of the current read request in a read request queue of the storage device, how far the storage device is. Accordingly, the hierarchical storage node may not even read some of the storage devices that contain the data fragments of the data object, thereby minimizing read/write operations on a particular storage device. In some embodiments, the hierarchical storage node can obtain the fragments in parallel.
• After obtaining the data fragments, the hierarchical storage node decodes the data fragments, e.g., based on the erasure coding used to encode the data segment, to generate the data segment, and then returns the data segment to the front-end subsystem310. In some embodiments, the hierarchical storage node may perform additional processes on the decoded data segment before returning it to the front-end subsystem310. For example, the hierarchical storage node can perform decompression and de-deduplication on the decoded data segment if the data segment was deduplicated and compressed.
• After the front-end subsystem310 obtains sufficient number of the data segments from the hierarchical storage nodes, the front-end subsystem310 decodes the data segments to generate the data object, and returns the data object to theclient system312a. In some embodiments, thestorage processing module430 may perform additional processes on the decoded data object before returning the data object to theclient312a. For example, thestorage processing module430 can perform decompression and de-deduplication on the decoded data object if the data object was deduplicated and compressed.
• As described above, the hierarchical spreading storage architecture distributes the storage resiliency provided to the data across the storage tiers—hierarchical storage nodes314-318 and storage devices of thestorage subsystem306. One of the advantages of such a distributed storage resiliency is that thestorage system1100 can withstand the loss of either some of the hierarchical storage nodes or some of the storage devices of a hierarchical storage node, or in some cases, both.
• Another advantage of the hierarchical spreading storage architecture is that the rebuilding process can be localized in some cases. That is, when a storage device associated with a particular hierarchical storage node fails, the data fragments of a segment stored at the failed storage device may be rebuilt using the remaining data fragments of the segment stored within the storage shelves of the particular hierarchical storage node. Thestorage system1100 may not have to obtain the fragments from the storage devices associated with another hierarchical storage node. For example, when a fragment F1 of the segment S1 is lost due to a failure of a storage device in thestorage shelves306a-b, the hierarchical storage node rebuilds a new data fragment for the data segment S1 using the remaining data fragments, F2-F8, stored at other storage devices within thestorage shelves306a-b. In some embodiments, the hierarchical storage node uses sufficient number of the data fragments, e.g., k number of the remaining data fragments to rebuild the new data fragment. The hierarchical storage node can use the encoding method used to generate the initial fragments to regenerate the new data fragment.
• Localizing the rebuilding process to a particular hierarchical storage node minimizes the network traffic, e.g., between the hierarchical storage nodes and the front-end subsystem310, between the hierarchical storage nodes, that might otherwise occur if the fragments are to be read from storage devices apart from that of the particular hierarchical storage node. This saves the time required for the fragments to traverse the network and therefore, can make the rebuilding process faster and more efficient. Further, localizing the rebuilding process to the storage devices of the particular hierarchical storage node, the read-write operations performed on storage devices of other hierarchical storage nodes is minimized, and therefore the wear of other storage devices is minimized.
• The hierarchical storage node can rebuild the data fragments of all the data segments whose storage resiliency is affected or a subset of those data segments. In some embodiments, the hierarchical storage node rebuilds the data fragments for a particular data segment if the current storage resiliency of the data segment is below the minimum storage resiliency to be provided for the data segment, e.g., as described with reference to rebuilding the data fragments inFIGS. 4 and 8.
• However, when a particular hierarchical storage node fails or a current storage resiliency of a data segment stored by the particular hierarchical storage node drops below the minimum storage resiliency thestorage system1100 uses the fragments from other hierarchical storage nodes to rebuild the lost fragments. For example, when thehierarchical storage node314 fails, the front-end subsystem310 obtains all or some of the remaining segments S2 and S3 from the remaining hierarchical storage nodes, generates a new segment S4 (not illustrated) and transmits it to another hierarchical storage node or one of thehierarchical storage nodes316 and318, which further encodes the new segment into fragments and stores them at its associated storage devices.
• The hierarchical spreading storage architecture can also be used to store metadata of the data received from a client of thestorage system1100.FIG. 12 is a block diagram1200 for storing metadata of a data object with the data object in astorage system1100 ofFIG. 11, consistent with various embodiments. The hierarchical spreading storage architecture can provide the same storage resiliency to the metadata of a data object that is provided to the data object. Examples of metadata can include, object ID, object size, object owner, creation time, created by, modified by, client-specified metadata, etc. Typically, metadata is stored separate from the data object. The hierarchical spreading storage architecture enables storing the metadata with the data object, thereby eliminating the need to have a separate database for metadata, the need to have specific infrastructure in place to ensure the metadata is consistent with the data, etc.
• When a write request is received at thestorage system1100, the payload data in the write request is analyzed to obtain themetadata510 and the data portion, e.g., data object405. The data object405 is then encoded, e.g., using encode/decode module418, to generate a number of segments1205, e.g., as described with reference toFIG. 11. Themetadata510 is combined with each of the segments1205, e.g., concatenated or prefixed to each of the segments1205, to generatecomposite segments1210. In some embodiments, themetadata510 can be a subset of the metadata of the data object405. Thecomposite segments1210 can then be sent to a number of hierarchical storage nodes, e.g., as described with reference toFIG. 11 for further storage at a set of storage devices associated with the hierarchical storage nodes.
• When a particular hierarchical storage node receives a composite data segment, it encodes the composite data segment to generate a number of data fragments such as fragments1215. Themetadata510 is combined with each of the fragments1215, e.g., concatenated or prefixed to each of the fragments1215, to generatecomposite fragments1220. Thecomposite fragments1220 can then be stored at the storage devices associated with the hierarchical storage node, e.g., as described with reference toFIG. 11.
• Note that thoughFIG. 12 illustrates combiningmetadata510 with both the data segments and the fragments, themetadata510 can be combined with either the data segments or the data fragments.
• In some embodiments, by storing themetadata510 with the data object405, the possibility of inconsistency between themetadata510 and the data object405 is eliminated. Further, since themetadata510 is attached to the segments1205 and/or fragments1215, thecomposite segments1210 can be moved across hierarchical storage nodes and thecomposite fragments1220 can be moved across storage devices without having to update themetadata510 and without risking the consistency between themetadata510 and the data object405.
• In some embodiments, another benefit of storing themetadata510 with the data object405 is that since a separate database and/or metadata server is not needed to maintain themetadata510, the read and write operations are relatively faster since no separate read/write is required to read/write themetadata510. In some embodiments, metadata retrieval is also simplified since a method call that is used for retrieving the data object405 can be modified to use retrieve themetadata510, which can simplify a number of functions performed related to themetadata510.
• FIG. 13 is a flow diagram of aprocess1300 of storing data to an object-based storage system using hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1300 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. Theprocess1300 begins atblock1305, and atblock1310, arequest module416 of thefrontend subsystem310 receives a write request including payload data. In some embodiments, the payload data includes data portion and metadata of the data. If the data portion is not in a format suitable for storing in an object storage system, e.g.,storage subsystem306, thefrontend subsystem310 converts the data portion to the suitable format, e.g., as the data object.
• Atblock1315, the encode/decode module418 encodes the data object to generate a number of encoded data segments, e.g., encoded data segments S1-S3. In some embodiments, the encode/decode module418 encodes the data object based on an erasure coding technique. The number of encoded data segments generated can be expressed as a function, e.g., n′=k′+m′, where variable k′ is the original amount of data segments or the minimum number of data segments required to regenerate or rebuild the data object, and variable m′stands for the extra or redundant segments that are added to provide protection from storage device/storage node failures. The variable n′ is the total number of segments created after the encoding process.
• After the encoded data segments are generated, a mapping of the object identifier and the segment identifiers of the encoded data segments are stored in themapping structure414 in thestaging area408.
• In some embodiments, apart from encoding the data object to generate the fragments, various other storage efficiency processes may be performed on the data object, e.g., deduplication, compression, encryption. One or more of these processes can be performed by thestorage processing module430.
• Atblock1320, thestorage layout module420 determines a storage layout for sending the encoded data segments across a number of hierarchical storage nodes, e.g., hierarchical storage nodes314-318. In some embodiments, thestorage layout module420 is configured to spread the encoded data segments across as many hierarchical storage nodes as possible, e.g., to provide better storage resiliency to the data object. That is, thestorage layout module420 attempts to identify different hierarchical storage nodes for storing different encoded data segments. In some embodiments, thestorage layout module420 selects the hierarchical storage nodes on a random basis. In some embodiments, thestorage layout module420 selects the hierarchical storage nodes on a random weighted basis. In some embodiments, the random weighted basis attempts to store the data segments evenly across the hierarchical storage nodes. For example, one type of weighting is to decrease the weight if there are already a specified number of segments stored at the hierarchical storage node. In some embodiments, the random weighted basis randomly identifies the hierarchical storage nodes at which the encoded data segments are to be stored as a function of decreasing the risk of data loss. For example, if a particular geographical region is prone to higher number of device failures, then the storage nodes in that geographical region may be weighted less so that a lower number of segments are written to the storage nodes in that geographical region.
• Atblock1325, thetransceiver module432 transmits the encoded data segments to the identified hierarchical storage nodes. For example, thetransceiver module432 can transmit the encoded data segments S1-S3 to hierarchical storage nodes314-318, respectively.
• Atblock1330, each of the hierarchical storage that receives an encoded data segment, processes the encoded data segment to store it at a set of storage devices associated with the hierarchical storage node, and theprocess1300 returns. The processing can include encoding the data segment to generate a number of data fragments (block1331). For example, thehierarchical storage node314 encodes the data segment to generate fragments F1-F8. In some embodiments, the hierarchical storage node encodes the data segment based on an erasure coding technique. Also, the erasure coding technique used to generate the data segments can be different from that used for generating the fragments from the segment.
• The hierarchical storage node includes a storage layout module, e.g., similar to thestorage layout module420, that determines a storage layout for storing the data fragments at a set of storage devices associated with the hierarchical storage node (block1332). In some embodiments, the storage layout module is configured to spread the encoded data fragments across as many storage devices as possible, e.g., to provide better storage resiliency to the data object. After the storage layout is determined, the hierarchical storage node stores the encoded data fragments at the identified storage devices (block1333).
• In some embodiments, the front-end subsystem310 also stores the metadata of the data object with the data segments and/or fragments. Additional details with respect to the process of storing the metadata is described at least with reference toFIGS. 9 and 17.
• FIG. 14 is a flow diagram of aprocess1400 of reading data from an object-based storage system using hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1400 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. Theprocess1400 begins atblock1405, and atblock1410, arequest module416 of thefrontend subsystem310 receives a read request, e.g., from aclient system312a, for obtaining a data object. In some embodiments, the read request includes an object identifier of the data object.
• Atblock1415, the fragment/segment identification module422, determines the encoded data segments of the data object using the object identifier. In some embodiments, a mapping of the object identifier and the encoded data segments are stored in themapping structure414 in thestaging area408.
• Atblock1420, thestorage layout module420 determines the storage layout of the encoded data segments using the mapping obtained from themapping structure414. The storage layout can include identification information of the hierarchical storage nodes where each of the encoded data segments are stored.
• Atblock1425, thetransceiver module432 identifies the hierarchical storage nodes that store sufficient number of the encoded data segments required to generate the data object. In some embodiments, the sufficient number of encoded data segments is k′ number of the encoded data segments. In some embodiments, thetransceiver module432 can obtain k′ to n′ number of segments. For example, thetransceiver module432 can stop fetching the segments after obtaining the first k′ segments. In another example, thetransceiver module432 can fetch all the n′ segments but use only the first k′ segments for regenerating the data object.
• Further, thetransceiver module432 can preferentially select a subset of the identified hierarchical storage nodes to obtain the segments from. Thetransceiver module432 can select a hierarchical storage node based on a number of factors, e.g., a read latency of the hierarchical storage node, type of the storage devices associated with hierarchical storage node, number of pending read requests ahead of the current read request in a read request queue of the hierarchical storage node, a geographical location of the hierarchical storage node.
• After the hierarchical storage nodes are identified, thetransceiver module432 requests each of the hierarchical storage nodes for the data segment.
• Atblock1430, each of the identified hierarchical storage nodes performs a number of steps, e.g.,1431-1433, to obtain the data segment. Atblock1431, the hierarchical storage node determines from a storage layout of the fragments, the set of storage devices that store sufficient number of the encoded data fragments required to generate the data segment. In some embodiments, the sufficient number of encoded data fragments is k number of the encoded data fragments. In some embodiments, the hierarchical storage node can obtain k to n number of fragments. For example, the hierarchical storage node can stop fetching the fragments after obtaining the first k fragments. In another example, the hierarchical storage node can fetch all the n fragments but use only the first k fragments for regenerating the data segment.
• Further, the hierarchical storage node can preferentially select a subset of the identified storage devices to obtain the fragments from. The hierarchical storage node can select a storage device based on a number of factors, e.g., a read latency of the storage device, a type of the storage device, number of pending read requests ahead of the current read request in a read request queue of the storage device, a geographical location of the storage device. Atblock1432, the hierarchical storage node obtains the sufficient number of fragments from the identified set of storage devices.
• Atblock1433, after obtaining the encoded data fragments, the hierarchical storage node decodes the encoded data fragments, e.g., based on the erasure coding method used to encode the data segment, to generate the data segment. After generating the data segment, the hierarchical storage node returns the data segment to the front-end subsystem310. In some embodiments, additional processes may be performed before decoding the data fragments. For example, the hierarchical storage node can decrypt the encoded data fragments if they were encrypted before being stored. In some embodiments, additional processes may be performed on the decoded data segment before the data segment is returned to the front-end subsystem310. For example, the hierarchical storage node can perform decompression and dededuplication on the decoded data segment if the data segment was deduplicated and compressed.
• After obtaining sufficient number of the encoded data segments, atblock1435, the encode/decode module418 of the front-end subsystem310 decodes the encoded data segments, e.g., based on the erasure coding method used to encode the data object, to generate the data object.
• Atblock1440, thetransceiver module432 transmits the data object in response to the read request, e.g., to theclient system312a, and theprocess1400 returns. In some embodiments, additional processes may be performed before decoding the data segments. For example, thestorage processing module430 can decrypt the encoded data segments if they were encrypted before being stored. In some embodiments, additional processes may be performed on the decoded data object before it is returned to theclient312a. For example, thestorage processing module430 can perform decompression and de-deduplication on the decoded data object if the data object was deduplicated and compressed.
• FIG. 15 is a flow diagram of aprocess1500 of rebuilding data fragments of a data object in hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1500 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. In some embodiments, the data fragments stored in thestorage subsystem306 may be lost due to a failure of a storage device. Theprocess1500 begins atblock1505, and atblock1510, a hierarchical storage node detects a failure of a storage device, e.g.,storage device304, associated with the hierarchical storage node. In some embodiments, the failure can be one or more of the storage device being not accessible, the storage device being physically damaged, the storage device determined to fail in a specified period, the storage device determined to fail in a specified number of read/write operations, etc.
• Atblock1515, the hierarchical storage node identifies the encoded data fragments that were stored at the storage device. For example, the hierarchical storage node can refer to the storage layout to determine the fragments stored at the storage device that has failed.
• Atblock1520, the hierarchical storage node identifies the one or more data segments corresponding to the identified encoded data fragments. For example, the hierarchical storage node can refer to the mapping structure to determine the data segments associated with the identified encoded data fragments.
• Atblock1525, the hierarchical storage node rebuilds some or all of the encoded data fragments that was stored at the storage device that failed. In some embodiments, rebuilding the data fragments include performing the method described in association with blocks1526-1530 for each of the identified data segments.
• Atblock1526, the hierarchical storage node identifies the storage devices where the data fragments of the identified data segment are stored. The hierarchical storage node may use the storage layout determined by the storage layout module of the node to identify the storage devices that store the data fragments of the data segment. Atblock1527, the hierarchical storage node computes the current storage resiliency of the data segment. In some embodiments, storage resiliency is defined as a resistance to loss of one or more storage devices storing a portion of a data segment or resistance to loss of one or more fragments of the data segment. In some embodiments, a current storage resiliency of a data segment is determined as a function of the number of fragments remaining out of n fragments and k. For example, if n is “10,” k is “8,” the number of redundant fragments, m is “2,” and therefore, the storage resiliency can be calculated as 25% (m/k*100). Note that the storage resiliency can be calculated using other functions and based on several other parameters. Thestorage system1100 may guarantee a storage resiliency range to the clients of the storage system, for example, a minimum storage resiliency and a maximum storage resiliency. In some embodiments, the storage resiliency range is part of the SLO guaranteed to the clients. In some embodiments, thestorage system1100 may not rebuild the lost data fragments until the current storage resiliency of the data segment is or below the minimum storage resiliency.
• Atdetermination block1528, the hierarchical storage node determines if the current storage resiliency of the data segment is less than the minimum storage resiliency. Responsive to a determination that the current storage resiliency of the data segment is not less than the minimum storage resiliency, theprocess1500 returns. On the other hand, responsive to a determination that the current storage resiliency is less than the minimum storage resiliency, atblock1529, the hierarchical storage node obtains sufficient number of fragments of the data segment stored at the identified storage devices (e.g., identified in block1526). In some embodiments, the hierarchical storage node can obtain the minimum number of fragments required to rebuild the data fragments.
• Atblock1529, the hierarchical storage node generates the replacement data fragments as a function of the obtained data fragments, and atblock1530, the hierarchical storage node stores the regenerated data fragments in at least a subset of the remaining storage devices. In some embodiments, the hierarchical storage node regenerates as many data fragments as required to meet a specified storage resiliency, which can be up to maximum storage resiliency. In some embodiments, regenerating the data fragments as a function of the obtained data fragments includes decoding the obtained data fragments to generate the data segment and encoding the generated data segment to generate the specified number of data fragments. In some embodiments, the hierarchical spreading storage performs the encoding and decoding using an erasure coding method.
• FIG. 16 is a flow diagram of aprocess1600 of rebuilding data segments of a data object in hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1600 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. In some embodiments, the data segments stored by a hierarchical storage node may be lost due to a failure of a storage device and/or a hierarchical storage node. Theprocess1600 begins atblock1605, and atblock1610, afailure detection module424 of front-end subsystem310 detects a failure of a hierarchical storage node and/or a failure of one or more storage devices of the hierarchical storage node that caused the storage resiliency of a particular data segment to drop. In some embodiments, the failure can be one or more of the storage device being not accessible, the storage device being physical damaged, the hierarchical storage node not being accessible, the storage device determined to fail in a specified period, the storage device determined to fail in a specified number of read/write operations, etc.
• Atblock1615, the fragment/segment identification module422 identifies the encoded data segment stored by the hierarchical storage device. For example, the fragment/segment identification module422 can refer to the storage layout to determine the segments stored at the particular hierarchical storage node that has failed.
• Atblock1620, the fragment/segment identification module422 identifies the data object to which the encoded data segment corresponds. For example, the fragment/segment identification module422 can refer to the mapping structure to determine the data segments associated with the identified data object.
• Atdetermination block1625, theregeneration module428 computes the current storage resiliency of the data object and determines if the storage resiliency of the object is below the specified minimum storage resiliency. In some embodiments, a current storage resiliency of a data object is determined as a function of the number of segments remaining out of n′segments and k′. For example, if n′ is “10,” k′ is “8,” the number of redundant segments, m′ is 2, and therefore, the storage resiliency can be calculated as 25% (m/k*100). Note that the storage resiliency can be calculated using other functions and based on several other parameters. In some embodiments, thestorage system1100 may not rebuild the lost data segments until the current storage resiliency of the data object is or below the minimum storage resiliency.
• Responsive to a determination that the current storage resiliency of the data object is not less than the minimum storage resiliency, theprocess1600 returns. On the other hand, responsive to a determination that the current storage resiliency is less than the minimum storage resiliency, atblock1630, thetransceiver module432 obtains sufficient number of segments of the data object stored at other hierarchical storage nodes. In some embodiments, thetransceiver module432 obtains the segments of the data object stored at other hierarchical storage nodes as described with at least with reference to blocks1425-1433 ofFIG. 14.
• Atblock1635, theregeneration module428 generates the replacement data segment as a function of the obtained data segments. In some embodiments, theregeneration module428 generates as many data segments as required to meet a specified storage resiliency for the data object, which can be up to a specified maximum storage resiliency of the data object. In some embodiments, regenerating the data segments as a function of the obtained data segments includes decoding the obtained data segments to generate the data object and encoding the generated data object to generate the specified number of data segments. In some embodiments, the hierarchical spreading storage performs the encoding and decoding using an erasure coding method.
• Atblock1640, thetransceiver module432 sends the regenerated data segments to one or more of the remaining storage devices for storage at their associated storage devices. In some embodiments, thetransceiver module432 transmits the replacement data segments of the data object to other hierarchical storage nodes as described with at least with reference to blocks1320-1333 ofFIG. 13.
• FIG. 17 is a flow diagram of aprocess1700 of deferred rebuilding of data segments of a data object in the hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1700 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. The rebuilding/regeneration process1600 can consume significant system resources for regenerating the encoded data segments, e.g., network resources for reading at least K number of encoded data segments from other hierarchical storage nodes, computing resources of the corresponding hierarchical storage nodes in obtaining the fragments of the corresponding data segment and decoding them to generate the encoded data segment, etc. In some embodiments, the consumption of the system resources can be minimized by postponing or deferring theregeneration process1600 until a later time, e.g., when the storage devices are replaced with new storage devices, when the data in the storage devices is migrated, etc.
• In some embodiments, the generation of replacement data segments for the lost data segments is deferred until after one or more of the failed storage devices and/or one or more of the hierarchical storage nodes is replaced. That is, the regeneration process may not be executed during the lifetime of the storage devices and/or the hierarchical storage nodes. In some embodiments, the timing of the regeneration process is controlled based on m′, the number of redundant encoded data segments to be generated. As described above at least with reference to theregeneration process1600, theregeneration process1600 is triggered when the current storage resiliency of the data object drops below the minimum storage resiliency. The storage resiliency of a data object is a function of the total number of encoded data segments, n′, stored across the hierarchical storage nodes, which is a function of m′. The m′ can be determined such that the storage resiliency of the data object does not drop below the minimum storage resiliency during the lifespan of one or more of the storage devices. In other words, the number of encoded data segments generated are such that a loss of a subset of the encoded data segments does not drop the storage resiliency of the data object below the minimum storage resiliency during the lifespan of one or more of the storage devices. The following paragraphs describe theprocess1700 in further detail.
• Theprocess1700 begins atblock1705, and atblock1710, theregeneration module428 obtains the historical information regarding a failure rate of storage devices of the type of the storage devices in theenvironment300. The historical information can include a number of parameters that can describe and/or help determine the failure information of a storage device, e.g., an annual failure rate (AFR) of the storage device of a particular type, an AFR of the storage device based on a particular workload on the storage device, how long a storage device is expected to survive based on a particular workload. Such historical information can be gathered from various sources, gathered from theenvironment300 over a period and/or can be input by a user such as an administrator of theenvironment300.
• Atblock1715, theregeneration module428 predicts the failure rate of the storage devices in theenvironment300 and generates the predicted information. Theregeneration module428 can interpolate the historical information with various parameters of the storage devices in theenvironment300, e.g., the number of storage devices in theenvironment300, a workload of the storage devices, the number of read/write operations performed on the storage devices, a remaining life of the storage devices, and determine the predicted failure rate of the storage devices.
• Atblock1720, theregeneration module428 determines the lifespan of the storage devices as a function of the historical information and the predicted information. Atblock1725, theregeneration module428 determines a statistical probability of a loss of a failure of one or more hierarchical storage nodes based on the determined lifespan of the storage devices. In some embodiments, a failure/loss of a hierarchical storage node is a function of the lifespan of the set of storage devices associated with the hierarchical storage node since a failure of one or more storage devices from the set can result in a failure of the hierarchical storage node. Further, a failure of the hierarchical storage node can result in a loss of the encoded data segment stored at the hierarchical storage node.
• Atblock1730, theregeneration module428 determines the redundant number of encoded data segments, m′, to be generated for the data object based on the statistical probability of the loss of the hierarchical storage node. Theregeneration module428 notifies the encode/decode module418 regarding the determined m′, and the encode/decode module418 encodes the data object to generate the encoded data segments accordingly.
• In some embodiments, theregeneration module428 may continuously adjust m′, e.g., based on a specified schedule or certain events such as when storage devices are added or removed, to factor in any change in the parameters of theenvironment300, e.g., change in workload on the storage devices, addition or removal or storage devices, etc.
• Note that although theprocess1700 is described as being performed by theregeneration module428, theprocess1700 can be performed by a combination of modules of the front-end subsystem310 and/or sub-modules of the regeneration module428 (not illustrated).
• FIG. 18 is a flow diagram of aprocess1800 of processing metadata and data fragments of a data object in hierarchical spreading storage architecture, consistent with various embodiments of the disclosed technology. In some embodiments, theprocess1800 may be implemented inenvironment300 ofFIG. 3, and using thestorage system1100 ofFIG. 11. In some embodiments, theprocess1800 is an implementation of the method ofblock925 ofFIG. 9. The data piece generated in theprocess900 ofFIG. 9, e.g., inblock920, can be considered as a data segment in the hierarchical spreading storage architecture. Theprocess1800 begins atblock1805, and atblock1810, themetadata processing module426 combines the metadata of a data object, e.g.,metadata510, with each of the segments, e.g., segments1205, to generate composite segments, e.g.,composite segments1210. In some embodiments, combining the metadata with data segment can include concatenating the metadata with segment or prefixing a segment with the metadata. In some embodiments, themetadata510 combined with segment can be a subset of the metadata of the data object405.
• After the composite segments are generated, atblock1815, thetransceiver module432 transmits the composite segments to a number of hierarchical storage nodes, e.g., as described at least with reference toblocks1320 and1325 ofFIG. 13 for further storage at a set of storage devices associated with the hierarchical storage nodes.
• Atblock1820, when a particular hierarchical storage node receives a composite data segment, it encodes the composite data segment to generate a number of data fragments, e.g., fragments1215 (block1821). In some embodiments, the composite data segment is encoded to generate a number of data fragments as described at least with reference to block1331 ofFIG. 13.
• Atblock1822, the particular hierarchical storage node combines each of the fragments with the metadata, e.g., concatenates or prefixes the fragments1215 with themetadata510, to generate the composite fragments, e.g., composite fragments1220.
• After the composite fragments are generated, atblock1823, the particular hierarchical storage node stores the composite fragments at a set of storage devices associated with the hierarchical storage node, e.g., as described with reference toblocks1332 and1333 ofFIG. 13.
• Note that althoughFIG. 18 illustrates combiningmetadata510 with both the data segments and the fragments, themetadata510 can be combined with either the data segments or the data fragments.
• FIG. 19 is a block diagram of a computer system as may be used to implement features of some embodiments of the disclosed technology. Thecomputing system1900 may be used to implement any of the entities, components or services depicted in the examples ofFIGS. 1-17 (and any other components described in this specification). Thecomputing system1900 may include one or more central processing units (“processors”)1905,memory1910, input/output devices1925 (e.g., keyboard and pointing devices, display devices), storage devices1920 (e.g., disk drives), and network adapters1930 (e.g., network interfaces) that are connected to aninterconnect1915. Theinterconnect1915 is illustrated as an abstraction that represents any one or more separate physical buses, point to point connections, or both connected by appropriate bridges, adapters, or controllers. Theinterconnect1915, therefore, may include, for example, a system bus, a Peripheral Component Interconnect (PCI) bus or PCI-Express bus, a HyperTransport or industry standard architecture (ISA) bus, a small computer system interface (SCSI) bus, a universal serial bus (USB), IIC (I2C) bus, or an Institute of Electrical and Electronics Engineers (IEEE) standard 1394 bus, also called “Firewire”.
• Thememory1910 andstorage devices1920 are computer-readable storage media that may store instructions that implement at least portions of the described technology. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links may be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection. Thus, computer readable media can include computer-readable storage media (e.g., “non-transitory” media) and computer-readable transmission media.
• The instructions stored inmemory1910 can be implemented as software and/or firmware to program the processor(s)1905 to carry out actions described above. In some embodiments, such software or firmware may be initially provided to thecomputing system1900 by downloading it from a remote system through the computing system1900 (e.g., via network adapter1930).
• The technology introduced herein can be implemented by, for example, programmable circuitry (e.g., one or more microprocessors) programmed with software and/or firmware, or entirely in special-purpose hardwired (non-programmable) circuitry, or in a combination of such forms. Special-purpose hardwired circuitry may be in the form of, for example, one or more ASICs, PLDs, FPGAs, etc.
Remarks
• The above description and drawings are illustrative and are not to be construed as limiting. Numerous specific details are described to provide a thorough understanding of the disclosure. However, in some instances, well-known details are not described in order to avoid obscuring the description. Further, various modifications may be made without deviating from the scope of the embodiments. Accordingly, the embodiments are not limited except as by the appended claims.
• Reference in this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the disclosure. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Moreover, various features are described which may be exhibited by some embodiments and not by others. Similarly, various requirements are described which may be requirements for some embodiments but not for other embodiments.
• The terms used in this specification generally have their ordinary meanings in the art, within the context of the disclosure, and in the specific context where each term is used. Some terms that are used to describe the disclosure are discussed below, or elsewhere in the specification, to provide additional guidance to the practitioner regarding the description of the disclosure. For convenience, some terms may be highlighted, for example using italics and/or quotation marks. The use of highlighting has no influence on the scope and meaning of a term; the scope and meaning of a term is the same, in the same context, whether or not it is highlighted. It will be appreciated that the same thing can be said in more than one way. One will recognize that “memory” is one form of a “storage” and that the terms may on occasion be used interchangeably.
• Consequently, alternative language and synonyms may be used for any one or more of the terms discussed herein, nor is any special significance to be placed upon whether or not a term is elaborated or discussed herein. Synonyms for some terms are provided. A recital of one or more synonyms does not exclude the use of other synonyms. The use of examples anywhere in this specification including examples of any term discussed herein is illustrative only, and is not intended to further limit the scope and meaning of the disclosure or of any exemplified term. Likewise, the disclosure is not limited to various embodiments given in this specification.
• Those skilled in the art will appreciate that the logic illustrated in each of the flow diagrams discussed above, may be altered in various ways. For example, the order of the logic may be rearranged, substeps may be performed in parallel, illustrated logic may be omitted; other logic may be included, etc.
• Without intent to further limit the scope of the disclosure, examples of instruments, apparatus, methods and their related results according to the embodiments of the present disclosure are given below. Note that titles or subtitles may be used in the examples for convenience of a reader, which in no way should limit the scope of the disclosure. Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains. In the case of conflict, the present document, including definitions will control.

Claims (31)

I/we claim:

1. A computer-implemented method comprising:

receiving, at a storage management computer node of a storage management system, a write request including a data object;

encoding, by the storage management computer node, the data object to generate a first specified number of multiple encoded data fragments, the encoded data fragments representing the data object, the first specified number of encoded data fragments including a second specified number of the encoded data fragments using which the data object can be regenerated;

determining, by the storage management computer node, a storage layout of the encoded data fragments for storing the encoded data fragments at multiple storage devices, the storage devices grouped into multiple storage shelves, wherein a number of the storage devices is equal to or greater than the first specified number of the encoded data fragments; and

transmitting, by the storage management computer node and based on the storage layout, to at least a subset of the storage shelves to store the encoded data fragments at the storage devices.

2. The computer-implemented method ofclaim 1, wherein encoding the data object to generate the first specified number of the encoded data fragments includes generating the encoded data fragments based on a specified ratio of the first specified number to the second specified number.

3. The computer-implemented method ofclaim 2, wherein the specified ratio is a function of a specified storage resiliency, the specified storage resiliency indicating resistance to at least one of a failure of a specified number of the storage devices or a loss of a specified number of the encoded data fragments without losing the data object.

4. The computer-implemented method ofclaim 1, wherein encoding the data object includes:

associating an object identifier with the data object,

associating fragment identifiers with the encoded data fragments of the data object, and

generating a mapping of the fragment identifiers to the object identifier.

5. The computer-implemented method ofclaim 4, wherein the object identifier and the fragment identifiers are stored in different namespaces of the storage management computer node.

6. The computer-implemented method ofclaim 1, wherein the encoding includes selecting a fragmentation technique to fragment the data object.

7. The computer-implemented method ofclaim 6, wherein selecting the fragmentation technique includes selecting the fragmentation technique based on at least one of a deduplication binning requirement or an erasure coding requirement.

8. The computer-implemented method ofclaim 1, wherein determining the storage layout includes determining the storage layout based on an attribute of the write request.

9. The computer-implemented method ofclaim 8, wherein the attribute of the write request includes a service level objective (SLO) of the write request.

10. The computer-implemented method ofclaim 8, wherein the attribute of the write request includes a specified storage resiliency, the specified storage resiliency indicating tolerance to failure of a specified number of the storage devices.

11. The computer-implemented method ofclaim 1, wherein the storage layout includes a first identification information of the storage shelves at which each of the encoded data fragments are stored.

12. The computer-implemented method ofclaim 11, wherein the storage layout includes a second identification information of a storage device within a storage shelf of the storage shelves at which each of the encoded data fragments is stored.

13. The computer-implemented method ofclaim 1, wherein determining the storage layout includes determining the storage devices at which the encoded data fragments are to be stored on a random basis.

14. The computer-implemented method ofclaim 1, wherein determining the storage layout includes determining the storage devices at which the encoded data fragments are to be stored on a random weighted basis.

15. The computer-implemented method ofclaim 14, wherein the random weighted basis randomly identifies the storage devices at which the encoded data fragments are to be stored as a function of an available storage capacity at the storage devices.

16. The computer-implemented method ofclaim 14, wherein determining the storage layout on the random weighted basis includes:

determining that a first storage device of the storage devices has higher available storage capacity than a second storage device of the storage devices, and

storing data at the first storage device at a higher rate than at the second storage device.

17. The computer-implemented method ofclaim 14, wherein the random weighted basis distributes the encoded data fragments across the storage devices evenly.

18. The computer-implemented method ofclaim 14, wherein the random weighted basis randomly identifies the storage devices at which the encoded data fragments are to be stored as a function of decreasing the risk of data loss.

19. The computer-implemented method ofclaim 1, wherein a number of the storage shelves is at least the first number of the encoded data fragments divided by a largest number of storage devices per storage shelf of the storage shelves.

20. A computer-readable storage medium storing computer-executable instructions comprising:

instructions for receiving, at a storage management computer node of a storage management system, a read request for obtaining a data object stored at a storage subsystem, the read request including an object identifier of the data object;

instructions for determining, by the storage management computer node and using the object identifier, multiple encoded data fragments of the data object, wherein the data object is stored at the storage subsystem as “N” number of the encoded data fragments, the “N” number of encoded data fragments including “K” number of the encoded data fragments using which the data object can be regenerated;

instructions for determining, by the storage management computer node, a storage layout of the encoded data fragments, the storage layout including identification information of (a) one or more of multiple storage shelves of the storage subsystem that store the encoded data fragments and (b) multiple storage devices of the storage shelves that store the encoded data fragments, wherein a number of the storage devices is equal to or greater than “N”; and

instructions for obtaining, by the storage management computer node and based on the storage layout, the encoded data fragments from the storage devices.

21. The computer-readable storage medium ofclaim 20 further comprising:

instructions for decoding the encoded data fragments obtained from the storage devices to regenerate the data object; and

instructions for transmitting the data object from the storage management computer node in response to the request.

22. The computer-readable storage medium ofclaim 20, wherein the “K” number of the encoded data fragments is a minimum number of encoded data fragments required to regenerate the data object.

23. The computer-readable storage medium ofclaim 20, wherein the instructions for obtaining the encoded data fragments includes instructions for obtaining at least the “K” number of the encoded data fragments.

24. The computer-readable storage medium ofclaim 23, wherein the instructions for obtaining the “K” number of the encoded data fragments includes:

instructions for selecting a first “K” number of the encoded data fragments that arrive at the storage management computer node from the storage devices.

25. The computer-readable storage medium ofclaim 23, wherein the instructions for obtaining the “K” number of the encoded data fragments includes:

instructions for selecting a subset of the storage devices as a function of at least one of multiple attributes of a specified storage device of the storage devices, and

instructions for obtaining the “K” number of the encoded data fragments from the subset of the storage devices.

26. The computer-readable storage medium ofclaim 25, wherein the attributes of the specified storage device includes a read latency of the specified storage device, a number of pending read requests at the specified storage device, or a number of pending write requests at the specified storage device.

27. The computer-readable storage medium ofclaim 20, wherein the encoded data fragments are generated from the data object based on a fragmentation technique to fragment the data object.

28. The computer-readable storage medium ofclaim 27, wherein the fragmentation technique is based on an erasure coding technique.

29. The computer-implemented method ofclaim 20, wherein a number of the storage shelves is at least the “N” number of the encoded data fragments divided by a largest number of storage devices per storage shelf of the storage shelves.

30. A system comprising:

a processor;

a first module configured to receive a write request including a data object;

a second module configured to encode the data object to generate a first specified number of multiple encoded data fragments out of which a second specified number of the encoded data fragments are used regenerate the data object, the encoded data fragments representing the data object;

a third module configured to determine a storage layout for storing the encoded data fragments at multiple storage devices, the storage devices grouped into multiple storage shelves, wherein a number of the storage devices is equal to or greater than the first specified number of the encoded data fragments; and

a fourth module configured to transmit the encoded data fragments to at least a subset of the storage shelves based on the storage layout to store the encoded data fragments at one or more of a set of the storage devices of each of the subset of the storage shelves.

31. The system ofclaim 30, wherein the second module is further configured to encode the data object as a function of erasure coding technique.

Images