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

171–180 of 291 posts

Re: Nanosecond timestamp collisions are common

#171

Post by ndriscoll »

EGreg wrote: post #125
ndriscoll wrote: post #120

Earlier quoted context omitted.

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.

What about when you delete rows? Do you just leave the space unused now? Or if you update a row to be larger? Rewrite the whole array (so possibly O(n) updates)?

How do you deal with data that gets accessed in different orders based on relationships from multiple other entities? Duplicate the data? If so, updates now get amplified and you can fit less data in RAM so you're more likely to require disk IO. If not, you need a layer of indirection (so you have an array of pointers instead of an array of data).

Even with a layer of indirection, updates that grow a row and require a reallocation will cause you to have to go update all pointers (also, those pointers need to be indexed to find who you need to update). To avoid write amplification, you can use an array of ids instead of an array of pointers. Now you want an id pointer lookup, which could be done with a hash map in O(1), or with a tree in O(logN) if you want to also allow efficient range queries.

I'm not exactly sure on the implementation details, but for ballpark numbers, for an 8 kB page size with 80% fill factor and 16 B entries (8 B key + 8 B pointer), with 10E9 rows, log(N) ought to be ~4 (page IOs). Not ideal, but the point is for a lot of real-world engineering, O(logN) is effectively O(1) (with a small enough constant factor that it's fine for general use).

So if your data is not write-once, trees are a well-rounded default data structure.

Re: Nanosecond timestamp collisions are common

#172

Post by vient »

datenwolf wrote: post #151
usefulcat wrote: post #136

Earlier quoted context omitted.

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 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 can drift from spec.

Re: Nanosecond timestamp collisions are common

#173

Post by SV_BubbleTime »

glodalitazic wrote: post #80
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.

Iirc you dont want to spend entropy that you don't need. The advantage of using the time means you need to spend less bits on expensive randomness and thus generation is cheaper.

I only work in embedded, so I’m not sure about fancy computers - but when we make UUIDv7s, I am certain the random is faster than pulling the time, formatting for milliseconds, then storing in position.

Re: Nanosecond timestamp collisions are common

#174

Post by SV_BubbleTime »

qwerty456127 wrote: post #87
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…

The problem with UUIDs is they are completely unreadable. Not just you can't understand them, it is prohibitively hard to even distinguish between them visually. This is why identifiers which would not include any bit of information (or noise) beyond the necessary minimum are useful in some cases.

Thus UUIDv7.

Re: Nanosecond timestamp collisions are common

#175

Post by SV_BubbleTime »

junon wrote: post #70
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.

UUIDv7 has two at least two such monotonic strategies. You can use a counter, or you can use those bytes to increase the random entropy.

Re: Nanosecond timestamp collisions are common

#176

Post by SV_BubbleTime »

michaelt wrote: post #44
Mikhail_Edoshin wrote: post #35

Earlier quoted context omitted.

Isn’t it simpler to use sequence keys then?

Ah but you see, UUIDs are web scale. And by web scale, I mean they're too big to exchange by any offline channel.

FWIW… we’re using UUIDv7s over BLE.

Re: Nanosecond timestamp collisions are common

#177

Post by zamadatix »

datenwolf wrote: post #159
amelius wrote: post #156

Earlier quoted context omitted.

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 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 for many:1 mappings (i.e. allow for decreases in entropy) while never providing better than 1:1 mappings (i.e. preserving entropy). At best, the hash is preserving the entropy of the timestamp and counter bits and, at worst, it is throwing some away. The question that follows: is there a better way that preserves the entropy of the inputs without the risk of throwing some away and, if so, was there some other reason to still use the hash? This is what I took amelius to be asking.

Knowing the timestamp delta is ~30ns then even a 1 THz processor would only execute 30,000 cycles before said timestamp increases and the outcome stays unique anyways. From that perspective, taking the low 16 bits of the cycle counter is already guaranteed to help produce perfectly unique timestamps, and without the risk of introducing hash collisions. It's also significantly easier to compute and now monotonic* now, whereas hashes were neither. From that perspective, I too don't see what value the hash is supposed to add to the information being fed to it in this case.

In threaded/distributed/parallel scenarios you may wish to throw the lane/core/node number in the bits as well. In the case having the same timestamp is supposed to be invalid this leaves you a simple deterministic way to tiebreak the situation as part of the creation of the timestamp itself.

*A 10 GHz CPU running for a little over 58 years could risk a 64 bit counter rollover in the middle of a time delta. If that's too close for comfort or you want the code to work on e.g. 32 bit counter systems, you'd need to eat more cycles and registers to set another bit to the outcome of whether current cycle count is < the one at the start of the current timestamp delta.

Re: Nanosecond timestamp collisions are common

#178

Post by nomel »

byteknight wrote: post #164
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.

This may be coming from a place of ignorance, but if that were the case, then time would drift significantly constantly due to Intel speed step for example. And if that were the source of truth for time, then when your computer is off, it wouldn’t be able to keep. I’m pretty sure they all have real time clock chips in the motherboards.

There's time keeping (which uses the real time clock) and high resolution clocks, which are good for relative timers. They're never the same components.

Re: Nanosecond timestamp collisions are common

#179

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…

Ah crud, you're right. What'd really be interesting to see is the ratio between d/dt rdtsc and d/dt clock_monotonic.

Re: Nanosecond timestamp collisions are common

#180

Post by dnstalk »

Comment out CLOCK_MONOTONIC_RAW because that's not available on FreeBSD, and it looks OK to me? My understanding is that we should see some timestamps repeating if there's a collision, correct? I can't get any collisions...

  > ./clock_gettime_demo/clock_gettime_demo
  clock_getres(CLOCK_REALTIME, ...)=1 ns
  clock_getres(CLOCK_MONOTONIC, ...)=1 ns

  CLOCK_REALTIME 30 samples:
  1689957434662039455
  1689957434662039526 (diff=71)
  1689957434662039566 (diff=40)
  1689957434662039606 (diff=40)
  1689957434662039636 (diff=30)
  1689957434662039676 (diff=40)
  1689957434662039706 (diff=30)
  1689957434662039736 (diff=30)
  1689957434662039766 (diff=30)
  1689957434662039796 (diff=30)
  1689957434662039826 (diff=30)
  1689957434662039856 (diff=30)
  1689957434662039886 (diff=30)
  1689957434662039916 (diff=30)
  1689957434662039946 (diff=30)
  1689957434662039987 (diff=41)
  1689957434662040016 (diff=29)
  1689957434662040047 (diff=31)
  1689957434662040076 (diff=29)
  1689957434662040107 (diff=31)
  1689957434662040137 (diff=30)
  1689957434662040167 (diff=30)
  1689957434662040197 (diff=30)
  1689957434662040227 (diff=30)
  1689957434662040257 (diff=30)
  1689957434662040297 (diff=40)
  1689957434662040327 (diff=30)
  1689957434662040357 (diff=30)
  1689957434662040387 (diff=30)
  1689957434662040417 (diff=30)

  CLOCK_MONOTONIC 30 samples:
  2168262770533974
  2168262770534023 (diff=49)
  2168262770534054 (diff=31)
  2168262770534094 (diff=40)
  2168262770534124 (diff=30)
  2168262770534164 (diff=40)
  2168262770534194 (diff=30)
  2168262770534224 (diff=30)
  2168262770534254 (diff=30)
  2168262770534284 (diff=30)
  2168262770534314 (diff=30)
  2168262770534344 (diff=30)
  2168262770534374 (diff=30)
  2168262770534404 (diff=30)
  2168262770534435 (diff=31)
  2168262770534464 (diff=29)
  2168262770534495 (diff=31)
  2168262770534524 (diff=29)
  2168262770534555 (diff=31)
  2168262770534585 (diff=30)
  2168262770534615 (diff=30)
  2168262770534645 (diff=30)
  2168262770534685 (diff=40)
  2168262770534715 (diff=30)
  2168262770534745 (diff=30)
  2168262770534775 (diff=30)
  2168262770534805 (diff=30)
  2168262770534835 (diff=30)
  2168262770534865 (diff=30)
  2168262770534895 (diff=30)
Post reply on HN