Nanosecond timestamp collisions are common • Hacker News Board

Re: Nanosecond timestamp collisions are common

#121

Post by newaccount74 » Fri, Jul 21, 2023, 12:21 PM UTC

3cats-in-a-coat wrote: post #22

LAC-Tech wrote: post #18

A lot of mention of UUDv7 in this thread which is good. But I also wonder what the collision rate for Ulids are.

I frankly don't understand how it's good. UUID originally was intended as something you use very sparingly, to name, say, a product SKU maybe, an organization, something like that. Not literally content that collides commonly at the same nanosecond, in the same application, in the same platform/org. At some point we have to question the sanity of using one single flat address space for everything from the tiniest ide…

The problem with hierarchic identifiers is that you need to be extremely dilligent when assigning them, and you make it extremely hard to refactor something in the future. But refactoring is something that happens all the time.

For example, you might have "comments" and "posts", and later merge the two entities and call them "notes". Now you have to figure out a way to merge the identifiers -- with UUIDs you don't have issues like this, because they are universally unique.

A lot of developers have found that UUIDv7 provides the properties they want (unique identifiers which sort by creation time), and they don't come with the hassle that other approaches come with.

Re: Nanosecond timestamp collisions are common

#122

Post by TRiG_Ireland » Fri, Jul 21, 2023, 12:24 PM UTC

e12e wrote: post #112

madsbuch wrote: post #67

Earlier quoted context omitted.

I am curios about this, and might be misunderstanding what you mean. Can you layout a demo architecture where you use multiple keys like you propose?

Any pure relational database design will eschew surrogate keys - most real-world systems will (should) add them back - because a surprising number of good natural keys end up changing (names change, phone numbers change, emails change, twitter handles become irrelevant/disappear, location of birth may change subject to geographic regions changing size...). And on top of all that, there are efficiency concerns. That s…

> location of birth may change

My British passport says I was born in Birr; my Irish passport says I was born in Galway. These are both correct, because they are answering different questions. (I was born in the town of Ballinasloe in County Galway, but my mother's place of residence at the time of my birth was the town of Birr in County Offaly.)

Re: Nanosecond timestamp collisions are common

#123

Post by ericHosick » Fri, Jul 21, 2023, 12:40 PM UTC

eru wrote: post #48

wood_spirit wrote: post #5

This is why you should use ids that combine both a time component and a sequence. Eg UUIDv7 has a milliseconds time component and then a field that increments for each event in the same millisecond, and then enough random bits to make collisions between ids generated on different machines astronomically unlikely. Of course there are only so many bits so you might generate too many events in the same time slice so the…

Why do you need the time component anyway? It's just eating up bits in your UUID without contributing much entropy.

UUIDs can serve different purposes. As others have mentioned, database performance on inserts might trump the need for difficult to guess UUIDs.

In other cases, the UUID needs to be as random as possible.

It really depends on the use case.

Re: Nanosecond timestamp collisions are common

#124

Post by tharkun__ » Fri, Jul 21, 2023, 12:47 PM UTC

EGreg wrote: post #99

madsbuch wrote: post #58

Earlier quoted context omitted.

You need it to make database indices perform better. If you don't need that, but just need a random UUID, UUIDv4 is better.

I dont know why people use relational databases other than they were first and “that’s the way it’s always been done”. Why not use a graph database? O(1) lookups instead of O(N). Why need indices if you can just point to the data. Why use JOINs when map-reduce querying is far more flexible?

They were not first.

ISAM and VSAM come to mind. Yes it says "files" in there a lot but it got used like a database with programming interfaces like finding records in a database. If you will this method is more like NoSQL databases than a relational DB. The I in ISAM was a step towards not having to know the key (true "NoSQL"). Kind of like today's NoSQL databases all also give the ability to add indexes now.

https://en.m.wikipedia.org/wiki/ISAM

Re: Nanosecond timestamp collisions are common

#125

Post by EGreg » Fri, Jul 21, 2023, 12:50 PM UTC

ndriscoll wrote: post #120

EGreg wrote: post #114

Earlier quoted context omitted.

Look, if you have N items related to X, at insert time, you store them in an array and have X point to that array, instead of foreign keys. For example, when a user has 7 articles. Do you want to just point to where the articles are stored? Or do you want to do O(log n) lookup for each article? And if you have many-to-many, do you want to join an Intermediate Table for even more processing, or just follow a pointer t…

How is that different from a clustered index?

A clustered index requires O(log N) lookups, since it's still an index.

I'm talking about pointing directly to the location of an array where things are stored. That array isn't a clustered index. Each array is different.

Re: Nanosecond timestamp collisions are common

#126

Post by sethammons » Fri, Jul 21, 2023, 1:01 PM UTC

getmeinrn wrote: post #4

I was going to post about "use a UUID", but I was surprised to learn that no UUID uses both timestamp + a random component. You can either get fully random with UUID4, or have a time + MAC based UUID with UUID1. Strange, I would have thought there would exist a UUID that uses time + random to minimize collisions like described in the post.

Ksuid may be what you want. Pretty much time sortable uuid.

Go implementation: https://github.com/segmentio/ksuid

Re: Nanosecond timestamp collisions are common

#127

Post by Timon3 » Fri, Jul 21, 2023, 1:12 PM UTC

EGreg wrote: post #103

Cthulhu_ wrote: post #40

Earlier quoted context omitted.

Yes, but only on single machines, UUID and co are intended for distributed systems. Although now I wonder if / how UUID v7 can do sequential keys on distributed systems. Mind you, on those systems "close enough" will probably be good enough, and sorting will be done by date instead of incremental ID.

So just prefix the node ID which is assigned when the node joins a swarm

How is that easier or better? Now you're letting your infrastructure details bleed into your database.

Re: Nanosecond timestamp collisions are common

#128

Post by datenwolf » Fri, Jul 21, 2023, 1:16 PM UTC

In other news: Water is wet.

The high resolution precision time counters are derived from the system base clock, usually operating at ~33MHz, which translates exactly into that 30ns granularity observed.

If you really want robust time derived timestamp identifiers, truncate the high resolution timer to at best 10µs resolution replace the low bits with the hash of them, concatenated with the value of the CPU cycle counter (`RDTSC` on x86).

Re: Nanosecond timestamp collisions are common

#129

Post by tjoff » Fri, Jul 21, 2023, 1:22 PM UTC

Thiez wrote: post #119

beefield wrote: post #95

Earlier quoted context omitted.

Knowing nothing about UUID v4 generation, I have likely a stupid question. What makes you so confident that all implementations and their entropy sources are flawless enough to make actual collision probability close enough to theory?

What makes us so confident that our database implements ACID correctly, the RAM stores bins correctly, and the disk drivers store the data correctly? In the end we have to make some assumptions about the correctness of (some of the) components.

We are not confident in any of that. Which is why we mitigate it with checksums, ECC etc.

So depending on the consequences you might opt to reduce the risk or help mitigate the consequences.

To just state that it is about as likely as my coffee maker being a portal to the future isn't very helpful. Poor entropy sources or bugs are not uncommon.

Re: Nanosecond timestamp collisions are common

#130

Post by wongarsu » Fri, Jul 21, 2023, 1:34 PM UTC

jstanley wrote: post #62

iforgotpassword wrote: post #59

Earlier quoted context omitted.

It also means once your hash function leaks for whatever reason or gets brute forced because of whatever weird weakness in your system, it's game over and everybody will forever be able to predict any future ids, guess neighboring ids, etc., unless you're willing to change the hash and invalidate all links to any content on your site. If I'm in a scenario where I think I need consecutive ids internally and random one…

You need 2 fields anyway, unless you want to have to brute force your hash function when you need to invert it.

Store just the sequential id, compute the hash on the edge.

This keeps your database simple and performant, and pushes complexity and work to the backend servers. This can be nice because developers are typically more at home at that layer, and scaling the backend can be a lot easier than scaling your database. But it also comes with the downsides listed in this thread.