Massively Scalable Object Storage for Storing Object Replicas

A method for locating objects on hosts in an online service with particular availability guarantees, the method comprising:

• consulting by a director a multi-level ring structure including at least two levels, wherein a first level of the ring structure corresponds to hard constraints on the placement of objects, and a second level of the ring structure corresponds to soft constraints on the placement of objects, wherein the sum of the constraints controls the location of objects within the online service, wherein the satisfaction of at least one hard constraint is satisfied by identifying at least one diverse storage pool, and wherein at least one soft constraint is satisfied by identifying at least one durable storage location;
• wherein each diverse storage pool includes a set of non-co-located storage elements, wherein no storage element of a diverse storage pool overlaps with any other storage element in any other diverse storage pool, the diverse storage pools communicably coupled with each other, and with the director, the set number of diverse storage pools being at least equal to a given replication number greater than one;
• wherein each diverse storage pool includes a plurality of partitions, mapped onto the storage element of the diverse storage pool, each partition being associated with a distinct durable storage location managed by at least one local processor operably connected to a local communications port,
• receiving from the director a selected set of distinct partitions, the cardinality of the set at least equal to the given replication number, wherein each distinct durable storage location is compliant with at least one hard constraint and one soft constraint, the contents of the selected set being deterministic relative to a selection key;
• and effecting a change in an object located at a distinct durable storage location in the selected set by interacting with the local processor associated with the selected location;
• the effected change selected from a set of operations including reading, writing, creating, deleting, and executing.

A method for ensuring the availability of data, the method comprising:

• partitioning, by a director, a plurality of storage pools into a set of diverse storage pools, the cardinality of the set of diverse storage pools being equal to a given replication number greater than one;
• each storage pool including a plurality of storage elements, each with a local processor and a local communications port, and a plurality of partitions, each partition being associated with a distinct durable storage location managed by the least one local processor, the plurality of partitions being mapped onto the plurality of storage elements, and the storage elements within a storage pool being communicably coupled with each other and with the director, each diverse storage pool including a set of non-co-located storage elements, wherein no storage element of a first diverse storage pool overlaps with any other storage element in any other diverse storage pool;
• creating a multi-level ring structure including at least two levels, wherein a first level of the ring maps a selection key to an ordered set of partitions, and a second level of the ring structure corresponding to a set of constraints on the partitions available for storage of an object, wherein the sum of the constraints controls the location of objects within the online service, wherein the satisfaction of at least one constraint is satisfied by identifying partitions mapped to storage elements within a number of diverse storage pools at least equal to the replication number, and wherein the mapping of the selection key to the corresponding ordered set of partitions being deterministic relative to the selection key;
• replicating a provided object to a number of partitions within the corresponding ordered set of partitions mapped by the selection key, the number of partitions being at least equal to the replication number.

A system for distributed evaluation, the system comprising:

• a director, the director comprising an inbound communications port, an outbound communications port, a local storage, a director processor, and a set of executable instructions stored on a non-transitory medium;
• a plurality of storage pools;
• each storage pool including a plurality of storage elements, each with a local processor and a local communications port, and a plurality of partitions, each partition being associated with a distinct durable storage location managed by the least one local processor, the plurality of partitions being mapped onto the plurality of storage elements, and the storage elements within a storage pool being communicably coupled with each other and with the director, each diverse storage pool including a set of non-co-located storage elements;
• a multi-level ring structure mapping a selection key to an ordered set of partitions, the ring operably connected to the director, the ring including at least two levels, wherein a first level of the ring maps a selection key to an ordered set of partitions, and a second level of the ring structure corresponding to a set of constraints on the partitions, wherein the mapping of the selection key to the corresponding ordered set of partitions being deterministic relative to the selection key;
• the executable instructions associated with the director being operable to:
• receive a request identifying a selection key and a set of arguments;
• retrieve the set of matching partitions based upon the selection key;
• and communicate at least a subset of the request to the storage element associated with each identified matching partition;
• wherein the local processor evaluates a set of instructions and data located within the identified matching partition and returns a computed response.