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.
Nanosecond timestamp collisions are common
201–210 of 291 posts
Re: Nanosecond timestamp collisions are common
#202Earlier 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.
One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.
it's commonly totally sufficient for IDs to represent a rough sort order
millisecond precision is great for a lot of use cases
Re: Nanosecond timestamp collisions are common
#203Earlier quoted context omitted.
Why? low bits + CPU cycle counter is enough. No need of the hash()
You don't know precisely at which frequency the cycle counter runs. Depending on the system load it might either run faster or slower than the lowest bits the HPTC. For what it's worth this part is more or less nondeterministic, so the sane thing to do, is spread out the information as much as possible (maximize entropy), in order to minimize the probability of collisions.
That's ok, the bits past the low bits are just there to avoid collisions, not an actual measure of high precision time beyond the low bits.
It's not worse than the hash solution, I'm just saying it's not necessary to hash it if the only objective is to reduce collisions.
In fact the hashing solution, if it is replacing the low bits with a hash of low bits plus something else, is actually destroying valuable time information.
Re: Nanosecond timestamp collisions are common
#204Earlier quoted context omitted.
How big is the 1 though?
When you’re talking about data sets so large they dictate what hardware you use, and introduce terms like “cluster”, then 1 = √n Which is why we need a version 2 of complexity theory, that doesn’t treat memory access or arithmetic on arbitrary precision numbers (aka as n actually goes to infinity) as O(1) operations. They aren’t. Which every large system engineer knows but few will talk about.
Why sqrt(n) and not log(n)?
And that complexity theory already exists. Typical whiteboard engineering uses transdichotomous models to gloss over some polylogarithmic factors (as do much of the literature), but more accurate models exist.
The difference isn't usually super relevant when comparing multiple solutions all using the same model of computation though since the extra terms don't tend to bump one complexity class above another when switching models, and if you cared about actual runtime characteristics you wouldn't be relying on log factors in such a crude tool anyway.
Re: Nanosecond timestamp collisions are common
#205Earlier 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.
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)
Re: Nanosecond timestamp collisions are common
#206Earlier quoted context omitted.
You don't know precisely at which frequency the cycle counter runs. Depending on the system load it might either run faster or slower than the lowest bits the HPTC. For what it's worth this part is more or less nondeterministic, so the sane thing to do, is spread out the information as much as possible (maximize entropy), in order to minimize the probability of collisions.
That's ok, the bits past the low bits are just there to avoid collisions, not an actual measure of high precision time beyond the low bits. It's not worse than the hash solution, I'm just saying it's not necessary to hash it if the only objective is to reduce collisions. In fact the hashing solution, if it is replacing the low bits with a hash of low bits plus something else, is actually destroying valuable time info…
That only works, if you know exactly, that the low bits are constant. Otherwise you may run into the issue that due to unsteady rate of RDTSC between two processes/threads that may be preemptively unscheduled between reading the HPTC and the RDTSC you might again end up with colliding time stamps. And if you took the derivative between timestamps taken in succession, you might even find is to be non-monotonic in places.
The combination of multiple counters incremented by individual unsteady clocks used to be a source for pseudo random scrambler sequences; these days we prefer LFSRs, but overall this is something that can be weird.
Hence my recommendation: Just throw xxHash32 on concatenation of the HPTC's low bits and the CPU clock cycle counter, and forgo any pretense of monotony in the low bits (because very likely you don't have it anyway).
Re: Nanosecond timestamp collisions are common
#207Earlier 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 feel like v7 is almost a strictly better v4. Assuming you can generate a v7 (you have a time source), what are the disadvantages?
Anyone who can see the uuidv7 can determine at what time it was generated. You might not want that for things exposed to users.
Re: Nanosecond timestamp collisions are common
#208Despite the resolution being nanoseconds, what is the actual precision of computer clocks? I can't imagine it is actually nanoseconds. Takes me back to teaching physics labs where I had to hound students to remember that the accuracy of their measuring device is not identical to the smallest number it displays...
> 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.
Re: Nanosecond timestamp collisions are common
#209Earlier quoted context omitted.
One benefit of keeping it separate is that you can choose the precision of the timestamp necessary. "Millisecond precision" is arbitrary and commonly insufficient.
it's commonly totally sufficient for IDs to represent a rough sort order millisecond precision is great for a lot of use cases
I didn't say that it wasn't. Hell even ms is too precise for many use cases (usually where date is used instead).
What I said was that it's useful to be able to select timestamp precision independently of UUID implementation. One size that fits all fits none best.
Re: Nanosecond timestamp collisions are common
#210Earlier quoted context omitted.
When you’re talking about data sets so large they dictate what hardware you use, and introduce terms like “cluster”, then 1 = √n Which is why we need a version 2 of complexity theory, that doesn’t treat memory access or arithmetic on arbitrary precision numbers (aka as n actually goes to infinity) as O(1) operations. They aren’t. Which every large system engineer knows but few will talk about.
Why sqrt(n) and not log(n)? And that complexity theory already exists. Typical whiteboard engineering uses transdichotomous models to gloss over some polylogarithmic factors (as do much of the literature), but more accurate models exist. The difference isn't usually super relevant when comparing multiple solutions all using the same model of computation though since the extra terms don't tend to bump one complexity c…
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 radii, not gate depth.
In a world where clusters are rare, Knuth made decent approximations. In a world where clusters are not only de rigeur but hosted on multitenant hardware spread out over upwards of 100 miles, those approximations are bullshit and need to change.