Patent Publication Number: US-9846540-B1

Title: Data durability using un-encoded copies and encoded combinations

Description:
BACKGROUND 
     Several leading technology organizations are investing in building technologies that sell “software-as-a-service”. Such services provide access to shared storage and/or computing resources to clients or subscribers. Within multi-tier e-commerce systems, combinations of different types of physical and logical resources may be allocated to subscribers and/or their applications, such as whole physical or virtual machines or storage devices, key-addressable object storage, CPUs, memory, network bandwidth, I/O capacity, or bundled resources such as database servers, scientific computation clusters, and the like. 
     For many storage services, the significant selling points of the service may include very high levels of data durability, suitable for enterprise-level mission-critical applications. Some network-accessible storage services may be designed to support data durability levels of 99.99999999% or higher, for example. Such high levels of durability may be difficult for businesses and individuals to support economically on their own premises, making the prospect of using the network-accessible storage service extremely attractive, at least for the more important or valuable portions of client data. 
     One straightforward approach to supporting high durability involves storing redundant copies of objects. For example, writes to storage objects may typically be replicated at several storage devices in such environments, often at different physical locations. In order to reduce storage costs while maintaining high durability levels, sophisticated algorithms may be used that divide a given storage object into smaller partitions or segments and then distribute encodings of the partitions among numerous storage devices. Such approaches, which can include various types of erasure coding techniques, may provide similar durability to simpler replication strategies, while requiring less storage than the simpler replication strategies. However, in high-durability storage systems that rely on encoding partitions of storage objects, the costs of decoding and re-assembling the encoded partitions may become significant, at least for some types of applications. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  illustrates an example of a system in which a storage service is configured to support high durability using un-encoded copies and encoded combinations of storage objects, according to at least some embodiments. 
         FIG. 2  illustrates an example of a provider network comprising multiple data centers, in which a given storage service node may store un-encoded copies and encodings of combinations of storage objects, according to at least some embodiments. 
         FIG. 3  illustrates example constituent elements of a durability manager of a storage service, according to at least some embodiments. 
         FIG. 4  illustrates an example approach to combining storage objects into durability groups, according to at least some embodiments. 
         FIG. 5  illustrates an example approach to determining the placement of storage objects on storage service nodes, according to at least some embodiments. 
         FIG. 6  is a flow diagram illustrating aspects of operations that may be performed at a storage service to support high durability, according to at least some embodiments. 
         FIG. 7  is a flow diagram illustrating aspects of operations that may be performed to determine durability group membership, according to at least some embodiments. 
         FIG. 8  is a flow diagram illustrating aspects of operations that may be performed to recover storage objects in the event of one or more failures, according to at least some embodiments. 
         FIG. 9  is a block diagram illustrating an example computing device that may be used in at least some embodiments. 
     
    
    
     While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to. 
     DETAILED DESCRIPTION 
     Various embodiments of methods and apparatus for implementing data durability for storage objects at a provider network using un-encoded copies and combination encodings are described. Networks set up by an entity such as a company or a public sector organization to provide one or more network-accessible services (such as various types of cloud-based storage, computing or database services) accessible via the Internet and/or other networks to a distributed set of clients may be termed provider networks herein. In the remainder of this document, the term “client”, when used as the source or destination of a given communication, may refer to any of the computing devices, processes, hardware modules or software modules that are owned by, managed by, or allocated to, an entity (such as an organization, a group with multiple users or a single user) that is capable of accessing and utilizing at least one network-accessible service of the provider network. A given provider network may include numerous data centers (which may be distributed across different geographical regions) hosting various resource pools, such as collections of physical and/or virtualized computer servers, storage servers with one or more storage devices each, networking equipment and the like, needed to implement, configure and distribute the infrastructure and services offered by the provider. A number of different hardware and/or software components, some of which may be instantiated or executed at different data centers or in different geographical regions, may collectively be used to implement each of the services in various embodiments. 
     In some embodiments, a storage service of a provider network may be designed to support configurable levels of durability for different sets of storage objects, e.g., based on respective service level agreements entered into with clients of the service. Generally speaking, the manner in which the client-visible data of a file or a key-indexed object is physically organized or stored at some combination of one or more storage devices may be controlled by the service, and details of the physical layout of the data need not be disclosed to the clients, as long as the service level agreements are met. The storage service may, for example, decide to partition or shard the client&#39;s data in various ways, and/or use techniques such as erasure coding to provide the desired levels of data durability, performance, high availability, and/or security. Using sophisticated encoding schemes may help to reduce the total amount of storage space required for a given level of durability, e.g., relative to storing several full un-encoded copies of the data. For some types of operations requested by clients in scenarios in which encoded versions and/or partitions of the data objects are stored, the service may generally be responsible for reconstructing the un-encoded versions (e.g., versions in which a requested subset or all of the contents of the storage object are presented in a format expected by the client), and providing the un-encoded versions to the clients. Thus, in one such embodiment, a client may wish to store M megabytes of text in a given storage object S. The service may divide the object S into N partitions, each with M/N megabytes of text, and store some number of encodings E of the partitions on K different storage devices, e.g., using erasure coding to achieve a desired durability level while optimizing the amount of space that is used. In response to a request to read the object S, the service may have to retrieve the encodings E from some subset or all of the K devices, perform the computations needed to decode the encodings E into the N partitions, concatenate the N partitions in the correct order, and provide the reconstructed object to the requesting client. 
     In some embodiments, the storage service may support a set of “local” computation operation types to be performed by the service on contents of client-owned storage objects at client request. Such operation types may be termed “local” with respect to the storage service because they may typically be implemented on the storage devices or nodes at which the client&#39;s data is stored, instead of being performed at the client&#39;s own computing devices after the client has received an un-encoded copy of the storage object from the service. For example, in one such embodiment, a local operation to determine, for a storage object that comprises text, how many times (and/or in which specific lines of text) a specified string or regular expression occurs, similar to the “grep” command supported in certain operating systems, may be supported by the storage service. If all the contents of a particular storage object are stored in an encoded format, the service may have to use nontrivial amounts of computation to first decode the contents, and then perform the text search operations corresponding to the grep command. Accordingly, in at least some embodiments, a hybrid approach may be used, in which some number of un-encoded copies of the full storage object are stored, and some number of encodings are also stored. The un-encoded copies may be preferred for performing the local computations, while the encoding may be used to reconstruct the un-encoded copies in the event of data loss, as described below in further detail. Such a hybrid approach may help the storage service achieve both (a) desired durability levels with space efficiency comparable to that of a fully-encoded approach, and (b) computational efficiency that results from access to un-encoded copies of the data. 
     According to at least one embodiment, as part of such a hybrid approach, a durability manager of a storage service may classify storage objects into durability groups (DGs), and then store encodings of several members of the durability groups taken together, as well as un-encoded copies of each of the members. The durability manager may thus be configured to identify a set of one or more other storage objects Sk to be included in a DG with a particular storage object Sj, where an encoding of a combination of at least the particular storage object Sj and one other storage object of the DG is to be stored at a node of the storage service to achieve a target data durability. The durability manager may also determine a number U of un-encoded copies of the particular storage object Sj to be stored, in addition to the encoding, to achieve the target data durability and a desired level of performance for a set of local computation operation types supported by the storage service. The set of un-encoded copies and encodings corresponding to a given DG may be referred to as the “artifacts” or “durability artifacts” of the DG herein. An encoding plan for the particular storage object Sj may then be generated in at least some embodiments, specifying (a) the specific storage objects of the durability group to be combined for the encoding, (b) a computation function to be used to obtain the encoding, and (c) a placement map indicating nodes of the storage service to be used to store the U un-encoded copies and the encoding. In accordance with the placement map, the encoding and the U un-encoded copies of the particular storage object may be stored at various selected nodes of the service. When a request to perform a local computation operation of a type included in the set of local computation operation types is received, the request may be directed to a particular node of the storage service at which an un-encoded copy of the particular storage object is located. In the event of a failure, e.g., in response to a detection that at least one of the un-encoded copies of the particular storage object is inaccessible, a new un-encoded copy of the particular storage object may be reconstructed based at least in part on the encoding. The same kind of approach may be taken for each of the other members Sk of the durability group—e.g., some number of un-encoded copies may be stored and used for supported local computations, and some set of encodings may be stored, such that the encodings may be used to re-generate the un-encoded copies in the event of failures. Storing encodings of the combinations of storage objects, rather than all of the storage objects separately, may help amortize the added storage costs typically incurred for high durability. 
     A number of different criteria may be used to identify the specific storage objects that are to form a given durability group in various embodiments. For example, in one embodiment, storage objects may be included in a durability group based on similar sizes, proximity in the timing of write requests to the storage objects (e.g., two objects to which writes were directed within a few milliseconds of each other may be included in a single durability group with a higher probability than objects to which the most recent writes were directed minutes or hours apart), common ownership by the same client entity, logical relationships between the objects (e.g., objects belonging in the same directory of a namespace may be more likely to be included in the same durability group than objects belonging to different directories), and so on. The formation of a new durability group, and/or the inclusion of a particular storage object in an existing durability group, may be triggered in some embodiments by the occurrence of an event—e.g., such durability group membership decisions may be triggered in response to receiving a write request from a client. 
     The number of un-encoded and/or full copies of a given storage object, as well as other details of the encoding plan, may be selected based on various combinations of criteria in different embodiments. For example, such criteria may in one embodiment include one or more of: (a) the size of the given storage object, (b) an expected frequency of local computation operations directed at the given storage object, (c) an expected frequency of access requests directed at the given storage object, (d) an expected lifetime of the given storage object (e.g., how long the storage object is expected to remain accessible before being deleted), (e) a metric of an expected amount of computation required to reconstruct the given storage object based at least in part on the encoding, or (f) a metric of a computational capacity of a node of the storage service at which either an un-encoded copy of one or more of the members of the durability group, or one or more encodings of the durability group members are to be stored. 
     In some embodiments, large provider networks supporting storage services of the kind described above may be organized into hierarchies based for example on geographical location or infrastructure failure independence. For example, a provider network may comprise a plurality of geographically distributed data centers, grouped into geographical regions, such as a “U.S. East” region, a “U.S. West” region, an “Asia-Pacific” region, and so on. In some embodiments, the provider network may comprise a plurality of “availability containers”. Each availability container may include a respective set of resources resident at one or more data centers, engineered in such a manner that effects of a failure within one availability container may not be expected to spread to any other availability container. For example, components of the power, cooling, networking, and security infrastructure may be set up in such a way that failures across different availability containers are not correlated. The various availability containers (which may also be referred to as availability zones) may be said to have independent failure profiles and independent availability profiles in such embodiments. According to some embodiments, the un-encoded copies and the encodings associated with a given storage object may be distributed among different availability containers of the provider network. For example, in accordance with the placement map generated by the durability manager, one un-encoded copy of a particular storage object may be stored in a first availability container, a second un-encoded copy may be stored in a second availability container, and an encoding may be stored in a third availability container. 
     According to at least one embodiment, a given storage service node, or a given storage device used by the storage service, may be configured to store un-encoded copies of some set of storage objects, as well as encodings of some set of storage object combinations. Thus, in such embodiments, a given storage device, storage service node, data center, or availability container need not be restricted to storing only un-encoded copies of storage objects, or to storing only encodings. The storage service may in some embodiments distribute encodings and/or un-encoded copies across storage devices or nodes based on the specific performance and other capabilities of the devices or nodes. 
     Example System Environments 
       FIG. 1  illustrates an example of a system in which a storage service is configured to support high durability using un-encoded copies and encoded combinations of storage objects, according to at least some embodiments. It is noted that  FIG. 1  is a simplified presentation of some the core concepts of the durability mechanism, not intended as a detailed representation of an actual implementation. For ease of explanation, for example, un-encoded copies of only a single durability group  150 A are shown, the storage objects of that durability group are assumed to be of the same size, and a relatively simplistic distribution of encodings and un-encoded copies associated with durability group  150 A is shown. 
     System  100  includes a provider network  102  within which a storage service accessible to clients  170  is implemented in the depicted embodiment. The provider network may include a plurality of availability containers  110 , such as availability containers  110 A,  110 B and  110 C, each comprising a plurality of service nodes  122  (e.g., service nodes  122 A and  122 B of availability container  110 A). Service nodes  122  may also be referred to as “storage nodes” and/or “back-end nodes”. A given service node  122  may, for example, include some amount of storage space (e.g., one or more disk-based storage devices, solid-state drives, or the like), as well as some computation resources (CPUs or processing cores), memory, networking resources and the like. Each availability container  110  may include numerous service nodes and/or other resources distributed among portions or all of one or more data centers, as described earlier, engineered in such a way that the availability profile (or failure profile) of each container is independent of the availability profile of other containers. That is, an occurrence of a failure (such as a storage device failure, CPU failure, electrical/power failure, a cooling system failure, or a networking link failure) in a given availability container is not expected to result in a correlated failure at any other availability containers. As a consequence of the design of the availability containers, storing respective copies of data at two different availability containers may result in substantially higher data durability than if the copies were stored within the same availability container, for example. 
     A durability manager  180  of the storage service is configured to determine how desired durability levels are to be supported for various storage objects  120  (e.g.,  120 A,  120 B,  120 C and  120 D) using some combination of un-encoded copies and encodings. Clients  170  may submit storage-related work requests, such as requests to create, write, read, and/or delete storage objects  120 , to work request routers  182  of the storage service, as indicated by arrow  133 . Work request routers  182  may represent front-end components of the storage service, with network addresses accessible to clients  170 . The work request routers  182  may redirect the work requests to the appropriate back-end service nodes  122  of the storage service, where the corresponding work operations (such as physical reads and writes) may be performed, as indicated by arrows  134 A,  134 B and  134 C. It is noted that in some embodiments, clients may be permitted to submit work requests directly to the service nodes, and in some such embodiments work request routers  182  may not be implemented. In at least some embodiments, in addition to (or instead of) the work request routers  182 , the durability manager  180  may read or write data to service nodes  122  (e.g., to store encodings on behalf of the clients, or to reconstruct un-encoded copies from encodings), as indicated by arrows  137 A,  137 B and  137 C. 
     In the depicted embodiment, the durability manager  180  is responsible for aggregating various storage objects  120  into durability groups  150  (e.g.,  150 A and  150 B), and using a hybrid approach for physical storage of the data of the durability group members, which includes storing some selected number of un-encoded or unmodified copies of the members&#39; data, and some selected number of encodings derived from combinations of the members&#39; data. It is noted that the terms “un-encoded copy” and “encodings” are used herein to distinguish storage object versions that clients initially generate (which are considered the un-encoded versions from the perspective of the service) from the products of computation functions applied by the service (which are considered encodings from the perspective of the service) to the client-generated versions. For example, a client may submit a text file containing one megabyte of English text as a storage object. A copy of the client-submitted file may be deemed “un-encoded” if, given the copy, the client is able to read and understand the contents of the file without any additional decoding. In contrast, if the storage service applies an erasure coding function, an exclusive-or function, or some other transformation to a portion or all of the file, or to a combination of contents of different files, the resulting output may be considered an encoding. 
     The durability manager  180  may also communicate with the work request routers  182 , as indicated by arrow  167 , e.g., to notify the work request routers  182  regarding the locations of various portions or replicas of un-encoded and encoded client data. In the depicted example, the durability manager  180  has decided to include four storage objects  120 A,  120 B,  120 C and  120 D within durability group  150 A. The membership of DG  150 A may have been determined based on the sizes of the objects  120 A, for example, or on when the objects were written. An un-encoded copy of object  120 A, UEC- 120 A- 1 , is stored at service node  122 A within availability container  110 A of the provider network. Similarly, un-encoded copy UEC- 120 B- 1  of storage object  120 B is stored at service node  122 B in availability container  110 B, un-encoded copy UEC- 120 C- 1  of storage object  120 C is stored at service node  122 K in availability container  110 B, and un-encoded copy UEC- 120 D- 1  of storage object  120 D is stored at service node  122 L in availability container  110 B. 
     In addition to the un-encoded copies, encodings derived from combinations of some of the members of durability group  150 A are also stored, e.g., at the direction of durability manager  180  in the depicted embodiment. In various embodiments, different encoding functions or algorithms may be used, and different combinations of the members of each durability group may be encoded collectively using the selected functions or algorithms. In the depicted example, a simple exclusive-or (xor) operation is used to generate the encodings, and as noted above, the objects  120 A,  120 B,  120 C and  120 D are assumed to be identical in size. For example, encoding  135 A, obtained by applying a bitwise exclusive-or to  120 A,  120 B and  120 C ( 120 A xor  120 B xor  120 C), is stored at service node  122 P in availability container  110 C, encoding  135 B ( 120 A xor  120 C xor  120 D) is stored at service node  122 Q, encoding  135 C ( 120 A xor  120 B xor  120 D) is stored at service node  122 R, and encoding  135 D ( 120 B xor  120 C xor  120 D) is stored at service node  122 S. 
     The durability mechanism being used in the example of  FIG. 1  is intended to enable the storage service to withstand the loss of any three service nodes, without irrecoverable loss of the contents of any of the storage objects of any durability group  150 , while using less storage space than would be required if three full un-encoded copies of each storage object were stored. Since each data object  120 A- 120 D has the same size, each encoding requires as much space as one of the storage objects (since a result of an exclusive-or operation takes as much space as any one of the operands). The total amount of storage space required is 8× the amount of space taken by any given storage object  120  of the durability group—4× for the four un-encoded copies, and 4× for the encodings. At the same time, the durability mechanism also allows local computation operations (such as substring searches, regular expression matches, or “grep”-like operations) to be performed efficiently at the service nodes where the un-encoded copies are stored, instead of requiring the storage objects to be reconstructed from encodings when such a computation is to be performed. With respect to a request for a supported local computation on the contents of storage object  120 A, for example, one of the work request routers  182  may simply direct the request to service node  122 A, where the computation may be performed, and the result of the computation may be returned (e.g., to the work request router  182  and thence to the requesting client  170 ). 
     Consider various examples of failures at three different service nodes, and how the various un-encoded copies and encodings may be reconstructed using the durability approach taken in  FIG. 1 &#39;s simplified example. Generally speaking, the reconstruction process in a given implementation may be dependent on mathematical properties of the encoding function used: for example, the exclusive-or operation has properties such as “A xor B xor C=(A xor B) xor C”, “A xor A=0” and “A xor 0=A”. If storage nodes  122 A,  122 B and  122 K failed, for example, the service would need to reconstruct un-encoded copies of  120 A,  120 B and  120 C using the encodings and UEC- 120 D- 1 . One way in which  120 A could be reconstructed is, for example, to perform the following computations: (a) temp1= 135 A xor  120 D (using encoding  135 A and UEC- 120 D- 1 ); (b)  120 A=temp1 xor  135 D (using temp1 and encoding  135 D). Similarly, un-encoded copies of  120 B or  120 C could also be retrieved using analogous exclusive-or operations. In general, for durability group  150 A, if any three un-encoded copies were lost as a result of a failure at respective service nodes  122 , the un-encoded copies could each be recovered. If the storage nodes containing any three (or even all four) encodings were lost, but the un-encoded copies of the storage objects remained accessible, the encodings could be generated simply by performing exclusive-or operations on the un-encoded copies—e.g., if  135 A,  135 B and  135 C were lost, the un-encoded copies of  120 A,  120 B and  120 C could be used to regenerate  135 A, un-encoded copies of  120 A,  120 C and  120 D could be used to regenerate  135 B, and un-encoded copies of  120 A,  120 B and  120 D could be used to generate  135 C. Also, if any combination of three artifacts (chosen from  120 A- 120 D and  135 A- 135 D) were lost, the remaining artifacts may be used to regenerate the lost ones. For the encoding approach illustrated in  FIG. 1 , for example, in one implementation any encodings that can be regenerated solely from intact un-encoded copies may first be regenerated, followed by all un-encoded copies, followed by the remaining encodings. It is noted that in contrast to the scenario illustrated in  FIG. 1 , at least in some embodiments, more than one of the artifacts for a given DG may be stored at a given service node. Storing more than one artifact at the same node or at the same device would typically result in lower durability than storing each of the artifacts at different devices or nodes, but such lower durability may well be sufficient for certain objects and/or for certain clients. 
     An example of a durability calculation for a scenario similar to that depicted in  FIG. 1  follows. When computing the absolute durability (e.g., the absolute probability of losing the data of any given storage object), the failure rates of the storage devices (or service nodes) may be taken into account. Assume that each of the storage nodes  122  comprises a respective storage device, and that the storage device is the only type of component whose failure is relevant to the durability calculation. (This would be roughly equivalent to assuming that failures of other devices, such as CPUs, network cards and the like, are much less frequent than failures at storage devices.) Assume that the storage service is able to fully recover the desired durability one week after a storage device fails. Assume further that we have a storage device that will fail with a 1 in 20 chance each year, and (to simplify the calculations) that years are actually 50 weeks long instead of just over 52 weeks. Accordingly, there is a 1 in 1000 chance that a given storage device will fail each week. Assume further that when a storage device fails in any way, all its data is lost. 
     As a preliminary exercise, consider a scenario where two un-encoded copies of each storage object  120  are stored on different devices. The odds of a storage object&#39;s data being lost each week are the odds that both devices will fail the same week, or 1 in 10^6. The storage space required is twice that of the original data. Next consider the example of  FIG. 1 , where each of the 8 artifacts (the four un-encoded copies and the four encodings) is stored on a separate storage device at a respective service node. If any three storage devices are lost, as described above, all the data can be recovered. However, if four storage devices are lost, data may be lost. To avoid going into the details of which combinations of four lost storage devices will cause data loss, we will instead assume that all 70 combinations of losing four storage devices will cause us to lose data (there are 70 possible ways in which four devices can be chosen out of eight). This gives us a weekly failure rate of 70 in 10^12, for an overall failure rate for these four storage objects of once in 285 million years. 
     Thus, the technique illustrated in  FIG. 1  is able to support a very high durability level, appropriate for many types of mission-critical applications. As mentioned earlier, in different implementations, several of the simplifying assumptions illustrated in  FIG. 1  may not apply. For example, a given storage node may include both un-encoded copies and encodings, not all the members of a given durability group  150  may be the same size, and encoding algorithms more sophisticated than simple exclusive-or computations (such as various types of erasure coding schemes) may be used. 
       FIG. 2  illustrates an example of a provider network  202  comprising multiple data centers  210  (e.g.,  210 A and  210 B), in which a storage service node may store un-encoded copies and encodings of combinations of storage objects, according to at least some embodiments. As shown, data center  210 A comprises service nodes  222 A and  222 B, while data center  210 B comprises service nodes  222 K and  222 L. 
     A given service node  222  of a storage service may include a plurality of storage devices  220  in the embodiment shown in  FIG. 2 , and a given storage device may be used to store un-encoded copies (UECs)  250  as well as encodings  235 . For example, service node  222 A includes storage device  220 A with a set of UECs  250 A and encodings  235 A, and storage device  220 B with UECs  250 B and encodings  235 B. Similarly, service node  222 B comprises storage device  220 K with UECs  250 K and encodings  235 K, and storage device  220 L with UECs  250 L and encodings  235 L. Service node  222 K at data center  210 B includes service node  222 K with storage devices  220 M (containing UECs  250 M and encodings  235 M) and  220 N (with UECs  250 N and encodings  235 N), while service node  222 L includes storage devices  220 P (with UECs  250 P and encodings  235 P) as well as  220 Q (with UECs  250 Q and encodings  235 Q). Each storage device  220  may include UECs from diverse durability groups (not shown in  FIG. 2 ), e.g., durability groups with different numbers of storage objects as members, with respective durability requirements, and with respective encoding techniques being used. In some embodiments, the durability manager  180  may store the locations of the various artifacts produced in accordance with the encoding plans (e.g., UECs and encodings) in a durability group database  282 , as indicated by arrow  234 . Work request routers  182  responsible for directing incoming work requests to service nodes may be provided access to the durability group database  282  in some embodiments, as indicated by arrow  233 . Thus at least in some embodiments, the durability group database  282  may serve as part of a notification mechanism for work request routers  182  to obtain updated location information for various UECs and/or encodings. 
     In the depicted embodiment, each service node  222  may also include a respective local compute operations manager (LCOM)  224 , such as LCOMs  224 A at service node  222 A, LCOM  224 B at service node  222 B, LCOM  224 K at service node  222 K, and LCOM  224 L at service node  224 L. Each LCOM may include one or more hardware and/or software components that are responsible for receiving requests (e.g., client-initiated requests redirected by the work request routers) for different types of local operations to be performed on storage objects  120 , implementing the requested local operations, and returning the results of the local operations (e.g., to the work request routers and/or to the requesting clients). Libraries implementing a plurality of local operation types may be supported in different embodiments, such as various types of text-based search/match operations, statistical or scientific data analysis (e.g., signal processing operations of various types), and so on. The supported local operation types may be made known to clients  170 , e.g., via one or more programmatic interfaces such as web sites or application programming interfaces (APIs) implemented by the storage service in some embodiments. In at least one embodiment, the storage service may also provide information regarding the expected performance (e.g., response times, throughputs and the like) for various types of local operations, and the associated pricing policies for the operations, so that clients may be able to make informed decisions regarding the costs and benefits of utilizing such features of the storage service. 
     Durability Manager Components 
       FIG. 3  illustrates example constituent elements of a durability manager  180  of a storage service, according to at least some embodiments. As shown, the durability manager  180  may comprise a DG (durability group) membership manager  302  responsible for determining which specific storage objects should be made members of various durability groups  150  to achieve the desired durability levels. As described below in the context of  FIG. 4 , in some embodiments durability groups may be formed in response to incoming write requests. Some of the factors that may be taken into account by DG membership manager  302  when selecting DG members may include, for example, the temporal proximity of write requests to different storage objects, the sizes of the storage objects, ownership information (e.g., which particular client entity, such as a particular user or business with a client account set up with the provider network, owns a given storage object may help determine whether that storage object should be added to a particular DG), and the like. 
     In at least some embodiments in which a DG comprises N storage objects, a given encoding generated by the durability manager  180  may be derived from only a subset of the members of the DG (i.e., using a function or algorithm that takes less than N storage objects as inputs). In the simplified scenario shown in  FIG. 1 , for example, there are four storage objects  120  in DG  150 A, and each encoding  135  is derived from the contents of three storage objects. Depending on the encoding algorithm used, the durability manager may have to select which specific subsets of the members of a given DG should be combined for encoding purposes—e.g., given members A, B, C, D, and E of a DG and an encoding function that is to generate  5  encodings of three members at a time, which specific triplets of A, B, C, D and E should be used. An encoding combination selector  304  may be responsible for identifying the appropriate combinations of DG members in the depicted embodiment. 
     Encoding generator  306  may be configured to select and/or implement the computation algorithm(s) used to obtain the encodings in the depicted embodiment. Different algorithms may be used in different implementations, depending for example on the durability requirement for a given DG, the computation resources available for the encodings, the client&#39;s budget, and so on. In some embodiments, the particular algorithm used for a given storage object may also be dependent on factors such as an anticipated access rate and/or the rate at which requests for local computations are expected, a target or goal for object reconstruction time, and so on. 
     Node type selector  308  and placement manager  310  may collectively help determine the locations at which the artifacts (un-encoded copies and encodings) corresponding to various storage objects are to be stored. For example, depending on their relative compute performance capabilities and storage-related performance capabilities, in one embodiment the nodes of a storage service may be categorized into some number of capability levels, and the node type selector  308  may be configured to determine the categories of nodes at which one or more un-encoded copies or encodings of a given DG should be stored. Using the node type information determined by the node type selector  308 , and/or information about the locations of various nodes in the data center(s) of the provider network, the placement manager  310  may identify which specific service nodes should be used for a given DG&#39;s UECs and encodings. In at least some embodiments, the node type selector  308  and/or the placement manager  310  may utilize access history information for storage objects implemented using the storage service when deciding the types of nodes or the specific nodes to be used for a given DG. For example, an analysis of access history information associated with earlier-created storage objects that contain application X&#39;s data may help with placement decisions for a new storage object being created for application X or related application Y. If, for example, local computations tend to be performed very frequently on the existing storage objects of application X, node type selector  308  may place a greater weight on selecting appropriately-configured service nodes for the local computations on UECs than on the performance capabilities of the nodes at which the encodings are stored. 
     In the embodiment illustrated in  FIG. 3 , artifact reconstructor  312  may be responsible for performing the computations necessary to restore the un-encoded copies or versions of the storage object, as well as any encodings that need to be reconstructed, in the event of failures that render some number of the original artifacts inaccessible. Notification manager  315  may be responsible for generating notifications, e.g., to work request routers  182 , to ensure that client work requests are directed to the appropriate service nodes. In one embodiment, for example, various work request routers  182  may subscribe (e.g., as listeners) to notification mechanisms implemented by notification manager  315 , or view contents of notification message queues used by the notification manager. In some embodiments, notifications may be provided in the form of updates to a DG database  282 . Work request routers  182  may maintain caches of location information for DG contents (e.g., UECs and encodings) in some embodiments, and notification manager  315  may inform work request routers when the caches should be invalidated and/or updated in different embodiments. It is noted that in various embodiments, one or more of the constituent elements of durability manager  180  that are illustrated in  FIG. 3  may not be implemented, and/or other elements not shown in  FIG. 3  may be implemented. For example, in an embodiment in which all service nodes have identical capabilities, node type selector  308  may not be required. 
     Durability Group Membership 
     In at least some embodiments, a storage service may implement a write-once model, according to which each write request results in a new physical storage object being created to store the modification indicated in the request, and in-place updates are not supported. For example, a 4-megabyte storage object with an object identifier S1 may be created starting at location X on a physical storage device. When a write request directed to a location within the first 4 megabytes of S1 is received, a new copy of the first 4 megabytes of S1 may be created, e.g., starting at location Y on the same physical storage device or a different physical storage device, and the original copy may (either immediately or eventually) be marked as obsolete or deleted in some embodiments. In some storage services that support the write-once model, writes may be performed in discrete units or chunks—e.g., 1-megabyte chunks may be supported for some storage objects, 4-megabyte chunks may be supported for other storage objects, and so on, such that a write requested to a given chunk results in a new version of the chunk being written to physical storage. In at least some embodiments in which the write-once model of storage is implemented, each write request may thus represent the creation of a new storage object, and membership in durability groups may be determined for each of the storage objects resulting from incoming write requests. Thus, in such embodiments, the times at which durability group membership is decided may be governed at least in part by the times at which write requests are received. 
       FIG. 4  illustrates an example approach to combining storage objects into durability groups, according to at least some embodiments. A sequence of write requests are received at the storage service in the depicted embodiment, with elapsed time increasing from the left to the right. Write requests of two sizes are shown by way of example: 4-megabyte (4 MB) writes and 8-megabyte (8 MB) writes. Note that if a write-once model is used, and writes are permitted only in 4 MB chunks or 8 MB chunks, a modification to any amount of data smaller than 4 MB may result in a 4 MB chunk write, and a modification to data larger than 4 MB and smaller than 8 MB may result in an 8 MB write. The write requests shown in  FIG. 4  may not necessarily represent updates to pre-existing storage objects (e.g., they may each represent the creation of a respective new object), and may not necessarily represent requests directed to a write-once storage system, however. 
     In  FIG. 4 , 4 MB write requests are received at times T 1  (write  402 A), T 3  ( 402 C), T 5  ( 402 E), and T 6  ( 402 F). 8-MB write requests are received at times T 2  ( 402 B), T 4  ( 402 D), T 7  ( 402 G), T 8  ( 402 H), T 9  ( 402 J) and T 10  ( 402 K). Each write request  402 A- 402 K results in a new storage object being created. The durability manager  180  (e.g., using its DG membership manager component  302 ) combines the storage objects into DGs based at least in part on the write sizes, and at least in part on the timings of the write requests. In at least some implementations, the contents of the write requests (i.e., the modified data) may be held in volatile or main memory at one or more devices of the storage service while the DG is populated, and the maximum amount of time the service can take to populate a given DG may be constrained, for example, to avoid running low on memory. 
     Generally speaking, the following guidelines may be used for DG generation in the depicted embodiment: (a) storage objects resulting from write requests of the same size that are received close to each other in time (e.g., within a DG membership time window  470 , whose duration may be a function of memory size constraints as mentioned above) are combined into a DG; (b) to the extent possible, storage objects of different sizes are not combined into a given DG and (c) if two write requests of the same size occur at times further apart than the time window  470 , they are not combined into a DG despite their equal size, even if an adequate number of members have not been found for a DG with members of that size. The optimum number of members of a DG may typically be a function of the encoding algorithm that the durability manager  180  decides to use for the DG. However, in at least some embodiments such as that depicted in  FIG. 4 , if the optimum number of members cannot be identified within some time limit such as time window  470 , a DG with fewer members may be generated. 
     In accordance with these guidelines, a DG  450 K with four members corresponding to 4 MB writes  402 A,  402 C,  402 E and  402 F may be formed by DG membership manager  302  in the depicted embodiment. All four of these write requests arrive at times within time window  470  of each other. For 8 MB writes, the DG membership manager  302  may create a DG  450 L initially populated with the storage object corresponding to write  402 B received at time T 2 . The DG membership manager  302  may wait for additional 8 MB write requests that arrive within time window  470  with respect to T 2 . In the depicted example, 8 MB write requests  402 D (at time T 4 ) and  402 G (at time T 7 ) match this time window criterion, while the next 8 MB write request  402 H (time T 8 ) falls outside the time window. Accordingly, even though the optimum number of members of the DG  450 L may be four, only three storage objects corresponding to write requests  402 B,  402 D and  402 G may  450 L. A new DG  450 M may be established for 8 MB write request  402 H, as no other 8 MB write request is received within time window  470  either before or after T 8 . DG  450 N may be created for 8 MB requests  402 J and  402 K received at times T 9  and T 10  (which are close enough to fall within time window  470 ). 
     In various embodiments, different approaches may be taken to generating encodings for “incomplete” DGs (such as DG  450 M, which contains just one storage object although the optimum DG size is four). For example, the number of full un-encoded copies of the storage objects may be adjusted upwards for incomplete DGs in some implementations, or different combinations may be encoded than may have been encoded had the DG been fully populated in accordance with the selected encoding plan or algorithm. In some embodiments, incomplete DGs may not be supported—i.e., each DG may be required to include the optimum number of members as decided by the durability manager  180  or the DG membership manager  302 . 
     Mapping Durability Group Artifacts to Storage Locations 
       FIG. 5  illustrates an example approach to determining the placement of storage objects on storage service nodes, according to at least some embodiments. In the depicted embodiment, a given storage service node may be classified based on its compute and/or storage capabilities, as indicated by node profile database  550 . For example, a service node may be termed a “class A” node if its compute capability is X (as expressed in, for example, operations per second of a reference compute workload) and its storage capability is Y (as expressed in storage operations per second of a specified type, and/or based on the storage space available at storage devices of the node). Similarly, a node with compute capability X and storage capability 4Y may be termed a “class B” node, a node with compute capability 4X and storage capability Y may be termed a “class C” node, and a node with compute capability 8X and 2Y may be termed a “class D” node. Various other node classes may be defined in node profile database  550  in different embodiments; the node classes shown in  FIG. 5  are examples, and are not intended to limit the node classification schemes that may be used. 
     As shown, in the depicted embodiment, a given data center  515  may include nodes of one or more of the classes. For example, data center  515 A includes two sets of class A nodes,  510 A and  510 B, and two sets of class B nodes,  510 C and  510 D. data center  515 B includes class A nodes  514 A, class B nodes  515 A, class C nodes  516 A, and class D nodes  517 A. The node type selector  308  of durability manager  180  may utilize the node profile database  550 , as well as access history database  525 , to identify the types of nodes that should be used for each of the artifacts of a given DG  150 , as indicated by arrows  533  and  535 . For example, access history database  525  may provide a history of how often local computation operations were performed relative to the lifetimes of storage objects, which may be helpful in identifying the computation profiles of the nodes that should be used; or the access history database may indicate how often storage objects owned by a given client entity are typically read and what the typical read sizes are, which may be useful in identifying the storage characteristics of the nodes to be used. 
     Node type selector  308  may select the kinds of nodes to be used, and provide an indication of the selected node classes to placement manager  310  in the depicted embodiment, as indicated by arrow  537 . Placement manager  310  may in turn consult a node location database  520  (as indicated by arrow  534 ), which stores current information regarding the availability of specific classes of service nodes at various data centers  515 . In accordance with the durability requirements of the storage objects being considered for placement, the placement manager  310  may generate placement maps  560  that specify which storage nodes (and/or specific storage devices) are to store which artifacts (e.g., where un-encoded copies for a DG are to be stored, and where the encodings are to be stored). 
     Methods for Durability Management Using UECs and Encodings 
       FIG. 6  is a flow diagram illustrating aspects of operations that may be performed at a storage service to support high durability, according to at least some embodiments. As shown in element  601 , a durability manager  180  of a storage service may be configured to identify members of durability groups, i.e., storage objects of which combination encodings (i.e., encodings of several group members) are to be stored in addition to un-encoded copies, to achieve a desired durability level and/or to support local computations (such as text search, regular expression matching, substring matching, and the like) efficiently. In some embodiments, DG membership decisions may be triggered as a result of receiving write requests, as illustrated in  FIG. 4 . Storage objects may be included in a durability group based on various factors such as similar sizes, proximity in the timing of write requests to the storage objects, common ownership by the same client entity, logical relationships between the objects (e.g., objects belonging in the same directory of a namespace may be more likely to be included in the same durability group, in comparison to objects of different namespaces), and so on. 
     The encoding function, i.e., the computations to be performed or the algorithms to be executed on the storage objects to generate the encodings, may be determined (element  604 ). For example, in some implementations, variants of the exclusive-or computations described with reference to  FIG. 1  may be used, while in other embodiments, erasure encoding techniques and/or other algorithms may be utilized. The number of un-encoded copies (UECs) of the various members of a DG may be determined (element  607 ). In some implementations, the same number of UECs may be stored of each of the members of a DG, while in other embodiments, different members may have different numbers of UECs stored. It is noted that at least in some implementations, the number of UECs to be stored for at least some storage objects may be predetermined (e.g., based on default parameters), and may not need to be computed in real time. The specific combinations of DG members for which encodings are to be generated may then be determined (element  610 )—for example, for a DG with five members A, B, C, D and E, combinations (A,B,C,D), (A,B,D,E), (B,C,D,E) and (A,B,C,E) may be selected for encoding. It is noted that in some embodiments, the choice of combinations may result in an asymmetry with respect to recoverability of the artifacts—e.g., some artifacts may be reconstructed if at most K failures occur, while other artifacts may be reconstructed if L failures (where L&gt;K) occur. In some such embodiments, the choices of the combinations may be made based at least in part on such asymmetry—e.g., artifacts that are expected to benefit from relatively higher durability may be selected for the L-failure recoverability, while other artifacts may be selected for K-failure durability. 
     A placement map indicating the specific nodes at which each of the artifacts is to be stored may then be generated (element  613 ), e.g., using a process similar to that shown in  FIG. 5 . The operations corresponding to elements  604 ,  607 ,  610  and  613  may be collectively referred to as the generation of encoding plans for DGs. Various components of the encoding plan associated with a given DG may be determined based on some combination of criteria such as the following: (a) the sizes of the storage objects that are members of the DG, (b) an expected frequency of local computation operations directed at one or more of the DG members, (c) an expected frequency of access requests directed at one or more of the DG members, (d) expected lifetimes of the members (e.g., how long the storage objects are expected to remain accessible before being deleted), (e) a metric of an expected amount of computation required to reconstruct the various storage objects of the DG using one or more of the encodings, or (f) a metric of a computational capacity of a node of the storage service at which either an un-encoded copy of one or more of the members of the DG, or one or more encodings of the DG members are to be stored. The UECs and the encodings may then be stored in accordance with the placement map (element  616 ). Requests for supported types of local computations may subsequently be directed to the nodes that store selected UECs of the storage objects (element  619 ). 
     As described earlier in the context of  FIG. 4 , in at least some embodiments decisions regarding durability group membership may be made in response to write requests, and that the relative timings and sizes of write requests may be considered when determining whether a particular storage object is to be included in a durability group in such embodiments.  FIG. 7  is a flow diagram illustrating aspects of operations that may be performed to determine durability group membership, according to at least some embodiments. As shown in element  701 , a time window TW for DG membership inclusion may be determined, e.g., based on configuration settings or on heuristics. If up to N storage objects, each of size S (or a size close to S), are to be included in a DG, and N write requests of the appropriate sizes are received during a time window TW, the N storage objects corresponding to the write requests may be selected for inclusion in a DG. It is noted that at least in some embodiment, not all the members of a durability group need be equal in size. 
     The storage service (e.g., a DG membership manager component  302  of a durability manager  180  of the service) may monitor write requests as they occur (element  704 ), as well as the sizes of the target storage objects of the write requests. Based on an analysis of the timing and sizes of the writes, the storage objects that are written to during a given time window TW may be grouped by size (element  707 ) in the depicted embodiment. Depending on the total number of write requests of each size that are received in the time window TW, some number of DGs may be established, e.g., based on the durability requirements of the storage objects (element  710 ). For example, if the storage system supports two different levels of durability D1 and D2, durability groups for objects with durability level D1 may typically be set up (assuming enough write requests of a similar size are received within the time window TW) with N1 members, while durability groups for objects with durability level D2 may typically be set up with N2 members, where N1 differs from N2. If not enough write requests arrive during a given time window, a DG with fewer than optimal members may be created in at least some embodiments. After the write requests received during a given time window are aggregated into DGs, another time window may be started (e.g., corresponding to the arrival of a new write request). In some embodiments, time windows of different durations may be used for different durability levels. In other embodiments, time windows may not be used at all, and the storage service may simply wait until enough write requests are received for a DG to be created. In at least one embodiment, DG creation need not be tied to write request arrival times at all, and storage objects may be assigned to durability groups regardless of the times at which they are created or updated. 
       FIG. 8  is a flow diagram illustrating aspects of operations that may be performed to recover storage objects in the event of one or more failures, according to at least some embodiments. As shown in element  801 , a storage service component such as durability manager  180  may detect that some set of storage devices or nodes is not accessible, e.g., as a result of hardware and/or software failures. Artifact reconstructor  312  or another component may identify the set of storage objects that may have been affected, and may initiate a recovery operation for such identified storage objects. For each potentially affected storage objects, the reconstructor may determine the (potentially empty) set of un-encoded copies that remain accessible, and the (potentially empty) set of encodings associated with the object. In some embodiments, a loop of operations corresponding to elements  804  of  FIG. 8  onwards may be repeated for each potentially affected storage object. 
     As shown in element  804 , during a given iteration of the loop, the next storage object Sk among those potentially affected may be identified. If some of the encodings associated with Sk are found to be inaccessible or affected by the failure(s), but the source un-encoded copies (e.g., UECS of various members of Sk&#39;s DG) from which the encodings can be determined remain unaffected, as determined in element  813 , new encodings to replace the inaccessible ones may be generated (element  816 ). It is noted that in at least some embodiments, depending for example on the encoding algorithm being used and/or on the specific UECs that survive the failure(s), a different set of encodings may be generated in operations corresponding to element  816  than were present before the failure(s). 
     If some UECs of Sk are inaccessible, but at least one UEC of Sk remains accessible, as detected in element  819 , the required number of replacement UECs may be generated by copying from the accessible UEC(s) (element  822 ). If all the UECs of Sk are no longer accessible, but a combination of one or more encodings of Sk and UECs of other members of the durability group are accessible, from which an Sk UEC can be obtained (as detected in element  825 ), the encodings and UECs of the other DG members may be used to reconstruct the required number of Sk UECs (element  828 ). In some scenarios, it may not be feasible to reconstruct the Sk UECs from the surviving artifacts, in which case Sk UECs and/or encodings may be recovered from backups, if appropriate backups are available (element  835 ). After Sk recovery has been addressed, if other potentially affected storage objects remain (as detected in element  843 ), the next such storage object may be considered, and operations corresponding to elements  804  onwards may be repeated for that storage object. It is noted that even if Sk recovery is not successful, if other affected storage objects remain in the same DG and are subsequently recovered, then recovery for Sk may be retried at that time in at least some embodiments. Otherwise, recovery for the set of storage objects affected by the failure(s) may be deemed complete (element  846 ). 
     It is noted that in different embodiments, the operations illustrated in the flow diagrams of  FIGS. 6, 7 and 8  may be performed in a different order than shown, or in parallel instead of sequentially. In some embodiments, some of the illustrated operations may be omitted, and/or other operations may be performed. 
     Use Cases 
     The techniques described above, of implementing high-durability storage solutions using some numbers of un-encoded copies of storage objects together with encodings of selected combinations, may be useful in a variety of different scenarios. For example, in some storage environments, other approaches to high durability may typically involve partitioning objects followed by encoding the partitions, which may require a substantial overhead to decode and/or reconstruct the objects before certain types of operations (such as text searches and grep-like operations) can be implemented. The hybrid approach outlined herein may help reduce the overheads and accompanying delays that result from such fully-partitioned and fully-encoded approaches, while sacrificing relatively little in terms of storage space used to achieve desired durability levels. 
     Illustrative Computer System 
     In at least some embodiments, a server that implements a portion or all of one or more of the technologies described herein, including the techniques to implement durability managers, work request routers, or storage service nodes, may include a general-purpose computer system that includes or is configured to access one or more computer-accessible media.  FIG. 9  illustrates such a general-purpose computing device  3000 . In the illustrated embodiment, computing device  3000  includes one or more processors  3010  coupled to a system memory  3020  via an input/output (I/O) interface  3030 . Computing device  3000  further includes a network interface  3040  coupled to I/O interface  3030 . 
     In various embodiments, computing device  3000  may be a uniprocessor system including one processor  3010 , or a multiprocessor system including several processors  3010  (e.g., two, four, eight, or another suitable number). Processors  3010  may be any suitable processors capable of executing instructions. For example, in various embodiments, processors  3010  may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors  3010  may commonly, but not necessarily, implement the same ISA. 
     System memory  3020  may be configured to store instructions and data accessible by processor(s)  3010 . In various embodiments, system memory  3020  may be implemented using any suitable memory technology, such as static random access memory (SRAM), synchronous dynamic RAM (SDRAM), nonvolatile/Flash-type memory, or any other type of memory. In the illustrated embodiment, program instructions and data implementing one or more desired functions, such as those methods, techniques, and data described above, are shown stored within system memory  3020  as code  3025  and data  3026 . 
     In one embodiment, I/O interface  3030  may be configured to coordinate I/O traffic between processor  3010 , system memory  3020 , and any peripheral devices in the device, including network interface  3040  or other peripheral interfaces such as various types of persistent and/or volatile storage devices used to store physical replicas of data object partitions. In some embodiments, I/O interface  3030  may perform any necessary protocol, timing or other data transformations to convert data signals from one component (e.g., system memory  3020 ) into a format suitable for use by another component (e.g., processor  3010 ). In some embodiments, I/O interface  3030  may include support for devices attached through various types of peripheral buses, such as a variant of the Peripheral Component Interconnect (PCI) bus standard or the Universal Serial Bus (USB) standard, for example. In some embodiments, the function of I/O interface  3030  may be split into two or more separate components, such as a north bridge and a south bridge, for example. Also, in some embodiments some or all of the functionality of I/O interface  3030 , such as an interface to system memory  3020 , may be incorporated directly into processor  3010 . 
     Network interface  3040  may be configured to allow data to be exchanged between computing device  3000  and other devices  3060  attached to a network or networks  3050 , such as other computer systems or devices as illustrated in  FIG. 1  through  FIG. 8 , for example. In various embodiments, network interface  3040  may support communication via any suitable wired or wireless general data networks, such as types of Ethernet network, for example. Additionally, network interface  3040  may support communication via telecommunications/telephony networks such as analog voice networks or digital fiber communications networks, via storage area networks such as Fibre Channel SANs, or via any other suitable type of network and/or protocol. 
     In some embodiments, system memory  3020  may be one embodiment of a computer-accessible medium configured to store program instructions and data as described above for  FIG. 1  through  FIG. 8  for implementing embodiments of the corresponding methods and apparatus. However, in other embodiments, program instructions and/or data may be received, sent or stored upon different types of computer-accessible media. Generally speaking, a computer-accessible medium may include non-transitory storage media or memory media such as magnetic or optical media, e.g., disk or DVD/CD coupled to computing device  3000  via I/O interface  3030 . A non-transitory computer-accessible storage medium may also include any volatile or non-volatile media such as RAM (e.g. SDRAM, DDR SDRAM, RDRAM, SRAM, etc.), ROM, etc., that may be included in some embodiments of computing device  3000  as system memory  3020  or another type of memory. Further, a computer-accessible medium may include transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as a network and/or a wireless link, such as may be implemented via network interface  3040 . Portions or all of multiple computing devices such as that illustrated in  FIG. 9  may be used to implement the described functionality in various embodiments; for example, software components running on a variety of different devices and servers may collaborate to provide the functionality. In some embodiments, portions of the described functionality may be implemented using storage devices, network devices, or special-purpose computer systems, in addition to or instead of being implemented using general-purpose computer systems. The term “computing device”, as used herein, refers to at least all these types of devices, and is not limited to these types of devices. 
     CONCLUSION 
     Various embodiments may further include receiving, sending or storing instructions and/or data implemented in accordance with the foregoing description upon a computer-accessible medium. Generally speaking, a computer-accessible medium may include storage media or memory media such as magnetic or optical media, e.g., disk or DVD/CD-ROM, volatile or non-volatile media such as RAM (e.g. SDRAM, DDR, RDRAM, SRAM, etc.), ROM, etc., as well as transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as network and/or a wireless link. 
     The various methods as illustrated in the Figures and described herein represent exemplary embodiments of methods. The methods may be implemented in software, hardware, or a combination thereof. The order of method may be changed, and various elements may be added, reordered, combined, omitted, modified, etc. 
     Various modifications and changes may be made as would be obvious to a person skilled in the art having the benefit of this disclosure. It is intended to embrace all such modifications and changes and, accordingly, the above description to be regarded in an illustrative rather than a restrictive sense.