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

261–270 of 291 posts

Re: Nanosecond timestamp collisions are common

#261

Post by datenwolf »

zamadatix wrote: post #249
datenwolf wrote: post #241

Earlier quoted context omitted.

Boltzmann. But it doesn't really matter, it's the same thing. Yes, I know that looking at a sequence of, say 1000 identical bits looks like it's got just 10 bits of entropy after simple RLE compression. But you must not forget the entropy that also generated in the computation itself, and subsequently dissipated into the universe.

It's not the same thing. If I define a function that always returns 1 then the Shannon entropy is extremely low regardless if the Boltzmann entropy of running it on a CPU is high. That the two measures can be different shows they cannot be the same thing. Related in concept, different in definition. In fact, you can even use the same formulas for calculating it - what differs is what your calculating it on.

> If I define a function that always returns 1…

then it's Kolmogorov complexity is also extremely low.

Look if you have a well enough hash function, it output should be near the Shannon limit and hardly compressible, and ideally contain as much entropy as it has bits. But you can feed in just a single bit or the entire knowledge of humanity, in the end you're going to get a fixed amount of bits, and entropy near of that, and if you throw any form of lossless compression at it, it will hardly compress.

But quantum mechanics tells us, that information cannot be destroyed. So when you feed it more bits, than it emits, then its mostly the entropy of the information you feed in, that you get out of the hash. But if you feed it just a single bit, the additional entropy comes from the computational process.

I know, this is now getting really philosophical, but here's something to ponder on: How would you implement a hash function for a reversible computing architecture?

Re: Nanosecond timestamp collisions are common

#262

Post by mattashii »

btilly wrote: post #227
mattashii wrote: post #66

Earlier quoted context omitted.

The logistics of combining fields in indexes and identifiers is relatively complex, while the logistics of indexing a single field is comparatively trivial. This is also why you don't ship timestamps using separate fields for second/minute/hour/day/month/year, but a single ISO-string or UNIX timestamp as representation: it makes querying and interpreting the value more consistent.

Disagree on "relatively complex". create index on $table ($field1, $field2); Seems pretty simple to me.

It is noy just the DDL of the primary table that needs to care about it, but also all foreign keys, DML, queries, APIs accessing the data, etc. Storing that UUIDv7 is likely going to be cheaper than pushing the cost of keeping a composite identity onto other components and systems that work with that data.

Re: Nanosecond timestamp collisions are common

#263

Post by wood_spirit »

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.

UUIDv7 was first proposed just a few years ago, but the rfc contains a good list of well known ULID systems that predate it.

Putting the timestamp in the high bits of random ids is a “trick” i learned from DBAs (that used to be a thing!) in the 90s. And often the drive was to improve DB insert performance as it was for the other uses of an ID you can order and reason about.)

Re: Nanosecond timestamp collisions are common

#264

Post by amelius »

notpushkin wrote: post #257
amelius wrote: post #144

Earlier quoted context omitted.

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

I don't see how sudden dinosaur appearance is a bad thing.

Perhaps it is made of anti-matter.

Re: Nanosecond timestamp collisions are common

#265

Post by throwawaymobule »

mcv wrote: post #65
dtech wrote: post #36

Earlier quoted context omitted.

Only v6 and v7, v8 is "whatever you want".

That's not much of a standard.

From my reading, it's standardized because it has a version number embedded, so it won't get confused with other uuids.

Probably a good idea to have somewhere to silo bespoke implementations. Just gotta hope they end up being unique.

Re: Nanosecond timestamp collisions are common

#266

Post by lazide »

Dylan16807 wrote: post #256
lazide wrote: post #253

Earlier quoted context omitted.

I never said anything about bit or key length at all? Let alone how much was random or not? Perhaps you’re confused?

Let's start over. People were talking about the value of time+random UUIDs versus all-random UUIDs, and how those behave. You said that sometimes the random behavior is preferable. In response to that, I was saying that even if you want to sort randomly at some particular step, you should use the time+random format, because other steps might not want to sort randomly. You should directly choose to use the random part…

UUIDv7 has a specific format that doesn’t support that.

For the case I’m describing, you can’t use it.

For situations you want write coalescing it’s fine though.

Not sure it we’re agreeing here?

Re: Nanosecond timestamp collisions are common

#267

Post by jfax »

This was realised in the development of imageboard software (futaba.php, later yotsuba.php that runs 4chan) in the naming images, which is a unix timestamp + random 3 digit number because just the timestamp often causes clashes.

Re: Nanosecond timestamp collisions are common

#268

Post by kprotty »

lazide wrote: post #195
kprotty wrote: post #193

Earlier quoted context omitted.

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

Are there cheaper ways of getting elapsed time with sub microsecond precision? Interested as I've only ever heard of rdtsc at the lowest level in userspace for x86.

Re: Nanosecond timestamp collisions are common

#269

Post by btilly »

mattashii wrote: post #262
btilly wrote: post #227

Earlier quoted context omitted.

Disagree on "relatively complex". create index on $table ($field1, $field2); Seems pretty simple to me.

It is noy just the DDL of the primary table that needs to care about it, but also all foreign keys, DML, queries, APIs accessing the data, etc. Storing that UUIDv7 is likely going to be cheaper than pushing the cost of keeping a composite identity onto other components and systems that work with that data.

Well, that depends on how you manage it. An ORM will find it trivial. Custom SQL, not always so much.

That said, PostgreSQL offers https://www.postgresql.org/docs/current/rowtypes.html which gives you the best of both worlds. A single field which contains 2 fields that can later be extracted. So everywhere you can write a single field for joins, etc. But then when you need it broken out...

Re: Nanosecond timestamp collisions are common

#270

Post by Dylan16807 »

lazide wrote: post #266
Dylan16807 wrote: post #256

Earlier quoted context omitted.

Let's start over. People were talking about the value of time+random UUIDs versus all-random UUIDs, and how those behave. You said that sometimes the random behavior is preferable. In response to that, I was saying that even if you want to sort randomly at some particular step, you should use the time+random format, because other steps might not want to sort randomly. You should directly choose to use the random part…

UUIDv7 has a specific format that doesn’t support that. For the case I’m describing, you can’t use it. For situations you want write coalescing it’s fine though. Not sure it we’re agreeing here?

What do you mean it doesn't support that?

There's some flexibility in how you fill in a UUIDv7, but let's go ahead and say that the ones we're worried about have the first 32 bits filled with timestamp and the last 32 bits filled with random.

If you want pure sort-by-time, then use it the normal way. If you want pure sort-by-random, then it's slightly awkward but you can prioritize the random part.

But the additional power is that you can shard by the last 32 bits, then sort by the first 32 bits within a shard. And you don't need weird workarounds like hashing the UUID.

You said "it’s easier to shard when writes occur randomly over the overall space. it’s easier to coalesce when writes all happen in a given place (head or tail)". But you can have both at the same time. You can have easy sharding and easy coalescing.

Post reply on HN