Distributed ID Generation and Bit Packing | Hacker News Reader

Distributed ID Generation and Bit Packing

push.cx

25 pointsmr_tyzic9 comments

Open articleView on HN

He could have just Googled. I think Twitter's Snowflake came to some very similar conclusions.

https://github.com/twitter/snowflake/

I even wrote something in Ruby as an idea based off it (although it hasn't been used in production yet)

https://github.com/pmarreck/ruby-snippets/blob/master/star_i...

Another (old) example of how Flickr does (or quite possibly "did") this

http://code.flickr.net/2010/02/08/ticket-servers-distributed...

Also see...

Simpleflake (like Snowflake, but uses a random number in place of the coordinated worker ID and sequence number): http://engineering.custommade.com/simpleflake-distributed-id...

"How to Generate a Sequence of Unique Random Integers", which uses prime number quadratic resides: http://preshing.com/20121224/how-to-generate-a-sequence-of-u...

You can save a lot of time by using a UUID/GUID and encoding in a different base for urls if you want to minimize length. They're 32 chars in hex or 22 characters in base-64.

He discussed alternative encodings, and that he wanted to find out how short he could make the identifiers.

The 47-bit scheme (3 version, 32 timestamp, 8 sequence, 4 parallel), when encoded in base62 (see his discussion) yields 8-character identifiers. That's potentially much better for a user than a 22-char Base64-encoded GUID.

As a user I don't want to type a 8 symbol random gibberish identifier any more than a 64 symbol one. Don't waste your time with making it less painful, use the time to avoid this scenario entirely.

Agreed, I would've just base64-encoded a GUID and been done with it, but it was clear that the author nerd-sniped[1] himself and couldn't put it down until he'd come up with a solution.

[1] As always, relevant XKCD: http://xkcd.com/356/

There's more to ID length concerns than just URL length. Those IDs tend to be IDs in a database which usually need to be indexed. Even packing the 128 bits of a UUID into a binary(16) can make your indexes quite large and make queries with joins surprisingly slow.

I think extra effort to go below 64 bits may be a bit unnecessary, getting from 128 to 64 can make a big difference on the back end.

Rather than just shuffling the bits, you could do a invertible operations, like you'd use in a block cipher. An unbalanced feistel network (24 and 23 bit halves) would be easy to implement, or even just invertible operations like "x=x^rotate(x, 5)".

Reply on news.ycombinator.com