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

251–260 of 291 posts

Re: Nanosecond timestamp collisions are common

#251

Post by Dylan16807 »

lazide wrote: post #250
Dylan16807 wrote: post #247

Earlier quoted context omitted.

Being random within each shard is still bad for write performance. Going fully random seems like a bad way to accomplish this goal. Why not keep the timestamp bits to use when appropriate, but use some of the random bits for shard selection?

Only when writing all at once and when you know what the shard boundaries are and the number of shards (and boundaries) are stable. If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically. Very large real world datasets are unlikely to be static long enough, and equipment stable enough, to not consider this eff…

> If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically.

I'm confused by your reply, because I never suggested not to use random bits for sharding.

I'm just saying that 60+ random bits should be enough to shard, change, grow, and sub-shard with. You don't need 122.

Re: Nanosecond timestamp collisions are common

#252

Post by hinkley »

danbruc wrote: post #242
hinkley wrote: post #223

Earlier quoted context omitted.

Integer arithmetic is really quantized logarithmic complexity. If your hardware has a bucket your number fits into, you're calculating n+1 or nxn in constant time. But if your data set doubles in size (especially for multiplication) you may find yourself in a bucket that doesn't exist or a more expensive one. Contemporary code is more likely to reach for bignum which is logn, but again stairstepped to each number of…

You cannot put 51 pigeons in 50 pigeonholes. So the key length of your hash keys is m >= logn, which means the time to compare keys is also logn, which means hash tables are never actually O(1) access or insert time. I am not sure I am following this argument. You are not going to have more than 2^64 pigeons and pigeonholes on any system soon and I almost dare to say you will never ever get to 2^128. And for 64 or 12…

Are your hash keys 8 bytes long? Mine aren't. Mine aren't even close.

Re: Nanosecond timestamp collisions are common

#253

Post by lazide »

Dylan16807 wrote: post #251
lazide wrote: post #250

Earlier quoted context omitted.

Only when writing all at once and when you know what the shard boundaries are and the number of shards (and boundaries) are stable. If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically. Very large real world datasets are unlikely to be static long enough, and equipment stable enough, to not consider this eff…

> If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically. I'm confused by your reply, because I never suggested not to use random bits for sharding. I'm just saying that 60+ random bits should be enough to shard, change, grow, and sub-shard with. You don't need 122.

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

Re: Nanosecond timestamp collisions are common

#254

Post by darkclouds »

Joker_vD wrote: post #57
darkclouds wrote: post #30

Earlier quoted context omitted.

> This is why you should use ids that combine both a time component and a sequence. Computers should run like clockwork, so in this example of using all the cores, in Windows and likely some other OS's, threads are assigned to cores when they are started and you can have many threads per core, ergo the time component should also have the thread and the core number combined with it with multi core systems. Its possibl…

> threads are assigned to cores when they are started Do they? I thought the normal behaviour was for cores to pick any available thread to run, so core migration is quite normal. > ergo the time component should also have the thread and the core number combined with it with multi core systems. Sorry, how exactly does it follow from the previous? You seem to have omitted the other half of your syllogism. After all, c…

>> threads are assigned to cores when they are started

>Do they? I thought the normal behaviour was for cores to pick any available thread to run, so core migration is quite normal.

The CPU and its cores know very little about threads, threads are a figment of the OS.

>Sorry, how exactly does it follow from the previous? You seem to have omitted the other half of your syllogism

Syllogism would perhaps be a intuitive word to use, why is this? What happened to you?

Re: Nanosecond timestamp collisions are common

#255

Post by Timon3 »

EGreg wrote: post #233
Timon3 wrote: post #167

Earlier quoted context omitted.

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

the content is not, but it can use a database function, such as CURRENT_TIMESTAMP or RANDOM() can it not?

I'm not sure what you're getting at. How are those connected to the topic? Those functions aren't infrastructure implementations either.

Re: Nanosecond timestamp collisions are common

#256

Post by Dylan16807 »

lazide wrote: post #253
Dylan16807 wrote: post #251

Earlier quoted context omitted.

> If they’re changing, growing, et c. you can’t tell where they’re at predictably and random is the least likely to cause problems and allow sub-sharding dynamically. I'm confused by your reply, because I never suggested not to use random bits for sharding. I'm just saying that 60+ random bits should be enough to shard, change, grow, and sub-shard with. You don't need 122.

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, instead of indirectly forcing it by making the entire UUID random.

Then you said "Only when writing all at once and when you know what the shard boundaries are and the number of shards (and boundaries) are stable."

I can't figure out how that relates to my post. I thought you were worried about insufficient random bits to use for sharding, but apparently that wasn't your concern. So I have no idea what your concern is. If you have a use case for randomness, use the random half of the UUID.

Re: Nanosecond timestamp collisions are common

#257

Post by notpushkin »

amelius wrote: post #144
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.

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

Re: Nanosecond timestamp collisions are common

#258

Post by zzo38computer »

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.

How will you sleep?

(Anyways, comparing the probabilities does not necessarily mean that the things being compared are both bad or both good.)

Re: Nanosecond timestamp collisions are common

#259

Post by zzo38computer »

fendy3002 wrote: post #26
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.

but is it higher or lower if the dinosaur is not fully grown?

I would guess slightly higher probability for a not fully grown dinosaur because the mass will be less, I think.

Re: Nanosecond timestamp collisions are common

#260

Post by bajsejohannes »

non-e-moose wrote: post #201

Silly Rabbit - absolutely accurate times are a security problem. CPU designers (even waay back in Alpha @ DEC) intentionally introduced clock jitter, just to prevent total predictability. For x86, I think if you performed 3-4 of them, and then saved the values in to registers, and then upon completion reported those values, you would find that the time deltas are NOT exactly the same.

Do you have any sources for this? My googling skills are failing me. I'm surprised early x86 (which I assume you're including) were aware of security issues with accurate clocks; I certainly wasn't until this millennium :D I would rather guess observed clock jitter would be explained by interrupts or some such. Not saying you're wrong, I'd just like to learn more.
Post reply on HN