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

191–200 of 291 posts

Re: Nanosecond timestamp collisions are common

#191

Post by datenwolf »

vient wrote: post #172
datenwolf wrote: post #151

Earlier quoted context omitted.

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

> RDTSC is directly influenced by frequency scaling Unfortunate wording, RDTSC itself is not influenced by frequency scaling, it has constant frequency on modern CPUs after all. Your video nicely shows that RDTSC delta is influenced by CPU frequency, as expected, but how does it affect using RDTSC as a clock? On my CPU RDTSC seems to tick at 3GHz, for example. I wonder how precise it is though, how much its frequency…

I did update my program, now it measures the ratio.

Re: Nanosecond timestamp collisions are common

#192

Post by amelius »

datenwolf wrote: post #190
marcosdumay wrote: post #185

Earlier quoted context omitted.

> it also creates entropy It's a nitpick, but it concentrates the entropy. It doesn't create any. I do think it will make the answer more clear, as the hash concentrates the less than 64 bits of entropy on that 128 bits of original data into a usable 64 bits package.

Actually hashes do create entropy (every computation creates entropy in some form or another). What's the entropy of a 4 bit number? What's the entropy of a 4 bit number hashed by a 64 bit hash function? The act of computation does in fact create entropy, as per the 2nd law of thermodynamics, a part of which shows up in the hash.

> every computation creates entropy in some form or another

Ok, what is the entropy created by this function that maps a 4-bit number to a 64 bit number:

    0 -> 0
    1 -> 1
    2 -> 1
    3 -> 1
    4 -> 1
    ...
    15 -> 1

Re: Nanosecond timestamp collisions are common

#193

Post by kprotty »

lazide wrote: post #158
blibble wrote: post #145

Earlier quoted context omitted.

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

Invariant (Constant) TSC is detectable via `cpuid` and applies to `rdtsc/rdtscp` by default. In that aspect, there's no tradeoff being made there (observable to software) AFAICK.

Re: Nanosecond timestamp collisions are common

#194

Post by sfink »

zamadatix wrote: post #177
datenwolf wrote: post #159

Earlier quoted context omitted.

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

The hash, in this case, is just one deterministic way to shorten the CPU counter to few bits which can then be used to increase the entropy of the timestamp by replacing the timestamps stale bits. What's being asked here is not why use some compressed bits of the CPU counter increases the entropy of the timestamp overall. Rather, why you'd use a hash of the entropy providing information to do this since hashes allow…

Yeah, when I was thinking about the hash, I thought of it as stuffing to fill the unused portion of the number that would look better than using zeroes.

TIMESTAMP010111101010101TSC "looks better" than TIMESTAMP000000000000000TSC even though they contain the same information.

I would drop the hash, it's deceptive.

I don't believe it breaks the monotonicity, though? I mean, it would if it weren't already broken. If you're taking the low 16 bits of the TSC, then a rollover in those 16 bits during the same timestamp will already go backwards. TIMESTAMP0...0 follows TIMESTAMPf...f.

Re: Nanosecond timestamp collisions are common

#195

Post by lazide »

kprotty wrote: post #193
lazide wrote: post #158

Earlier quoted context omitted.

None of these are performant, no? Generally, you can have consistency, speed, or low cost - but not more than two at the same time.

Invariant (Constant) TSC is detectable via `cpuid` and applies to `rdtsc/rdtscp` by default. In that aspect, there's no tradeoff being made there (observable to software) AFAICK.

interesting results! i guess it depends in if you consider 35ish cycles expensive or not.

[https://community.intel.com/t5/Software-Tuning-Performance/H...]

Re: Nanosecond timestamp collisions are common

#196

Post by datenwolf »

amelius wrote: post #192
datenwolf wrote: post #190

Earlier quoted context omitted.

Actually hashes do create entropy (every computation creates entropy in some form or another). What's the entropy of a 4 bit number? What's the entropy of a 4 bit number hashed by a 64 bit hash function? The act of computation does in fact create entropy, as per the 2nd law of thermodynamics, a part of which shows up in the hash.

> every computation creates entropy in some form or another Ok, what is the entropy created by this function that maps a 4-bit number to a 64 bit number: 0 -> 0 1 -> 1 2 -> 1 3 -> 1 4 -> 1 ... 15 -> 1

60 bits. Yes, I know, you can compress it down very well. But consider that entropy in computation involves not just the bits you store, but also the bits that the processor touches and eventually dissipates as heat into the universe.

Re: Nanosecond timestamp collisions are common

#197

Post by datenwolf »

dheera wrote: post #188
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)

Why? low bits + CPU cycle counter is enough. No need of the hash()

You don't know precisely at which frequency the cycle counter runs. Depending on the system load it might either run faster or slower than the lowest bits the HPTC. For what it's worth this part is more or less nondeterministic, so the sane thing to do, is spread out the information as much as possible (maximize entropy), in order to minimize the probability of collisions.

Re: Nanosecond timestamp collisions are common

#198

Post by iforgotpassword »

wongarsu wrote: post #157
jstanley wrote: post #153

Earlier quoted context omitted.

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.

I might be misremembering, but didn't YouTube do this in the early days? So yeah, that was what I was thinking of when replying, not a traditional hash function.

Re: Nanosecond timestamp collisions are common

#199

Post by dan-robertson »

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 don’t think this is right. I am pretty doubtful of the discussion of the granularity of the results of clock_gettime, but I failed to find any sources and I don’t have a suitable computer to hand to experiment.

But here are two more doubts:

1. On at least some systems, clock_gettime will be implemented by a vdso call that (on x86) uses rdtsc to give you the time, so you should expect its results to be pretty highly correlated with an rdtsc immediately afterwards, so you aren’t really adding useful entropy (whereas you are losing time-locality of your identifiers which may be desirable if they are to end up as primary keys somewhere)

2. On some systems (eg some AMD processors), rdtsc gave me pretty low precision results (eg rounding to the nearest 10 cycles) so you also won’t necessarily get the entropy you would expect from the description of the instruction. I failed to find a reference for this too apart from an offhand mention in a paper about timing attacks.

Re: Nanosecond timestamp collisions are common

#200

Post by pxx »

datenwolf wrote: post #190
marcosdumay wrote: post #185

Earlier quoted context omitted.

> it also creates entropy It's a nitpick, but it concentrates the entropy. It doesn't create any. I do think it will make the answer more clear, as the hash concentrates the less than 64 bits of entropy on that 128 bits of original data into a usable 64 bits package.

Actually hashes do create entropy (every computation creates entropy in some form or another). What's the entropy of a 4 bit number? What's the entropy of a 4 bit number hashed by a 64 bit hash function? The act of computation does in fact create entropy, as per the 2nd law of thermodynamics, a part of which shows up in the hash.

I don't think you understand what this conversation is about. We are considering information theoretic entropy, not thermodynamic entropy from the mechanism of computation itself.

The result of applying a deterministic function on a random variable cannot have more entropy than the underlying random variable. This is a theorem, one that is trivial enough to not have a name. But you can find solution sets to homework that will prove it for you: https://my.ece.utah.edu/~rchen/courses/homework1_sol_rr.pdf

Post reply on HN