Repository: kubernetes
Issue: Evolve watchcache to optimize LIST calls and support pagination
Labels: kind/bug,sig/scalability,sig/api-machinery,priority/important-longterm,lifecycle/frozen,triage/accepted

This issue is significantly inspired by discussion I had with @smarterclayton an year ago or so. However, given that we're facing more and more issues and concerns related to it, it's probably the highest time to actually get back to it.

The key point that I didn't realize back then (not sure about Clayton) is that actually, we can do that in an incremental way as opposed to how I was thinking about it back then (which was effectively a rewrite almost from scratch, which was blocking me from pushing for this).


**Current state**:
watchcache in principle stores two types of information
- a cyclic buffer of events - that allow us to server watches from it completely; it's size is dynamically adjusted to ensure that we are keeping at least X (default 75s) seconds of history:
https://github.com/kubernetes/kubernetes/blob/ace55542575fb098b3e413692bbe2bc20d2348ba/staging/src/k8s.io/apiserver/pkg/storage/cacher/watch_cache.go#L156-L163

- a store (indexer) - the current state of all objects:
https://github.com/kubernetes/kubernetes/blob/ace55542575fb098b3e413692bbe2bc20d2348ba/staging/src/k8s.io/apiserver/pkg/storage/cacher/watch_cache.go#L165-L169


**Problems**
There are two main problems with the current implementation of it:

(a) Without watchcache certain types of LIST calls are extremely inefficient, e.g. "list pod from a given node" (that Kubelet is sending on initialization). The reason for that etcd is not aware of k8s resource model, so doesn't allow filtering, so we basically need to fetch all data from etcd, deserialize it all, filter out and only then send the requested data.
Watchcache is critical for optimizing it, as it allows to skipping the "fetch and deserialize" steps from the above. 
Additionally, if multiple lists are happening at the same time, even though they are deserializing the same set of objects, they are doing that independently.

(b) Watchcache doesn't support pagination (mostly because it stores only the current state in memory). This leads to extremely confusing logic that we have that:
- if RV=0, we always serve from watchcache, ignoring pagination
- if RV="", we always serve from etcd, respecting pagination
- otherwise, if limit is unset, we serve from watchcache, otherwise we (inefficiently) serve from etcd respecting pagination:
https://github.com/kubernetes/kubernetes/blob/ace55542575fb098b3e413692bbe2bc20d2348ba/staging/src/k8s.io/apiserver/pkg/storage/cacher/cacher.go#L600-L616


**Desired state**
We would like to evolve watchcache to address the above two problems. Here is roughly what to do:

A) When serving a LIST from etcd, deserialization of objects in kube-apiserver is generally order of magnitude more expensive than fetching them from etcd. So the first step is to optimize this. Note that, we generally should have all (or at least almost all) of those objects already deserialized in watchcache store, because we store a current state in memory. So we should just organize the data better, to utilize it.

B) So we can basically construct a cache of a form:
[RV, key] ->  object
Then we can use this cache to deserialize this object once, not potentially many times:
https://github.com/kubernetes/kubernetes/blob/master/staging/src/k8s.io/apiserver/pkg/storage/etcd3/store.go#L940-L955
https://github.com/kubernetes/kubernetes/blob/master/staging/src/k8s.io/apiserver/pkg/storage/etcd3/watcher.go#L458-L477

The above seems trivial, modulo the fact that we need to know when to remove items from that cache.
The trick is that we already have that information in watchcache. We keep the item in the above cache as long as:
- it is part of the "current state" of watchcache (i.e. there weren't new version for a given key) or
- it is still kept in "transaction log" part of watchcache as a "previous" object:
- https://github.com/kubernetes/kubernetes/blob/master/staging/src/k8s.io/apiserver/pkg/storage/cacher/watch_cache.go#L72

It's just a matter of providing a callback to remove the item from the cache, when it is effectively being dropped from watchcache

C) [Optimization] Once this is done, we can consider all LIST going to etcd fetch only keys (WithKeysOnly option) [which returns also RV of a given key, but doesn't provide the value) and using the above cache to fetch the data.
There is an issue that if (because of slow watch), this cache is lagging behind current state, we may not yet have the data in cache. So we either wait (with timeout) or fallback to listing with data in that case. It's a useful optimization, but I don't think it's critical at this point.

The above (A)-(C) points make serving list calls from etcd much cheaper, on the cost of effectively just a single map, whose values are objects that are stored in memory of watchcache anyway. So the memory cost of that should be easily acceptable.

D) The remaining thing is to allow pagination from watchcache (because as mentioned above, without that, some LIST calls like "list pods from my node" will remain to be unnecessarily expensive (watchcache has support for predefined set of indexes)).

What we basically need to do that is we would need to ensure that:
- we are able to get the set of objects from a given point-in-time
- we can effectively iterate over state in a sorted order
as the continuation token is effectively a pair (RV, last_returned_key)

The standard technique for doing that is BTree with copy-on-write semantics.
Let's assume for a moment we have one. Then what we can do is:
- we basically replace the `store` in watchcache with that BTree
  [it's slightly more tricky, because we need to support indexes, but in the current implementation index is effectively a map from index_value -> [list of keys for which index(object with that key) has a given value]; so assuming that the length of any list is relatively short, we should be able to efficiently maintain it in a second btree; alternatively we can just ignore indexes for past versions (i.e. when listing from past version, we iterate over all objects - the index isn't needed for correctness and we list from past version only for pagination purposes, which with indexes should be really rare)
- when we call a paginated LIST from watchcache, we clone (with copy-on-write) semantic the current tree and serve the request from that cloned copy; we also cache a root to that tree in another cache C
- when the continuation request comes, we get that that btree from cache C and continue serving from it
- the tree is removed from cache C, when a RV from which it was created is removed from the watchcache transaction log
- [Technically we should also think if we then shouldn't extent transaction log (default 75s) to be more aligned with etcd history window (default 150s).]

The above seem to be relatively simple change assuming we have a btree.

A quick web search shows this golang btree implementation: https://github.com/google/btree - I didn't look into quality of it, but at the interface level it seems to expose things we need.

Implementing (D) would allow us to clean up the semantics of pagination for watchcach (and also graduate pagination feature to GA: https://github.com/kubernetes/enhancements/tree/master/keps/sig-api-machinery/365-paginated-lists )
Note that this change is somewhat independent from the above (A)-(C).

/sig api-machinery
/sig scalability
/kind bug
/priority important-longterm

@smarterclayton @deads2k @lavalamp @kubernetes/sig-api-machinery-bugs 
@kubernetes/sig-scalability @mborsz @jkaniuk @shyamjvs