Method of using common storage of parity data for unique copy recording

A disclosed method is performed at a fault-tolerant object-based storage system including M data storage entities, each is configured to store data on an object-basis. The method includes obtaining a request to store N copies of a data object and in response, storing the N copies of the data object across the M data storage entities, where the N copies are distributed across the M data storage entities. The method additionally includes generating a first parity object for a first subset of M copies of the N copies of the data object, where the first parity object is stored on a first parity storage entity separate from the M data storage entities. The method also includes generating a manifest linking the first parity object with one or more other subsets of M copies of the N copies of the data object.

TECHNICAL FIELD

The present disclosure relates generally to storage systems, and in particular, to enabling more efficient storage of parity data for data recovery.

BACKGROUND

On behalf of customers, cable or other media delivery service providers typically use largescale unique copy cloud digital video recorder (DVR) storage in order to record programs. Unlike other large scale storage systems, most of the content in unique copy cloud DVR deployments consists of identical objects. These identical objects are stored hundreds, if not thousands of times, as repeated instances of the same content.

The Digital Millennium Copyright Act (DMCA), enacted in the United States of America on Oct. 28, 1998, provides that one and only one unique instance of the media data may be created for each customer. In order to comply with copyright and the associated fair use restrictions, the cloud DVR file systems would store multiple copies of the same video data, e.g., one for each person recording the video. These copies are often stored in a fault tolerant manner with the associated parity data. Using parity data, the original data can be recovered in the event of disk or hardware failure.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Numerous details are described herein in order to provide a thorough understanding of the illustrative implementations shown in the accompanying drawings. However, the accompanying drawings merely show some example aspects of the present disclosure and are therefore not to be considered limiting. Those of ordinary skill in the art will appreciate from the present disclosure that other effective aspects and/or variants do not include all of the specific details of the example implementations described herein. While pertinent features are shown and described, those of ordinary skill in the art will appreciate from the present disclosure that various other features, including well-known systems, methods, components, devices, and circuits, have not been illustrated or described in exhaustive detail for the sake of brevity and so as not to obscure more pertinent aspects of the example implementations disclosed herein.

Overview

Enterprise data storage can benefit from techniques that enable writing large volumes of data across a set of one or more computing devices (e.g., storage entities) in a fault-tolerant manner. In the context of recording media programs, such as television programs and movies, multimedia content often includes hundreds, if not thousands, of sets of identical objects. In the fault-tolerant system, a sizable amount of identical parity data is also stored. Although the parity data provides resiliency and redundancy to the data object being stored, storing the parity data is a significant overhead to disk storage. Particularly in an uncompressed cloud DVR environment, a sizable amount of parity data is also generated and stored, e.g., hundreds, if not thousands of times, as repeated (e.g., identical) instances of the same parity data. This drives up the cost of the overall storage and increases the amount of computation resources for generating and writing the duplicate content. In light of these considerations, and in accordance with various implementations, a method is disclosed for efficient parity data generation and storage. In some implementations, the method includes generating and storing compressed parity data for identical content instances. The method in accordance with the embodiments described herein thus reduces the disk overhead and increases the amount of multimedia data objects storable in the file system.

Various implementations disclosed herein include systems, devices, and methods for generating and storing parity data that correspond to multiple copies of a multimedia data object. For example, in some implementations, a method is performed at a fault-tolerant object-based storage system including M data storage entities and one or more controllers, where each of the M data storage entities is configured to store data on an object-basis. The method includes obtaining a request to store N copies of a data object within the fault-tolerant object storage system. The method further includes storing the N copies of the data object across the M data storage entities in response to the request, where the N copies of the data object are distributed across the M data storage entities, such that any two sequential copies of the N copies are stored on two separate storage entities of the M data storage entities. The method also includes generating a first parity object for a first subset of M copies of the N copies of the data object, where the first parity object is stored on a first parity storage entity separate from the M data storage entities. The method additionally includes generating a manifest linking the first parity object with one or more other subsets of M copies of the N copies of the data object.

Example Embodiments

FIGS. 1A and 1Bare block diagram representations of a storage environment100in accordance with some implementations. While certain specific features are illustrated, those of ordinary skill in the art will appreciate from the present disclosure that various other features have not been illustrated for the sake of brevity and so as not to obscure more pertinent aspects of the example implementations disclosed herein. To that end, in some implementations, the storage environment100includes client devices130, such as a television130a, a smartphone130b, and/or a laptop130c. Other types of client devices130not shown include set-top boxes, video game consoles, tablets, computers, and any other electronic devices configured to obtain and convey audiovisual media information.FIG. 1Aillustrates that one or more client devices130are connected to a public or external network140(e.g., the Internet). In some implementations, a respective client device130is connected to the public or external network140in order to transmit one or more read/write requests101, e.g., client requests101a,101b,101cand101d, to a recording entity103and/or to an object-based storage system104.

In some implementations, the storage environment100is configured to store audio/visual data associated with multicast (e.g., broadcast) content and acts as a digital video recorder (DVR). As both data and read/write requests can be received over a network, the storage environment100can function as a cloud-based DVR. To that end, in some implementations, a respective client request, such as the client request101, includes information identifying a portion of a media item, such as a video or an episode of a TV show. In some implementations, the client device130transmits several client requests101in succession in order to enable storage of a portion of a media item. For example, one client request corresponds to two seconds of data for a news program that the client device130arequests to be recorded. In order to record half an hour worth of the news program, the client device130awould send nine hundred successive client requests101through the public network140to the recording entity103.

FIG. 1Aalso illustrates that, in some implementations, the storage environment100includes the recording entity103connected by a public or private network150to the object-based storage system104. In some implementations, the recording entity103receives one or more client requests101and generates one or more recording requests102. For example, in a media storage environment, a client device, such as the laptop130c, sends one client request101ato the recording entity103in order to record a portion of a particular media item. In some implementations, the recording entity103is managed or operated by an entity that provides multimedia content to end users, such as a cable television provider, an online-streaming platform, and/or a satellite programming provider.

In some implementations, the recording entity103aggregates the one or more client requests101into the one or more recording requests102. In some implementations, the one or more recording requests102include a batch request. For example, the recording entity103may receive one hundred client requests101within a predefined batching time period from one hundred distinct client devices130. The one hundred client requests101may be associated with the same two seconds of a particular media item. In response to the one hundred client requests101, the recording entity103translates those client requests101into a single batch request102for storage at the object-based storage system104. In such implementations, there is a many-to-one relationship between the client requests101and the batch request102. As such, many client requests101are aggregated or packaged into the single batch request102. In some other implementations, there is a one-to-one relationship between the client requests101and the batch requests102. For instance, if one received client request101corresponds to recording a particular media item within the predefined batching time period, the recording entity103creates the batch request102that corresponds to the single client request101.

In some implementations, the storage environment100does not include the recording entity103as a separate component. For instance, the recording entity103can be part of the object-based storage system104. In such implementations, the client requests are received by the object-based storage system104and the one or more client requests101are passed to the object-based storage system104through the public or private network150.

FIG. 1Billustrates a portion of the storage environment100in accordance with some implementations. In some implementations, the portion of the storage environment100as shown inFIG. 1Bis the object-based storage system104(FIG. 1A) that receives a batch request102acorresponding to one or more client requests101(FIG. 1A). In some implementations, the object-based storage system104is configured to primarily store data in one or more storage entities (e.g., storage entities108and/or ingest storage entity106) on an object-basis, rather than, for example, a file-basis. The object-based storage system104(also known as the object storage system) described herein stores and manages data as objects, where each object includes a globally unique identifier, the content data, and/or metadata corresponding to the content data. In contrast, file-based storage systems often manage data storage through the use of hierarchy, a globally unique path for a respective file, and a naming convention that does not require a unique name for each file.

In some implementations, the object-based storage system104receives stand-alone client requests, or client requests packaged as batch request(s)102a, as described above with respect toFIG. 1A. In some implementations, the batch request102aincludes information such as a copy count111along with a data object112. The copy count111specifies the number of copies of the data object112for storage within the object-based storage system104. For example, the data object112can include data corresponding to a particular video of a basketball game, and the copy count111indicates that in response to requests from five hundred client devices, five hundred copies of the data object112are to be stored in the storage space of the object-based storage system104.

Still referring toFIG. 1B, in some implementations, the object-based storage system104includes one or more storage entities, such as servers, disks, and other computing devices. These components work together in order to store information corresponding to a recording request (e.g., the recording request102as shown inFIG. 1A) received by the object-based storage system104. In some implementations, a respective storage entity (e.g., a storage entity108a) of the object-based storage system104stores data and/or parity data. In some implementations, any storage entity (e.g., the storage entity108a,108b,108c, or108d) can be defined as an ingest storage entity106. When a storage entity is designated as the ingest storage entity106, other storage entities, such as the storage entities108a,108b,108c, and108d, are referred to as peer storage entities with respect to the ingest storage entity106.FIG. 1Billustrates that one or more storage entities (e.g., the storage entity108c) include components, such as a controller160, an error control module162, memory170(e.g., RAM), and storage space180(e.g., non-volatile memory). In some implementations, each of the storage entities is a server or a stripe in the fault-tolerant object-based storage system104. Collectively, the storage entities (e.g., the storage entities108and the ingest storage entity106) in the object-based storage system104are a cluster of servers in accordance with some implementations.

In some implementations, the controller160for a respective storage entity has control links to every other storage entity of the object-based storage system104. In some implementations, the error control module162generates or directs the generation of fault tolerant data in the storage entity180. In some implementations, the error control module162resides within the controller160(not shown); while in some other implementations, the error control module162is an entity distinct (e.g., separate) from the controller160as shown inFIG. 1B.

While the storage entity108cis shown to include components such as the controller160, memory170, and storage180, it will be understood by one of ordinary skill in the art that any storage entity of the object-based storage system104can have one or more of these components or other components not shown. Further, the components can be combined, integrated, or separated. For example, in some implementations, the error control module162includes memory for storing a compression setting163. As will be described below in detail with reference toFIGS. 2A-2C, in some implementations, the parity compression indicator stored in the compression setting163is user configurable.

When the compression setting163indicates that the parity compression is turned on, the error control module162directs the generation of compressed parity objects in order to save space for storing the data objects, as will be described below with reference toFIGS. 2B and 2C. In comparison, when the compression setting163indicates that the parity compression is turned off, the error control module162does not direct compression of the parity object, and duplicate parity objects may be generated for duplicate data objects, as will be described in detail below with reference toFIG. 2A.

It should be noted that when the parity compression indicator is on, there is no one-to-one relationship between the parity and the recorded data object. Because the parity object itself is not the original multimedia data, the compression of the parity objects for duplicate data objects would not yield information that identical copies of the recorded data object exist. Accordingly, turning on the compression setting163would not violate copyright and the associated fair use restrictions in the United States. Legal requirements are different around the world. Providing a user configurable compression setting163would allow the customer to decide whether to turn on or off the parity object compression in order to comply with local requirements.

As an interface of the object-based storage system104, in some implementations, the ingest storage entity106of the object-based storage system104receives and/or transmits data, an instruction, or any type of communication from outside the object-based storage system104, e.g., the batch request102a. As explained above, any storage entity (e.g., the storage entity108a,108b,108c, or108d) can be defined as the ingest storage entity106. In other words, in some implementations, a respective storage entity, designated as an ingest storage entity106for a respective recording request, is not designated as the ingest storage entity106for all received batch requests. For example, one storage entity identified as Server B of the object-based storage system104receives a first batch request to record an episode of a cooking show. In this example, Server B serves as the ingest storage entity106with respect to the first batch request. Subsequently a different storage entity, which is identified as Server G of the object-based storage system104, is designated as an ingest storage entity for a subsequent batch request.

In some implementations, the ingest storage entity106also receives and/or transmits various communications within the object-based storage system104, such as communicating write requests containing write operations to storage entities108a,108b,108c, and/or108d. In particular, in some implementations, the object-based storage system104reduces the risk of losing the stored data object112by distributing copies of the data object112among various storage entities108. In some implementations, the object-based storage system104is configured to use distributed erasure coding (DEC) in order to store information for fault-tolerance purpose. In some implementations, the parity data generated according to DEC are also distributes across multiple storage entities108.

For example, the object-based storage system104is configured with a particular data-to-parity storage ratio (also known as the DEC pattern). The data-to-parity storage ratio indicates how many storage entities will store content data (e.g., copies of the data object112) corresponding to a respective batch request102a, and how many storage entities will store the parity information corresponding to the respective batch request102a. In case the data-to-parity storage ratio is 3:2, for example, the object-based storage system104includes three storage entities for storing content data and two storage entities for storing the corresponding parity data. In such implementations, the ingest storage entity106converts one recording request to multiple write operations and communicates the multiple write requests to other storage entities. In the above example of a 3:2 DEC pattern storage system, the ingest storage entity106converts one batch request102ato five write operations in total, e.g., three write operations for writing data objects and two write operations for writing parity objects.

In another example, the batch request102acan correspond to storage of four hundred copies of the data object112(e.g., a popular talk show). InFIG. 1B, the fault-tolerant object-based storage system104can be configured to store and distribute data as well as the corresponding parity data for the batch request102aacross four data-storing storage entities108a,108b,108c, and108dand two parity-storing storage entities (not shown), e.g., a DEC pattern of 4:2. Upon receiving the batch request102a, one hundred copies of the data object112are stored at the storage entity108aof object-based storage system104, one hundred copies are stored at the storage entity108b, one hundred copies are stored at the storage entity108c, and one hundred copies are stored at the storage entity108d. Further, a first parity data corresponding to the data object112can be stored at a first storage entity (not shown) of the object-based storage system104, and a second parity data corresponding to the data object112can be also stored at a second storage entity (not shown) of the object-based storage system104.

In some implementations, the ingest storage entity106selects a set of storage entities, e.g., the storage entities108a,108b,108c, and108d, to receive the write requests corresponding to the received request102a. While in some other implementations, instead of making the selection at the ingest storage entity106, another entity within the object-based storage system104performs the selection of the storage entities108a,108b,108c, and108d. The set of storage entities corresponds to the data-to-parity storage ratio represented by M:N, so that the subset including M data-storing storage entities is assigned to store data associated with the request102aand the subset including N parity-storing storage entities is assigned to store parity data associated with the request102a. In some implementations, the ingest storage entity106is among the M data-storing or N parity-storing storage entities for a respective batch request102a. In other words, the ingest storage entity106is one of the storage entities108, and is designated as the ingest storage entity106for receiving the request102aand generating write requests as well as storing data and/or parity objects.

In some implementations, the ingest storage entity106generates write requests for transmission to each of the determined set of storage entities and offloads the processing burden to the selected storage entities for completing the writing requests. In some implementations, the ingest storage entity106does not generate the number of copies specified by the copy count111by itself. This frees up the bandwidth by avoiding transmission of duplicate copies of the data object112between the ingest storage entity106and the storage entities, such as the storage entities108a,108b,108c, and108d, and reduces memory and CPU usage at the ingest storage entity106. In such implementations, each write request includes information such as the data object112, a location for retrieving data object112, the copy count111, the storage entity number of the receiving storage entity (e.g., 3rd data storage entity of 5), the data-to-parity storage ratio, and/or whether the receiving storage entity is a parity-storing or data-storing storage entity for this particular write request etc. Upon receiving the write requests, each storage entity108pulls one copy of the data object112from memory of the ingest storage entity106, and proceeds to make the appropriate number of copies on a corresponding disk.

For example, the storage entity108aof object-based storage system104receives a write request from the ingest storage entity106. The write request identifies where to retrieve the data object112from the memory of ingest storage entity106. The write request further identifies299additional copies of the data object112will be stored within the object-based storage system104based on the copy count111. Additionally, the write require specifies that the storage entity108ais a data-storing storage entity, where the data-to-parity storage ratio is 3:2, and the storage entity108ais the third data-storing storage entity receiving the write request. According to such write request, 100 copies (1 original object plus 99 copies) of data object112will be stored at the first data-storing storage entity of the set, 100 copies will be stored at the second data-storing storage entity, and 100 copies will be stored at the third data-storing storage entity, namely, the storage entity108a. Upon receiving the write request, the storage entity108apulls one copy of the data object112from memory of the ingest storage entity106and determines 100 copies of the data object112to write within its storage space.

In some implementations, the locations of the data objects and parity objects in the object-based storage system104are maintained by manifest164. The manifest data164in accordance with some implementations provides information for media content rendering and recovery. During media content rendering, using the manifest data164, the data objects distributed on the storage entities106and108can be pieced together prior to being provided to the client devices130(FIG. 1A). During media content recovery, the manifest data164provides information related to identifying the association (or linking) of the parity objects with the data objects. As such, during fault recovery, the corresponding parity objects can be located to restore a missing data object.

ThoughFIG. 1Billustrates the manifest data164as one entity separately from other components of the object-based storage system104, the manifest data164can be stored within any of the components of the object-based storage system104and can be distributed over multiple components of the object-based storage system104. For example, the manifest data164identifying the association between the data objects and the parity objects can be stored within the error control module162and accessible by the storage entities108, as will be described in detail below with reference toFIG. 3.

WhileFIG. 1Billustrates five storage entities106,108a,108b,108c, and108din the object-based storage system104, those of ordinary skill in the art will appreciate from the present disclosure that various other combinations of storage entities, servers and/or computing devices in the object-based storage system104can be implemented and have not been illustrated for the sake of brevity. Each of the depicted example storage entities106,108a,108b,108c, and108dof the object-based storage system104can be implemented on the same or separate computing devices. In some implementations, the object-based storage system104can be a geographically-distributed storage system, including multiple computing devices networked over multiple locations.

FIG. 2Ais a block diagram of a storage environment200demonstrating a first approach to storing multiple copies of parity data corresponding to a data object, in accordance with some implementations. In some implementations, this approach is used when the parity compression indicator stored in the compression setting163(FIG. 1B) indicates that the parity compression is turned off. As such, parity objects are generated and stored for duplicate data objects.

In the approach shown inFIG. 2A, an ingest storage entity with memory202receives a recording request to store multiple copies of a respective data object208and to back up each of the multiple copies using parity data. The ingest storage entity generates the number of copies of the data object208as indicated by the copy count, e.g., in the memory202. After writing copies of the data object208to the memory202, the ingest storage entity sends the storage data and instructions corresponding to each of the data object208to one or more parity-storing storage entities. A parity-storing storage entity, with memory204(e.g., RAM) and persistent storage206(e.g., non-volatile memory), receives the storage data and instructions, and stores each incoming data object208in the memory204as respective data object208-p. The parity-storing storage entity optionally sends a feedback message to the ingest storage entity after each data object has been stored in the memory204.

The storage technique illustrated inFIG. 2Ais inefficient and wasteful of computational resources. For example, if 1000 copies of data object208and 500 copies of parity data object208are requested to be stored in the storage environment200, the communication path between the ingest storage entity and one or more storage entities transports 1500 copies of object, 1500 write instructions, and 1500 acknowledgment messages.FIG. 2Aillustrates that the parity-storing storage entity translates the data object208-pin the memory204into corresponding parity data values210and moves them to the persistent storage206by performing a one-to-one translation and copying.

FIG. 2Bis a block diagram of a storage environment250demonstrating a second approach to storing parity data corresponding to a data object208in accordance with some implementations. In some implementations, this approach is used when the parity compression indicator stored in the compression setting163(FIG. 1B) is turned on. As such, compressed parity objects are generated and stored for duplicate data objects in order to save space and bandwidth for data object storage. Thus, the storage environment250shown inFIG. 2Bis an improvement over the storage environment200shown inFIG. 2A. Elements common toFIGS. 2A and 2Binclude common reference numbers, and the differences betweenFIGS. 2A and 2Bare described herein for the sake of brevity.

To that end, the storage environment250includes memory of ingest storage entity202, memory of parity storage entity204, and storage of parity storage entity206. In contrast to the approach shown inFIG. 2A, a single copy of the data object208is stored in the memory202of the ingest storage entity. In some implementations, the ingest storage entity sends a write instruction to one or more parity-storing storage entities in order to translate the data object208into corresponding parity data and in order to make a particular number of copies of the parity data object. In some implementations, the ingest storage entity pushes data object208to the parity-storing storage entity, while in some other implementations the ingest storage entity instructs the parity-storing storage entity to retrieve the data object208from the memory202. In some implementations, after the parity-storing storage entity obtains the data object208from the memory202of the ingest storage entity, the parity-storage entity stores the data object208in the memory204as data object208-p. In some implementations, the parity-storing storage entity sends a communication back to the ingest storage entity in order to indicate that the parity-storage entity has stored the data object208-pin the parity storage entity memory204.

Relative to the first approach described above with reference toFIG. 2A, the second approach illustrated inFIG. 2Bsaves both storage space and communication bandwidth. For example, if 1000 copies of data object208and parity data object208are requested to be stored in the storage environment250, the communication path between the ingest storage entity and one or more storage entities transports one copy of object, one write instruction, and possibly one acknowledgment message. Thus, relative to the first approach shown inFIG. 2A, the second approach as shown inFIG. 2Breduces the disk overhead and computational resources for writing objects, so that more concurrent data objects208can be processed and stored.

FIG. 2Cis a block diagram of a storage environment280demonstrating a third approach to storing parity data corresponding to multiple data objects208-1,208-2,208-3,208-4,208-5. . .208-N, in accordance with some implementations. In some implementations, this approach is used when the parity compression indicator stored in the compression setting163(FIG. 1B) is turned on. As such, compressed parity objects are generated and stored for duplicate data objects in order to save space and bandwidth for data object storage. The storage environment280shown inFIG. 2Cis an improvement over the storage environment200shown inFIG. 2A. Elements common toFIGS. 2A and 2Cinclude common reference numbers, and the differences betweenFIGS. 2A and 2Care described herein for the sake of brevity.

To that end, the storage environment280includes memory of ingest storage entity202, memory of parity storage entity204, and storage of parity storage entity206. In some implementations, the ingest storage entity detects that a number of data objects stored at the data-storing storage have matching values, e.g., the data objects208-1,208-2,208-3,208-4,208-5. . .208-N. In response to detecting duplication of the data objects208, the ingest storage entity generates a copy count and communicates the copy count to the parity-storing storage entity. Upon receiving the communication from the ingest storage entity, the parity-storing storage entity does not create additional copies of data object208in the memory204of the parity storage entity. Instead, as shown inFIG. 2C, the parity-storing storage entity generates parity value210from one copy of data object208-pand stores the parity data object210into the persistent storage206.

FIG. 2Cshows that the use case of common storage of parity data for unique copy recording is not limited to batch requests as shown inFIGS. 1B and 2B. In case duplicate data exist in the data requested for storage, the duplication of data objects can be recognized and the savings would be realized by reducing the amount of parity data generated and stored. Thus, relative to the first approach described above with reference toFIG. 2A, the third approach as shown inFIG. 2Csaves the storage space for storing the parity object and saves the communication bandwidth. For example, if 1000 matching data objects208and parity data are requested to be stored in the storage environment280, the communication path between the ingest storage entity and one or more storage entities transports one copy of object, one write instruction, and possibly one acknowledgment message. Thus, relative to the first approach shown inFIG. 2A, the third approach as shown inFIG. 2Creduces the disk overhead for writing parity object210, so that space can be saved for storing the data objects208.

FIG. 3is a block diagram of a storage environment300with three data-storing storage entities302,304, and306, and two parity-storing storage entities308and310(e.g., a DEC pattern of 3:2), demonstrating compressed parity data storage in accordance with some implementations.FIG. 3illustrates the outcome of applying the compression techniques described above with reference toFIGS. 2B and 2C. In particular, as shown inFIG. 3, the number of parity objects stored at parity storage entity0308and parity storage entity1310has decreased relative to using the first approach shown inFIG. 2A.

To that end, in some implementations, the error control module162receives a request to store N copies of the data object at M data storage entities. In the request, N is the copy count as derived from a batch request (e.g., the batch request102aas shown inFIG. 1B) or from recognizing repeat patterns in the data objects (FIG. 2C). The storage system also includes X parity storage entities for storing parity objects, where the X parity storage entities are different from the M data storage entities, e.g., M data servers (or M data stripes) and X parity servers (or X parity stripes). In the example of storage environment300, the request specifies storing 29 copies of the data object across three data stripes and storing parity objects across two parity stripes, e.g., N=29, M=3, and X=2, and DEC pattern of 3:2.

In response to receiving the request, the error control module162generates the parity object0330for a data object set320, which contains three copies of the data object distributed across the three data storage entities302,304, and306. Additionally, the error control module162determines whether the copy count29is divisible by the number of data storage entities302,304, and306. Since 29 is not divisible by 3 data stripe count (e.g., data stripe0302, data stripe1304, and data stripe2306), the error control module162generates and retains parity object2332for the last data object set324. Further, according to the DEC pattern of 3:2, the error control module162generates the parity object1340that corresponds to the first data object set320and generates the parity object3342that corresponds to the last data object set324.

In the event of disk or hardware failure, the missing data object(s) can be recovered using the common parity, e.g., the parity object0330and/or the parity object1340. In some implementations, in order to establish the association of other copies of the data objects to the parity object0330and parity object1340, the error control module162generates the manifest data164. For example, inFIG. 3, records in the manifest164link the parity object0330and the parity object1340with another set of three data objects, e.g., the set of data objects322. As such, the error control module162compresses the repeating pattern in the parity data and represents it as a single instance of parity, e.g., the parity object0330and/or the parity object1340. In some implementations, a repeat count is stored with the parity object(s)330and/or340in order to establish the association of the parity object(s) with the data objects.

It should be noted that thoughFIG. 3illustrates an example of distributing 29 data objects sequentially and evenly across three data storage entities and generating the parity objects330,332,340, and342for the 29 data objects, one of ordinary skill in the art will appreciate that the parity compression techniques described herein can be used for any number of data objects and/or storage entities and a variety of data object storage arrangements, e.g., nonsequential storage of data objects.

FIG. 4is a flowchart representation of a method400of writing compressed parity data in accordance with some implementations. In some implementations and as detailed below as an example, the method400is performed at a fault-tolerant object storage system, such as the object-based storage system104inFIG. 1B, or a component of the storage system104, such as the storage entity108cinFIG. 1B. In some implementations, the fault-tolerant object storage system includes M data storage entities (e.g., a cluster of servers), where each of the M data storage entities is configured to store raw media data on an object-basis (e.g., a video, an episode of TV show, or 10 MB of multimedia data). In some implementations, the fault-tolerant object storage system also includes a number of parity storage entities for storing parity objects (e.g., the parity storage entities308and310for storing the parity objects330,332,340, and342, as shown inFIG. 3). In some implementations, these parity storage entities are different from the M data storage entities for storing data objects, e.g., the parity stripes308and310are different servers from the data stripes302,304, and306as shown inFIG. 3.

In some implementations, the method400is performed by processing logic, including hardware, firmware, software, or a combination thereof. In some implementations, the method400is performed by a processor, a controller, and/or a circuitry executing code stored in a non-transitory computer-readable medium (e.g., a memory). In some implementations, the method400is performed by an error control module, such as the error control module162inFIG. 1B. Briefly, the method400includes obtaining a request to storing duplicate copies of a data object and generating compressed parity object(s) in response to receiving the request.

To that end, as represented by block410, the method400includes obtaining a request to store N copies of a data object within the fault-tolerant object storage system. As explained above with reference toFIGS. 1B and 2B, in some implementations, one or more client requests are aggregated or packaged into a batch request. In some implementations, the request is generated in response to detecting duplication of the data object, as shown inFIG. 2C.

As represented by block420, the method400also includes storing the N copies of the data object across the M data storage entities in response to the request. In some implementations, as represented by block422, the N copies of the data object are distributed across the M data storage entities such that any two sequential copies of the N copies are stored on two separate storage entities of the M data storage entities. In other words, each instance of the data object is stored on one server, e.g., a first instance of the data object is stored on server302, a second instance is stored on server304, and a third instance is stored on server306, as shown inFIG. 3.

As represented by block430, the method400includes generating a first parity object for a first subset of M copies of the N copies of the data object. In some implementations, as represented by block432, the first parity object is stored on a first parity storage entity separate from the M data storage entities. For example, in a DEC pattern of 3:2 as shown inFIG. 3, the first parity object0330is generated for the data object set320comprising the first three data objects, and the first parity object0330is stored on the parity stripe308separate from the three data stripes302,304, and306.

Still referring toFIG. 4, as represented by block440, the method400includes generating a manifest linking the first parity object with one or more other subsets of M copies of the N copies of the data object. In other words, the manifest establishes the association of other copies of the data object to the parity object generated above. For example, as shown inFIG. 3, in DEC pattern of 3:2, after generating the first parity object0330for the first three data objects, the manifest164links the first parity object0330with another three data objects. In some implementations, a repeat count is stored with the parity object in order to establish the association of the parity object with other duplicate copies of the data object.

Writing compressed parity data in accordance with various implementations of method400changes how the parity is generated. Instead of generating parity for copies of the data object, the file system generates parity for a single copy of stored data object. In the event of disk or hardware failure, the data object can be recovered using the common parity. For example, in a conventional system with a DEC striping pattern of 16:2, the parity storage overhead would be 2/16, corresponding to 12.5%. In such conventional system, the parity storage overhead for a 10 MB video object that has 2000 copies stored in the file system using 16:2 distributed erasure coding would be (10 MB*2000)*12.5%=2500 MB. Using the parity compression method400described herein, because the copy count2000is divisible by the number of data stripes16, two parity objects would be generated. Thus, the parity overhead would be 2*10 MB=20 MB. Thus, the larger the copy count, the more significant the parity overhead savings would be realized in accordance with implementations described herein. By reducing the amount of parity data required for fault tolerance, the system in accordance with various implementations described herein increases the amount of multimedia data that can be stored in the file system and reduces the disk overhead for writing data. As such, more concurrent video objects can be stored at the same time on less amount of hardware.

FIG. 5is a flowchart representation of a method500of writing parity data in accordance with some implementations. In some implementations and as detailed below as an example, the method500is performed at a fault-tolerant object storage system, such as the object-based storage system104inFIG. 1B, or a component of the storage system104, such as the storage entity108cinFIG. 1B. In some implementations, the fault-tolerant object storage system includes M data storage entities (e.g., a cluster of servers), where each of the M data storage entities is configured to store raw media data on an object-basis (e.g., a video, an episode of TV show, or 10 MB of multimedia data). In some implementations, the fault-tolerant object storage system also includes a number of parity storage entities for storing parity objects (e.g., the parity storage entities308and310for storing the parity objects330,332,340, and342, as shown inFIG. 3). In some implementations, these parity storage entities are different from the M data storage entities for storing data objects, e.g., the parity stripes308and310are different servers from the data stripes302,304, and306as shown inFIG. 3.

In some implementations, the method500is performed by processing logic, including hardware, firmware, software, or a combination thereof. In some implementations, the method400is performed by a processor, a controller, and/or a circuitry executing code stored in a non-transitory computer-readable medium (e.g., a memory). In some implementations, the method500is performed by an error control module, such as the error control module162inFIG. 1B. Briefly, the method500includes obtaining a copy count value N associated with a request to storing N copies of a data object, generating parity object(s) in response to receiving the request, where duplicate parity objects are generated when a compression indicator is off and compressed parity data is generated when the compression indicator is on, and restoring missing data utilizing the parity data.

To that end, as represented by block510, the method500includes obtaining a copy count value N associated with a request to store N copies of a data object within the fault-tolerant object storage system. As represented by block512and as explained above with reference toFIGS. 1B and 2B, in some implementations, the copy count is specified in a batch request. The use case is not limited to batch request. As explained above with reference toFIG. 2C, in case duplicate data exists in the data for storage, the copy count is obtained by identifying the number of duplicates in the data, as represented by block514. The savings thus can be realized by reducing the amount of parity data generated and stored. In such implementations, the copy count is obtained by receiving multiple requests (e.g., client requests) to store data within the fault-tolerant object storage system, identifying the N copies of the data object in the data (i.e., duplicates or identical data) associated with the multiple requests, and generating the request to store the N copies of the data object within the fault-tolerant object storage system.

In some implementations, as represented by block520, the method500includes storing N copies of the data object across the M data storage entities in response to the request. As represented by block530, the method500includes generating a first parity object for a first subset of M copies of the N copies of the data object and generating a manifest linking the first parity object with one or more other subsets of M copies of the N copies of the data object. In some implementations, the N copies of the data object are evenly and/or sequentially distributed across the M data storage entities, and the first parity object is generated based on the M copies of the data object in the first subset. For example, inFIG. 3, the 29 instances of the data object are evenly and sequentially distributed across 3 data stripes on 3 servers, e.g., N=29 and M=3. The first subset320contains three instances of the data object, and these three instances are stored on three different servers302,304, and306. The parity object0330is calculated based on the subset320.

In some implementations, as represented by block532, the method500further includes (a) generating a second parity object for the first subset of M copies of the N copies of the data object, where the second parity object is different from the first parity object; (b) linking, within the manifest, the second parity object with one or more other subsets of M copies of the N copies of the data object, and (c) storing the second parity object on a second parity storage entity separate from the first parity storage entity. For example, inFIG. 3, there are two parity stripes308and310. The first parity object0330is generated for the set320corresponding to the first three data objects. The second parity object1340is also generated for the set320corresponding to the first three data objects. The second parity object1340is stored on the parity stripe310separate from the parity stripe308, where the first parity object0330is stored.

Still referring toFIG. 5, in some implementations, as represented by block540, the method500includes determining whether or not a compression indicator is on, e.g., the error control module162determines whether the compression setting163is configured by the user to turn on the compression. In some implementations, based on a determination that the compression indicator indicates that the parity compression is off (“No” path from block540), the method500includes generating more parity objects for duplicate data, as described above with reference toFIG. 2A. On the other hand, with reference to block560, in accordance with a determination that the compression indicator indicates that the parity compression is on (“Yes” path from block540), the method500includes determining whether N is divisible by M, as represented by block560. In case N is not divisible by M, as represented by block570, the method500includes determining a remainder number of the N copies of the data object, where the remainder number of copies is less than M, and generating a remainder parity object for a last subset of N copies of the data object, e.g., generating the remainder parity object for the remainder number of the N copies of the data object. For example, inFIG. 3, since the copy count29is not divisible by the data stripe count3, the last parity object2332will be different from the first parity object0330and thus is retained.

In some implementations, as represented by block572and similar to the step represented by block532, once the remainder parity object is generated, the method500further includes (a) generating an additional remainder parity object for the last subset of N copies of the data object, where the additional remainder parity object is different from the remainder parity object; (b) linking, within the manifest, the additional remainder parity object with the remainder number of the N copies of the data object, and (c) storing the additional remainder parity object on a second parity storage entity that is separate from the first parity storage entity. For example, inFIG. 3, there are two parity stripes308and310. The remainder parity object2332is generated for the last subset set324, which corresponds to the last two remainder data objects. The additional remainder parity object3344is also generated for the remainder set324corresponding to the last two remainder data objects. The additional remainder parity object3342is stored on the parity stripe310that is separate from the parity stripe308, where the remainder parity object2332is stored.

In some implementations, as represented by block580, the method500includes restoring a missing data object using a corresponding parity object associated with the missing data object and corresponding data objects stored in the fault-tolerant object storage system. In other words, to recover a missing data object in a data stripe, the corresponding data objects in the other data stripes and parity stripe(s) (at the same offset and for the same length) are read and combined using the DEC algorithm to recreate the original data object. Because each of the stripes (data and parity) resides on a different server, a server may be lost and all its data can still be recovered. For example, inFIG. 3, if the data object in the subset322residing on the storage entity302(e.g., the data storage entity0302) is lost, the common parity object0330and the corresponding data object in the first subset320(e.g., the data object residing on the storage entity302in the first subset320) can be used to derive the values of the lost data object.

In some implementations, during the recovery process, the common parity object is located through the manifest164, as shown inFIG. 3. In some implementations, the common parity object includes a repeat indicator (e.g., a repeat count). As such, the common parity object is represented as a parity object with a corresponding repeat count. During the recovery process, the common parity object for the missing data object(s) can be located by evaluating the repeat count associated with the parity object.

FIG. 6is a block diagram of a computing device600in accordance with some implementations. In some implementations, the computing device600corresponds to a storage entity such as storage entity108cofFIG. 1Band performs one or more of the functionalities described above with respect to a storage entity. While certain specific features are illustrated, those skilled in the art will appreciate from the present disclosure that various other features have not been illustrated for the sake of brevity, and so as not to obscure more pertinent aspects of the embodiments disclosed herein. To that end, as a non-limiting example, in some implementations the computing device600includes one or more processing units (CPU's)602(e.g., processors), one or more output interfaces603(e.g., a network interface), a memory606, a programming interface608, and one or more communication buses604for interconnecting these and various other components.

In some implementations, the communication buses604include circuitry that interconnects and controls communications between system components. The memory606includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices; and, in some implementations, include non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices. The memory606optionally includes one or more storage devices remotely located from the CPU(s)602. The memory606comprises a non-transitory computer readable storage medium. Moreover, in some implementations, the memory606or the non-transitory computer readable storage medium of the memory606stores the following programs, modules and data structures, or a subset thereof including an optional operating system630and a parity data storage module640. In some implementations, one or more instructions are included in a combination of logic and non-transitory memory. The operating system630includes procedures for handling various basic system services and for performing hardware dependent tasks. In some implementations, the parity data storage module640is configured to create parity objects and compress parity information corresponding to a data object. To that end, the parity data storage module640includes a parity value determination module641, a parity data generation module642, a parity data compression module643, a parity data writing module644, a decompression module645and a request interpretation module646.

In some implementations, the parity value determination module641is configured to calculate a parity value corresponding to a data object set. To that end, the parity value determination module641includes a set of instructions641aand heuristics and metadata641b. In some implementations, the parity data generation module642is configured to generate one or more parity objects associated with a data object, and corresponding to one or more data object sets corresponding to the data object. To that end, the parity data generation module642includes a set of instructions642aand heuristics and metadata642b. In some implementations, the parity data compression module643is configured to compress one or more generated or determined parity objects, including in some implementations, generating a manifest linking the parity object with one or more other subsets of the data object. In some implementations, the parity data compression module643stores a repeat count with the parity object in order to establish the association of the parity object with other duplicate copies of the data object. To that end, the parity data compression module643includes a set of instructions643aand heuristics and metadata643b.

In some implementations, the parity data writing module644is configured to write one or more parity objects, including compressed parity data, repeat count, and/or manifest links. To that end, the parity data writing module644includes a set of instructions644aand heuristics and metadata644b. In some implementations, the decompression module645is configured to decompress compressed parity data. To that end, the decompression module645includes a set of instructions645aand heuristics and metadata645b. In some implementations, the request interpretation module646is configured to read and extract information from a write request (e.g., received from an ingest storage entity). To that end, the request interpretation module646includes a set of instructions646aand heuristics and metadata646b.

Although the parity value determination module641, parity data generation module642, parity data compression module643, parity data writing module644, decompression module645and request interpretation module646are illustrated as residing on a single computing device600, it should be understood that in other embodiments, any combination of the parity value determination module641, parity data generation module642, parity data compression module643, parity data writing module644, decompression module645and request interpretation module646can reside in separate computing devices in various implementations. For example, in some implementations each of the parity value determination module641, parity data generation module642, parity data compression module643, parity data writing module644, decompression module645and request interpretation module646resides on a separate computing device.