There are a lot of questions here on stackoverflow regarding URL shorteners as well as elsewhere on the internet, e.g.
How to code a URL shortener?
How do URL shortener calculate the URL key? How do they work?
http://www.codinghorror.com/blog/2007/08/url-shortening-hashes-in-practice.html
However, there is one thing I don't understand. For instance, http://goo.gl uses four characters at the moment. However, they claim their short URLs don't expire. As mentioned in the article on coding horror, if they can't recycle URLs, the only possible solution is at one point to add an additional character.
Ok, so far so good. With 4 characters that means about 15 million unique addresses. For something like Google Maps, I don't think that is very much and if you can't recycle, my guess is they run out of available addresses fairly quickly.
Now for the part I don't get. While handing out addresses, they start to run out of unused addresses. They have to check if a newly generated address has not been issued yet. The chance this has happened and the address is already in use increases. The straightforward solution of course is to generate a new URL over and over again until they find a free one or until they have generated all 1.5 million alternatives. However, this surely can't be how they actually do it, because this would be far too time-consuming. So how do they manage this?
Also, there are probably several visitors at once asking for a short URL, so they must have some synchronization going on as well. But how should the situation be managed when the fifth character needs to be added?
Finally, when doing some research on how the URLs from http://goo.gl work, of course I requested a short URL for a map on Google Maps several times. None of them will ever be used. However, when Google would strictly enforce the policy of URLs not expiring once issued, this means that there are lots and lots of dormant URLs in the system. Again, I assume Google (and the other services as well) have come up with a solution to this problem as well. I could imagine a clean up service which recycle URLs which have not been visited in the first 48 hours after creation or less then 10 times in the first week. I hope someone can shed some light on this issue as well.
In short, I get the general principle of URL shorteners, but I see several problems when these URLs cannot expire. Does anyone know how the problems mentioned above might be resolved and are there any other problems?
EDIT
Ok, so this blog post sheds some light on things. These services don't randomly generate anything. They rely on the underlying database's auto-increment functionality and apply a simple conversion on the resulting id. That eliminates the need to check if an id already exists (it doesn't) and the database handles synchronization. That still leaves one of my three questions unanswered. How do these services "know" if a link is actually used once created?
