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

241–250 of 291 posts

Re: Nanosecond timestamp collisions are common

#241

Post by datenwolf »

amelius wrote: post #214
datenwolf wrote: post #196

Earlier quoted context omitted.

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

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.

Re: Nanosecond timestamp collisions are common

#242

Post by danbruc »

hinkley wrote: post #223
hansvm wrote: post #212

Earlier quoted context omitted.

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

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 128 bit keys comparisons and many other operations are for all practical purposes constant time. I guess you could argue that this is sweeping a factor of log(n) under the rug because of things like carry chains which could be faster for smaller bit sizes but I am not sure that this is really useful on common hardware, an addition will take one clock cycle independent of the operand values.

Re: Nanosecond timestamp collisions are common

#243

Post by jandrewrogers »

stickfigure wrote: post #221
p-e-w wrote: post #43

Earlier quoted context omitted.

The difference is that you can still use sequential IDs internally, while exposing hashed IDs to the outside. This protects your database from collisions under all circumstances, while in the absolute worst case, a single user might experience bugs because two external IDs collide.

This is a weird proposal. If you're using non-hashed IDs internally and exposing hashed IDs externally, you are going to need to map those (securely hashed) ids back to internal ids when the client hands them to you. I guess you could do this with complete table scans, hashing the ids and looking for matches, but that would be horribly inefficient. You could maintain your own internal reverse index of hash -> id but…

Yes, it is more reasonable to use encrypted IDs externally from structured/sequential IDs internally, not hashed IDs. Recovering the internal ID from the external ID is computationally trivial since it will fit in a single AES block and you don't have to worry about collisions.

Re: Nanosecond timestamp collisions are common

#244

Post by remram »

lazide wrote: post #229
remram wrote: post #228

Earlier quoted context omitted.

If that is the case then why shouldn't the storage system hash the IDs itself, to spread them as it requires?

Because sometimes you want some data to be collocated, while the rest sharded. For instance, you might use a random object ID as a prefix value in the index, followed by attribute ID which isn’t. Or a modified time, so you can have a history of values which can be read out linearly. If using it directly, that means Objects and their data are sharded randomly across, but when looking for an objects attributes (or attr…

Sounds like it should be an attribute of the index and not require a change in the data. To me, anyway.

    CREATE INDEX ... USING HASH;

Re: Nanosecond timestamp collisions are common

#245

Post by lazide »

remram wrote: post #244
lazide wrote: post #229

Earlier quoted context omitted.

Because sometimes you want some data to be collocated, while the rest sharded. For instance, you might use a random object ID as a prefix value in the index, followed by attribute ID which isn’t. Or a modified time, so you can have a history of values which can be read out linearly. If using it directly, that means Objects and their data are sharded randomly across, but when looking for an objects attributes (or attr…

Sounds like it should be an attribute of the index and not require a change in the data. To me, anyway. CREATE INDEX ... USING HASH;

I’ve never seen that kind of optimization on a dataset that would fit on a database server of any kind. Tens of PB or EB usually, but sometimes only several hundred TB if it’s high load/in-memory only.

Re: Nanosecond timestamp collisions are common

#247

Post by Dylan16807 »

lazide wrote: post #205
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.

depending on scale and architecture, either behavior can be better. 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)

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?

Re: Nanosecond timestamp collisions are common

#248

Post by zamadatix »

sfink wrote: post #194
zamadatix wrote: post #177

Earlier quoted context omitted.

The hash, in this case, is just one deterministic way to shorten the CPU counter to few bits which can then be used to increase the entropy of the timestamp by replacing the timestamps stale bits. What's being asked here is not why use some compressed bits of the CPU counter increases the entropy of the timestamp overall. Rather, why you'd use a hash of the entropy providing information to do this since hashes allow…

Yeah, when I was thinking about the hash, I thought of it as stuffing to fill the unused portion of the number that would look better than using zeroes. TIMESTAMP010111101010101TSC "looks better" than TIMESTAMP000000000000000TSC even though they contain the same information. I would drop the hash, it's deceptive. I don't believe it breaks the monotonicity, though? I mean, it would if it weren't already broken. If you…

I guess it depends which portion you look at. If you solely look at the time based portion you do indeed still have a function which never decreases but that is true even in the case of reading the raw counter whole on its own anyways. If you look at the whole value, including the hashed portion, it's no longer monotonic.

In the cycle based case looking at the whole value is the same thing as looking at a relative time stamp which has more precision that the system clock. In this way, it's "truly" monotonic across the entire value, not just monotonic on a part and unique in another.

Side topic: It also comes with an even stronger guarantee of always increasing instead of just "not changing direction". Is there a name for that?

Re: Nanosecond timestamp collisions are common

#249

Post by zamadatix »

datenwolf wrote: post #241
amelius wrote: post #214

Earlier quoted context omitted.

What definition of entropy do you use? (I'm using Shannon entropy.)

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.

Re: Nanosecond timestamp collisions are common

#250

Post by lazide »

Dylan16807 wrote: post #247
lazide wrote: post #205

Earlier quoted context omitted.

depending on scale and architecture, either behavior can be better. 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)

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

Post reply on HN