Comparing Google Megastore

A small pile of Googlers recently presented a paper, "Megastore: Providing Scalable, Highly Available Storage for Interactive Services" (PDF) that details the architecture of a major distributed database used at Google.

Megastore "has been widely deployed within Google for several years ... handles more than three billion write and 20 billion read transitions daily ... [and] stores nearly a petabyte ... across many datacenters."

Others have already summarized the paper ([1] [2]), so I'll focus on my reaction to it. What I found surprising about Megastore, especially when comparing to other large scale databases, is that it favors consistency over performance.

For consistency, Megastore provides "full ACID semantics within partitions", "supports two-phase commit across entity groups", guarantees that reads always see the last write, uses Paxos for confirming consensus among replicas, and uses distributed locks between "coordinator processes" as part of detecting failures. This is all unusually strong compared to the more casual eventual consistency offered by databases like Amazon's Dynamo, Yahoo's HBase, and Facebook's Cassandra.

The problem with providing Megastore's level of consistency is performance. The paper mostly describes Megastore's performance in sunny terms, but, when you look at the details, it does not compare favorably with other databases. Megastore has "average read latencies of tens of milliseconds" and "average write latencies of 100-400 milliseconds". In addition, Megastore has a limit of "a few writes per second per entity group" because higher write rates will cause conflicts, retries, and even worse performance.

By comparison, Facebook expects 4ms reads and 5ms writes on their database, so Megastore is an order of magnitude or two slower than what Facebook developers appear to be willing to tolerate.

Google application developers seem to find the latency to be a hassle as well. The paper says that Googlers find the latency "tolerable" but often have to "hide write latency from users" and "choose entity groups carefully".

This makes me wonder if Google has made the right tradeoff here. Is it really easier for application developers to deal with high latency all of the time than to almost always have low latency but have to worry more about consistency issues? Most large scale databases have made the choice the other way. Quite surprising.

Update: Googler DeWitt Clinton writes with a good point: "We build on top of Megastore when we require some of those characteristics (availability, consistency), and to Bigtable directly when we require low latency and high throughput instead. So it's up to the application to decide what tradeoffs to make, definitely not one-size-fits-all."

Google, Bing, and web browsing data

I suppose I should comment, as everyone else on the planet has, on Google's claim that Bing is copying their results.

My reaction is mostly one of surprise. I am surprised that Google wants this issue discussed in the press. I am surprised that Google wants this aired in the court of public opinion.

Google is trying to draw a line on what use of behavior data is acceptable. Google clearly thinks they are on the right side of that line, and I do too, but I'm not sure the average searcher would agree. And that is why Google is playing a dangerous game here, one that could backfire on them badly.

Let's take a look at what Google Fellow Amit Singhal said:

This experiment confirms our suspicion that Bing is using some combination of:

• Internet Explorer 8, which can send data to Microsoft via its Suggested Sites feature
• the Bing Toolbar, which can send data via Microsoft’s Customer Experience Improvement Program

or possibly some other means to send data to Bing on what people search for on Google and the Google search results they click.

Of course, what Amit does not mention here is that the widely installed Google Toolbar and the fairly popular Google Chrome web browser sends very similar data back to Google, data about every page someone visits and every click they make. Moreover, Google tracks almost every web search and every click after a web search made by web users around the world, since almost every web search is done on Google.

By raising this issue, Google very publicly is trying to draw a particular line on how toolbar and web browsing data should be used, and that may be a dangerous thing for Google to do. The average searcher, for example, may want that line drawn somewhere other than where Google might expect it to be drawn -- they may want it drawn at not using any toolbar/Chrome data for any purposes, or even not using any kind of behavior data at all -- and, if that line is drawn somewhere other than where Google wants it, Google could be hurt badly. That is why I am surprised that Google is coming out so strong here.

As for the particular issue of whether this is copying or not, I don't have much to say on that, but I think the most thought-provoking piece I have seen related to that question is John Langford's post, "User preferences for search engines". John argues that searchers own their browsing behavior and can reveal what they do across the web to whoever they want to. Whether you agree or not with that, it is worth reading John's thoughts on it and considering what you think might be the alternative.

Update: In the comments, Peter Kasting, a Google engineer working on Chrome, denies that Chrome sends clickstream data (the URLs you visit) back to Google. A check of the Google Chrome privacy policy ([1] [2]) appears to confirm that. I apologize for getting that wrong and have corrected the post above.

Update: A few days later, search industry watcher Danny Sullivan writes, "In short, Google doesn’t occupy any higher ground than Microsoft, from what I can see, when it comes to using data gathered from browser add-ons to improve its own services, including its search engine." Whether you think Danny is right or not, his article demonstrates that Google was wrong in thinking they would easily win if they took this fight to the press.

YouTube uses Amazon's recommendation algorithm

In a paper at the recent RecSys 2010 conference, "The YouTube Video Recommendation System" (ACM), eleven Googlers describe the system behind YouTube's recommendations and personalization in detail.

The most interesting disclosure in the paper is that YouTube has switched from their old recommendation algorithm based on random walks to a new one based on item-to-item collaborative filtering. Item-to-item collaborative filtering is the algorithm Amazon developed back in 1998. Over a decade later, it appears YouTube found a variation of Amazon's algorithm to be the best for their video recommendations.

Other notable tidbits in the paper are what the Googlers have to do to deal with noisy information (noisy video metadata and user preference data), the importance of freshness on videos (much like news), that they primarily used online measures of user satisfaction (like CTR and session length) when competing different recommendation algorithms against each other and tuning each algorithms, and the overall improvement (about x3 better) that recommendations got over simple features that just showed popular content.

Some excerpts from the paper:

Recommending interesting and personally relevant videos to [YouTube] users [is] a unique challenge: Videos as they are uploaded by users often have no or very poor metadata. The video corpus size is roughly on the same order of magnitude as the number of active users. Furthermore, videos on YouTube are mostly short form (under 10 minutes in length). User interactions are thus relatively short and noisy ... [unlike] Netflix or Amazon where renting a movie or purchasing an item are very clear declarations of intent. In addition, many of the interesting videos on YouTube have a short life cycle going from upload to viral in the order of days requiring constant freshness of recommendation.

To compute personalized recommendations we combine the related videos association rules with a user's personal activity on the site: This can include both videos that were watched (potentially beyond a certain threshold), as well as videos that were explicitly favorited, “liked”, rated, or added to playlists ... Recommendations ... [are the] related videos ... for each video ... [the user has watched or liked after they are] ranked by ... video quality ... user's unique taste and preferences ... [and filtered] to further increase diversity.

To evaluate recommendation quality we use a combination of different metrics. The primary metrics we consider include click through rate (CTR), long CTR (only counting clicks that led to watches of a substantial fraction of the video), session length, time until first long watch, and recommendation coverage (the fraction of logged in users with recommendations). We use these metrics to both track performance of the system at an ongoing basis as well as for evaluating system changes on live traffic.

Recommendations account for about 60% of all video clicks from the home page ... Co-visitation based recommendation performs at 207% of the baseline Most Viewed page ... [and more than 207% better than] Top Favorited and Top Rated [videos].

For more on the general topic of recommendations and personalization on YouTube, please see my 2009 post, "YouTube needs to entertain".

By the way, it would have been nice if the Googlers had cited the Amazon paper on item-to-item collaborative filtering. Seems like a rather silly mistake in an otherwise excellent paper.

Update: To be clear, this was not intended as an attack on Google in any way. Googlers built on previous work, as they should. What is notable here is that, despite another decade of research on recommender systems, despite all the work in the Netflix Prize, YouTube found that a variant of the old item-to-item collaborative filtering algorithm beat out all others for recommending YouTube videos. That is a very interesting result and one that validates the strengths of that old algorithm.

Latest reading

A few things that have caught my attention lately:

• Google generates $24 per user, Yahoo $8, and Facebook $4. ([1])
  
  
• Paul Graham's most important traits in founders. I'd say they even are in priority order. ([1])
  
  
• Groupon competitors suddenly are everywhere. Not surprising, there's no technology barrier here, and it is easy to attract people if you offer 50% off at a popular store. But, I wonder if this booming fad is sustainable. Particularly concerning is that only 22% who use a Groupon offer return to the merchant, which, combined with the steep discounts, make this look expensive. ([1] [2] [3] [4])
  
  
• Google is accused of copying a bunch of someone else's code. And this isn't the first time. Back in 2005, Google was accused of copying much of the code for Orkut. ([1] [2]).
  
  
• Great, updated, and free book chapters on how people spam search engines. I particularly like the new discussion of spamming click data and social sites. ([1])
  
  
• A very dirty little secret: most AOL subscribers don't realize they don't need to be paying, and the revenue from hoodwinking those people is a big part of AOL's profits. ([1])
  
  
• Best article I've seen on why Google CEO Eric Schmidt is stepping down ([1])
  
  
• With this latest move, Amazon closes the gap between their low level cloud services (microleasing of servers and storage) and the higher level offerings of Google App Engine and Microsoft Azure. ([1])
  
  
• The trends of abandoning TV and embracing smartphones have been vastly overstated. Most Americans watch more TV than ever and use dumbphones. ([1] [2]).
  
  
• A claim that Facebook has resorted to scammy malware-type advertisements in an effort to drive revenue. ([1]).

The experiment infrastructure at Google

Papers that reveal details of Google's internal systems are always fun. At KDD 2010 a few months ago, four Googlers presented "Overlapping Experiment Infrastructure: More, Better, Faster Experimentation" (PDF).

The paper describes Google's tools for handling the challenging task of running many experiments simultaneously and includes tidbits on how they launch new features. Some excerpts:

We want to be able to experiment with as many ideas as possible .... It should be easy and quick to set up an experiment ... Metrics should be available quickly so that experiments can be evaluated quickly. Simple iterations should be quick ... The system should ... support ... gradually ramping up a change to all traffic in a controlled way.

[Our] solution is a multi-factorial system where ... a request would be in N simultaneous experiments ... [and] each experiment would modify a different parameter. Our main idea is to partition parameters into N subsets. Each subset is associated with a layer of experiments. Each request would be in at most N experiments simultaneously (one experiment per layer). Each experiment can only modify parameters associated with its layer (i.e., in that subset), and the same parameter cannot be associated with multiple layers ... [We] partition the parameters ... [by] different binaries ... [and] within a binary either by examination (i.e., understanding which parameters cannot be varied independently of one another) or by examining past experiments (i.e., empirically seeing which parameters were modified together in previous experiments).

Given this infrastructure, the process of evaluating and launching a typical feature might be something like: Implement the new feature in the appropriate binary (including code review, binary push, setting the default values, etc) ... Create a canary experiment (pushed via a data push) to ensure that the feature is working properly ... Create an experiment or set of experiments (pushed via a data push) to evaluate the feature ... Evaluate the metrics from the experiment. Depending on the results, additional iteration may be required, either by modifying or creating new experiments, or even potentially by adding new code to change the feature more fundamentally ... If the feature is deemed launchable, go through the launch process: create a new launch layer and launch layer experiment, gradually ramp up the launch layer experiment, and then finally delete the launch layer and change the default values of the relevant parameters to the values set in the launch layer experiment.

We use real-time monitoring to capture basic metrics (e.g., CTR) as quickly as possible in order to determine if there is something unexpected happening. Experimenters can set the expected range of values for the monitored metrics (there are default ranges as well), and if the metrics are outside the expected range, then an automated alert is fired. Experimenters can then adjust the expected ranges, turn off their experiment, or adjust the parameter values for their experiment. While real-time monitoring does not replace careful testing and reviewing, it does allow experimenters to be aggressive about testing potential changes, since mistakes and unexpected impacts are caught quickly.

One thing I like about the system they describe is that the process of launching is the same as the process for experimentation. That's a great way to set things up, treating everything to be launched as an experiment. It creates a culture where every change to be launched needs to be tested online and experiments are not treated so much as tests to be taken down when done as candidates to be sent out live as soon as they prove themselves.

Another thing I like is the real-time availability of metrics and ability to very quickly change experiment configurations. Not only does that allow experiments to be shut down quickly if they are having a surprisingly bad impact which lowers the cost of errors, but also it speeds the ability to learn from the data and iterate on the experiment.

Finally, the use of standardized metrics across experiments and an "experiment council" of experts who can be consulted to help interpret the experimental results is insightful. Often, results of experiments are subject to some interpretation, unfortunately enough interpretation that overly eager folks at a company can attempt to torture the data until it says what they want (even when they are trying to be honest), so an effort to help people keep decisions objective is a good idea.

One minor but surprising tidbit in the paper is that binary launches are infrequent ("weekly"); only configuration files can be pushed frequently. I would have thought they would push binaries daily. In fact, reading between the lines a bit, it sounds like developers might have to do a bit of extra work to deal with infrequent binary pushes, trying to anticipate what they will want during the experiments and writing extra code that can be enabled or disabled later by configuration file, which might interfere with their ability to rapidly learn and iterate based on the experimental results. It also may cause the configuration files to become very complex and bug-prone, which is alluded to in the section of the paper talking about the need for data file checks. In general, very frequent pushes are desirable, even for binaries.

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.

Machine learning on top of GFS at Google

Googler Tushar Chandra recently gave a talk at the LADIS 2010 workshop on "Sibyl: A system for large scale machine learning" (slides available as PDF), which discusses a system that Google has built to do large scale machine learning on top of MapReduce and GFS.

This system probably is just one of many inside the secretive search giant, but we don't often get these kinds of peeks inside. What I found most interesting was the frank discussion of the problems the Google team encountered and how they overcame them.

In particular, the Googlers talk about how they building on top of a system intended for batch log processing caused some difficulties, which they overcame by using a lot of local memory and being careful about arranging data and moving data around. Even so, the last few slides mention how they kept causing localized network and GFS master brownouts, impacting other work on the cluster.

That last problem seems to have been an issue again and again in cloud computing systems. That pesky network is a scarce, shared resource, and it often takes a network brownout to remind us that virtual machines are not all it takes to get everyone playing nice.

On a related topic, please see my earlier post, "GFS and its evolution", and its discussion of the pain Google hit when trying to put other interactive workloads on top of GFS. And, if you're interested in Google's work here, you might also be interested in the open source Mahout, which is a suite of machine learning algorithms mostly intended for running on top of Hadoop clusters.

Insights into the performance of Microsoft's big clusters

A recent article from Microsoft in IEEE Computing, "Server Engineering Insights for Large-Scale Online Services" (PDF), has surprisingly detailed information about the systems running Hotmail, Cosmos (Microsoft's MapReduce/Hadoop), and Bing.

For example, the article describes the scale of Hotmail's data as being "several petabytes ... [in] tens of thousands of servers" and the typical Hotmail server as "dual CPU ... two attached disks and an additional storage enclosure containing up to 40 SATA drives". The typical Cosmos server apparently is "dual CPU ... 16 to 24 Gbytes of memory and up to four SATA disks". Bing uses "several tens of thousands of servers" and "the main memory of thousands of servers" where a typical server is "dual CPU ... 2 to 3 Gbytes per core ... and two to four SATA disks".

Aside from disclosing what appear to be some previously undisclosed details about Microsoft's cluster, the article could be interesting because of insights into the performance of these clusters on the Hotmail, Bing, and Cosmos workloads. Unfortunately, the article suffers from taking too much as a given, not exploring the complexity of interactions between CPU, memory, flash memory, and disk in these clusters on these workloads, and not attempting to explain the many oddities in the data.

Those oddities are fun to think about though. To take a few that caught my attention:

• Why are Bing servers CPU bound? Is it because, as the authors describe, Bing uses "data compression on memory and disk data ... causing extra processing"? Should Bing be doing so much data compression that it becomes CPU bound (when Google, by comparison, uses fast compression)? If something else is causing Bing servers to be CPU bound, what is it? In any case, does it make sense for the Bing "back-end tier servers used for index lookup" to be CPU bound?
• Why do Bing servers have only 4-6G RAM each not have more memory when they mostly want to keep indexes in memory, appear to be hitting disk, and are "not bound by memory bandwidth"? Even if the boxes are CPU bound, even if it somehow makes sense for them to be CPU bound, would more memory across the cluster allow them to do things (like faster but weaker compression) that would relieve the pressure on the CPUs?
• Why is Cosmos (the batch-based log processing system) CPU bound instead of I/O bound? Does that make sense?
• Why do Cosmos boxes have more the same memory than as Bing boxes when Cosmos is designed for sequential data access? What is the reason that Cosmos "services maintain much of their data in [random access] memory" if they, like Hadoop and MapReduce, are intended for sequential log processing?
• If Hotmail is mostly "random requests" with "insignificant" locality, why is it designed around sequential data access (many disks) rather than random access (DRAM + flash memory)? Perhaps the reason that Hotmail is "storage bound under peak loads" is that it uses sequential storage for its randomly accessed data?

Thoughts?

Update: An anonymous commenter points out that the Bing servers probably are two quad core CPUs -- eight cores total -- so, although there is only 2-3G per core, there likely is a total of 16-24G of RAM per box. That makes more sense and would make them similar to the Cosmos boxes.

Even with the larger amount of memory per Bing box, the questions about the machines still hold. Why are the Bing boxes CPU bound and should they be? Should Cosmos boxes, which are intended for sequential log processing, have the same memory as Bing boxes and be holding much of their data in memory? Why are Cosmos machines CPU bound rather than I/O bound and should they be?

Update: Interesting discussion going on in the comments to this post.

What is the benefit of freaking customers out?

Miguel Helft and Tanzina Vega at the New York Times have a front page article today, "Retargeting Ads Follow Surfers to Other Sites", on a form of personalized web advertising now being called retargeting.

An excerpt:

People have grown accustomed to being tracked online and shown ads for categories of products they have shown interest in, be it tennis or bank loans.

Increasingly, however, the ads tailored to them are for specific products that they have perused online. While the technique, which the ad industry calls personalized retargeting or remarketing, is not new, it is becoming more pervasive as companies like Google and Microsoft have entered the field. And retargeting has reached a level of precision that is leaving consumers with the palpable feeling that they are being watched as they roam the virtual aisles of online stores.

In remarketing, when a person visits an e-commerce site and looks at say, an Etienne Aigner Athena satchel on eBags.com, a cookie is placed into that person’s browser, linking it with the handbag. When that person, or someone using the same computer, visits another site, the advertising system creates an ad for that very purse.

The article later goes on to contrast this technique of following you around with products you looked at before with behavioral targeting like Google is doing, which learns your broader category interests and shows ads from those categories.

If the goal of the advertising is to be useful and relevant, though, I think both of these are missing the mark. What you want to do is help people discover something they want to buy. Since the item they looked at before obviously wasn't quite right -- they didn't buy it after all -- showing that again doesn't help. Showing closely related alternatives, items that people might buy after rejecting the first item, could be quite useful though.

As marketing exec Alan Pearlstein says at the end of the NYT article, "What is the benefit of freaking customers out?" Remarketing freaks people out. If we are going to do personalized advertising, the goal should be to have the advertising be useful, either by sharing value with consumers using coupons as Pearlstein suggests, or by helping consumers find something interesting that they wouldn't have discovered on their own.

But, publishers should be careful when working with these new ad startups. A startup has a huge incentive to maximize short-term revenue and little incentive to maximize relevance. For the startup, as long as it brings in more immediate revenue, it is perfectly fine to show annoying ads that freak customers out and drive many away. Publishers need to force the focus to be on the value of the ads to the consumer so their customers are happy, satisfied, and keep coming back.

Measuring online brand advertising without experiments

A few Googlers recently published a paper with a terribly dull title, "Evaluating Online Ad Campaigns in a Pipeline: Causal Models at Scale" (abstract, PDF), at the KDD 2010 conference.

The paper turns out to be a quite interesting attempt to measure the impact of online display advertising -- a notoriously difficult problem -- by looking at how it changes people's searching and browsing online. That's hard enough, but these crazy Googlers also are trying to do this without using A/B testing. To do that last trick, they separate people into those the exposed who have seen the ad and the controls who have not seen the ad while carefully limiting the controls only to people who are similar to the exposed.

From the paper:

Traditionally, online campaign effectiveness has been measured by "clicks" ... However, many display ads are not click-able ... and some campaigns hope to build longer-term interest in the brand rather than drive immediate response. Counting clicks alone then misses much of the value of the campaign.

Better measures of campaign effectiveness are based on the change in online brand awareness ... [due] to the display ad campaign alone. We ... [find] the change in probability that a user searches for brand terms or navigates to brand sites that can be attributed to an online ad campaign.

Randomized experiments ... are the gold standard for estimating treatment effects ... [but it] requires an advertiser to forego showing ads to some users ... [which] advertisers are not keen to [do] ... Estimation without randomization is more difficult but not always impossible .... Simply put, the controls [we pick] were eligible to be served campaign ads but were not.

Our estimates require summary (not personally identifiable) data on exposed and controls. The summary data are obtained from several sources, including the advertiser's own campaign information, ad serving logs, and sampled data from users who have installed Google toolbar and opted in to enhanced features.

By the way, some have speculated in the past ([1] [2]) that Google toolbar data is being used for Google's advertising, but there was no public confirmation of that from Google. To my knowledge, this is the first public confirmation that data from Google's ubiquitous toolbar is being used by them in at least some way in their advertising.

For more on related topics, please see also my November 2008 post, "Measuring offline ads by their online impact", and my July 2008 post, "Google Toolbar data and the actual surfer model".

Human computation and lemons

NYU Professor Panos Ipeirotis has an insightful post, "Mechanical Turk, Low Wages, and the Market for Lemons", that looks at why wages are so low, usually well below minimum wage, on Amazon's MTurk.

His theory is that spammers and cheaters have turned MTurk into a market for lemons. The quality is now so bad that buyers demand a risk premium and require redundant work for quality checks, splitting what might be a risk-reduced fair wage three to five ways among the workers.

An excerpt from his post:

A market for lemons is a market where the sellers cannot evaluate beforehand the quality of the goods that they are buying. So, if you have two types of products (say good workers and low quality workers) and cannot tell who is whom, the price that the buyer is willing to pay will be proportional to the average quality of the worker.

So the offered price will be between the price of a good worker and a low quality worker. What a good worker would do? Given that good workers will not get enough payment for their true quality, they leave the market. This leads the buyer to lower the price even more towards the price for low quality workers. At the end, we only have low quality workers in the market (or workers willing to work for similar wages) and the offered price reflects that.

This is exactly what is happening on Mechanical Turk today. Requesters pay everyone as if they are low quality workers, assuming that extra quality assurance techniques will be required on top of Mechanical Turk.

So, how can someone resolve such issues? The basic solution is the concept of signalling. Good workers need a method to signal to the buyer their higher quality. In this way, they can differentiate themselves from low quality workers.

Unfortunately, Amazon has not implemented a good reputation mechanism. The "number of HITs worked" and the "acceptance percentage" are simply not sufficient signalling mechanisms.

If you like Panos' post, you might also be interested in GWAP guru and CMU Professor Luis von Ahn's recent post, "Work and the Internet", where Luis bemoans the low wages on MTurk and questions whether they amount to exploitation. Panos' post is a response to Luis'.

Please see also my 2005 post, "Amazon Mechanical Turk?", where I wrote, "If I scale up by doing cheaper answers, I won't be able to filter experts as carefully, and quality of the answers will be low. Many of the answers will be utter crap, just made up, quick bluffs in an attempt to earn money from little or no work. How will they deal with this?"

Big redesign at Google News

It has been widely reported that Google News has done a major redesign -- its first since 2002 apparently -- to more prominently feature personalization and customization.

Before I comment on it, in the interest of full disclosure, I should say that I am absurdly biased on this particular topic, having run Findory and talked at length over the years with Google, their partners, and their competitors about news personalization.

That said, I don't like what they've done. And I'm not the only one. Thomas Claburn at InformationWeek catalogs the complaints he is seeing at InformationWeek and elsewhere, summarizing it all by comparing it to the "New Coke" flop.

I think what the Google team has done is a lovely example of personalization done poorly, by people who really should know better. They change navigation links based on personalization even when confidence is low (one of my links in the left hand nav is for "Lindsay Lohan", which is hard to stomach). The article recommendations are often off, cannot be corrected, do not change in real time as you read articles, and there is no explanation of why something was recommended. There is no ability to see, edit, or rate your reading history. The ability to exclude or favor sources appears to be hacked on; the only way to do it is to manually type in the names of sources.

Under the surface, there appears still to be a lot of implicit personalization based on past behavior, but, from what someone using it sees, the focus is entirely on customization. I can "edit personalization" and "add sections" to put categories on my page. And that is about the limit of my control and the limit of the explanations of why articles are appearing. People like to be in control. They like to understand why something happens, especially if they don't agree with it. And Google News offers very little control or explanations.

Adding to the other problems, the design seems really busy and confused to me, like the Googlers can't decide what they are doing and -- in a fashion more typical of Microsoft -- just keep adding features. Hey, look, it's your fast flipping, clustered, personalized, customizable, widget-complete newspaper! Love it, it's Googly! C'mon, Google, what happened to keeping it clean, simple, and relevant?

Google to personalize metashopping

In an interview with CNet, Googler Sameer Samat talks about Google's future plans for shopping search, including personalization and recommendations.

An excerpt:

One thing Google doesn't do very well is provide the shopping-as-adventure experience ... You might go to the mall with a specific product in mind, but a well-designed mall ... forces you to discover -- and hopefully purchase -- other products that you might not have even known you wanted: the marketing types like to call this "serendipity." Google wants to be known as a destination for that kind of experience, said Sameer Samat, director of product management.

After years of trying and failing to reach that goal, Google plans to give it another go over the coming months. Don't expect Google to turn into a full-blown online retailer among the likes of Amazon.com or Buy.com just yet. But the combination of personalized features for product search pages and what Samat thinks is "the largest database of products that has been created" could entice people to actually shop on Google.

Google's current approach works best for those who are on a mission when they shop, shoppers who already know what they want and are just looking for additional information before sealing the deal ... [But] there are millions of other people who treat shopping as leisure, rather than a simple transaction. These are people who ... prefer browsing to targeted shopping, knowing that every now and then they'll discover something totally unique or completely unexpected.

Google wants to serve more of those people ... [by making] recommendations based on that list of products and lists submitted by others to help you discover new products: sort of like Amazon's recommendations page meets Pandora's radio stations meets Google.

"Shopping is not just about search, it's not just about intent, it's about discovery," Samat said. "If we can do it, and do it well, we will have built something that's really amazing; it should be the most comprehensive experience for shopping you could ever find."

On a related note, Google is pushing aggressively to get retailers to use Google's commerce search engine to run their search experience. Each deal Google signs gives them more detailed information about another retailing vertical. It's all about the data.