Nanosecond timestamp collisions are common • Hacker News Board

Re: Nanosecond timestamp collisions are common

#221

Post by stickfigure » Fri, Jul 21, 2023, 7:45 PM UTC

p-e-w wrote: post #43

cacheyourdreams wrote: post #42

Earlier quoted context omitted.

If you're going to do that then you might as well just use UUID, since you effectively reintroduce the negative aspects of that (infinitesimally miniscule chance of collisions, computation involved in the calculation, etc.)

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 now I have to ask what's the point? You aren't saving any storage and you're adding a lot of complexity.

Seems like if you want random unguessable external ids, you're always better off just generating them and using them as primary keys.

Also, you aren't protecting your database "from collisions under all circumstances" - there's no guarantee your hash won't collide even if the input is small.

Re: Nanosecond timestamp collisions are common

#222

Post by [deleted] » Fri, Jul 21, 2023, 7:47 PM UTC

danbruc wrote: post #91

qwerty456127 wrote: post #86

Earlier quoted context omitted.

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

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.

[deleted]

Re: Nanosecond timestamp collisions are common

#223

Post by hinkley » Fri, Jul 21, 2023, 7:49 PM UTC

hansvm wrote: post #212

hinkley wrote: post #210

Earlier quoted context omitted.

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.

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 integers it takes to represent the entire number. A bigger problem when your data set is sparse, so that values grow faster than population (eg, UUID).

But on the topic of hash tables, you can only reach 'O(1)' if you can avoid collisions. And to avoid collisions you need a key of length m, which grows as n grows. 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. Actual access time for a hash table on non-imaginary hardware is √nlogn, not O(1).

If you consider that we have applications that are just a single hash table occupying the entire RAM of a single machine, then this is not picking nits. It's capacity planning.

Re: Nanosecond timestamp collisions are common

#224

Post by daniel-cussen » Fri, Jul 21, 2023, 7:49 PM UTC

zokier wrote: post #107

ajb wrote: post #73

Earlier quoted context omitted.

For devices clocked above 1Ghz it's perfectly possible for the clock to increment every ns, although that doesn't make it accurate to that level, and multi core systems may have clocks that are not synchronised to that level. ARMv8 guarantees that it's clock increments at at least 1Ghz, for intel and earlier ARM it's more complicated

Cycle counting is one thing, but it gets tricky when you have frequency scaling in play. Another problem that even without freq scaling, cpu clocks are not designed to be super accurate/exact, and the true frequency might vary significantly even if the nominal freq is fixed

It doesn't matter that much they're not super accurate exact, they do in fact count ticks n tocks j dandy. I wonder if they are counted equally, interesting question if i do say so myself about my own question, i know rising edge is steady w the next rising edge, n falling edge w falling edge, but yeah...no i think that's a specification figure of merit, that they be balanced w respect to each other. N Intel® despite it's many failures, long ago forecast n long overdue due to the sheer difficulty of their business model n how long they kept it going--they were saying it was going to end soon in the late seventies already--n you know what, i'm fine w that. They don't make old chips rot like other software companies i could mention, bits rot but glass is timeless. Which brings me back to the point, in my analysis the problem is not the clocks being inaccurate but rather the jitter, which means a single run will not suffice in describing a repeatable exact clock time taken for eg an inner loop, which is what is worth bothering with. The minimum jitter attainable currently is 1 cycle, n then i guess you run the same code repeatedly n take the minimum with more repeatability as a consequence of that low jitter.

In the early nineties it was not so, you'd get the same number of clock cycles again n again n again.

N then it gets tricky because cycle counts are thresholds set within which, if voltages n frequency are proper, the operation will complete deterministically w a soft error rate no greater than the system as a whole, about one per 30 years of hammering on the chip at sea level. Which is not enough for my tastes, n the jitter is a fucking mess.

I much prefer the GA144, least jitter of any platform bar none, sensible because it is fully asynchronous logic, no clock anywhere in sight until you connect it to an oscillator, n even then the vibration doesn't rock the system like that of a grandfather clock synchs w another grandfather clock with whose pendulum's swing the former clock's pendulum swing is aligned. GA144 it's pretty easy to tell average case complexity of a function down to the tens of picoseconds, at which point you have to check that there's no open window letting a draft in. In fact the time trial will tell you such a draft is coming into the house, it happened to me, while not from a parallel universe in spacial dimensions it is by all means from another universe in the time dimension.

Re: Nanosecond timestamp collisions are common

#225

Post by pc86 » Fri, Jul 21, 2023, 8:01 PM UTC

TRiG_Ireland wrote: post #122

e12e wrote: post #112

Earlier quoted context omitted.

Any pure relational database design will eschew surrogate keys - most real-world systems will (should) add them back - because a surprising number of good natural keys end up changing (names change, phone numbers change, emails change, twitter handles become irrelevant/disappear, location of birth may change subject to geographic regions changing size...). And on top of all that, there are efficiency concerns. That s…

> location of birth may change My British passport says I was born in Birr; my Irish passport says I was born in Galway. These are both correct, because they are answering different questions. (I was born in the town of Ballinasloe in County Galway, but my mother's place of residence at the time of my birth was the town of Birr in County Offaly.)

So British place of birth means "mother's residence" and not place of birth?

Re: Nanosecond timestamp collisions are common

#226

Post by wewtyflakes » Fri, Jul 21, 2023, 8:05 PM UTC

godelski wrote: post #208

Rapzid wrote: post #98

Earlier quoted context omitted.

> I can't imagine it is actually nanoseconds It's nanoseconds.

1? 10? 100? Those are all nanoseconds. When someone is asking about precision it tends to be a good thing to be precise in your answer.

You were similarly not precise in your skepticism. ;)

Re: Nanosecond timestamp collisions are common

#227

Post by btilly » Fri, Jul 21, 2023, 8:50 PM UTC

mattashii wrote: post #66

mcv wrote: post #64

Earlier quoted context omitted.

But shouldn't that be a separate field then?

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.

Re: Nanosecond timestamp collisions are common

#228

Post by remram » Fri, Jul 21, 2023, 9:05 PM UTC

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)

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

Re: Nanosecond timestamp collisions are common

#229

Post by lazide » Fri, Jul 21, 2023, 9:18 PM UTC

remram wrote: post #228

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)

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 attribute by time), their index entries are always co-located and you can read them out linearly with good performance.

If blindly hashing keys to distribute them, you can’t do that. Also, you can’t really do a linear read at all, since no data will be ‘associatable’ with others, as the index value is randomized, and what is stored in the index has no related to the key provided by the user.

You can only do a straight get, not a read. That is very limiting, and expensive with large data sets as most algorithms benefit greatly from having ordered data. (Well, you could do a read, but you’d get back entries in completely random order)

Needless to say, this is ‘advanced’ usage and requires pretty deep understanding of your data and indexing/write/read patterns, which is why random hashing is the most common hash map behavior.

Re: Nanosecond timestamp collisions are common

#230

Post by hinkley » Fri, Jul 21, 2023, 9:23 PM UTC

yohannesk wrote: post #219

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.

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

Yeah they had a problem where the amortized ID rate was less than the number of valid UUIDs you could generate in a given time interval, but with a peak rate well above that, so UUIDs weren't quite going to function for naming/numbering them. You gotta be pushing a lot of messages through a system to hit that, but it's possible. And adding more layers of coordination on top of something meant to reduce coordination overhead tends to... make things messy.

I've half-heartedly tried to look up his problem every time I've had to introduce UUIDs to something (most recently fixing agents not generating correlation IDs), and I have not figured out which version of UUID he was talking about. I now suspect it was some proprietary or industry-specific quote-unquote UUID spec rather than an industry wide one. I may look through the UUID7 spec at some point to see if they mention prior art. Much more plausible than him being a time traveler.