Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nanosecond timestamp collisions are common

evanjones.ca

Post reply on HN
Print view View original

101–110 of 291 posts

Re: Nanosecond timestamp collisions are common

#101

Post by bArray »

> I was wondering: how often do nanosecond timestamps collide on modern systems? The answer is: very often, like 5% of all samples, when reading the clock on all 4 physical cores at the same time.

A few things to consider:

1. This would depend a lot on how regularly you are checking, the more regular, the more collisions.

2. There may also be some weirdness where threads doing similar tasks will synchronise or desynchronise to maximize throughput.

3. Your system may not offer accurate nanosecond time. For this reason some OSes tend not to offer lower than microsecond time, as the clocks simply cannot offer higher usable accuracy. You're also measuring the time to call the function(s), create the timestamp, etc.

A simple solution I had years ago was to add random precision to reduce collisions. That breaks most tie situations. If you have 5% ties in nano seconds, with random pico second accuracy your collisions are down to 0.005%. You could also seed the random offset by an ID.

Re: Nanosecond timestamp collisions are common

#102

Post by willis936 »

qwerty456127 wrote: post #86
eru wrote: post #48

Earlier quoted context omitted.

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

> Why do you need the time component anyway? To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are cases when this is not convenient to do. E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.

One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.

Re: Nanosecond timestamp collisions are common

#103

Post by EGreg »

Cthulhu_ wrote: post #40
Mikhail_Edoshin wrote: post #35

Earlier quoted context omitted.

Isn’t it simpler to use sequence keys then?

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

Re: Nanosecond timestamp collisions are common

#104

Post by LeoNatan25 »

vbezhenar wrote: post #3

If you need unique nanosecond, keep track of the previously generated one and increase it if necessary. Would require global lock or atomic stuff, but should be good enough for practical uses.

If there are collisions seen, that means there would be lock contention at this critical section, thus not a “good enough” solution.

Re: Nanosecond timestamp collisions are common

#105

Post by lyu07282 »

enyone wrote: post #24
p-e-w wrote: post #21

If you want unique identifiers, use version 4 (random) UUIDs. Problem solved. The probability of a collision is roughly the same as the probability of a fully grown dinosaur spontaneously manifesting in your bedroom due to quantum fluctuations.

the dinosaur is now on my bed, what next?

I would just call Randall Munroe, he will know what to do

Re: Nanosecond timestamp collisions are common

#106

Post by aljarry »

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…

What's wrong with using UUIDs for things that are commonly used every nanosecond? It's still improbable to get 2 UUIDs for identifier for the same "thing" in the system, even if you generate billions of them per second. It's a pretty good way to get non-colliding IDs without a central registry. That's the main feature.

I've never seen duplicated UUID generated, and if that's the issue, you may think about using cryptographic randomness source to generate it.

UUID v7 has millisecond precision + 72 bits of randomness, which is _a lot_.

Also, central registry for IDs seems like a great way to shoot yourself in a foot, in case it's down, your network is down, you're on cellular connection, on a plane...

Re: Nanosecond timestamp collisions are common

#107

Post by zokier »

ajb wrote: post #73
godelski wrote: post #60

Despite the resolution being nanoseconds, what is the actual precision of computer clocks? I can't imagine it is actually nanoseconds. Takes me back to teaching physics labs where I had to hound students to remember that the accuracy of their measuring device is not identical to the smallest number it displays...

For devices clocked above 1Ghz it's perfectly possible for the clock to increment every ns, although that doesn't make it accurate to that level, and multi core systems may have clocks that are not synchronised to that level. ARMv8 guarantees that it's clock increments at at least 1Ghz, for intel and earlier ARM it's more complicated

Cycle counting is one thing, but it gets tricky when you have frequency scaling in play. Another problem that even without freq scaling, cpu clocks are not designed to be super accurate/exact, and the true frequency might vary significantly even if the nominal freq is fixed

Re: Nanosecond timestamp collisions are common

#108

Post by victor106 »

EGreg wrote: post #97
danbruc wrote: post #91

Earlier quoted context omitted.

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything

That sounds too good to be true. Is that really true of all grapdb’s?

Also, if that’s really true why can’t everyone just use graphdb’s?

Re: Nanosecond timestamp collisions are common

#109

Post by e12e »

EGreg wrote: post #97
danbruc wrote: post #91

Earlier quoted context omitted.

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything

How big is the 1 though?

Re: Nanosecond timestamp collisions are common

#110

Post by sgarland »

danbruc wrote: post #91
qwerty456127 wrote: post #86

Earlier quoted context omitted.

> Why do you need the time component anyway? To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are cases when this is not convenient to do. E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

Page splits… page splits everywhere.
Post reply on HN