Nanosecond timestamp collisions are common • Hacker News Board

Re: Nanosecond timestamp collisions are common

#161

Post by moduspol » Fri, Jul 21, 2023, 3:41 PM UTC

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.

We ran into this, though we were using millisecond timestamps with the Number type.

Ended up working around it by adding numbers after the decimal point. DynamoDB apparently supports up to 38 digits of precision, and JavaScript (we're NodeJS based) by default encodes numbers to allow for up to 16 digits (combined, before and after the decimal point). A UNIX epoch millisecond timestamp is 13 digits, so we were able to use 3 just to add uniqueness without having to update anything else in our codebase.

We certainly now plan to essentially always use string-based (and generically named) partition and sort keys, which would allow us to more easily do what you're describing.

Re: Nanosecond timestamp collisions are common

#162

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

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…

The HRT patch set for Linux (which is eight years old) claims that Linux had a 10μs clock resolution before the patch, and conversations on SO suggest the resolution is now 1ns, so I believe this information is dated, or at least OS dependent.

Re: Nanosecond timestamp collisions are common

#163

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

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…

I’m feeling a bit like an accidental time traveler, because I can recall a conversation at a tech meetup that had to have been at least ten years ago where someone was struggling with unique UUIDs because they were bursting above 1000 UUIDs per millisecond and not happy with the available options.

How old is UUID7? I can’t get the internet to tell me.

Re: Nanosecond timestamp collisions are common

#164

Post by byteknight » Fri, Jul 21, 2023, 3:54 PM UTC

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.

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.

Re: Nanosecond timestamp collisions are common

#165

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

e12e wrote: post #109

EGreg wrote: post #97

Earlier quoted context omitted.

Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything

How big is the 1 though?

When you’re talking about data sets so large they dictate what hardware you use, and introduce terms like “cluster”, then 1 = √n

Which is why we need a version 2 of complexity theory, that doesn’t treat memory access or arithmetic on arbitrary precision numbers (aka as n actually goes to infinity) as O(1) operations. They aren’t. Which every large system engineer knows but few will talk about.

Re: Nanosecond timestamp collisions are common

#166

Post by EGreg » Fri, Jul 21, 2023, 3:59 PM UTC

Timon3 wrote: post #148

EGreg wrote: post #138

Earlier quoted context omitted.

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.

You’re complaining that the infrastructure details are bleeding into the intrastructure implementation?

Re: Nanosecond timestamp collisions are common

#167

Post by Timon3 » Fri, Jul 21, 2023, 4:02 PM UTC

EGreg wrote: post #166

Timon3 wrote: post #148

Earlier quoted context omitted.

Why? Tight coupling doesn't make things easier.

You’re complaining that the infrastructure details are bleeding into the intrastructure implementation?

Infrastructure details are bleeding into non-infrastructure implementation. Your database content is not an infrastructure implementation.

Re: Nanosecond timestamp collisions are common

#168

Post by tredre3 » Fri, Jul 21, 2023, 4:06 PM UTC

hinkley wrote: post #163

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…

I’m feeling a bit like an accidental time traveler, because I can recall a conversation at a tech meetup that had to have been at least ten years ago where someone was struggling with unique UUIDs because they were bursting above 1000 UUIDs per millisecond and not happy with the available options. How old is UUID7? I can’t get the internet to tell me.

UUID7 was first drafted a bit over a year ago: https://datatracker.ietf.org/doc/html/draft-peabody-dispatch...

Re: Nanosecond timestamp collisions are common

#169

Post by coding123 » Fri, Jul 21, 2023, 4:13 PM UTC

EGreg wrote: post #97

danbruc wrote: post #91

Earlier quoted context omitted.

More importantly if you have an index on purely random IDs, then each insert will go to some random position into the tree whereas having IDs that increase with time will make all new IDs end up at the end of the tree which reduces index fragmentation.

Or, you could use a graph database and stop having frustrating relational impedance mismatch, nonlocality etc. You can have O(1) lookups instead of O(log N) for almost everything

Graph databases don't solve that. All databases, document, graph, rel ALL implement indexes to find specific things in the exactly the same way. Very well known tree, hash and other techniques.

The representation (outside of indexing) has properties that make your USE CASE better or worse. EGreg would not be someone to hire to architect a solution. He'll just put your 1Trillion row per month use-case in a graph DB like Neo4J and you'll just watch it fall over when you run billing.

Re: Nanosecond timestamp collisions are common

#170

Post by SV_BubbleTime » Fri, Jul 21, 2023, 4:16 PM UTC

ericHosick wrote: post #123

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.

UUIDs can serve different purposes. As others have mentioned, database performance on inserts might trump the need for difficult to guess UUIDs. In other cases, the UUID needs to be as random as possible. It really depends on the use case.

Yea. This is an easy one. We use both.

For our “session” records, it’s a UUIDv7. This sorts beautifully, and if I wanted to, I could look at a log and easily see all the entries in a particular session.

For a larger db, we just need unique entries and at least in Dynamo, it is an advantage to equally distribute them as much as possible. UUIDv4 there.