apache/hadoop · error · IOException

key out of order: {key} after {lastKey}

Error message

key out of order: {key} after {lastKey}

What it means

Thrown by MapFile.Writer.append (via checkKey) when the key being appended compares LESS than the previous key using this writer's comparator (comparator.compare(lastKey, key) > 0). A MapFile is a sorted archive: every append must be non-decreasing. The message names both the offending key and the previous lastKey, so the sort break is visible immediately.

Source

Thrown at hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/MapFile.java:421

      long pos = data.getLength();      
      // Only write an index if we've changed positions. In a block compressed
      // file, this means we write an entry at the start of each block      
      if (size >= lastIndexKeyCount + indexInterval && pos > lastIndexPos) {
        position.set(pos);                        // point to current eof
        index.append(key, position);
        lastIndexPos = pos;
        lastIndexKeyCount = size;
      }

      data.append(key, val);                      // append key/value to data
      size++;
    }

    private void checkKey(WritableComparable key) throws IOException {
      // check that keys are well-ordered
      if (size != 0 && comparator.compare(lastKey, key) > 0)
        throw new IOException("key out of order: "+key+" after "+lastKey);
          
      // update lastKey with a copy of key by writing and reading
      outBuf.reset();
      key.write(outBuf);                          // write new key

      inBuf.reset(outBuf.getData(), outBuf.getLength());
      lastKey.readFields(inBuf);                  // read into lastKey
    }

  }
  
  /** Provide access to an existing map. */
  public static class Reader implements java.io.Closeable {
      
    /** Number of index entries to skip between each entry.  Zero by default.
     * Setting this to values larger than zero can facilitate opening large map
     * files using less memory. */
    private int INDEX_SKIP = 0;

View on GitHub (pinned to 2add963021)

Solutions

1. Sort all entries with the SAME comparator the writer uses before appending (see example: sort with WritableComparator.get(keyClass)).
2. If input is a Hadoop job, run it through a reduce phase (or use sort job) so keys arrive sorted.
3. Verify a custom comparator's compare() is a valid total order and matches how the data was produced; unit-test it against sample pairs.
4. If you truly need unsorted data, use SequenceFile.Writer instead — MapFile's index requires sorted keys.

Example fix

// before: appends unsorted keys, throws on second append
try (MapFile.Writer w = new MapFile.Writer(conf, dir,
         MapFile.Writer.keyClass(Text.class))) {
  for (Map.Entry<Text, Text> e : hashmap.entrySet()) w.append(e.getKey(), e.getValue());
}

// after: sort entries with the writer's comparator first
WritableComparator cmp = WritableComparator.get(Text.class, conf);
List<Map.Entry<Text, Text>> es = new ArrayList<>(hashmap.entrySet());
es.sort((a, b) -> cmp.compare(a.getKey(), b.getKey()));
try (MapFile.Writer w = new MapFile.Writer(conf, dir,
         MapFile.Writer.keyClass(Text.class))) {
  for (Map.Entry<Text, Text> e : es) w.append(e.getKey(), e.getValue());
}

WritableComparator cmp = WritableComparator.get(Text.class, conf);
if (lastKey != null && cmp.compare(lastKey, nextKey) > 0) {
  throw new IllegalArgumentException("Input not sorted at key " + nextKey);
}
writer.append(nextKey, value);

try {
  writer.append(key, value);
} catch (IOException e) {
  if (e.getMessage() != null && e.getMessage().startsWith("key out of order")) {
    failJobWithHint("Feed sorted input or use SequenceFile for unsorted data");
  } else { throw e; }
}

When it happens

Trigger: Appending keys in any order other than ascending per the comparator in effect — e.g. emitting Text keys out of lexicographic order, or appending IntWritable 5 after 10; using a custom WritableComparator whose compare() disagrees with the order the producer sorted by; a downstream job's reduce output assumption broken because the comparator differs from the mapper's partition/sort comparator.

Common situations: Feeding a MapFile.Writer from an unsorted map output instead of reduce-sorted output; changing the key class's serialization (e.g. Text encoding change) without regenerating files; custom comparators where compare() is not consistent with the natural order the data was produced in.

Related errors

• key out of order: {k} after {lastKey}
• Input files cannot be merged as they have different Key clas
• key class or comparator option must be set
• Mkdirs failed to create directory {dirName}
• Could not rename {oldDir} to {newDir}

AI-assisted analysis of apache/hadoop@2add963021 (2026-08-22). Data as JSON: /api/errors/c8e559c124b3b781. Report an issue: GitHub.