Repository: kubernetes
Issue: idea: More memory efficient watch cache
Labels: sig/scalability,priority/awaiting-more-evidence,sig/api-machinery,kind/feature,lifecycle/frozen

The current watch cache requires apiserver hold at least every item in a collection in memory (otherwise it cannot serve lists from the cache), and more (a history window). This is a large amount of memory consumed.

There's an alternative design that IIRC wasn't possible with etcd2 but should now be possible: catch-up watches.

Instead of serving a list from the cache,
* we'd serve it directly from etcd if it is paginated (which we already do), since paginated requests are relatively cheap.
* But unpaginated list requests will have a max frequency, e.g. 1 / second. All requests for the same list get held for either that amount of time, or until an in-flight etcd list query finishes. Then we serve the same data to all requesting clients. (To make this memory efficient, we may have to do a series of paginated requests against etcd, and stream the results to clients.) This greatly penalizes unpaginated lists, and that's OK IMO.

We'd retain the part of the watch cache that multiplexes a single watch to many watchers. We keep all these watchers at exactly the same revision; as a change comes in, we broadcast it to all watchers.

Now, for a new watch request, we have a problem-- the request might be for revision X, when all the existing watchers are on revision Y.
* If X > Y, add the watcher, and just skip events until the existing watchers catch up.
* If X < Y, add the watcher and begin queueing (not sending) events; do a query from etcd between revisions X and Y (e.g., this could be a watch that we terminate early!). If that's successful, send those to the watcher, then the queued events (if any), then the watcher is caught up.

This is inefficient if there's many revisions that need to be processed for every new watcher. We can help this by keeping a small cache of revisions, so that we have to do fewer and smaller revision queries from etcd (this cache can be arbitrarily small, unlike the cache for supporting LISTs). Alternatively, we could batch these as suggested for lists above.

Here's some challenges with this:
* boundary conditions: lots of opportunity to have an off-by-one error when joining watchers or batching catch-up watch requests. Exhaustive testing can fix this.
* filters: lists from etcd and catch-up watch requests could well end up throwing away much of the events for not matching a filter. This is inefficient and would be worse than the existing design for these queries (the existing design is already pretty bad--aside from targeted queries which have been optimized). The only real (IMO) solution for this problem is to push the selection behavior into the storage layer, but that's super hard.

TL;DR: Our existing cache is about locally reproducing the watch behavior. This proposal is about changing the theoretical nature of this, so that instead we think of it in terms of joining up requests that can share work. It's no longer primarily a cache, it's a smart [singleflight](https://godoc.org/golang.org/x/sync/singleflight).

There's a memory/cpu tradeoff here, at least as long as apiserver has to do the filtering. So, I'm not claiming we should do this immediately, I just want to document the approach. This would let apiserver scale to bigger cluster sizes (where not everything fits in RAM). Which is another way of saying it'd permit some amount of horizontal scaling (add more machines) instead of vertical scaling (add more RAM).

/sig api-machinery
/priority awaiting-more-evidence