Nanosecond timestamp collisions are common • Hacker News Board

Re: Nanosecond timestamp collisions are common

#211

Post by fluoridation » Fri, Jul 21, 2023, 6:47 PM UTC

p-e-w wrote: post #31

jraph wrote: post #23

Earlier quoted context omitted.

I will take my chance :-) More seriously, If you can use them, good old increments are probably best. They are fast and cheap. Especially in a database. They can have privacy/security issues (you could guess things by the values of ids of stuff). UUIDs are better in those case or when you deal with a distributed system.

> They can have privacy/security issues (you could guess things by the values of ids of stuff). Push them through a secure hash function, and that problem is solved too (assuming you can keep the base counter private).

A block cipher is better, as it's guaranteed to not have collisions.

Re: Nanosecond timestamp collisions are common

#212

Post by hansvm » Fri, Jul 21, 2023, 6:51 PM UTC

hinkley wrote: post #210

hansvm wrote: post #204

Earlier quoted context omitted.

Why sqrt(n) and not log(n)? And that complexity theory already exists. Typical whiteboard engineering uses transdichotomous models to gloss over some polylogarithmic factors (as do much of the literature), but more accurate models exist. The difference isn't usually super relevant when comparing multiple solutions all using the same model of computation though since the extra terms don't tend to bump one complexity c…

Speed of light. Imagine a data center containing exabytes of data. How long does it take to access an arbitrary bit of that data? We use clusters because computers cannot contain an infinite amount of memory, storage, or CPUs, because of physics. You see this same thing play out at smaller scales but it's more obvious at the macro scale. More addresses take logn time to sort out, but time to access is measured in rad…

Oooh interesting, thank you. I totally misunderstood this as the "integers never need more than 64 bits, so hash tables are constant" argument.

Re: Nanosecond timestamp collisions are common

#213

Post by hinkley » Fri, Jul 21, 2023, 6:52 PM UTC

tredre3 wrote: post #168

hinkley wrote: post #163

Earlier quoted context omitted.

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

That's kinda what I figured. So you can see my confusion.

Re: Nanosecond timestamp collisions are common

#214

Post by amelius » Fri, Jul 21, 2023, 7:17 PM UTC

datenwolf wrote: post #196

amelius wrote: post #192

Earlier quoted context omitted.

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

What definition of entropy do you use?

(I'm using Shannon entropy.)

Re: Nanosecond timestamp collisions are common

#215

Post by _flux » Fri, Jul 21, 2023, 7:24 PM UTC

SV_BubbleTime wrote: post #176

michaelt wrote: post #44

Earlier quoted context omitted.

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.

Should you, though? BLE itself uses UUIDs, but the ones it uses are in a shortened format just because the BLE frames are small and the protocol is not too fast.

Granted I've even used JSON over GATT so maybe I should keep my mouth shut :).

Re: Nanosecond timestamp collisions are common

#216

Post by dtech » Fri, Jul 21, 2023, 7:27 PM UTC

willis936 wrote: post #209

preseinger wrote: post #202

Earlier quoted context omitted.

it's commonly totally sufficient for IDs to represent a rough sort order millisecond precision is great for a lot of use cases

I didn't say that it wasn't. Hell even ms is too precise for many use cases (usually where date is used instead). What I said was that it's useful to be able to select timestamp precision independently of UUID implementation. One size that fits all fits none best.

Lucky for you, they also define UUIDv8 as a free-for-all where you can do whatever you want, and nanosecond precision is one of the examples given in the RFC.

Re: Nanosecond timestamp collisions are common

#217

Post by SV_BubbleTime » Fri, Jul 21, 2023, 7:30 PM UTC

_flux wrote: post #215

SV_BubbleTime wrote: post #176

Earlier quoted context omitted.

FWIW… we’re using UUIDv7s over BLE.

Should you, though? BLE itself uses UUIDs, but the ones it uses are in a shortened format just because the BLE frames are small and the protocol is not too fast. Granted I've even used JSON over GATT so maybe I should keep my mouth shut :).

It’s for an auth use. And at least we’re using CBOR. But I get your point.

Re: Nanosecond timestamp collisions are common

#218

Post by maxekman » Fri, Jul 21, 2023, 7:34 PM UTC

There is some interesting content regarding this in the Timestamps and Sequencing section in this post about the Go execution tracer overhaul: https://go.googlesource.com/proposal/+/ac09a140c3d26f8bb62cb...

Re: Nanosecond timestamp collisions are common

#219

Post by yohannesk » Fri, Jul 21, 2023, 7:37 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.

Were they not happy due to possible collisions or something else?

Re: Nanosecond timestamp collisions are common

#220

Post by dtech » Fri, Jul 21, 2023, 7:37 PM UTC

madsbuch wrote: post #82

dtech wrote: post #77

Earlier quoted context omitted.

I feel like v7 is almost a strictly better v4. Assuming you can generate a v7 (you have a time source), what are the disadvantages?

Entropy. You loose bits to a known source, which reduce entropy of the UUID.

I do feel 74 bits per second is enough though. That would require 2^(74/2) = 137 billion UUIDs generated in a single second for a 50% chance of a single collision.