Aching Brain

Something we’ve been ruminating on at work recently is uniqueness.  We’d quite like everything in our system to have a unique identifier, usually referred to as a GUID or Globally Unique IDentifier.  This way you can access any entity from any place, and the display method of said entity is determined by the place of access.  By way of example, if you were to access an email, you’d see the email, but if you were looking at a folder full of emails, you’d see the email in the context of the folder that contains it.

Back to uniqueness though.  We don’t really need our GUIDs to be truly globally unique, only unique within our system.  Ideally we’d also like them to be short so if you email someone a url their client won’t wrap the line in the middle of our GUID.

The simplest way to ensure this would be with a number.  This is easy to maintain as they can be sequential, generated by a database and don’t need any special rules.  The only problem is the namespace is not very big.  If you allow five characters for your GUID in the familiar base 10 number system, you have 10,000 potential values, or 10⁵.

10,000 is a good start but what if you’ve got entities in different tables?  Entity#1 in table A is not the same as entity#1 in table B.  Perhaps we can do better.

The canonical GUID implementation is the Universally Unique Identifier or UUID.  UUID has been standardised as RFC4122 by people a lot cleverer than me so let’s assume it’s pretty good.  A UUID takes the following form:

550e8400-e29b-41d4-a716-446655440000

Right away we can see that it’s going to result in a much larger namespace than using numbers as it incorporates letters as well.  This expands the value each character can be from 10 to (26 + 10), giving us a base 36 namespace.  A five character GUID in base 36 has 60,466,176 possible values, or 36⁵.

Version 5 UUIDs are calculated by taking an existing source of uniqueness (a URL is recommended) and hashing it using the SHA-1 algorithm.  This is not fantastic for us as we’re trying to create a GUID which will be used in the creation of a URL, so we’re going to have to look elsewhere.

The simple thing to do would be to generate them randomly.  This is not as bad as it sounds and appears to be a standard way of doing it.  We’ve just introduced a subtle problem though.  As we are now randomly generating the GUID we become vulnerable to the birthday paradox.  From this rather nifty calculator, we can deduce that we’ll reach a 99.9% probability of a collision (eg. two items with the same GUID) with a five character GUID in base 36 after 29,903 items.  Although this means we are fairly likely to have collisions with randomly generated GUIDs, it’s still much better than using integers which reach 99.9% after just 372 items.

Clearly the way to increase the namespace is to increase the base of the number system we are using.  There’s easy thing we can do here – include capital and lower case letters.  YouTube do this to great effect, even including punctuation:

http://www.youtube.com/watch?v=ZOU8GIRUd_g

So lower case (26), upper case (26), integers (10) and underscores (1) gives us base 56 – 550,731,776 potential values at five characters, or 56⁵. No need to stop at underscores though – RFC2396 tells us that the only restricted characters for URLs are ; / ? : @ & = + $ ,.  That leaves !@£%^*()[]{}”‘\|><. etc etc.

At 11 base 56 characters, YouTube can accommodate nearly 17,000,000,000,000,000,000 videos (or 1.7 x 10^-8 hella videos) before running out of GUIDs.  When they do, they can just add another character on to literally increase the namespace exponentially or simply allow additional punctuation marks.  Taking the birthday paradox into account, they can have 15,325,262,787 videos before a 99.9% probability of collision occurs.  If they currently have 120,000,000 they are still a long way off needing to extend their namespace.

So there you have it.  Increase your number base to reduce the chance of GUID collision and make your life easy when trying to make everything in your database have a unique, email friendly identifier.

Popularity: 1% [?]

I’ve been trying to install Macromedia Adobe Flash Media Server 3 on my local development box and have run into some problems.

To help out anyone else trying to do the same thing, here’s how I did it.

First you need to install nspr

Add a user/group for it to run under:

Then download and extract the media server as per usual. Before installing it, you need to fiddle the install script so that it will install on your “unsupported” platform. Open installFMS in your favourite text editor and find the line that reads

Change it to something appropriate like

Then start the installation script as normal. Tell it that you don’t want it to run as a daemon (as it requires the Red Hat only chkconfig command) and that you don’t want it to start the server when done.

After you’ve installed the server, you’ll need to make the bundled libasneu.so.1 library available for use:

For some reason the install messed up the configuration files, adding things like the administrative user name twice. Check conf/fms.ini to make sure this hasn’t happened to you.

The installer creates init scripts at /etc/init.d but in order to use them you first need to create a file called .autostart in the installation directory:

You should then be able to start and stop the server normally:

And use rc-update to have the server start on boot:

Good luck.

Popularity: 35% [?]

I just came across this while using Prototype:

To save you the trouble of running it yourself, I’ll tell you what happens – the unescaped percent symbol causes a URI malformed error to be thrown.

Very odd. The Prototype documentation for toQueryParams says:

Parses a URI-like query string and returns an object composed of parameter/value pairs.

Since it’s a URI-like query string and not an actual query string (by which I mean one that’s been through the browser address bar and as such subject to whatever text munging the browser does), my example above should be a legal use case.

After a little digging around in prototype.js, it seems that the problem is caused by the JavaScript function decodeURIComponent() not enjoying being given a string that contains an unescaped percent symbol. Usually percent symbols are used in conjunction with a number to represent a non-alphanumeric character in a URL – %20 for space, etc, but in the above it’s a literal percent symbol.

My first attempt to fix it changed lines 98 and 100 of string.js in the Prototype source to use the built in escape function:

This worked for my use case but caused Prototype to fail a different unit test. Changing them to the following worked out okay:

Granted the unescape(…(escape(…)) is a little clumsy, but it seems to get the job done.

Adding the following unit test to string.html allows to test for the above:

I’ve created some test pages which demonstrate the problem.

There is also a patch file available. Apply it to /src/string.js in your Prototype source tree.

Update

I’ve also filed a bug.

Popularity: 36% [?]

This is more a note to myself than anyone else, but to compile Apache2 on OS X, use the following configure:

When Apache starts whinging about “dlname not found, assuming libtool archive” and shit, and refuses to produce .so modules instead kicking out a bunch of .a and .la files in their place, it means you’ve fucked up somewhere along the line, probably because this isn’t the first time you’ve tried to run the configure script.

Delete the entire Apache source directory and start again. If you are lucky you’ll even get a nice copy of libexpat.0.dylib at the end of it all.

Popularity: 33% [?]

Alex is currently wondering if the Glastonbury ticket website is run off of a beige box in the corner of someone’s flat with a cat chewing on the network cable.

Honestly, what with all the pre-registering bollocks it’s not like they were unaware of the demand. Why can’t they design a server infrastructure that can handle enough requests?

Popularity: 33% [?]