Yelp/mrjob — Issue #307: Sort gives different results on EMR than locally
Author: rspeer
Created: 2011-12-13 20:40:59+00:00
State: open

I have a graph-traversing job that needs to visit each node immediately before it visits the outgoing edges. All the nodes and edges are represented as lines in a tab-separated file.

Bafflingly, the results I was getting were correct when I ran locally on my Mac, but were wrong and nearly empty when running on Amazon Elastic MapReduce.

I identified the key problem by putting a no-op reduce after my map step: the sort order is different on EMR! In fact, I cannot understand what order my values are coming out in. At first I thought it was just case-insensitive, but other weirdnesses in the order tell me something else must be going on.

All my intermediate values were labeled as either "NODE" or "edge", with the intent that "NODE" would sort before "edge". This requires, essentially, that the values for each key appear in lexicographic order. Here's what the reducing step sees on a small input when I run locally:

```
"/"	"edge\tedge\tA\t1.0"
"/conjunction/E"	"NODE\t0.0"
"/conjunction/E"	"NODE\t0.0"
"/conjunction/E"	"edge\tedge\tF\t1.0"
"A"	"NODE\t1.0"
"A"	"edge\tedge\t/conjunction/E\t1.0"
"A"	"edge\tedge\tB\t1.0"
"A"	"edge\tedge\tC\t1.0"
"B"	"NODE\t0.0"
"B"	"edge\tedge\t/conjunction/E\t1.0"
"B"	"edge\tedge\tD\t1.5"
"C"	"NODE\t0.0"
"C"	"edge\tedge\tD\t-1.0"
"D"	"NODE\t-0.0"
"D"	"NODE\t0.0"
"F"	"NODE\t0.0"
```

That's correct. But here's what it sees when I run on EMR:

```
"/"	"edge\tedge\tA\t1.0"
"/conjunction/E"	"edge\tedge\tF\t1.0"
"/conjunction/E"	"NODE\t0.0"
"/conjunction/E"	"NODE\t0.0"
"A"	"edge\tedge\tC\t1.0"
"A"	"NODE\t1.0"
"A"	"edge\tedge\t/conjunction/E\t1.0"
"A"	"edge\tedge\tB\t1.0"
"B"	"NODE\t0.0"
"B"	"edge\tedge\tD\t1.5"
"B"	"edge\tedge\t/conjunction/E\t1.0"
"C"	"NODE\t0.0"
"C"	"edge\tedge\tD\t-1.0"
"D"	"NODE\t0.0"
"D"	"NODE\t-0.0"
"F"	"NODE\t0.0"
```

Why does "edge" appear before "NODE"? Why does "D" appear before "/conjunction/E" in the values, but after it in the keys?