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.

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.
• Cannot compare keys for unsorted TFiles.
• Entries are not comparable for unsorted TFiles
• Incorrect key length: expected=
• Incorrect state to start a Meta Block

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

Appendix: 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)