dgraph-io/badger · error

keys not in sorted order (last key: %s, key: %s)

Error message

keys not in sorted order (last key: %s, key: %s)

What it means

sortedWriter.Add enforces that keys arrive in strictly ascending order, since SSTables must be built with sorted keys. If the incoming key is <= the last key added (by badger's internal key comparison, which includes version/timestamp), Add refuses to proceed.

Source

Thrown at stream_writer.go:419

	for {
		select {
		case req := <-w.reqCh:
			process(req)
		case <-w.closer.HasBeenClosed():
			close(w.reqCh)
			for req := range w.reqCh {
				process(req)
			}
			return
		}
	}
}

// Add adds key and vs to sortedWriter.
func (w *sortedWriter) Add(key []byte, vs y.ValueStruct) error {
	if len(w.lastKey) > 0 && y.CompareKeys(key, w.lastKey) <= 0 {
		return fmt.Errorf("keys not in sorted order (last key: %s, key: %s)",
			hex.Dump(w.lastKey), hex.Dump(key))
	}

	sameKey := y.SameKey(key, w.lastKey)

	// Same keys should go into the same SSTable.
	if !sameKey && w.builder.ReachedCapacity() {
		if err := w.send(false); err != nil {
			return err
		}
	}

	w.lastKey = y.SafeCopy(w.lastKey, key)
	var vp valuePointer
	if vs.Meta&bitValuePointer > 0 {
		vp.Decode(vs.Value)
	}

View on GitHub (pinned to 2a001d466f)

Solutions

  1. Sort all entries by key and then by version descending (badger's internal order) before adding
  2. Ensure each key+version pair is added at most once
  3. If duplicate keys with different versions are expected, verify versions decrease for the same key as badger expects
  4. Check the source iteration (e.g. db.NewKeyIterator) uses badger's ordering, not a custom comparator

Example fix

// before
sort.Slice(entries, func(i, j int) bool { return bytes.Compare(entries[i].Key, entries[j].Key) < 0 })
// after
sort.Slice(entries, func(i, j int) bool {
    if c := bytes.Compare(entries[i].Key, entries[j].Key); c != 0 { return c < 0 }
    return entries[i].Version > entries[j].Version // badger requires descending versions
})
Defensive patterns

Strategy: validation

Validate before calling

// Go: validate ordering before Add
var lastKey []byte
func checkOrdered(k []byte, v y.ValueStruct) error {
    if len(lastKey) > 0 && badger y.CompareKeys(k, lastKey) <= 0 {
        return fmt.Errorf("out of order: %s after %s", k, lastKey)
    }
    lastKey = append(lastKey[:0], k...)
    return nil
}

Try / catch

// Go
if err := sw.Add(key, vs); err != nil {
    if strings.Contains(err.Error(), "keys not in sorted order") {
        return fmt.Errorf("input data unsorted at key %q: %w", key, err)
    }
    return err
}

Prevention

When it happens

Trigger: Adding keys to a StreamWriter/sortedWriter out of order — e.g. key <= previous key including same key with lower or equal version; feeding keys not sorted by the (key, version) tuple; using a key iteration order that doesn't match badger's CompareKeys semantics.

Common situations: Streaming from a source that isn't sorted (map iteration, unsorted database dump); re-adding the same key/version twice; loading data from an external store where the caller assumed plain lexicographic sort was enough but versions differ.

Related errors

AI-assisted analysis of dgraph-io/badger@2a001d466f (2026-09-05). Data as JSON: /api/errors/f685e224e9287dcb. Report an issue: GitHub.