24 Sep 2002 Bram   » (Master)

Notify Lists

Raph wonders about notify lists. I've spent a lot of time thinking about algorithms for this, but haven't talked about it much, since it turns out that the simple solutions are near optimal.

Unrelated to the technical messaging aspects, I'd like to point out that the most logical form of addressing for instant messaging is person@machine. Reusing email addresses makes the system both easy to use and viral, and doesn't introduce yet another identifier for users to remember and manage.

There are two simple approaches. The first is completely centralized. All users report to a single central machine when they log in, and get data back when their friends come online. This system is very efficient, but it has a single point of failure, although in practice a single site can be made quite reliable. It also doesn't scale very well, although the number of messages involved in online status reports is so small it might hardly matter.

The second basic approach is for each user to have a 'home base' they log into, and for home bases to report interest and online status to each other. This approach is very reliable and scales very nicely, but is inefficient under some circumstances. If a typical user has thousands of friends but only a dozen are online at once, lots of unnecessary interest messages get sent. For notify lists this isn't a big deal, since a large fraction of users are online at all times, and the total number of messages is pretty small anyway, but there might be similar applications where it's a real issue.

Before explaining the hybrid solution, I should explain the inter-home protocol.

There is some reliable ordered transport layer, not necessarily TCP. On top of that, there are four messages, all of them idempotent -

  • I'm interested in user X.

  • I'm not interested in user X.

  • User X is online.

  • User X is not online.

The one subtlety is that if one side changes from not interested to interested, the other side must report online status (not necessarily instantly though, as we'll see below).

Let's look at what happens if Alice is in Bob's notify list and Alice comes online first. Messages are sent as follows -

  1. Alice tells her home she's online.

  2. Bob tells his home he's online, and sends it an 'interested in Alice'.

  3. Bob's home sends an 'interested in Alice' to Alice's home.

  4. Alice's home sends an 'Alice is online' to Bob's home.

  5. Bob's home sends an 'Alice is online' to Bob.

Now let's look at what happens if Bob comes online first -

  1. Bob comes online, tells his home he's online and sends it an 'interested in Alice'.

  2. Bob's home sends an 'interested in Alice' to Alice's home.

  3. Alice's home sends an 'Alice is not online' to Bob's home.

  4. Bob's home sends an 'Alice is not online' to Bob.

  5. Alice tells her home she's online.

  6. Alice's home sends Bob's home an 'Alice is online'.

  7. Bob's home sends Bob an 'Alice is online'.

Of course, someone else using Bob's home might also be interested in Alice, in which case several of the messages in the above dialogue would be unnecessary. Also, as an optimization Bob's home may remember his notify list so it doesn't have to be re-uploaded every time he comes online.

The hybrid solution, which has some of the benefits of both of the above methods, is to introduce 'collators' which handle the information for a group of home machines. Collators speak the inter-home protocol to each other, and get some of the message reduction benefit of doing everything with a single centralized server.

Let's look at how the message flow works if Alice is in Bob's notify list and is already online when Bob comes online -

  1. Bob tells his home base he's online, and sends an 'interested in Alice'. If Bob's home already has a user who's online and has Alice in their notify list (unlikely), then Bob's home responds immediately and the protocol stops here.

  2. Bob's home sends an 'interested in Alice' to Bob's home's collator. If another user whose home is using this collator is interested in Alice (likely), then this collator responds immediately, otherwise the protocol continues as follows.

  3. Bob's home's collator sends an 'interested in Alice' to Alice's home's collator. If a user on another collator is interested in Alice (very likely), then this collator responds immediately, otherwise the next two steps are necessary.

  4. Alice's home's collator sends an 'interested in Alice' to Alice's home.

  5. Alice's home sends an 'Alice is online' to Alice's home's collator.

  6. Alice's home's collator sends an 'Alice is online' to Bob's home's collator.

  7. Bob's home's collator sends an 'Alice is online' to Bob's home.

  8. Bob's home sends an 'Alice is online' to Bob.

I've glossed over the details of how collators are found, how homes set and change what their collators are, and how failures on the messaging level are reported, but all those problems can be solved in reasonably straightforward ways.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!