postgresql - Generating an Instagram- or Youtube-like unguessable string ID in ruby/ActiveRecord

Question

Upon creating an instance of a given ActiveRecord model object, I need to generate a shortish (6-8 characters) unique string to use as an identifier in URLs, in the style of Instagram's photo URLs (like http://instagram.com/p/P541i4ErdL/, which I just scrambled to be a 404) or Youtube's video URLs (like http://www.youtube.com/watch?v=oHg5SJYRHA0).

What's the best way to go about doing this? Is it easiest to just create a random string repeatedly until it's unique? Is there a way to hash/shuffle the integer id in such a way that users can't hack the URL by changing one character (like I did with the 404'd Instagram link above) and end up at a new record?

Answer 1

Here's a good method with no collision already implemented in plpgsql.

First step: consider the pseudo_encrypt function from the PG wiki. This function takes a 32 bits integer as argument and returns a 32 bits integer that looks random to the human eye but uniquely corresponds to its argument (so that's encryption, not hashing). Inside the function, you may change the formula: (((1366.0 * r1 + 150889) % 714025) / 714025.0) with another function known only by you that produces a result in the [0..1] range (just tweaking the constants will probably be good enough, see below my attempt at doing just that). Refer to the wikipedia article on the Feistel cypher for more theorical explanations.

Second step: encode the output number in the alphabet of your choice. Here's a function that does it in base 62 with all alphanumeric characters.

CREATE OR REPLACE FUNCTION stringify_bigint(n bigint) RETURNS text
    LANGUAGE plpgsql IMMUTABLE STRICT AS $$
DECLARE
 alphabet text:='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
 base int:=length(alphabet); 
 _n bigint:=abs(n);
 output text:='';
BEGIN
 LOOP
   output := output || substr(alphabet, 1+(_n%base)::int, 1);
   _n := _n / base; 
   EXIT WHEN _n=0;
 END LOOP;
 RETURN output;
END $$

Now here's what we'd get for the first 10 URLs corresponding to a monotonic sequence:

select stringify_bigint(pseudo_encrypt(i)) from generate_series(1,10) as i;

 stringify_bigint 
------------------
 tWJbwb
 eDUHNb
 0k3W4b
 w9dtmc
 wWoCi
 2hVQz
 PyOoR
 cjzW8
 bIGoqb
 A5tDHb

The results look random and are guaranteed to be unique in the entire output space (2^32 or about 4 billion values if you use the entire input space with negative integers as well). If 4 billion values was not wide enough, you may carefully combine two 32 bits results to get to 64 bits while not loosing unicity in outputs. The tricky parts are dealing correctly with the sign bit and avoiding overflows.

About modifying the function to generate your own unique results: let's change the constant from 1366.0 to 1367.0 in the function body, and retry the test above. See how the results are completely different:

 NprBxb
 sY38Ob
 urrF6b
 OjKVnc
 vdS7j
 uEfEB
 3zuaT
 0fjsab
 j7OYrb
 PYiwJb

---

Update: For those who can compile a C extension, a good replacement for pseudo_encrypt() is range_encrypt_element() from the permuteseq extension, which has of the following advantages:

• works with any output space up to 64 bits, and it doesn't have to be a power of 2.

• uses a secret 64-bit key for unguessable sequences.

• is much faster, if that matters.