Hacker News new | ask | show | jobs
by mumrah 4242 days ago
If you want sequential IDs with no chance of collisions, read up on "flake" IDs

* https://blog.twitter.com/2010/announcing-snowflake

* http://engineering.custommade.com/simpleflake-distributed-id...

* http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-...

* https://github.com/mumrah/flake-java

2 comments

For .NET / SQL Server people, check out GuidCombs if you want better Primary Key performance. These are a great way of making GUIDs sequential for database use, giving indexing performance close to ints on SQL Server.

I imagine this approach could also work on Postgres and other dbs that have made GUID/UUIDs a first class data type. You'd just have to understand how that database applies its indexing algorithm.

Description of the GuidComb approach here: http://www.informit.com/articles/article.asp?p=25862

GuidComb implementation in C# (from NHibernate core) here: https://github.com/nhibernate/nhibernate-core/blob/master/sr...

"no chance of collisions" can't be applicable to any finite-length ID. Low chance, perhaps.

That said, this appears to be exactly the scheme MongoDB uses (except Mongo IDs are 96 bits).

Ok, Less likely than the chance your computer will spontaneously catch fire while running your code. Less likely than the chance the sun will emit a colossal solar flare and engulf the earth in a firey death.
Right, but that's the point of a GUID. Claiming no chance makes it sound like its distinct from other GUID generators in that way. I think the intended claim is "here is a scheme for roughly timestamp-ordered GUIDs", which makes it clear that the timestamp-ordering is the interesting part.
Actually it can. As long as they aren't randomly generated. UUID4s are random, lots of them including the mongodb use a timestamp/mac address as the first n bits of the guid. Not sure whether they have "no chance of collisions" but it is very possible.
"no chance" means making a claim that there will never be 2^N devices generating IDs simultaneously (for N somewhere around 30-60)

2 machines can have the same MAC addresses (they are reprogrammable) and can operate at the same microsecond.

"aren't randomly generated" is not practical constraint in a high-speed distributed system (where you don't have time for synchronization overhead).

Its an infinitesimally small chance. You'd need a mac collision, must be generated at the same time, and a uuid collision. Even at the largest scales (Google et all) the probability of that happening is effectively 0.
Yes. And my glass of water could spontaneously turn into ice. However, I do not expect it to happen anytime soon.
Please, generate 2^<length>+1 of them and let me know how it goes.