Consistency-based service-level agreements in cloud storage environments

An application programming interface is provided that allows applications to assign multiple service-level agreements to their data transactions. The service-level agreements include latency bounds and consistency guarantees. The applications may assign utility values to each of the service-level agreements. A monitor component monitors the various replica nodes in a cloud storage system for latency and consistency, and when a transaction is received from an application, the monitor determines which of the replica nodes can likely fulfill the transaction in satisfaction of any of the service-level agreements. Where multiple service-level agreements can be satisfied, the replica node that can fulfill the transaction according to the service-level agreement with the greatest utility is selected. The application may be charged for the transaction based on the utility of the service-level agreement that was satisfied.

BACKGROUND

Cloud storage services, such as the popular class of “NoSQL” data stores, have been designed to meet the needs of diverse applications from social networking to electronic commerce. Such storage services replicate application data on multiple machines to make it highly available and to improve performance. Many provide a relaxed form of consistency, eventual consistency, in order to achieve elastic scalability and good performance while some strive for strong consistency to maintain the semantics of one-copy serializability. To allow local access and ensure data survivability even during a complete data center failure, many storage systems offer the option of replicating data across different regions of the world, called “geo-replication.”

With data being replicated on a world-wide scale, the inherent tradeoffs between performance and consistency are exaggerated due to the high communication latencies between data centers. The performance difference between reads with different consistencies can be substantial. Strongly consistent reads generally involve multiple replicas or are serviced by a primary site whereas eventually consistent reads can be answered by the closest replica. Even within a data center, the latency of strongly consistent reads has been measured as eight times that of reads with weaker session guarantees. With geo-replication, the performance differences can be more than two orders of magnitude.

SUMMARY

An application programming interface is provided that allows applications to assign multiple service-level agreements to their transactions that read and write data in a replicated cloud storage service. The service-level agreements include latency bounds and consistency guarantees. The applications may further assign utility values to each of the service-level agreements according to their desirability. A monitor component monitors the various replica nodes in a cloud storage service for latency and consistency, and when a transaction is received from an application, the monitor determines which of the replica nodes can likely fulfill the transaction in satisfaction of any of the service-level agreements. Where multiple service-level agreements can be satisfied, the replica node that can fulfill the transaction according to the service-level agreement with the greatest expected utility is selected. The application may be charged for the transaction based on the utility of the service-level agreement that was satisfied.

In an implementation, a service-level agreement is selected by a computing device. A transaction request is generated by the computing device. The generated transaction request and the selected service-level agreement are provided by the computing device. A result associated with the transaction request and an indication that the service-level agreement was complied with are received by the computing device.

In an implementation, a transaction request is received at a computing device. The transaction request includes a plurality of service-level agreements. Information about a plurality of nodes is received at the computing device. Based on the service-level agreements and the information about the nodes, whether the transaction request can be fulfilled in accordance with any of the service-level agreements at one of the nodes is determined by the computing device. If it is determined that the transaction request can be fulfilled in accordance with any of the service-level agreements at one of the nodes, the transaction request is fulfilled according to one or more of the service-level agreements at the node, and an indication that the transaction was fulfilled according to one or more of the service-level agreements at the node is provided by the computing device.

DETAILED DESCRIPTION

FIG. 1is an illustration of an example environment100for enabling service-level agreements in a cloud storage service. The environment100may include a client device110and a cloud storage service150in communication with one another through a network120. The network120may be a variety of network types including the public switched telephone network (PSTN), a cellular telephone network, and a packet switched network (e.g., the Internet).

In some implementations, a client device110may include a desktop personal computer, workstation, laptop, PDA, smart phone, cell phone, or any WAP-enabled device or any other computing device capable of interfacing directly or indirectly with the network120. A client device110may be implemented using a general purpose computing device such as the computing system500illustrated inFIG. 5, for example. While only one client device110is shown, it is for illustrative purposes only; there is no limit to the number of client devices110that may be supported.

The cloud storage service150may provide distributed data storage and data processing services to the client device110. The cloud storage service150may be implemented using a variety of cloud computing systems such as WINDOWS AZURE by MICROSOFT. Other cloud services may be used.

The cloud storage service150may include a plurality of computing nodes180(i.e., nodes180a-n). The nodes180may provide computation and data storage services to the client devices110. In particular, the nodes180may store one or more data objects for the client devices110, as well as retrieve data values from stored data objects for the client devices110. Each of the nodes180may be implemented using one or more general purpose computing devices such as the computing system500. While only four nodes180are shown, it is for illustrative purposes only; there is no minimum or maximum number of nodes180that may be supported.

The cloud storage service150may provide computation and data services to one or more applications115executing on the client devices110. Examples of the applications115that may use the cloud storage service150may include online shopping applications, e-mail applications, social networking applications, and gaming applications. Other types of applications115may be supported.

In some implementations, the cloud storage service150may receive and fulfill one or more transaction requests117from the applications115of the client devices110. The transaction requests117may include put requests and get requests. A put request may be a request to store a data value at a data object, and a get request may be a request to retrieve a stored data value from a data object. A get request may include a key118that uniquely identifies the data object that stores the requested data value in the cloud storage service150. The data value may be read from the identified data object. The data object may be stored at one or more of the nodes180in the cloud storage service150. A series of transaction requests117may be grouped together into what is referred to herein as a session.

A put request may have a data value and a key118that identifies the data object that the data value may be written to. The data value may be written to the identified data object at one or more of the nodes180. Where the put request is a request to store a new data value, a data object may be created on one or more of the nodes180and the data value may be stored at the new data object. In addition, a key118may be assigned to the data object and provided to the application115and/or client device110.

In some implementations, the nodes180may be separated into what are referred to as primary nodes and secondary nodes. Each primary node may be associated with a subset of the data objects maintained by the cloud storage service150. Put requests for data objects that are associated with the primary node are routed to the primary node and fulfilled by the primary node. The primary nodes may periodically push the updates that were made to the data objects to one or more of the secondary nodes. Each secondary node may similarly be associated with a subset of the data objects maintained by the cloud storage service150. The secondary nodes may push updates received from the primary nodes to other secondary nodes. Get transactions fulfilled from a primary node may be guaranteed to include the most recently updated data values, while get transactions fulfilled from a secondary node may not have the most recently updated data value.

As may be appreciated, each node180may be located in a different geographic location, and therefore may have a different latency with respect to the client device110. For example, a node180that is located in the same city as the client device110may be able to more quickly fulfill a get transaction request117than a node180that is located in a different city than the client device110. Further, because of how the nodes replicate data and the various geographic locations associated with each node180, the node with the most current data value (i.e., most consistent) for a data object may not be the node with the lowest overall latency.

Different applications115may have different requirements or needs with respect to latency and consistency of data values. For example, a video game application may value low latency for data value transactions higher than consistency to reduce lag. Similarly, a banking application may value consistency over low latency.

Accordingly, to help the cloud storage service150and/or the application115select the most appropriate node180to handle a transaction request117, the client device110may further include a service-level agreement engine116. The service-level agreement engine116may allow an application115to specify one or more service-level agreements119for each transaction request117(or session) using an application programming interface. The service-level agreements119may specify one or more performance guarantees and/or consistency guarantees.

More specifically, a service-level agreement119may specify a latency bound and a consistency guarantee. The latency bound may be a minimum acceptable latency (e.g. 100 ms, 200 ms, 300 ms, etc.), and the consistency guarantee may be a minimum acceptable consistency (e.g., most recent data value, no older than 200 ms, no older than 500 ms, etc.).

The service-level agreement engine116may determine which, if any, of the nodes180can fulfill a transaction request117according to the associated service-level agreement119associated with the transaction request117using the key118and information about each of the nodes180. The information about each node180may include information about the round-trip communication latency of each node180with respect to the client device110, and information about the consistency of the data values stored or maintained by each node180(e.g., the latest update times or version numbers of the data objects maintained by the node180).

If the transaction request117can be fulfilled according to the service-level agreement119, then the service-level agreement engine116may fulfill the transaction request117. Otherwise, the service-level agreement engine116may return an error or indication that the service-level agreement engine116cannot fulfill the transaction request117using the specified service-level agreement119.

The latency bound of the service-level agreement119may specify the latency for the transaction request117in milliseconds. In an implementation, the consistency guarantee of the service-level agreement119may take one of the following values: strong; eventual; read-my-writes; monotonic; and bounded. Strong may be the highest consistency guarantee and may be fulfilled using the most recent update for a data object. Eventual is less than strong and may be fulfilled with any updated data value for the data object. Read-my-writes may be fulfilled using the most recently updated value for the data object in a current session, or any data value if the data object was not updated in the current session. Monotonic is fulfilled using a same or later data value from a previous get transaction request117for the current session, or any data value if no get transactions requests117have been fulfilled for the current session. Bounded may include a specified time value t, and may be fulfilled using a data value that was updated no more than t second ago.

In some implementations, an application115may specify multiple service-level agreements for a transaction request117or session. Where multiple service-level agreements119are specified, the service-level agreements may be ranked or ordered according to the desirability of the service-level agreements119. The service-level agreements119may be ranked by the application115. For example, a first service-level agreement may be the service-level agreement that the application115would most like honored, a second service-level agreement may be a less acceptable service-level agreement that may be used if the service-level agreement engine116finds that the first service-level agreement cannot, or in not likely to be, honored. Some applications115may specify a “catch-all” or unrestricted service-level agreement119that allows for all latency and consistency guarantees to prevent a transaction request117from failing on account of the service-level agreement engine116being unable to honor any of the higher ranked service-level agreements119.

In some implementations, rather than rank the service-level agreements119, the application115may associate a utility with each of the service-level agreements119. The service-level agreement engine116may then attempt to fulfill the transaction request117according to the service-level agreement119with the greatest utility.

The utility may further be used to bill or charge applications115for the fulfilled transaction requests117. When a transaction request117is fulfilled for a client device110, the application115may be charged an amount of money or fee that is proportional to, or based on, the utility of the service-level agreement119that was met by the cloud storage service150. Such arrangements may allow applications115to pay for the levels of latency and consistency that are desired, encourage application designers to consider whether high latency and/or low consistency service-level agreements119would be suitable for their applications115, as well as encourage cloud storage services150to fulfill transaction requests117according to the service-level agreements119with the greatest utility.

FIG. 2is an illustration of an example service-level agreement engine116and an example node180. As illustrated, the service-level agreement engine116includes a monitor230, latency data240, and consistency data250. The node180includes a replication agent210, a commit coordinator220, and a table270. More or fewer components may be supported by the service-level agreement engine116and/or the node180.

The commit coordinator220of the node180may assign timestamps to committed (i.e., fulfilled) transaction requests117. In particular, the commit coordinator220may assign a timestamp to each committed put transaction request117. In some implementations, the commit coordinator220may be part of primary nodes and not secondary nodes. The commit coordinator220may further validate transactions117before they are committed or written to a data object. Where there are multiple primary nodes, the commit coordinator220may ensure that all committed transaction requests117are immediately replicated to the other primary nodes.

The replication agent210may control the propagation of data values and data objects between the nodes180. In particular, the replication agent210may ensure that the data object updates associated with the put transaction requests117that are made by the primary nodes are eventually also applied by each of the secondary nodes. The updates may be applied by each secondary node in order of the timestamps associated with each transaction request117. Any system, method, or technique known in the art for the replication of data between nodes180may be used. One example of a replication technique that may be used is a gossip protocol.

The replication agent210may store data objects in the table270. The table270may be implemented using a variety of data structures and may include the keys118corresponding to each data object and the most recent data value associated with the data object. Each data object may also have an associated timestamp which is the timestamp associated with the most recent transaction request117that the node180is aware of for that data object (i.e., the timestamp assigned by the commit coordinator220).

In some implementations, the replication agent210may maintain previous versions of one or more data objects. Each version may be associated with a different timestamp. The highest timestamp that the replication agent210is aware of is known as the high timestamp for the node180.

The replication agent210may periodically prune or delete older versions of data objects from the table270. The date of the last pruning performed by the replication agent210is known as the low time stamp for the node180. Any system, method, or technique for pruning data objects from a table270may be used.

With respect to nodes180that are primary nodes, the replication agent210may periodically transmit null transactions along with a current time to one or more of the other nodes180if a transaction request117has not been committed by the commit coordinator220for a period of time. The replication agents210at the receiving nodes180may then update their high timestamp to the current time associated with the null transaction. As described further below, by updating the high timestamps of the nodes180the service-level agreement engine116may learn which nodes180include up-to-date data values in their tables270.

The monitor230of the service-level agreement engine116may collect information from each of the nodes180, and may store the collected information as the latency data240and the consistency data250. The collected information about the nodes180may be used by the service-level agreement engine116to determine if a transaction request117can be fulfilled according to the one or more service-level agreements119at one or more of the nodes180.

In some implementations, the monitor230may determine the information by periodically contacting each of the nodes180. For example, the monitor230may periodically ping each node180. Alternatively, each of the nodes180may periodically provide the information to the monitor230. The information may be used by the monitor230to determine the latency data240and the consistency data250. In some implementations, the information may also include the ranges of keys118that correspond to the data objects that are stored in the tables270of each node180.

With respect to the consistency data250, the information provided by the node180may include the high timestamp of the node180and the low time stamp of the node180as determined by the replication agent210. The high and low timestamps may be stored as the consistency data250. The window of time defined by the high and low timestamps may be used by the service-level agreement engine116to determine the consistency of the data objects in the table270of the particular node180.

With respect to the latency data240, the information provided by the node180may include a measured latency between the client device110and the node180. For example, the node180may periodically measure the latency between it and the client device110. Alternatively or additionally, the monitor230may determine the latency between the client device110and the node180by requesting the consistency data250from the node180, and based on the amount of time that elapses before the requested data is received (i.e., round trip time), may determine the latency between the client device110and the node180. Because the observed latency may be skewed by a variety of factors including temporary network congestion or high processing loads of the nodes180, in some implementations, the latency data240for a node180may be an average latency of some number of previously observed latencies.

The service-level agreement engine116may use the latency data240and the consistency data250to determine which if any of the nodes180can fulfill a transaction request117according to a service-level agreement119. As described above, a service-level agreement119may include a latency bound and a consistency guarantee. With respect to the latency bound, the service-level agreement engine116may determine if a node180can fulfill a transaction request117within the latency bound based on the latency data240. The service-level agreement engine116may determine that the node180can fulfill the transaction request117within the latency bound of the service-level agreement119based on the latency data240if the latency bound is greater than the latency data240for the node180.

In some implementations, the service-level agreement engine116may determine a probability that the node180can fulfill a transaction request117(or all transaction requests117associated with a session) within the latency bound based on the latency data240. For example, as described above, the latency data240may have multiple observed latencies for the nodes180over a period of time. The service-level agreement engine116may then determine the probability by comparing the latency bound with each of the observed latencies. In some implementations, the probability calculation may be weighted to favor more recent observed latencies.

With respect to the consistency guarantee, the service-level agreement engine116may determine if node180can fulfill a transaction request117(or all transaction requests117associated with a session) according to the consistency guarantee based on the consistency data250. How the service-level agreement engine116determines if the consistency guarantee can be met may depend on the consistency guarantee selected by the application115.

In some implementations, for purposes of determining if a consistency guarantee is met, the service-level agreement engine116may determine one or more acceptable read timestamps for the transaction request117. The read timestamps for a transaction request117may be determined based on the consistency guarantee selected for the transaction request117, the data objects that were read and written in any previous transaction requests associated with a current session, and the key(s)118associated with the transaction request117. The service-level agreement engine116may determine the probability that the node180can fulfill the transaction request according to the selected consistency guarantee based on the acceptable read timestamps and the range of timestamps between the high and low timestamps associated with the node180.

For the strong consistency guarantee to be met, the read timestamp must be at least as large as the commit timestamps of put operations using any of the keys118associated with get operations in the transaction request117. This guarantees that each get operation accesses the latest version of the data object that existed at the start of the transaction associated with the request117. Thus, the low-end of the acceptable timestamp range is the maximum timestamp of all versions stored at primary nodes180for the keys118associated with the transaction request117.

For read-my-writes consistency guarantees, a session state of the client device110may record a commit timestamp of any previous transactions in a session that performed put operations. The low-end of the read timestamp range may be the maximum timestamp of any previously committed put operations associated with keys118being accessed in the current transaction.

For monotonic reads consistency guarantees, the session state of the client device110may record the timestamps and keys118of all data objects with values returned by previous get operations. The read timestamp may be at least as large as the maximum recorded timestamp for any keys118accessed in the transaction.

For bounded staleness consistency guarantees, the smallest acceptable read timestamp may be the current time minus the desired time bound. Client devices110and nodes180may have approximately synchronized clocks.

For eventual consistency guarantees, any read timestamp may be acceptable. However, reading from time zero, while technically not a violation of the consistency guarantee, may be ineffective for applications115. Choosing the current time may not be acceptable since it has the same effect as choosing strong consistency with the same limitations on performance and availability.

For any consistency guarantee (except strong), there may be a trade-off in selecting a read timestamp from the acceptable range: choosing more recent times produces more recent data, which applications115desire, but choosing older times results in a broader set of nodes180that can potentially meet the consistency guarantee, thereby increasing the likelihood of meeting a given service-level agreement119. Any method or technique for choosing a read timestamp may be used.

Computing the acceptable timestamp range for many of the consistency guarantees may include the service-level agreement engine116determining, at the start of the transaction, the set of get operations that are associated with the current session or transaction request117. In some cases, determining the set of keys118being accessed may be impractical, such as when the key118for a get operation depends on user input or data retrieved in some prior get operation within the same transaction. For such transactions, the service-level agreement engine116may obtain a conservative time range by assuming that every data object will be read (i.e., a get operation). For strong consistency gets operations, for example, the service-level agreement engine116may obtain the timestamp of the latest commit from every primary node180.

The service-level agreement engine116may determine if a service-level agreement119for a transaction request117can be met by a node180if both of the latency bound and the consistency guarantee can be met by the node180. Alternatively, the service-level agreement engine116may determine a probability that a service-level agreement119for a transaction request117can be met by a node180by multiplying the determined probability that the latency bound can be met by the node180with the determined probability that the consistency guarantee can be met by the node180.

Where multiple service-level agreements119for a transaction request117may be met by one or more nodes180, the service-level agreement engine116may select which service-level agreement119and node180to use to fulfill the transaction request117. In some implementations, the service-level agreement engine116may select the service-level agreement119with the greatest utility or that has the greatest associated rank. Where multiple nodes180meet the selected service-level agreement119, the service-level agreement engine116may select the node180with the lowest overall associated latency. Alternatively or additionally, the service-level agreement engine116may randomly select the node180, or may select the node180using a load balancing algorithm. Other methods for selecting a node180may be used.

In implementations where each service-level agreement119is associated with a utility value, the service-level agreement engine116may select a node180to fulfill a transaction request117using an expected value function. The service-level agreement engine116may then select the node180that can fulfill the transaction request117with the highest expected value.

For example, the service-level agreement engine116may, for each node180, calculate the expected value for each service-level agreement119for the node180by multiplying the probability that the node180can fulfill the service-level agreement119by the utility associated the service-level agreement119. The node180that can fulfill a service-level agreement119for the transaction request117with the highest calculated expected value may be selected by the service-level agreement engine116.

After selecting the node180to fulfill the transaction request117, the service-level agreement engine116may provide the transaction request to the selected node180. The node180may then fulfill the request117, and the node180may send an indication or confirmation that the transaction117was fulfilled to the service-level agreement engine116. Where the transaction request117is a get transaction request117, the confirmation may include the data value that was read from the data object corresponding to the key118.

In some implementations, the confirmation may include information that the service-level agreement engine116can use to determine which of the service-level agreements119were met by the fulfillment of the transaction request117. For example, the information may include the actual timestamp of the data object used in the transaction request117, and or the actual observed latency associated with the fulfillment of the transaction request117. As may be appreciated, because the latency data240and/or the consistency data250of the monitor230may not be up to date, the actual service-level agreement119that is fulfilled by the node180may be different than the service-level agreement119that the service-level agreement engine116predicted would be fulfilled by the node180. Accordingly, the service-level agreement engine116may determine which of the service-level agreements119were actually fulfilled for the transaction request117.

The service-level agreement engine119may confirm to the application115that the transaction request117was fulfilled and may include any data value(s) or key(s) generated as a result of the transaction request117. The confirmation may include the service-level agreement119that was determined to have been fulfilled. The service-level agreement engine119may further charge or bill the application115based on the utility of the service-level agreement119that was fulfilled.

FIG. 3is an operational flow of an implementation of a method300for providing a transaction request and a plurality of service-level agreements to a cloud storage service. The method300may be implemented by the application115of a client device110, for example.

A plurality of service-level agreements is input at301. The plurality of service-level agreements119may be provided by the application115of the client device110. In some implementations, each service-level agreement119may have a latency bound and a consistency guarantee. In addition, each service-level agreement119may have an associated utility value. A user or operator associated with the application115may select or input the plurality of service-level agreements119using an application programming interface, for example.

A transaction request is generated at303. The transaction request117may be generated by the application115of the client device110. The transaction request117may be one or more put or get requests. A put request may be a request to write a data value to a data object, and a get request may be a request to read a data value from a data object. Other transaction requests may be supported. The transaction request117may include one or more keys118that identify the data objects being accessed.

The generated transaction request and the plurality of service-level agreements are provided at305. The generated transaction request117and the plurality of service-level agreements119may be provided by the application115to the service-level agreement engine116. The engine116may then select one of a plurality of nodes180of the cloud storage service150to fulfill the request according to one of the service-level agreements119.

A result associated with the transaction request is received at307. The result may be received by the application115from the service-level agreement engine116. For put transaction requests117, the result may be a confirmation that the data value was stored for the data object. For get transaction requests117, the result may include a data value that was retrieved from the data object. The result may further have an indicator of which service-level agreement119of the plurality of service-level agreements119were complied with by the cloud storage service150. A service-level agreement is complied with if the transaction request117was fulfilled in according with both the latency bound and the consistency guarantee of the service-level agreement.

FIG. 4is an operational flow of an implementation of a method400for fulfilling a transaction request117in accordance with a plurality of service-level agreements119. The method400may be implemented by the service-level agreement engine116and/or the cloud storage service150, for example.

A transaction request is received at401. The transaction request117may be received by the service-level agreement engine116from the application115of the client device110. The transaction request117may be associated with a plurality of service-level agreements119, and each service-level agreement may include a latency bound and a consistency guarantee. In addition, each service-level agreement may have an associated utility.

Information about a plurality of nodes is received at403. The information about the plurality of nodes180may be received by the monitor230of the service-level agreement engine116. The information may include timestamps (i.e., a high timestamp and a low timestamp) from each of the nodes180. The timestamps may be used by the monitor230to determine consistency data250regarding each of the plurality of nodes180. The information may further include latency information such as a roundtrip time between the client device110and each of the plurality of nodes180. The latency information may be used by the monitor230to determine latency data240regarding each of the plurality of nodes180.

Whether the transaction request can be fulfilled in accordance with any of the plurality of service-level agreements at one of the plurality of nodes is determined at405. The determination may be made by the service-level agreement engine116using the latency data240and the consistency data250. In some implementations, the service-level agreement engine116may make the determination by, for each node180and service-level agreement119, determining if the average latency for the node is less than the latency bound in the service-level agreement119and the timestamps associated with the node180are in accordance with the consistency level of the service-level agreement119. For example, if the consistency level is strong, then the timestamps may be in accordance with the consistency level if the high time stamp for the node180is equal to the highest timestamp known by the service-level agreement engine116.

If the transaction request can be fulfilled in accordance with any of the service-level agreements, then the method400may continue at407. Otherwise, the method may continue at415where an indication is provided that the transaction cannot be fulfilled.

A node of the plurality of node is selected to fulfill the transaction request at407. The node180may be selected by the service-level agreement engine116. Where multiple nodes180are able to satisfy one or more of the service-level agreements119, the service-level agreement engine116may select a node180to fulfill the transaction. In some implementations, the engine116may select the node180that can fulfill the transaction117according to the service-level agreement with the highest utility.

In other implementations, the service-level agreement engine116, for each node180and service-level agreement119, may determine a probability that the node180can fulfill the transaction117according to the service-level agreement119. The service-level agreement engine116may then determine an expected utility for the node180and service-level agreement119by multiplying the determined probability by the utility associated with the service-level agreement119. The node associated with the greatest determined expected utility may be selected.

For example, in some implementations, at the start of a transaction117, for each service-level agreement119and each node118storing a key118that is accessed in the transaction117, the service-level agreement engine116may compute the expected utility that would accrue from performing the get operations at that node118. This expected utility may be the product of the probability that the node118can fulfill the get operations according to the service-level agreement119and the utility associated with the service-level agreement119. The service-level agreement engine116may record the best node180for each key118/service-level agreement119pair; if multiple nodes180offer the same expected utility, the service-level agreement engine116may choose one at random to balance the load or pick the one that is most up-to-date or closest. The service-level agreement engine116may then compute the total expected utility for each service-level agreement119by summing over the best nodes180for all keys118. The service-level agreement engine116may then choose the service-level agreement119and node180with the highest expected utility.

The transaction request is fulfilled at the selected node at409. The transaction request117may be fulfilled by the selected node180of the cloud storage service150. The transaction request117may be fulfilled by either storing or retrieving a data value in the table270associated with the selected node180.

The service-level agreement that was complied with is determined at411. The service-level agreement119may be determined by the service-level agreement engine116. The service-level agreement119may be determined by determining the actual consistency guarantee that was met by the node180and the actual latency associated with performing the transaction. The service-level agreement engine116may then determine the service-level agreement119with highest rank or utility that was achieved based on the actual consistency and latency bounds of the completed transaction.

An indication that the transaction request was fulfilled in accordance with the determined service-level agreement is provided at413. The indication may be provided to the application115by the service-level agreement engine116. The indication may also include any data values retrieved by the selected node180from the transaction request117.

With reference toFIG. 5, an exemplary system for implementing aspects described herein includes a computing device, such as computing system500. In its most basic configuration, computing system500typically includes at least one processing unit502and memory504. Depending on the exact configuration and type of computing device, memory504may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated inFIG. 5by dashed line506.

Computing system500may have additional features/functionality. For example, computing system500may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated inFIG. 5by removable storage508and non-removable storage510.

Computing system500typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computing system500and includes both volatile and non-volatile media, removable and non-removable media.

Computing system500may contain communication connection(s)512that allow the device to communicate with other devices. Computing system500may also have input device(s)514such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s)516such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.