This article misses the point. It’s not about the random writes, it’s about locality, a critical property of data. Random identifiers like v4 UUIDs have no locality: writes and reads will occur all over the index (no matter what index data structure you have).
The key advantage of UUIDv7’s is that they enable temporal locality, so when your database needs to check uniqueness constraints (for idempotent processing), only a small portion of the index will be hot (recent items). With random identifiers, the working set eventually becomes all of the data and your database will be page faulting continuously.
Speaking of which, I knew this was supposed to be an issue, so used a sequential UUID generator for identifiers used in indexes in SQL Server.
I then ran a tool which migrated from a previous database design to a new design (as part of work on rebuilding a product).
The database had some tables over 10m rows, in a schema with hundreds of tables, with a total data size over 10GB.
I did one migration using the sequential generator and one using the standard, random generator.
I then ran performance tests on the application that used the database - against both versions. I saw no difference in performance.
I kept the sequential generator in, just because I didn’t know if I’d missed some access pattern that would be pathological, or if the data would get to a size where this mattered.
I was pretty sure that the indexes for this database would be big enough for this to show up.
It sounds like you’ve seen this happen. Do you have anything you can point me at which shows where it became an issue in a real world database, please? I don’t doubt it’s an issue, just want to understand the kind of scenarios where it is worth the extra complexity of forcing sequential (or ‘temporally local’) ID generation.
The main issue of random keys is not on reading, it’s on insert: while the CS complexity is O(log n) in both cases an insert in the middle of the tree can cascade into a lot more effective rebalancing work than an insert at the end. This also causes a lot of write amplification, as each of these rebalancing needs to rewrite a bunch of blocks.
Although because there’s a loss of locality, it can have an impact on batch reads (when trying to read records which are temporally close). I would expect that effect to be larger if the index is clustered (that is not the case in Postgres).
Also I think random inserts can cause a btree to be very sparse, which takes more space and requires more reading than a denser tree, but I’d expect that to show even less especially with SSDs.
All UUIDv4 problems suddenly become null with a Hash Index instead of a B tree-based structure.
Constraints can’t usually be backed by hash indexes e.g. in postgres a PK or UNIQUE constraint only works with a btree. So UUIDv4 requires a tradeoff between your data model decisions and your efficiency.
Yes, you’re right. Of course we can assume UUIDv4 takes care of uniqueness anyway (assuming proper implementation), but I think I should update the PostgreSQL specific section, because it’s worth to note and I guess some architects are not willing to take the risk.
Of course we can assume UUIDv4 takes care of uniqueness anyway
In the source table yes, but if you use it as join key then you may want / need to enforce unicity in tables where it’s an FK. In that case there is no intrinsic enforcement.
That seemed counterintuitive (wouldn’t a hash index be perfect for a unique index?) but I found an enlightening thread on the PG mailing list on why this is so.
IIUC this has now been lifted relatively recently (some number of years ago). I was thankful of this because I wanted a unique index on user-controlled strings, but btree indexes have effective length limits. So to resolve this I moved the index to a hash index which has no such limits.
This is what the migration ended up looking like:
ALTER TABLE feeds
DROP CONSTRAINT feeds_url_key,
ADD EXCLUDE USING hash (url WITH =);
I can’t remember exactly what the downsides of this are. At least you are losing prefix lookups but that wasn’t an issue in my use case.
I have a use case for CRDTs where v7 is exactly what I want for synchronising data between clients that run independently of each other until one decides to synchronise its changes:
I get good lookup times when I use them for unique foreign keys, and they are unique across all the devices that generate them.
Also important is that I can order them, so if a client has seen key X as its last received delta, I can just send everything “after” that.
I don’t have to store an extra time column to sort by every time I synchronise - doubling the index (id + time).
There is no privacy leak either, since every client that participates must receive the timestamp anyway. (Otherwise you can’t use CRDTs in my case).
In the general case, I would store a separated date time column anyway. UUIDv7 or other timestamp-based IDs (e.g., Snowflake ID) are not meant to give the creation date of something per se. That’s just some sort of coincidence because time is a good universal coordinator between distributed k-sorted ID generators. Of course, relying on it for some applications is okay, but implementations are allowed to alter timestamps for various reasons.
Querying range of identifiers might not be necessary from the customer use case, but is useful for partitioning data. You could instead partition on a secondary created_at timestamp, but now you’ve lost your global uniqueness guarantee: the same ID could appear in multiple partitions.
Good point, but just to be sure I understand. If you trust your UUID implementation (v4 or v7), why should you be concerned about losing uniqueness guarantee across multiple partitions? UUID is a pretty fair guarantee already, right?
Say the identifiers are generated in the application rather than the DB. During an insert the connection failed after the insert succeeded on the DB, but before this could be signalled to the application. The application retries the insert. If partitioning on created_at timestamps assigned by the DB, the new insert could succeed and you have two rows with the same ID in two separate partitions in the same table. Partitioning on v7 UUID ranges avoids this (admittedly edge) case.
I don’t think the article said either version of UUID was faster than serial. It avoided discussing serial in detail because making serial IDs public can increase the system’s vulnerability to bad actors:
UUIDv4 IDs have properties that make them suitable as public identifiers, unlike traditional auto-incremented integers.
They don’t disclose business information, e.g., number of orders so far.
They are not guessable: one cannot enumerate all identifiers to discover resources.
It is guessable yes, but then again, if you restrict the data resources to the owners of those resources, guessing does not give any information away about resources that the user does not own.
Enumeration then also doesn’t make sense (order 1000 out of how many?). If you rely on randomness for security that means you do security by obscurity, which is not optimal.
You can share an auto-incremented integer by also supplying an acces token for that resource. If the access token is not provided, return “resource not found”.
Enumeration then also doesn’t make sense (order 1000 out of how many?). If you rely on randomness for security that means you do security by obscurity, which is not optimal.
If you rely on randomness for security that means you do security by obscurity, which is not optimal.
Not optimal when it comes to a computer system for keeping information secure. I would argue that here the number of x (where in the above example x=#orders) is the information to be kept secret rather than a part of the system?
The German Tank problem is interesting! I wonder if production variability is accounted for. A software system with clients is not equivalent to a wartime production facility.
The security part is in response to this part:
They are not guessable: one cannot enumerate all identifiers to discover resources.
Using Hash Index in PostgreSQL is perilous before v10, beacuse they are not WAL-logged and not replicated. From version 10 and after, it’s perfectly fine.
I sure hope that’s not relevant to many people these days, as v11 is the earliest receiving support and v16 is current.
In the context of distributed system, it’s important to be sure different machines generates IDs without risk of collision. It’s not clear if UUIDv7 is more risky than UUIDv4 in that regard.
It’s just as random with a splash of locality at the beginning…
A v7 UUID has only 74 random bits, compared to 122 for v4. There’s clearly more of a chance of collisions with v7. (Although I have to think there are very few applications where 2^74 possible UUIDs per millisecond is not enough, especially if your main concern is “friendly” nodes generating colliding IDs.)
Isn’t the time technically random also because it’s “insertion time” ? You can’t know when someone will generate a UUID (and how long all the processes between hitting their “enter” key and getting those bits takes). Otherwise you know the future.
The relevant property isn’t whether you predict the ids, it’s whether they’re correlated. If your uuidv4s start colliding, there’s a bug in your rng which you should fix. If you have a lot of writes all in the same ms, well, there are a lot of possible causes of that and they’re not all bugs.
(Don’t think just of the random distribution of a single id, think of the random distribution of the entire set of ids. It’s possible e.g. for the former to be uniform while the latter is clumpy.)
B+ trees (and B trees in general) allows efficient queries on range (expressions that use the =, >, >=, <, <=, BETWEEN operators.) It appears that resources with a public exposed ID rarely need to be queried in range according to their primary key.
FWIW I did have a need for using between heavily with UUID’s, for partitioning the data for offload. With UUIDv4 it allows you to quite conveniently divide the entire space into 2^n partitions. With UUIDv7 I think it might still work with SQL Server, since it has a weird comparison order for UUID’s, but it definitely isn’t going to work for PostgreSQL.
This article misses the point. It’s not about the random writes, it’s about locality, a critical property of data. Random identifiers like v4 UUIDs have no locality: writes and reads will occur all over the index (no matter what index data structure you have).
The key advantage of UUIDv7’s is that they enable temporal locality, so when your database needs to check uniqueness constraints (for idempotent processing), only a small portion of the index will be hot (recent items). With random identifiers, the working set eventually becomes all of the data and your database will be page faulting continuously.
Speaking of which, I knew this was supposed to be an issue, so used a sequential UUID generator for identifiers used in indexes in SQL Server.
I then ran a tool which migrated from a previous database design to a new design (as part of work on rebuilding a product).
The database had some tables over 10m rows, in a schema with hundreds of tables, with a total data size over 10GB.
I did one migration using the sequential generator and one using the standard, random generator.
I then ran performance tests on the application that used the database - against both versions. I saw no difference in performance.
I kept the sequential generator in, just because I didn’t know if I’d missed some access pattern that would be pathological, or if the data would get to a size where this mattered.
I was pretty sure that the indexes for this database would be big enough for this to show up.
It sounds like you’ve seen this happen. Do you have anything you can point me at which shows where it became an issue in a real world database, please? I don’t doubt it’s an issue, just want to understand the kind of scenarios where it is worth the extra complexity of forcing sequential (or ‘temporally local’) ID generation.
The main issue of random keys is not on reading, it’s on insert: while the CS complexity is O(log n) in both cases an insert in the middle of the tree can cascade into a lot more effective rebalancing work than an insert at the end. This also causes a lot of write amplification, as each of these rebalancing needs to rewrite a bunch of blocks.
Although because there’s a loss of locality, it can have an impact on batch reads (when trying to read records which are temporally close). I would expect that effect to be larger if the index is clustered (that is not the case in Postgres).
Also I think random inserts can cause a btree to be very sparse, which takes more space and requires more reading than a denser tree, but I’d expect that to show even less especially with SSDs.
Constraints can’t usually be backed by hash indexes e.g. in postgres a PK or UNIQUE constraint only works with a btree. So UUIDv4 requires a tradeoff between your data model decisions and your efficiency.
Yes, you’re right. Of course we can assume UUIDv4 takes care of uniqueness anyway (assuming proper implementation), but I think I should update the PostgreSQL specific section, because it’s worth to note and I guess some architects are not willing to take the risk.
In the source table yes, but if you use it as join key then you may want / need to enforce unicity in tables where it’s an FK. In that case there is no intrinsic enforcement.
That seemed counterintuitive (wouldn’t a hash index be perfect for a unique index?) but I found an enlightening thread on the PG mailing list on why this is so.
https://www.postgresql.org/message-id/592254A5.9000809%40anastigmatix.net
IIUC this has now been lifted relatively recently (some number of years ago). I was thankful of this because I wanted a unique index on user-controlled strings, but btree indexes have effective length limits. So to resolve this I moved the index to a hash index which has no such limits.
This is what the migration ended up looking like:
I can’t remember exactly what the downsides of this are. At least you are losing prefix lookups but that wasn’t an issue in my use case.
I have a use case for CRDTs where v7 is exactly what I want for synchronising data between clients that run independently of each other until one decides to synchronise its changes:
As always, use the right tool for the right job.
In the general case, I would store a separated date time column anyway. UUIDv7 or other timestamp-based IDs (e.g., Snowflake ID) are not meant to give the creation date of something per se. That’s just some sort of coincidence because time is a good universal coordinator between distributed k-sorted ID generators. Of course, relying on it for some applications is okay, but implementations are allowed to alter timestamps for various reasons.
For CRDTs I think it’s a great fit though!
Querying range of identifiers might not be necessary from the customer use case, but is useful for partitioning data. You could instead partition on a secondary created_at timestamp, but now you’ve lost your global uniqueness guarantee: the same ID could appear in multiple partitions.
Good point, but just to be sure I understand. If you trust your UUID implementation (v4 or v7), why should you be concerned about losing uniqueness guarantee across multiple partitions? UUID is a pretty fair guarantee already, right?
Say the identifiers are generated in the application rather than the DB. During an insert the connection failed after the insert succeeded on the DB, but before this could be signalled to the application. The application retries the insert. If partitioning on created_at timestamps assigned by the DB, the new insert could succeed and you have two rows with the same ID in two separate partitions in the same table. Partitioning on v7 UUID ranges avoids this (admittedly edge) case.
If you’re using postgres I’m really curious to hear why a UUID would be faster than
serialanyway.I don’t think the article said either version of UUID was faster than
serial. It avoided discussingserialin detail because makingserialIDs public can increase the system’s vulnerability to bad actors:It is guessable yes, but then again, if you restrict the data resources to the owners of those resources, guessing does not give any information away about resources that the user does not own.
Enumeration then also doesn’t make sense (order 1000 out of how many?). If you rely on randomness for security that means you do security by obscurity, which is not optimal.
You can share an auto-incremented integer by also supplying an acces token for that resource. If the access token is not provided, return “resource not found”.
Just place two orders, one day (or one hour or one week) apart. Observe how the order ID has changed during that time.
You can get pretty good estimates for how many based on a a series of observations.
Not optimal when it comes to a computer system for keeping information secure. I would argue that here the number of x (where in the above example x=#orders) is the information to be kept secret rather than a part of the system?
The German Tank problem is interesting! I wonder if production variability is accounted for. A software system with clients is not equivalent to a wartime production facility.
The security part is in response to this part:
They are not guessable: one cannot enumerate all identifiers to discover resources.Yeah I realize it went unaddressed, I’m just curious. It’s true that it leaks data and is guessable.
IDORs has entered the chat xD
I sure hope that’s not relevant to many people these days, as v11 is the earliest receiving support and v16 is current.
It’s just as random with a splash of locality at the beginning…
A v7 UUID has only 74 random bits, compared to 122 for v4. There’s clearly more of a chance of collisions with v7. (Although I have to think there are very few applications where 2^74 possible UUIDs per millisecond is not enough, especially if your main concern is “friendly” nodes generating colliding IDs.)
Isn’t the time technically random also because it’s “insertion time” ? You can’t know when someone will generate a UUID (and how long all the processes between hitting their “enter” key and getting those bits takes). Otherwise you know the future.
The relevant property isn’t whether you predict the ids, it’s whether they’re correlated. If your uuidv4s start colliding, there’s a bug in your rng which you should fix. If you have a lot of writes all in the same ms, well, there are a lot of possible causes of that and they’re not all bugs.
(Don’t think just of the random distribution of a single id, think of the random distribution of the entire set of ids. It’s possible e.g. for the former to be uniform while the latter is clumpy.)
FWIW I did have a need for using between heavily with UUID’s, for partitioning the data for offload. With UUIDv4 it allows you to quite conveniently divide the entire space into 2^n partitions. With UUIDv7 I think it might still work with SQL Server, since it has a weird comparison order for UUID’s, but it definitely isn’t going to work for PostgreSQL.