Getting started with Mechanical Turk for data cleanup

In the months leading to the launch of Redfin Open Book, we embarked in an ambitious data cleanup project. We had 7,500+ free-form text fields from which we needed to extract structured vendor information. We ended up with 3,000+ cleaned database records. In this post I’ll walk you through how we used MTurk, and share the lessons I learned from using it.

The source data

These free-form text fields were notes taken by folks in the field about the various vendors they worked with in client transactions. As with any free-form text fields, the content was about as unique as the person entering it. Some of these notes were fairly suitable for computer processing, containing information in a similar format as below:

Jane Doe
ABC Company
(206) 555-5555
123 Main St, #75
Seattle, WA

The challenge was that they frequently included “notes to self” about the vendor, like “Jane will be at the client’s on 4/15” or “Quoted 675 to the client”, etc. Variations in order were also frequent.

A dead end

Having a software engineering background (and reminiscing about my year-long school project on Natural Language Processing) the first approach I attempted was automated tools for extracting and structuring the data.

I spent a couple of days brushing up on text mining tools, and I found the most suitable to be RapidMiner (great tool, hopefully will do a write-up later).

However, I realized I wouldn’t be able to extract much more than emails and phone numbers without a significant investment in coding.

Tapping the collective: getting started with MTurk

I had researched MTurk in the past and was somewhat familiar with the premise of the service. However, I had never used it beyond small trial jobs.

I won’t go into detail about how it works — that’s what the documentation is for. Here are some basic concepts that should get you up-and-running with little prior experience:

• At the core of MTurk there’s the concept of a “HIT” or human intelligence task, which is the unit of work you’ll request from your workers
• When defining a HIT, you need to think of:
  • A set of input variables (what data will you provide?)
  • A set of output variables (what data you want to extract?)
  • The layout the workers will see
• You get to define the job parameters in the HIT Template, these include qualifications you’ll ask for the workers, how much will you pay per HIT and how many times you want each HIT to be completed (you want at least 2, more on this below)
• You publish HITs in “batches”. There is a command-line interface, an API or you can simply upload .CSV files. I used the latter.

Step-by-step guide

Here are the key steps. For brevity I skipped some steps that are self-explanatory (like funding your account, etc.)

1. Create your account, if you don’t already have one at https://requester.mturk.com/
2. Click on the “Design” tab, and select any category
3. From the list of templates presented, select the “Data Correction” template, as it has a few examples on how to work with input/output fields
4. Create a title for the HIT, be descriptive of what’s required from the worker. Besides the reward per HIT, this is the information that workers will use to make a decision on whether they work on your HIT or not. Here’s what I used: ”You will see a small paragraph of text that contains contact information about a vendor and you’ll split it into separate fields (name, address, phone, etc)”
5. Update any parameters you’d like. I changed the rewards per assignment (started paying 8c) and the number of assignments to 2 per HIT
6. Click on the layout, and using HTML form syntax you will be able to define the input and output parameters
   • Input parameters are strings of the form ${Parameter}. In my case I had two inputs: The free-form text field, and a unique ID that I could join back to our database records
   • Output parameters will be the names that you give to the form elements (INPUT, TEXTAREA, etc) that appear in your design layout. In my case they were: First Name, Last Name, Phone, Address, etc.
7. After saving, you’re ready to load your first batch. Go to the “Publish” tab
8. Click the “Download” link to the right of the “Upload” button. You will receive a .CSV file with a column for each input.
9. Make your data match that .CSV format, you filling out the input parameters. I did some pre-processing on Excel to discard rows that weren’t worth processing (e.g. empty or single word notes), and I replaced newlines with “/” characters using Excel’s SUBSTITUTE function
10. Upload an initial file with a small sample of your data (100 or less)
11. Go to “Manage” and in a few minutes you should be able to download a .CSV with the results
12. The results .CSV has tons of columns, but starting on column AA you will see a column for each input and each output (in alphabetical order)
13. If you chose two assignments per HIT, you will see two rows of output for each row you submitted
14. For post-processing, I highly recommend Excel. Here’s an example spreadsheet I used. Columns AA & AB are the data shown to the workers, columns AZ through AP is the results from the HITs (two rows per HIT). Columns AS through BH are for comparing content and using conditional formatting to highlight the fields where there were discrepancies between the two outputs from the same HIT
15. Fixing discrepancies can be labor-intensive, using simple Excel macros can be of great help. An alternative that occurred to me was to feed the discrepancies back into MTurk to identify the correct output. I ended up not pursuing it since I could enroll the help of some folks at work to give me a hand. Let me know if you try this alternative!
16. After all discrepancies are resolved, voilà! you have structured data you can upload to your database
17. Make any updates necessary to the design template and publish subsequent batches to process the rest of your data

Tips and Tricks

• The one tip to remember: Run small batches first to see if there’s a pattern in the discrepancies you’re getting. Go back to your layout design and address those by being specific about what you want from the workers. Using this iterative approach I reduced the error rate from 11% to 4%
• Less ambiguity yields better results. Initially I only asked for “First Name” & “Last Name”, but I saw differences on how cases like “Arthur C. Clarke” were handled. I decided to add a “Middle Name” column, and discrepancies in name dropped from 8% to under 2%. Similar improvement applied to Address when I added “Suite #” as a separate field to extract.
• Be clear on the format you expect on the extracted data. Phones had a high discrepancy rate until I requested the phone numbers to be in the 888-888-8888 format
• The more specific you are (i.e. more columns) the *faster* the workers get through your HITs. That’s because you’re leaving out the guesswork about how you want the data entered. The hourly rate dropped from $4.20 for the first batches to $2.40 for the last batch, which had five additional columns.
• When you see an odd pattern of errors (in my case it was First/Last name swapped), take a look at the worker ID. Some workers were making the same error over and over again, so I was able to quickly fix the errors when I filtered by that worker
• Reject the HITs where the worker clearly didn’t follow instructions. You will be able to request a minimum HIT success rate in future batches, and you’re helping future requesters.

JSON in Postgres

Since Dec 2011 we’ve been storing a small portion of our data as JSON in Postgres.  This blog post gives a quick overview of why we decided to do this, how it works, and what we’ve learned so far.

Why JSON in Postgres?

Redfin’s basic stack includes a Java-based web app on top of a relational database.  We started with MySQL and switched to Postgres a few years ago.

Overall we’re happy with a relational DB, but it does have its pain points.  Perhaps the biggest issue is the difficulty involved in changing schema.  To change the shape of a table Postgres must take a table lock, which means that nobody can read or write to the table while the schema change is happening.  Some schema changes take little time to process (e.g. if the table is small or you’re adding a nullable column).  But some schema changes can take a while to process, which translates to a lot of downtime. Various other people have written about this same problem before. To give just one example, here’s what the folks at FriendFeed had to say about it: http://backchannel.org/blog/friendfeed-schemaless-mysql

We had a situation where we wanted to store information about the various service providers in our new Open Book directory.  We expected to iterate on the data model, and we wanted this to be easy.  So we decided to follow a similar approach to the one used by the folks at FriendFeed: to store data in our relational DB but in a semi-structured fashion.

Aside: why not use a NoSQL store?  We considered this.  The main reason we decided against NoSQL (for now) is that it would require a lot more to deploy, monitor, and maintain.  Things that already work with our Postgres setup (backups, etc) would need to be setup anew.  Also, for this particular use-case we didn’t need the scale that NoSQL offers, and we were hesitant about some of the trade-offs that often come with NoSQL (limitations in transactional support, queries you can pose, etc.).

Postgres offers a few ways to manage semi-structured data:

• XML: http://www.postgresql.org/docs/9.1/static/datatype-xml.html
• Hashmap: http://www.postgresql.org/docs/9.1/static/hstore.html
• Array: http://www.postgresql.org/docs/9.1/static/arrays.html

We were hoping to use JSON because it’s more flexible than hashmaps or arrays, and because it’s familiar – we use it all the time.  Unfortunately, Postgres doesn’t (yet) offer built-in support for JSON.  It appears that one guy, Joey Addams, worked on adding JSON support to Postgres as a Google summer-of-code project back in 2010, but he didn’t quite finish at the time.  Looks like he may finish soon:  http://stackoverflow.com/questions/4995945/optimize-escape-json-in-postgresql-9-0/5448248#5448248.

In the meantime we developed our own strategy to store data as JSON in Postgres, to define indexes on facts inside the JSON, and to query it.

How does it Work?

Let’s take a hypothetical example – you want to store a bunch of products (televisions, shoes…).  They will have some common facts (price) and also some facts that are unique to each type of product (televisions have a resolution, shoes have a size).  You suspect that you’ll want to change the schema frequently, to add/modify both the common facts and the custom facts.

create table products (
   id    bigserial primary key,
   json  text
)

insert into products(json) values
   ('{"type":"television", "price": 899.99, "resolution":"1080p"}'),
   ('{"type":"shoe", "price": 74.99, "size":10.5}')
;

As far as Postgres is concerned, the json column is a plain-old text column.

Clearly you can fetch a product by ID:

select * from products where id=1;

But how do you query for products based on facts inside the JSON field?  Here’s how we do it:

select * from products
   where
   jsonGet(json, '$.type') = 'television'
   and jsonGet(json, '$.resolution') = '1080p';

What’s going on here?  We’re making use of a special function: jsonGet.  This is not a built-in function; it’s one we added to Postgres, a custom function. You can write custom Postgres functions in one of several procedural languages. We opted for Perl. Our function uses jsonpath, which is like XML path – it’s a simple language for identifying a portion of a JSON document.

What about performance?  If we do nothing special, these queries will be very inefficient – Postgres will be forced to do a table scan and evaluate the jsonGet function on each record.  The way to avoid table scans is to add the appropriate indexes.  Here’s how to add an index for all product prices:

create index products_price on products(jsonGet(json,'$.price'));

This is a functional index.  Whenever you create or update a record in the products table, Postgres will run the jsonGet function to extract the price fact from JSON and store just that fact inside the index.  If, later, you query by price using the same jsonGet function, Postgres will use the index and avoid the table scan.  In other words, you’re trading off some performance at create/update-time in order to achieve better performance at query-time.

As another example, here’s how to add an index for TV resolutions:

create index products_television_resolutions
   on products(jsonGet(json,'$.resolution'))
   where jsonGet(json,'$.type') = 'television';

This is a partial index.  Postgres will only store records in this index for products of type ‘television’.  Similarly, Postgres will use this index for queries that include both of the jsonGet filters – the one on type and the one on resolution.

So far I described how it works at the DB-level.  There’s more to say about how this works in our Java layer, but in the interest of brevity I’ll leave that discussion out of this blog post (if you’re interested, leave a note in the comments below).

So…does it Work?  Do we like it?

Yes, it does work!  We’ve been using this technique since December to track information about service providers in our Open Book directory.  The quantity of data is still modest (in the low 10’s of thousands of records) but we haven’t seen any major gotchas.

Is this a silver bullet?  No, I wouldn’t say that.  This strategy has pluses and minuses.

The biggest benefit is that schema changes are generally easier.  Changing the shape of our JSON data doesn’t feel like a big scary thing.  We follow the DRY principal – instead of defining the data model both in SQL and in Java, we define it just once, in Java.  It’s very easy to change the Java code to add a new field.  It’s also quick to change the Java code to modify or remove a field, but those changes are definitely trickier – our app code now needs to be smart enough to deal with records of various shapes, both old and new.

The JSON format gives us the freedom to collapse one-to-many relationships into a single record (denormalize).  This isn’t always a good thing to do, but where appropriate this strategy allows us to skip a join and achieve better performance.

Finally, this solution required less work than deploying a new unfamiliar NoSQL solution, and allowed us to maintain full transactional support.

The minuses are:

1. There’s still more infrastructure.  We had to deploy plperl, json, and jsonpath libraries to our DB servers.  It took some tinkering to figure this out (most recently, we ran into issues with plperl on Postgres 9.1 on Windows).

2. This is an unfamiliar technique.  Again, it’s not as radically different as a full-on transition to NoSQL, but it still takes more ramp-up time for other developers to figure out how to query using jsonpath.

3. This strategy doesn’t jive too well with our Java layer.  I didn’t talk much about our Java layer, but the short story is that we use hibernate.  I can’t say we love everything about hibernate, but it’s our standard, and it does make it easy to work with tables and relationships.  For example, if you have a customers table and a real_estate_agents table, then hibernate maps these records to Java objects and gives you a simple way to walk the relationship from one object to another: customer.getRealEstateAgent().  This just doesn’t work when you have rich data stored as JSON inside fat columns – hibernate doesn’t understand the make-up of these JSON columns.  So, you, the developer, are forced to crack open the JSON, find the ID of the related object, and query for it separately.  It’s all doable, but it leads to longer code.

What do you think?

Do you use a relational database? Have you struggled with schema changes? Have you tried storing semi-structued data in a relational DB? Did it work out? Or did you choose to switch to a non-relational store? We’re interested to know – please leave your thoughts in the comments below.

Source for jsonGet

In case it’s useful, here’s the source code of our jsonGet function:

create or replace function jsonGet(text,text) returns text as
$$
	my ($json_text,$json_path_text) = @_;

	use JSON;
	$json = JSON->new->allow_nonref;
	$json_hash = $json->decode($json_text);

	use JSONPath;
	my $jpath = JSONPath->new();
	my $result_array = $jpath->run($json_hash, $json_path_text);

	# If there is a single item in the result array,
	# just format that item and return it
	# Otherwise, format the whole array

	$length = @{$result_array};

	my $formatted_result;
	if ($length == 1) {
		$formatted_result = $json->encode($result_array->[0]);
		# strip quotes
		$formatted_result =~ s/^"(.*)"$/$1/;
	} else {
		$formatted_result = $json->encode($result_array);
	}
	return $formatted_result;
$$
language plperlu immutable;

Kudos

Kudos to masukomi for his jsonPath implementation!

Also kudos to Ben Scheirman for the Happy Elephant photo :-)

Prefetching Web Content: Trials and Tribulations

Stoyan is totally right and I’m totally wrong (see his comment below, which reads “The thing about google maps you load is that it’s an html page. When you load html page in object tag it’s as if you put it in an iframe. It includes all markup and extra css/js/img resources.”) My test was incorrect. I was testing with a Google Maps URL, but I should have been testing with a Google Maps API URL. I can’t explain how I used the wrong URL- I THOUGHT I copied that URL directly from our web site, but apparently not.

I’m sorry for the mistake and any confusion it may have created.

[Click below for the full content of the original post.]
Read the rest of this entry »

Use dojo.hash instead of dojo.back

In Dojo 1.4, the Dojo Toolkit team introduced a new “dojo.hash” library for managing the back button in AJAX applications. It’s a replacement for “dojo.back,” which was available in Dojo 1.0. If you’re deciding whether to use dojo.hash vs. dojo.back for your next web application, you should use dojo.hash.

Background: Back Button in AJAX

AJAX applications can update a page inline without navigating to a new page. This makes the page much more responsive, but since everything happens in one page, it makes the back button much less useful.

Way back in 2005, someone figured out a clever trick that would allow AJAX applications to support the back button. If a page at http://www.example.com/#beds=4 changed the URL to http://www.example.com#beds=3, the “#” in the URL would guarantee that the page wouldn’t reload, but the user could still click the back button to go back to “#beds=4″. The user could then click the forward button to go forward to “#beds=3″, navigating back and forth through the browser’s history.

In general, modifying the URL of a page would add an entry to the browser’s history, even if the change was in the URL’s “hash fragment”, the part of the URL that appears after the “#” sign. Since hash fragment changes don’t cause the page to reload, AJAX applications could use the hash fragment to add browser history entries dynamically.

To detect these changes, the page would use a “setInterval” timer to automatically poll the URL for updates every 100ms or so. (In IE8, Microsoft introduced the “onhashchange” event, eliminating the need to poll for changes in the hash fragment; all modern browsers now support “onhashchange”.)

It wasn’t quite that easy, of course. On some browsers, the page must use a hidden iframe to add entries to the browser’s history. In 2007, Brad Neuberg worked out most of the thorny details and wrote the Really Simple History library, which is now in wide use across many JavaScript libraries. His insights were incorporated into the dojo.back library, which was released with Dojo v1.0.

What’s Wrong with dojo.back

There are two problems with dojo.back: first, dojo.back loses history information when the user refreshes the page, and second, dojo.back uses document.write, which makes it difficult to use dojo.back correctly.

1) Refreshing the Page and Bookmarking the URL

dojo.back allows us to pass it a JavaScript object, storing the object in a hashmap in memory. dojo.back modifies the URL to include a random unique string. When the user clicks the back button, dojo.back fires a “back” event; when the user clicks the “forward” button, dojo.back fires a “forward” event.

So, if a user navigates to our site at http://www.example.com/ and performs some action that the user should be allowed to undo, we can pass a memento to dojo.back, e.g. {beds: 4, baths: 2}. dojo.back will modify the URL to http://www.example.com/#1288732596876 and keep a record in memory that “#1288732596876″ corresponds to {beds: 4, baths: 2}. If the user clicks the back button, the URL will revert to http://www.example.com/, and dojo will notify our code.

But that introduces a problem: what if the user refreshes the page? The hashmap in memory is then erased, and all of those entries in the browser’s history are now useless.

A similar problem occurs if the user wants to bookmark your URL for later, or share the URL with another user over email. Since the URL doesn’t contain the data we need to re-create the original object, the data is lost when the current window closes.

There seems to be an obvious fix for this problem: couldn’t we just use “#beds=4&baths=2″ in the URL instead of a random string? Instead of purely unique hash values, we could use a hash value that has meaning, i.e. a “semantically-named” hash value.

That is the correct fix, but there’s no way to do this correctly with dojo.back. dojo.back allows us to configure the “unique” string of the hash value, but we can’t instruct dojo.back to reconstruct mementos from the hash. If the user refreshes the page, dojo.back will erase its in-memory hashmap; it’s not smart enough to read “#beds=4&baths=2″ and re-inflate that into {beds: 4, baths: 2}.

Worse, if we use “#beds=4&baths=2″ as our semantically-named hash value, there’s a good chance that it won’t be unique. So if the user starts at “#beds=4&baths=2″ and then goes on to “#beds=4&baths=1″ and then finally to “#beds=4&baths=2″, dojo.back has no way to know whether the user went FORWARD to “baths=2″ or BACKWARD to “baths=2″

For this reason, dojo.back includes this cryptic warning at the top of its documentation:

NOTE: There are problems with using dojo.back with semantically-named fragment identifiers (“hash values” on an URL). In most browsers it will be hard for dojo.back to know distinguish a back from a forward event in those cases. For back/forward support to work best, the fragment ID should always be a unique value (something using new Date().getTime() for example). If you want to detect hash changes using semantic fragment IDs, then consider using dojo.hash instead (in Dojo 1.4+).

In other words, if we use dojo.back, our hash values need to be dates, e.g. “#1288732596876″, not meaningful strings like “#beds=4&baths=2″, or Dojo will confuse “back” navigation with “forward” navigation.

So, if you want your back button to keep working after refresh, or if you want users to share your URLs with each other, you should use dojo.hash instead of dojo.back.

2) dojo.back is harder to deploy because it uses document.write

Most of what we now know about back-button support was figured out in 2005, when the web was younger. At that time, no browser supported the onhashchange event; the only way to get AJAX back button to work properly in some browsers was to include the embedded iframe before the onload event.

Brad Neuberg figured out that the magic trick was to add the iframe using document.write; this technique was incorporated into dojo.back. document.write is a very dangerous technique on modern browsers, because the specified behavior is for document.write to modify the page if it’s called before the onload event, or to completely erase the entire page if it’s called after the onload event.

As a result, dojo.back has another cryptic note in its documentation:

WARNING: dojo.back.init() must be called before the page’s DOM is finished loading. Otherwise it will not work. Be careful with xdomain loading or djConfig.debugAtAllCosts scenarios, in order for this method to work, dojo.back will need to be part of a build layer.

Fortunately, this document.write hack is not required in any of Dojo’s currently supported browsers; notably, it’s not required in IE6+ or Safari 3+. In fact, if you’re reading this blog post in IE, you’re probably using IE8 or IE9, which has “onhashchange” built-in and requires no iframe at all.

dojo.hash uses an iframe, but does not attempt to create it using document.write; as a result, it’s a lot safer to use than dojo.back.

dojo.hash Is the Way of the Future

dojo.hash is a very simple library compared to dojo.back. In fact, if the browser supports the “onhashchange” event, then it does almost nothing more than attach the “onhashchange” event to the “/dojo/hashchange” topic. (You can also use dojo.hash to get/set the hash fragment in a convenient way.)

dojo.hash makes no attempt to store state objects in memory; instead, anyone who uses dojo.hash must serialize their memento into a hash string before passing it to dojo.hash. (dojo.objectToQuery is particularly useful for for this serialization.) When subscribing to the “/dojo/hashchange” topic, Dojo will invoke a callback function, passing it the current hash fragment.

We think you will find dojo.hash more useful than dojo.back for almost all situations. If dojo.back works for you today, you may not need to upgrade, but if you’re building something new and deciding which library to use, we strongly recommend dojo.hash.

Ryan Dahl Introduces Node.JS

Ryan Dahl, the creator of a high-performing web server written in JavaScript, came by Redfin’s San Francisco office to talk about his creation, Node.JS. It was a very funny, thoughtful talk, particularly because Ryan is somehow both opinionated and careful with the truth. He is the latest in a long line of speakers for Engineer-to-Engineer, a series of technical talks hosted by Redfin, Digg, Pandora and Greylock on topics such as Hadoop, Scala, HTML5, Cassandra and Clusto.

Ryan’s presentation is here, and below is a summary of what he said.

This is going to be very introduction-level, with apologies to anyone who has dived deeper.

The goal of Node is to do easy network programming, to be able to create servers and clients that can be thrown together in a fairly simple way, using JavaScript.

Node.JS is a set of C++ bindings for network I/O and socket I/O. The strong focus is on putting together network servers.

Node is a command-line tool. You need to compile it. There are no binaries available. It’s something that runs from your terminal. It doesn’t have any dependencies other than Python to build it.

Let’s understand it by example… The first example is a program that prints Hello and then in 2 seconds, says World.

1. setTimeout(function () {
2. console.log(’world’);
3. }, 2000);
4. console.log(’hello’);

Node has a lot of browser-like APIs. When you’re in JavaScript, you expect it to be Browser-ey, even if it’s not Browser…ish, that is, even if it doesn’t run in the browser.

Node exits automatically. The program drops out when there’s nothing else to do. If there’s a callback pending it keeps running. In the example, after World, the program exits.

Now let’s make this more complicated. What if we want Hello every half second, then on an interrupt signal we want the program to print Bye?

1. setInterval(function () {
2. console.log(’hello’);
3. }, 500);
4.
5. process.on(’SIGINT’, function () {
6. console.log(’bye’);
7. process.exit(0)
8. });

In the browser your central object is the window; in node it’s a process. This global variable exists always.

It’s like a browser listening for a click event. And it’s also like a UNIX program in that you have to end the program. The process object emits an emit when it receives a signal; you only have to listen for it. You can get the pid, the program arguments, you can grab memory usage, you can get the executable path.

A TCP server emits a connection event, whenever someone connects, it says connect, and then it connects.

Now let’s create an event…

1. net = require(“net”);
2.
3. s = net.createServer();
4.
5. net.on(’connection’, function (c) {
6. c.end(’hello!’);
7. });
8.
9. s.listen(8000);

You can load a module; browser-based JavaScript doesn’t support this. You create a server in line 3, in line 5 – 7, we add an event listener, and then finally on line 9 you set up a port so the server is actually listening.

File I/O is non-blocking too. Node does File I/O. Here’s a program that outputs the last time /etc/passwd was modified.

1. var stat = require(’fs’).stat;
2.
3. stat(’/etc/passwd’, function (err, s) {
4. if (err) throw err;
5. console.log(’modified: %s’, s.mtime);
6. });

If you’re on a server being hit by thousands of people, you can’t just wait for the disk to spin, so Node takes the pragmatic view that you should never wait for something to happen. Set up the action to occur, but don’t wait for this action to occur. Give a callback and then drop back. There are two parameters. There’s an error object if the file is not there. Otherwise, you print out the time modified.

Node can do HTTP too. If it was just TCP and file stuff, that would be very limiting. Load the HTTP module; it is called every time you have a request, it writes to the response the header and Hello and World.

1. var http = require(’http’);
2.
3. var server = http.createServer(function (req,res) {
4. res.writeHead(200, {’Content-Type’: ’text/plain’});
5. res.write(’Hello\r\n’);
6. res.end(’World\r\n’);
7. })
8.
9. server.listen(8000);

The HTTP response is chunked because we don’t know how long it will end up being, so we can’t put a Content-Length header at the top. Node is very good at streaming: we’re not limited to “Here’s this movie, buffer it all.” Node streams up to memory, down to disk.

Here’s a streaming HTTP server… it can stream responses without introducing a large amount of weight, you don’t use a thread for each of these. If you curl it, you get Hello, then two seconds later, you get World.

1. var http = require(’http’);
2. server = http.createServer(function (req,res) {
3. res.writeHead(200, {’Content-Type’: ’text/plain’});
4.
5. res.write(“Hello\r\n”);
6.
7. setTimeout(function () {
8. res.end(’World\r\n’);
9. }, 2000);
10.});
11.
12.server.listen(8000);

This is low-level. It allows streaming requests, and requests can be hung while waiting for other things. With AJAX, connections are continually asking “Do you have anything new?, which can be very taxing on the server. Long polling, on the other hand, only involves asking once and then getting a response when the server wants to send you one.

Node’s HTTP server is enabled by the HTTP parser. You can check out http://github.com/ry/http-parser

You might be thinking: “HTTP, Jeez, how hard could it be, it’s a simple protocol.” You’re wrong. HTTP in the real world is extremely complicated. It’s difficult to be able to parse the headers and be able to expose this streaming nature without buffering. This HTTP server buffers nothing. It’s totally callback-based.

The HTTP server only uses 28 bytes per HTTP connection, which is important when you have 1,000 people chatting on a server. 28 bytes is acceptable for overhead; 4 megabytes isn’t.

Now let’s do inter-process communication with other processes. In this example, you pull out the child process. This is something that can spin the disk. Your CPU is much, much faster than the disk. Don’t wait for the disk.

1. exec = require(’child_process’).exec;
2. exec(’ls /’, function (err, output) {
3. if (err) throw err;
4. console.log(output);
5. });

It’s worth nothing that Node never forces output buffer. You can also stream data through the standard in and out of a child process.

Now we spawn the program cat, and we get a reference to that program. Whatever you send to cat, it sends back. You type in Hello, wait 2 seconds, then type Bye. You get Hello, then wait 2 seconds, then get Bye.

1. spawn = require(’child_process’).spawn;
2.
3. cat = spawn(’cat’);
4.
5. cat.stdin.write(’hello\n’);
6.
7. setTimeout(function () {
8. cat.stdin.end(’bye\n’);
9. }, 2000);
10.
11. cat.stdout.on(’data’, function (d) {
12. console.log(d);
13. });

Connecting streams is common. Where I want to go with Node is thinking of everything in terms of streams. There’s standard in and out, there’s file streams, HTTP connections. But mainly we deal a lot with streams. Generally we’re proxying streams and modifying them in the middle.

So this is JavaScript outside the browser. Yes! That’s almost what everybody wants. We’re interacting with the OS in a browser-like way.
We have an HTTP library for streaming. But wait there’s more… here’s a contrived but interesting web-server benchmark. We’ve set up four web servers. They’re all going to respond with a 1 megabyte file. 100 concurrent clients connect.

• Node can handle 822 reqests per second
• Nginx (web server written in C, popular with the Ruby crowd, consider this as good as it gets): 708
• Thin: 85
• Mongrel: 4

This should be shocking to you. You should be urinating right now. Or getting angry. It shocks me.

There are some caveats. NGINX peaked at 4mb of memory, and Node 60mb of memory. I also didn’t sit down for hours and try to make NGINX fast, as I did with Node.

There are a lot of places in Node where the opposite is true, where it sucks while everything else is good. SSL for example.

Node is written on Google’s V8, the JavaScript engine in Chrome. V8 is a masterpiece of engineering. Google took the 14 best VM engineers and locked them in a closet in Denmark. They were given the JavaScript spec and then told to make it fast.

It’s an amazing VM. Much better than Ruby or Python. Incomparable. Or comparable I guess… All these callbacks must seem weird to you but that is where our speed increase comes from.

Result = query (‘select * from T’); //use result

If you’ve done traditional web programming, you’ve probably used activerecord and you access some record. You use a function to do the I/O, but what does your software do while it’s accessing the database. In many cases, nothing. It’s the year 2010, we’re using Rails, and when you access a database, it stops, the world stops for who knows how long, the database might be in LA, and it takes 2 seconds to respond.

To mitigate that, we load balance with multiple processes, all waiting 2 seconds. That’s a form of concurrency to be sure, I guess that’s what processes are for.

When you access stuff in the CPU, it’s very fast. You can assume any operation to take zero amount of time, until you access the disk or the network. It’s not appropriate to treat operations in the CPU in the same way as operations on disk or I/O. Abstracting I/O as a function doesn’t make sense when the time-frames are so different.

• 3 cycles for L1
• 14 cycles for L2
• 250 cycles for RAM
• 41M cycles for disk
• 240M cycles for network

It’s unacceptable to wait for the database when you’re serving many clients. You can fork a thread – it’s hard in Ruby because its threading system is utterly crap, but Java can – so when one thread blocks while accessing the database, you can start new threads. That’s fine. But you can’t use an OS thread for each socket when you want good concurrency. Threads have weight to them, and context-switching is costly too. Each thread takes 4 meg of memory, which is a lot when you have 1,000 concurrent users.

The alternative to using threads is to structure your code like this:

Query (‘select..’ function (result) { //use result });

Node is fast because it never blocks on I/O. And JavaScript is great for this. In Ruby there’s EventMachine, in Python there’s Twisted, somehow it doesn’t jive, you sit down to write the code and it doesn’t work the way that programming language is meant to work, it doesn’t work with all the modules out there – like a MySQL library — to do I/O. But the browser was already set up to be an event loop. Brendan Eich was a genius. Yes it does one thing at a time, but also many things very quickly, because you never block on I/O.

And there’s a culture of JavaScript, an entire generation of programmers who grew up programming browsers, and now they can code on a server, without forking a thread and blocking on except. Java people on the other hand find this callback concept difficult to grasp. “What do you mean? What is it doing while it’s doing nothing?”

Node jails you into this evented-style programming. You can’t do things in a blocking way, you can’t write slow programs.

Node consists of 3 C libraries: V8; event loop (libev) so you don’t have to write something for every OS; a thread pool (libeio), which is necessary for file I/O. There’s a layer for bindings, C++ glue, then the standard library is written in JavaScript. It’s not a thin binding to a C web server, it actually goes through a lot of JavaScript – that’s impressive – V8 is up to the task. I used to write web servers in Ruby, it was awful, every line of Ruby hurts performance; it’s a beautiful language, but a crappy virtual machine. V8 is not that way.

JavaScript can only access the main thread, the C layer has access to blocking functions – we don’t want to have a global interpreter lock – let’s let the experts have access to the threads. To use the threads, program in C.

I wouldn’t use Node.JS to make big websites, but it is one of the only solutions for making real-time, long-polling things. You’ll probably have a bunch of Rails servers and one Node server for a specialized function. As frameworks mature, you can use Node to build the whole website. You won’t have to load-balance it because it’s very fast but you’ll probably have to put it behind a web server, because you don’t trust it, or because SSL support still sucks. The bottleneck will be your gigabit connection into that machine, not memory or anything else.

And that was it! Many thanks to Ryan for a dazzling talk, and to everyone who came. Thanks too to Greylock, Digg and Pandora for helping us put on the event…

Introducing MultiMarker: The fastest way to add many hundreds or thousands of markers on Google Maps

At Google IO 2009, our fearless leader Sasha Aickin (my boss) demonstrated our high-performance Google Maps utility library to the world; we provided directions explaining how to code it, but we didn’t actually ship the code.

Today, I’m proud to announce that we’ve made our MultiMarker utility library code (formerly known as SuperMarker) available to everyone under the Apache License 2.0. As far as we know, it’s the fastest way to add many hundreds or thousands of markers on Google Maps.

HOW FAST IS IT?

Below, we compare the time required to add 1000 markers in four ways:

1. V2 map using the default GMarker
2. V2 map using Pamela Fox’s MarkerLight
3. V3 map using the default google.maps.Marker
4. Using our MultiMarker library

Note that the GMarker timings you see here were recorded by stopwatch, NOT by automated timer. Also note that these browsers were running on different machines, so you shouldn’t use this table to compare browsers with each other; just compare the columns within each row.

UPDATE: This table was updated on April 22nd to reflect the faster markers available in Google Maps v3.4 nightly.

As you can see, a speedup of 10-100x is possible using the MultiMarker technique, depending on which version of GMaps you’re using.

Try the examples for yourself:

Google Maps V2 Comparison Test
Google Maps V3 Comparison Test

Enjoy!

Service Oriented Architecture with Varnish and Edge Side Includes

As we talked about before, Redfin uses Varnish to implement Edge Side Includes (ESI.) This involved breaking a single big (and expensive) page into individual chunks; each chunk would be generated by separate code, and would be cached on a different schedule.

Once we broke our expensive page into chunks that could be individually cached, it seemed pretty easy to have those chunks served up by different backend servers. Voilà, a monolithic app became “service oriented“! This would let us run the different software components on different machines (with different performance characteristics, different SLAs, even implementations in different languages/environments!)

Of course, nothing is actually that easy, and we made a number of mis-steps before we figured out how to do it.

How To

Varnish allows you to define multiple backends in your VCL. And in your vcl_recv function, you can decide which backend should handle a particular request. At Redfin, we added a new Varnish backend for each of our ESI endpoints, and we added logic to choose the relevant backend by URI. In practice, we actually only have one pool of machines handling our ESI requests, so all of our Varnish backends actually point to the same place.

So the first piece of the puzzle is on our main web servers. On the main web servers, requests go through Varnish. Requests for “normal” pages are sent through to Tomcat, but requests for ESIs are sent to one of the SOA backends. Here’s an example of what the VCL file might look like:


backend default {
  .host = "localhost";
  .port = "8080";
}
backend similars {
  .host = "similars.redfin.com";
  .port = "6081";
}
backend relevantlinks {
  .host = "relevantlinks.redfin.com";
  .port = "6081";
}

sub vcl_recv {
  if (req.url ~ "^/esi-listing-similars" || req.url ~ "^/esi-property-similars") {
    set req.backend = similars;
  }
  else if (req.url ~ "^/esi-listing-trackbacks") {
    set req.backend = relevantlinks;
  }


You might have noticed that the “localhost” backend is associated with port 8080 (where Tomcat is running), but the ESI backends are associated with port 6081 (where Varnish is running on those remote machines.)

We want the instance of Varnish on the main web server to cache content from the main web server, and the instances of Varnish on the ESI backends to cache the content from those backends. This has a few benefits:

• Our effective cache is bigger, since we have caches on multiple machines, each of which has fixed memory
• Having independent caches prevents one set of items from pushing another set out of the cache. If all the data were in a single cache, then cache entries holding similars information (which is small, but expensive to recreate) could be pushed out of the cache by cache entries of “main page” content (which is big and relatively cheap to recreate, but we’d still like to cache.)
• It’s easy to flush individual caches without having to worry about performance problems with other parts of the site

We have another design goal: we’d like to have a single distribution of our software. We’d like to have a single WAR that we can put on any machine; we do NOT want to have to deal with multiple builds, with figuring out which build has been installed on which machine, etc. We’d like to be able to switch a single machine from being a standard web server to being an ESI endpoint without having to redeploy or reconfigure.

This creates a conundrum. We want our main web servers and our ESI servers to be identical, but we also want them to act different. In particular, when an instance of Varnish on a web server gets a request for an ESI fragment, it should redirect that request to an ESI server (more precisely: to the Varnish instance running on an ESI server.) But when an instance of Varnish on an ESI server gets a request for an ESI fragment, it should forward the request to the local Tomcat instance. It should NOT forward the request to ITSELF. Forwarding port 6081 to port 6081 creates an infinite loop- not good.

We want to break the symmetry between the standard web servers and the ESI servers, and we do that by messing with the URIs.

We prepend our ESI URIs with a known prefix, which means “forward this to the ESI server.” But when we process the URI (while forwarding it), we strip off that prefix, so that the ESI server does not also forward it to itself. That’s harder to say than it is to code. The VCL code looks like this:


sub vcl_recv {
  if (req.url ~ "^/backend/") {
    set req.url = regsub(req.url, "^/backend/", "/");

    if (req.url ~ "^/esi-listing-similars" || req.url ~ "^/esi-property-similars") {
      set req.backend = similars;
    }
    else if (req.url ~ "^/esi-listing-trackbacks") {
      set req.backend = relevantlinks;
    }


This breaks the circularity. The path of requests looks like:

1. A requests comes into Varnish on the standard web server for /path/to/a/page
2. Varnish forwards the request to the local Tomcat instance
3. Tomcat responds with HTML that includes <esi:include src=”/backend/esi-listing-similars” />
4. Varnish processes the ESI, and must make a request for /backend/esi-listing-similars
5. The Varnish instance on the standard web server strips off “/backend”, and sends a request for “/esi-listing-similars” to the ESI server
6. The Varnish instance on the ESI server gets the request for “/esi-listing-similars”
7. Since there’s no “/backend” prefix, the Varnish instance on the ESI server forwards the request to its local Tomcat instance
8. The Tomcat instance on the ESI server processes the request, and responds with the relevant HTML fragment
9. The Varnish instance on the ESI server caches the HTML fragment and returns it
10. The Varnish instance on the standard web server parses the HTML fragment into the main page content and returns it to the browser

This example points out another tricky bit- how do we assure that the HTML fragment is cached by the Varnish service on the ESI server, but not by the Varnish service on the standard web server? To handle this correctly, we add a header to the response which indicates if it’s already been cached:


sub vcl_fetch {
  if (req.url ~ "^/esi-") {
    if (obj.http.X-RF-Cached ~ "true") {
      pass;
    }
    set obj.http.X-RF-Cached = "true";


This code says “If there’s an X-RF-Cached header present, then don’t attempt to cache. If there is NOT an X-RF-Cached header present, then add one, and attempt to cache.” With this addition, the HTML fragments will only be cached on the first Varnish instance they pass through, which is on the ESI server in our case.

How NOT To

The solution described above works, and meets our requirements. But we also tried some solutions that did NOT work. Perhaps you can learn from our failures…

Putting Absolute URIs into ESI Includes

Our first thought was that we’d put absolute URIs into our ESI includes in the HTML. For instance, we tried to put <esi:include src=”http://similars.redfin.com:6081/esi-listing-similars” /> into the main HTML of our page. Varnish simply (and correctly, I think) ignores the host name and port. Including http://similars.redfin.com:6081/esi-listing-similars will cause Varnish to act as if you included /esi-listing-similars, and Varnish will use whichever backend it thinks is relevant, regardless of the host name or port in the URI.

Using a Single Server as both a Standard Web Server and an ESI Server

When doing testing, or when some of our servers were unavailable, we were tempted to use a single server as both the standard web server and the ESI server. It seemed like this should work- the trick with the “/backend” prefix should prevent infinite circularity. However, it didn’t work. It seems that Varnish is doing its own checks for circularity, and noticing that a single request passed through the same Varnish instance multiple times (which NORMALLY would be a problematic example of circularity, but we’ve got our clever symmetry breaker in there!) Anyway, Varnish doesn’t allow it, and causes those semi-circular requests to fail.

P.S.

Thanks to D’Arcy Norman for the photo!

Synchronous/Asynchronous Switching with Varnish

When your webapp is serving up content that’s expensive to generate, you may want to serve it up asynchronously- via AJAX calls. This is particularly appealing when content is “below the fold.”

However when that content is cached, you want to serve it up as quickly as possible. If you’ve already calculated the content, you’d like to include it inline in the page, without requiring an AJAX roundtrip. That way, you avoid the latency of an unnecessary round-trip. You also allow the page to be fully rendered (so content doesn’t jump around), etc.

You can optimize for the empty cache, or you can optimize for the full cache, but it seems hard to optimize both experiences.

Redfin faces exactly this conundrum with our listing pages (e.g. http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622.) Calculating the Similar Listings and Similar Sales is expensive and performed in real time. We cut this Gordian Knot through the use of the Varnish caching reverse proxy, along with clever use of ESI (Edge Side Includes.) For an overview of how we use Varnish at Redfin, see our previous post.

We want to say “if there’s a cache miss, then do AJAX, but if there’s a cache hit, then just include the content.” We have to make sure that the AJAX calls will fill the cache, such that subsequent requests will see cache hits, of course!

I’ll outline what the requests/responses look like for us, then I’ll include some pseudocode that supports this.

At the beginning of time, the cache is empty, and the browser requests information on a Listing.

That’s all great, but we still haven’t used the cache! The cache entry will get used for subsequent requests for the same page, like this:

There are two things worth noting about this exchange.

First, when the backend server gets a request for /similars?property_id=604622, it has to decide if it should be returning the real HTML, or should be returning Javascript that will retrieve the HTML via AJAX. It makes this decision based on the value of a header passed in by the client. When the client is making an AJAX request, it knows it better NOT get back a response that generates AJAX requests (that’d be a death spiral.) Therefore, when it makes the AJAX request, it includes the special header. In all other cases, the special header is NOT included. When the header is included in a request, the server will generate the real HTML. When the header is not included, Varnish may answer the request from cache, or it may pass through to the backend server. If the request is fulfilled by the Varnish cache, then it’s the real HTML, but if it’s fulfilled by the backend server, it’ll be the AJAXy HTML.

Second, there are two URLs that have to do with similars.

/similars?property_id=604622 is an internal-use-only URL that returns the content (either the proper HTML or the AJAX code.)

/extranet-similars?property_id=604622 is an externally facing URL that only returns an ESI fragment (which will subsequently be filled in by Varnish. This way, the ESI endpoints are never available to the extranet; Varnish can get to them, but extranet clients have no need for them. This lets us be lazy with the ESI URLs. For example, URLs that are exposed to the extranet do extra validation to check if the user is logged in, etc. URLs for internal use only, such as the ESI URLs, can skip that work. This also lets us change the URLs when the property changes, to facilitate cache busting (see the “Cache busting” section in ESI and Caching Trickery in Varnish for more information.

Pseudocode

OK, so we know what we want the interaction to look like. What code will make this happen? Here’s some Javaish pseudocode that illustrates how it might work:


/*
Invoked for requests like http://www.redfin.com/[address]/home/[property id]
*/
public void handlePropertyRequest(Request request, Response response, long propId) {
   Property property = getProperty(propId);
   response.write("<html><head></head><body>" +
      ...
      "<esi:include src='/extranet-similars?property_id=" +
         propId +
         "&last_mod=" +
         property.getLastModified() +
      "'/>" +
      ...
      "</body></html>");
}



/*
Invoked for (extranet) requests like /extranet-similars?property_id=[property id]&last_mod=[date]
*/
public void handleExtranetSimilarsRequest(Request request, Response response, long propId) {
   Property property = getProperty(propertyId);
   response.write("<esi:include src='/extranet-similars?property_id=" +
         propId +
         "&last_mod=" +
         property.getLastModified() +
      "'/>");
}



/*
Invoked for (intranet) requests like /similars?property_id=[property id]&last_mod=[date]
*/
public void handleSimilarsRequest(Request request, Response response, long propId) {
   if (null == request.getHeader("full_html")) {
      //This request does NOT demand that we return the actual HTML.
      // We will return a script block that will fetch the HTML via AJAX.
      response.write("<script>" +
         "dojo.addOnLoad(" +
            "function() {" +
               "dojo.xhrGet({" +
                  "url: 'http://www.redfin.com/extranet-similars?property_id=" + propId + "'," +
                  "load: function(response, ioArgs){" +
                     "dojo.byId('similar_homes').innerHTML = response;" +
                     "return response;" +
                  "}," +
                  "headers: {'full_html': 'true'}," +
                  "handleAs: 'text'" +
               "});" +
            "}" +
         ");" +
         "</script>");
      //Do NOT cache the script
      response.setCacheable(false);
   }
   else {
      //This request wants the actual HTML for similars
      response.write(getSimilarsHTML(propId));
      //The similars HTML is cacheable- that's the whole point!
      response.setCacheable(true);
   }
}


ESI and Caching Trickery in Varnish

Varnish is a high performance, flexible, open source HTTP accelerator.

We started using Varnish at Redfin in our last major release, a few weeks ago. It’s pretty much invisible to our end users, but we’re so happy with it that we wanted to give the folks who made Varnish their props in public. It has really been great!

Varnish combines three technologies that are really useful at Redfin:

1. A caching reverse proxy to reduce load on our backend servers
2. ESI (Edge Side Includes) to break a page into snippets of HTML which can each have their own caching strategy
3. VCL (Varnish Configuration Language) which enables fine grained control of Varnish

We use Varnish to accelerate the delivery of home details pages. When you visit the page for a home (e.g. http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622), parts of that page are cacheable but other parts can’t be easily cached. For example, the description of the home may be available to all users, but MLSs require us to hide some historical information from users who aren’t logged in. Further, while most of the page might be highly cacheable, the “Sites Linking to 830 El Camino Del Mar” section isn’t as easy to cache- a blog post that refers to our page (via a trackback) may come in at any time.

ESI nesting makes it easy to accomodate these vagaries.

Conceptually, here’s what the HTML for our main page looks like:

<html>
<body>
Some notes about this home

Median House Values:
<esi:include src="/esi-listing-regions?listing-id=123" />
</body>
</html>


Varnish will fill in the details of each of the esi:include sections with results from the “src” URL. In this example, a single HTTP request from the browser to Varnish will cause Varnish to make three HTTP requests to the backend server (one for the main page, one for the trackbacks, and one for the similars.)

Turning a single request into three requests doesn’t really help per-se, but it does enable caching. Previous to ESI, we were unable to cache the page as a whole since the “Sites Linking to” section was uncacheable. By breaking the page into three sections, we can support caching for some of the sections, while disallowing caching of the other sections.

The workflow of a request that’s partially answered from cache might look something like this:

1. The browser requests http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622
2. Varnish receives that request, and looks up the URL in its cache
3. Varnish finds a match in the cache, so it doesn’t send the request for /CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622 through to the backend. Instead it retrieves the content from the cache, and searches it for ESI tags.
4. Varnish finds the ESI include for /esi-listing-trackbacks?listing-id=123
5. Varnish looks up /esi-listing-trackbacks?listing-id=123 in the cache. There’s no entry, so Varnish requests /esi-listing-trackbacks?listing-id=123 from the backend.
6. The backend calculates the content for /esi-listing-trackbacks?listing-id=123 and returns it (along with cache control headers specifying that the results should not be cached)
7. Varnish likewise retrieves the results for /esi-listing-regions?listing-id=123
8. Varnish knits the three HTML snippets together and returns the results to the browser

The big win here is that ESI allows us to cache the main body of the page, even though the trackbacks cannot be cached. This is a tricky bit, so I’ll repeat it. The “outer” HTML, which is the main body of the page, is cached. But the “inner” HTML, the HTML for trackbacks, is NOT cached. The cache of the outer content doesn’t include the inner content- it just includes a token saying “fill in this inner content before you use this cache entry.”

Of course, that’s just the simplest case. In practice, we faced a number of minor challenges while implementing this.

1. Recording every hit

We have two conflicting goals. On the one hand, we’d like to serve content up from cache as often as reasonable- users get the content faster, and our backend systems scale better. On the other hand, we’d like to record every page hit. Whenever a user views a page describing a listing, we record various information. We would like every request to get through Varnish and into our backend, so that we can record this information.
As with nearly every problem in Computer Science, this is solved by adding a layer of code. In this case, the “outer” request is NEVER cached, but all it does is record the hit and generate an ESI include. The “inner” request does the heavy lifting, but responses are cached. For example, the user might request http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622 which would result in this “outer” response:

Cache-Control: max-age=0

<esi:include src="/esi-display-listing?cache-for-logged-out&listing-id=604622" />

which would in turn generate a cache lookup for /esi-display-listing?cache-for-logged-out&listing-id=123. If that’s cached, it’s fast. If it’s not cached, we gotta do all the work.

2. Caching public content without caching user-specific content

The main page content for a home (e.g. http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622) is the same for all anonymous users. However, users that are logged in will see additional details, such as whether or not that home is a “favorite.” Thus, it’s easy to cache for anonymous users, but harder to cache for logged in users (we don’t cache the main page content for logged in users.) It’s easy enough to set the cache-control response headers such that Varnish won’t cache content for logged in users. But we wanted to optimize a bit more- we wanted to avoid even attempting cache lookups when the user is logged in. We did this by adding VCL which examines the incoming request. If the request includes cookies that indicate the user is logged in, we skip the cache lookup. We also put a special token into the URL to make it easy for the VCL logic to know that it should do this magic for the request (since the URLs are ESI URLs, they’re not visible to the extranet.) Here’s what the VCL looks like:

sub vcl_recv {
    ...
    if (req.http.Cookie ~ "RF_AUTH") {
        set req.http._rf_login = regsub( req.http.Cookie, "^.*?RF_PARTY_ID=([^;]*?);*.*$", "\1" );
    }

    # cookies by default make requests in Varnish uncacheable
    unset req.http.Cookie;
    ...
    if (req.url ~ "cache-for-logged-out") {
        #Directive says to use cache for logged out users, but not for logged in users
        if (req.http._rf_login) {
            #Since there's an RF_AUTH, the user is logged in- do not use cache
            pass;
        }
        else {
            #The user is NOT logged in- use cache (but do not look up based on cookies)
            lookup;
        }
    }
    ...
}


3. Cache busting

We’d like to cache HTML describing a listing for a long time (24 hours), but when we get new listing data, we want to show that to users immediately.

One approach is to explicitly invalidate any cache entries that refer to the listing. We could identify all Varnish instances that might cache the data and individually invalidate the content in each one. However, that’s a little difficult to do from Java, it may be unreliable (it requires that we keep good records about all Varnish instances), and it’s generally a PITA.

Instead, we include the last modified time of the listing in the URL. Again, the ESI URLs are internal, so this doesn’t dirty our extranet URLs. My earlier example was incomplete. A request for http://www.redfin.com/CA/San-Francisco/830-El-Camino-Del-Mar-94121/home/604622 might generate a response that looks like this:

<esi:include src="/esi-display-listing?cache-for-logged-out&listing-id=604622&last-mod=1272651333452" />

(note the “last-mod” argument, which represents that last modification date of the Listing.) That way, whenever the listing changes, the URL to the main ESI fragment will change- stale cache entries will be orphaned.

4. Tuning Varnish

When we initially deployed Varnish, we were seeing 503 errors- Varnish was returning 503 Service Unavailable errors. Michael Young (our intrepid CTO) changed many of the Varnish settings, including connect_timeout, sess_workspace, thread_pool_min, and thread_pool_max. The most important thing he did was match the Varnish threads to our expected traffic, and the 503 errors went away (pretty much.)

P.S. Thanks to Odalaigh for the gorgeous image

Laziness (in proxies) is a virtue

We use Hibernate for object-relational mapping (ORM) and organize our code into domain objects and data access objects.

Historically many of our domain objects have been marked with the “@Proxy(lazy = false)” Hibernate annotation. This annotation tells Hibernate that it should NOT create lazy proxies for the annotated class.

At Redfin, these were almost all bugs. We should never use “@Proxy(lazy = false)” without a big comment explaining why it’s necessary. Our default should be “@Proxy(lazy = true)”. Laziness is good!

Here’s my quick understanding of the effects of the @Proxy annotation. As with everything in Hibernate, each individual piece seems simple, but when you consider all the features that Hibernate exposes, and how they interact, it can become pretty complicated.

Hibernate Load Options

When Hibernate loads objects that refer to other objects (i.e. have member objects), it needs to do something about the associated objects. For example, suppose that Cat objects contain (optional) references to Owner objects. When Hibernate is loading a Cat object into memory, it has to decide what to do about the Owner member variable. There are a number of things it COULD do:

1. When it constructs SQL to load the Cat, it could include the Owner table and columns in the SELECT clause, so that all the data is loaded at once
2. It could load the Cat object, and subsequently load the Owner object (via a second SQL statement)
3. It could load the Cat object, and set the Owner member to a placeholder (a proxy), which can be filled in later when the Owner information is needed

Note that it CANNOT simply do nothing about the Owner- if it instantiates a Cat and leaves the Owner member null when the DB says that the Cat DOES have an Owner, then consumers of the Cat will be misinformed- they’ll think that the Cat has no Owner, which is false.

Option 1 (get all the info in 1 SQL statement) is efficient when loading multiple Cats for which the Owner information is needed. For example, if some code needed to iterate over 1000 Cats, and get Owner information for each one, this approach would be efficient.

However, option 1 is inefficient in cases where the secondary information is not needed. E.g. if some code needed to iterate over 1000 Cats but did NOT need to get Owner information, then loading the Owner information is an obvious inefficiency.

Worse, taking option 1 to the extreme can cause an explosion in the data load. For example, a Cat might have an Owner, the Owner might have a Home, the Home might have a Address, which might have a City, which might have a State, etc. Loading the whole object graph into memory via SQL could be very inefficient. Further, every change to domain objects could cause many SQL statements to get hairier (e.g. adding a Country member to the State object would effectively add to the SQL needed to load Cat objects.)

Option 2 (load the Cat, then load the Owner) is simple, and often not bad, but never optimal (if you know you’ll need the Owner info, it’s more efficient to load it in a single SQL statement; if you know you won’t use it you should never load it; if you won’t know until later, delaying the load is better.)

However, option 2 is particularly bad when bulk operations are being performed. For instance, if some code were to load up every Cat object in the database to do some processing, this could be accomplished via a single SQL statement (though it’d probably be better to break it into chunks of, say, 10,000 Cat objects.) However, Hibernate would run a “SELECT * FROM owners” type statement for every Cat object that has an Owner- potentially millions of SQL statements.

Option 3 (load the Cat and set it’s Owner member variable to a proxy- load the Owner info on demand) is a compromise. It allows code to do bulk operations without loading the ancillary information (e.g. load all Cat objects without ever loading any Owner objects.) However, it requires additional SQL statements to load the secondary information IF that info is needed (e.g. if code loaded all Cat objects, then accessed the Owner for each Cat, option 3 would result in potentially millions of SQL statements.) Note that if the Owner information is never needed, then option 3 is most efficient- the information is never loaded.

Hibernate allows programmers to influence which strategy it will take. It offers (at least) two types of control: direct control over the SQL it generates, and control over the proxies.

See https://www.hibernate.org/315.html and https://www.hibernate.org/162.html for information on Hibernate fetching strategies and lazy loading.

Controlling SQL

When you’re implementing a DAO method, you can tell Hibernate whether it should proactively fetch information about member objects.

Under the Criteria API, Hibernate lets you call criteria.setFetchMode to tell Hibernate that it should load the additional info immediately, or should defer it. Hibernate uses the term “eager” to mean “load immediately”, and “lazy” to mean “defer loading.”

When using HQL, you can use the FETCH keyword to specify the fetch mode, which is equivalent.

When using SQL, you can use the query.addJoin method to tell Hibernate that you’ve written SQL which retrieves information for member objects. In this case, you’ll be responsible for writing the joins, etc., yourself.

Controlling Proxies

Hibernate also lets you control the existence and behavior of proxies via the tags mentioned above. Annotating a class with “@Proxy(lazy = false)” tells Hibernate to NOT support lazy proxies for that type of object (of course “@Proxy(lazy = true)” tells Hibernate to support lazy proxies.) This allows the writer of the domain object to essentially override the wishes of the writer of the DAO. If the DAO writer would like to load members in a lazy manner, but the domain object in question doesn’t support lazy loading, then Hibernate will NOT lazy load the object (since it cannot.)

If you’re writing a class for which lazy loading would be dangerous, then you SHOULD disallow lazy proxies, since DAO writers probably won’t understand the detailed load requirements of your class. However, this is unusual. In most cases, lazy proxies are safe.

Since the writer of the domain object can control what choices are available to the writer of the DAO object, they need to use that power judiciously. You CAN code all of your domain objects to disallow lazy loading, which will force all writers of DAOs to use load options 1 or 2 (load all members via fancy SQL, or load all members via secondary SQL statements.) But you generally should not. DAO writers often rely on option 3 (lazy loading), particularly when they know that the member objects will never be accessed (or when they’re not sure.) If you specify “@Proxy(lazy = false)”, you’ve made it impossible for DAO writers to use option 3, which means it may be difficult for them to get their code to perform well. Worse, the writer of the DAO may not realize that you did that, or may not understand the implications. Hibernate queries are actually kinda hard to view, so the writer of the DAO may have created a huge performance problem and not even known it (until you go into production.)

Only the client really knows

Even the writer of the DAO doesn’t know how the client will use the objects it returns. If you’re implementing the CatDAO, you might add a method like getBasementCatsAndOwners, which would return all black cats and pre-fetch the corresponding owners. You think you’re clever because you’ve avoided a major performance problem, but a caller might try to get the Home for each Owner, defeating your pre-fetching strategy. The DAO writer should do their best to anticipate the needs of their callers, and to name and document their methods such that callers can understand what they do, but ultimately the caller is in control, and can (unintentionally) defeat the optimizations of the DAO writer. If your database were large and you knew that you had clients that sometimes needed Owners, sometimes needed Owners and Homes, etc., you might make three methods: CatDAO.getBasementCats, CatDAO.getBasementCatsAndOwners, and CatDAO.getBasementCatsAndOwnersAndHomes.

Conclusion: @Proxy(lazy = false) is generally evil

As mentioned above, when you indicate that a domain object should not support lazy proxies, you make it hard for DAO writers to get their code to perform well. Worse, you disable a capability that they may be counting on, and they may not notice until there are major performance problems. Unless you have a good reason to, use “@Proxy(lazy = true)” on your domain objects.

P.S.

Lazy proxies do have some known problems.

First, the lazy proxy is NOT the same as the actual object. If you depend on the datatype of the object, you may have problems, since the type of the proxy isn’t the same as the type of the actual object (e.g. a proxy for an Owner is not actually an Owner- it’s a subclass.)

Second, you may have to think carefully about methods like equals() or hashCode(), since the proxies may not do what you expect.

P.P.S
Thanks to carloneworld for the great lazy kitty photo!