I'm able to reproduce this reliably in integration test.
I'm going to submit a unit test shortly.

@kubernetes/sig-api-machinery @kubernetes/sig-scalability @xiang90 @philips

I think there's another issue out there for this race already...

On Tue, Jun 7, 2016 at 3:39 PM, Hongchao Deng notifications@github.com
wrote:

@kubernetes/sig-api-machinery
https://github.com/orgs/kubernetes/teams/sig-api-machinery
@kubernetes/sig-scalability
https://github.com/orgs/kubernetes/teams/sig-scalability @xiang90
https://github.com/xiang90 @philips https://github.com/philips

—
You are receiving this because you are on a team that was mentioned.
Reply to this email directly, view it on GitHub
#27004 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/AAnglqZtHhw01q0DTEUlm9DnTVvSsrm_ks5qJfMdgaJpZM4IwbhE
.

@lavalamp You mean #26082? I would wait for @hongchaodeng's reproduce.

Yes, thanks for linking.

On Tue, Jun 7, 2016 at 4:46 PM, Xiang Li notifications@github.com wrote:

@lavalamp https://github.com/lavalamp You mean #26082
#26082? I would wait for
@hongchaodeng https://github.com/hongchaodeng's reproduce.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#27004 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/AAngluCIOx94_cWA-XAsN4Hy4SIfuYi3ks5qJgLVgaJpZM4IwbhE
.

I have some doubts on #26082's description of event sequence. See #26167 (comment)

Let's keep it separated from this issue.

@saad-ali this may be related to the flake you are working on.

The problem is a lack of syncronization between the store and the queue. If you can make a test case that reproduces an error, that would be great. I didn't manage that last time I messed with that code.

Reproduced in unit test. See #27064

@lavalamp
I totally agree.
I think we should keep all the checking, syncing in one place -- the store. Let me sort it out and submit the code shortly.

@lavalamp This should be triaged for 1.3

I read through informer code more thoroughly today. I figure out there is more problems beyond missing Delete events. Resync can return inconsistent data, Replace (on relist) can return inconsistent data, and also Delete. These 3 functions are the ones calling store functions: ListKeys, GetByKey.

@hongchaodeng - what do you mean by "inconsistent data" above? Can you please clarify?

Currently the store is used in delta fifo like this:

Replace, Resync:
    for _, k := range f.knownObjects.ListKeys() {
        ...
        deletedObj, exists, err := f.knownObjects.GetByKey(k)

In this code, there could be new events being processed, data being changed between ListKeys() and iterating, between each iteration of GetByKey().

Things can get weird. For example, I have event A=1,B=1, B=2, A=2, . I could end up getting B=1 and A=2. But I would definitely expect B=2 for a List(). I might get wrong for the use case. But without strong guarantee of consistency, we end up with a lot of workarounds and dealing with complicated code...

Another problem is the interleaving of Resync and normal flow in ListAndWatch() of Reflector, i.e. Replace -> Add/Update/Delete. #26966 is the example of that.

Delete:
    if _, exists, err := f.knownObjects.GetByKey(id); err == nil && !exists {
        return nil
    }

This is what the issue is about.

I don't understand - the whole Replace method is under lock, as well as Add, Update, ...

These cannot interrupt each other...

Replace method is under lock, as well as Add, Update, ...

Not between methods of DeltaFIFO.
There is race that the events are pop()-ed from DeltaFIFO but concurrently processed by informer controller. Thus interleaving sequences of operations might occur.

Sorry - I still don't understand - can you please give some exact example? Like what needs to happen to trigger the race (e.g. on Replace?)

@wojtek-t I think @hongchaodeng is talking about this bug:
#26167 (comment)

On Thu, Jun 9, 2016 at 12:24 AM, Wojciech Tyczynski <
notifications@github.com> wrote:

Sorry - I still don't understand - can you please give some exact example?
Like what needs to happen to trigger the race (e.g. on Replace?)

—
You are receiving this because you are on a team that was mentioned.
Reply to this email directly, view it on GitHub
#27004 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/ACsVaU0nHhHD5ocbBT_EiZaNb86kDm5Bks5qJ7-SgaJpZM4IwbhE
.

Regards,
Chao Xu

Randomly assigning people per thread participation. Please correct assignees as necessary.

I thought about it a bit and to be honest, I don't think we can do a smart small change to fix that.

I think that there are basically two options possible here:

1. spread some really complicated locking all over the code to lock the "knownObjects" (which is unfortunately not owned by the DeltaFIFO in most of cases
2. don't pass "knownObjects" to DeltaFIFO as an argument and instead store the own copy of "knownObjects" internally. Then proper locking would be quite simple in that case, (but it will have a significant memory overhead).

To be honest, I think 1 is not-maintainable. So I would vote for 2. but that's also far from ideal solution...

All accessors to the store are locked today, right? So could we allow DeltaFIFO to start a critical section that also holds the lock? That's kind of like 1, but doesn't DeltaFIFO have a relatively small critical section on the store it needs to borrow?

@smarterclayton - I'm not sure I understand.
The real issue here is "controller framework" is running "DeltaFIFO::Pop()" in a loop and processing what it gets by updating its internal storage (which is also knownKeys in DeltaFIFO).
So basically there is an inconsistency in state of "DeltaFIFO" and "knownKeys" during the period from "when Pop() is already called to the moment that information is applied to knownKeys in the controller".

So the only possibility I can see here is that "Pop()" also returns a "unlock function" which is called by the caller when the even returned from Pop is already processed and in fact this unlocks DeltaFIFO (but this isn't a nice solution...)

This is a perfect opportunity to use PopLockAndDrop() function... :) Jokes aside, is there not a need for Pop to allow another caller to properly hold a lock anyway? We've had this use case in a lot of places where we wanted:

fifo.PopObject(func(object interface{}) error {
  // do something with object
})

that operates under the store lock. The downside is that we'd have to provide to the function the store without locks (since they aren't reentrant):

fifo.PopObject(func(store cache.Store, object interface{}) error {
  // store assumes the locks are already held
  // do something with object
  // do something lock safe with store
})

Wouldn't that allow us to atomically apply changes and talk back to store?

Yeah - I think that passing a function to Pop() should work. And it should be a big change too.

Back when I last thought about this problem, I was imagining having some
mechanism for Informer to get a Locker interface from the store passed in.
Then I think you just need a mechanism so the store doesn't double-lock
when Informer e.g. calls Add. I agree it's not a trivial change.

On Mon, Jun 13, 2016 at 8:57 AM, Wojciech Tyczynski <
notifications@github.com> wrote:

Yeah - I think that passing a function to Pop() should work. And it should
be a big change too.

—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#27004 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/AAnglqWsLDO3WuCJfdEF61aPgB8HOMP6ks5qLX3hgaJpZM4IwbhE
.

Sorry - I actually wanted to write that passing a function to Pop should NOT be a big change...

@lavalamp do you think it's a bad idea about passing a function to Pop()?
Your suggestion seems much more difficult (and would require much more work).

I guess I don't know that just changing Pop can fix this-- I thought the
problem was with putting stuff into the queue, not taking it out. If you
can fix it by passing a function into Pop then by all means go for it. I
think @hongchao has a repro test case you can use to see if it works.

On Mon, Jun 13, 2016 at 9:30 AM, Wojciech Tyczynski <
notifications@github.com> wrote:

Sorry - I actually wanted to write that passing a function to Pop should
NOT be a big change...

@lavalamp https://github.com/lavalamp do you think it's a bad idea
about passing a function to Pop()?
Your suggestion seems much more difficult (and would require much more
work).

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#27004 (comment),
or mute the thread
https://github.com/notifications/unsubscribe/AAnglvS1t6mkIAJRUe7L8i09KF8f6TS4ks5qLYW4gaJpZM4IwbhE
.

I have tried several alternatives to solve the problem, including all kinds of weird locking mechanisms. It only gets the codebase super complicated and coupling DeltaFIFO queue and store more.

There is fundamental design flaw in current informer.

As shown above, the controller gets events from DeltaFIFO and process events to update the store, notify handlers. But there is another place handling events as well. The DeltaFIFO also does logic on (re)listing store, checking if items is in store, etc. The design doesn't make sense if we want to achieve serializability on operations on single store!

The design should be:

The queue is just queuing events. No more operations about store should be done there.
The controller should be the single master that has control over queue, store and serialize all operations here.

I have tried a prototype of rewriting the informer in this way. It's a joyful experience with more maintainable code. (I have also found design problems in reflectors. But it's another issue.)

#27341 is supposed to fix this issue

@wojtek-t I think #27341 is solving a different problem from the one described by @hongchaodeng. The original problem reported in this issue is that some code in DeltaFIFO is written under the impression that DeltaFIFO.knownobjects is reflecting the latest watch events, but in fact, the DeltaFIFO.knownobjects only reflects the objects that have been processed, that is, not including the deltas that are still in DeltaFIFO.items.

We know this causes at least two issues:

1. this issue: the check in the DeltaFIFO.Delete() should also check DeltaFIFO.items to see if the object exists after all the queued deltas are applied.
2. Fix race between periodic sync and delete event. #26167, in DeltaFIFO.Resync(), we should only sync the objects that still exist after all the deltas in DeltaFIFO.items are applied.

Here is the interaction flow between the queue and store:

What @caesarxuchao is questioning are valid concerns. Basically, in Relist, Resync, there are still interactions (mostly getting).

Having dredged through that code during our resync adventure, I'd give a +1 to @hongchaodeng's idea. But I'm not in favor of making such a change until 1.4...

@caesarxuchao - thanks for comments; those are valid points;
However, those issues are easy to fix - those can be easily fixed in the DeltaFIFO itself. I can send a second PR tomorrow (that will fix those two).

Thanks @wojtek-t!

@timothysc
We have been digging in controller and informer to do profiling. It's also our v1.4 goal to do it and other optimizations.

@caesarxuchao - in fact, those two issue that you described were bugs, not even races.
Sending PR that is fixing it now.

/cc @sdminonne