News for hackers. Stuff that matters.
Re:Nanosecond timestamp collisions are common by p-e-w on Friday July 21, 2023 @03:51AM (#36811167)
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.

Re:Nanosecond timestamp collisions are common by jraph on Friday July 21, 2023 @03:53AM (#36811181)
I will take my chance :-)

More seriously, If you can use them, good old increments are probably best. They are fast and cheap. Especially in a database. They can have privacy/security issues (you could guess things by the values of ids of stuff). UUIDs are better in those case or when you deal with a distributed system.

Re:Nanosecond timestamp collisions are common by p-e-w on Friday July 21, 2023 @04:01AM (#36811244)
> They can have privacy/security issues (you could guess things by the values of ids of stuff).

Push them through a secure hash function, and that problem is solved too (assuming you can keep the base counter private).

Re:Nanosecond timestamp collisions are common by cacheyourdreams on Friday July 21, 2023 @04:12AM (#36811324)
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.)
Re:Nanosecond timestamp collisions are common by p-e-w on Friday July 21, 2023 @04:16AM (#36811357)
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.
Re:Nanosecond timestamp collisions are common by cacheyourdreams on Friday July 21, 2023 @04:23AM (#36811397)
Yes, I tend to like this philosophy in database design, of internal sequential ids which are used for joins between tables etc. and an exposed "external reference". But I typically would use a UUID for my external reference rather than a hash of the internal id.
Re:Nanosecond timestamp collisions are common by newaccount74 on Friday July 21, 2023 @04:38AM (#36811482)
Doesn't that just add a whole lot of unnecessary complexity? If elements have multiple IDs, one of which should not be leaked to the outside, that's just asking for trouble in my opinion.

Is generating UUIDv4 or UUIDv7 really too much effort? I'd assume that writing the row to the database takes longer than generating the UUID.

Re:Nanosecond timestamp collisions are common by iforgotpassword on Friday July 21, 2023 @04:53AM (#36811586)
It also means once your hash function leaks for whatever reason or gets brute forced because of whatever weird weakness in your system, it's game over and everybody will forever be able to predict any future ids, guess neighboring ids, etc., unless you're willing to change the hash and invalidate all links to any content on your site.

If I'm in a scenario where I think I need consecutive ids internally and random ones externally, I'll just have two fields in my tables.

Re:Nanosecond timestamp collisions are common by jstanley on Friday July 21, 2023 @05:17AM (#36811722)
You need 2 fields anyway, unless you want to have to brute force your hash function when you need to invert it.
Re:Nanosecond timestamp collisions are common by wongarsu on Friday July 21, 2023 @09:34AM (#36813565)
Store just the sequential id, compute the hash on the edge.

This keeps your database simple and performant, and pushes complexity and work to the backend servers. This can be nice because developers are typically more at home at that layer, and scaling the backend can be a lot easier than scaling your database. But it also comes with the downsides listed in this thread.

Re:Nanosecond timestamp collisions are common by jstanley on Friday July 21, 2023 @11:17AM (#36814804)
That's fine, but when a request comes in referencing only a hash and not an id (because you're not leaking ids to clients), how do you get the id?
Re:Nanosecond timestamp collisions are common by wongarsu on Friday July 21, 2023 @11:27AM (#36814920)
Good point. Back when we did that we just used a reversible hash function (some would call it encryption). There are some simple algorithms meant for encrypting single integers with a reasonable key.
Re:Nanosecond timestamp collisions are common by iforgotpassword on Friday July 21, 2023 @01:51PM (#36817072)
I might be misremembering, but didn't YouTube do this in the early days? So yeah, that was what I was thinking of when replying, not a traditional hash function.
Re:Nanosecond timestamp collisions are common by asimpletune on Friday July 21, 2023 @05:43AM (#36811893)
If you're hashing for security reasons, I think you should still maintain a salt.
Re:Nanosecond timestamp collisions are common by stickfigure on Friday July 21, 2023 @03:45PM (#36818648)
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 by jandrewrogers on Friday July 21, 2023 @08:31PM (#36821921)
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 by marcosdumay on Friday July 21, 2023 @12:56PM (#36816302)
Hum, no. You can easily hash numbers from 1 up to the value you see and guess the next value.

If you want a secure identifier, make a random 64 or 128 bits number (a UUID type 4). And do not use this number as an internal identifier, because identifiers performance is all about predictability and low entropy.

Re:Nanosecond timestamp collisions are common by gnulinux on Friday July 21, 2023 @01:05PM (#36816447)
If you use a robust salt, such a randomly generated long salt, attacker won't be able to guess the next hash.
Re:Nanosecond timestamp collisions are common by fluoridation on Friday July 21, 2023 @02:47PM (#36817821)
A block cipher is better, as it's guaranteed to not have collisions.
Re:Nanosecond timestamp collisions are common by p-e-w on Friday July 21, 2023 @03:57AM (#36811214)
Unless the RNG itself is the problem, there's no reason not to. All kinds of civilization-ending catastrophes are vastly more likely than a collision in a space of size 2^122.
Re:Nanosecond timestamp collisions are common by dtech on Friday July 21, 2023 @04:01AM (#36811247)
v7 looks nicer since it solves v4's locality issue and you're still a gazillion times more likely to win the lottery than generate a collision.
Re:Nanosecond timestamp collisions are common by p-e-w on Friday July 21, 2023 @04:06AM (#36811280)
Unfortunately, many libraries don't implement it yet.
Re:Nanosecond timestamp collisions are common by gmhafiz on Friday July 21, 2023 @05:50AM (#36811936)
It is still in draft and I've watched the spec changed at least once.
Re:Nanosecond timestamp collisions are common by enyone on Friday July 21, 2023 @03:54AM (#36811184)
the dinosaur is now on my bed, what next?
Re:Nanosecond timestamp collisions are common by MattPalmer1086 on Friday July 21, 2023 @03:56AM (#36811207)
Close the door and immediately switch to v5.
Re:Nanosecond timestamp collisions are common by quickthrower2 on Friday July 21, 2023 @06:28AM (#36812160)
Enjoy the non heat-death of the universe
Re:Nanosecond timestamp collisions are common by lyu07282 on Friday July 21, 2023 @07:23AM (#36812510)
I would just call Randall Munroe, he will know what to do
Re:Nanosecond timestamp collisions are common by Ankaios on Friday July 21, 2023 @07:31PM (#36821439)
Find a better random number generator.
Re:Nanosecond timestamp collisions are common by fendy3002 on Friday July 21, 2023 @03:55AM (#36811194)
but is it higher or lower if the dinosaur is not fully grown?
Re:Nanosecond timestamp collisions are common by zzo38computer on Saturday July 22, 2023 @03:25AM (#36824150)
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 by littlestymaar on Friday July 21, 2023 @05:35AM (#36811837)
> 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.

I'd love to see the math for the probability of the second option.

Re:Nanosecond timestamp collisions are common by beefield on Friday July 21, 2023 @07:01AM (#36812341)
Knowing nothing about UUID v4 generation, I have likely a stupid question. What makes you so confident that all implementations and their entropy sources are flawless enough to make actual collision probability close enough to theory?
Re:Nanosecond timestamp collisions are common by Thiez on Friday July 21, 2023 @08:11AM (#36812892)
What makes us so confident that our database implements ACID correctly, the RAM stores bins correctly, and the disk drivers store the data correctly?

In the end we have to make some assumptions about the correctness of (some of the) components.

Re:Nanosecond timestamp collisions are common by tjoff on Friday July 21, 2023 @09:22AM (#36813439)
We are not confident in any of that. Which is why we mitigate it with checksums, ECC etc.

So depending on the consequences you might opt to reduce the risk or help mitigate the consequences.

To just state that it is about as likely as my coffee maker being a portal to the future isn't very helpful. Poor entropy sources or bugs are not uncommon.

Re:Nanosecond timestamp collisions are common by amelius on Friday July 21, 2023 @10:27AM (#36814190)
> 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.

Re:Nanosecond timestamp collisions are common by notpushkin on Saturday July 22, 2023 @03:11AM (#36824078)
I don't see how sudden dinosaur appearance is a bad thing.
Re:Nanosecond timestamp collisions are common by zzo38computer on Saturday July 22, 2023 @03:22AM (#36824133)
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 by amelius on Saturday July 22, 2023 @06:54AM (#36825177)
Perhaps it is made of anti-matter.