Bret Taylor's blog

We need better mobile multitasking

2014-04-24T05:48:34Z

The dominant trend in mobile design is to make apps completely immersive and tactile. Almost every new app I see has the same design philosophy: big text and photos, usually one per screen, that you can page through with the flick of a finger.

These next generation apps are beautiful, but they don’t address my biggest mobile usability concern: multitasking. In many ways, current design trends are moving in the opposite direction — every app experience is full screen, completely taking over my device and ignoring the app I was using previously.

Whenever I need to do research or genuinely use two apps simultaneously, I still have to go back to my laptop (despite being a poster child for embracing mobile). I think the mobile OS that figures out a multitasking interface that is as efficient as PCs will gain much wider adoption on tablets. It may even reinvigorate tablet sales by expanding the use cases for post-PC devices.

I personally want a tabbed interface for apps on my tablet like I have for sites in my web browser. I am in the minority based on current mobile design trends, but I care more about the utility of transitioning between apps quickly than I do about the size of my photos.

As an engineer, it is interesting to observe the nuanced differences between desktop browsers and mobile apps as it relates to user interface. I am not talking about HTML vs. native code, but which parts of the interface are in the developer’s control vs. the end user’s control.

Web browsers are distinctly about user control. As the end user, I control the size of the window. I can right click on a link and control whether it opens in the same tab or a new tab. I can install plugins that directly manipulate apps written by other people. I can highlight anything I see and copy it to the clipboard. As a developer, you have to try really hard to disable these behaviors, and in most cases, it is impossible to do so.

Mobile apps have taken the opposite approach for a combination of technical and product design reasons. Everything is in the developer’s control. Text isn’t selectable unless the developer decides it is. When a user clicks on a link or a button, the developer gets to choose what happens. Whenever I click on an address on my iPad, it automatically opens in Apple Maps even though I use Google Maps exclusively (I am admittedly biased). As the end user, I have absolutely no control over any these behaviors.

I think multitasking is a natural side effect of operating systems that offer greater end user control. PC-like windowed interfaces are clearly not the right choice for tablets, but we need something better than we have now (and no, Android intents aren’t even close to enough).

I think it will require a philosophical shift from where we are now, taking some control out of the hands of app developers and putting it back in the hands of the end user so she can control what apps are on her screen at the same time. I think doing so would put the final nail in the coffin for PCs and make my tablet a true replacement for my laptop.

Vector Graphics in iOS via PDF

2013-11-03T06:44:33Z

I make iOS card games in my spare time. I love playing cards on my iPhone, and I love making the AI for the computer player (yes, I am that type of person).

When I started my first game, I couldn't find any decent library to render playing cards on iOS. There were a bunch of repositories of playing card images (most of them hideous), but none worked for me. I needed multiple resolutions: iPhone, iPad, retina, non-retina, etc. I really wanted to be able to specify and change card sizes in my code.

I eventually discovered an awesome vector playing card set on Google Code, but quickly ran into a different roadblock: iOS does not support rendering vector graphics natively.

There are a few open source projects like SVGKit that offer full stack SVG parsing, but I was intimidated about importing such a large library into my weekend project just to render a playing card.

Knowing iOS and Mac OS support PDF natively, I decided to take a different approach: convert my vector graphics to a PDF document. PDF supports vector drawing, and I could use the Core Graphics PDF functions to convert them to UIImages, i.e.,

NSURL *url = [NSURL fileURLWithPath:[NSBundle.mainBundle pathForResource:@"Card" ofType:@"pdf"]];
CGSize size = CGSizeMake(100, 200); // Output image size
CGPDFDocumentRef document = CGPDFDocumentCreateWithURL((CFURLRef)url);
UIGraphicsBeginImageContextWithOptions(size, false, 0);
CGContextRef context = UIGraphicsGetCurrentContext();
CGContextTranslateCTM(context, 0.0, size.height);
CGContextScaleCTM(context, 1.0, -1.0);
CGPDFPageRef page = CGPDFDocumentGetPage(document, 1);
CGContextConcatCTM(context, CGPDFPageGetDrawingTransform(page, kCGPDFBleedBox, CGRectMake(0, 0, size.width, size.height), 0, true));
CGContextDrawPDFPage(context, page);
UIImage *image = UIGraphicsGetImageFromCurrentImageContext();

In practice, I converted the repository of playing card graphics into a 52 page PDF document (one per card), and convert them to images in a single batch. It isn't particularly fast, but it was still faster than the competing SVG libraries. As long as you cache the UIImage you generate, it is more than fast enough, and much easier (and much smaller) than generating 4 or 8 images per graphic given the proliferation of iOS device screen resolutions.

I hadn't seen any other people using this technique (PDF as a vector graphics file format for iOS), so I figured I would blog about it in case it is useful to other people.

I also open sourced the card rendering library in case it is useful to anyone else working on card games on iOS.

Fork/download ios-cards on GitHub.

Social Cookbook: an open source Open Graph app

2012-07-27T19:28:38Z

Last week, at Facebook's annual f8 conference in San Francisco, we released Open Graph along with the new Facebook Timeline. Open Graph is the biggest change to Facebook's Platform since it launched in 2007. If you missed the live stream of the conference, I highly recommend you check out the keynote.

At a recent Facebook Hackathon, I made a social cookbook app built on Open Graph to test all of our new products. I am open sourcing it in case it is useful for any of you to get started with the product. You can use the app at http://socialcookbook.me/, but the source code is probably more interesting than the app for most of you. It is available on Github.

Note that in this Developer Beta period, the app probably won't work properly (i.e., it won't add stuff to your Timeline yet). It will start working in its current form as soon as Timeline starts rolling out more broadly and Open Graph is open for business.

Here's what the app looks like:

When you add a new recipe or a friends' recipe to your cookbook, that activity also goes to your Facebook timeline:

Once you add a recipe to your cookbook, you can let your friends know you cooked the recipe with the click of a button - and that, of course, also is reflected on your timeline.

In the Facebook developer app, I configured those Open Graph actions (I use "clip" for adding a recipe to your cookbook) and the "recipe" object type:

I configured three different aggregations for people's timelines: Cooked Recipes (a reverse chronological list of recipes I've cooked), Most Cooked Recipe (an "item" layout style with the recipe you cooked most often that month or year), and My Recipes (a grid of all the recipes you added that month).

I also support uploading photos, which are stored in Amazon S3 and served by Amazon CloudFront.

The bulk of the code is in cookbook.py. The service is built with Tornado for obvious reasons :)

Hope this helps you get started with Open Graph.

Web Sockets in Tornado

2012-07-27T19:29:17Z

I have been playing around with HTML 5 Web Sockets for a personal project. The Web Sockets API enables web browsers to maintain a bi-directional communication channel to a server, which in turn makes implementing real-time web sites about 1000% easier than it is today.

Currently, the only reasonable technical facility available to browsers to communicate to web servers is XMLHttpRequest. Sites that update in real-time like FriendFeed use a number of horrible hacks on top of XMLHttpRequest like long-polling to get data in real-time. (If you are interested, Tornado ships with a chat demo application that uses this long-polling technique - here is the JavaScript in all its hacky glory).

Web Sockets support a much simpler interface that enables both the client and the server send messages to each other asynchronously:

var ws = new WebSocket("ws://friendfeed.com/websocket");
ws.onopen = function() {
    ws.send("This is a message from the browser to the server");
};
ws.onmessage = function(event) {
    alert("The server sent a message: " + event.data);
};

Google Chrome just added support for Web Sockets, and most major browsers will deploy Web Socket support in their next major release. Chrome's release inspired me to play around with the protocol, which is extremely compatible with the design and goals of the Tornado web server we released a few months ago.

I implemented a Web Socket module for Tornado. Here is an example handler that echos back every message the client sends:

class EchoWebSocket(tornado.websocket.WebSocketHandler):
    def open(self):
        self.receive_message(self.on_message)

    def on_message(self, message):
       self.write_message(u"You said: " + message)

You map WebSocketHandlers to URLs the same as all of your other handlers in your application. However, since the Web Socket protocol is message-based and not really related to HTTP, all of the standard Tornado read and write methods have been replaced with the two methods send_message() and receive_message().

You can download the module on Github. Let me know if you encounter any issues if you start using it.

With this Tornado module, Web Sockets listen on the same host and port as all of your other request handlers. Once the initial HTTP connection is made, the connection protocol "switches" (or "upgrades" in the language of the Web Socket spec) from HTTP to the Web Socket protocol. I am not sure how most load balancers or proxies would respond to connections like this (most would probably close the connection or puke on the response). I plan on playing around a bit with nginx this weekend, but if you have had any anecdotal experience getting Web Sockets working with production load balancers, I would love to hear about it in the comments.

OAuth WRAP support in FriendFeed for feedback

2012-07-27T19:29:50Z

As David Recordon mentioned on the Facebook Developer Blog, the Facebook Platform team is working to move Facebook Connect over to OAuth over the next year. As a part of that effort, we have been working with Google, Microsoft, Yahoo!, and a number of other engineers on the OAuth WRAP standard, which aims to be much simpler to implement than the existing OAuth standard.

As a part of this effort, I implemented OAuth WRAP support in FriendFeed so we could have a live implementation of the standard to play with. I am really interested in getting feedback about the standard from developers who are currently using OAuth or Facebook Connect or both. If you have never used WRAP before, try it out, and let me know what you think (the comments on this post are a great forum, or feel free to send feedback to the OAuth WRAP mailing list).

To get started:

Register your application on FriendFeed to get an OAuth consumer key and consumer secret
Read the OAuth WRAP specification and check out the Google AppEngine example application that implements WRAP
Try implementing WRAP! The FriendFeed Authorize URL is https://friendfeed.com/account/wrap/authorize, and the Access Token URL is https://friendfeed.com/account/wrap/access_token

The FriendFeed WRAP implementation does not support refreshing tokens; the tokens never expire.

An overview of OAuth WRAP

The main difference between OAuth and OAuth WRAP is that WRAP does not have elaborate token exchanges or signature schemes. Instead, all server-to-server WRAP calls happen via SSL. The "access token," which grants your client the ability to make API calls on a user's behalf, is protected by SSL rather than by a shared secret and signature scheme.

The browser-based authorization experience looks exactly the same to an end user. First, you redirect the user to the Authorize URL (https://friendfeed.com/account/wrap/authorize) with your Consumer Key and callback URL. After the user authorizes, the server redirects the user back to your callback URL with a verification code. You call the Access Token URL (https://friendfeed.com/account/wrap/access_token) with that verification code to get back the Access Token.

After that, you simply need to make all your API calls via HTTPS, and you include the Access Token in the URL or in an HTTP header. There are no signatures, and no additional token exchanges necessary. Your API calls will look like https://friendfeed-api.com/v2/feed/home?wrap_access_token=....

My initial experience with WRAP

It was really easy to implement OAuth WRAP support in FriendFeed. I was able to implement WRAP on top of our existing support for OAuth, using the same tokens for both. As a consequence, our existing user interfaces for revoking applications work whether an app is using OAuth or OAuth WRAP. If we hadn't implemented OAuth support, OAuth WRAP would have been much easier to implement on its own because it is stateless; the verification code / access token exchange is so much simpler than the OAuth token exchange protocol.

On the client side, it was also much easier because of the lack of signatures (HTTPS calls are just as easy as HTTP with most HTTP client libraries). Using HTTPS for all requests seemed a bit weird at first, but in practice I realized I was simply moving signature calculation one level lower in the stack. I am curious how you all feel about it when you try the API out.

My tech talk on Tornado (video and slides)

2012-07-27T19:30:21Z

I gave a tech talk on Tornado yesterday evening at Facebook's offices. My slides and a video of the talk are below. If you have any questions, feel free to comment below, or join the Tornado discussion group to chat with other Tornado developers.

The technology behind Tornado, FriendFeed's web server

2012-07-27T19:31:44Z

Today, we are open sourcing the non-blocking web server and the tools that power FriendFeed under the name Tornado Web Server. We are really excited to open source this project as a part of Facebook's open source initiative, and we hope it will be useful to others building real-time web services. Check out the announcement on the Facebook Developer Blog. You can download Tornado at tornadoweb.org.

Background

While there are a number of great Python frameworks available that have been growing in popularity over the past couple years (particularly Django), our performance and feature requirements consistently diverged from these mainstream frameworks. In particular, as we introduced more real-time features to FriendFeed, we needed the support for a large number of standing connections afforded by the non-blocking I/O programming style and epoll.

We ended up writing our own web server and framework after looking at existing servers and tools like Twisted because none matched both our performance requirements and our ease-of-use requirements.

Tornado looks a bit like web.py or Google's webapp, but with additional tools and optimizations to take advantage of the non-blocking web server and tools. Some of the distinctive features of Tornado:

All the basic site building blocks - Tornado comes with built-in support for a lot of the most difficult and tedious aspects of web development, including templates, signed cookies, user authentication, localization, aggressive static file caching, cross-site request forgery protection, and third party authentication like Facebook Connect. You only need to use the features you want, and it is easy to mix and match Tornado with other frameworks.
Real-time services - Tornado supports large numbers of concurrent connections. It is easy to write real-time services via long polling or HTTP streaming with Tornado. Every active user of FriendFeed maintains an open connection to FriendFeed's servers.
High performance - Tornado is pretty fast relative to most Python web frameworks. We ran some simple load tests against some other popular Python frameworks, and Tornado's baseline throughput was over four times higher than the other frameworks:

Basic usage

The main Tornado module is tornado.web, which implements a lightweight web development framework. tornado.web is built on our non-blocking HTTP server and low-level I/O modules. Here is "Hello, world" in Tornado:

import tornado.httpserver
import tornado.ioloop
import tornado.web

class MainHandler(tornado.web.RequestHandler):
    def get(self):
        self.write("Hello, world")

application = tornado.web.Application([
    (r"/", MainHandler),
])

if __name__ == "__main__":
    http_server = tornado.httpserver.HTTPServer(application)
    http_server.listen(8888)
    tornado.ioloop.IOLoop.instance().start()

A Tornado web application maps URLs or URL patterns to subclasses of tornado.web.RequestHandler. Those classes define get() or post() methods to handle HTTP GET or POST requests to that URL. The example above maps the root URL '/' to the MainHandler class, which prints the "Hello, world" message.

All of the additional features of Tornado mentioned above (like localization and signed cookies) are designed to be used on an à la carte basis. For example, to use signed cookies in your application, you just need to specify the secret cookie signing key when you create your application:

application = tornado.web.Application([
    (r"/", MainHandler),
], cookie_secret="61oETzKXQAGaYdkL5gEmGeJJFuYh7EQnp2XdTP1o/Vo=")

and then you can call set_secure_cookie() and get_secure_cookie() in your request handlers:

class LoginHandler(tornado.web.RequestHandler):
    def post(self):
        # Process login username and password
        self.set_secure_cookie("user_id", user["id"])
        self.redirect("/home")

You can find detailed documentation for all of these features at tornadoweb.org/documentation. A few of my favorite features are discussed in greater detail below.

Asynchronous requests

Tornado assumes requests are not asynchronous to make writing simple request handlers easy. By default, when a request handler is executed, Tornado will finish/close the request automatically.

You can override that default behavior to implement streaming or hanging connections, which are common for real-time services like FriendFeed. If you want a request to remain open after the main request handler method, you simply need to use the tornado.web.asynchronous decorator:

class MainHandler(tornado.web.RequestHandler):
    @tornado.web.asynchronous
    def get(self):
        self.write("Hello, world")
        self.finish()

When you use this decorator, it is your responsibility to call self.finish() to finish the HTTP request, or the user's browser will simply hang.

Here is a real example that makes a call to the FriendFeed API using Tornado's built-in asynchronous HTTP client:

class MainHandler(tornado.web.RequestHandler):
    @tornado.web.asynchronous
    def get(self):
        http = tornado.httpclient.AsyncHTTPClient()
        http.fetch("http://friendfeed-api.com/v2/feed/bret",
                   callback=self.async_callback(self.on_response))

    def on_response(self, response):
        if response.error: raise tornado.web.HTTPError(500)
        json = tornado.escape.json_decode(response.body)
        self.write("Fetched " + str(len(json["entries"])) + " entries "
                   "from the FriendFeed API")
        self.finish()

When get() returns, the request has not finished. When the HTTP client eventually calls on_response(), the request is still open, and the response is finally flushed to the client with the call to self.finish().

For a more advanced asynchronous example, take a look at the chat demo application included with Tornado. The chat demo uses AJAX and long polling to implement a remedial real-time chat room on Tornado. You can also see the chat demo in action on FriendFeed's servers.

Third-party authentication

Tornado comes with built-in support for authenticating with Facebook Connect, Twitter, Google, and FriendFeed in addition to OAuth and OpenID. To log a user in via Facebook Connect, you just need to implement a request handler like:

class LoginHandler(tornado.web.RequestHandler, tornado.auth.FacebookMixin):
    @tornado.web.asynchronous
    def get(self):
        if self.get_argument("session", None):
            self.get_authenticated_user(self.async_callback(self._on_auth))
            return
        self.authenticate_redirect()

    def _on_auth(self, user):
        if not user: raise tornado.web.HTTPError(500, "Auth failed")
        self.set_secure_cookie("uid", user["uid"])
        self.set_secure_cookie("session_key", user["session_key"])
        self.redirect("/home")

All of the authentication methods support a relatively uniform interface so you don't need to understand all of the intricacies of the different authentication/authorization protocols to leverage them on your site.

See the auth and facebook demo applications included with Tornado for detailed examples of third party authentication.

And more...

Check out the Tornado documentation for a complete list of features and modules.

You can discuss the project, send feedback, and report bugs in our mailing list on Google Groups.

How FriendFeed uses MySQL to store schema-less data

2012-07-27T19:32:30Z

Background

We use MySQL for storing all of the data in FriendFeed. Our database has grown a lot as our user base has grown. We now store over 250 million entries and a bunch of other data, from comments and "likes" to friend lists.

As our database has grown, we have tried to iteratively deal with the scaling issues that come with rapid growth. We did the typical things, like using read slaves and memcache to increase read throughput and sharding our database to improve write throughput. However, as we grew, scaling our existing features to accomodate more traffic turned out to be much less of an issue than adding new features.

In particular, making schema changes or adding indexes to a database with more than 10 - 20 million rows completely locks the database for hours at a time. Removing old indexes takes just as much time, and not removing them hurts performance because the database will continue to read and write to those unused blocks on every INSERT, pushing important blocks out of memory. There are complex operational procedures you can do to circumvent these problems (like setting up the new index on a slave, and then swapping the slave and the master), but those procedures are so error prone and heavyweight, they implicitly discouraged our adding features that would require schema/index changes. Since our databases are all heavily sharded, the relational features of MySQL like JOIN have never been useful to us, so we decided to look outside of the realm of RDBMS.

Lots of projects exist designed to tackle the problem storing data with flexible schemas and building new indexes on the fly (e.g., CouchDB). However, none of them seemed widely-used enough by large sites to inspire confidence. In the tests we read about and ran ourselves, none of the projects were stable or battle-tested enough for our needs (see this somewhat outdated article on CouchDB, for example). MySQL works. It doesn't corrupt data. Replication works. We understand its limitations already. We like MySQL for storage, just not RDBMS usage patterns.

After some deliberation, we decided to implement a "schema-less" storage system on top of MySQL rather than use a completely new storage system. This post attempts to describe the high-level details of the system. We are curious how other large sites have tackled these problems, and we thought some of the design work we have done might be useful to other developers.

Overview

Our datastore stores schema-less bags of properties (e.g., JSON objects or Python dictionaries). The only required property of stored entities is id, a 16-byte UUID. The rest of the entity is opaque as far as the datastore is concerned. We can change the "schema" simply by storing new properties.

We index data in these entities by storing indexes in separate MySQL tables. If we want to index three properties in each entity, we will have three MySQL tables - one for each index. If we want to stop using an index, we stop writing to that table from our code and, optionally, drop the table from MySQL. If we want a new index, we make a new MySQL table for that index and run a process to asynchronously populate the index without disrupting our live service.

As a result, we end up having more tables than we had before, but adding and removing indexes is easy. We have heavily optimized the process that populates new indexes (which we call "The Cleaner") so that it fills new indexes rapidly without disrupting the site. We can store new properties and index them in a day's time rather than a week's time, and we don't need to swap MySQL masters and slaves or do any other scary operational work to make it happen.

Details

In MySQL, our entities are stored in a table that looks like this:

CREATE TABLE entities (
    added_id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
    id BINARY(16) NOT NULL,
    updated TIMESTAMP NOT NULL,
    body MEDIUMBLOB,
    UNIQUE KEY (id),
    KEY (updated)
) ENGINE=InnoDB;

The added_id column is present because InnoDB stores data rows physically in primary key order. The AUTO_INCREMENT primary key ensures new entities are written sequentially on disk after old entities, which helps for both read and write locality (new entities tend to be read more frequently than old entities since FriendFeed pages are ordered reverse-chronologically). Entity bodies are stored as zlib-compressed, pickled Python dictionaries.

Indexes are stored in separate tables. To create a new index, we create a new table storing the attributes we want to index on all of our database shards. For example, a typical entity in FriendFeed might look like this:

{
    "id": "71f0c4d2291844cca2df6f486e96e37c",
    "user_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
    "feed_id": "f48b0440ca0c4f66991c4d5f6a078eaf",
    "title": "We just launched a new backend system for FriendFeed!",
    "link": "http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
    "published": 1235697046,
    "updated": 1235697046,
}

We want to index the user_id attribute of these entities so we can render a page of all the entities a given user has posted. Our index table looks like this:

CREATE TABLE index_user_id (
    user_id BINARY(16) NOT NULL,
    entity_id BINARY(16) NOT NULL UNIQUE,
    PRIMARY KEY (user_id, entity_id)
) ENGINE=InnoDB;

Our datastore automatically maintains indexes on your behalf, so to start an instance of our datastore that stores entities like the structure above with the given indexes, you would write (in Python):

user_id_index = friendfeed.datastore.Index(
    table="index_user_id", properties=["user_id"], shard_on="user_id")
datastore = friendfeed.datastore.DataStore(
    mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
    indexes=[user_id_index])

new_entity = {
    "id": binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"),
    "user_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
    "feed_id": binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"),
    "title": u"We just launched a new backend system for FriendFeed!",
    "link": u"http://friendfeed.com/e/71f0c4d2-2918-44cc-a2df-6f486e96e37c",
    "published": 1235697046,
    "updated": 1235697046,
}
datastore.put(new_entity)
entity = datastore.get(binascii.a2b_hex("71f0c4d2291844cca2df6f486e96e37c"))
entity = user_id_index.get_all(datastore, user_id=binascii.a2b_hex("f48b0440ca0c4f66991c4d5f6a078eaf"))

The Index class above looks for the user_id property in all entities and automatically maintains the index in the index_user_id table. Since our database is sharded, the shard_on argument is used to determine which shard the index gets stored on (in this case, entity["user_id"] % num_shards).

You can query an index using the index instance (see user_id_index.get_all above). The datastore code does the "join" between the index_user_id table and the entities table in Python, by first querying the index_user_id tables on all database shards to get a list of entity IDs and then fetching those entity IDs from the entities table.

To add a new index, e.g., on the link property, we would create a new table:

CREATE TABLE index_link (
    link VARCHAR(735) NOT NULL,
    entity_id BINARY(16) NOT NULL UNIQUE,
    PRIMARY KEY (link, entity_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

We would change our datastore initialization code to include this new index:

user_id_index = friendfeed.datastore.Index(
    table="index_user_id", properties=["user_id"], shard_on="user_id")
link_index = friendfeed.datastore.Index(
    table="index_link", properties=["link"], shard_on="link")
datastore = friendfeed.datastore.DataStore(
    mysql_shards=["127.0.0.1:3306", "127.0.0.1:3307"],
    indexes=[user_id_index, link_index])

And we could populate the index asynchronously (even while serving live traffic) with:

./rundatastorecleaner.py --index=index_link

Consistency and Atomicity

Since our database is sharded, and indexes for an entity can be stored on different shards than the entities themselves, consistency is an issue. What if the process crashes before it has written to all the index tables?

Building a transaction protocol was appealing to the most ambitious of FriendFeed engineers, but we wanted to keep the system as simple as possible. We decided to loosen constraints such that:

The property bag stored in the main entities table is canonical
Indexes may not reflect the actual entity values

Consequently, we write a new entity to the database with the following steps:

Write the entity to the entities table, using the ACID properties of InnoDB
Write the indexes to all of the index tables on all of the shards

When we read from the index tables, we know they may not be accurate (i.e., they may reflect old property values if writing has not finished step 2). To ensure we don't return invalid entities based on the constraints above, we use the index tables to determine which entities to read, but we re-apply the query filters on the entities themselves rather than trusting the integrity of the indexes:

Read the entity_id from all of the index tables based on the query
Read the entities from the entities table from the given entity IDs
Filter (in Python) all of the entities that do not match the query conditions based on the actual property values

To ensure that indexes are not missing perpetually and inconsistencies are eventually fixed, the "Cleaner" process I mentioned above runs continously over the entities table, writing missing indexes and cleaning up old and invalid indexes. It cleans recently updated entities first, so inconsistencies in the indexes get fixed fairly quickly (within a couple of seconds) in practice.

Performance

We have optimized our primary indexes quite a bit in this new system, and we are quite pleased with the results. Here is a graph of FriendFeed page view latency for the past month (we launched the new backend a couple of days ago, as you can tell by the dramatic drop):

In particular, the latency of our system is now remarkably stable, even during peak mid-day hours. Here is a graph of FriendFeed page view latency for the past 24 hours:

Compare this to one week ago:

The system has been really easy to work with so far. We have already changed the indexes a couple of times since we deployed the system, and we have started converting some of our biggest MySQL tables to use this new scheme so we can change their structure more liberally going forward.

My FriendFeed presentation from MIT/Stanford Venture Lab

2012-07-27T19:33:22Z

Last week, I gave a short presentation about FriendFeed before a panel at the MIT/Stanford Venture Lab. The panel, entitled "Lifestreaming: The Real-time Web," included me, Loic Le Meur (Seesmic), Leah Culver (Pownce), and Jeff Clavier (SoftTechVC), and it was moderated by Kara Swisher.

After Louis Gray's writeup of my presentation and Kara Swisher's video made the rounds on FriendFeed, I have gotten a number of requests for my slides. I uploaded my presentation to Scribd, and it is embedded below.

The slides that got the most attention were about FriendFeed's traffic. FriendFeed has stored over 100 million entries shared by FriendFeed users. Getting to that point was a bit rocky. This slide shows FriendFeed's traffic growth in its first four months:

FriendFeed launched in private beta a little less than a year ago with a great article in the New York Times, but, like most start-ups, that initial attention dropped quickly. By the end of our fourth month, our traffic levels had just creeped up to the levels we had at launch. Needless to say, it was a tough and emotional time for all of us at FriendFeed as we grappled with the product, marketing, and PR issues that may have been contributing to our stagnant growth.

That growth curve quickly changed over the rest of the year. Here is FriendFeed's traffic until August or so (I highlighted the time period from the previous graph):

Those first four months don't even register on the y-axis we have grown so much since. So what happened around March? Diagnosing success and failure is a favorite past time of many in Silicon Valley, and I expect this blog post will inspire an analysis or two. I included a few of our theories in the slides. Among the features that have contributed to our growth:

Public launch - We launched out of private beta in late February, opening sign-ups and getting a brief surge of press.
Timing - Life-streaming, open forms of social networking, and the "real-time web" became popular trends around that time period with the growing popularity of Twitter, FriendFeed, and others. FriendFeed certainly benefited (both in terms of PR and user adoption) from the increased attention on the space.
Developer API - We launched the FriendFeed API in that time period, which inspired a wide range of desktop and mobile applications. Some, like Twhirl, had established user-bases, and the addition of FriendFeed support made using FriendFeed seamless for a large number of new users.
Speed and reliability - We have focused quite a bit on making FriendFeed fast, responsive, and reliable. Many of our users started using the site because it is faster and more reliable than sites that serve similar functions.
The press uses FriendFeed - Since FriendFeed is about content discovery, it has been fairly widely adopted by content producers, from bloggers to professional journalists. We have tried to make the product work well for this unique (but important) subset of our users. As a consequence, I think FriendFeed has gotten more press than many other products of its size.
FriendFeed Rooms - We launched FriendFeed Rooms to make it easier for groups like classes, conference attendees, and companies to adopt FriendFeed. Since then, it has been adopted for an incredibly wide range of uses, from Life Science discussions to Live-blogging the Apple WWDC, and many of our users have joined to participate in a particular Room.

Whatever the specific reasons, this growth timeline is not atypical for new web services. Check out this interesting post about Weebly's growth from David Rusenko, for example. As David put it, "If you give up within a month or two, your product definitely won't be successful."

I also think growth comes in stages, and our company has significant challenges ahead of us as our product and user base evolves to become more mainstream. I know there are other great blog posts about this topic from entrepreneurs — if you know of any good articles, I'd love to see links in the comments.

We need a Wikipedia for data

2012-07-27T19:34:03Z

I just started blogging. I am not sure what I want to write about, but I think one theme will be "things I want but want someone else to build." This article describes one of those things.

At Google, I worked on a number of projects that required data from third party data sources. We licensed mapping data for 100s of countries for Google Maps, movie showtimes data for Google Movies, and stock data for Google Finance, among many others.

After leaving Google and the company of the Google BizDev team, I have come to realize how hard it is for a everyday programmer to get access to even the most basic factual data. If you want to experiment with a new driving directions algorithm, it is infinitely more difficult than coming up with an algorithm; you have to hire a lawyer and a sign a contract with a company that collects that data in the country you are developing for. If you want to write an open source TiVo competitor, you need television listings data for every cable provider in the country, but your options are tenuous at best. In July, the most popular "free" listings service shut down their site, breaking most MythTV installations. The CD database (which is used to recognize CD track names when you rip CDs on your computer) has gone through a number of controversial transitions and license changes for similar reasons.

Even when data is available under a reasonable license, it often suffers from extremely serious quality or discoverability problems. The US Census Bureau publishes map data, but it only includes a small subset of the attributes required for a real mapping product. The Reuters corpus, which is a standard body of text used in data mining and information retrieval research, requires you to sign two agreements, send them to some organization via snail mail, and get the corpus via snail mail on CDs (what century is this, folks?).

I think all of these barriers to data are holding back innovation at a scale that few people realize. The most important part of an environment that encourages innovation is low barriers to entry. The moment a contract and lawyers are involved, you inherently restrict the set of people who can work on a problem to well-funded companies with a profitable product. Likewise, companies that sell data have to protect their investments, so permitted uses for the data are almost always explicitly enumerated in contracts. The entire system is designed to restrict the data to be used in product categories that already exist.

Imagine what amazing applications would be created if every programmer in the world had free access to all of these data sets:

Map data for all countries in a relatively uniform data format
White pages data (names and addresses) for all cities of the world
Stock data for all major exchanges for all time
Movie showtimes data for all cities in the world
Television schedule data for all cities in the world
Sports scores and stats for all sports in the world for all time
Rich meta data for all musical albums and movies from all labels for all time

The interesting thing is, almost every internet company would benefit if this data were freely available. Most internet companies have embraced open source operating systems because every company needs an operating system, and no company wants their OS to be a competitive advantage - they just want it to work. I would argue we are all in the same boat with these factual data sources. No one really wants factual data accuracy and completeness to be their competitive advantage; we all want the best data possible to build the best products possible, and discrepancies in data quality are artifacts of the extremely inefficient economy of buying and selling data we currently live in. If everyone had the same, high quality data, all of our products would be better for it.

To this end, I think we should create a Wikipedia for data: a global database for all of these important data sources to which we all contribute and that anyone can use. When a user reports an inaccurate phone number in your products, save it back to the DataWiki so everyone can benefit, and in return, you get everyone else's improvements as well. If your local movie theater doesn't have listings data in DataWiki, you can type it in yourself, and everyone in your town can benefit, and all the products you use that access movie listings will automatically update. Need better mapping data for a city? Pay to collect it, and upload it to the DataWiki. In return you get all the other cities other companies paid for (sort of like a company contributing device drivers to the Linux kernel).

DataWiki seems like an extremely hard problem, and I don't think it would work unless some big companies got on board and donated their data sets to bootstrap the process. However, I think all companies would benefit almost immediately from the quality improvements that would come from openness. Some data sets are more expensive to collect than others, and those certainly seem like the hardest data sets to make freely available.

I have some concrete ideas on how this could work for some data sets, but I will save them for future posts. In the meantime, what are some of the most interesting existing projects attempting to open up these data sources? I only know of a few, and none of them has really taken off.

Update: Check out this great summary of the sites people have mentioned in the comments on ReadWriteWeb.

Experimenting with Google App Engine

2012-07-27T19:34:36Z

Google App Engine was actually the last project I worked on before I left Google. I was the PM of the project when it started, but has grown quite a bit since I left Google last June, and now it is has many more engineers and a handful of extremely talented PMs. I was fortunate enough to be able to see Kevin Gibbs and crew at Campfire One yesterday, and I could barely sit through the whole talk I was so excited to play around with the system.

I have been "meaning to" start a blog for months. Blog software is extremely simple to implement, so I figured it would be a great app to test out on the new App Engine infrastructure. This blog runs on the code I wrote this evening.

The lack of SQL is actually refreshing. Like Django and many other frameworks, you declare your data types in Python:

class Entry(db.Model):
    author = db.UserProperty()
    title = db.StringProperty(required=True)
    slug = db.StringProperty(required=True)
    body = db.TextProperty(required=True)
    published = db.DateTimeProperty(auto_now_add=True)
    updated = db.DateTimeProperty(auto_now=True)

I used a web framework we use at FriendFeed. It looks a lot like the webapp framework that ships with App Engine and web.py (which inspired both of them). It took virtually no effort to get it to work in App Engine thanks to App Engine's support for WSGI.

Running the application looks a lot like the App Engine examples:

application = web.WSGIApplication([
    (r"/", MainPageHandler),
    (r"/index", IndexHandler),
    (r"/feed", FeedHandler),
    (r"/entry/([^/]+)", EntryHandler),
])
wsgiref.handlers.CGIHandler().run(application)

Generating the front page is totally easy:

class MainPageHandler(web.RequestHandler):
    def get(self):
        entries = db.Query(Entry).order('-published').fetch(limit=5)
        self.render("main.html", entries=entries)

Generating the Atom feed is equally easy:

class FeedHandler(web.RequestHandler):
    def get(self):
        entries = db.Query(Entry).order('-published').fetch(limit=10)
        self.set_header("Content-Type", "application/atom+xml")
        self.render("atom.xml", entries=entries)

I wanted to use slugs in my URLs to entries to make them friendlier, so I had to do a query to lookup entries for entry URLs:

class EntryHandler(web.RequestHandler):
    def get(self, slug):
        entry = db.Query(Entry).filter("slug =", slug).get()
        if not entry:
            raise web.HTTPError(404)
        self.render("entry.html", entry=entry)

I also needed security for adding/editing blog entries. App Engine lets you use Google's account system, which is nice for small apps like this. Likewise, it knows which users are "admins" for the app, so I decided to use this built-in role to handle security for the blog: only admins can add/edit entries. First, I wrote a decorator that will automatically add admin security to any RequestHandler method (redirecting to the login page if the user is not logged in):

def administrator(method):
    @functools.wraps(method)
    def wrapper(self, *args, **kwargs):
        user = users.get_current_user()
        if not user:
            if self.request.method == "GET":
                self.redirect(users.create_login_url(self.request.uri))
                return
            raise web.HTTPError(403)
        elif not users.is_current_user_admin():
            raise web.HTTPError(403)
        else:
            return method(self, *args, **kwargs)
    return wrapper

My edit handler looks like this:

class NewEntryHandler(web.RequestHandler):
    @administrator
    def get(self):
        self.render("new.html")

    @administrator
    def post(self):
        entry = Entry(
            author=users.get_current_user(),
            title=self.get_argument("title"),
            slug=self.get_argument("slug"),
            body=self.get_argument("body"),
        )
        entry.put(entry)
        self.redirect("/entries/" + entry.slug)

I don't think this blog will ever get millions of page views, but it is pretty cool that it could in theory :) I didn't have to configure anything. I didn't need to make an account system to make an administrative section of the site. And the entire blog is less than 100 lines of code. I deployed by running a script, and I was done. No machines, no "apt-get install", no "sudo /etc/init.d/whatever restart", nothing.

I am impressed. The App Engine team has done a fantastic job, and I think they have already changed the way I do hobby projects.

The next logical question is: would I run a real business on infrastructure that is so different than everyone else's? If I change my mind about App Engine, what are my options? I am hoping a number of open source projects spring up as alternatives to lower the switching costs over the next year. I will be very interested to see how many startups take the leap and run on App Engine entirely in the meantime.