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

141–150 of 291 posts

Re: Nanosecond timestamp collisions are common

#141

Post by jsolson »

datenwolf wrote: post #135
imglorp wrote: post #132

Earlier quoted context omitted.

Integrating a hash might improve (not guarantee) the uniqueness situation but not the monotonicity situation. Right?

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.

Re: Nanosecond timestamp collisions are common

#142

Post by EGreg »

dlisboa wrote: post #140
EGreg wrote: post #99

Earlier quoted context omitted.

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?

I've been interested in learning more about them and how to best utilize them in my company. What graph database and query language would you recommend (regardless of stack)?

1. Memgraph 2. Neo4j

As for query language: definitely Cypher!

Re: Nanosecond timestamp collisions are common

#143

Post by amelius »

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…

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

Re: Nanosecond timestamp collisions are common

#144

Post by amelius »

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.

But now the probability of bad things happening increased by about a factor of two, which is not acceptable.

Re: Nanosecond timestamp collisions are common

#145

Post by blibble »

crote wrote: post #137
byteknight wrote: post #131

Earlier quoted context omitted.

Wouldn't those operations reduce the accuracy of the time stamp?

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

Re: Nanosecond timestamp collisions are common

#146

Post by jjk166 »

amelius wrote: post #143
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…

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

Re: Nanosecond timestamp collisions are common

#147

Post by rdtsc »

Erlang/Elixir (BEAM VM) makes this very clear - it's a distinction between monotonic vs strictly monotonic.

https://www.erlang.org/doc/apps/erts/time_correction.html#mo...

> In a monotonically increasing sequence of values, all values that have a predecessor are either larger than or equal to its predecessor.

These are available via the https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 function.

https://www.erlang.org/doc/apps/erts/time_correction.html#st...

> In a strictly monotonically increasing sequence of values, all values that have a predecessor are larger than its predecessor.

Strictly monotonic values imply some synchronization / coordination, with an associated performance impact when there are many concurrent processes. This functionality is available via the https://www.erlang.org/doc/man/erlang.html#unique_integer-1 function. With a warning associated with it:

> Strictly monotonically increasing values are inherently quite expensive to generate and scales poorly. This is because the values need to be synchronized between CPU cores. That is, do not pass the monotonic modifier unless you really need strictly monotonically increasing values.

Re: Nanosecond timestamp collisions are common

#148

Post by Timon3 »

EGreg wrote: post #138
Timon3 wrote: post #127

Earlier quoted context omitted.

How is that easier or better? Now you're letting your infrastructure details bleed into your database.

They should bleed into your database. The database is part of your infrastructure and it contains details like where to find the replicas and so on

Why? Tight coupling doesn't make things easier.

Re: Nanosecond timestamp collisions are common

#149

Post by BiteCode_dev »

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…

Or UUID7

Re: Nanosecond timestamp collisions are common

#150

Post by derefr »

rdtsc wrote: post #147

Erlang/Elixir (BEAM VM) makes this very clear - it's a distinction between monotonic vs strictly monotonic. https://www.erlang.org/doc/apps/erts/time_correction.html#mo... > In a monotonically increasing sequence of values, all values that have a predecessor are either larger than or equal to its predecessor. These are available via the https://www.erlang.org/doc/man/erlang.html#monotonic_time-0 function. https://www…

Relatedly, Erlang's own refs aren't created by a strictly-monotonic global generator; but rather are internally a pair of a regular monotonic identifier, and the PID of the requesting process. In other words, they're akin to UUIDv1s, or to https://en.wikipedia.org/wiki/Snowflake_ID s.

You only really need strictly monotonic global identifiers if you need immediately-consistent first/last-write-wins. If you can instead rely on eventually-consistent first/last-write-wins (i.e. if your write events enter an event store/queue that linearizes them by ID, and then all "simultaneous" writes but the one with highest ID priority can be dropped/ignored, either during processing, or on read), then I'd recommend first considering packed (nodeID, seq) pairs. And, if you want global event orderibility, considering the snowflake ID formulation (timestampMajor, nodeID, timestampMinor, seq) specifically.

Post reply on HN