Serial type and possible exceptions

sql

#1

Hi every one.

I have a few question about using serial as primary key

Serial type can generate collision only on system with number of insert >= 100000 per second or can an exception occur in smaller systems?

This red line concerns 100K per table, database, node or cluster?
What can happen after crossing generate 100000 ids per second: system will return “not unique” id or the query return an error?


(Andrew Dona-Couch) #2

Hi @todo, these are some interesting questions about the behavior of SERIAL with an extremely large number of inserts per second. I’ll try to answer them to the best of my knowledge.

The limit is the number of bits used to represent the timestamp part of the return value of unique_rowid(), 48 bits, with a resolution of 10 microseconds. The implementation uses GenerateUniqueInt (implementation here: https://github.com/cockroachdb/cockroach/blob/280c15872575a775b4f5f7a63fe8fd3e29c3dfed/pkg/sql/sem/builtins/builtins.go#L3456) to provide unique integers. That method uses locking to ensure the results are truly unique (though there is a todo comment in that code that raises an interesting question).

// TODO(pmattis): Do we have to worry about persisting the milliseconds value
// periodically to avoid the clock ever going backwards (e.g. due to NTP
// adjustment)?

Since the lock that GenerateUniqueInt takes is global, there doesn’t seem to be a way to cause a collision just by increasing load. Per that todo comment I’m not so sure about clock jumps.

Since the other part of the default value is the node id, I think the limit is per node, since rows created on different nodes would never collide. (see https://www.cockroachlabs.com/docs/stable/create-table.html#create-a-table-with-auto-generated-unique-row-ids)

That’s an interesting question. GenerateUniqueInt guarantees its result is monotonic. It looks to me like it would just mean that the timestamp clock is always running faster than real time, so the timestamp gets further and further ahead. This just means you won’t have the full 89 years of unique timestamps that method guarantees, but you shouldn’t have a uniqueness violation as far as I can tell.

We’d definitely recommend using UUID instead if that’s possible for your application, since it’s so much more resistant to collision. The performance will be better, too, since new row ids will scatter across ranges for the table rather than concentrating in one hot range.


(Dmitriy Cherchenko) #3

I’ve had this same question before but haven’t had the time to ask it. Thanks for the help.

However, I’m still not sure about the locking that’s being done:
Is the lock like a transaction? Does it require communicating will all other nodes?

Also, doesn’t UUID have the same timestamp collision problem (even though that’s less likely)? If there are 100,000 rows being generated per node per second (suppose the load is not being distributed uniformly), and part of a UUID is a timestamp, it seems there could be a timestamp collision.

What I’m really wondering is if there is a lock (transaction?) when generating a UUID. Is there at least a guarantee that UUIDs generated by a particular node will not collide?


(Andrew Dona-Couch) #4

Hi @widerwebs, happy to help.

No, the lock I mentioned is node-local. I think maybe my use of the term “global” was confusing, I meant like a node process global variable, not that it was global to the cluster. Each node has its own monotonic sequence, and combined with a the node id this makes the generated row id unique on the cluster.

Both uuid_v4() and gen_random_uuid() use version 4 UUID, which doesn’t incorporate a timestamp at all, it’s just random bits. Apparently the chances of collision are monumental, see https://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

There isn’t any such guarantee, but apparently the odds are very small. From the Wikipedia link: “Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.”