Should prefixNext(0xFF) return "" instead of 0xFF00?

[disksing]

Typically, we use prefixNext(x) to calculate the upper bound when we want to scan all keys have prefix x.

In other word, the range [x, prefixNext(x)) should contain all keys that start with x.

For the specific key 0xFF, all other keys that are equal or greater than it start with 0xFF, so the upper bound should be +inf. Then it leads to the conclusion that prefixNext(0xFF) should return "" (represents +inf when it is the range end key).

This issue does not affect any usage in tidb. But if someone use txn API and try to scan keys prefixed with 0xFF, it will fail.

Current implementation:

tidb/kv/key.go

Lines 43 to 58 in c0d6185

	func (k Key) PrefixNext() Key {
	buf := make([]byte, len(k))
	copy(buf, []byte(k))
	var i int
	for i = len(k) - 1; i >= 0; i-- {
	buf[i]++
	if buf[i] != 0 {
	break
	}
	}
	if i == -1 {
	copy(buf, k)
	buf = append(buf, 0)
	}
	return buf
	}

[disksing]

/cc @coocood

[coocood]

Another option is to return strings.Repeat(0xFF, maxKeyLen).

[coocood]

In practice set maxKeyLen to 8 can solve 99% of the problems.

[disksing]

I think it is a good idea too.

[XuHuaiyu]

@coocood Does this problem still exist?
If so, please assign an assignee for this issue~

[coocood]

Yes, but we are not sure if it needs to be fixed.

[shafreeck]

@coocood I think it is a serious bug that needs to be fixed. distributed/titan which is a Redis layer above TiKV uses PrefixNext often, may meet the bug unexpectedly.