Uncovering Kubernetes List Ordering: WatchCache, WatchList, and Hidden Costs

Agreement

Kubernetes list responses are returned in alphabetical order from a to z.

Reason

The ordering convention exists to keep list results consistent before and after enabling the WatchCache feature. When WatchCache is disabled, the request is passed directly to Etcd, which naturally returns keys in lexical ascending order.

Implementation

When WatchCache is disabled, Etcd provides the ordered result. In the kube-apiserver implementation, the Etcd API Range operation does not explicitly set SortOrder or SortTarget, yet the returned data is already sorted by key. The same behavior occurs when using etcdctl to retrieve a key collection.

The default sorting comes from Etcd's Range implementation, which returns keys in alphabetical order when no explicit sorting parameters are set. The relevant code is:

// 最终排序位置
func (ti *treeIndex) visit(key, end []byte, f func(ki *keyIndex) bool) {
    keyi, endi := &keyIndex{key: key}, &keyIndex{key: end}
    ti.RLock()
    defer ti.RUnlock()
    ti.tree.AscendGreaterOrEqual(keyi, func(item btree.Item) bool {
        if len(endi.key) > 0 && !item.Less(endi) {
            return false
        }
        if !f(item.(*keyIndex)) {
            return false
        }
        return true
    })
}

Further down the call chain, the Range method in the apiserver adds a default sort order when the request does not target KEY:

func (a *applierV3backend) Range(ctx context.Context, txn mvcc.TxnRead, r *pb.RangeRequest) (*pb.RangeResponse, error) {
    // ...
    sortOrder := r.SortOrder
    if r.SortTarget != pb.RangeRequest_KEY && sortOrder == pb.RangeRequest_NONE {
        // Since current mvcc.Range implementation returns results
        // sorted by keys in lexicographically ascending order,
        // sort ASCEND by default only when target is not 'KEY'
        sortOrder = pb.RangeRequest_ASCEND
    }
    // ...
}

Thus, by default mvcc.Range returns results sorted alphabetically.

WatchCache Effects

When WatchCache is enabled, the list may appear unordered because, until Kubernetes v1.27, the WatchCache store did not perform explicit sorting. Starting with PR #113730 (v1.27), the store sorts the final data using Go's sort.Sort on a slice that implements sort.Interface.

This sorting was performed while holding a lock, which interfered with the Reflector's event handling and introduced unnecessary latency. The issue was fixed in PR #122027 (v1.30) by moving the sorting outside the critical section.

Even without this bug, each list request incurs an extra sorting step. The current implementation uses the pdqsort algorithm (a generic Go implementation contributed by ByteDance), which is 2–60× faster than previous sorts and requires no extra memory, making its impact negligible compared to serialization and network transfer. A further optimization could replace it with slices.Sort, which uses generics and pdqsort for even lower latency.

Potential Alternatives

One idea is to keep the WatchCache store ordered when events are written, eliminating the need for per‑request sorting. However, the performance gain is expected to be modest and would need empirical evaluation.

WatchList Considerations

WatchList streams list results from the WatchCache store to reduce memory usage. In v1.29.0 it remains alpha and does not guarantee strict alphabetical ordering because it merges data from the store (ordered by resource version) with data from the cacheWatcher channel, which is also ordered by resource version, not by key.

Two pending PRs aim to address this:

PR #120897 – Ensure initial events are sorted for WatchList.

PR #122830 – Ensure the cache is at the most recent ResourceVersion when streaming is requested.

These changes would require the server to wait until the full cache is available and sorted before streaming, introducing additional latency.

The latency depends on Etcd's ProgressNotify interval (default 10 minutes, configurable via --experimental-watch-progress-notify-interval). Reducing this interval to 5 seconds can lower the worst‑case delay, but the inherent delay from the bookmark timer (1 s–1.25 s) remains. Future work may leverage the ConsistentRead mechanism to request Etcd progress notifications more frequently (e.g., every 100 ms).

Conclusion

What seems like a trivial requirement—returning an ordered list—actually touches many components: Etcd's default ordering, kube‑apiserver's Range implementation, WatchCache sorting, and the emerging WatchList streaming logic. The effort required to maintain this guarantee illustrates the hidden complexity in Kubernetes, and similar obscure features likely exist throughout the platform.

References

pr#113730: https://github.com/kubernetes/kubernetes/pull/113730

pr#122027: https://github.com/kubernetes/kubernetes/pull/122027

pdqsort: https://blog.csdn.net/ByteDanceTech/article/details/124464192

pr#120897: https://github.com/kubernetes/kubernetes/pull/120897/

pr#122830: https://github.com/kubernetes/kubernetes/pull/122830