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]).

Read More

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.

Read More

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.

Read More

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.

Read More

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]

Read More

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.

Read More

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.

Read More