Hacker News Reader

Comment by zackmorris | Hacker News Reader

See also Firebase push IDs:

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.

View on HN

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

And now you need every host to have an atomic clock too.

Maybe CRDTs would be better.

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.

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

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.

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.

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

> 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/to...

> How this wasn't considered database 101 decades ago just blows my mind.

Decades ago they didn't have distributed data stores.

What is a database then? They've existed for close to 40 years now.

Until recently (and even recently, for the most part) databases have been, almost entirely, centralized (though often shared) stores, not distributed stores.

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

the Go oklog/ulid package now supports that

Supports what?

> 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?

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

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/3714...

https://stackoverflow.com/questions/15360245/when-using-uuid...

https://softwareengineering.stackexchange.com/questions/1394...

https://softwareengineering.stackexchange.com/questions/3469...

I'm pretty sure Google's Spanner uses something like Paxos, but you should fact check that, it might just be for replication.

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

Not just that, you can use range queries like this: 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.

Reply on news.ycombinator.com