5 ms·

If you want sequential IDs with no chance of collisions, read up on "flake" IDs * https://blog.twitter.com/2010/announcing-snowflake https://blog.twitter.com/2

by mumrah 12y ago

If you want sequential IDs with no chance of collisions, read up on "flake" IDs * https://blog.twitter.com/2010/announcing-snowflake https://blog.twitter.com/2010/announcing-snowflake * http://engineering.custommade.com/simpleflake-distributed-id-generation-for-the-lazy/ http://engineering.custommade.com/simpleflake-distributed-id... * http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-ordered-unique-id-generator-in-erlang/ http://boundary.com/blog/2012/01/12/flake-a-decentralized-k-... * https://github.com/mumrah/flake-java https://github.com/mumrah/flake-java

thedufer 12y ago
"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).
- Goopplesoft 12y ago
  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.
  - gohrt 12y ago
    "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).
    - Goopplesoft 12y ago
      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.
  - malka 12y ago
    Yes. And my glass of water could spontaneously turn into ice. However, I do not expect it to happen anytime soon.
  - thedufer 12y ago
    Please, generate 2^<length>+1 of them and let me know how it goes.
- JoeAltmaier 12y ago
  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.
  - thedufer 12y ago
    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.
pauldbau 12y ago
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 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/src/NHibernate/Id/GuidCombGenerator.cs https://github.com/nhibernate/nhibernate-core/blob/master/sr...

by mumrah 12y ago

thedufer 12y ago

"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).

Goopplesoft 12y ago
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.
- gohrt 12y ago
  "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).
  - Goopplesoft 12y ago
    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.
- malka 12y ago
  Yes. And my glass of water could spontaneously turn into ice. However, I do not expect it to happen anytime soon.
- thedufer 12y ago
  Please, generate 2^<length>+1 of them and let me know how it goes.
JoeAltmaier 12y ago
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.
- thedufer 12y ago
  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.

pauldbau 12y ago

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 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/src/NHibernate/Id/GuidCombGenerator.cs https://github.com/nhibernate/nhibernate-core/blob/master/sr...