Mailinator(tm) Blog

Mailinator for Testing

2009-11-11T11:10:00.001-08:00

Recently I implemented a captcha system in Mailinator.

If you're a normal user - you've probably never seen it. That's because it doesn't get activated until emails with the same subject get read more than like 10 times in a minute. Needless to say, if you're using Mailinator to sign-up for something here and there, that's not a normal use case.

But if you're a script - or a person signing up for some website over and over and over (and over) - you hit this pretty fast. It has done a fantastic job of stopping scripts pretty succinctly and slowing down humans zealously working over some site. The main problem with the latter is that many of those sites don't like that and may then ban Mailinator. That's not good for anyone.

What surprised me about the captcha system is how many people emailed me that I broke their test scripts. That is, they had email system tests (i.e. "Thanks for registering!") that use Mailinator as an end point. Their test then (with variation per user of course) checks the Mailinator inbox that their system correctly sent the email.

ManyBrain, Inc. (the company that owns Mailinator) has offered for a long time testing packages that completely bypass Mailinator's abuse system for high-volume testing or other emailing.

I'd be interested in however in improving this service and making it more mainstream. If you use Mailinator for testing - or would like to - I'd like to hear from you.

How would you use it? What kind of volume? I can't believe anyone is excited about scraping HTML (that wasn't particularly designed to be scraped) to get test results. Mailinator already has a (secret, shhh) JSON interface thats not public. That would seem to be the way to go.

My thoughts is a JSON-based SOAP/REST/whatever API that allows testing scripts to read emails. Whats a reasonable method and threshold of use to start charging? Possibly a sister site to Mailinator itself would be a better home for the testing service.

If there's enough interest to support the development, I'd be excited to get this up and running.

Email me at paul@manybrain.com

More Alternate Domains !

2009-09-21T00:45:00.000-07:00

I've added a few more alternate domains. If you've never used them, they are simply other domains (for example, sogetthis.com) that forward all email to Mailinator.

Simply, if you send email to fred@mailinator.com - or - fred@sogetthis.com it works exactly the same way and your email will arrive in the "fred" inbox at Mailinator both ways.

You can find alternate domains (including the new ones mixed in) on the front page of Mailinator on the left column.

I'll be sneaking more into the rotation soon!

You can't type "mailinator.com" in Facebook

2009-06-22T10:16:00.000-07:00

I've known for awhile that Facebook directly bans signing up with a mailinator address (several of the alternate domains work - and more are on the way).

Interestingly, I commonly attend San Francisco & Silicon Valley entrepreneur events and I've met a few facebook people. In one instance, I had a fun jabbing match with a Facebooker who ended up being a friend. He assured me that Facebook will ban mailinator for good and I assured him I'll be working to get around that as a personal challenge :)

(I then sent a box full of Mailinator t-shirts to his office)

In any case, what I didn't know is that in Facebook chat (or wall posts) you cannot actually type "mailinator.com". It prevents you. Wow. Paranoid much? (Somehow I don't think "mailinator.com" is abusive as the message that pops up says - and note that you can type "mailinator" (without the ".com") which is apparently fine and dandy - for the moment anyway).

I did successfully create a Mailinator facebook page (feel free to become a fan!) and so far its still up. We'll see how long that lasts :)

A Beautiful Race Condition

2009-06-09T05:53:00.000-07:00

I recently gave a keynote at the ICIS 2009 conference in Shanghai. The topic was why multithreaded programming seemed so easy, yet turned out to be so hard. The fun part was I investigated (per my last post and this one) several old, personal concurrency demons I knew existed but wanted to know more about.

One of those was, indeed, my favorite race condition. It doesn't escape me that its probably wholly unhealthy to even *have* a favorite race condition (akin to having a favorite pimple or something) - but nonetheless, the elegance of this one still makes my heart aflutter.

The scenario of this race is that we assume, not terribly inaccurately, that race conditions at times, can cause corrupted data. However, what if we have a situation where we sort of don't mind some corrupted data? A "good enough" application as it were.

The dangerous part of all this is if we assume (without digging in) what kind of data corruption can happen. As you'll see, you might just not get the type of data corruption you were hoping for (which is one of the sillier sentences I've ever written).

The particular instance of this kind of happy racing I've encountered is where someone uses a java.util.HashMap as a cache. I've never done such a thing myself, but I heard about this race and thus this analysis. They may use it with a linked-list or maybe just raw, but the baseline is that they figure a synchronized HashMap will be expensive - and in their case, a race condition inside the HashMap will just lose (or double up on) an entry now and then.

That is - a race condition between two (or more) threads might accidentally drop an entry causing an extra cache miss - no biggie. Or, it may cause one thread to re-cache an entry that didn't need it. Also no biggie. In other words, a slightly imprecise, yet very fast cache is ok by them. (of course, this assumption is dead wrong - don't do that - read on for why!)

So they setup a HashMap in some global manner, and allow any number of nefarious threads bang away on it. Let them put and get to their hearts content.

Now if you happen to know how HashMap works, if the size of the map exceeds a given threshold, it will act to resize the map. It does that by creating a new bucket array of twice the previous size, and then putting every old element into that new bucket array.

Here's the core of the loop that does that resize:

1:  // Transfer method in java.util.HashMap -
2:  // called to resize the hashmap
3:
4:  for (int j = 0; j < src.length; j++) {
5:    Entry e = src[j];
6:    if (e != null) {
7:      src[j] = null;
8:      do {
9:      Entry next = e.next;
10:     int i = indexFor(e.hash, newCapacity);
11:     e.next = newTable[i];
12:     newTable[i] = e;
13:     e = next;
14:   } while (e != null);
15:   }
16: }

Simply, after line 9, variable e points to a node that is about to be put into the new (double-wide) bucket array. Variable
next holds a reference to the next node in the existing table (because in line 11, we'll destroy that relation).

The goal is that nodes in the new table get scattered around a bit. There's no care to keep any ordering within a bucket (nor should there be). HashMap's don't care about ordering, they care about constant time access.

Graphically, let's say we start with the HashMap below. This one only has 2 buckets (the default of java.util.HashMap is 16) which will suffice for explanatory purposes (and save room).

As our loop starts, we assign e and next to A and B, respectively. The A node is about to be moved, the B node is next.

We have created a double-sized bucket array (in this case size=4) and migrate node A in iteration 1.

Iteration 2 moves node B and Iteration 3 moves node C. Note that next=null is the ending condition of our while loop for migrating any given bucket (read that again, its important to the end of the story).

Also important to the story, note that the migration inverted the order of Node's A and B. This was incidental to the smart idea of inserting new nodes at the top of the list instead of traversing to find the end each time and plunking them there. A normal put operation would still have to check that its inserting (and not replacing) but given a resize can't replace, this saves us a lot of "find the end" traversals.

Finally, after iteration 3, our new HashMap looks like this:

Our resize accomplished precisely the mission it set out to. It took our 3-deep bucket and morphed it into a 2-deep and 1-deep one.

Now, that's all well and good, but this article isn't about HashMap resizing (exactly), its about a race condition.

So, let's assume that in our original happy HashMap (the one above with just 2 buckets) we have two threads. And both of those threads enter the map for some operation. And both of those threads simultaneously realize the map needs a resize. So, simultaneously they both go try to do that.

As an aside, the fact that this HashMap is unsynchronized opens it up to a scary array of unimaginable visibility issues but that's another story. I'm sure that using an unsynchronized HashMap in this fashion can wrack evil in ways unlike man has ever seen, I'm just addressing one possible race in one possible scenario.

Ok.. back to the story.

So two threads, which we'll cleverly name Thread1 and Thread2 are off to do a resize. Let's say Thread1 beats Thread2 by a moment. And let's say Thread1 (by the way, the fun part about analyzing race conditions is that nearly anything can happen - so you can say "Let's say" all darn day long and you'll probably be right!) gets to line 10 and stops. Thats right, after executing line 9, Thread1 gets kicked out of the (proverbial) CPU.

1:  // Transfer method in java.util.HashMap -
2:  // called to resize the hashmap
3:
4:  for (int j = 0; j < src.length; j++) {
5:    Entry e = src[j];
6:    if (e != null) {
7:      src[j] = null;
8:      do {
9:      Entry next = e.next;
     // Thread1 STOPS RIGHT HERE
10:     int i = indexFor(e.hash, newCapacity);
11:     e.next = newTable[i];
12:     newTable[i] = e;
13:     e = next;
14:   } while (e != null);
15:   }
16: }

Since it passed line 9, Thread1 did get to set its e and next variables. The situation looks like this (I've renamed e and next to e1 and next1 to keep them straight between the two threads as both threads have their own e and next).

Again, Thread1 didn't actually get to move any nodes (by this time in the code, it did allocate a new bucket array).

What happens next? Thread2, that's what. Luckily, what Thread2 does is simple - let's say it runs through the full resize. All the way. It completes.

We get this:

Note that e1 and next1 still point to the same nodes. But those nodes got shuffled around. And most importantly the next relation got reversed.

That is, when Thread1 started, it had node A with its next as node B. Now, its the opposite, node B has its next as node A.

Sadly (and paramount to the plot of this story) is that Thread1 doesn't know that. If you're thinking that the invertedness of Thread1's e1 and next1 are important, you're right.

Here's Thread1's next few iterations. We start with Thread2's bucket picture because thats really the correct "next" relations for our nodes now.

Everything sort of looking ok.. except for our e and next at this point. The next iteration will plunk A into the front of the bucket 3 list (it is after all, next). And will assign its next to whatever happens to already be there - that is, node B.

Woah. Thar she blows.

So right about now Thread1 goes into, what we like to call in the biz, an "infinite loop". Any subsequent get operations that hit this bucket start searching down the list and, go into, yep - an infinite loop. Any put operation that first needs to scan the nodes to see if its going to do a replace, will, you guessed it, go into an infinite loop. Basically, this map is a pit of infinite loopeness.

If you remember we noted that race conditions cause data corruption. Well, yeah, thats what we have here - just very unlucky data corruption on pointer structures. I'm the first to admit this stuff is tricky - if you found errors in my analysis I'll happily fix this post.

Now I had the happy fortune for a time of sharing an office with Josh Bloch who wrote java.util.HashMap. When I innocently mentioned he had a bug in his code given this behavior, he did indeed (to use Josh's word's) go non-linear on me.

And he was right. This is not a bug. HashMap is built specifically for its purpose and this implementation is not intended as threadsafe. There's a gaggle of ways to make it threadsafe, but in plain, vanilla, (and very fast) form - its not. And needless to say, you shouldn't be using it that way.

Race conditions are nothing to mess with and the worst ones are the ones that don't crash your program but let it wander down some unintended path. Synchronization isn't just for fun you know.

And nefarious uses of HashMap aside, I still attest - this is, indeed, a beautiful race.

On Java Visibility

2009-06-08T08:00:00.000-07:00

A semi-famous example of broken Java synchronization is this:

class SomeClass {

  private boolean keepGoing = true;

    public boolean get() {
      return keepGoing;
    }

    public synchronized boolean set(boolean x) {
      keepGoing = x;
    }
}

I believe this example is in Josh Bloch's book "Effective Java" (which I now notice I somehow lost my copy in my most recent move - don't tell Josh).

The idea is here that someone (ostensibly) thought that they'd save some performance by not synchronizing a getter and just synchronizing the setter. There definitely is a cost to synchronization and needless to say, getting doesn't change anything - so why bother paying that cost for gets?

As has been pointed out long before this post, without a synchronize on a getter, there is no guarantee of visibility when doing the get. That is, if one thread calls set(false), there's no guarantee that any other thread will know it happened.

Consider code that might use the code above:

class SomeOtherClass {

  SomeClass keepGoing = new SomeClass();

  class Thread1 implements Runnable {
    public void run() {
      while (keepGoing.get()) x++;
      System.out.println("done1");
    }
  }

class Thread2 implements Runnable {
    public void run() {
    keepGoing.set(false);
  }
  }
}

Let's say you start a Thread1 running. And of course, keepGoing.get() is true, so it just keeps looping along. Then lets say an eternity (or maybe 2 seconds) later you start Thread2.

If we had reliable visibility, Thread1 would end the moment after Thread2 sets keepGoing to false.

If you've read Josh's book, its no surprise that it doesn't. Specifically, Thread1 doesn't end. It keeps going. Thread2 ends happily and Thread1 never ends.

The only interesting part to me was that this always worked. Always. Adding to the complexity of visibility concerns is that memory is "leaky". That is, even without guaranteed visibility you often get unreliable visiblity.

So, I dug a little deeper. If you're adventurous enough to grab a debug-version of the JDK and run it with the -XX:+PrintOptoAssembly option. You get to see the optimizations the JIT are making. That is, you see the assembly code version of your Java code - post-optimization. Check out Koshuke Kawaguchi's Blog for some instructions.

So here's Thread1's loop code after JIT optimization at runtime:

02c movq R10, precise klass manybrain/test/Main: 0x0000000040a50968:Constant:exact * # ptr
036 movsbl R8, [R10 + #596 (32-bit)] # byte ! Field manybrain/test/Main.keepGoing
03e testl R8, R8
041 je,s B4 P=0.000000 C=147944.000000
041
043 B2: # B3 <- B1 Freq: 1
043 movl R8, [R10 + #592 (32-bit)] # int ! Field manybrain/test/Main.x
043
04a B3: # B3 <- B2 B3 top-of-loop Freq: 1e-35
04a incl R8 # int
04d movl [R10 + #592 (32-bit)], R8 # int ! Field manybrain/test/Main.x
054 testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC # manybrain.test.Main$Thread1::run @ bci:14 L[0]=_
# OopMap{r10=Oop off=84}
05a jmp,s B3
05a
05c B4: # N53 <- B1 Freq: 4.76837e-07
05c movl RSI, #27 # int
061 nop # 2 bytes pad for loops and calls

If you're old school, welcome home.

If you're not, then this might look like a lot of goop. So let's parse out just the interesting parts.

Line 41 is an conditional jump. Basically, if keepGoing (per the comment in line 36) is false, we jump to line 5C (label B4) and end the code segment. You and I know that keepGoing started true, so basically that jump isn't followed.

Lines 43-5a are the loop that does x++.

And checkout line 5a. That is an unconditional jump back to the top of the loop. So what does all this mean? That the JIT did some very aggressive optimization. In fact, remember our original loop from Thread1?

while (keepGoing.get()) x++

The JIT has optimized this to:

if (keepGoing.get()) {
  while (true) x++;
}

No wonder the loop never ends. You've got bigger problems now than a little leaky visibility issue. I'm positive I'm oversimplifying, but effectively the JIT saw your get method wasn't synchronized and made the assumption that it could optimize as such. If you didn't guarantee visibility, it didn't need to either. Obviously, add the synchronization modifier to the get method and all this badness won't happen.

Moral of the story is much like the inevitable topics discussed at a lunch with Jeremy Manson - you can't optimize away correct synchronization; as all you'll probably do is optimize the "correctness" part away.

Talkinator on 5 Watts

2009-05-21T08:43:00.001-07:00

I've written previously about the architecture of the Talkinator server. As a synopsis, the entire thing is basically completely custom. Custom webserver, custom comet server, custom RPC, custom encoding, custom everything (to the Java programmer, this translates as it needing no other jars to run apart from me deciding to use Cliff Click's NonBlockingHashMap instead of Doug Lea's ConcurrentHashMap).

I also pointed out that the only reason you'd want to do something like that is for fun or experimentation or well, ok, that's about it. In any case, this also has a nice side-effect of making everything rather wee. The Talkinator server is strikingly frugal in terms of memory and cpu.

Fast forward to today and I recently found GlobalScale's plug computer. (Url is http://www.globalscaletechnologies.com/p-22-sheevaplug-dev-kit.aspx ).

Simply put, its a 512M ram, 512M disk, custom CPU that pretty much only has a USB and ethernet connector. It has Ubuntu 9.04 (minimized) installed on it, costs about $120, and runs on an advertised 5W of power (of course, the crappy lightbulb in my room is probably 60W). Pretty much you plug in ethernet, plug in power - and then go ask your router where it DHCP'd to.

Then you ssh in. Voila!

I did some linux reconfig and thought about what to install... (a common dilemma when you buy a server without having a purpose). Well, how about the Talkinator server?

Installed Java, unzipped the server - and we're off to the races.

As a test, I made it available on the net and put a second chat box on the front page of http://www.talkinator.com. No one will tell you this is a powerhouse machine - but clearly its specs do allow for some applications to do just fine. (Please allow for some slowness on the plugcomputer because, unlike the regular Talkinator server, its not in a datacenter - its in my bedroom. And its on a dedicated, but still not uber, DSL line)

I went ahead and ran some very informal benchmarks on it. I ran a simple test of how many 404's my custom webserver could push on the plug computer and on a dual-core Opteron rackmount server (which also happens to be in my bedroom - dont ask).

Plug-computer: 550 requests per second
Dual-core Opt: 7700 requests per second (possibly just saturating bandwidth)

Not bad for 5W.

PS: As you can imagine, I probably wont run this test forever, so if you read this entry at some point in the future, the 2nd talkinator box on the home page might be gone.

PPS: Because I'm lazy, the talkinator server on the plugcomputer is running on a non-standard port. So if you're coming in from behind a proxy or firewall or something - you might not see it.

How long before an email is removed from the system?

2009-01-26T10:38:00.000-08:00

I get this question a fair bit. How long, exactly, is an email available to be read after it enters the system?

Its hard to answer because its literally dependent upon the incoming rate at which email arrives. In effect, new email "pushes out" old email. That's a bit simplified as some email is thrown away based upon spam rules (if you get 100,000 emails with the same subject, you can probably say they aren't all going to be read).

So, whats the average? This weekend, email was lasting around 10 hours before getting "pushed out" of memory. I've seen that jump down to an hour - but mostly its around 5-7 hours.

I'll note that the primary Mailinator use case is that people tend to read email soon after it arrives. In other words, if email only lasted 15 minutes, we'd actually fill the needs of many users.

(I'd be *very* interested in hearing ways you use Mailinator that need mail to stick around longer.)

No, Mailinator didn't spam you

2009-01-08T22:04:00.000-08:00

I must say, it's rare these days but I still now and then get emails from folks that think Mailinator spammed them. As it says on our contact page, this is pretty unlikely. I say that because Mailinator is custom software and that software contains no specific way to actually have a user "send" email. There's no chance of Mailinator being an open-relay as it stands. And of course, there is no place at all on the site to accept an email for sending.

I suppose its possible, but it would involve a hacker breaking into the server, installing some other email server (which would likely conflict with mailinator itself), configuring it, and then start pummeling it for their nefarious purposes. Given that any self-respecting spammer has a billion zombies at their disposal and that this would definitely be discovered very quickly (my colo vendor loves to watch my bandwidth), it doesn't seem like an efficient way to spam.

In any case, I still get accused of spamming at times. And all that accusation takes is for a spammer to forge the return address as a mailinator address. Let me tell you, forging a return address is stunningly easy. Here's 3 million or so guides how to do it if you're wondering.

Below is an actual email header someone sent me.

The interesting parts are really the first two lines. As you see the forged return path is ronb@mailinator.com. Now if you know mailinator, you know ANYONE can check that box. It belongs to no one and everyone (as outlined in the FAQ - Mailinator guarantees NO PRIVACY. All emails are viewable by ANYONE).

The 2nd line (i.e. Received:) shows the IP (and dns) of the server that actually sent the email. Something at abac.net. That looks like a hosting company somewhere. One thing I can tell you though is that that server has zero to do with mailinator. The spam email never ever touched the mailinator server. So even if I devoted my life to stopping this email, there's nothing I could do.

Return-Path: ronb@mailinator.com
Received: from 216.55.169.94 (216-55-169-94.dedicated.abac.net
216.55.169.94)
by smtpin4.mail.de.uu.net (8.14.1/8.14.1) with SMTP id n083RPV6001157;
Thu, 8 Jan 2009 03:27:26 GMT
Message-Id: 200901080327.n083RPV6001157@smtpin4.mail.de.uu.net
From: "RON" ronb@mailinator.com
Reply-To: "RON" ronb@mailinator.com
To: xxxxxxxxxxxxxx --> edited

This is sort of similar to a phishing attack. Someone gets an email from their bank, then goes to the phish site, then loses all their money. In truth their bank had nothing to do whatsoever with any of that but the bank still gets blamed.

The saddest part for me is that even after I respond to people showing them the real culprit, its not uncommon for them to stay mad at me. I suppose its because they then don't know who they're going to yell at now and I'm still available for the job.

Mailinator is about letting you protect your real email address. It might be to prevent spam but at times it might even be to receive spammy email they really want (just not at their primary address).

Regardless what you use it for, it won't email you. It just doesn't do that.

Plenty of people threaten to blacklist Mailinator from ever sending them email again. Yes, please do! As I've said in the past, feel free to put mailinator.com on the tippy-tippy-top of all your spam blacklists. Mailinator doesn't send any email at all - so you can be sure any email that looks like it came from a mailinator address is forged. And I'll sleep just fine if such email gets blacklisted.

Dear World, email addresses are not identity

2008-12-08T15:34:00.000-08:00

Its no secret that part of putting up any website or service is the consideration of security measures to stop people from abusing the system. And as you can imagine, those particular issues are probably doubled or tripled with a site like Mailinator (and of course Talkinator). Needless to say, I've gotten pretty good at unorthodox security.

Anonymity does indeed breed bravery.

The normal Mailinator use case is that you have a need for a quick email address to sign-up for some web service. Some people however, use Mailinator as an actual primary email repository. With the RSS feed, it acts as a convenient dropbox for newsletters or other semi-private email needs.

Unfortunately, there are some wacky funsters out there that think it might be fun to sign-up for some website over and over and over and over (and over). Often this is for some site that has "vote for your favorite band" or "sign up for a free gift" or some such thing.

The primary flaws of these systems is not Mailinator - its that these websites equate the idea of identity with email addresses. Seriously, long before Mailinator existed I had 3 or 4 email accounts that I actively used and another 10 I had probably abandoned. I'm not sure what those site designers were thinking - Mailinator or not, email addresses are FREE.

If you give someone something that has any value at all in exchange for free email addresses, they're going to ask for lots. I'm probably in a unique position to view this, but I see this idea as incredibly broken.

One option I had was to simply ignore this idea. Let crafty script-writers create systems that sign up for Wink accounts 1000 times an hour. (As I write this, I'm watching some automated system using several hundred IPs trying to sign-up for wink.com using Mailinator - and watching the Mailinator system dutifully send each request to the abuse page).

The problem with this is that someday, wink.com will catch on. And they'll ban Mailinator. This is sadly, a wonderfully broken solution to a still existing broken site design.

The problem for me is that I likely have legitimate users that want to sign up for Wink - and I want them able to do so (and I imagine Wink might want more users too, so by extension they'll lose some or all of the ones I lost). What's insanely broken for sites banning Mailinator is that there are tens of Mailinator-copy-cat disposable web services out there. Or even worse, someone with access to a server and a domain, who can install sendmail and create a few thousand accounts. Simply put, banning mailinator is like catching a single mouse and thinking you've solved the mouse problem.

You stop the bad guys, but for about a day until they implement a new system.

I had an interesting discussion with an acquaintance recently. During the conversation I described Mailinator to him. His mouth gaped open and told me he would look into it and probably ban it from his site. I asked what he would be banning it "from". He said he had a trial piece of software that people could sign-up for and download. And he wanted their real information to email them later (i.e. I did my best not to say that he was sending "spam") to see if they wanted to buy.

I noted that sometimes when I download software to try, I do want to enter my real email. I'm interested enough to want to be registered. But other times, I'm just in browsing mode. If given the chance I'd download and check it out, but if you give me too much impedance I'll probably just go check out his competitor.

In those cases when I'm just browsing, I'll use mailinator.

In other words, there are 3 types of potential customers. Those that don't care about his software. Those who really love the idea of trying his software and will do anything to do so. And those who are on the fence.

For obvious reasons, Mailinator is my "on-the-fence" tool of choice. If he banned it, he'd be refusing some subset of those potential customers. So it basically comes down to the question - whats better?

1) Definitely get user information you can spam later - or
2) get your product in front of as many eyeballs as possible.

Also noting the fact that NO email insures any relation to an actual person whatsoever (including yahoo, gmail, hotmail, etc.) - whats the point?

We continued our discussion and agreed that from a marketing perspective, you actually don't want to remove the email sign-up altogether. It actually brings value to some customers. If you remove it or make it optional, most everyone will skip it just to get to the goodies. But by leaving it and knowing that some people, using Mailinator or Yahoo or whatever, will give you temporary email addresses, you're maximizing your potential customer base.

It didn't hurt my argument to mention a few other disposable email services that he'd have to ban too. I sure don't know them all - they seem to come and go a lot. And that surely doesn't count ones that run semi-privately. Basically, it would be a fulltime job to keep up.

Oh. So, back to our script kiddies above. Mailinator includes a system to stop scripts from signing up for websites over and over. I love fun algorithms/data-structures so your homework can be to design something like Mailinator's abuse trigger system - a key-value datastruct that ages with time and is refreshed by lookups that come in at some notable (and tweaked) rate (in the same ballpark as a LRU cache, but definitely more dynamic).

Its unlikely a human will set-off the triggers but its possible. The sad part (for script writers) is that the algorithm doesn't trigger until their script gets going, so its probably a bit heart-breaking to spend a few hours perfecting a script to scrape Mailinator and then have Mailinator detect it only once it gets going and shut it down hard.

The first level is the Abuse Page. If you push it, Mailinator will ban IP addresses - but only under certain conditions. That's rather an imprecise way of stopping abuse. In addition, it looks for patterns of mailbox usage regardless of IP. An obvious one is that if one subject "Welcome to Wink!" shows up a lot in the read emails. Sadly, its difficult to distinguish valid users trying to sign-up for wink amongst the botnet hitting right now - so they'll probably get the abuse page too for the time being.

Potential site abusers taught me a lot and hardened the site considerably. Abuse attempts are still a common occurrence but far less normal than a few years ago. I assume many scripters went to less caring disposable services.

I often get asked if I care if sites ban Mailinator. I don't really. In some cases its prudent if you really do need to email people that use your service. In most cases however, its simply a knee-jerk reaction attempting to patch an otherwise flawed system. Not only is it a sure way to eliminate some potential customers, the flaw will show up again soon when the abusers shift to another method - and probably another method without Mailinator's facilities to stop scripts.

In the end, there is no real identity on the Internet. At least none past an IP address and a subpoena. At best, email is optional identity. And prudently, it should probably be treated that way.

Reserved Names in Talkinator

2008-12-04T10:04:00.000-08:00

Talkinator now includes a beta feature (ok, all features are beta) to allow reserved names. Each room can have only one and the person owning the site (and cut and pasting the code) designates the reserved name and the password to access it.

If you already have a Talkinator in your site, just click the </> icon (i.e. get the code!) in the upper right of any talkinator chatbox and create your Talkinator with your reserved name!

Please let us know how it works and especially if you find any bugs! (email to support@manybrain.com)

So, Mailinator's core-duo server now gets 3 Terabyte a month

2008-11-11T15:55:00.000-08:00

Its been awhile since I've updated my article The Architecture of Mailinator. That was a long time ago and really and tons has changed. To save you reading that article if you're in a hurry, the crux was that Mailinator was originally based on the unix email program sendmail, which pretty much died at around 800,000 emails a day. And then it discusses the design of the fully custom SMTP server designed for mailinator.

In that article, Mailinator was running on a single AMD cpu and processing 3 million emails a day or so. Well, somewhere in there I got a deal with my hosting company and was running a dual dual-core opteron machine. Mailinator ran on that for about a year as our email load doubled a time or two.

Eventually I needed a server for another project and realized that giving Mailinator that dual-opteron was pretty overkill. So I "downgraded" the machine to a core-duo. Which is where it runs now. In the aforementioned article we were getting 3 million emails a day - now I sometimes see 2 million an hour.

For the geeks out there, this is still of course a highly-multithreaded java implementation often running 4000 simultaneous threads. Pure Java I/O (not that stinky and slow NIO.

Today I got an email from my hosting server that I "surpassed my allotted bandwidth". I'm pretty used to getting subpoena's and such, but not so many of these.

Apparently, Mailinator received 3.1 Terabytes of email in the last 4 weeks.

Thats (ballpark) 480 million emails or so in that 4 weeks. As I've said before, that doesn't compare to any bigger email service, but then again, I bet they have more than one server :) I'll also emphasize that numbers I usually throw up here were measured or calculated by me - that 3T number comes from my provider so I hope its accurate as they want money for it !

Thats a LOT of spam (sure there's web traffic in there which might be hefty in other circumstances, but it doesn't hold a candle against the mail traffic).

I've priced things out and although my server still has plenty of computing capacity left, I'm clearly hitting an artificial (i.e. pay for more) bandwidth limit. It makes far more economical sense to simply get another server (per all pricing schemes I find) than to buy more bandwidth on this one.

So, someday I'll get around to writing the next "Architecture of Mailinator" article and although it almost sounds funny to me after all this time, I'll likely be talking about "both" Mailinator servers. Not just our trust little core duo.

The Revolutionary Fuzzy-Logical Super-Duper Mailinator Captcha System(tm)

2008-11-03T07:52:00.000-08:00

So, after many years of resistance for various reasons, Mailinator has finally implemented a DELETE button. That's right. The number one frequently-asked-question that isn't in the FAQ has been answered.

The reasons for its delay are many. In the early days I was too worried that someone would write a script that would attack the system and delete every email out there. Then after a year or two of people writing scripts to attack Mailinator in every other way - I had enough AI built into the system to stop most of it. (As always, I define "attack" as something that could bring the system down or ruin its use for other users - spamming Mailinator is really not on the radar, its not our place to define what is spam in this context).

Subsequently, I looked at implementing it a few times but tended to back off. If you've read this blog awhile you know that Mailinator and Talkinator at least partially existed as a testbed for implementing server ideas (some earlier articles: The Architecture of Mailinator and Benchmarking Talkinator).

And while implementing a delete function might sound simple - it had some interesting complexities in the architecture. In any case I'm happy to say - its finally here.

And here's the best news. To thwart all those rascally script-kiddies (who probably have seen the rather hidden but sometimes funny Mailinator Abuse Page) we're proud to announce the "Revolutionary Fuzzy-Logical Super-Duper Mailinator Captcha System(tm)" !!!!!

Thats right. The great service and ironclad spam (fighting/loving/tolerating, your call) abilities of Mailinator are now in a REVOLUTIONARY captcha system! We could have used a pre-written captcha system but that would have been sadly inferior and very non-mailinatory!

Just look at it and you'll know that this is going to take some major AI, image processing and statistical analysis to crack past this sucker.

Oh. And one more thing.... (got that from Steve Jobs)

We at Mailinator are happy to announce that this Captcha system is just TOO GOOD not to share with the world. So, you guessed it, we're releasing it as a web service !

You can now include The Revolutionary Fuzzy-Logical Super-Duper Mailinator Captcha System(tm) in your websites too !!!

Here's the highly-technical, low-level URL:

(edit: url momentarily removed due to immense user respo.. ok.. just a bug... be bak soon)

(where yourDestination.html is where you want the captcha to go after very securely and precisely verifying the humanness (and also non-computerness) of your user).

Put this in your web pages and sleep well!

(Disclaimer: This captcha system, although highly-advanced and chock-full of the latest advances in modern artificial intelligence does a better-than-expected job of verifying humans are humans. However we've noticed an eensy bug that seems to prevent it from sometimes (or "usually" really (actually its probably more like "mostly" (sometimes its pretty "always" tho))) figuring out that computers aren't humans. So consider this and "alpha" release.. or maybe "pre-alpha" or something like that. A "prototype", yeah, its a "prototype").

PS: Have your own idea for a captcha? Make the image 80x24 pixels and send it to support@manybrain.com !

PPS: The delete function is in beta. Please let us know of any bugs.

The Developer's Mailinator

2008-10-23T10:17:00.000-07:00

I get a surprising number of emails from developers testing some sort of emailing system and wondering if its "ok" to send those emails to Mailinator.

Of course - the answer is yes!

In fact, thanks to an email from one of those developers named Dave, I've actived port 587 on Mailinator to be an active receiving port (in addition to port 25).

Mailinator has always accepted email addressed to any domain - (i.e. have a domain name? point your MX record to the mailinator server and it will arrive just fine) so it really is a pretty solid testbed. Remember, you can see the raw email (headers and all) by clicking the "text" link on any mailinator show-email page.

The only caveat here is that Mailinator's defenses don't come down ever - even for testing. If you want to send a few thousand emails to Mailinator, it very well might start throwing emails away. As is sort of our goal - we don't mind spam (actually - given the nature of Mailinator - who are we to even define what spam is?). But we ARE interested in the Mailinator service staying up and running. Any legal (and nice - please read terms of service) use is fine by us - but if Mailinator thinks you're being overzealous, we'll probably side with it :)

Mailinator for your IGoogle Homepage

2008-09-02T08:12:00.000-07:00

Frank Ellermann has created a very pretty integration of Mailinator into the iGoogle homepage. It now installs with just a click!

Thanks Frank!

See it here: Mailinator iGoogle.

Benchmarking Talkinator

2008-08-20T14:08:00.000-07:00

I really wrote Talkinator for one reason - to play around with some server architectures I had bouncing around in my head. Now, any programmer in almost any language will tell you that it would take just a few hours on a Saturday to write a chat server. Its really not that hard.

If you add in the fact of using Ajax and then emulating sessions over a stateless protocol, and then add in a mildly usable client, you're probably up to a weekend or two. But its still not rocket science.

The Talkinator server in reality took me over a year to write. Partially because it was a weekend project and I surely didn't give every weekend to it. Also, because I ripped out the architecture more than once. At first it was a Java applet that did nice pretty TCP communication. I made a false assumption that applets, maybe after 10 years, didn't suck anymore. But I was wrong. They still suck - and a lot.

Finally, I settled on the ajax client model it is on now. I also really didn't want to use asynchronous/NIO networking. The world seems to still fight me (without doing their own benchmarking) but NIO only makes sense when you can't do Thread-per-connection. On linux, threads (using NPTL and kernel 2.6) are cheap now. And Java IO (synchronous I/O) is measurably faster than Java NIO (asynchronous I/O). In fact, this has nothing to do with Java, I've had many great conversations with C++ folks who find the same thing.

This is where chat becomes mildly interesting. Chat is of course, a "broadcast" networking model. That is, one user sends a message and that message must be propagated to some number of other users. Clearly, many networking applications follow this model, but given that chat is just text - its a rather pure form. It has comparably few details and I could focus just on the data pushing part.

As I said, writing a chat server is easy. However, like many things, writing a chat server that scales is harder. And because of its combinatorial nature, it grows dangerously fast. For this reason, it seemed like a fun project to make a fast broadcast server.

I mentioned that asynchronous/NIO is still suitable when you cant do Thread-per-connection and for Java you soft-max at around 12000 threads (in my testing) and hard-max at 16383 (JVM just wont make more - although some JVMs goto 32767). A chat server is almost the canonical example of a server that has very many, low traffic connections. Its a perfect candidate for NIO.

The trick with synchronous I/O is that a thread will block on every read and every write to the clients. A chat server has the bandwidth to handle 10's of thousands of users, but not if every user equals a thread.

Although synchronous IO reads and writes are blocking, the sequence of conversation events (avoiding the word "protocol" here) in this scenario is clearly defined. Once a client opens a socket and sends a message (on a blocking read), the thread can basically abandon that client. Simply put the client in a data structure and go off and service other clients. The client connection then "hangs open" until some thread comes back and gives it some data (i.e. someone in the same room sent a message). Note that the thread does block on that initial read, but in essence, we know its coming right away. And if it doesn't, we be sure to have a fast socket timeout for this particular wait.

In effect, Talkinator is a synchronous IO system which can support tens of thousands of open connections, running on just a few hundred threads (on a LAN it only needs a few tens of threads).

The weird part to me is that this is a blocking-IO but non-thread-per-connection server.

Every incoming message wakes up a thread to do the data read. Now each incoming message causes the need for (on average lets say) 10 outgoing messages. So sending is a lot of work as compared to reading. But we only wake threads for incoming messages - so once a thread enters the system when you say "Hello there", it has a lot of work to do on the sending side. The threads however, aren't picky about who's sending work they do. A thread you woke might remain active for a long time sending messages in rooms you've never heard of. If one thread incites the need for 100 outgoing messages, a small army of threads spawned from previous incoming messages jump in to help with the sending work. Once the current mound of sending work subsides, threads start going inactive (until more messages arrive).

Messages are queued for each user. When the system isn't too busy, most messages go out by themselves with very low latency. But as the system gets busy, message queues might grow a bit. Thus when a send finally happens, all those messages get sent at once. In effect, its sort of a "dynamic batching" system. We trade latency for throughput (and memory) on a dynamic basis. Room merges cause 30 deep queues but those are rare. Even in busy times I don't see deep queues at all - this implies low latency.

We call many pieces of software out there "engines". But to me, this really is like an engine. The faster it goes - the faster it will go. It is its own chain reaction.

One final note on this engine - I use no blocking queues (in the synchronization sense, not the IO sense). To me, blocking queues are simply a forced thread context switch. I let the thread that did the accept then jump in and do the read and subsequent work. On linux, a thread timeslice is on the order of 10ms before its forcibly swapped out. You can service a lot of messages in 10ms. A context switch isn't hugely expensive but its not free either and I see no reason to force more than will already happen.

Also, a socket accept followed by an immediate read is also probably a context switch. Because chances are, the read data isn't here yet (although we know its coming) so I'm right now playing with the idea of a thread accepting, then going off to help other threads do some sending, then coming back to do its read. Hopefully giving the read a chance to have its data in incoming-buffers first.

I started the project with Tomcat but quickly moved away and wrote my own webserver. Of course, using blocking IO. I found quickly that my little webserver could serve at most about 25000 web requests per second. It turns out that this isn't a limitation of my webserver. Socket accepts in linux (and probably everywhere) are damn expensive.

I expanded Talkinator's webserver to use keepalive (a fundamental feature on every contemporary webserver). In my benchmarks now, on my quad-core desktop the talkinator server can push about 39000 messages per second. Keep in mind this is processed messages as in decoded, packaged, and queued for particular recipients. (I often see claims of people sending millions of messages per second on various non-chat systems - this is quite easy if you don't have an incoming request to parse and are sending one-to-one endpoints - simply fill a 10G buffer with pre-formatted messages, start the timer, and hit "send" - basically your CPU is doing nothing and all you're measuring is the speed of your network).

I'll note that pretty much the entire software stack of Talkinator is custom. The webserver, the RPC, the cometd mechanism, and even the message encoding. Apart from an exercise in performance and me having fun, there was no particularly good reason to re-invent all those wheels. Just "adding another server or 3" would have probably worked equally well.

The ajaxian portion of the system requires that a message is sent per user every so often regardless of activity. If in fact, if we make an aggressive estimate that each user gets a message every 10 seconds, then one talkinator server could handle 390,000 users. This is an interesting thought exercise but its my expectation that the bottleneck of the system will be bandwidth or memory long before we ever run into an actual CPU problem.

I'll specifically note here that this discussion was not about scalability at all. It was about per server throughput. The talkinator scalability model is orthogonal would probably warrant its own blog entry.

This server would be faster if written in C++ or C. But the threading techniques I employed here were only possible (for me I mean) in Java. If this performance seems out-of-whack to you in any way, simply write a server in your favorite language that reads but ignores the incoming request and returns a tiny html webpage as fast as it can. This will give you a feel for the "fastest possible webserver". After that, every feature is slowing you down.

I don't suppose there is a moral here other than this is an experiential report of one of my weekend projects. Seriously, if you still believe asynchrounous/NIO beats synchronous/IO (and it did when linux threads killed the system after just a few hundred were started) you might want to do some research. Threaded socket programming is back.. and with a vengeance.

Bob Cringely on Talkinator

2008-07-30T09:12:00.000-07:00

Bob Cringely, well-known computer industry guy wrote a nice article about the "Five percent solution". He uses Talkinator as prime example!

I like this idea - I remember many years ago someone telling me about Google and I thought they were nuts - "I have Altavista - why do I need this Google thing? (silly name by the way)". Or even a bigger one for me was when I first heard of YouTube - so some little guy is going against an already established Google Video with their only real distinguishing feature is that they only allow "short videos"?

Bob's right - sometimes a very established idea simply needs a 5% twist to take it to the next level.

Thanks Bob !

Talkinator notes

2008-07-24T18:06:00.001-07:00

When Mailinator came out, people simply couldn't get over the fact that there was no login - I mean, how can you have email that doesn't have a login and password? It was a very strong paradigm shift for some folks.

For Talkinator, this paradigm shift has so far been the shock of "all of a sudden" being in a live discussion in a Talkinator room. Again, they didn't sign in or realize it would happen. Its rather common for people to not believe its actually live (often they assume its some sort of advertisement).

It took awhile for people to get-it as far as how Mailinator works. Paradigm shifts come slow - but they're often a lot of fun.

Introducing... Talkinator(tm)

2008-06-24T11:39:00.000-07:00

Mailinator's creation was rather an exercise in disbelief. After all, there isn't much to it - in fact, its just email with some key components removed. That is, no sign-in, no registration, and no passwords. At first glance, it seemed like there'd be no purpose for such a thing - but people on the Internet have a sneaky way of finding uses for new paradigms.

From that idea, Mailinator has a new little brother - Talkinator. If you've used Mailinator in the past few days its likely you've bumped into it. Its doing for internet chat what Mailinator did for email. No sign-in, no registration, no passwords. Fully embeddable in any website you want - or use it right from the Talkinator site.

As with Mailinator, privacy is not guaranteed or even implied(in the current incarnation, it sort of can't be) - so never put any personal information in Talkinator (or anywhere else on the Internet for that matter).

Talkinator is partially a part-two of the Mailinator experiment. Its also partially a logical extension - and also partially just the result of me tinkering around with a lot of ideas. It took a surprisingly long time to write, but thats partially because I wasn't in a hurry. Its using what is to me, a very experimental server architecture (which I'll write about eventually.. if it ends up working :) ).

Almost everything is custom including the webserver right down to the http parsing. That includes the RPC mechanism and even the http encoding. Non-custom parts include using the GWT to create the javascript client (which rocks) and Cliff Click's non-blocking hash map (which also rocks). It is in essence, an exercise in re-inventing the wheel AND premature optimization (or at least "meticulous optimization" - whether or not its premature is up to debate).

There's plenty more to say here from a user and technical standpoint, but I'll stop talking for now - so that you can start.

Mobile Mailinator

2008-04-12T01:33:00.000-07:00

Great idea - a nice write-up on how to use Mailinator on your mobile phone!

http://ergo.rydlr.net/?p=63

How fast is Java Volatile? or Atomic? or Synchronized?

2008-03-30T14:18:00.001-07:00

This is a question I've wondered awhile. And I've gone ahead and made a stab at finding out. One question that I had was I had always heard that AMD chips have an on-cpu memory controller and Intel's don't (at least not until they're upcoming Nehalem line). Now I'm first to admit I'm talking above my knowledge (please correct profusely).

But the idea was that some operations (notably I've heard volatile reads which I didnt test here) are very similar regardless of volatility.

I spent a few hours making up a benchmark. I'm publishing the benchmark below for one important reason - to get it right. This is big disclaimer: Don't trust these results - at least with any precision. I do conclude that contended synchronization is expensive - thats a pretty expected result so hopefully we're somewhere on the right track.

However, Java benchmarks are very hard to right. So hard in fact that they do a hardness-overflow and end up looking easy - which is precisely what makes them so hard to get right. Hence - given that only I have seen this benchmark, its pretty likely to be broken some (and hence why its published here for public review to help fix).

With all that...

What I've tested here are storage operations. Specifically:

Storage to a local variable (mostly used as a control)
Storage to an instance variable
Storage to a static variable
Storage to a static volatile variable
Storage to a static AtomicLong variable
Storage to a static variable protected by syncrhonization

I tested this on 3 different CPUs, all with JDK1.6 and variously on Linux and Windows. One very important point is do *not* compare the absolute numbers in the graphs directly. In no case are comparing the same CPU across 2 operating systems. The CPUs are wildly different in capability.

So we can explain more with a graph:

This is the run on a dual-core dual-Opteron machine. Note the blue-bar is local variable storage. As you'd expect it simply destroys everything else. This is very probably because the smart JVM went in and realized it could optimize the assignment out of the loop. Note the blue-bar just gets happier and happier as we add cores. The threads are completely unaffected by each other and we get actual linear increases in power. Even at 5 threads (note we have 4 cores) we get some speedup.

The orange and yellow bars are instance variable and static variable stores respectively. Some level of indirection or inability to optimize jumps in and makes things a bit more sane. Surprising we get little or no improvement as we add threads.

The three thread-visible methods of store are so slow they barely show up. This brings up an important point, let's assume you wrote an application and made it correctly thread safe. Using synchronization or volatiles or whatever. You *cannot* optimize away synchronization in the name of performance. It simply can't be done. (conversely, if you could then it wasn't correctly thread-safe to start). You can however, at times, replace one type of synchronization primitive with another.

That being said, lets take a closer look at the same graph with just the barrier memory store operations.

Volatile and Atomic are neck-and-neck. Synchronization is still a big loser, especially after we contend giving it two threads.

One other anecdote - while running the non-memory-barrier benchmarks, my CPU meter showed 100% user space usage. With these benchmarks however, it went to 30-40% kernel cpu usage.

Ok, jumping to the Core2Quad Extreme CPU. Definitely a faster processor but with a different memory architecture.

Local store again goes flying. Oddly the instance store doesn't do much but the static store increases nicely with the cores. And, once again, we can't even fricken see the barriered writes.. so here they are.

Look how great the JVM does knowing that just one thread is out there. It can really optimize the code to elide or at least marginalize the impact. Surprisingly, synchronization still gets nailed across the board.

Note that according to what I have so far, a synchronized static store is something 50 times slower than a simple static store. And 10 or so times slower than a volatile static store.

One more.. and its a fun one. Windows XP running on a Dothan. (Funny, I realized I hadn't directly known that Dothan was single core, but I just assumed it after I saw the graphs.)

Crazy. Add a few threads and performance doesn't even budge. Of course, with only one core a system can completely avoid all the complex architecture keeping cores in sync. Why its local writes are worse as compared to instance beats me.

Also, although I said don't compare graphs, this little single core Dothan beats the Core2Quad in all barrier-ed writes after 2 threads. Note that on the local writes, the Core2Quad is something like 50 time faster. But even on the simple static volatile store - at 2 threads, the Dothan is now twice as fast.

So. Pardon my informalness here - I'm actually quite expecting feedback to break this code in grand ways and force me to redo all the runs and rewrite all the text (which I'll be happy to do if we get a clean bench out of this). I have no intention of making very specific claims once this benchmark is firmed up - but I would like to have a "sense" of the costs of these different operations.

Source code for the Benchmark.

Introducing: Alternate Inbox Names

2008-03-27T22:26:00.000-07:00

Mailinator helps thousands of people every day avoid spam. It's been a great success.

One point that always sort of bothered me however was that by giving out a Mailinator address, you were basically telling people not only how to email you, but also how they can check *your* email. If I say "Email me at binkypop@mailinator.com", the whole world knows where to send and read my email!

Well, this is no longer a problem. Today we added "Alternate Inboxes" to Mailinator. We've always had alternate domains, but this is quite different.

Now, if you check any inbox on Mailinator (say, binkypop), listed on the page is the alternate inbox name. All alternate inbox names start with "M8R-". For example, for binkypop, the alternate inbox name is M8R-yg1hkn@mailinator.com.

So simply put, if you email binkypop@mailinator OR M8R-yg1hkn@mailinator.com it doesn't matter. Both emails would end up in the binkypop inbox (and nothing in the M8R-yg1hkn inbox). The only way to find out an alternate inbox name is to check the inbox here first - thus if you give out the alternate address, there is no way for anyone to guess that it actually goes to binkypop.

So.. pick yourself a favorite Mailinator inbox name (make it big, long, and hard-to-guess please!), go check the inbox to find out the alternate inbox name, and hand it out all over the web (of course, alternate domains work on alternate inboxes too!).

Then check the box (or RSS it) knowing only you know thats the real destination. Also, keep in mind - you don't have to remember the alternate inbox name ever - you just have to remember the real destination address. You can always go to Mailinator and get the alternate anytime just by checking the inbox. And of course, the regular think-up-on-the-fly-and-use Mailinator you know and love hasn't changed a bit. This feature is purely optional (I'm surprised how fast people started using it!)

(This feature is in beta and we might end up changing the alternate address scheme some)

This is cool. Alternate inboxes really do up the ante in Mailinator's spam fighting abilities. Enjoy !

Fun Mailinator server stats

2008-03-04T16:14:00.001-08:00

All averages have some fuzziness in them. Max numbers were observed but are unlikely the actual max.

100% custom SMTP Server written in Java using blocking I/O, multiple (at times thousands) of threads, and liberal use of non-blocking data structures.
------------------------------------------------------------

Average daily incoming emails: 6.5 million
Average daily incoming bandwidth: 18.4G
Average # of threads running at any time: ~450
load average: (uptime cmd) 0.04, 0.05, 0.00

Average email size: 2194 bytes
Ram devoted to email storage (compressed): 400M-500M
Average number of stored messages: 218,675
Average number of active inboxes: 94.575
Average memory allocated to Java VM: 880M

Max observed emails in one hour: 1,000,085
Max observed emails in one second: 1,274

Kill the myth please. NIO is not faster than IO

2008-02-18T14:39:00.000-08:00

I'm giving 3 talks at the Software Developer's Conference West in Santa Clara, CA on March 3-7.

One of them is a tutorial on how to interview in Silicon Valley (fun stuff).

Another is how to write high-performance servers in Java. Specifically, why NIO is really not the best way anymore (post linux 2.6 kernel and NPTL) and multithreaded I/O is the new old-way of doing things. Its a fun talk and largely discusses the internals of Mailinator and how it runs a few thousand simultaneous threads without breaking a sweat.

On top of that, as it turns out, in pure throughput, IO smokes NIO in all tests I tried. And I'm not alone - Rahul Bhargava of Rascal Systems did a very nice analysis of this and posted it, sadly, in some forums at theserverside.com.

The post is solid gold and I'm posting it below just for posterity as I'd hate to see those forums come down some day and I lose access to that post. Incidentally, I disagree with Rahul that "fewer threads are easier to debug". It only takes 2 to make a deadlock or race condition.

The original URL for this post is:
http://www.theserverside.com/discussions/thread.tss?thread_id=26700

And like I said, it was written by Rahul Bhargava of Rascal Systems. Here it is:

-------------------------------------------------

I have been benchmarking Java NIO with various JDKs on Linux. Server is
running on a 2 CPU 1.7 GHz, 1GB RAM, Ultra160 SCSI 36GB disk

With Linux kernel 2.6.5 (Gentoo) I had NPTL turned on and support for
epoll compiled in. The server application was designed to support
multiple disptach models :

1. Reactor with Iterative Disptach with multiple selector threads. Essentially
the accepted connections were load-balanced between varying number of
selector threads. The benchmark then applied a step function to experimentally
determine the optimal # of threads and connection per selector ratio.

2. Also a simple concurrent blocking disptach model was supported. This is
essentially a reader thread per connection model.

Client application opens concurrent persistent connections to the server
and starts blasting messages. Server just reads the messages and does
basic un-marshalling to ensure message is ok.

Results were interesting:

1. With NPTL on, Sun and Blackwidow JVM 1.4.2 scaled easily to 5000+ threads. Blocking
model was consistently 25-35% faster than using NIO selectors. Lot of techniques suggested
by EmberIO folks were employed - using multiple selectors, doing multiple (2) reads if the first
read returned EAGAIN equivalent in Java. Yet we couldn't beat the plain thread per connection model
with Linux NPTL.

2. To work around not so performant/scalable poll() implementation on Linux's we tried using
epoll with Blackwidow JVM on a 2.6.5 kernel. While epoll improved the over scalability, the
performance still remained 25% below the vanilla thread per connection model. With epoll
we needed lot fewer threads to get to the best performance mark that we could get out of NIO.

Here are some numbers:

(cc = Concurrent Persistent Connections, bs = Is blocking server mode on Flag,
st = Number of server threads, ct = Connections handled per thread,
thruput = thruput of the server )

cc, bs,st,ct, thruput
1700,N,2,850,1379
1700,N,4,425,1214
1700,N,8,212,1240
1700,N,16,106,1140
1700,N,32,53,1260
1700,N,64,26,1115
1700,N,128,13,886
1700,N,256,6,618
1700,N,512,3,184
1700,Y,1700,1,1737

As you can see the last line indicates vanilla blocking server (thread per connection)
produced the best thruput even with 1700 threads active in the JVM.

With epoll, the best run was with 2 threads each handling around 850 connections in
their selector set. But the thruput is below the blocking server thruput by 25%!

Results shows that the cost of NIO selectors coupled with OS polling mechanism (in
this case efficient epoll VS selector/poll) has a significant overhead compared to
the cost of context switching 1700 threads on an NPTL Linux kernel.

Without NPTL of course it's a different story. The blocking server just melts at 400 concurrent
connections! We have run the test upto 10K connections and the blocking server outperformed
NIO driven selector based server by same margin. Moral of the story - NIO arrives at the scene
a little too late - with adequate RAM and better threading models (NPTL), performance gains
of NIO don't show up.

Sun's JVM doesn't support epoll() so we couldn't use epoll with it. Normal poll() based
selector from Sun didn't perform as well. We needed to reduce the number of connections
per thread to a small number (~ 6-10) to get comprabale numbers to epoll based selector.
That meant running lot more selector threads kind of defeats the purpose of multiplexed IO.
The benchmarks also dispell the myth created by Matt Welsh et al (SEDA) that a single
threaded reactor can keep up with the network. On a 100Mbps ethernet that was true: network
got saturated prior to server CPUs but with > 1Gbps network, we needed multiple selectors
to saturate the network. One single selector's performance was abysmal (5-6x slower than
concurrent connections)

For application that want to have fewer number of threads for debuggability etc, NIO may be
the way to go. The 25-35% performance hit may be acceptable to many apps. Fewer threads
also means easier debugging, it's a pain to attach a profiler or a debugger to a server hosting
1000+ threads :-) . Bottom line with better MT support in kernels (Linux already with NPTL), one
needs to re-consider the thread per connection model

Rahul Bhargava
CTO, Rascal Systems

Mailinator allows 831375028249471605232943589 trillion different email addresses. Please choose a good one.

2008-02-07T13:01:00.000-08:00

Thats just an approximation really (allowing for 36 possible characters (there's more really) and email names of up to 25 characters).

Regardless, there's a lot of possibilities. So just a friendly reminder - please use Mailinator !!! But choose an offbeat name.
There's plenty to choose from :)

Update: math error, number was too low

More on the "pen1s" post

2008-02-01T11:34:00.000-08:00

In my post about searching 185 mailinator emails per second in Mailinator, I think I failed to adequately explain the goal of it. Its intent was to document a thought process - it was not intended nor tried to be a taxonomy of search algorithms (I gave some very nice links if you're looking for that). I really don't think the world needs another taxonomy of string searching algorithms, or at least not one written by me.. Nor does it need another academic analysis of any existing algorithms - there are plenty of those out there (and I linked Wikipedia in that post too where appropriate to describe specific algorithms).

Over a long history of reading about algorithms, I realized that I rarely found many analysis of algorithms from an engineer viewpoint. I am a recovering academician, but engineering is where you get to tinker with things. I've read many times Boyer-moore's best case is O(n/m) - but whats the *real* case? The usual case? How can that influence me in using any of these algorithms? Many searching algorithms display their worst case when you search for stuff like "AAAA" and your search string is "AAAABAAAABAAAAAB" - well guess what, I don't often search for that kind of thing in practice.

Also many people don't truly understand Big O notation (my great aunt made incredible homemade donuts, but ask her about algorithmic analysis? not so much). Considering some examples in the concrete, especially realistic cases can provide insight. For example, tell your favorite non-algorithmic person that there is an algorithm called "bubble sort", and it sorts numbers for you. But in order to sort 100 numbers, it has to look at each of those numbers on the order of 100 times. Effectively it must do on the order of 10,000 comparisons to sort 100 numbers - they'd look at you like you're crazy.

That post (and future ones in the series if i write them) attempts to detail an evolutionary engineering thought process on designing an algorithm for a specific purpose. The article started with the canonical "naive" but undeniably correct solution. When considering any problem, correctness is in my opinion, an excellent place to start.

I did not "forgot" to mention any other searching algorithms. They simply didn't not yet arise in this thought process (several people mentioned Aho-Corasick, which I didnt mention by name but certainly alluded to its features when I mentioned the finite state machines of regular expressions). A Trie is a basis for AC, but its definitely not AC (which others seemed confused about).

As I said, we're by far mostly interested in the "usual case" running time (which future installments will empirically demonstrate). I was also pretty clear in the last installment that what I had presented so far was *not* was I was using in Mailinator. Some people seemed to miss that (they people seem so excited to comment, they must have not actually read much of the post). I'm not sure how far this thread of blog posts will go - again, I'm documenting my thinking.

And very importantly, I was also clear (and trying to be clearer) that I am in some sense over-engineering this problem. I know that - that is basically a goal here. I likely don't need the performance I ultimately will end up with. This is not science - its fun.

So to concisely re-state the purpose of the blog entry - I'm documenting the thought process that coincided with evolving needs for an over-engineered multi-term string searching algorithm. Thought processes almost by nature go down wrong avenues - which isn't bad, its educational. The interesting parameters are such that we have a hundred or so words (expecting that to grow) and rarely find any of them. Engineering analysis is limited as compared to academic analysis in that you give specific cases and values - you are really only able to look at one instance of a big problem. But again, that all I'm trying to do here.

Thus, If you're looking for a in-depth explanation of Boyer-Moore (which some people who didn't read the sentence in the last post where I said I wasn't providing that) seemed to want, or you want a nice taxonomy of effective string searching algorithms, then you should probably go read something like that. Because this.. wasn't that.

As other interesting facts, I chose 185 emails/second because it was a relatively representative rate for Mailinator. I truly don't know Mailinator's max rate - I've seen 1200 emails/second and I've seen 10 emails/second. The number 185 was chosen as representative, not as the only possibility.

Finally, as I said, I'm aware of algorithms such as Rabin-Karp, Aho-Corasick, and Wu-Manber (in fact, I see Udi most days at work). From a storytelling standpoint, it wouldn't be much of a tale if I didn't get an interesting result in the end. Aho-Corasick is linear on the search space and Wu-Manber is nicely sub-linear. Not to give it away, but Mailinator's algorithm is also sub-linear. It isn't Wu-Manber and all truth be told, Wu-Manber is notably better in memory use and worst case running time.

If you're asking then why should you use such a thing? I'm not advocating you should. Again, the idea here isn't so much the final algorithm (which is really just the punchline). Its really way more about how we get there.