Papers on specialized databases at Google

Googlers have published two papers recently at academic conferences detailing new specialized databases that are heavily used within Google.

The first paper is a USENIX 2010 paper describing Percolator. Percolator is the database powering Caffeine, which is Google's new system to provide fresher search results by adding new documents and updates to documents to their search index in near real-time.

The Percolator paper is titled "Large-scale Incremental Processing Using Distributed Transactions and Notifications" (PDF). An excerpt:

We have built Percolator, a system for incrementally processing updates to a large data set, and deployed it to create the Google web search index. By replacing a batch-based indexing system with an indexing system based on incremental processing using Percolator, we process the same number of documents per day, while reducing the average age of documents in Google search results by 50%.

Percolator is built on top of the Bigtable distributed storage system .... Percolator was built specifically for incremental processing and is not intended to supplant existing solutions for most data processing tasks. Computations where the result can't be broken down into small updates (sorting a file, for example) are better handled by MapReduce. Also, the computation should have strong consistency requirements; otherwise, Bigtable is sufficient. Finally, the computation should be very large in some dimension (total data size, CPU required for transformation, etc.); smaller computations not suited to MapReduce or Bigtable can be handled by traditional DBMSs.

Percolator is a specialized database that adds new consistency guarantees (as well as triggers, which they call "observers") to Bigtable. One thing that is interesting is how specialized this system is. Percolator, for example, is in no way intended for online operations and can, in some cases, delay a transaction for tens of seconds due to stray locks. But, that is fine for the near real-time search index update task for which it is designed.

The second paper is a VLDB 2010 paper on Dremel. Dremel is a column store database designed to be orders of magnitude faster for some interactive database queries than MapReduce.

This paper is titled "Dremel: Interactive Analysis of Web-Scale Datasets" (PDF). An excerpt:

Dremel is a scalable, interactive ad-hoc query system for analysis of read-only nested data. By combining multi-level execution trees and columnar data layout, it is capable of running aggregation queries over trillion-row tables in seconds. The system scales to thousands of CPUs and petabytes of data, and has thousands of users at Google. In this paper, we describe the architecture and implementation of Dremel, and explain how it complements MapReduce-based computing.

Dremel can execute many queries over such data that would ordinarily require a sequence of MapReduce (MR) jobs, but at a fraction of the execution time. Dremel is not intended as a replacement for MR and is often used in conjunction with it to analyze outputs of MR pipelines or rapidly prototype larger computations .... Dremel provides a high-level, SQL-like language to express ad hoc queries. In contrast to layers such as Pig and Hive, it executes queries natively without translating them into MR jobs.

The paper includes some fun motivational examples describing how people use Dremel for rapid prototyping of new ideas. There is a huge advantage in spending just seconds rather than hours to examine the potential of a new feature for a classifier or a new signal for relevance rank. Dremel lets Googlers twiddle the feature multiple times to optimize it in just a few minutes, then run a big, multi-hour MapReduce job to get the final data, a huge advantage over rivals that might take days to do the same investigation.

Dremel, like all column stores, it works best when selecting just a few columns from the data, but that is a very common case well worth optimizing for. One fun aside briefly mentioned in the paper is that they see another order of magnitude or two speedup if they can stop after only looking at 98% of the data or so because waiting for straggler chunks causes big slow downs. So, if you are willing to have (unusually slightly) inaccurate results, you can get huge boosts in speed from stopping queries early. That is also not new, but again a very common case and worth thinking about.

In both of these papers, what I find so remarkable is how willing Google is to build specialized databases to speed up tasks. Percolator can only be used for tasks have huge data, strong consistency requirements, and can tolerate occasional latency of tens of seconds, but that is perfect for near real-time search index updates. Dremel can only be used for selecting a few columns of data, but it is extremely common that a MapReduce job wants to ignore almost all the data in each record. It reminds me of the specialized search index structures and kernel twiddles Google does, which are other interesting examples of the lengths Google is willing to go to maximize the usefulness of their internal tools and the performance of their systems.

Groupon is not Googly

It is being widely reported that Google is bidding as much as $6B for Groupon. From an article in the New York Times:

Google has offered Groupon $5.3 billion, with the promise of $700 million in performance bonuses for management.

It could ... give Google access to a large sales force ... Groupon has 3,100 employees ... [and] 35 million [Groupon] subscribers worldwide, with 17 million in North America.

11 months [ago] ... Groupon ... [had only] 200 employees ... [Now] about 1,000 people work in the Chicago office and some 2,000 more are spread across its sprawling worldwide network, which includes the employees of its recent international acquisitions, ClanDescuento and Citydeal.de — group-buying sites in Chile and Germany. According to Groupon, the company is adding more than 200 employees a month.

It is unclear to me why Google is so interested in this company, so much so that it is willing to pay nearly twice what it paid for DoubleClick.

Google helps people find information. It's mission is "to organize the world's information and make it universally accessible and useful." In advertising, Google helps people find millions of interesting small businesses and sort through billions of products to get what they need.

Groupon is very different. Groupon runs one deal per day per market. There is no technology at Groupon, no information finding, no long tail, no massive data stream. What there is is a large (but very recently hired) sales force, significant revenue, and a decent subscriber base. Those are the kinds of things that looks good to MBAs building spreadsheets and empires, but are not deeply aligned with Google's mission of organizing information and making it useful.

It looks like this is a done deal at this point. But Groupon is not Googly. I fear these cultures are not going to blend well when mashed together. I wish these two luck, but this looks to be more like the kind of union where the bride walks away with the house and the dog in a few years than one where both sides thrive.

Update: It appears it was not a done deal after all.

An update on Google's infrastructure

Google Fellow Jeff Dean gave a talk at Stanford for the EE380 class with fascinating details on Google's systems and infrastructure. Krishna Sankar has a good summary along with a link to video (Windows Media) of the talk.

Some fun statistics in there. Most amazing are the improvements in data processing that have gotten them to the point that, in May 2010, 4.4M MapReduce jobs consumed 39k machine years of computation and processed nearly an exabyte (1k petabytes) of data that month. Remarkable amount of data munching going on at Google.

The talk is an updated version of Jeff's other recent talks such as his LADIS 2009 keynote, WSDM 2009 keynote, and 2008 UW CS lecture.

[HT, High Scalability, for the pointer to Krishna Sankar's notes]

More on why paywalls fail

Felix Salmon on why paywalls fail:

It’s not just that readers don’t see the value in paying for content when something “similar” can be found elsewhere. It’s also that there is positive extra value in reading free content, since it becomes much easier to share that content via email or blogs or Facebook or Twitter, you don’t need to worry about following links or running into paywalls, and in general you know that the site will play well with others on the open web.

If Newsday puts up a paywall and it fails, is that because readers can find content similar to Newsday’s elsewhere for free? Yes, in part. But it’s also because the people who would otherwise visit Newsday.com have lots of other things they also like to do. They like to spend time in Farmville, or they want to watch a video of a dog skateboarding, or they want to see their house on Google Earth, or they want to go walk their dog. These aren’t people who need certain information and are going to seek it out at the lowest cost; they’re just people who would visit Newsday’s website if it was free, but won’t if it isn’t.

That’s why gateways and paywalls are such problematic things, online: they’re a bit like that crappy VIP room in the back of the nightclub which is much less pleasant than the big main space. You might wander in there from time to time if it’s free, but if you need to buy an expensive bottle of Champagne to do so, forget it. There’s lots of other stuff to do, both online and off. And so the walled-off areas of the internet simply get ignored.

It is not just that the content has to be uniquely valuable to make the hurdle of a paywall worth it to readers. It is also that the experience of a paywall detracts from the value of the content because of the hassle to all readers, including when someone wants to share an article with a colleague but cannot because of the paywall.

I would add that, even ignoring the value of sharing, the hurdle of a paywall often seems to be underestimated. As described in Dan Ariely's Predictably Irrational ([1] [2]), among other places ([3]), free has no transaction costs, no risk of loss, and great appeal. Charging anything, anything at all, creates transaction costs and risk, to the point that the vast majority of people will not do it unless the perceived value is obvious and obviously high.

Round-up of latest reading

I've been active microblogging on Google Reader lately. Here's a summary of some of the topics that have caught my attention recently.

• Microsoft's Bing finally launches a form of personalized search ([1] [2] [3])


• Netflix is shifting entirely to Amazon Web Services, not just for streaming, but for almost everything ([1] [2])


• Postmortems of startup failures ([1] [2])


• It took four long years, but spiking Android sales and the promising early reviews of Windows Phone 7 probably signal the beginning of the end of the iPhone's reign ([1] [2] [3])


• Microsoft cut benefits again. Their lack of corporate memory is just astounding. Look for new problems in morale and retention, just like after 2004, then for the benefits to be reinstated a couple years later, like they did in 2006. ([1] [2] [3])

More in my shared items microblogging stream or, if you use Google Reader, search for me and follow my shared items there.

Eric Schmidt on automatic search

Google CEO Eric Schmidt talks up automatic search from mobile devices:

Ultimately, search is not just the web but literally all of your information - your email, the things you care about, with your permission - this is personal search, for you and only for you.

"The next step of search is doing this automatically. When I walk down the street, I want my smartphone to be doing searches constantly - 'did you know?', 'did you know?', 'did you know?', 'did you know?'.

This notion of autonomous search - to tell me things I didn't know but am probably interested in, is the next great stage - in my view - of search.

While I agree with the idea of heavily localized and personalized searches, especially on mobile devices, I think this autonomous search feature sounds really annoying. You don't want to get in people's way. You don't want to interrupt them with something unimportant, especially if you are interrupting someone who is trying to get something done.

Perhaps what might be desirable would be better described as recommendations and personalized advertising, not as some Googly version of Clippy popping up and chirping, "Did you know? Did you know?"

Update: Interesting discussion in the comments about whether what Google is building is really personalized advertising, not search.

Causing internal competition and low morale through compensation policy

Over at Mini-Microsoft, Microsoft employees are listing the details of their compensation changes after their performance reviews.

Reading through them, it is pretty clear that almost everyone is unhappy, both with their reviews and with their relative gains. Which is exactly what you would expect.

This is an instructive example of how forced rank and fine-grained compensation adjustments based on forced rank hurt morale and ends up competing people inside a company against each other.

What you want in an organization is people focused on working together as a team. But, when you use forced rank, a fixed compensation budget for the group, and compensation changes tied to rankings, success for everyone becomes a zero-sum game. You can do just as well by bringing down people on your team -- so you look relatively better -- as by helping people on your team. In fact, it is probably easier to do better by dragging down your colleagues because you have direct control over that.

Performance-based compensation sounds great in theory, but never works in practice, partly because managers lack the information and objectivity to implement it well, partly because people never remember what they do badly and so are almost always angered by the review and compensation adjustments.

For more on this topic, please see my earlier posts, "The problem with forced rank", "Management and total nonsense", and "Joel Spolsky on management methods".

Cuil is dead

Cuil is dead:

Cuil, the much maligned search engine that at one time had hopes of toppling Google, has gone offline ... It may be done for good. Those employees who are still with the company apparently weren't paid this week, and they're starting to say they’re looking for new jobs.

Flashback to the hype of July 2008 around Cuil:

Take yesterday's over-hyped launch of stealth search startup Cuil, which was quickly followed by a backlash when everyone realized that it was selling a bill of goods. This was entirely the company's own fault. It pre-briefed every blogger and tech journalist on the planet, but didn’t allow anyone to actually test the search engine before the launch.

The company's founders have a good pedigree ... But creating a big index is only half the battle. A good search engine has to bring back the best results from that haystack as well. Here Cuil falls short ... The results Cuil returns aren't particularly great, and sometimes completely off the mark.

And what happened soon after:

The launch of the search engine was nothing but a classic PR trainwreck, with much hype and little to show for. Cuil failed to deliver good enough results to drive anyone to change their search behavior, and quickly became the subject of backlash and criticism because of their poor performance and indexing methods that actually took websites down in the process.

I took a peek at how they're doing traffic-wise out of sheer curiosity. After all, with no less than $33 million in funding and a founding management team consisting of ex-Google search experts, something had to give, right? Well, no. Cuil isn't performing well any way you look at it ... search engine traffic is nearing rock bottom.