reconciler: Provide ability to check if updates up to a certain revision has been reconciled

[gandro]

In Cilium, various policy related subsystems need to wait for datapath updates to be plumbed through before certain other actions can happen. For example, DNS responses that allow IPs in a toFQDN policies only must be released once the IP's identity has been added to the BPF policy map. Another usecase is metrics, where it would be interesting to know how long it took for a certain revision of the table to be reconciled (which might expose potential bottlenecks).

When using the generic reconciler to reconcile BPF maps, this is currently very hard to implement such as logic on top of the reconciler API: Simply checking if the table has no pending entries is not sufficient, since deletions might still have to be reconciled. In addition, retries make it hard to track progress via the Operations interfaces, since it basically requires the tracker to track what retries are still in flight (and detect if they have been cancelled).

Therefore, it would be great if the reconciler had the built-in ability to check if all changes up to a certain revision have been reconciled. This could take the form of a callback mechanism, e.g.

type Reconciler interface {
    OnRevisionReconciled(rev statedb.Revision, callback func(statedb.Revision))
}

[joamaki]

Here's some thoughts:

1. Callbacks in that form I think aren't enough as we need cancellation and completion, so I'd do Observable[Revision] instead if we go with something like this. Asking for callback on specific revision being reconciled seems way too much book-keeping overhead to me (unless it comes with the Status, but then I wouldn't use callbacks, see point 5.).

2. As I want StateDB and reconciler to be as safe and resilient as possible, I don't want the callback to have the ability to block or slow down the reconciler, hence the implementation will need to be decoupled, e.g. maybe via cond variable and separate goroutine (pain to implement cancellation, but maybe periodic ticker to wake up or we can use https://pkg.go.dev/v.io/x/lib/nsync#CV.WaitWithDeadline)

3. I would much prefer avoiding callbacks if at all possible though and instead of pushing have whoever is interested pull the revision (via atomics). This works fine for tracking what's the lowest revision on updates as we can use the watch channel on the table to get triggered to check it (since status is written back by the reconciler). Deletions we don't get a trigger for though so something else is needed. One option is to keep a watch channel inside the reconciler that gets closed&swapped every round (it would mostly cost a heap allocation, so likely ok, need to benchmark). With that we can have ReconciledRevision() (statedb.Revision, <-chan struct{}) which gives the caller the ability to decide when to check (which is a property I really like).

4. To implement this sort of indicator of "lowest revision reconciled" we need a min-heap in addition to the retry queue so we know what's the next smallest revision in the retry queue. So this is more complicated to implement than it seems.

5. While the normal way of looking up changes in objects (wait for watch channel and requery) works for checking if an update to an object has been reconciled, it indeed doesn't work for deletions. One way we could solve this would be to introduce StatusPendingWatch() (reconciler.Status, <-chan struct{}) and store a watch channel inside the reconciler.Status. This channel would be closed when an Update or Delete on it succeeds (or if it fails as well? coming up with good semantics might be tricky). It'd be an extra 8 bytes on reconciler.Status but other than that it'd be opt-in. This might be a better way to deal with the situation like FQDN where we need to unblock a response in a timely manner as we get a signal per object (otoh there I think we don't that much care about deletions...).

[gandro]

Answering a bit out of order:

e.g. maybe via cond variable and separate goroutine (pain to implement cancellation, but maybe periodic ticker to wake up or we can use https://pkg.go.dev/v.io/x/lib/nsync#CV.WaitWithDeadline)

I suggested a callback exactly because I originally experimented with an approach where I had a condvar and one go routine per "wait for revision" query. I think for the metrics use-case that is too much overhead.

I'm fine with it being observable instead of a callback, but I'd like to avoid having to spawn one Go routine per queried revision.

--

The use cases I have in mind all boil down to:

0. Control plane detects that some state needs changing
1. Control plane opens a new write transaction
2. Control plane issues a set of updates and deletions
3. Control plane commits transaction (at revision X)
4. Control plane wants to delay a certain action until the reconciler has reconciled (or cancelled) all updates in step 2

I think this is a really common pattern.

To implement this sort of indicator of "lowest revision reconciled" we need a min-heap in addition to the retry queue so we know what's the next smallest revision in the retry queue.

Yes, but if we don't do that, then we are just offloading the bookkeeping to the client. Someone has to do the work.

Let's take the Status channel proposal for example: If the control plane has to wait on a set of channels, then the control plane has to keep track of what entries it touched in step 2 to collect all channels. It then needs to also poll all of them and wait for them to complete. In particular if it issued a lot of updates then it needs to manage lots of entries.

From the control-plane's perspective it would be much simpler to obtain the final revision at step X and ask the reconciler if that revision has been processed.

In particular, the reconciler would only have to track retries, which arguable a much smaller set than the total set of updates and deletions that the control-plane would have to track.

So this is more complicated to implement than it seems.

I absolutely agree. I've played around with multiple implementations on top of the Operations interface and I didn't like any of them. However, I strongly believe that exactly because this is a non-trivial problem to solve that it should be the reconciler who does it, rather than offloading this error-prone logic to clients instead.

[joamaki]

Hmm one way to do this that wouldn't need much additional state would be to keep a "watermark" of the highest succeeding revision and then after each reconciliation round update this by iterating over the objects starting from the previous watermark and finding the new highest with non-pending status.

Iteration is quite fast and if we set this up so that we only iterate when there was a failure then this should work pretty well.

One tricky part is that each reconciliation attempt updates the object and thus assigns a new revision to it. So probably should consider the revision of the object in which it was marked as "Pending" as the one that's looked at. This all can still be pretty confusing though, especially if the object gets updated again as pending from potentially other source than the one waiting for it to be reconciled. E.g. does a subsequent update of the object before it had been reconciled mean that that old revision is now reconciled "successfully"? If not then again we need to keep track of the revisions of every object with Pending status and then "reassociate" to a newer revision.

The watermark could be exposed as an atomic.Uint64 that can be polled. I would prefer avoiding any blocking constructs (callbacks, channels, stream.Observable) as a misbehaving implementation could block reconciliation. Could also do condition variables if we want to avoid polling.

EDIT: Hmm now the revisions are starting to feel like the wrong thing to latch onto and something "WaitGroup"-like associated with the Status would make more sense. Would that be manageable for the control-plane? It'd create a "ReconciliationWaitGroup" that it'd use with StatusPending() to add to the wait group and after all the inserts it'd wait for it to finish. The API would have to be such that we can't just overwrite a previous Pending status (which the reconciler may have not seen yet) and forget to mark the old wait group as done.