Sunday, 20 September 2015

Reducees and Erlang I/O

Last week there was discussion on twitter after I made a comment that I had now found that the Erlang I/O used reducees not iteratees, and that I got the terminology wrong was not surprising seeing that neither existed when I did it. In the follow-up discussion I also commented that I thought them so simple as to be hardly worth naming. Also, that the difficult bit is formulating the problem so you know what to solve.

I still hold by that.

So how do reducees, not iteratees, relate to the Erlang I/O system and why is the concept simple, almost trivial, while getting the problem right is the hard bit? That I will now try to explain.

We must go way back in time to when we (Joe Armstrong, Mike Williams and myself) were migrating Erlang from being a Prolog based interpreter to being its own system. So while Joe was hacking the compiler, in Erlang of course, and Mike writing the VM, in C of course, I was writing many of the libraries, in Erlang of course. And one of the libraries was about I/O.

After a bit of thinking I arrived at the following basic requirements:
  1. It must work in a highly concurrent environment.
  2. It must be able to interface many different device types.
  3. I should be able to reuse the I/O functions irrespective of the device type.
  4. It should never block on doing I/O to a device.
  5. While the device speaks bytes the Erlang side need not.
So what do I mean by these requirements?
- It must work in a highly concurrent environment.
There are going to be many processes accessing a "device" simultaneously and it must be able to handle this sensibly. This is not a performance problem. So basing the I/O on a getchar/putchar model won't work, and if anyone doubts me try starting multiple UNIX programs in one shell all doing I/O and see the resultant mess on the screen.

- It must be able to interface many different device types.
This, of course, is nothing special or strange and is expected of most i/o systems.

- I should be able to reuse the I/O functions irrespective of the device type.
This again is nothing strange. I want to avoid having to write special I/O formatting functions for different device types.

- It should never block on doing I/O to a device.
Now, we are getting interesting. Seeing one of the most important requirements for the Erlang language/system is that it must be reactive and non-blocking then naturally this also extends to the I/O system. Not just at the device level where is all I/O operations already are non-blocking (yes, we have had this from the very beginning) but through all levels of the I/O system. No I/O function call should block the system more than any other function call.

- While the device speaks bytes the Erlang side need not.
This again is nothing strange, it just allows to have nicer interface to the I/O system.

I just want to point out that these requirements didn't just spring out of nowhere but evolved as I was thinking about the problem, from past experience and from how other systems do it. System 5 streams were influential.

So where did we go from here?

My idea was to make the I/O system built on processes, very Erlangy, very concurrent and non-blocking and also very scalable. It is based around the concept of an "I/O-server". This is a process which handles all the I/O requests to/from a device, a device being a physical device, a file, the screen, a TCP socket, etc. It has two "sides". On one side the I/O-server speaks Erlang I/O requests and on the other side it speaks the device, basically sending receiving bytes to/from the device in the right format. At this level devices speak bytes. It would typically go through an Erlang port.

The I/O-server is then a process which sits in a receive loop processing i/o requests as they come. It would handle one request at a time. This is just the standard Erlang way of processing requests so it would be just as non-blocking and reactive as the rest of system.

So output is easy. When you do an output call you send a chunk of bytes, an iolist, to the I/O-server and it device side will see that it is sent to the device. Or you could send the I/O-server a function to generate bytes which it evaluates and then sends the bytes to the device. The Erlang I/O system has both. The I/O-server would guarantee that all the output from each request was sent as one block of data to the device.

Input is more difficult. A fundamental problem is that most times when you do a read of some sort you don't know how many bytes you need from the device. Even for the "trivial" case of getting a line this can be very difficult. How long is the line, 0 bytes, 1 byte, 42 bytes, 4711 bytes, ...? And what if the number of bytes you need in no way relates to the bytes are received from the device.

Now things are getting interesting! So an obvious way to solve this is to send the I/O-server a function which is used to collect bytes until it gets enough and then return them to the caller. You first call it with the bytes you have. What happens if it needs more bytes?

One solution is for the collect function to call a function which returns more bytes. A major problem with this solution is that the I/O-server now loses control and is no longer in charge which in really needs to be. For example it may need to handle messages from the device or other I/O requests, all this while we are processing the original input request.

A much better solution is for the collect function to work with the bytes that it has been given and return a status:

- OK, I could collect what I was supposed to and here is the result to send back and here are the remaining bytes.
- More, I need more bytes and here is a continuation to call me with when you get more bytes.
- Error, an error occurred, here is the error and the remaining bytes.

So the I/O-server will keep calling the collect function as long is it requires more and then send back the reply when it is done. The I/O-server is then ready to process the next request. It has always been in control if necessary. Also the collect function is completely general as it has no knowledge of how the bytes are collected or how the return value is handled, which was our third requirement.

The collect function with this type of interface is a reducee. QED

Would it have been easier if reducees had already been "invented" and I knew about them? I don't think so. The major difficulty here was trying to clearly formulate the problem and define a structure which solved the problem. Once that was done the reducee part just naturally fell out, but without that structure the reducee had no meaning. That is why I commented that I found them so simple as to be hardly worth naming. I still don't.

OK, this became much longer than I intended, sorry for that.

Using processes like the I/O-server to build the I/O system makes many things very easy, almost trivial, for example:
  • Having a master/slave nodes for file system where all file access goes through the master node.
  • Starting a task on another and have all its default I/O go to your node.
  • With a TCP I/O-server open a listen socket and for every connection start a new shell and have all its default I/O go through the socket (10 lines of code).
Once you get used to structuring your application using processes and concurrency many things become quite straightforward.