X hits on this document

PDF document

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





8 / 8

Another change in bidder behavior we have observed is an increasing sophistication towards arbitrage opportunities. As the market price differential between resources increases there have been greater opportunities for teams to profit from one auction to the next. This behavior has led to the design of a more robust internal budgeting and provisioning process inside Google to encourage sharing, mobility, and thrift by internal teams, and to discourage hoarding and overestimating. Future research will study these behavioral issues in more detail.


In this paper, we have thus proposed a framework for allocating and pricing resources in a grid-like environment. This framework employs a market economy with prices ad- justed in periodic clock auctions. We have implemented a pilot allocation system within Google based on these ideas. Our preliminary experiments have resulted in significant im- provements in overall utilization; users were induced to make their services more mobile, to make disk/memory/network tradeoffs as appropriate in different clusters, and to fully utilize each resource dimension, among other desirable outcomes. In addition, these auctions have resulted in clear price signals, information that the company and its engineering teams can take advantage of for more efficient future provisioning.

Future research will expand on several dimensions of our work here. On the theoretical side, we intend to more deeply explore existence, convergence, efficiency, and other properties of our clock pricing algorithm. We are also studying some alternative algorithms which explicitly optimize an operator- specified function. On the implementation side, we will expand our market-based allocation system while refining our reserve pricing strategies and overall user experience. These experi- ments will allow us to better understand user behavior and also to more fully evaluate the utility of employing “market economies” for these heterogeneous, large-scale computing environments.


Many others have made contributions to Google’s evolving market economy. We would like to first acknowledge the work of Srikanth Rajagopalan in the design and implementation of the market inside Google as described in the experimental results section. We would also like to thank Hal Varian and Cos Nicolaou for early design input about building a market economy for internal allocation of computing resources. Our experimental results would not have been possible without the help of many internal teams which helped us integrate our experimental system into the existing tools that engineers use for provisioning, budgeting, and reserving resources inside Google. Finally, we are grateful to the early participants in our resource market, who offered useful practical feedback about the platform. We would particularly like to acknowledge

the help of Girish Baliga, Andrew Barkett, Dan Birken, Hal Burch, Geoffrey Gowan, Vlad Grama, Alex (Sang) Le, Andrew McLaughlin, and Adam Rogoyski.


[1] R. Buyya, J. Giddy, and H. Stockinger, “Economic models for resource management and scheduling,” Concurrency and Computation: Practice and Experience, vol. 14, no. 13-15, pp. 1507–1542, Nov. 2002. [2] C. Ernemann, V. Hamscher, and R. Yahyapour, “Economic scheduling in grid computing,” in JSSPP ’02: Revised Papers from the 8th Interna- tional Workshop on Job Scheduling Strategies for Parallel Processing, Jul. 2002, pp. 128–152. [3] R. Wolski, J. S. Plank, T. Bryan, and J. Brevik, “G-commerce: Market formulations controlling resource allocation on the computational grid,” in IPDPS ’01: Proceedings of the 15th International Parallel and Distributed Processing Symposium, Apr. 2001. [4] K. Lai, B. Huberman, and L. Fine, “Tycoon: a distributed market-based resource allocation system,” HP Labs, Tech. Rep., Feb. 2008. [5] C. Waldspurger, T. Hogg, B. Huberman, J. Kephart, and W. Stornetta, “Spawn: a distributed computational economy,” IEEE Transactions on Software Engineering, vol. 18, no. 2, pp. 103–117, Feb. 1992. [6] O. Regev and N. Nisan, “The popcorn market: online markets for computational resources,” Decision Support Systems, vol. 28, no. 1-2, pp. 177–189, Mar. 2000. [7] M. P. Wellman, J. K. MacKie-Mason, D. M. Reeves, and S. Swami- nathan, “Exploring bidding strategies for market-based scheduling,” in EC ’03: Proceedings of the 4th ACM Conference on Electronic Commerce, Jun. 2003, pp. 115–124. [8] A. AuYoung, B. N. Chun, C. Ng, D. Parkes, A. Vahdat, and A. C. Snoeren, “Practical market-based resource allocation,” University of California, San Diego, Tech. Rep., Aug. 2007. [9] D. C. Parkes, R. Cavallo, N. Elprin, A. Juda, S. Lahaie, B. Lubin, L. Michael, J. Shneidman, and H. Sultan, “Ice: an iterative combinatorial exchange,” in EC ’05: Proceedings of the 6th ACM Conference on Electronic Commerce, Jun. 2005, pp. 249–258. [10] P. Cramton, Y. Shoham, and R. Steinberg, Eds., Combinatorial Auctions. MIT Press, 2006. [11] L. Ausubel and P. Cramton, “Auctioning many divisible goods,” Journal of the European Economic Association, vol. 2, no. 2-3, pp. 480–493, Apr. 2004. [12] L. Ausubel, P. Cramton, and P. Milgrom, “The clock-proxy auction: a practical combinatorial auction design,” in Combinatorial Auctions,

P. Cramton, Y. Shoham, and R. Steinberg, Eds. ch. 5.

MIT Press, 2004,

[13] C. Kenyon and G. Cheliotis, “Grid resource commercialization: eco- nomic engineering and delivery scenarios,” in Grid Resource Manage- ment: State of the Art and Future Trends, J. Nabrzyski, J. Schopf, and

J. Weglarz, Eds. pp. 465–478.

Norwell, MA: Kluwer Academic Publishers, 2004,

[14] J. Smith, E. Chong, A. Maciejewski, and H. Siegel, “Decentralized market-based resource allocation in a heterogeneous computing sys- tem,” in IPDPS ’08: IEEE International Symposium on Parallel and Distributed Processing, Apr. 2008, pp. 1–12. [15] M. Stonebraker, R. Devine, M. Kornacker, W. Litwin, A. Pfeffer, A. Sah, and C. Staelin, “An economic paradigm for query processing and data migration in mariposa,” in PDIS ’94: Proceedings of the Third International Conference on Parallel and Distributed Information Systems, Sep. 1994, pp. 58–68. [16] S. Ghemawat, H. Gobioff, and S.-T. Leung, “The google file system,” in SOSP ’03: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, Oct. 2003, pp. 29–43. [17] F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Bur- rows, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: a distributed storage system for structured data,” in OSDI ’06: Proceedings of the 7th Symposium on Operating Systems Design and Implementation, Nov. 2006, pp. 205–218.

Document info
Document views27
Page views27
Page last viewedThu Jan 19 17:13:45 UTC 2017