X hits on this document

PDF document

google-cluster-auctions.pdf - page 2 / 8





2 / 8

the world. These types of allocation problems have been studied extensively from a theoretical standpoint, but few practical applications have been introduced and evaluated. Those few appearing in the literature have been small-scale and limited to very specific application domains [6], [7]. As discussed in [8], much work remains to be done in making these “market-based” approaches both practical and scalable.

In this paper, we propose a novel, high-level approach to the pricing and allocation of resources in large-scale, “grid” sys- tems. In particular, users specify desired bundles of resources along with the maximum amount they are willing to pay (or, if selling, the minimum amount they are willing to receive). In addition, the system operator acts as a seller of resources and sets reserve prices based on the current utilization of each resource pool. The final winners and prices are then determined through a clock auction starting at the latter prices. By repeating this process on a regular time scale (e.g., weekly), one can thus develop a dynamic, efficient “economy” for computing resources within a distributed, heterogeneous environment.

Given this framework, we implemented a combinatorial exchange within Google and ran experiments in which this was used to allocate resources across the company’s engineering teams. Our preliminary results indicate that this approach of- fers several advantages over traditional allocation mechanisms:

  • 1)

    Allows market participants to make engineering design tradeoffs with the jobs they choose to run on their allocated resources. Teams that find resource A at a significant discount to resource B may bid on resource A and set about reengineering their job to use less of resource B and more of resource A.

  • 2)

    Long-term resource utilization can be taken into account when setting reserve prices for new resources brought into the marketplace. In this way bidding behavior can be encouraged that improves the overall bin-packing of system clusters. Specifically, in later sections we develop a utilization weighted reserve price calculation to encour- age uniform utilization levels across resource pools.

The remainder of this paper is organized as follows. We be- gin in the next section by discussing our mathematical model for resources and user preferences in a large-scale computing environment. Section 3 describes the clock auction mechanism used to set prices in our system. Section 4 addresses the utilization-based reserve pricing scheme described above. Our experimental results are discussed in Section 5. Finally, in Section 6, we conclude and give directions for future research.


Consider a large-scale computing system with R resource pools, indexed as r = 1, 2, . . . , R and U users, indexed as u = 1, 2, . . . U. The former represent aggregations of individual, physical resources which are divisible and shared across the users. Although the units of resources are the same for all resource pools, the pools in practice need not have exactly the same characteristics. Geographic location, location of other required resources or data, network connectivity, or

other secondary characteristics may (or may not) distinguish a particular pool for a particular user. In the experiments described later, these pools represented high-level, resource / location pairs (e.g., “CPUs in cluster 1”). The exact criteria used to distinguish these groups, however, is flexible and ultimately depends on the system being modeled. Similarly, the definition of a “user” is also flexible; in the case of our experiments, these were taken as distinct engineering teams within the company.

These users, given some initial endowment of money and resources, seek to buy, sell, and trade the latter in an individ- ually optimal way. The exact details of this optimization are application-dependent. In many “grid” settings, however, the underlying user preferences are highly combinatorial; that is, users get maximal utility from particular bundles of resources consisting of very specific resource combinations. CPUs in a particular place, for instance, are probably not useful unless the user can get colocated memory, disk, and network resources as well. At the same time, these preferences may also reveal strong substitutability among resource bundles. For example, a user may demand a certain combination of CPU, memory, and disk but may be indifferent with respect to the exact location.

These preferences are well-understood by the users but not necessarily by the system operator. As discussed in the introduction, therefore, we propose that prices and allocations be set through an auction. In particular, users announce bids encapsulating their desired bundles and “willingness to pay” criteria in a tree-based bidding language similar to TBBL described in [9]. More formally, we assume that each user u submits some bid, Bu, consisting of the pair {Qu, πu}. T h e fi r s t t e r m i s a s e t o f R - c o m p o n e n t v e c t o r s , q 1 u , q 2 u representing bundles of resources over which u is indifferent. , . . . I n o t h e r w o r d s , u d e s i r e s [ q 1 u X O R q 2 u X O R q 3 u . . ponents of each vector, in turn, encode either the quantities of each resource desired (if positive) or offered (if negative). The second bid term, πu, gives the total, maximum amount that u is willing to pay (if positive) or the minimum amount that u is willing to receive (if negative). We assume that this is a scalar value applying to all bundles in Qu. Extending the model to allow for vector π’s, corresponding to distinct valuations for each individual user bundle, does not significantly change our results and is omitted for notational simplicity. . ] . T h e c o m -

We also assume that all bids are entered simultaneously, i.e. users cannot modify their bids based on the actions of others or provisional feedback from the system. In practice, participants are typically given some window of time in which to enter bids and, possibly, respond to environmental conditions. In this case, our analysis here still holds if we instead consider the bids to be the final values as of the end of the entry period. Modeling the dynamics of this initial phase is a very interesting problem, but one that is outside the scope of our investigation here.

Document info
Document views14
Page views14
Page last viewedSun Oct 23 08:10:09 UTC 2016