URL shortening – How do they do it

URL shortening services had experienced a big push in the age of social networks rising, such as Twitter, where big urls collide with the 140 characters user input restriction.

So there was this need of magically transform URLs like this one http://raduboncea.ro/2009/04/01/twitter-autofollow-and-dm-using-python-twitter-imaplib-and-gmail/ into something like this http://tinyurl.com/cralfk.

Many would be tempted to think there is some kind of compression algorithm that would shorten a big URL and make it fit into a unique combination of 4,5 or 6 characters and then decompressed upon user request. Well it doesn”t work like this, mathematics prohibit it.

So how does it actually work?
A URL shortening service takes the big URL and saves it into a database along with an auto incremented numerical value, an id or sequence, so we would have the first big URL saved with ID=1, the second with ID=2 and so on. When someone would ask for http://tinyurl.com/1/ we would get from the database the big URL identified by ID=1 and redirect the user to that URL.

But there is a problem: having numerical ids does not shorten urls too much. For the URL number 1 million we would have 7 numerical characters. So the next step is to change base numerotation from 10 to a bigger one, lets say 36, so we include all a-z small latin letters or, why note, 62 which includes also the capital chars A-Z.
In 36 base we can save as much as 1.679.615 URLs into 4 characters. On base 62 we have 14.776.335 URLs fit into 4 chars, almost 10 times as much as base32 and 14.776 times base10.

Some security issues.
Many shortening services stopped to the algorithm above without digging into a very important security issue which is related to how redirects work. It is critical, before redirecting users to the URL they requested to check what’s behind that URL, to check if the URL is not yet another redirect which may result into a recursive loop and may disrupt the service.

A malicious user may save a URL to a page which will later modify to redirect back to the service URL and thus attempting to generate an infinite loop which could make the interpreter to hang.

To avoid this kind of DoS vulnerability, we must not allow redirects to our own links and to limit redirects to outside to a smaller finite number of depths analysis.

Beneath a small model-view example in django, using also urllib to check for redirects and the base10-base62 conversion algorithm similar to the base36 which is included in django.





Washington Times gândește opensource

Ieri washingtontimes.com a decis să împărtășească câteva din sursele folosite de ei pentru ziarul online.

Sursele sunt module ale platformei django, o platformă de dezvoltare a aplicațiilor web
dezoltată în python pe principiul MVC, tot mai larg adoptată de programatori, mai ales după ce Google s-a decis să sprijine comunitatea Django prin folosirea acestei platforme în dezoltarea aplicațiilor proprii (Google Sites ar fi un exemplu) și suportul platformei de către Google App Engine.

Ce conține repozitoriul:

  • django-projectmgr, așa cum zice și numele este o aplicație de management conflicte, buguri, task-uri, todo, etc
  • django-supertagging folosește api-ul de la Open Calais pentru a genera tag-urile cele mai relevante conținutului
  • django-massmedia. Modulul ăsta l-am testat personal și este aur curat. Permite management de media content (imagini, muzică, video) în toate formatele existente. Are auto slugging, poate fi integrat cu supertaggingul de mai sus. Se pot uploada bulk conținut arhivat și prelucrarea lor în masă.
  • django-clickpass permite autentificarea openid, permițând conturile de Google, Yahoo!, Facebook, Hotmail, etc.

Ca o notă, toate aceste aplicații necesită ultima versiune de django (1.0.2). Nu funcționează cu 0.96.