Wednesday, June 27, 2007

When you need to shoot the birds... pick the right cannon!

Today's post will be about... engineering, surprisingly. And a little bit about knowing the requirements upfront.

This is a story that happened back around RL's New Year's Eve, on a skate rink near the Paradize Lost. Helena was there, having fun herself and entertaining the public, and during the casual small talk she mentioned she wanted to make a snowmen contest. Which obviously implies voting.

It was a very interesting proposition - I usually do not script just for "pure money" (well, I do only if the money/time spent ratio is sufficiently high), but rather mainly for the sake of making something new and something I have not done before. Voting system I have not done by then yet.

So - the first question - "how many people are you gonna have voting?" - "don't know" - "well, 1000, 10000 or 10000 ?" - "still do not know".

Ok, I say for myself - let's take 50000.

"How many participants?" - "Not sure" - "less than 100?" - "yes".

Ok, this is something to start with. In any case, the overall design was pretty clear:

  • one prim per contestant to accept the votes, and display the results
  • some kind of validation storage, which would store the keys of the avatars who has already voted, to avoid double-voting.
  • the contestant prims would check out with the validation storage, whether the person has already voted, and if not - then store the vote, and increase the counter for that particular prim.
  • ideally, i would somehow be able to remember who voted for whom, and have the results auditable.

So, according to the requirements, I need to store some 50000 key-key pairs somewhere... (considering that an LSL script does not even get that many *bytes* of memory, it had to be something modular).

So, the first module is a "single storage script". An atomic piece, which can hold something like 100 pairs. Now, let's put ten of these into a prim - we get a storage unit, which can hold a thousand. The search is not fantastically efficient, but still...

Now we link a bunch of these "child storage units" to a single "master prim" which does the high-level "memory management" and figures which ones are full, where to search, etc.

All right. I spend something like 3 full days (there were some days off) to build this monster, and then was just about to show it, when I got invited to an event somewhere, and there was a griefer attack there.

The net result of the exercise was that I had lost all my hair. It took me a while to find back the place where I bought it, and buy another copy, but this loss of hair has prevented me from losing much more hair - when I thought about the same thing messing up my "superstorage".

Then I said "no way".

And hence a much more simple and almost as robust system was born. Indeed, I decided to use an external server. Being a little bit of a paranoid, I do not run any scripts on web server. Not at all. No exceptions. And I did not want to install mysql/php/whatnot, just for this. Besides, the machine I use is very very weak - so a theoretical spike in the requests I would not be able to handle.

So I needed another way... Ok, here we go. Create a new virtual host just for this, and write a script to continuously monitor its logfile.

The voting attempts are done via requests "/vote/voter-key-here?for-whom-to-vote" - if there is something, then the person has already voted. If not - then the HTTP server returns "file not found" and the vote can be recorded.

Needless to say, that this opens a race condition for double-voting for more than candidate during the time window when the request has been already sent, but not yet processed by the script (which monitors the requests in the logfile, and creates the file in "/vote" directory accordingly. However since it was not a military-grade application I did assume this margin of error would be OK. But actually I think I still tackled that. :-)

The files "/candidate/candidate-key-here" would contain the counters for each of the contestants, which would equal to the number of voices - and since the script that processes the votes would be single-threaded - I get rid of the concurrency issue - since the results are incremented centraly.

I do have an auditable log of all the votes - it is simply a htaccess.log - so if something messes up or I find a bug in the script - I can always just re-run it, first wiping out the files with the counters. Any surge is ok - since even my dumb server can still serve static pages reasonably fast - and any other computations I do at the pace *I* determine.

The "tail-and-count-votes" script on the server side I decided to write in Ruby - it is a pretty high-level and readable language, took around 40 minutes.

The voting prims were easy - just cut out the fat from the previous version that is not needed anymore...

So the overall result was ready in under half a day, with no significant brain strain - it was very simple.

There are a few lessons I grabbed out of this:

  • It is good to plan for scalability. But sometimes it helps to consider the "natural upper bounds" more carefully.
  • The first most obvious solution (prototype?) is not the best, but it teaches you. Make sure you can do it fast, and then proceed to "the real thing".
  • Don't be afraid to think outside the (LSL) box.

After some testing and a couple of bugs fixed, the voting system ran for a few weeks. The overall number of participants was probably around couple of hundred, and seems to have worked flawlessly, I did not get any single IM with complaints.

But maybe they were just merciful :-)


vint said...

Snow man contest? :d

Dalien said...

yes - it was at the skating rink =)