Double the Page Size: How etcd LIST Escapes the Selector Death Spiral

TL;DR: kubectl get pods -l app=nginx --limit=100 asks etcd for 100 objects, but etcd does not know what a label selector is. It returns 100 raw keys, the apiserver filters them, and if only 4 of the 100 matched, the response has 4 objects in it, not 100. The naive repair - fetch many more pages of 100 - is a death spiral, because a 1% match rate means 100 round trips. The etcd store instead doubles its page size on every iteration, capped at maxLimit = 10000, so the second page asks for 200 keys, the third for 400, and the selector collapses into a handful of large pages instead of hundreds of tiny ones. The continue token that carries the page boundary is base64-encoded JSON, and the decoder refuses any token whose start key is not already path.Clean-normalised, so a client cannot walk out of its own prefix.

A paginated LIST is a promise: “give me at most N objects, and give me a token that lets me fetch the next N”. The promise is easy when nothing filters anything. It is hard when the client asks for a label selector, because the filtering happens after the storage layer has already chosen which objects to hand back.

That mismatch is the whole problem. The etcd store’s paging loop is written in terms of keys in the range; the API’s paging loop is written in terms of objects that matched. When those two numbers diverge, a naive implementation pages forever.

The limit the client asked for

The page-size cap is a plain constant, separate from whatever limit the client asked for:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:56
const (
	// maxLimit is a maximum page limit increase used when fetching objects from etcd.
	// This limit is used only for increasing page size by kube-apiserver. If request
	// specifies larger limit initially, it won't be changed.
	maxLimit = 10000
)

Read the comment carefully, because it encodes the whole policy: the cap only bounds increases. If a client asks for limit=50000, the apiserver honours 50000 and the cap never applies - it stops the doubling from running away, it does not truncate legitimate large requests. And there are two “limits” in play: the client’s opts.Predicate.Limit is the API-level contract (at most that many matching objects), while the store’s limit variable is the etcd page size (how many raw keys to ask for).

etcd does not know about your label selector

etcd stores opaque byte strings under opaque keys. It has no idea what app=nginx means, and it cannot apply a selector for you. So the store asks etcd for a page of raw keys and applies the predicate itself, in appendChunk:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:1063
	for i, kv := range kvs {
		if paging && int64(v.Len()) >= pred.Limit {
			return lastKey, evaluated, true, nil
		}
		lastKey = kv.Key
		ok, err := s.processListItem(ctx, kv, pred, newItemFunc, aggregator, v)
		if err != nil {
			return lastKey, evaluated, false, err
		}
		if ok {
			evaluated++
		}
		// free kv early. Long lists can take O(seconds) to decode.
		kvs[i] = nil
	}
	return lastKey, evaluated, false, nil
}

Two things to notice. lastKey is advanced for every key processed, including the ones the selector rejected - the continue token therefore points at the last key examined, not the last key returned, which is exactly what you want for resumption. And limitReached is reported when the loop finds it already has enough matching objects, which is how the caller learns “there is more, and here is where to resume”. The Count field etcd returns is likewise a count of raw keys in the range, not of matching objects. The apiserver is explicit about the consequences - PrepareContinueToken (continue.go:100) refuses to report a remainingItemCount when a selector is in play, because the number would be a lie: etcd’s count includes every key it walked, matched or not. Only when the predicate is empty does it compute itemsCount - limit and hand it back to the client.

Doubling the page size

The consumer loop in GetList (store.go:825) pulls chunks until it has filled the client’s limit, or the range is exhausted. The conditions at the bottom of that loop are the ones that matter: it keeps going only while the response is under-full, and it stops the moment v.Len() >= opts.Predicate.Limit. The producer of those chunks is the page-size doubler:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:893
			hasMore := int64(len(getResp.Kvs)) < getResp.Count
			// use the same resource version for subsequent requests
			if withRev == 0 {
				withRev = getResp.Revision
			}
			// capture the next continue key before yielding, the consumer nils out kvs as it decodes them
			if len(getResp.Kvs) > 0 {
				continueKey = string(getResp.Kvs[len(getResp.Kvs)-1].Key) + "\x00"
			}
			revision := withRev
			if !yield(listChunk{kvs: getResp.Kvs, revision: &revision, count: getResp.Count, hasMore: hasMore}, nil) {
				return
			}
			if !hasMore {
				return
			}
			if limit < maxLimit {
				// We got incomplete result due to field/label selector dropping the object.
				// Double page size to reduce total number of calls to etcd.
				limit *= 2
				if limit > maxLimit {
					limit = maxLimit
				}
			}
		}
	}
}

The arithmetic is the whole trick, and it is worth doing out loud. Start with limit=100 and a selector that matches 1% of objects. Page 1 asks etcd for 100 keys, gets 100 keys, 1 matches, the consumer is still under 100, so it wants more. The producer doubles: page 2 asks for 200 keys, 2 match. Page 3 asks for 400. Page 4 for 800. After ten pages the page size is 51 200, which the cap clamps to 10 000, and from then on every page returns 10 000 raw keys - roughly 100 matches at a 1% hit rate. The client fills its 100-object page in one or two more requests, not a hundred.

The doubling is geometric, so the number of round trips is O(log(needed_keys / limit)) rather than O(needed_keys / limit): a LIST that takes 100 etcd round trips takes 10 instead. Two details make this safe. The limit *= 2 happens after the yield, so it is only reached when the consumer explicitly asked for more - a consumer that is satisfied never triggers a second page at all. And the clamp is if limit < maxLimit, so once the page size reaches 10 000 it stops growing rather than growing without bound. Note also what the doubling does not change: the client’s requested limit. The response still contains at most opts.Predicate.Limit matching objects, because appendChunk stops as soon as it has that many.

The continue token

The token is the client’s handle on “where I got to”: a small structured object, JSON-encoded and base64’d.

go
// staging/src/k8s.io/apiserver/pkg/storage/continue.go:82
// EncodeContinue returns a string representing the encoded continuation of the current query.
func EncodeContinue(key, keyPrefix string, resourceVersion int64) (string, error) {
	nextKey := strings.TrimPrefix(key, keyPrefix)
	if nextKey == key {
		return "", fmt.Errorf("unable to encode next field: the key and key prefix do not match")
	}
	out, err := json.Marshal(&continueToken{APIVersion: "meta.k8s.io/v1", ResourceVersion: resourceVersion, StartKey: nextKey})
	if err != nil {
		return "", err
	}
	return base64.RawURLEncoding.EncodeToString(out), nil
}

The struct is fixed at meta.k8s.io/v1 with three fields - v, rv, start - and the version is baked in because a rolling upgrade cannot have half the fleet writing a format the other half cannot read. The start key is stored relative to the key prefix, so a token for /registry/pods/ does not leak the prefix into the payload.

The decoder is where the security-relevant code lives. A continue token is client-supplied input, and it names the key the next page starts at. If the client could put ../../registry/secrets/ in there, the next page would range over a different key space entirely - a cross-resource read:

go
// staging/src/k8s.io/apiserver/pkg/storage/continue.go:56
	switch c.APIVersion {
	case "meta.k8s.io/v1":
		if c.ResourceVersion == 0 {
			return "", 0, ErrInvalidStartRV
		}
		if len(c.StartKey) == 0 {
			return "", 0, ErrEmptyStartKey
		}
		// defend against path traversal attacks by clients - path.Clean will ensure that startKey cannot
		// be at a higher level of the hierarchy, and so when we append the key prefix we will end up with
		// continue start key that is fully qualified and cannot range over anything less specific than
		// keyPrefix.
		key := c.StartKey
		if !strings.HasPrefix(key, "/") {
			key = "/" + key
		}
		cleaned := path.Clean(key)
		if cleaned != key {
			return "", 0, fmt.Errorf("%w: %v", ErrGenericInvalidKey, c.StartKey)
		}
		return keyPrefix + cleaned[1:], c.ResourceVersion, nil
	default:
		return "", 0, fmt.Errorf("%w %v", ErrUnrecognizedEncodedVersion, c.APIVersion)
	}
}

The defence is elegant: normalise the key with path.Clean, then reject the token if cleaning changed it. A key that is already clean - /pods/foo

passes. A key with a traversal - /pods/../../secrets - cleans to /secrets, which differs from the input, so the token is rejected outright. The apiserver never repairs a hostile token; it refuses it. The other two guards are equally blunt: a token with rv == 0 is invalid (ErrInvalidStartRV), because a continue token must pin a resourceVersion
that is how the pages stay consistent - and an empty start key is invalid (ErrEmptyStartKey). An unrecognised v is rejected too, which is what makes a future meta.k8s.io/v2 possible without breaking old clients. And ValidateListOptions (interfaces.go:372) rejects a request that carries both a continue token and an explicit resourceVersion, because they could disagree.

The stream path, and the graceful fallback

The paginated path above is the fallback. etcd 3.7 added a RangeStream RPC, and the apiserver prefers it when it can:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:747
// shouldStream determines whether a list request should use etcd RangeStream.
func shouldStream(opts storage.ListOptions) bool {
	// Only recursive lists stream, a non-recursive request reads a single object.
	if !opts.Recursive {
		return false
	}
	// etcd is unaware of selector matches, so a filtered page can't carry a proper limit.
	// Stream only unfiltered pages.
	if opts.Predicate.Limit > 0 && !opts.Predicate.Empty() {
		return false
	}
	return utilfeature.DefaultFeatureGate.Enabled(features.EtcdRangeStream) &&
		etcdfeature.DefaultFeatureSupportChecker.Supports(storage.RangeStream)
}

Note the second condition, and the reason given: a filtered page cannot carry a proper limit, so the stream path is only used for unfiltered pages. The stream RPC does not understand selectors either, and unlike the paginated path it has no doubling mechanism, so a filtered stream would hit the same wall with fewer options.

The interesting part is what happens when etcd is too old to have RangeStream. The store probes with one call and interprets Unimplemented as “not supported”:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:951
	stream, streamErr := s.client.KV.GetStream(ctx, startKey, streamOpts...)
	var first clientv3.RangeStreamResponse
	var firstOk bool
	if streamErr == nil {
		first, firstOk = <-stream
		if firstOk && grpcstatus.Code(first.Err()) == grpccodes.Unimplemented {
			return nil, false
		}
	} else if grpcstatus.Code(streamErr) == grpccodes.Unimplemented {
		return nil, false
	}

Unimplemented is a normal gRPC status, not an error condition - it means “this server does not have that RPC”. The store treats it as a capability probe, falls back to the paginated path, and records the fact so the next request does not probe again. The checker’s default for storage.RangeStream is true - optimistic - and MarkUnsupported flips it to false for rangeStreamRecheckInterval (10 minutes), after which the apiserver tries again. That recheck interval is what lets a cluster survive an etcd upgrade: the apiserver keeps working against the paginated path while it waits, and picks the stream path back up when the new etcd is in place. The watch side does the same thing, with the same fallback:

go
// staging/src/k8s.io/apiserver/pkg/storage/etcd3/watcher.go:309
func (wc *watchChan) sync() error {
	if wc.recursive && utilfeature.DefaultFeatureGate.Enabled(features.EtcdRangeStream) &&
		etcdfeature.DefaultFeatureSupportChecker.Supports(storage.RangeStream) {
		err := wc.syncStreamRecursive()
		if err == nil {
			return nil
		}
		if grpcstatus.Code(err) != grpccodes.Unimplemented {
			return err
		}
		etcdfeature.DefaultFeatureSupportChecker.MarkUnsupported(storage.RangeStream)
		klog.V(4).Infof("etcd server does not support RangeStream for %v; falling back to paginated list", wc.watcher.groupResource)
	}
	return wc.syncPaginated()
}

The paginated watch sync is worth contrasting with the LIST path, because it does not double. syncPaginated (watcher.go:325) asks for defaultWatcherMaxLimit - which is maxLimit, 10 000 - raw keys per page and keeps the page size fixed for the whole sync. No doubling, because a watch sync has no client-supplied limit to fill: it wants all the objects, so a bigger page is simply better and there is no “the page came back too small” signal to react to.

The cacher ignores limit for resourceVersion=0

Most LIST traffic never reaches the etcd store at all. The watch cache serves it from memory, and for an unpinned list the cacher deliberately ignores the limit:

go
// staging/src/k8s.io/apiserver/pkg/storage/cacher/cacher.go:749
// computeListLimit determines whether the cacher should
// apply a limit to an incoming LIST request and returns its value.
//
// note that this function doesn't check RVM nor the Continuation token.
// these parameters are validated by the shouldDelegateList function.
//
// as of today, the limit is ignored for requests that set RV == 0
func computeListLimit(opts storage.ListOptions) int64 {
	if opts.Predicate.Limit <= 0 || opts.ResourceVersion == "0" {
		return 0
	}
	return opts.Predicate.Limit
}

The reason is consistency, not laziness. A list at resourceVersion=0 means “whatever is current right now” - the cache is free to be a moving target, and the result is explicitly not a consistent snapshot. But a paginated list is a different contract: the pages together form one snapshot, and the client must be able to resume mid-way and see the same world. If the cacher applied a limit to an unpinned list, the boundary between page 1 and page 2 would depend on whatever happened to be in the cache between the two requests, and the pages could not be joined into a consistent set. So the cacher refuses to paginate an unpinned list. The delegator draws the same line: a request with a limit and a specific, non-zero resourceVersion goes to etcd (ShouldDelegateList, delegator/interface.go:51), while resourceVersion=0 with no continue token is served from the cache with the limit dropped.

The trade-offs

What it buys. A filtered LIST costs O(log) round trips to etcd instead of O(matching_ratio_inverse). At a 1% match rate, filling a 100-object page goes from roughly 100 etcd calls to about 10; at 0.1%, from 1 000 to about 13. Larger pages also mean more sequential etcd reads, which is what etcd’s own storage layer wants.

What it costs.

Memory. A 10 000-key page is 10 000 decoded objects in flight. The apiserver holds them all before it can filter them down.
Over-fetch. The client asked for 100 objects and the apiserver read 10 000 keys to find them. The trade is explicit: read 100x the data once, or make 100 round trips.
The cap is a cap. maxLimit = 10000 is not configurable. A selector so selective that even 10 000 raw keys rarely contain a match will still crawl, and there is no flag to raise the ceiling.
The stream path gives up on filters entirely. shouldStream refuses to stream a filtered page, so the doubling trick only exists on the paginated path. On etcd 3.7+ an unfiltered LIST takes the stream path and never touches the doubling at all.
The continue token is a security boundary. Clients treat it as opaque; it is not, and the path.Clean check in DecodeContinue is the only thing between a client and a cross-prefix read.

Wrapping up

The one thing to remember: the etcd store’s page size is not the client’s limit. The store starts at the client’s limit and doubles it on every iteration, capped at maxLimit = 10000 (staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go:909), because etcd applies no selector and a filtered page comes back under-full. The response still honours the client’s limit - appendChunk stops as soon as it has enough - so the doubling only changes how many raw keys are read.

The part people get wrong: “the apiserver returns at most limit objects, so it must have asked etcd for limit objects”. It did not. It asked for limit, then 2*limit, then 4*limit, up to 10 000 keys per page, and threw away everything that did not match. And the reverse trap: the remainingItemCount field is nil whenever a selector is present, because etcd’s Count counts raw keys, and reporting it as a count of remaining objects would be a lie.

What to go do about it: measure the gap with apiserver_storage_list_fetched_objects_total versus apiserver_storage_list_returned_objects_total (and the apiserver_storage_list_evaluated_objects_total in between) - a large fetched/returned ratio is exactly the selector death spiral, and it is the number that tells you the doubling is doing work. Per-request cost is in apiserver_etcd_request_duration_seconds with the operation label (list versus listStream - the latter means the RangeStream path is live). To see whether the stream path is available, look for the etcd server does not support RangeStream message at -v=4; the EtcdRangeStream feature gate is Beta and on by default, but the storage.RangeStream capability defaults to true and is only downgraded for 10 minutes after an Unimplemented response. And remember that the cacher ignores limit for resourceVersion=0 lists (cacher.go:756) - if you want a paginated, consistent list you must send a non-zero resourceVersion, and you must treat the returned continue token as opaque.