[ANN] Miou, a simple scheduler for OCaml 5

[dinosaure]

I’m pleased to announce the experimental release of Miou (0.0.1~beta1): a round-robin scheduler for OCaml 5. Miou is a small library that focuses on implementing system & network applications.

You can now find the project on GitHub, Robur’s repository, as well as its documentation and a few tutorials. You can install it via opam: opam install miou. It requires at least OCaml 5.0.0. This release was marked by the implementation of a happy-eyeballs/dns¹ client combining concurrency and parallelism. The aim is to be able to continue implementing services using this library and to guide the user/developer towards good system practices.

The project is still in an iteration phase with the implementation of services such as dns and email in order to validate our design. This release invites you to iterate with us to benefit from everyone’s experience.

We will complete this thread with articles specifying the implementation of Miou. The documentation gives a good overview of our objectives and the Miou framework. If you are interested, we invite you to read it.

We would like to thank everyone who has been involved in any way in the project for their experience and their contributions. And we hope to consider other experiences and feedback in order to develop Miou in the same way as Robur has already done for the other projects.

---

1: Implementing happy-eyeballs via the excellent ocaml-dns project has enabled us to:

1. check that it is possible to launch a background task managing connections without being able to detach a task
2. satisfy the notions of socket ownership
3. implement a real application using one of the protocols we maintain

[UnixJunkie]

I think it’s “round-robin”.

[Phil_Tomson]

Unless it’s supposed to be a play on work stealing? Then it should be spelled ‘round robbing’.

[dinosaure]

Yeah, it’s a round robin scheduler, sorry for the typo .

[zapashcanon]

How does it compare to eio ?

[dinosaure]

I’m thinking of detailing the reasons why we set out to make Miou knowing about Eio’s existence. But I’ll give a quick description of the differences.

Miou has had several iterations internally and one of them was very close to what Eio can offer. But an informed choice was made to implement a round-robin scheduler to better match our objectives in order to implement services (dns, email, http, etc.).¹ In this respect, and as far as I know, Eio has never described a scheduling policy so formally.

Miou drew a lot of inspiration from affect when it came to composability. This is a question that Eio tried to answer with objects (but it seems, for obscure reasons, that this is no longer the case). As far as we’re concerned, affect and lwt (with lwt.unix) seem to be the right compromise for us, developing unikernels and unix applications. We do not wish to incorporate the idea of capabilities.² We just propose miou (the heart of the library) as well as miou.unix for the development of unix applications.

Finally, on a slightly more social subject, where there is perhaps no difference but which we would like to make clearer, we would like to keep development minimalist but commit ourselves to the long-term maintenance of Miou, while leaving room for other people to complete what may be missing from the Miou framework. In other words, predating on community spaces in order to create a monopolising piece of software is certainly not our goal.

Once again, there are some fundamental technical differences (such as the use of Effect.Shallow instead of Effect.Deep). But I’m going to write a few articles to clarify these differences and, more importantly, their implications. What is certain is that Miou is no better than Eio (or worse, depending on your point of view), it completes the multiplicity of solutions in a fundamentally erratic world .

---

1: There isn’t just one type of scheduler for any application. In addition, we would certainly advise you to use moonpool for certain applications. The fact that we have formally assumed the implementation of a round-robin scheduler allows us to identify and describe the drawbacks of this type of scheduler in detail (because there are some in all the proposed solutions).

2: We weren’t convinced by the choice of capabilities or the new methods for injecting a backend. We’ve experimented with them at several levels (passing through values, functors, variants, etc.) with unikernels and they can be very powerful for certain uses but too complex for others. In a use that would inevitably become systematic (since we’re talking here about the scheduler - a central element in your application), the old design of lwt (and lwt.unix) seems to us to be the simplest and sufficiently expressive for the development of unikernels (on which the POSIX interface is unavailable): c’est dans les vieux pots qu’on fait les meilleurs soupes.

[talex5]

Just to clarify a few things here:

But an informed choice was made to implement a round-robin scheduler […] In this respect, and as far as I know, Eio has never described a scheduling policy so formally.

Eio keeps a queue of runnable fibers per domain, so for pure computation it is always round-robin. For IO, it is up to the backend how to schedule IO, and backends could allow some sources to be prioritised. However, all current backends just do RR too. For example, here’s a test case reading from /dev/zero (which should never need to block):

open Eio.Std

let ( / ) = Eio.Path.( / )

let () =
  Eio_main.run @@ fun env ->
  Eio.Path.with_open_in (env#fs / "/dev/zero") @@ fun zero ->
  let test l =
    let buf = Cstruct.create 10 in
    for _ = 1 to 1000 do
      let got = Eio.Flow.single_read zero buf in
      traceln "%s: read %d bytes" l got
    done
  in
  Fiber.both
    (fun () -> test "A")
    (fun () -> test "B")

You should find that the output alternates:

+A: read 10 bytes
+B: read 10 bytes
+A: read 10 bytes
+B: read 10 bytes
[...]

I get this output for both the eio_posix and eio_linux (uring) backends. If you don’t see that, let me know; it’s likely a bug.

Once again, there are some fundamental technical differences (such as the use of Effect.Shallow instead of Effect.Deep).

Note that the choice of how to handle effects is up to the backend in Eio. All current backends do use Deep handlers, indeed (I have no strong opinions about this and am curious to know if shallow handlers would offer some benefit).

[dinosaure]

If we’re talking about a round-robin scheduler, you need to specify a quanta. Suspending a task doesn’t just depend on whether you want to suspend it. You must have a limit that suspends the task independently of the state of the task - which is, in general, time.

The availability of tasks to receive system events depends on this limit - you can’t assume that a task waiting (for a connection, for example) is more likely to be executed than another task waiting (for a packet). The important thing is that A or B have the same chance of receiving events (whether they arrive immediately or in an hour’s time).

So what is the quanta for Eio?

[patricoferris]

Cool library! I’m very happy to see different schedulers because I think the space is still so new it’s good to explore it and find the good bits and the limitations of different designs and ultimately everyone is free to use the scheduler they wish.

A few questions after taking it for a spin. First, and most selfishly, do you think you would consider supporting Meio (not to be confused with Miou :)). Contrary to Meio’s name, I came to think of it as potentially a generic task/async viewing library. I’m not familiar enough with all the internals of Miou yet but I tried shoehorning things in and got a very minimal product working. Some changes here to generalise Meio and hasty changes to Miou. Meio is still along way away, it requires at least the custom runtime events coming in OCaml 5.1.0, but thought I would ask because I think it would be good for Meio to be a little bit more agnostic. The image is from Meio monitoring Miou.

@dinosaure

But I’m going to write a few articles to clarify these differences and, more importantly, their implications.

I’m looking forward to this. One choice is making tasks return promises which you explicitly await as compared to Eio’s default structured concurrency approach? I suppose with the promises you could implement a form of structured concurrency should you wish?

Reading the library source code, the quanta in Miou is number of times you perform an effect? So if I understand correctly once a fiber has performed quanta effects its time being the fiber currently running is over? If that’s the case I assume in Eio it is the same except quanta is not configurable and is implicitly 1… perhaps I’ve completely missed something though. Does Miou also assume to be the outermost effect handler as it seems to capture effects it doesn’t understand and raise Invalid_effect ?

And have you considered supporting DLA?

Interested to see where Miou goes and the follow up explanations :))

[dinosaure]

Thank you for your reply, it’s always nice to see that people accept the multiplicity of solutions .

@patricoferris

A few questions after taking it for a spin. First, and most selfishly, do you think you would consider supporting Meio (not to be confused with Miou :)). Contrary to Meio’s name, I came to think of it as potentially a generic task/async viewing library. I’m not familiar enough with all the internals of Miou yet but I tried shoehorning things in and got a very minimal product working. Some changes here to generalise Meio and hasty changes to Miou . Meio is still along way away, it requires at least the custom runtime events coming in OCaml 5.1.0, but thought I would ask because I think it would be good for Meio to be a little bit more agnostic. The image is from Meio monitoring Miou.

I really like meio! At the moment, Miou uses a log system to show what’s going on (see MIOU_DEBUG=1 ...), but I’m keeping something to do with meio in mind. If I understand correctly, it’s important for Miou to emit events to OCaml. In that case, it should be easy to find a bridge between Miou and meio I think. Miou’s code base is really simple. So we can probably find some time together to think about that and implement something in the end.

Your change seems more or less right to me, so I think we can start discussing what you’re proposing in more detail. But first of all, thank you for your work!

@patricoferris

I’m looking forward to this. One choice is making tasks return promises which you explicitly await as compared to Eio’s default structured concurrency approach? I suppose with the promises you could implement a form of structured concurrency should you wish?

Yes, it’s an approach that we’ve more or less already tried out with awa-ssh for example. It’s also a response to a number of memory leak problems that we’ve already seen (especially on mirage-tcpip) which can be explained by the fact that Lwt.async allows you to forget a task.

This is a design choice that we support, even if it requires us to rethink certain implementations. I mentioned happy-eyeballs in the introduction because it was one of the projects where we did a whole bunch of contortions in relation to lwt.

@patricoferris

Reading the library source code, the quanta in Miou is number of times you perform an effect? So if I understand correctly once a fiber has performed quanta effects its time being the fiber currently running is over?

That’s exactly it, and if you know the fundamental difference between Effect.Deep and Effect.Shallow, you should begin to understand why we used the latter .

Again, as far as the round-robin scheduler is concerned, quanta is perhaps the most important thing to explain to the user - it’s obviously not just a matter of putting a task at the end of the toto-list after it’s made a system call. Quanta has a real influence on the performance of your application. In addition, we’ve applied ourselves to writing a tutorial on this subject. More generally, and as I replied to @zapashcanon, formally establishing a scheduler’s task management policy is really what needs to be explained to the user.

If we consider the round-robin scheduler and its quanta, we have to write our application in a certain way. It would be better if the user had the means to think about this certain way .

@patricoferris

Does Miou also assume to be the outermost effect handler as it seems to capture effects it doesn’t understand and raise Invalid_effect ?

At the moment, it raises an exception if it doesn’t know the effect, so I admit I haven’t really asked the question yet.

@patricoferris

And have you considered supporting DLA ?

As far as DLA is concerned, I still have a lot of worries about understanding what I could do considering our domain pool implementation. I sincerely hope I’ll have time to talk to @polytypic and find a solution that satisfies us both (I’ve already started talking to him about this). But yes, it’s on my TODO list!

[haesbaert]

I, for one, support this initiative very much, all the best and good luck!

[patricoferris]

@dinosaure

If I understand correctly, it’s important for Miou to emit events to OCaml. In that case, it should be easy to find a bridge between Miou and meio I think. Miou’s code base is really simple.

Yep that’s right. I think it will mainly boil down to:

• Deciding on the right interface for describing things schedulers do https://github.com/patricoferris/meio/blob/generalise/src/runtime_events/meio_runtime_events.mli
• Then with those difference how to render them nicely – for example whilst hacking together the Miou x Meio example I had to change rendering based on tasks vs. cancellation contexts. The latter being more Eio specific in the sense of there always being one or more.

There’s also the question of performance overhead. IIUC runtime events are relatively cheap themselves but at the moment Meio does a fair amount of backtrace mangling to reconstruct where calls came from which is super useful I think. But it looks like we might be lucky and get a compiler-supported version Automatically insert source location by let-def · Pull Request #126 · ocaml/ocaml · GitHub .

But as I said we’re a while away from that, but it would be good to have multiple inputs on the correct API to see if it can be as useful as possible without becoming overly complex to accommodate the various schedulers.

@dinosaure

In addition, we’ve applied ourselves to writing a tutorial on this subject. More generally, and as I replied to @zapashcanon, formally establishing a scheduler’s task management policy is really what needs to be explained to the user.

Ah cool, I forgot about the tutorial. I wrote a simple Eio version along with the two from Miou just to have them side by side to look at GitHub - patricoferris/aperitif: Exploring various effect-based OCaml schedulers (note there’s no parallelism in the Eio one, just concurrency).

@dinosaure

it’s on my TODO list!

Hope that list shrinks as well as expands, bon courage !

[dinosaure]

I’m delighted to announce the beta2 release of Miou. This summarises the feedback we’ve received and specifies the API that this library should offer in terms of scheduling.

As a reminder, Miou is intended to be simple and designed for developing services and integrating into a unikernel. We were talking about implementing a library such as happy-eyeballs with Miou, but we have now made available a library that implements an HTTP client and/or server (http/1.1, h2 as well as alpn support via ocaml-tls).

This has enabled us to find bugs typical of a transition between OCaml 4 and OCaml 5, in particular illegal parallel access to data on mirage-crypto (although we would like to observe the implications in terms of performance of our fix).

We will of course continue to listen and experiment with Miou in order to develop this library in a way that suits us and our users. The documentation has been updated accordingly and is now available here.

[dinosaure]

I am delighted to announce the release of miou.0.1.0. This release is undoubtedly the culmination and synthesis of the work of several individuals to offer a library that best fits our needs. We’re quite convinced by the API we’re proposing and quite happy with the implementation. As such, we’re coming out of beta to offer version 0.1.0. Above all, this means that the API will change very little, and the library is now ready for use. However, we are not yet in 1.0.0 because we would like to give you time to use Miou, to observe possible bugs, and to give us time to correct these possible bugs in order to prepare version 1.0.0 with peace of mind. You can install the package via OPAM (it will be available soon):

$ opam install miou

We would sincerely like to thank all individuals who have contributed, whether directly or indirectly, to the project.

Furthermore, this new version of Miou builds upon the excellent work of @polytypic and his picos project. We have incorporated certain elements that are suitable for implementing a scheduler, and we hope that our efforts will lead to a certain standardization of the effects used by different schedulers in OCaml.

This rewrite has been carried out while trying to maintain the same semantics and API as what we offered in version 0.0.1~beta2 (however, it is the nature of a beta to potentially break versions). This rewrite culminated in the reimplementation of an HTTP client and server (supporting http/1.1
or h2 with TLS which can handle 200k req/sec) as well as our good old happy-eyeballs example. Moreover, the outcome of these implementations is more satisfying to us than their previous versions. At least for now, considering the various changes our cooperative has embarked on ¹, we will not yet release them.

We also took the time to integrate a version of the priority queue verified using Why3. We would like to thank @Armael and @backtracking (as well as the individuals who contributed to and maintained the Vocal project) for their assistance.

Finally, I would like to personally thank the Robur cooperative for providing me with the necessary time to evolve this project.

This release further confirms what we aim to offer to users, and in this regard, we have taken the time to write a small book explaining the use of Miou. This can also be seen as an introduction to asynchronous programming and effects. It is available here and is part of the Miou distribution.

For any questions or assistance, we are available via email, this forum, or Discord.

Happy hacking!

1: As explained in this article, we try to replace Cstruct.t by string and it requires obviously a deep change across severals packages.

[mooreryan]

@dinosaure

we have taken the time to write a small book explaining the use of Miou. This can also be seen as an introduction to asynchronous programming and effects.

This is a really nice resource. Thanks for taking the time to put it together!