kvs_watch() can miss values due to merged commits

[garlick]

The kvs commit code attempts to merge contemporaneous commit requests to minimize intermediate directory versions landing in the content store and kvs.setroot event handing.

If a key changes in two commits and those commits are merged, only the last in value will be committed, and thus the kvs.setroot triggered watch response will be generated only for the last value.

[garlick]

Considering that the root of the namespace can be the target of a watch, commit merging is fundamentally at odds with the goal of getting a watch response for every change of every possible watch target. Commit merging should be disabled in the KVS and we should look for other ways to recoup the performance lost.

[garlick]

As a first step let's make this configurable so we can see what we're dealing with performance wise.

[chu11]

@garlick Now that I understand the KVS code atleast medium well, I was trying to figure out "passing args to modules", when I saw this. It seems that an option to make commit merging configurable already exists? Unsure if you were thinking of something different.

static void process_args (ctx_t *ctx, int ac, char **av)
{
    int i;

    for (i = 0; i < ac; i++) {
        if (strncmp (av[i], "commit-merge=", 13) == 0)
            ctx->commit_merge = strtoul (av[i]+13, NULL, 10);
        else
            flux_log (ctx->h, LOG_ERR, "Unknown option `%s'", av[i]);
    }
}

[garlick]

Oops, well... does it work? (I must have forgotten about that when I opened the issue)

[chu11]

Code review wise, it appears it does. Although I don't see any tests for this yet.

[garlick]

A test addition for the option would be welcome.

How we want to deal with the bigger problem is an open question.

To put a finer point on the situation: a kvs_watch() response will always be generated when a watched key changes. The problem is that if it changes more than once in a (merged) commit, the "middle" watch responses are not generated (since they are overwritten within the commit they are not even stored) and the intermediate values are lost to the watcher. In other words you'll be notified of the last value in a series of changes.

If you're watching a state machine where the current state is represented as the value of a key, as learned the hard way by @dongahn a while ago, some state transitions may be lost. There are ways to work around this but the behavior is unexpected and feels inconsistent with the transactional design.

A partial "solution" to this problem might be to add an optional "no merge" flag param to kvs_commit() to disable merging for that commit only. Then if you were doing something like the state machine example you could at least have straightforward way to address it.

[garlick]

Actually, a better proposal might be to add that flag to kvs_put(). Then the commit could still be merged with non-conflicting commits.

[chu11]

Yeah, my first goal was to try and add some tests. Not sure if I can kludge t/kvs/commit.c to do what I want. I'm thinking multiple commits to same key w/ a fence and a separate watcher thread to watch would probably suffice.

[dongahn]

@garlick: Yeah, JSC is now essentially a thin layer of flux events, not using the watch capability. So this is not a problem.

Introducing a parameter tokvs_put so that kvs users can avoid any block spot for that key if and only if they need it seems like a great compromise. Perhaps 99% of kvs users don't have to use this (e.g., write and forget) while enabling 1% of the users to do what they need. Hopefully, introducing this parameter doesn't add too much overhead to the critical path to general commit performance, though.

[chu11]

@garlick Been working on a KVS test to see if the commit-merge option is working. When commit merging is disabled (flux module load -r 0 kvs commit-merge=0), the test is basically create a thread with a watcher that will watch for (lets say) 8 changes to a key. Then another 8 threads are launched each doing a single put & commit to the same key with different numbers in each thread. So I would expect the watcher thread to eventually get 8 notifications that a key value changed.

I often get less than the 8 notifications. It appears on occasion that a change has simply been missed and a watch notification isn't sent (or isn't received?). Is it possible if lots of commits occur quickly that a watcher could "miss" a commit? Lots of debug statements in the KVS commit side of the code, and I think that part is working properly. Beginning to look at the watcher side b/c no idea how that works.

Hopefully I didn't do something obviously dumb.

Test is t/kvs/commitwatch.c if you're curious. https://github.com/chu11/flux-core/tree/issue813

[chu11]

@garlick Ugh, I'm stupid ...

for (i = 0; i < watchcount; i++) {
     kvs_watch_once()
     parse & print out what I got
}

multiple commits can occur on the kvs side during the parse & print part of the code.

[garlick]

Oh right, you'll want a regular watch there that gets a stream of responses, one per change.

I didn't quite understand why you sometimes do a fence in this test? Commits to the same key under a fence are guaranteed to produce only one watch response. Or was that the point?

[chu11]

The fence is only when running a test when --merge is specified, which should only be done when the kvs module is loaded with commit-merge=1. That's the test to make sure commit merging is working.

[garlick]

What's the purpose of using the fence there? The fence builds a single commit until nprocs have called kvs_fence() to make their contribution, so that won't exercise the commit merging optimization in the KVS master. (Apologies if I'm stating the obvious and have missed what you're intending!).

[chu11]

@garlick Ahhh. I now see what you're saying. My original intent was to make a test to verify merging works with commit-merge=1 and fencing seemed like the way to "force" merging. But you're right, the fence merges all those commits into one, the commits are not actually merged later on in the commit_merge_all function.

Hmmm. Any thoughts on how one might be able to guarantee a merge happening?

[garlick]

Hmmm. Any thoughts on how one might be able to guarantee a merge happening?

Hard to do since it requires multiple commits to arrive in the same reactor loop.

Crazy idea: add a flag to the commit message that, purely for testing, instructs the master to break up every operation into its own commit. Then you'll be guaranteed to have put them all queued up in the same loop that the commit message was received...

[dongahn]

Is it a possibility to introduce a testing hook into the prepare watcher to sync with the external test committers? The prepare handler only returns when the external testers finish sending their commits...

I also wonder if one can test this with some statistical guarantee as opposed to deterministic guarantee. Just random houghts.

[chu11]

@garlick Are you thinking of a flag variable one might pass to kvs_commit?

@dongahn The statistical thing was something I was thinking about. For example, launching 100 commits and getting < 100 watch responses. But it of course isn't guaranteed.

At some point this one unit test may be more work than is worthwhile. At some point we just grep the broker log to make sure a commit merge occurred :-)

[garlick]

I agree probably too much work for too little gain.

(To answer your question, I was thinking just change the protocol and create the message manually. Yep, too much work)

[chu11]

Yeah, I uncommented some of the debugging in the broker and just manually checked the broker log to make sure the option was working. So that would probably be the simplest thing to do if an actual unit test were made.

[dongahn]

@dongahn The statistical thing was something I was thinking about. For example, launching 100 commits and getting < 100 watch responses. But it of course isn't guaranteed.

At some point this one unit test may be more work than is worthwhile. At some point we just grep the broker log to make sure a commit merge occurred :-)

Maybe this should be the way. A tester sends n consecutive commits rapidly and check at least one a commit merge happens. If n is big enough to overcome network delays etc, this should happen with a high probability. Converse, if the tester send m commits each with k interval in between where k >> the merge window, statistically speaking you shouldn't see a merge... Well, PASS/FAIL can still be non-deterministic. Maybe the testing results are the numbers, not PASS/FAIL..

[grondo]

Thinking about a way to test these difficult to reproduce timing conditions or corner-cases in general is a good idea. Lots of systems have separate interfaces for testing (e.g. something like the test-only commit flag described here, or better yet a separate kvs.test.* set of interfaces), or perhaps there is some kind of general interface or debug mode we could design that could be useful in more than just a single service? (e.g. would it be helpful if there was a way to "pause" a service, queue up messages, then "restart" -- or do something similar with perceived advancement of time?) Similarly, a "trace" interface might be useful during testing.

Sorry if that is out of left field, but perhaps a larger issue could be created if it is of interest.

[chu11]

@dongahn The other consideration I had was that some "timeout" would have to be added to the test, such that we can assume no additional watch events appear. So that also adds a pause into the unit tests that I disliked. I suppose one here and there is ok, but we wouldn't want to start adding of ton of them.

[chu11]

Thinking about this a bit last weekend, I may need a special feature for testing otherwise testing the final solution (such as Jim's suggested flag to kvs_put or kvs_commit) may be difficult.

I'm now thinking, I could add a special msg handler in the KVS, say kvs.test.pausecommits, that could temporarily pause all commits from working. By pausing, we can easily control the ability to test/not test commit merging.

[chu11]

Ugh, only after playing around with the above idea, did I realize that with such a pause in committing will make a kvs_commit() call hang ... so basically by delaying some commits from happening immediately, it helps increase probability that a commit merge will occur. But again it doesn't guarantee it. Oh well.

[chu11]

Tried to experiment with kvs_put() with a "don't merge" flag and I hit a snag. If a kvs_commit() call contains multiple puts (e.g. a=1 and b=1), if one of the puts is flagged as "mergeable" but the other is flagged as "un-mergeable", during the commit-merge phase, the two would have to be split out of the same fence_t structure. There's various fallout of from this, such as should multiple rpc responses be sent on each commit? Or should there only be one response and thus internally it'll have to know when the "last" put was commited?

Could be solved several ways, but I think the most reasonable is to add the "don't merge" flag into kvs_commit instead. All puts within a single commit should be mergeable or un-mergeable.

[garlick]

Or maybe if any puts in a commit have the unmergeable flag, then the whole commit should be considered unmergeable?

[chu11]

Had considered that, but how different is that from passing the flag via kvs_commit() instead? Internally, some looping over the puts ops would have to be done to find merge/no-merge flags.

Perhaps there as an API usage subtlety that would make a flag in kvs_put() favorable?

[garlick]

My apologies - I kind of lost track of what we're doing here when I responded last. What's the purpose of the flag you're now working on? We talked about a couple different things: one was an API extension that would prevent certain keys from being merged (useful for state machine use case). The other was a test flag that would break up puts within a commit into separate commits that are likely/guaranteed to be merged.

[chu11]

Ahhh, I'm talking about the API extension flag. So here's figuratively what I was thinking above:

kvs_put ("a", "1", MERGE_FLAG);
kvs_put ("b", "1", NO_MERGE_FLAG);
kvs_commit ()

Internally, the a=1 and b=1 are added to the same fence. If we were to allow puts on the same commit/fence to be mergeable and unmergeable, then there is various fallout from that, as the fence has to be "split up" to some extent.

So my initial feeling is we should put the merge/unmerge flag in the commit instead.

kvs_put ("a", "1");
kvs_put ("b", "1");
kvs_commit (NO_MERGE_FLAG)

saying all the puts within a commit/fence are mergeable or unmergeable. They can't be mixed.

Your suggestion above (assuming you were talking the API extension) "if any puts in a commit have the unmergeable flag, then the whole commit should be considered unmergeable". To me, this seems not much different than simply moving the flag to the kvs_commit() instead??

[garlick]

Ah, thanks for clarifying.

I would assume you'd only want one flag to prevent merging, with the default being "try to merge if merging is enabled and there happen to be multiple commits pending".

My thought above was that there might be an opportunity to do more merging if the flag were associated with individual puts. A commit containing a=1 with the nomerge flag, and another containing b=1 with the nomerge flags could be merged since no value of a or b could be lost if the two commits were merged. However, I think there are some corner cases to handle if done that way, such as if one commit contained "a.b.c=1" (nomerge) and another contained "unlink a". There's not too much to be gained by doing it this way anyway, so my vote would be for the commit flag.

[chu11]

Your example made me think of a potential issue. Example of three commits that come in in this order and are queued up at the same time:

commit 1 is mergeable: A=1
commit 2 is mergeable: A=2
commit 3 is mergeable: A=3

In this case, the three get merged, and the only watch notice that is sent out is A=3. But lets say we have this.

commit #1 is mergeable: A=1
commit #2 is not mergeable: A=2
commit #3 is mergeable: A=3

Hypothetically, we could merge commit #1 & #3. So there would be two watch notices, A=3 and A=2. The final setting would be A=2.

This doesn't seem right to me. Should unmergeable commits act as a "barrier" of sorts? Where you cannot merge any commits that cross an unmergeable one?

[garlick]

So there would be two watch notices, A=3 and A=2. The final setting would be A=2.

Hmm, yes I think you're right, only "adjacent" commits should be mergeable so the order is preserved. For now anyway. We may have to introduce some new semantics for ordered requests once we implement overlay self-healing.