5 ms·

See also Firebase push IDs: https://firebase.googleblog.com/2015/02/the-2120-ways-to-ensure-unique_68.html https://firebase.googleblog.com/2015/02/the-2120-way

See also Firebase push IDs: https://firebase.googleblog.com/2015/02/the-2120-ways-to-ensure-unique_68.html https://firebase.googleblog.com/2015/02/the-2120-ways-to-ens... Lexicographically sortable identifiers are critical for any distributed data store if you want anything close to consistency. I've run into the issue of not having them and having to settle for some kind of <autoincrement_id><UUID> key and it's a huge PITA. How this wasn't considered database 101 decades ago just blows my mind. I'd like to see a spec included in this for synchronizing clocks or using RAFT/Paxos for generating ULIDs with strong guarantees on sort order. Also a minor gripe - I wish that the ULID spec checked for microsecond collisions instead of millisecond, because that would be more useful for realtime networked gaming and simulations.

pspeter3 8y ago
Do you know of any ID systems that have that behavior?
- nixpulvis 8y ago
  I'm pretty sure Google's Spanner uses something like Paxos, but you should fact check that, it might just be for replication.
- zackmorris 8y ago
  Unfortunately no, but some (many?) REST APIs turn the problem on its head by using private autoincrement IDs in the database and public UUIDs with either a direct 1:1 mapping between the two or a mapping that is unique to each user. This is mostly done for security reasons but I'm not sure if it's considered a best practice because it can introduce additional complexity at the sharding and caching levels (among others): https://softwareengineering.stackexchange.com/questions/371413/use-uuid-on-top-of-auto-increment-id https://softwareengineering.stackexchange.com/questions/3714... https://stackoverflow.com/questions/15360245/when-using-uuids-should-i-also-use-auto-increment https://stackoverflow.com/questions/15360245/when-using-uuid... https://softwareengineering.stackexchange.com/questions/139450/is-obscuring-obfuscating-public-facing-database-ids-really-a-best-practice https://softwareengineering.stackexchange.com/questions/1394... https://softwareengineering.stackexchange.com/questions/346971/should-backend-ids-be-public-or-not-on-a-rest-api https://softwareengineering.stackexchange.com/questions/3469...
AYBABTME 8y ago
the Go oklog/ulid package now supports that
- ngrilly 8y ago
  Supports what?
Dylan16807 8y ago
> Also a minor gripe - I wish that the ULID spec checked for microsecond collisions instead of millisecond, because that would be more useful for realtime networked gaming and simulations. If you can manage the difficult task of getting your clocks synced that precisely, it's probably easy to shift two characters over from random to timestamp.
- mehrdadn 8y ago
  > If you can manage the difficult task of getting your clocks synced that precisely It's only a matter of time (in both senses I guess). See e.g. https://blogs.technet.microsoft.com/networking/2018/07/18/top10-ws2019-hatime/ https://blogs.technet.microsoft.com/networking/2018/07/18/to...
nixpulvis 8y ago
At a certain point you'll end up wanting fancy clocks too. I believe this is what Google does with Spanner.
joatmon-snoo 8y ago
> Lexicographically sortable identifiers are critical for any distributed data store if you want anything close to consistency. wat? This doesn't make any sense to me. Requiring that events be partially ordered if not totally ordered is a consistency requirement, sure, but I'm failing to understand how a database's consistency depends on the data you're putting in the database.
- cryptonector 8y ago
  And now you need every host to have an atomic clock too. Maybe CRDTs would be better.
  - edoceo 8y ago
    I use ULID in a distributed system where some clocks are off by a bit, still works well, untill the skew is way off. The time can be extracted from the ULID for verification before INSERT.
    - riffraff 8y ago
      Won't removing time bizs increase the chance of collisions? UUIDs rely on a lot of randomness to avoid the issue, but in ULID this is much more limited, and the timestamp fills in for some of it, afaiu
      - edoceo 8y ago
        We don't remove the time bits, we inspect them for reasonable values. Eg: never ever older than 2014-01-01 and older than 24h from our clock gets extra logging+meta-data.
- advisedwang 8y ago
  I think they're talking about data locality. If a single processing step access data that are "neighbours", in some systems that data is likely served from a single server. This means a) better performance and b) higher likelihood of consistency. Of course the guarantee is still merely eventual consistency, but data locality does reduce the chance this becomes visible.
wyldfire 8y ago
> I wish that the ULID spec checked for microsecond collisions instead of millisecond Most computers don't have wall clocks with even more millisecond precision, much less microsecond. The wall clocks are generally OS tick precision (~5-10ms ballpark) with poorer still accuracy. Seems like the use case is one that is niche. Maybe an extension?
antonvs 8y ago
> How this wasn't considered database 101 decades ago just blows my mind. Decades ago they didn't have distributed data stores.
- vladsanchez 8y ago
  What is a database then? They've existed for close to 40 years now.
  - dragonwriter 8y ago
    Until recently (and even recently, for the most part) databases have been, almost entirely, centralized (though often shared) stores, not distributed stores.
jayd16 8y ago
Did anyone else find it ironically irritating that firebase example json was an unordered dictionary instead of a properly ordered list?
InGodsName 8y ago
Not just that, you can use range queries like this: https://redis.io/commands/zrangebylex https://redis.io/commands/zrangebylex To find events between two specific points. It can also be used in Dynamodb which is what we use in adtech.

pspeter3 8y ago

Do you know of any ID systems that have that behavior?

nixpulvis 8y ago
I'm pretty sure Google's Spanner uses something like Paxos, but you should fact check that, it might just be for replication.
zackmorris 8y ago
Unfortunately no, but some (many?) REST APIs turn the problem on its head by using private autoincrement IDs in the database and public UUIDs with either a direct 1:1 mapping between the two or a mapping that is unique to each user. This is mostly done for security reasons but I'm not sure if it's considered a best practice because it can introduce additional complexity at the sharding and caching levels (among others): https://softwareengineering.stackexchange.com/questions/371413/use-uuid-on-top-of-auto-increment-id https://softwareengineering.stackexchange.com/questions/3714... https://stackoverflow.com/questions/15360245/when-using-uuids-should-i-also-use-auto-increment https://stackoverflow.com/questions/15360245/when-using-uuid... https://softwareengineering.stackexchange.com/questions/139450/is-obscuring-obfuscating-public-facing-database-ids-really-a-best-practice https://softwareengineering.stackexchange.com/questions/1394... https://softwareengineering.stackexchange.com/questions/346971/should-backend-ids-be-public-or-not-on-a-rest-api https://softwareengineering.stackexchange.com/questions/3469...

AYBABTME 8y ago

the Go oklog/ulid package now supports that

ngrilly 8y ago
Supports what?

Dylan16807 8y ago

> Also a minor gripe - I wish that the ULID spec checked for microsecond collisions instead of millisecond, because that would be more useful for realtime networked gaming and simulations. If you can manage the difficult task of getting your clocks synced that precisely, it's probably easy to shift two characters over from random to timestamp.

mehrdadn 8y ago
> If you can manage the difficult task of getting your clocks synced that precisely It's only a matter of time (in both senses I guess). See e.g. https://blogs.technet.microsoft.com/networking/2018/07/18/top10-ws2019-hatime/ https://blogs.technet.microsoft.com/networking/2018/07/18/to...

nixpulvis 8y ago

At a certain point you'll end up wanting fancy clocks too. I believe this is what Google does with Spanner.

joatmon-snoo 8y ago

> Lexicographically sortable identifiers are critical for any distributed data store if you want anything close to consistency. wat? This doesn't make any sense to me. Requiring that events be partially ordered if not totally ordered is a consistency requirement, sure, but I'm failing to understand how a database's consistency depends on the data you're putting in the database.

cryptonector 8y ago
And now you need every host to have an atomic clock too. Maybe CRDTs would be better.
- edoceo 8y ago
  I use ULID in a distributed system where some clocks are off by a bit, still works well, untill the skew is way off. The time can be extracted from the ULID for verification before INSERT.
  - riffraff 8y ago
    Won't removing time bizs increase the chance of collisions? UUIDs rely on a lot of randomness to avoid the issue, but in ULID this is much more limited, and the timestamp fills in for some of it, afaiu
    - edoceo 8y ago
      We don't remove the time bits, we inspect them for reasonable values. Eg: never ever older than 2014-01-01 and older than 24h from our clock gets extra logging+meta-data.
advisedwang 8y ago
I think they're talking about data locality. If a single processing step access data that are "neighbours", in some systems that data is likely served from a single server. This means a) better performance and b) higher likelihood of consistency. Of course the guarantee is still merely eventual consistency, but data locality does reduce the chance this becomes visible.

wyldfire 8y ago

> I wish that the ULID spec checked for microsecond collisions instead of millisecond Most computers don't have wall clocks with even more millisecond precision, much less microsecond. The wall clocks are generally OS tick precision (~5-10ms ballpark) with poorer still accuracy. Seems like the use case is one that is niche. Maybe an extension?

antonvs 8y ago

> How this wasn't considered database 101 decades ago just blows my mind. Decades ago they didn't have distributed data stores.

vladsanchez 8y ago
What is a database then? They've existed for close to 40 years now.
- dragonwriter 8y ago
  Until recently (and even recently, for the most part) databases have been, almost entirely, centralized (though often shared) stores, not distributed stores.

jayd16 8y ago

Did anyone else find it ironically irritating that firebase example json was an unordered dictionary instead of a properly ordered list?

InGodsName 8y ago

Not just that, you can use range queries like this: https://redis.io/commands/zrangebylex https://redis.io/commands/zrangebylex To find events between two specific points. It can also be used in Dynamodb which is what we use in adtech.