söndag, september 20, 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.


28 kommentarer:

  1. If you need some help with your assignment, try ehomework service

  2. Java consulting has been much in demand for over a decade now. Leading outsourcing destinations like India, China etc. shelter a large number of reputed Java consulting providers, which handle a wide array of Java-based projects from design to implementation with a lot of proficiency. See more programming homework

  3. Thanks for sharing the information.

  4. nice site.. thanks for sharing my web site link....

  5. My Assignment Services is a well-established and prominent name in providing high-quality assignment help online to students since almost a decade. You can trust our academic ghostwriters completely to get best quality write-ups including case studies, research proposals, dissertations and theses, and more. It is the best assignment help Adelaide provider.Students should always keep themselves ready to meet the university requirements in order to achieve good grades, moreover, they prefer attending lengthy classes instead of writing assignments. Students who are not comfortable with writing assignments can avail university assignment help by buy assignment at My Assignment Services comparatively low prices.

  6. If you need assignment help in Sydney, Australia, Essayassignmenthelp.com.au is the best place for you. Get the assignments at cost effective rate.

  7. Online Assignment Expert has a a Professional and Experienced Writing Experts from Australia, UK and US. They are highly qualified and skilled professional writers who have vast experience in writing assignments, dissertations, essays, research Report  writing etc. We provide online assignment help. Our writers meet all the requirements of students or those who search assignment help guide them.

  8. Online Assignment Expert has recently deployed its team of R programming assignment help experts who provide academic assistance to the students pursuing programming courses. We have been guiding and consulting students across Australia so that they can overcome their academic problems. Moreover, we are offering our statistics assignment help service exclusively at a discounted rate. Students can grab this opportunity and enjoy professional guidance at reasonable prices! Also, with our systemic literature review assignment help professionals, you can easily submit high-quality assignments, and score excellent grades in these writing tasks as well.

  9. Thanks for your informative content. It's extremely useful to students for further research and assistance. However, there is an academic assignment help provider that goes by the name TutorVersal, who has been offering various assignment writing services like Essay Help services, report writing services, case study services et cetera. The company has delivered thousands of assignments in which students scored high-distinction grades. They have never let any student down and in addition, offers various essay writing help services in subjects like management, nursing, law, engineering, and more. They constantly strive to provide the best academic solutions at the cheapest price as they know how difficult it is for a student to manage such expenses. Thus, any students who feel helpless in their academic assignments can avail prime assignments services at Tutorversal.com.

  10. Hello
    My name is Chris Paul and This is a very nice post, Thanks for Sharing.

    For Best Perdisco Assignment Help in US for 24*7.

  11. Highly Professional Finance Assignment Help Inbound Services In Australia.
    A lot of students every year face extreme difficulties in preparing their highly valuable finance assignments. Therefore, to provide them with quality assistance, My Assignment Help OZ is offering their most-accurate finance assignment help services to guide students facing problems in their academics. Also, the team constantly strives to achieve 100% client-satisfaction by providing MYOB assignment help, financial accounting assignment help and specialised services in various other subjects as well.
    Along with professional finance assignment services, we also provide live sessions to students who have insufficient conceptual knowledge. Thus, any student can avail our professional services, by writing to us at info@myassignmenthelpoz.com .

  12. One of the best articles that give business analytics assignment help to the students studying this course. I am an assignment help expert at My Assignment Services, a known name among the students when it comes to business analytics assignments. We are a team of more than 500 experts spread across the globe and delivering quality content to every student who comes to us for auditing assignment help, business analytics assignment help or any other subdomain of business analytics. There are a number of things that the students need to keep in mind while writing their assignments and such tips and explanations can only go a certain length. Therefore, we are offering a customised business analytics assignment help where we prepare your entire assignment help from scratch delivering a high-quality content like hundreds of before. Embark on an academic journey and get the most professional and affordable assignment help today!

  13. Amzing written by you!!!

    Lovedollpalace is an online shop to buy realistic sex dolls & life size love doll for sex, quality TPE and silicone realistic adult dolls at affordable price. So visit our website and choose amazing dolls.

  14. Excellent information on your Article, thank you for taking the time to share with us such a nice article. Amazing insight you have on this, it's nice to find a website that details so much information about different artists. My Assignment help

  15. This post is a pool of information. The readers are quite impressed after reading this impressive post.
    This impressive post certainly encourages to choose Assignment Help Australia Services.
    You can email us at cs@Myassignmenthelpau.Com or Phone Number: +61-2-8005-8227

  16. Hello
    My name is Chris Paul and This is a very nice post, Thanks for Sharing.

    24*7 Programming Assignment Help anytime in Australia.

  17. Hello
    My name is Alena Carter and This is a very nice post, Thanks for Sharing.

    One of the best IT company Locus Rags in India.

  18. Very nice blog and articles. I am really very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post. My Assignment help


  19. Hello
    My name is Jacob Parker and This is a very nice post, Thanks for Sharing.

    Web and Application Solution Provider Company LOCUS RAGS in India.

  20. Sample Assignment bestows over the college going students with online assignment help. It is a consultancy possessing academic experts providing a number of subject-specific assignment helps. Management assignment help, economics assignment help, MATLAB assignment Help, MySQL assignment help, marketing assignment help, etc. are a few to name. The assignment help packages that they supply the students with ensure the students receive an HD or a full money back. With their assignment consultation services, the students can learn by exposing themselves to out-of-the-box learning when it comes to module related studies. For the quality of the in-depth research that is conducted before the experts at Sample Assignment lay their hands on a specific assignment, the prices are kept very close to the ground while the company has its head touching the sky. They offer services in Essays, CDRs, Resumes, Thesis, Research Proposals, Research Papers, Dissertations, etc. Be it any of the above, they provide ready to study from assignment solutions to the students who work-save in order to pay for the service and the online assignment services provider works on the motive of giving out value for every coin a particular student pays for the online assignment help Australia. With their Partial Payment and the optional feature of Countless Revisions, they have earned themselves two consecutive years of recognition.

  21. Hello
    My name is Jack Peter and This is a very nice post, Thanks for Sharing.

    Best LOCUS RAGS IT Company in India.

  22. Great Job! Appreciated for this post. here are modern love doll so choose among of these to full fill your requirement

    sex dolls
    sex dolls for men
    love doll
    Realistic sex dolls
    sex doll