Message Routing Paradigms

Eric Newhuis <>
Sat Dec 14 03:46:21 CET 2002


Luke et al,

First of all a big thanks to you Luke, Peter, Scott, Vance, Jani, and
Sean (in no particular order) for responding with all this great
information.  If Erlang-the-language is not enough to sell me on OTP
then Erlang-the-community certainly is.  This is great feedback; I
really appreciate the help.

My *first* problem is to deal with routing messages from server to
server so I can keep a lot of data coherent across many nodes on a
network.  I estimate order ~ 500,000 records split among about 10 data
tables for starters.  About 10,000 records are updated every second on a
single node.  Multiple nodes can feed other nodes so that, in total,
there may be 50,000 updates per second in one server farm.

Satellite servers that are *mostly* subscribers are also fed information
from this farm and supplemented with data that is "more local".  I have
no control over the structure of supplemental records stored in the
satellite servers.  And so it is feasible that some of them may grow
larger than my main farm.

Also, over time, about once a month we are defining new tables and
record formats and so we want the message format to be flexible and not
depend on a brittle database schema.  I desire minimal recompilation of
services already in production.

In short, all of the above just states that I have a rather large
distributed database that is too big to fit in one place and does not
need to fit in one place.

Subscribers are dynamic.  They come and go as they see fit.  And they
can subscribe to changes in individual records or record sets or simple
event messages not associated with tables.  And subscribers change their
subscriptions often, about 1/s.  Most subscribers have 100s of
subscriptions.

The subscribable record sets are defined with a simple pattern matching
language that matches variable-length lists of Erlang values or
wildcards.  So, for example, a subscriber could choose to subscribe to
either [a,b,c,d], ['_',b,c,d], [a,b,'_',d], or a multitude of other
possibilities.

My current thinking leads me to believe that more complex
pattern-matching based on queries like ['$1', '<', 200] will be too slow
to handle the expected transaction rate.  But I'd be happy to find out
that I'm wrong.

Thus far my current approach has been to implement a Trie structure in
the Message Router that maps patterns to lists of subscriber PIDs.  I
traverse the trie on every published message to find all patterns that
match the message, forwarding the message to all of the subscribers.

This was my first *real* data structure in Erlang and I was shocked to
discover that it only took me an hour to write a rather complex
insertion function in Erlang.

It would be wonderful to discover that such a thing already exists, such
a thing as either the simple wildcard match or the more advanced pattern
matching grammar that Erlang supports (as described in the erts module
documentation).

Also, FIFO must be maintained from a single publisher so that all
subscribers of messages that originate from a single publisher receive
them in the same order they were published.

Thanks everyone for reading this far.  This is a lot to digest.

Sincerely,
Eric




More information about the erlang-questions mailing list