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

281–290 of 291 posts

Re: Nanosecond timestamp collisions are common

#281

Post by eru »

qwerty456127 wrote: post #86
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.

> Why do you need the time component anyway? To sort or filter the records by time. Sure, you can just add an extra column if you need this, but there are cases when this is not convenient to do. E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.

> E.g. when you want to be able to export the records info files, naming the files with the IDs and still be able to sort them.

You could name them by (time, id)?

Re: Nanosecond timestamp collisions are common

#282

Post by eru »

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…

Just explicitly use (time, random uuid) as a key in your sorting, instead of sullying your uuid with time information?

Re: Nanosecond timestamp collisions are common

#283

Post by eru »

KMag wrote: post #134
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.

Otherwise, failure recovery requires robust storage. Upon startup, you just wait until your timestamp ticks over, and then you know you're not re-issuing any UUIDs. With a pure counter-based system, you need robust distributed storage and you need the machine to reserve batches of IDs via committing writes to the robust distributed storage. Otherwise, a disk failure may cause you re-issue UUIDs. Though, seeding a thr…

> With a pure counter-based system, you need robust distributed storage and you need the machine to reserve batches of IDs via committing writes to the robust distributed storage. Otherwise, a disk failure may cause you re-issue UUIDs.

Yes, a pure counter based system is probably worse than one that uses time. Don't use counters, especially not in a distributed setting.

Re: Nanosecond timestamp collisions are common

#284

Post by eru »

rvnx wrote: post #231
frankreyes wrote: post #89

Earlier quoted context omitted.

Create a new column with an MD5 hash of the other columns. Easy. /s

This is how it works, except it's not MD5 but a less-costly hash function

MD5 is a useless hash function these days.

It's not cryptographically secure (anymore). And there are cheaper non-cryptographically secure hash functions.

Re: Nanosecond timestamp collisions are common

#285

Post by eru »

EGreg wrote: post #99
madsbuch wrote: post #58

Earlier quoted context omitted.

You need it to make database indices perform better. If you don't need that, but just need a random UUID, UUIDv4 is better.

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?

You might want to read Codd's paper: https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf

Re: Nanosecond timestamp collisions are common

#286

Post by eru »

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.

PRNGs are cheap to compute, and 'random' enough.

Re: Nanosecond timestamp collisions are common

#287

Post by eru »

madsbuch wrote: post #155
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?

How do you do constant time lookup an graph databases? My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)

> My intuition let's me know that you can not get below O(n log n) (Lower limit for comparison based ordering)

That intuition should point at O(log n), shouldn't it?

In any case, it totally depends how your data is stored and how/what you want to look up.

If you already have some kind of id of your node in the graph you want to look up, you can get O(1) lookup and still call it a graph database. If you have to traverse the graph, then it depends on the structure of the graph and where your entry point is, etc.

I'm rather skeptical of graph databases. Whatever they can do, you can do with a relation database and datalog. (Think of datalog as SQL plus recursion, perhaps.) See https://en.wikipedia.org/wiki/Datalog

Re: Nanosecond timestamp collisions are common

#288

Post by wood_spirit »

Dylan16807 wrote: post #277
lazide wrote: post #276

Earlier quoted context omitted.

The point I'm making is all these shenanigans are completely unnecessary, don't really help, and make everything extremely hard to manage, reason about, and get performance from - all to try to force usage of a specific key format (UUID) in a situation which it is not designed for, and for which it is not suited. It's square peg, round hole. And folks working on Exabyte sized indexed datasets generally already get th…

"it allows easy/cheap write combining" is not "completely unnecessary". What the heck, at least be consistent. And it's not shenanigans! You could shard based on the first bytes of a key, or you could shard based on the last bytes of the key. Neither one should be harder. Neither one is shenanigans. > It's square peg, round hole. Going entirely random is an even worse peg.

Wow a long thread of back and forth and confusion :)

Fwiw I’m with Dylan on this one!

I have direct experience of absolutely humongous data processing using random bits for shard selection where each shard uses sorted storage and benefits from the sortability of the time bits so, with just the smallest buffering, all inserts are basically super fast appends.

This is super normal in my experience. And I can’t wait for the new UUID formats to land and get widely supported in libs to simplify discussions with event producers :)

Re: Nanosecond timestamp collisions are common

#289

Post by zamadatix »

datenwolf wrote: post #261
zamadatix wrote: post #249

Earlier quoted context omitted.

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 t…

Most hashes are really good but the point was why replace the perfectly unique information in the cycle counter + time stamp combo with "most likely nearly unique" in the first place. After all, if the former isn't unique then neither are the hashes anyways.

Hashes are EXTREMELY compressible, albeit known algorithms are extraordinarily slow. E.g. I can compress any SHA256 output to a matter of kilobytes, maybe less, by using the SHA256 algorithm as the compressor algorithm and iterating through seeds until I get a match. With true entropy you can't guarantee that for all inputs, regardless of how long you take.

Different types of "information" ate at play here with the different types of entropy as well. If I have a 16 bit hash function and feed it a 64 bit value 48 bits of computational information is lost (at minimum). What happens with the physical information you used to represent the computation after you get the information result is separate from what happens with the computational information.

Re: Nanosecond timestamp collisions are common

#290

Post by 15155 »

eru wrote: post #282
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…

Just explicitly use (time, random uuid) as a key in your sorting, instead of sullying your uuid with time information?

ULID schemes aren't just about big endian sorting advantages, they often better enable time-based sorting mechanisms.
Post reply on HN