opened
wojtek-t
username_0
### Background
Currently, to serve LIST operation in apiserver we do the following:
- read all objects of a given resource from etcd
- filter out objects that user is not interested in
- return the result

This means, that complexity of LIST operation is proportional to the number of all objects of a given type, not to the number of objects returned to the user.

As an example, consider 1000-node cluster with 30.000 pods running in it. If a user has a ReplicationController with, say 10 replicas, then listing them requires requires reading all 30.000 from etcd, filtering them and returning just 10 which are interesting for the user.


### Proposal

We would like to make the LIST operation proportional to the number of elements it returns as a result.

With the "Cacher" layer (used by watch in apiserver: #10475), we already store a copies of objects with a given type in apiserver so if we add an Indexer to it (which should be simple), we would be able to effectively serve list operations from it.

The problem is that a cache in apiserver is delayed (usually by tens to hundreds milliseconds). So if we just start to serve list operations from there we will change the semantics - e.g. it can happen that if you POST an object to apiserver and call LIST immediately after, the returned list may not contain already POSTed object.

In many cases, this doesn't really matter, for example if LIST is only done to start watching from that point, we will get eventual consistency anyway (just the starting point changes). However, it can possibly break some other clients.

I can see 3 main options:
- just change the semantics
- add an option (parameter) to LIST operation to force listing from database; however, in this case we should probably make listing from database by switched off by default to take advantage from it wherever it's possible
- change the LIST operation to take ResourceVersion paramater and ensure that what we return in a result is no older than the given ResourceVersion (however, to make it efficient, we don't give any guarantees on how fresh the result is - we only promise to return the result not older than the given ResourceVersion).

[The third option is the best in my opinion].

What do you think about it?

@kubernetes/goog-control-plane @kubernetes/goog-csi 
@username_2 @brendandburns @username_4 @username_3 
@username_1 @derekwaynecarr
Speed-up LIST operations by serving them from memory
issue
created
smarterclayton
username_1
Today, we don't enforce that guarantee necessarily in a cluster because we
don't specify quorum=true reads.  This will make it more likely though.

We had proposed taking the resourceVersion as minimum read before, I'm in
favor of that as well.
comment
created
wojtek-t
username_0
We had proposed taking the resourceVersion as minimum read before, I'm in
favor of that as well.

Was this discussed somewhere on github? I didn't see that...
comment
created
smarterclayton
username_1
Very old https://github.com/kubernetes/kubernetes/pull/846#issuecomment-54387892
comment
created
lavalamp
username_2
@username_0 and I discussed this IRL yesterday and I'm also in favor of accepting a resourceVersion on list. It means clients that care have to change, e.g. kubectl may want to cache the resource version it got on a POST for reuse in a subsequent LIST.
comment
created
lavalamp
username_2
@username_0 do you plan on fixing watches at the same time or will that be a second step? I think most of the benefit is quite possibly in fixing the number of times the watches invoke filterfuncs...
comment
created
smarterclayton
username_1
We *might* want to make clients stateful and observe this themselves.
comment
created
bgrant0607
username_3
Hah. I'm not the only one who remembers old issues. :-)

I'm in favor of accepting resourceVersion on GET, as well, as you could guess from that comment. That would only help new, smart clients, however.

An option not mentioned was implementing a full-blown cache coherence protocol, to invalidate on write and subsequently fetch the most recent copy of the resource.
comment
created
quinton-hoole
username_4
@username_3 that's the write-through cache that I proposed above.  It sounds like you're also in favor of that.

While the "minimum resource version on get" option is theoretically correct, it does impose quite a burden on less sophisticated client developers.  We will definitely cause a lot of difficult to track down bugs in clients which write and then read dumbly, no matter how loudly we tell developers not to do that.
comment
created
lavalamp
username_2
That sounds quite complex-- does a write on apiserver A invalidate the cache of apiserver B? It must, to be useful, but then we're replicating much of etcd's functionality.
comment
created
lavalamp
username_2
I can see making a correct write-through cache on a single apiserver by just stopping the world until your write shows up in the watch from etcd.

Simply adding the written object to the cache before seeing it in the watch means that you decouple the cache's state from etcd's state and sounds dangerous-but-possibly-fixable in the single apiserver case, and infeasible in the multiple apiserver case.
comment
created
erictune
username_5
Seems like the "semantics" you are worried about changing already happen in an HA cluster?  I think that is what clayton means in his comment about quorum=true (though even with quorum=true a read could still occasionally get stale data I think?)

If so, then isn't option 1 the best choice?
comment
created
erictune
username_5
Also, option 4: 
Add indexer to cache.  Within a single apiserver, queue up pending requests, the do the following:
```
for ever:
   refresh cache and indexes
   while (head of queue is readonly op):
     pop(head) and handle op using cache/index
   while (head of queue is read/write op):
     pop(head) and handle op using direct etcd access.
```

This maintains the "semantics" in the case of a single apiserver, and in the case of multiple apiservers with session affinity (which I predict will become common for larger clusters).
comment
created
erictune
username_5
Option 4 does not require updating the cache bit by bit, and so may be much less bug-prone and easier to implement.

Assuming read operations are 10x to 1000x more common than write operations, then you still get huge batching benefits.

Also, since many writes are going to be status updates, and since the semantics you want to preserve are less relevant for status writes, you could possibly modify the algorithm to handle "readonly and status-only-writing" operations in a single batch.  That would increase the reuse frequency of the cache and indices.
comment
created
lavalamp
username_2
@username_5 I don't see how that works. How does apiserver know that a given
list needs to see a given write?
comment
created
erictune
username_5
In option 4, it conservatively assume that all reads need to see any write.
comment
created
lavalamp
username_2
OK, so that's what I said above "I can see making a correct write-through cache on a single apiserver by just stopping the world until your write shows up in the watch from etcd" + go to etcd instead of stopping the world.

The problem with going to etcd is that it reverts to n^2 behavior for a little bit after every write. Since the time for the cache to see the write should be measured in 100's of ms, I think it may be better to just block everyone until it shows up.
comment
created
erictune
username_5
Okay, what @username_2 said SGTM.
comment
created
smarterclayton
username_1
Yuck.  This still seems like an optimization for infrastructure components
and advanced clients, so forcing clients to be smarter is 100% ok by me.
No one runs list all namespaces who isn't a list watcher and a reflector.
I'd prefer to optimize smart clients first.
comment
created
bgrant0607
username_3
In addition to caching performed by the apiserver, caching is also performed outside it, in clients, but potentially also in intermediate caches.

We do have to make it possible for a client to DTRT in the presence of an arbitrary number of intermediate caches. So, we at least need the resourceVersion-based solution.
comment
created
wojtek-t
username_0
Simply adding the written object to the cache before seeing it in the watch means that you decouple the cache's state from etcd's state and sounds dangerous-but-possibly-fixable in the single apiserver case, and infeasible in the multiple apiserver case.

I completely agree.


So do I understand correctly, that we want to do resourceVersion-based solution first and then possibly implement something more difficult in the future (if needed)? I think that's reasonable.
comment
created
lavalamp
username_2
@username_0, SGTM
comment
created
smarterclayton
username_1
When you say intermediate caches, which ones are you referring to?  Anyone
using an intermediate cache is probably doing so for resilience or
performance, and is by definition a sophisticated client.  The vast
majority of clients have no sophistication.  If we accept multiple
apiservers, DTRT for unsophisticated clients is slow but correct.  DTRT for
sophisticated clients is resource version tracking with resource version
preconditions.  What else do we need?

On Wed, Oct 21, 2015 at 12:29 PM, Daniel Smith <notifications@github.com>
wrote:

> @username_0, SGTM
>
>
comment
created
janetkuo
username_6
This may affect deployment. Deployment needs to keep track of the number of available pods, scale rcs accordingly, and make sure the number of available pods is within a certain range (depends on deployment strategy).
comment
created
wojtek-t
username_0
@username_6 - it will be possible to still list "the current" version from etcd (by setting parameters correctly). So it will not be breaking change.
comment
created
wojtek-t
username_0
The initial version (without indexers) is very close to be done.

However, after some deeper thinking I would like to suggest a slightly different semantics:

1.  if "resourceVersion" parameter is NOT specified for the request (today this is the case for all requests), we still serve this request from etcd

2. if "resourceVersion" parameter is specified for the request - than we only guarantee that the returned result is at least that fresh

 This makes this mechanism backward compatible (which I think is a huge advantage).

 However, to do it, we need to be able to distinguish set & not-set "resourceVersion". And to do it, I would need to change the "storage.Interface":
https://github.com/kubernetes/kubernetes/blob/master/pkg/storage/interfaces.go#L74
so that resourceVersion is passed as string there (not uin64). 

 If we do that - it's easy to distinguish empty and non-empty string (it doesn't work for uint64, because it should be fine to set "0" as resourceVersion if we don't need any guarantees).

@username_2 @username_1 @username_7 - any thoughts on it ^^
comment
created
lavalamp
username_2
@username_0 I agree with your suggested semantics (actually I thought that's what we were going to do originally-- maybe I misunderstood).

Another solution--possibly less invasive--is to make it a pointer so you can pass nil.
comment
created
wojtek-t
username_0
@username_2 - I'm also fine with pointer, but since in the whole system we are using "resourceVersion" as string - see e.g.
https://github.com/kubernetes/kubernetes/blob/master/pkg/api/types.go#L96

it would be more consistent to pass it as string (we will not need any transformations in that case).
comment
created
lavalamp
username_2
By which you mean the transformations can be hidden behind the storage
interface? I think I'm fine with that.
comment
created
wojtek-t
username_0
I think I'm fine with that.

Thanks - I will prepare a PR tomorrow.
comment
created
smarterclayton
username_1
Yes, hiding RV transformation behind storage is right.

Question on 2

- as a controller doing list watch - If I list, I don't specify RV.  I get
the latest.  If I watch from that RV it's extremely likely to be current
(as close as possible)
- as a sophisticated client, if I specify RV, I get RV or newer or an error?
comment
created
timothysc
username_7
While I like this, I wonder at what point can we/should we just be passing a constraint filter to the kV store itself.   

@xiang90 ^ SELECT resource FROM table WHERE (constraint)
comment
created
smarterclayton
username_1
Range scans are part of the etcd 3 API design.
comment
created
wojtek-t
username_0
- as a controller doing list watch - If I list, I don't specify RV.  I get
the latest.  If I watch from that RV it's extremely likely to be current
(as close as possible)
- as a sophisticated client, if I specify RV, I get RV or newer or an error?

I'm afraid I didn't fully understand your question.

[Once this is implemented] if you specify RV in the LIST operation, you are guaranteed to get at least that fresh response. However, you also get the exact RV from which the results is returned. So you can then start watching from exactly that point.
Does it answer your question or I misunderstood it?
comment
created
smarterclayton
username_1
My original concern was a change that breaks naive clients.  I was trying
to validate that naive clients (no rv) are unaffected.  The question about
error was for expired rv versions or rv versions in the future for List.
comment
created
wojtek-t
username_0
Yes - naive clients will be unaffected.

Passing rv for list that is old - will result in returning ~current state (the guarantee that the result is at least that fresh as the rv passed, is then satisfied).
Passing rv that is in the future, will simply block the LIST call until then.
comment
created
smarterclayton
username_1
How long do we block for?  Timeout specified on request?  What error is
returned on timeout (our server timeout error)?

How long do we block for?  Timeout specified on request?  What error is
returned on timeout (our server timeout error)?

On Dec 4, 2015, at 10:44 AM, Wojciech Tyczynski <notifications@github.com>
wrote:

Yes - naive clients will be unaffected.

Passing rv for list that is old - will result in returning ~current state
(the guarantee that the result is at least that fresh as the rv passed, is
then satisfied).
Passing rv that is in the future, will simply block the LIST call until
then.
comment
created
wojtek-t
username_0
How long do we block for?  Timeout specified on request?  What error is
returned on timeout (our server timeout error)?

Currently specific timeout is not supported (other than the default http server timeouts, which is a generic mechanism IIUC). Do you think it's not enough?
comment
created
wojtek-t
username_0
Actually, @username_2 added timeout in #20433
comment
created
lavalamp
username_2
I randomly made it 60 seconds, I think we need to be defensive about clients asking for RVs in the distant future (or from other collections).
comment
created
wojtek-t
username_0
@username_2 - what do you mean by "or from other collections" ?
comment
created
lavalamp
username_2
E.g., reading from /pods, sending that RV to /services.
comment
created
wojtek-t
username_0
That shouldn't be a big deal - resource version is common for all resources (there is a single RV in etcd). I agree that technically it's incorrect, but that shouldn't cause problems in my opinion.
comment
created
lavalamp
username_2
It *does* cause problems, though! See the other commit in #20433. Someone read from one table, passed that (big) RV into list of services. But the service watch RV was stuck at the last service write, *not* the global number--which had since advanced--so apiserver hung on startup.
comment
created
lavalamp
username_2
And anyway, clients need to treat it as separate, because we could swap out the storage, like we do with events.
comment
created
wojtek-t
username_0
I agree that client need to treat is as separate - I just though that it's not urgent...
comment
created
lavalamp
username_2
Anything left to do here? @username_0 can we close this?
comment
created
wojtek-t
username_0
The missing thing here is the Indexer mechanism. But this is definitely not for 1.2 and I think we can create a separate issue for it.
comment
created
lavalamp
username_2
#4817 already exists, we can reuse that. Thanks!
comment
closed
lavalamp
username_2
issue