What causes "key out of order: {k} after {lastKey}" in apache/hadoop?

Open the reader WITHOUT an explicit comparator so it derives the default one from the file's key class (data.getKeyClass()).

apache/hadoop · error · IOException

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

Error message

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

What it means

Thrown by MapFile.Reader's private readIndex() while it loads the index into memory: consecutive index keys must be ascending under the comparator in use, and comparator.compare(lastKey, k) > 0 means they are not. Per the code comment, this check exists specifically to detect an incompatible comparator — the file's index was written under a different ordering than the reader is applying. It surfaces lazily, on the first seek/get that forces index loading.

Source

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

        return;
      this.count = 0;
      this.positions = new long[1024];

      try {
        int skip = INDEX_SKIP;
        LongWritable position = new LongWritable();
        WritableComparable lastKey = null;
        long lastIndex = -1;
        ArrayList<WritableComparable> keyBuilder = new ArrayList<WritableComparable>(1024);
        while (true) {
          WritableComparable k = comparator.newKey();

          if (!index.next(k, position))
            break;

          // check order to make sure comparator is compatible
          if (lastKey != null && comparator.compare(lastKey, k) > 0)
            throw new IOException("key out of order: "+k+" after "+lastKey);
          lastKey = k;
          if (skip > 0) {
            skip--;
            continue;                             // skip this entry
          } else {
            skip = INDEX_SKIP;                    // reset skip
          }

	  // don't read an index that is the same as the previous one. Block
	  // compressed map files used to do this (multiple entries would point
	  // at the same block)
	  if (position.get() == lastIndex)
	    continue;

          if (count == positions.length) {
	    positions = Arrays.copyOf(positions, positions.length * 2);
          }

View on GitHub (pinned to 2add963021)

Solutions

Open the reader WITHOUT an explicit comparator so it derives the default one from the file's key class (data.getKeyClass()).
If you must pass a comparator, use the exact comparator class that wrote the file — check how the file was produced.
If key serialization changed across versions, regenerate the MapFile with the current code before reading.
Catch IOException around the first seek/get (index loading is lazy) to fail fast with your own context.

Example fix

// before: custom/decreasing comparator contradicts the file's ordering
MapFile.Reader r = new MapFile.Reader(dir, conf,
    SequenceFile.Reader.comparator(new LongWritable.DecreasingComparator()));
r.get(new LongWritable(42), value); // throws on first index load

// after: let the reader derive the comparator from the file's own key class
MapFile.Reader r = new MapFile.Reader(dir, conf);
r.get(new LongWritable(42), value);

Defensive patterns

Strategy: validation

Validate before calling

// derive the comparator from the file itself instead of guessing one
try (MapFile.Reader probe = new MapFile.Reader(dir, conf)) {
  Class<?> fileKeyClass = probe.getDataKeyClassForValidation(); // or open data via SequenceFile
}
new MapFile.Reader(dir, conf); // no comparator option = default comparator from key class

Try / catch

try {
  reader.seek(newKey); // first seek/get triggers readIndex()
} catch (IOException e) {
  if (e.getMessage() != null && e.getMessage().startsWith("key out of order")) {
    // reader comparator incompatible with file — reopen without explicit comparator
    reader = new MapFile.Reader(dir, conf);
  } else { throw e; }
}

Prevention

Don't pass SequenceFile.Reader.comparator() to MapFile.Reader unless it is verbatim the comparator that wrote the map.
Remember index loading is lazy — wrap the FIRST access (seek/get), not just the constructor, in error handling.
After changing a key class's serialization or a comparator's logic, regenerate MapFiles; do not read across the change.

When it happens

Trigger: Opening a MapFile with SequenceFile.Reader.comparator(cmp) where cmp orders keys differently than the comparator that wrote the file — e.g. a custom WritableComparator with different byte semantics, or a reversed/decreasing comparator; also a key class whose serialization changed between writing and reading so raw byte order no longer matches.

Common situations: Passing LongWritable.DecreasingComparator (or any descending comparator) to read an ascending map; upgrading a custom Writable whose compare() logic changed; reading a MapFile written by an old Hadoop version with modified key serialization; reader constructed with a comparator whose getKeyClass() differs in bytes-for-bytes layout from the writer's.

Related errors

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