I was recently trying to fix our Erlang Jukebox (which Tony is still owing a Blog Post for (and once he’s done that I can write a blog post on adding m3u support to our Erlang Jukebox (and some time after that it should be opensourced…))) so that it would randomly enqueue the wrong track, just to spice things up. Erlang has a uniform function in the random module which returns a float uniformly distributed between 0 and 1. “Brilliant” said I.
However, the random module stores its state in the process dictionary which means that each process has a different state for the random module. It also seems to get seeded by preset values rather than by some more suitable time-based value. So, all works well within the same process:
> lists:foreach(fun(E) -> io:format("~w~n", [random:uniform()]) end,
lists:seq(1,10)).
0.289971
0.186964
0.640637
0.553759
0.478947
0.457143
0.920461
0.915298
0.968977
0.903338
ok
But, once all the call to uniform happens fresh in each process, things are a little less ideally random:
> lists:foreach(fun(E) -> F = fun() ->
io:format("~w~n", [random:uniform()]) end,
spawn(F) end,
lists:seq(1,10)).
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
9.23009e-2
ok
And of course, in our Erlang Jukebox (yes, the same one Tony’s due to blog about), using the Erlang webserver Yaws, one process is spawned per HTTP request. So I needed to seed the random module with a time based value to make sure that overall, the behaviour was, well, random.
September 6th, 2006
matthew
One of the new projects that I’m working on involves a messaging infrastructure in Erlang. Without boring you with the details, the basic idea is that there are two types of messages, A and B and these are both sent to a thread (or a process in Erlang). One A must be paired with one B before the A and B can be discarded. Performance is an issue so this pairing must be fast. Several approaches were developed in trying to make this go very fast:
- The first approach is also the dumbest. All A and B messages are sent to the same process. The process deals with these messages in a fifo order and thus must internally maintain queues of As and Bs, matching them as becomes possible. The problem with this is that flooding the process with As or Bs cripples performance because of processing the queue in fifo order. So a DoS attack is very possible and would often accidentally occur (most traffic is bursty).
- The next idea is to not process the messages in a fifo order. This is possible because of Erlang’s receive statement which can do pattern matching on the messages in the queue. The problem is that the process must scan every message in the queue in a fifo order each time through the receive block until it finds one that matches. So whilst the DoS attack can’t happen in the same way, it can still cripple performance as the message queue must be scanned until you reach the end and find the first message of the other type so that the pairing can occur. So this cripples performance again.
- Use three processes. Send messages of one type to one process and of the other type to another process. These processes are then buffers. They process messages in a fifo order (which is fast) and put all the messages they receive into an internal queue. The third process (the pairer) then sends fetch messages to these buffers which then send a predetermined number of messages in their internal queue to the pairer. The pairer then scans its messages in a non-fifo way but because the message queue is effectively bounded, there is no significant performance drop. The points are these:
- There is potentially a DoS attack possible which prevents the buffers from receiving the fetch message. However, firstly by processing the message queue in a fifo order it will be received, just possibly not immediately; and secondly, the buffers simply remove A or B messages from their message queues and place them in an internal queue, thus there is very little processing done. So getting through several thousand A or B messages does not take and real amount of time.
- The pairer only asks for more messages (via fetch messages sent to the buffers) iff it has exhausted its quota of messages: i.e. it asks for n messages from each buffer and will only ask for more if it has received n messages from each buffer. This means that its queue will never be more than 2 n messages long.
- Careful testing reveals that n = 7 is the best performance on the hardware I have available. This balances the cost of the pairer processing messages out of order with the extra round trip to the buffers. Lower n means that there are too many round trips sending fetch messages to the buffers but the non-fifo processing is really cheap. Higher values of n mean the pairer’s message queue gets too big so the non-fifo processing costs too much.
- By using three processes, it can make good use of thread level parallelism hardware. The two buffers can get through their message queues in parallel as can the pairer. There’s also therefore the possibility of distribution across multiple machines.
- It’s very possible to alter the pairer so that it sends the fetch messages after it has achived m pairings where m < n. This means the pairer’s message queue would be a maximum of 2 n + 2(n - m) messages long but would reduce the delay between the pairer sending the fetch messages and the buffers being able to receive the fetch message and send messages on to the pairer - effectively the fetch message ends up higher up in the buffers’ message queues.
It’s quite ironic that a language that seems, at least on the face of it, ideal for messaging-type applications turns out to have implicit semantics that, if not hindering, at least make you think much harder when trying to implement certain requirements…
August 1st, 2006
matthew
I had a brief email exchange with the developers of
Dialyzer, the
static analyzer (some might call it a type checker) for
Erlang programs. Currently Dialyzer only
performs analysis on the functional fragment of Erlang and I was
enquiring whether to extend that to handle communication. That would
allow the detection of basic input/output mismatches, e.g. when a
message is sent to a process that does not match any of the patterns
it is willing to receive.
Going further, one might be able to employ the various techniques
developed for process algebras to reason about the concurrent
behaviour of Erlang programs and, for example, detect deadlocks and
enforce information flow security properties. A good example of such a
tool is TyPiCal. It
would be amazing to have something like that for Erlang. After all,
what makes Erlang interesting is not the functional programming aspect
currently checked by Dialyzer, but its support for concurrency,
distribution and fault-tolerance. It is incredibly difficult to
correctly implement systems that involve the latter. If there is any
area of programming in which we want the help of static analysis then
this is it!
Anyway, it turns out that there are no immediate plans to extend
Dialyzer in that direction. However, I was pointed at some related
research that I had hitherto been unaware of: Karol Ostrovský’s PhD
thesis, which in
Part II describes the
sound instantiation of Kobayashi’s generic type system for the
pi-calculus to session types,
extension of session types to multi-session types (which, afaict,
handle sessions that involve asynchronous comms, and servers that
handle multiple sessions without spawning),
application of multi-session types to type check communication of
Erlang processes.
Overall this looks like a promising attempt at constructing a
process-algebra-based type system that is decidable and yet expressive
enough to reason about non-trivial real-world protocols (IMAP4 is used
as an example). The theory behind it seems to be quite involved, but
that could just be due to the presentation format - a thesis rather
than a paper. It will be interesting to see whether this research is
carried any further and eventually materialises in tools for Erlang.
June 26th, 2006
matthias