Towards Energy-Proportional Datacenters

Posted by Dennis Abts, Michael R. Marty, Philip M. Wells, Peter Klausler, and Hong Liu

This is part of the series highlighting some notable publications by Googlers.

At Google, we operate large datacenters containing clusters of servers, networking switches, and more. While this gear costs a lot of money, an increasingly important cost -- both in terms of dollars and environmental impact -- is the electricity that drives the computing clusters and the cooling infrastructure. Since our clusters often do not run at full utilization, Google recently put forth a call to industry and researchers to develop energy proportional computer systems. With such systems, the power consumed by our clusters would be directly proportional to utilization. Servers consume the most electricity, and therefore researchers have responded to Google’s call by focusing their attention towards servers. As the servers become increasingly energy proportional, however, the “always on” network fabric that connects servers together will consume an increasing fraction of datacenter power unless it too becomes energy proportional.

In a paper recently published at the International Symposium on Computer Architecture (ISCA), we push further towards the goal of energy-proportional computing by focusing on the energy usage of high-bandwidth, highly-scalable cluster networking fabrics. This research considers a broad set of architectural and technological solutions to optimize energy usage without sacrificing performance. First, we show how the Flattened Butterfly network topology uses less power since it uses less switching chips and fewer links than a comparable-performance network built using the more conventional Fat Tree topology. Second, our approach takes advantage of the observation that when network demand is low, we can reduce the speed at which links transmit data. We show via simulation, that by tuning the speeds of the links very rapidly, we can reduce power consumption with little impact on performance. Finally, our research is a further call to action for the academic and industry research communities to make energy efficiency, and energy proportionality in particular, a first-class citizen in networking research. Put together, our proposed techniques can reduce energy cost for typical Google workloads seen in our production datacenters by millions of dollars!

Read More

Google North American Faculty Summit - Day 2

Posted by Andrew Tomkins, Director of Engineering, Google Research

Friday at the Google Faculty Summit, we discussed ideas around online social capabilities. Chris Messina opened the discussion with a talk about open initiatives for the social web. Damon Horowitz, founder of Aardvark, gave a talk about the Aardvark experience. But in this post, I’d like to talk about a panel I moderated on the future of the social web. The panel consisted of four experts in the area. Joseph Smarr came to Google after eight years as CTO of social networking site Plaxo. Lada Adamic is on the faculty at University of Michigan, where she studies the nature of social and information networks. Eytan Adar is also on the faculty at the University of Michigan, where he studies the evolution of production and consumption of data over time. Luis von Ahn is on the faculty of Carnegie Melon University and also an employee at Google; he studies mechanisms to connect significant human efforts to interesting problems.

One theme that received a lot of attention from panelists and audience members alike was the benefits and pitfalls of social personalization. In the context of an activity stream, there seems to be general agreement that passing lightweight updates among friends is a valuable tool for “social grooming,” or keeping light contact with friends as a way of maintaining the state of the friendship. For information discovery, however, the topic received more debate: real-world social networks have always been used to both push and pull information, but in conjunction with high-quality search, it's reasonable to ask which types of information needs can be best addressed by your friends. Social network connections typically display homophily (similarity) in the dimensions of geography and interests, so your friends are more likely to have something interesting to say about your local area and your longstanding hobbies or interests, along with other subjects. If so, the answer you receive has two added bonuses. First, your background knowledge about your friend will aid you in assessing the quality of the answer. And second, an answer from a friend satisfies not just an information need but also a human need to interact and share experiences. This socially augmented information can arrive through a push channel in which your friend already posted (for example) a review for a restaurant, or through a pull channel in which you send to your friends a request for information. The same mechanisms for social information sharing may also operate powerfully in the context of a group coming together around a shared interest or goal, rather than just in the context of an individual. Consider for example a group of students working together to understand some new material. The same two mechanisms apply: knowledge about the other students helps you evaluate their contributions, and the interactions in the group have value beyond the pure information transmitted.

There was considerable discussion about social networks' capacity to funnel information to a user through the lens of a particular viewpoint or ideology. Imagine an individual who arrives on the web as a supporter or detractor of a particular political figure or mindset, and then surrounds him or herself with like-minded people online, enjoying positive and supportive discussions but failing to encounter a diverse set of views and counter-opinions. Literature in the social sciences, beginning with the famous Asch conformity experiments from the 1950s, details the mechanisms that cause people to conform to group expectations and even abandon normal personality traits based on the norms of the new situation. And work by Nobel Prize-winning economist Thomas Schelling shows that very small and "reasonable" biases we might have towards avoiding becoming an extreme minority might lead a system to evolve into a highly balkanized state. Similar models have been proposed and evaluated in the Internet domain, and some preliminary measurements have been performed. While faculty members in the audience surmised that personalization could lead to more extremism, the group agreed there is no conclusive evidence.

Another topic we touched on is mechanism design: the problem of designing systems so that agents in the system, each acting selfishly, will together produce some desired outcome. Consider a social networking game. If the desired outcome is revenue for the game manufacturer, then the actions that increase status in the game (using real-world currency to purchase items in the game; inviting friends to join and participate in the game; clicking on advertisements in the game) are designed well to support this goal. Rewarding the action of bringing new friends into the game is one obvious approach to increasing the total user population. More subtly, any game system must provide sufficient fun to be worth the expense to users. The dramatic success of casual online games of this form (6 percent of U.S. pageviews come from these games, according to a study by Ravi Kumar and myself in the WWW 2010 conference) is a testimony to the presence of successful mechanisms of this form.

Finally, here is a small sampling of other issues that arose in the panel as controversial points or interesting areas for future research:

1. Social networks draw massive amounts of user time. We are beginning to get some limited visibility into exactly how this attention is allocated, which raises the research question of how much utility users are actually deriving from this investment of time, either in information, entertainment, social grooming or other intangibles.
2. In certain online communities, we see behavioral norms that are skewed towards public visibility of essentially all activity. Do these norms reflect the desires of the populations that choose to join the community, or do they emerge specifically because of the technical tools offered by the website that hosts the community?
3. Social networks are increasingly offering richer tools to users in an attempt to capture nuances of interactions that exist in the real world. In the fullness of time, how close will we get, and when will this happen?
4. Social networks formalize the status of a friendship, with significant breakpoints at initiation, acceptance and removal of a binary tie. The visibility of these events leads to both "overfriending" and offense when friendships are refused or removed. Are there improved mechanisms to produce and manage the relationships in online social networks, and if so, what are these mechanisms?
5. Social network graphs are notoriously difficult to partition into large regions with few edges between them (the sole exception being parts of a network that interact using different languages). A series of computational challenges arise when attempting to shard these networks for distributed analysis or serving from multiple computers.

One thing is clear from the discussion on Friday: social networks are increasingly becoming a valuable area for academic study. Faculty from widely disparate areas of computer science have thought deeply about the issues and implications of these tools; active research is ongoing in essentially all top institutions; and social network dynamics are appearing in the undergraduate curriculum. On top of that, they are an interdisciplinary phenomenon, involving not only many aspects of CS (UX, mechanism design, intense system requirements, security and privacy) but also psychology, economics and ethics, to name a few. There is much to study in order to understand these networks and maximize their societal value.

Read More

Google North American Faculty Summit - cloud computing

Posted by Brian Bershad, Director of Engineering, Site Director, Google Seattle

Of the three themes of our 2010 Faculty Summit, cloud computing was the one that pervaded all others, from security in the cloud to the presumption of cloud infrastructure behind the social web. But in our more focused discussion on cloud computing last Thursday, we started with the premise of “prodigiousness,” a concept introduced by Afred Spector, VP of Research and Special Initiatives.

While we all know that systems are huge and will get even huger, the implications of this size on programmability, manageability, power, etc. is hard to comprehend. Alfred noted that the Internet is predicted to be carrying a zetta-byte (10²¹ bytes) per year in just a few years. And growth in the number of processing elements per chip may give rise to warehouse computers of having 10¹⁰ or more processing elements. To use systems at this scale, we need new solutions for storage and computation. It was these solutions we focused on throughout our discussions.

In the plenary talk, Andrew Fikes spoke on storage system opportunities. Among many topics, he talked about shifting engineering foci to storage management and optimization not just on an individual cluster of co-located systems, but across geographically distributed clusters. The goal is so-called planetary-scale systems. This brings up all manner of diverse challenges ranging from the need to continually balance storage vs. transmission costs, the need to account for variable network latency characteristics, and the desire to optimize storage (e.g., by physically storing only one copy of a file that many feel they have rights to, or own).

We had a few roundtables in the afternoon for deeper discussions. In the table I led, we discussed two systems for “programming the data center” developed by systems researchers at Google Seattle/Kirkland. The first, Dremel, is a scalable, interactive ad-hoc query system for analysis of read-only nested databases. Dremel was recently presented in a paper at VLDB (Dremel: Interactive Analysis of Web-Scale Datasets, Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis. In Proceedings of the 36th Int'l Conf on Very Large Data Bases, 2010). The system serves as the foundational technology behind BigQuery, a product launched in limited preview mode at Google I/O in May.

We also discussed FlumeJava, a Java library that makes it easy to develop, test and run efficient data-parallel pipelines at data center scale. FlumeJava was developed by programming languages researchers at Google Seattle, and is currently in widespread use within Google. It was presented at the recent PLDI conference (FlumeJava: easy, efficient data-parallel pipelines, Craig Chambers, Ashish Raniwala, Frances Perry, Stephen Adams, Robert R. Henry, Robert Bradshaw, Nathan Weizenbaum. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation). The work reflects Google’s commitment to programming language and compiler technologies at scale.

The field of data center programming has progressed substantially in the last 10 years. Dremel and FlumeJava systems represent abstractions of a higher level than the MapReduce construct we previously introduced, and we think they are easier to use (within their domain of applicability) and more automatically optimizable. With time, the field will discover new “instructions” and even better abstractions leading us to a point where computations which run on nearly unlimited processors can be expressed as easily as sequential programs. We are working hard to make progress here, and I look forward to reporting on our progress in the future.

Read More

Google Publications

Posted by Corinna Cortes and Alfred Spector, Google Research

We often get asked if Google scientists and engineers publish technical papers, and the answer is, “Most certainly, yes.” Indeed, we have a formidable research capability, and we encourage publications as well as other forms of technical dissemination--including our contributions to open source and standards and the introduction of new APIs and tools, which have proven to sometimes be foundational.

Needless to say, with our great commitment to technical excellence in computer science and related disciplines, we find it natural and rewarding to contribute to the scientific community and to ongoing technical debates. And we know that it is important for Google to help create the fundamental building blocks upon which continuing advances can occur.

To be specific, Googlers publish hundreds of technical papers that appear in journals, books, and conference and workshop proceedings every year. These deal with specific applications and engineering questions, algorithmic and data structure problems, and important theoretical problems in computer science, mathematics, and other areas, that can guide our algorithmic choices. While the publications are interesting in their own right, they also offer a glance at some of the key problems we face when dealing with very large data sets and demonstrate other questions that arise in our engineering design at Google.

We’d like to highlight a few of the more noteworthy papers from the first trimester of this year. The papers reflect the breadth and depth of the problems on which we work. We find that virtually all aspects of computer science, from systems and programming languages, to algorithms and theory, to security, data mining, and machine learning are relevant to our research landscape. A more complete list of our publications can be found here.

In the coming weeks we will be offering a more in-depth look at these publications, but here are some summaries:

Speech Recognition

"Google Search by Voice: A Case Study," by Johan Schalkwyk, Doug Beeferman, Francoise Beaufays, Bill Byrne, Ciprian Chelba, Mike Cohen, Maryam Garrett, Brian Strope, to appear in Advances in Speech Recognition: Mobile Environments, Call Centers, and Clinics, Amy Neustein (Ed.), Springer-Verlag 2010.

Google Search by Voice is a result of many years of investment in speech at Google. In our book chapter, “Google Search by Voice: A Case Study,” we describe the basic technology, the supporting technologies, and the user interface design behind Google Search by Voice. We describe how we built it and what lessons we have learned. Google search by voice is growing rapidly and being built in many languages. Along the way we constantly encounter new research problems providing the perfect atmosphere for doing research on real world problems.

Computer Architecture & Networks & Distributed Systems

"Energy-proportional Datacenter Networks," by Dennis Abts, Mike Marty, Philip Wells, Peter Klausler, Hong Liu, International Symposium on Computer Architecture, ISCA, June 2010.

Google researchers have called on industry and academia to develop energy-proportional computing systems, where the energy consumed is directly proportional to the utilization of the system. In this work, we focus on the energy usage of high-bandwidth, highly scalable cluster networks. Through a combination of an energy-efficient topology and dynamic fine-grained control of link speeds, our proposed techniques show the potential to significantly reduce both electricity and environmental costs.

Economics & Market Algorithms

"Quasi-Proportional Mechanisms: Prior-free Revenue Maximization," by Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav, Latin American Theoretical Informatics Symposium, LATIN, April 2010.

Say a seller wishes to sell an item, but the buyers value it vastly differently. What is a suitable auction to sell the item, in terms of efficiency as well as revenue? First and second price auctions will be efficient but will only extract the lower value in equilibrium; if one knows the distributions from which values are drawn, then setting a reserve price will get optimal revenue but will not be efficient. This paper views this problem as prior-free auction and proposes a quasi-proportional allocation in which the probability that an item is allocated to a bidder depends (quasi-proportionally) on their bids. The paper also proves existence of an equilibrium for quasi-proportional auctions and shows how to compute them efficiently. Finally, the paper shows that these auctions have high efficiency and revenue.

"Auctions with Intermediaries," Jon Feldman, Vahab Mirrokni, S. Muthukrishnan, Mallesh Pai, ACM Conference on Electronic Commerce, EC, June 2010.

We study an auction where the bidders are middlemen, looking in turn to auction off the item if they win it. This setting arises naturally in online advertisement exchange systems, where the participants in the exchange are ad networks looking to sell ad impressions to their own advertisers. We present optimal strategies for both the bidders and the auctioneer in this setting. In particular, we show that the optimal strategy for bidders is to choose a randomized reserve price, and the optimal reserve price of the centeral auctioneer may depend on the number of bidders (unlike the case when there are no middlemen).

Computer Vision

"Discontinuous Seam-Carving for Video Retargeting," Matthias Grundmann, Vivek Kwatra, Mei Han, Irfan Essa, Computer Vision and Pattern Recognition, CVPR, June 2010.

Playing a video on devices with different form factors requires resizing (or retargeting) the video to fit the resolution of the given device. We have developed a content-aware technique for video retargeting based on discontinuous seam-carving, which unlike standard methods like uniform scaling and cropping, strives to retain salient content (such as actors, faces and structured objects) while discarding relatively unimportant pixels (such as the sky or a blurry background). The key innovations of our research include: (a) a solution that maintains temporal continuity of the video in addition to preserving its spatial structure, (b) space-time smoothing for automatic as well as interactive (user-guided) salient content selection, and (c) sequential frame-by-frame processing conducive for arbitrary length and streaming video.

Machine Learning

"Random classification noise defeats all convex potential boosters," Philip M. Long, Rocco A. Servedio, Machine Learning, vol. 78 (2010), pp. 287-304.

A popular approach that has been used to tackle many machine learning problems recently is to formulate them as optimization problems in which the goal is to minimize some “convex loss function.” This is an appealing formulation because these optimization problems can be solved in much the same way that a marble rolls to the bottom of a bowl. However, it turns out that there are drawbacks to this formulation. In "Random Classification Noise Defeats All Convex Potential Boosters," we show that any learning algorithm that works in this way can fail badly if there are noisy examples in the training data. This research motivates further study of other approaches to machine learning, for which there are algorithms that are provably more robust in the presence of noise.

IR

"Clustering Query Refinements by User Intent," Eldar Sadikov, Jayant Madhavan, Lu Wang, Alon Halevy, Proceedings of the International World Wide Web Conference, WWW, April 2010.

When users pose a search query, they usually have an underlying intent or information need, and the sequence of queries he or she poses in single search sessions is usually determined by the user's underlying intent. Our research demonstrates that there typically are only a small number of prominent underlying intents for a given user query. Further, these intents can be identified very accurately by an analysis of anonymized search query logs. Our results show that underlying intents almost always correspond to well-understood high-level concepts.

HCI

"How does search behavior change as search becomes more difficult?", Anne Aula, Rehan Khan, Zhiwei Guan, Proceedings of the ACM Conference on Human Factors in Computing Systems, CHI , April 2010.

Seeing that someone is getting frustrated with a difficult search task is easy for another person--just look for the frowns, and listen for the sighs. But could a computer tell that you're getting frustrated from just the limited behavior a search engine can observe? Our study suggests that it can: when getting frustrated, our data shows that users start to formulate question queries, they start to use advanced operators, and they spend a larger proportion of the time on the search results page. Used together, these signals can be used to build a model that can potentially detect user frustration.

Read More

Google North American Faculty Summit - Day 1

Posted by Úlfar Erlingsson, Manager, Security Research

Thursday, July 29 was the first day of the Google North American Faculty Summit, our sixth annual event bringing together Google engineers and subject matter experts with leading computer science faculty, mostly from North America but some from as far away as Japan and China. This year’s summit is focused on three topics: cloud computing, security and privacy, and social networking. It was these first two areas that we discussed yesterday, in a series of talks by Googlers, informal meetings and small round-table discussions.

After an introduction from Alfred Spector, Google’s VP of Research and Special Initiatives, we dove right into the technical talks, covering the “arms race” of malware detection, privacy and public policy, passwords and authentication, and operations and infrastructure security at large scale. I gave a talk on the changes that cloud computing brings to security, both challenges such as privacy and authentication, as well as opportunities for security improvements, which I wanted to summarize briefly below.

Cloud services have defined a new model for end-user cloud applications that are accessed via single-user devices or browsers. Unlike software on personal computers, or on time-shared servers, cloud applications execute logically on stateless clients accessing a substrate of redundant back-end servers. While a single client may execute multiple applications, those applications are typically isolated and communicate only via the cloud, thus eliminating local dependencies and simplifying device management. As well as being isolated and stateless, clients are also provisioned with software upon use, which makes any client pretty much the same as any other and facilitates transparent access from different locations and devices.

There are many clear security benefits that accrue from this cloud application software model. To start with, it eliminates much of the complex, error-prone management traditionally required for each client. Also, because clients and servers are replicated or stateless, security policies can be enforced using simple, conservative fail-stop mechanisms. Cloud applications are also highly dynamic, with new software versions easily deployed through client restart or rolling server upgrades. Not only does this greatly simplify deploying fixes to software vulnerabilities, it also allows for the possibility of deploying specialized software versions, with custom security aspects, to different clients and servers. Such software instrumentation could be used for many diverse security purposes, especially when combined with randomization: these include artificially-induced heterogeneity as well as the large-scale construction and enforcement of models for appropriate software behavior. In short, cloud applications help with basic, but hard-to-answer security questions such as: Am I running the right software? Or, is it known to be bad? Is it behaving maliciously, and can I recover if it is?

Following my talk, faculty attendees had a variety of insightful questions—as they did for all the presenters today. Roy Campbell, from University of Illinois at Urbana-Champaign, raised the issue of zero-day attacks, and how they might be handled and prevented. My response was that while it might be impossible to eliminate all security bugs, it is possible to get strong guarantees and higher assurance about fundamental software aspects. As an example, I mentioned the Native Client open source Google project that establishes strong, verifiable guarantees about the safety of low-level software. Another question raised was whether Multics-like protection rings were relevant to today's cloud computing applications. Although the mechanisms may not be the same as in Multics, my reply was that layered security and defense in depth are more important than ever, since cloud computing by necessity makes use of deep software stacks that extend from the client through multiple, nested back-end services.

On Friday’s agenda: the technical possibilities of the social web. We’ll be back with more highlights from the summit soon—stay tuned.

Read More

And the award goes to...

Posted by Fernando Pereira, Research Director

Google's very own Tushar Chandra along with his coauthors, Vassos Hadzilacos, and Sam Toueg, received the prestigious Dijkstra Prize in Distributed Computing at the ACM Symposium on Principles of Distributed Computing conference in Zürich. This award is given for outstanding papers that have had great impact on the theory and practice of distributed computing for over a decade.

Their papers introduced and precisely characterized the notion of unreliable failure detection in a distributed system:

• Tushar D. Chandra and Sam Toueg. "Unreliable Failure Detectors for Reliable Distributed Systems," Journal of the ACM, 43(2):225-267, 1996.
  (The first version appearing in the Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, 1991.)
• Tushar D. Chandra, Vassos Hadzilacos and Sam Toueg. "The Weakest Failure Detector for Solving Consensus," Journal of the ACM, 43(4):685-722, 1996.
  (The first version appearing in the Proceedings of the 11th ACM Symposium on Principles of Distributed Computing, 1992.)

Tushar currently works on large-scale machine learning and distributed systems at Google.

You can find more information about the award and the papers here.

Congratulations to Tushar, Vassos, and Sam!

Read More

Googlers receive multiple awards at the 2010 International Conference on Machine Learning

Posted by Fernando Pereira, Research Director

Googlers were recognized in three of the four paper awards at ICML 2010:

• Sajid Siddiqi was co-recipient of the best paper award for Hilbert Space Embeddings of Hidden Markov Models with Le Song, Byron Boots, Geoff Gordon, and Alex Smola
• John Duchi, who is also a graduate student at UC Berkeley, was co-recipient of the best student paper award for On the Consistency of Ranking Algorithms with Lester Mackey and Michael Jordan
• And last but not the least, Yoram Singer was co-recipient of the best 10-year paper award for the most influential paper of ICML 2000, Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers (pdf) with Erin Allwein and Robert Schapire, which has currently 852 citations in Google Scholar.

I feel a particular connection to this last paper as Rob and Yoram were members of technical staff and Erin a student intern at the department I headed at AT&T Labs when this work was done.

Congratulations to all!

Read More