Lwt: Mvar read

[kydos]

In my experience at times it is useful to access the content of an Mvar w/o taking it and letting other concurrent computation consume the value in the mvar. Today one is forced to do a take/put which works out, but perhaps the read operation could be implemented in a far more efficient manner.

[hcarty]

Edit: Removed in favor of follow up comment.

[hcarty]

So, I thought this had been discussed previously. And it was: https://github.com/ocsigen/lwt/issues/443

At the time, the consensus was that adding such a function would be a violation of an mvar's expected behavior.

[aantron]

Perhaps we can add a peek function. The argument against it was that it breaks an assumption that only one reader ever "gets" any one value from an mvar. It would be nice to keep this. However, if the user of Lwt_mvar wants to break it, perhaps we should allow it. We can document this under peek, so that the user understands that without peek, Lwt_mvar provides stronger logical guarantees.

cc @raphael-proust

[kydos]

Let me share our use case to motivate some of the suggested changes. Imagine you have a protocol router that has to dispatch incoming messages. Suppose that the design relies on an immutable state that is kept in a mvar. The forwarding of data-plane messages does not require any mutation thus it would be extremely useful to have a peek. However concurrent handling of control-plane messages order their changes by leveraging the semantics of the mvar. For us it is essential that the forwarding of data plane messages is as efficient as possible, thus the wish for something like a peek. Does this make sense?

[aantron]

It's still a bit abstract, but I think I see what you mean.

Would you be willing to create a PR that adds a Lwt_mvar.peek : 'a t -> 'a Lwt.t? (Or do you want 'a t -> 'a option? In that case, it should probably be peek_available to match the existing take_available).

I'll add docs about the property of Lwt_mvar that using peek "violates" to it afterwards :)

[aantron]

Looking at it more deeply, however, I'm not certain about the semantics of peek. With take, one reader is awakened. How many readers should be awakened with peek? It seems like you would have to awaken readers until one of them does a take. However, what if all readers are using peek? What if one reader is doing peek in a loop? It may be possible that you need Lwt_stream instead of Lwt_mvar.

[kydos]

@aantron, I think we should only provide a peek_available : 'a t -> 'a option as this solves the problem of waking up -- since peek_available never leads to sleep and makes the semantics a bit simpler to implement. When peek_available returns None then there are really two approaches, resorting to a take/put couple or busy waiting with a yield statement. In any case having an extremely efficient peek_avalilable would still improve performance in "read-dominated" computations such as in our broker.

What do you think?

[aantron]

peek_available definitely suffers from less issues than peek :)

However, that we need to either busy-loop in case of None, or use a take/put pair suggests that there is no "good" interpretation of what to do in response to None; I couldn't easily come up with one either. Essentially, this treatment of None means that peek_available becomes peek, just the user has to implement the waiting part. And that leads to the same question, which is how much polling should be done on a value that is not taken out of the mvar? I guess that the user implements the wait at least allows us to rely on an application-specific answer to that question, but that also makes me suspect that this means that peek/peek_available might not belong in the library.

This makes me suspect that Lwt_mvar almost addresses your need in this use case, but not quite, and we might not be able to make it work fully. I suggest looking at these other options to see if they fit better:

• React.S (signals), with Lwt helper Lwt_react.S.
• Lwt_stream.
• lwt-pipe.
• Something custom built with either Lwt_condition and Lwt_mutex, or just directly using Lwt.t.

[kydos]

@aantron when I mentioned the busy-loop or the take/put thought that this is what the client code would if in case it would get a None. In any case the user of the Lwt_mvar is in a better position to know what would make the most sense.

I am familiar with Lwt_stream and it's bounded version. In fact one could indeed emulate the MVar with a bounded Lwt_stream of length 1. The peek problem would also be solved. I'll do some experiments and will let you know.

Lwt_react.S and lwt-pipe I am not familiar with, but will take a look.

Thanks for your suggestions!

[aantron]

My guess is that React.S will be the most "right."

The fundamental difference between Lwt_mvar and all these other options is that Lwt_mvar has a queue of readers, and wakes up readers sequentially, one at a time, one reader in response to one write.

By contrast, all the other synchronization primitives have a list of leaders, and wake all of them up concurrently in response to writes.

The problem with Lwt_mvar and peek is basically a question of how should peek interact with the reader queue. None of these other data structures have a reader queue, since they wake all readers. So, there is no question :) And that's why they all have a reasonable interpretation of peek.

[kydos]

@aantron I just recalled that the bounded Lwt_stream fails the when a push is tried on a full stream on which a push is already pending. This is not very convenient in our case and, know that I gather my memories, is one of the main reasons why we had picked Lwt_mvar instead of streams.

For our use case having a peek_available that may returns None if there is nothing to peek and let the caller deal with this eventuality would be quite useful.

[aantron]

Ok, let's add it :) Would you be willing to create the PR, or I shall I do it?

[kydos]

@aantron happy to create the PR, but I've not looked yet at how this could be implemented in the Lwt_mvar implementations. In any case it would be fun to learn more about Lwt's internal, thus I can try to come up with a proposal if you want. Please feel free to suggest were I should be looking if you already have an idea of how to implement this.

[hcarty]

@kydos You can probably start from the take_available definition. In fact, it may be enough to have the function directly return the current mvar_contents value.

It's definitely worth reading through the lwt_mvar.ml implementation to learn a bit more about the internals if you have time to do so! It's a small but interesting block of functionality.

[aantron]

@kydos, the implementation is actually really simple. I think you can basically copy/paste take_available, which @hcarty linked to, and delete the call to next_writer. Should probably add tests, to make sure we are not overlooking anything.

[kydos]

@aantron and @hcarty thanks very much for the suggestions. I'll try to get the PR done by this week. I'll also let you know what -- if any -- performance improvements we see on our broker.

[raphael-proust]

In order to have a peek function, we could also have two distinct readers set:

• the readers queue is left as is
• a bystander_readers list is added

When an element is read, all the bystanders are woken up with the value and then one of the readers is woken up. If we see mvars as way to manage ownership (one writer transfers to one reader), then the new set of observers receive borrowed versions. (Of course, there's no enforcement of what readers do with the value, it's just a convenient way to think about it.)

[raphael-proust]

Proof of concept: https://github.com/raphael-proust/lwt/commit/5c229143978771a2fdf54eb39d55084131f1e178

Although I'm not confident I got the reader-writer-borrower dance right.

[aantron]

Nice, that's a good idea.

I'm still concerned, though, about what happens when one calls borrow in a loop while there is a value in the mvar, that remains.

Perhaps we need a borrow/peek but also a borrow_next/peek_next function, which always "blocks" until the next write, even if a value is already available?

In combination with peek_available, this would allow a peeking reader to check if there is a value now, use it if desired, then go to "sleep" until the next time something can be peeked, if needed.

In fact, it seems that these are the two primitives that are needed, and an ordinary borrow/peek is not needed.

What does everyone think?

[aantron]

I guess one issue with peek_available+peek_next is that there is a race condition, where if a reader does peek_available, then some Lwt I/O, and then should want to do a peek_next, a writer may already have written into the mvar in the interim. The reader has no way of knowing that the writer has done this, so if the reader does peek_next, it will skip the latest new value and wait until the next one.

Perhaps we need to return some kind of generation counter from peek_available, and that counter can be passed back in peek_next. If the counter is still the same as the counter stored in the mvar, no write has occurred, and peek_next waits. If the counter has since been incremented in the mvar by a write, peek_next returns the current value immediately, if available.

This suggests that we need a peeking "view" type, which will abstract away this counter.

There may be a better way of solving this, or an argument that it's not necessary to begin with.

[raphael-proust]

How about: peek: 'a t -> 'a option * 'a Lwt.t which does both peek_available and peek_next at the same time? It returns a value (if there is any) and a promise for the next write. Or borrow: 'a t -> ('a, 'a Lwt.t) either which returns either the immediate value (if any) or a promise (otherwise).

In both case, it should be able to stall a borrower loop. There might still be race conditions in tricky cases but I'm not sure. As long as all the borrowers/readers resolve before next_writer then it should be ok? I think?

I'm also concerned that someone might see this function and think that the signature would be useful and then they only use borrowers and no readers and the mvar gets stuck. I guess documentation can help with that.

[raphael-proust]

Untested proof of concept https://github.com/raphael-proust/lwt/commit/ce85143cebf1ce023f1886502a637b5b3b1278d6

[rneswold]

Does a ref handle this use-case?

[raphael-proust]

The issue is if you want a peeker when accessing the value from a specific part of the code but you still want the writers/readers dances of an Mvar for other accesses.

If you want only peekers, then yes, a ref works.

[raphael-proust]

@kydos Are the proposed changes ok for your use case? Basically it adds

val peek : 'a t -> 'a option * 'a Lwt.t
(** [peek mvar] is [v, p] where
    - [v] is
        - [Some w] if [mvar] is currently holding a value (i.e., if there has
        been more [put] than [take]), or
        - [None] otherwise; and
    - [p] is a promise for the next value written onto [mvar].
    Usage note: [peek] does not remove value from the [mvar]. You need to use
    [take] in order to allow further [put] to resolve. *)

One thing that would be needed before a merge is an explanation of what happens if you call peek again when the promise resolves. Specifically whether you can observe the same value again (current implementation) or not.

[aantron]

Closing due to lack of feedback. Please reopen if needed.