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

61–70 of 291 posts

Re: Nanosecond timestamp collisions are common

#61

Post by mlichvar »

mgaunard wrote: post #27
zokier wrote: post #16

I guess I'm old, the macOS behaviour is more in line with my expectations. But this got me thinking, how feasible it would be to tie the various clock systems of a computer to some reference clock, like 10 MHz GPSDO? Obviously it wouldn't improve the granularity, but you could ensure that the timestamps are actually accurate. Because otherwise I doubt that random computer clock would be accurate down to 32ns even wit…

Getting a 10MHz PPS signal requires specialized expensive hardware and typically doesn't scale well to cover every server. That sort of thing is best left to extreme applications with FPGAs or ASICs. In particular the 10MHz version; a lot of commodity hardware only supports the 1Hz one. There's still an in-between of PPS and NTP: PTP.

A major problem in synchronization of the system clock is PCIe. Hardware can timestamp PPS signal or PTP/NTP packets with accuracy of a few nanoseconds if everything is well compensated, but the PCIe bus between the CPU and the timestamping HW has a latency of hundreds of nanoseconds with potentially large asymmetry, degrading the accuracy significantly.

Measuring that error is difficult. A possibility is to run a program periodically making random reads from memory (avoiding the CPU cache) to generate a PPS signal on the memory bus, which can be observed with a scope. There is a lot of noise due to other memory activity, RAM refresh, etc. From the configured memory speed and tRCD+tCL timings the uncertainty of the error can be reduced.

This might improve with new hardware. There is a feature called Precision Time Measurement (PTM), which is a hardware implementation of an NTP-like protocol in PCIe, but so far I have seen this working only on some onboard NICs.

Re: Nanosecond timestamp collisions are common

#62

Post by jstanley »

iforgotpassword wrote: post #59
newaccount74 wrote: post #50

Earlier quoted context omitted.

Doesn't that just add a whole lot of unnecessary complexity? If elements have multiple IDs, one of which should not be leaked to the outside, that's just asking for trouble in my opinion. Is generating UUIDv4 or UUIDv7 really too much effort? I'd assume that writing the row to the database takes longer than generating the UUID.

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.

Re: Nanosecond timestamp collisions are common

#63

Post by fer »

grose wrote: post #12

This is why it scares me a bit to use a raw timestamp as a sort key in DynamoDB. I append a (random) unique ID to the timestamp text to avoid it. Better safe than sorry, I figure.

I have a use case that uses a similar solution, but for a different reason: it doesn't scare me to use timestamp as sort key I since I know my hash keys are unique and I only write every few seconds. But I still add random amount of ms (well under the frequency of writes/updates), because otherwise I'll be hitting hot partition issues on the GSI (indexed by timestamp, as you can guess).

Re: Nanosecond timestamp collisions are common

#64

Post by mcv »

madsbuch wrote: post #58
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.

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

But shouldn't that be a separate field then?

Re: Nanosecond timestamp collisions are common

#66

Post by mattashii »

mcv wrote: post #64
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.

But shouldn't that be a separate field then?

The logistics of combining fields in indexes and identifiers is relatively complex, while the logistics of indexing a single field is comparatively trivial. This is also why you don't ship timestamps using separate fields for second/minute/hour/day/month/year, but a single ISO-string or UNIX timestamp as representation: it makes querying and interpreting the value more consistent.

Re: Nanosecond timestamp collisions are common

#67

Post by madsbuch »

mcv wrote: post #64
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.

But shouldn't that be a separate field then?

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?

Re: Nanosecond timestamp collisions are common

#68

Post by littlestymaar »

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

I'd love to see the math for the probability of the second option.

Re: Nanosecond timestamp collisions are common

#69

Post by junon »

madsbuch wrote: post #67
mcv wrote: post #64

Earlier quoted context omitted.

But shouldn't that be a separate field then?

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?

There are many DBMSes that combine columns into a singular primary key. Performance tradeoffs vary, especially when it comes to indexing.

Re: Nanosecond timestamp collisions are common

#70

Post by junon »

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…

Don't even need the "same millisecond" part to save a few cycles, use case depending. An overflowing increment with a counter of any sort plus a few random bits is usually enough.

If you're clever enough, neither needs a branch.

Post reply on HN