A performance Brokerage for Heterogeneous Clouds

6.5 Performance Tranches and Pricing

In this section we define the broker’s performance offerings and pricing. For each of the 31 benchmarks offered, the broker periodically takes a cross section of measurements of available instances, that is, one for each instance the broker has rented³⁵ that is available for rent. Over a period of time the union of these cross-sections gives a ‘global’ past performance history, which for workload w_m we denote by global_perf^(m):

global_perf^(m) := { perf^(inst,m)(t): all inst ϵ I, t > 0 and perf^(inst,m)(t) is defined}6.7
The broker divides global_perf^(m) into 4 sub-ranges corresponding to the 25^th percentile, the 50^th percentile, the 75^th percentile and the 100^th percentile respectively. We refer to these as tranche A, B, C and D. Note that as global_perf^(m) is updated tranche points are subject to change. When a user orders instances they do so by specifying the number of instances required, the workload and the tranche, with the latter defining the minimum required level. For example, if a user requests tranche C then they require instances with a minimum performance better (lower is better) than the 75^th percentile of global_perf^(m).
How should we price instances? We first determine a base level of performance for each benchmark, base_perf_m , which we use as a reference point for all instances. Each instance has a price that the broker is paying (some seller) at the CeX. Instances with performance above base_perf_m (lower is better) will be re-priced above the CeX price whilst those with performance less than base_perf_m will be re-priced below the CeX price. We re-price by determining the speed up relative to base_perf_m . When re-pricing an instance we first calculate its mean performance from current time t_i to the time t_j the instance was obtained and first measured. The mean of this sample, _m,

is an unbiased estimator of constant_m and calculating its speed up relative to base_perf_m, that is:

speed_up_m := base_perf_m / _m. 6.8
The price of the instance is then drawn from U[price_cex(inst), speed_up_m*price_cex(inst)]. That is:
price(inst) ~ U[price_cex(inst), speed_up_m* price_cex(inst)]. 6.9
Note that the broker is acting like a Gode and Sunder (1993) ZI-C trader, as discussed in section 4.4. We recall in this model that a trader randomly generates a price between some specified values and these are generated independently from one trade to the next. Whilst Cliff’s (1997) ZIP traders employ a learning rule so that prices are generated according to a strategy, this requires visibility of pricing, as found for example on exchanges operating central limit order books. However, in our case, the broker is quoting a price for a client in a private trade, as typical of OTC markets. As such ZIP models are not suitable.
How should we determine base_perf_m? In financial markets, risk, or volatility, is often measured by the number of standard deviations from the mean – typically of a normal distribution. On a normal distribution, one standard deviation below the mean corresponds to the 84th percentile. However, as we typically have a multi-modal distribution, and the mean is not necessarily representative, so we choose to set base_perf_m to be the performance value corresponding to the 75th percentile of global_perf^(m). As base_perf_m coincides with tranche C, any instances below this, i.e. tranche D, would be charged at less than the CeX price, leaving the broker open to potentially indefinite losses. As such, we choose to only sell tranches A, B and C. Note that as global_perf^(m) is updated the pricing is subject to change; this means that pricing is automatically updated to reflect available performance.
Whilst we have chosen to price an instance relative to a performance gain, there are of course numerous other ways to price. Indeed, clients such as FinRisk may be prepared to pay higher prices simply due to the value that performance assurance offers them. In a value-add approach the broker may simply choose to price each tranche at some percentage above the market price, for example, tranche A is 20% above market, tranche B is 10% and C is 5%. In practice, different prices will draw forth different levels of demand and that will be decided by the market.
Pricing must provide an incentive to use the broker, and potential clients will likely take into account their expected cost of obtaining instances in a particular tranche, and when this is amortised over an expected duration it allows for a comparison with the broker price. In the next section we describe the construction of a population of clients, and the value of the broker’s proposition for them.

6.6 The Broker’s Clients

In this section we describe the construction of a population of clients who submit orders to the broker. A client submits an order by specifying (num_instances, workload, tranche). Can we find a suitable proxy for use as performance demand data? That is, can we find suitable data from which we can construct a population of users who submit requests of the form above? This is a vital consideration as it ensures validity of data assumptions regarding this aspect of the model.

Wolski and Brevik (2014) discuss the usage of Eucalyptus, a private infrastructure Cloud platform, at 3 different organisations. Notably, each organisation is using Eucalyptus in a production setting with the second organisation charging other business units for usage. From each of the 3 anonymised data sets it is possible to deduce: (1) inter-arrival times for requests (2) numbers of instances (3) instance size and (4) instance lifetime. However, there is no data we can use a performance proxy. Further, the largest cluster consists of only 13 nodes with 24 cores per node, whilst the other 2 have 7 nodes each with 12 and 8 cores per node respectively. Such small clusters cannot support elasticity for multiple workloads concurrently, and so the trace data is perhaps unlikely to be representative of public Cloud workloads. Further, as each Cluster serves one organisation only, each data set is specific to that organisation’s workloads.
Facebook³⁶ and Yahoo³⁷ have both released Hadoop based workload traces. However, our broker is focused on providing for a range of workload specific needs, rather than one specific type of workload and so we consider these traces as unrepresentative and so unsuitable for our needs. For similar reasons we also consider HPC workload traces, such as the San Diego Supercomputer Centre trace (SDSC, 2000), to be unsuitable.
6.6.1 2011 Google Workload Trace
In 2011 Google released a workload trace covering a 29 day period during which 925 distinct users submitted ~650,000 jobs requesting more than 25,000,000 tasks to be run onto a production cell of ~12,500 hosts (Reiss and Wilkes, 2011). Analysis of the trace typically focuses on resource utilisation (Reiss et al., 2012; Liu and Cho, 2012; Verma et al., 2015), but we are motivated by its potential suitability for use as proxy for performance demand. We discuss this trace in more detail below.
Google’s internal Cloud is structured into cells containing heterogeneous physical machines referred to as hosts. Each cell runs a heterogeneous mix of workloads, from public facing services such as Gmail to batch jobs. To run a workload a user submits a job specifying one or more identical tasks (same binary) to be run, resource requirements (CPU, RAM and Disk) and possibly some constraints. The workload scheduler, codenamed Borg, is responsible for scheduling tasks to hosts and general resource and job management. Different tasks from different jobs can run concurrently on the same hosts within a cell. By mixing different workloads from different services and internal groups, rather than provisioning per service/group cells, Google can benefit from uncorrelated demand in the same way that Public Clouds do.
Verma et al. (2015) describe workloads as being of 2 types: long running services and batch workloads. The former typically handle short-lived latency sensitive requests, such as web-search, or vital infrastructure services such as monitoring. Jobs specify a priority level which is used to ensure it can obtain resources when needed. A priority is expressed as an integer in the range 0 to 11 with 11 being the highest priority and 0 the lowest.
Further, Borg defines a set of non-overlapping priority bands, which Reiss et al. (2012) categorise as: Infrastructure (priority 11), Monitoring (priority 10), Production (priority 9), Batch (priority 8-2) and Free (priority 1-0). Resource requirements of higher priority jobs can be met by ‘throttling’ resources of lower priority jobs, and indeed may see low priority jobs terminated, known as eviction, before completion. These jobs may be restarted elsewhere in the cluster if there is capacity available; however, jobs within the Infrastructure, Monitoring or Production bands cannot evict each other.
Resource control is managed through the use of containers, which are standard Linux processes that have been restricted in some manner, and each task runs within its own container. Containers on the same host share the underlying kernel, but have their own name-spaces for process ids, networking and inter-process communication (IPC). The use of containers is often referred to as Operating Systems virtualisation or lightweight virtualisation, with the latter being a reference to the fact that they can be created/booted much faster than a traditional VM. However, this comes at the expense of the security and isolation provided by a hypervisor. Through the use of control groups (cgroups), resources such as CPU allocation can be dynamically assigned to containers.
In some regards the Borg system is similar to the on-demand/spot market operated by EC2: in the latter, lower value spot instances may be terminated, and the resources reclaimed for higher value on-demand instances; in the former the scheduler can evict low priority jobs for higher priority ones. However, unlike Public on-demand Clouds, in order to submit a job to Borg a user must have sufficient quota available which needs to be purchased in advance. Further, resource quotas are purchased at particular priority bands with higher priority quota costing more than the same quantity of lower priority quota. Finally, quotas are time limited and are typically purchased in monthly units. Purchasing in advance eases the capacity planning problem for Google, and we find obvious analogies with the use of reserved instances by EC2 as well as the WZH truth-telling reservation based system.
6.6.2 Suitability of Google Workload Trace
Is the trace suitable as a proxy for our broker? The scale of the data set and the mixture of workloads (from production level services to free test and development) mean it is more likely to be representative of the type of workloads we would expect to see on the Cloud. Indeed, as batch jobs lasting anywhere from a few minutes to days are prevalent in the trace we would consider that this range of lease durations would capture lease usage of FinRisk, which runs batch simulations overnight, ready for next day trading
Further, priority can be considered as a performance requirement – higher priority jobs have a more urgent need of resource access than lower priority ones in order to perform some useful work. Indeed, the trace is an example of performance pricing as it costs more to run a job with a higher priority than a lower one. Further, each job specifies a number of tasks and each task is run in its own container. As we have noted, containers are often referred to as OS virtualisation, and so we use number of tasks/containers in a job as a proxy for number of instances required.
6.6.3 Constructing a Population of Clients
For each of the 925 users in the trace we construct a corresponding client for the broker as follows. For each job in the trace we construct a corresponding order by mapping: (num_of_containers, priority) -> (num_instances, tranche).
Following Reiss et al. (2012) who categorise priority to band as: Infrastructure (priority 11), Monitoring (priority 10), Production (priority 9), Batch (priority 8-2) and Free (priority 1-0), we implement the following priority band to tranche mapping as follows:

Infrastructure, Monitoring and Production -> Tranche A [9-11]

Batch -> Tranche B [2-8]

Free -> Tranche C [0,1]
Finally, for each job in the trace we can determine its overall time spent in the ‘system’. That is, from the time it was submitted until the time it was successfully completed, evicted or failed. We use total job time as a proxy for instance lease times i.e. the duration that clients lease instances from the broker. However, the trace contains a significant number of jobs that are short running and we choose to filter out all jobs shorter than min_charge. This ensures that the broker does not profit by charging a client for longer than they have rented the instance for, although we note AWS benefited from rounding usage up to the nearest hour on EC2.
Jobs which run the full length of the trace are also filtered as we cannot determine their exact length. Further, some jobs request large numbers of containers; indeed, we have some jobs which start in excess of 50,000. The broker limits order size to 20 instances, chosen due it being the default limit on EC2 for concurrent running instances of standard types. After filtering jobs for these conditions and with min_charge = 10, for example, we are left with ~ 120,000 orders of which 12% are tranche A, 51% for tranche B and 37% for tranche C. The average number of instances requested per order is 2.4 with a median lease period of 25 minutes. Note that this is not known to the broker a priori.
Although we have constructed a population of clients with performance needs, we do not know how price sensitive they are. Clearly, for a given performance level we would expect there to be a limit price i.e. a particular price beyond which they would likely not buy. How can we determine a plausible limit price? Clients can obtain instances from the CeX, through other brokers, and implement an instance seeking strategy. We recall the effective price when instance seeking is the provider/market price plus the expected performance overhead, amortised over an instance’s duration.
A client can estimate both duration and seeking costs, allowing them to compare expected effective cost with the price the broker is offering. If the former is above the latter then the client should accept the broker price. However, even if that is not the case then some risk-averse users will still prefer a fixed price to expected ones. In our simulations we assume 25% of the population is risk-averse and we note that the proportion of the population that is risk-averse is typically considered quite high (Halek and Eisenhauer, 2001). Indeed, the propensity for people to take out insurance, which is a loss making game i.e. the premium paid is higher than they expected pay-out, demonstrates that risk-aversion is commonplace. Arguably, clients such as FinRisk are likely to fall into the risk-averse category, as there are potentially severe financial implications for them should they be unable to find performance in time.
Clients can estimate both duration and seeking costs as follows: The former can be estimated from the performance level and a known quantity of work. Indeed, estimating duration of instance use is one of the reasons why the broker is useful. When estimating the latter, the client can use tranche definitions to obtain an estimate of the probability that an instance will be in a particular tranche. For example, as tranche A is defined as the top 25% of the performance history, p = 0.25 is an estimate of the probability of obtaining an instance in tranche A. For the purposes of comparing prices the client assumes performance of instances in future requests is independent of the performance of past instances on the CeX. This allows the client to estimate the effective cost.
When the performance independence assumption is not valid, our result in section 4.2 suggest that the expected cost is the same but variation increases. As such, on a CeX where the independence assumption is not valid we would likely see more risk-averse users and indeed our 25% assumption may be on the low side.
In a given period of time, how much demand per workload per tranche would we expect? This is a vital consideration for on-demand services which must rent instances in advance from the CeX for re-sale. We consider this issue in the next section.