Nanosecond timestamp collisions are common • Hacker News Board

Re: Nanosecond timestamp collisions are common

#151

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

usefulcat wrote: post #136

datenwolf wrote: post #128

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 cou…

I thought clock_gettime() usually does use rdtsc(p) on Linux? Possibly depending on the particular clock type (montonic, realtime, etc). Either way I'd be interested in knowing more.

RDTSC is directly influenced by frequency scaling. So while monotonic, its clock interval is neither constant, nor deterministic on modern systems.

Here's a small online visualization of RDTSC average and standard deviation I just hacked together: https://gist.github.com/datenwolf/151486f6d73c9b25ac701bdbde...

On a system with frequency scaling you can see that under higher load the difference between RDTSC in subsequent iterations of a tight loop that does nothing else than reading that register will drop. Here's how it looks on the system I'm currently using: https://www.youtube.com/watch?v=FKKjSJ1JZ78

Re: Nanosecond timestamp collisions are common

#152

Post by chaoticmass » Fri, Jul 21, 2023, 3:17 PM UTC

Reminds me of some Lotus Notes folklore. Apparently they used to use timestamps with a resolution of 1 second as unique IDs for things. When there was a collision, they would just add 1 second. Eventually, you'd end up with items being in the future because there would be so many collisions.

Re: Nanosecond timestamp collisions are common

#153

Post by jstanley » Fri, Jul 21, 2023, 3:17 PM UTC

wongarsu wrote: post #130

jstanley wrote: post #62

Earlier quoted context omitted.

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.

That's fine, but when a request comes in referencing only a hash and not an id (because you're not leaking ids to clients), how do you get the id?

Re: Nanosecond timestamp collisions are common

#154

Post by datenwolf » Fri, Jul 21, 2023, 3:18 PM UTC

jsolson wrote: post #141

datenwolf wrote: post #135

Earlier quoted context omitted.

Well, you can always attempt to catch the CPU cycle counter overflow (happens at roughly 10Hz on current machines), adding up the carries and add it to a nanosecond counter shifted up by a few bits. Problem with the CPU cycle counter is, that it's not in lockstep with the HPTC, due to dynamic frequency scaling. If you really, really, really need system wide, nanosecond precision timestamps, you'll have to resort to d…

Some of this is not current. Constant-rate TSCs are ~15-20 years old. Synchronized TSCs are at least ten. Also RDTSC produces a 64-bit result, so it does not overflow at a rate of several Hz.

It's 64 bit on 64 systems. In the world of hard realtime applications there's still a huge armada of systems out there in the field running on 32 bit (think motion control, CNC machines, industrial robotics). If you're developing software that's concerned with this kind of precision, you might find yourself confronted with such "outdated" systems more often, than not.

Also see https://news.ycombinator.com/item?id=36814762

Re: Nanosecond timestamp collisions are common

#155

Post by madsbuch » Fri, Jul 21, 2023, 3:23 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?

How do you do constant time lookup an graph databases?

My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)

Re: Nanosecond timestamp collisions are common

#156

Post by amelius » Fri, Jul 21, 2023, 3:23 PM UTC

jjk166 wrote: post #146

amelius wrote: post #143

Earlier quoted context omitted.

> replace the low bits with the hash of them Doesn't this hash-step only increase the probability of collisions? What is this step intended to solve?

> replace the low bits with the hash of them, concatenated with the value of the CPU cycle counter (`RDTSC` on x86) you're concatenating two values and then taking the hash of the combination, ie: hash(low bits + CPU cycle counter)

But a hash() destroys information.

When you are trying to reduce collisions, why would you use a function that is known to introduce collisions?

Re: Nanosecond timestamp collisions are common

#157

Post by wongarsu » Fri, Jul 21, 2023, 3:27 PM UTC

jstanley wrote: post #153

wongarsu wrote: post #130

Earlier quoted context omitted.

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.

That's fine, but when a request comes in referencing only a hash and not an id (because you're not leaking ids to clients), how do you get the id?

Good point. Back when we did that we just used a reversible hash function (some would call it encryption). There are some simple algorithms meant for encrypting single integers with a reasonable key.

Re: Nanosecond timestamp collisions are common

#158

Post by lazide » Fri, Jul 21, 2023, 3:28 PM UTC

blibble wrote: post #145

crote wrote: post #137

Earlier quoted context omitted.

Modern CPUs don't really give you accurate nanosecond-scale time stamps anyways. The CPU will randomly speed up or slow down, execute instructions out of order, and even speculatively execute instructions. Not to mention that it'll have a dozen different clocks - which are not guaranteed to be in sync.

> The CPU will randomly speed up or slow down constant_tsc has been a thing for more than a decade > execute instructions out of order, and even speculatively execute rdtscp serialises > Not to mention that it'll have a dozen different clocks - which are not guaranteed to be in sync. synchronised_tsc has been a think for about 6 years now

None of these are performant, no?

Generally, you can have consistency, speed, or low cost - but not more than two at the same time.

Re: Nanosecond timestamp collisions are common

#159

Post by datenwolf » Fri, Jul 21, 2023, 3:33 PM UTC

amelius wrote: post #156

jjk166 wrote: post #146

Earlier quoted context omitted.

> replace the low bits with the hash of them, concatenated with the value of the CPU cycle counter (`RDTSC` on x86) you're concatenating two values and then taking the hash of the combination, ie: hash(low bits + CPU cycle counter)

But a hash() destroys information. When you are trying to reduce collisions, why would you use a function that is known to introduce collisions?

Because the raw value from the timestamp will be very low entropy and have the short scale variation concentrated in just a few bits. A hash not just destroys information, it also creates entropy by mixing that information over all the bits that come out of it. And using 64 bit hash replacing a 64 bit nanosecond counter that has short term entropy of less than 16 bits, you're in fact reducing the likelihood of a collision by a factor of 2^48.

Re: Nanosecond timestamp collisions are common

#160

Post by hinkley » Fri, Jul 21, 2023, 3:35 PM UTC

I’ve met too many people who are surprised by millisecond or microsecond timestamp collisions.

My most memorable and least favorite variety of this is when people try to assemble a timestamp from two system calls, one for the most significant digits and a second for the least.

If the smallest digits roll over from 99x to 00x after you read the large digits, due to process preemption, you can create a time stamp for an entity that happens before the entity that caused it to exist. This breaks some code spectacularly (I’ve seen infinite loops at least twice).

If you haven’t memorized this as a thing to always avoid, you end up with tests that pass 99.5% of the time, and it can take someone with very good pattern matching skills to catch that the same test has been red once a week for a month and a half, which is a very long time for a logic bomb to live in CI/CD code before getting fixed.