apache/hadoop · error · IOException

Keys are not added in sorted order

Error message

Keys are not added in sorted order

What it means

Thrown while closing a key append stream on a sorted TFile (writer created with a comparator name) when the new key compares less than the previously appended key under the file's comparator. Sorted TFiles require keys in non-decreasing order because the block index and binary-search-based scanners depend on it. Once thrown, the writer is inconsistent and only close() is valid.

Source

Thrown at hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/file/tfile/TFile.java:474

           * verify length.
           */
          if (expectedLength >= 0 && expectedLength != len) {
            throw new IOException("Incorrect key length: expected="
                + expectedLength + " actual=" + len);
          }

          Utils.writeVInt(blkAppender, len);
          blkAppender.write(key, 0, len);
          if (tfileIndex.getFirstKey() == null) {
            tfileIndex.setFirstKey(key, 0, len);
          }

          if (tfileMeta.isSorted() && tfileMeta.getRecordCount()>0) {
            byte[] lastKey = lastKeyBufferOS.getBuffer();
            int lastLen = lastKeyBufferOS.size();
            if (tfileMeta.getComparator().compare(key, 0, len, lastKey, 0,
                lastLen) < 0) {
              throw new IOException("Keys are not added in sorted order");
            }
          }

          BoundedByteArrayOutputStream tmp = currentKeyBufferOS;
          currentKeyBufferOS = lastKeyBufferOS;
          lastKeyBufferOS = tmp;
          --errorCount;
        } finally {
          closed = true;
          state = State.END_KEY;
        }
      }
    }

    /**
     * Helper class to register value after close call on value append stream.
     */
    private class ValueRegister extends DataOutputStream {

View on GitHub (pinned to 2add963021)

Solutions

1. Sort the input records with the exact same comparator before appending
2. If the data is not sorted, create the writer with a null comparator name to get an unsorted TFile
3. For a custom comparator, unit-test that compare(a,b) < 0 exactly when a should precede b, including unsigned bytes, prefixes, and equal keys

Example fix

// before
writer = new TFile.Writer(out, blockSize, "none", "com.example.MyComparator");
for (Record r : unsortedRecords) { writer.append(r.key(), r.value()); } // may throw

// after
unsortedRecords.sort(myComparator); // same ordering as MyComparator
writer = new TFile.Writer(out, blockSize, "none", "com.example.MyComparator");
for (Record r : unsortedRecords) { writer.append(r.key(), r.value()); }

// Mirror the file comparator on the last appended key before writing
RawComparator<byte[]> cmp = fileComparator; // same comparator passed to TFile.Writer
if (lastKey != null && cmp.compare(key, 0, key.length, lastKey, 0, lastKey.length) < 0) {
  throw new IllegalArgumentException("Input not sorted at key: " + Arrays.toString(key));
}
writer.append(key, value);
lastKey = key.clone();

catch (IOException e) {
  if ("Keys are not added in sorted order".equals(e.getMessage())) {
    // writer is inconsistent: close it, discard the partial file, fix ordering upstream
  }
}

When it happens

Trigger: writer.append(...) or prepareAppendKey(...)+write where the key is smaller than the last key, judged by the comparator passed to the TFile.Writer constructor (e.g. "memcmp", a BytesComparator, or a custom RawComparator class name).

Common situations: Feeding unsorted input into a sorted writer; a custom RawComparator whose compare() disagrees with the order keys were produced (sign inversion, comparing only a prefix, unsigned vs signed byte handling); merging sources each sorted with a different comparator; Hadoop version changes altering comparator semantics.

Related errors

• Cannot close TFile in the middle of key-value insertion.
• Incorrect key length: expected={expectedLength} actual={len}
• Incorrect state to start a new key: {state}
• Incorrect state to start a new value: {state}
• Incorrect state to start a Meta Block: {state}

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