6 ms·

What are the advantages of sortable UUIDs with embedded timestamps over random 128 bits and a created_at column?

by jozvolskyef 5y ago

munhitsu 5y ago
CRDT
weird-eye-issue 5y ago
Not having a created_at column and the index bloat that goes with it?
notamy 5y ago
It works better for databases that can only sort on the primary key (iirc Cassandra is one of these)
scrollaway 5y ago
One data point instead of two. Which may or may not have advantages depending on your situation. At any rate it's definitely simpler, and you don't have to forego the created_at column either.
lytedev 5y ago
My understanding is that if the UUID is not sortable, inserting it into an index can be a performance hit. So if you have a write-heavy table with non-sorted primary keys, you will have a lower ceiling (higher overhead).
- srcreigh 5y ago
  Know about primary vs secondary indexes? Generally 1 index contains the data, all the other indexes have pointers to that index in their leaf nodes. Usually the PK index contains the data So loading 1000 consecutive rows in a created_at secondary index takes two steps: 1) created_at index B-Tree traversal (maybe 10 pages from disk, max?) 2) Potentially loading 1000 randomly sorted pages from disk, dereferencing pointers (EXPENSIVE!) Whereas, if your primary key is sorted by time, loading 1000 rows is 1) slightly larger primary B-Tree traversal 2) no 2, you're done :)
  - srcreigh 5y ago
    I don't expect to get an explanation for why this received downvotes - but maybe someone can offer one? My best theory is that it's the Reddit "I don't need to understand how stuff works to be a programmer" crowd.
- NyxWulf 5y ago
  The lack of sorting is what this rfc is fixing.
ignoramous 5y ago
> What are the advantages of sortable UUIDs I guess for use-cases like Instagram's: "Generated IDs should be sortable by time (so a list of photo IDs, for example, could be sorted without fetching more information about the photos)... If you use a timestamp as the first component of the ID, the IDs remain time-sortable... [but require] more storage space (96 bits or higher) to make reasonable uniqueness guarantees" [0] [0] https://archive.is/xiMGZ https://archive.is/xiMGZ
- zimpenfish 5y ago
  cf also Twitter's Snowflake[1] which is [timestamp, worker number, sequence number] to give the same "roughly sortable by time" property. [1] https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake https://blog.twitter.com/engineering/en_us/a/2010/announcing...
BenoitEssiambre 5y ago
On top of reasons given by others, if the data likely to be queried together tends to get stored together because of this, things will be much more cache efficient and queries potentially much faster since for db loads, cache efficiency (not just ram but CPU cache), alleviates some of the most important performance bottlenecks.
causasui 5y ago
I use KSUIDs a ton in DynamoDB; it saves me from having to create and fill another index to sort items by creation time. The only case where I don't use them is if I don't want to create time of the item to be known to the user.
bilinguliar 5y ago
This allows you to keep recent records in DB cache, for example. Contrary, random keys would constantly invalidate the cache unless all your data fits in memory.
ape4 5y ago
Isn't that a possible security issue. MACs used to be predictable but then became random.
- jozvolskyef 5y ago
  I presume you are referring to UUIDv4/1, which has 122 random bits. It is a common misconception that this is insecure. In reality, the UUIDv4/1 is just a way to encode 122 random bits, which is more than enough for most needs. The property of being practically unguessable comes from the random generator, not from the encoding. Secondly, whether or not being predictable is a problem depends on the use case. The keys used on this forum are predictable and it is not an issue.
- lazide 5y ago
  I’m pretty sure you mean ‘stable’ not predictable here re:MACs? The issue with using Mac addresses is it essentially leaked tracking information on the machine being used to generate the uuid - you could associate every ID it ever generated back to that same machine, correlate it to things like open WiFi AP logs, whatever. Which is pretty scary sometimes. Many OS’s now randomly generate a new MAC on every disconnect/connect for this reason, to at least give some privacy.
masklinn 5y ago
Random primary keys play hell on database indexes.
cratermoon 5y ago
https://en.wikipedia.org/wiki/Partial_sorting https://en.wikipedia.org/wiki/Partial_sorting
mrighele 5y ago
The linked RFC talks about this (it refers to UUIDv4, which is not much different from 128 random bits): " First, most of the existing UUID versions such as UUIDv4 have poor database index locality. Meaning new values created in succession are not close to each other in the index and thus require inserts to be performed at random locations. The negative performance effects of which on common structures used for this (B-tree and its variants) can be dramatic. As such newly inserted values SHOULD be time-ordered to address this."
- LukeShu 5y ago
  > UUIDv4, which is not much different from 128 random bits To quantify how different: UUIDv4 has 6 fixed bits and 122 random bits.
- bob1029 5y ago
  Note that this totally-random key behavior is actually highly desirable when using dynamic programming techniques such as with the Splay Tree. It makes it statistically impossible for the tree to fall into a degenerate state.
  - pjscott 5y ago
    Splay trees aren't a dynamic programming thing (and aren't used in any database storage backends I know of). They are, however, conjectured to be no more than a constant factor slower than a dynamically optimal binary search tree. https://en.wikipedia.org/wiki/Optimal_binary_search_tree https://en.wikipedia.org/wiki/Optimal_binary_search_tree
    - bob1029 5y ago
      > Splay trees aren't a dynamic programming thing My mistake - I meant to write "dynamic optimality". As for the "not used in any database storage backends", I have personally started experimenting with them due to higher-order effects they can provide relative to their optimization technique. The fact that the most recently accessed node is always at the root also means that incremental tree updates are well-bounded in terms of # of nodes that would need to be rewritten to disk. This allows for much more efficient usage of storage-friendly things like append-only log structures.
gumby 5y ago
That is addressed in the introduction -- random access inserts (i.e. specularity) can be quite inefficient depending on your backing store.
jandrewrogers 5y ago
There are two issues not mentioned in the other comments with a random 128-bit UUID in real systems, both related to data scale: - They defeat data compression, which is an integral part of many database engines these days for both performance and scalability reasons. - For some very large systems, there is a UUID collision tail risk that while small is large enough to be plausible.
- neur4lnet 5y ago
  Its compression a legitimate concern for primary keys?
  - bob1029 5y ago
    If you are getting good compression on your primary keys, this may be cause for alarm. These should be high-entropy items.
    - jandrewrogers 5y ago
      The sole constraint on a primary key is that it is unique. Even in distributed systems, deterministically unique keys are almost always much more compressible than probabilistically unique keys, which is a double win. Should you desire a high-entropy key, e.g. for hash tables or security, this can be trivially derived from the low-entropy key while still guaranteeing deterministic uniqueness. Compressible primary keys are superior in every way.
  - jandrewrogers 5y ago
    Definitely, I've run into this problem many times. UUIDs are pretty bulky data types in database terms, usually larger than most other types in a typical table on average and possibly larger than rest of the row after including the index overhead, which creates cache pressure. Logical columns in a table are commonly stored physically as a vector, of UUIDs in this case, expressly for the purpose of compressing the representation. This saves both disk cache and CPU cache. For queries, the benefit of scanning compressed vectors is that it reduces the average number of page faults per query, which is one of the major bottlenecks in databases. Also, some data models (think graphs) tend to be not much more than giant collections of primary keys. Using the smallest primary key data type that will satisfy the requirements of the data model is a standard performance optimization in databases. It is not uncommon for the UUID that the user sees to be derived from a stored primary key that is a 32-bit or 64-bit integer.
orf 5y ago
Imagine you’re not using a storage platform that supports that access pattern. Think S3, DynamoDB or even a directory of files. Being able to encode your sort key in your primary key is a pretty nice property.
- datavirtue 5y ago
  Hmmm...Now I'm wondering why I never bothered to prepend a timestamp to a GUID.
  - orf 5y ago
    Because then it wouldn’t be a UUID in a format that other systems might expect or work more efficiently with.
halfmatthalfcat 5y ago
Using the uuid as a PK do to cursor based pagination for one.
parhamn 5y ago
it depends what "created_at" means, if it means "persisted_at" then they're also a bit different because these sorts of UUIDs are generated before being persisted (often long before for offline-and sync systems).
dheera 5y ago
Searching records and returning the results time-sorted in O(n) time instead of O(n log n) time.
deleted 5y ago
[deleted]
junon 5y ago
FWIW the linked RFC's "Background" section is really easy to understand even for people who aren't well versed in dist-sys concepts. I suggest giving it a read - it's quite well written.
runeks 5y ago
Follow-up question: What are the advantages of sortable UUIDs with embedded timestamps over having an auto-incrementing id column, a created_at column, and using the composite primary key (created_at, id)?
- rswail 5y ago
  Because an auto-incrementing id column has to be coordinated between processes that are writing to the database. That means allocating ids in blocks that are large enough that processes aren't blocked in getting an allocation, but they still need to request a block to maintain writing. That sequence allocation needs to be ACID as well, so that there is no chance of any allocation being repeated.

What are the advantages of sortable UUIDs with embedded timestamps over random 128 bits and a created_at column?

munhitsu 5y ago

CRDT

weird-eye-issue 5y ago

Not having a created_at column and the index bloat that goes with it?

notamy 5y ago

It works better for databases that can only sort on the primary key (iirc Cassandra is one of these)

scrollaway 5y ago

One data point instead of two. Which may or may not have advantages depending on your situation. At any rate it's definitely simpler, and you don't have to forego the created_at column either.

lytedev 5y ago

My understanding is that if the UUID is not sortable, inserting it into an index can be a performance hit. So if you have a write-heavy table with non-sorted primary keys, you will have a lower ceiling (higher overhead).

srcreigh 5y ago
Know about primary vs secondary indexes? Generally 1 index contains the data, all the other indexes have pointers to that index in their leaf nodes. Usually the PK index contains the data So loading 1000 consecutive rows in a created_at secondary index takes two steps: 1) created_at index B-Tree traversal (maybe 10 pages from disk, max?) 2) Potentially loading 1000 randomly sorted pages from disk, dereferencing pointers (EXPENSIVE!) Whereas, if your primary key is sorted by time, loading 1000 rows is 1) slightly larger primary B-Tree traversal 2) no 2, you're done :)
- srcreigh 5y ago
  I don't expect to get an explanation for why this received downvotes - but maybe someone can offer one? My best theory is that it's the Reddit "I don't need to understand how stuff works to be a programmer" crowd.
NyxWulf 5y ago
The lack of sorting is what this rfc is fixing.

ignoramous 5y ago

> What are the advantages of sortable UUIDs I guess for use-cases like Instagram's: "Generated IDs should be sortable by time (so a list of photo IDs, for example, could be sorted without fetching more information about the photos)... If you use a timestamp as the first component of the ID, the IDs remain time-sortable... [but require] more storage space (96 bits or higher) to make reasonable uniqueness guarantees" [0] [0] https://archive.is/xiMGZ https://archive.is/xiMGZ

zimpenfish 5y ago
cf also Twitter's Snowflake[1] which is [timestamp, worker number, sequence number] to give the same "roughly sortable by time" property. [1] https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake https://blog.twitter.com/engineering/en_us/a/2010/announcing...

BenoitEssiambre 5y ago

On top of reasons given by others, if the data likely to be queried together tends to get stored together because of this, things will be much more cache efficient and queries potentially much faster since for db loads, cache efficiency (not just ram but CPU cache), alleviates some of the most important performance bottlenecks.

causasui 5y ago

I use KSUIDs a ton in DynamoDB; it saves me from having to create and fill another index to sort items by creation time. The only case where I don't use them is if I don't want to create time of the item to be known to the user.

bilinguliar 5y ago

This allows you to keep recent records in DB cache, for example. Contrary, random keys would constantly invalidate the cache unless all your data fits in memory.

ape4 5y ago

Isn't that a possible security issue. MACs used to be predictable but then became random.

jozvolskyef 5y ago
I presume you are referring to UUIDv4/1, which has 122 random bits. It is a common misconception that this is insecure. In reality, the UUIDv4/1 is just a way to encode 122 random bits, which is more than enough for most needs. The property of being practically unguessable comes from the random generator, not from the encoding. Secondly, whether or not being predictable is a problem depends on the use case. The keys used on this forum are predictable and it is not an issue.
lazide 5y ago
I’m pretty sure you mean ‘stable’ not predictable here re:MACs? The issue with using Mac addresses is it essentially leaked tracking information on the machine being used to generate the uuid - you could associate every ID it ever generated back to that same machine, correlate it to things like open WiFi AP logs, whatever. Which is pretty scary sometimes. Many OS’s now randomly generate a new MAC on every disconnect/connect for this reason, to at least give some privacy.

masklinn 5y ago

Random primary keys play hell on database indexes.

cratermoon 5y ago

https://en.wikipedia.org/wiki/Partial_sorting https://en.wikipedia.org/wiki/Partial_sorting

mrighele 5y ago

The linked RFC talks about this (it refers to UUIDv4, which is not much different from 128 random bits): " First, most of the existing UUID versions such as UUIDv4 have poor database index locality. Meaning new values created in succession are not close to each other in the index and thus require inserts to be performed at random locations. The negative performance effects of which on common structures used for this (B-tree and its variants) can be dramatic. As such newly inserted values SHOULD be time-ordered to address this."

LukeShu 5y ago
> UUIDv4, which is not much different from 128 random bits To quantify how different: UUIDv4 has 6 fixed bits and 122 random bits.
bob1029 5y ago
Note that this totally-random key behavior is actually highly desirable when using dynamic programming techniques such as with the Splay Tree. It makes it statistically impossible for the tree to fall into a degenerate state.
- pjscott 5y ago
  Splay trees aren't a dynamic programming thing (and aren't used in any database storage backends I know of). They are, however, conjectured to be no more than a constant factor slower than a dynamically optimal binary search tree. https://en.wikipedia.org/wiki/Optimal_binary_search_tree https://en.wikipedia.org/wiki/Optimal_binary_search_tree
  - bob1029 5y ago
    > Splay trees aren't a dynamic programming thing My mistake - I meant to write "dynamic optimality". As for the "not used in any database storage backends", I have personally started experimenting with them due to higher-order effects they can provide relative to their optimization technique. The fact that the most recently accessed node is always at the root also means that incremental tree updates are well-bounded in terms of # of nodes that would need to be rewritten to disk. This allows for much more efficient usage of storage-friendly things like append-only log structures.

gumby 5y ago

That is addressed in the introduction -- random access inserts (i.e. specularity) can be quite inefficient depending on your backing store.

jandrewrogers 5y ago

There are two issues not mentioned in the other comments with a random 128-bit UUID in real systems, both related to data scale: - They defeat data compression, which is an integral part of many database engines these days for both performance and scalability reasons. - For some very large systems, there is a UUID collision tail risk that while small is large enough to be plausible.

neur4lnet 5y ago
Its compression a legitimate concern for primary keys?
- bob1029 5y ago
  If you are getting good compression on your primary keys, this may be cause for alarm. These should be high-entropy items.
  - jandrewrogers 5y ago
    The sole constraint on a primary key is that it is unique. Even in distributed systems, deterministically unique keys are almost always much more compressible than probabilistically unique keys, which is a double win. Should you desire a high-entropy key, e.g. for hash tables or security, this can be trivially derived from the low-entropy key while still guaranteeing deterministic uniqueness. Compressible primary keys are superior in every way.
- jandrewrogers 5y ago
  Definitely, I've run into this problem many times. UUIDs are pretty bulky data types in database terms, usually larger than most other types in a typical table on average and possibly larger than rest of the row after including the index overhead, which creates cache pressure. Logical columns in a table are commonly stored physically as a vector, of UUIDs in this case, expressly for the purpose of compressing the representation. This saves both disk cache and CPU cache. For queries, the benefit of scanning compressed vectors is that it reduces the average number of page faults per query, which is one of the major bottlenecks in databases. Also, some data models (think graphs) tend to be not much more than giant collections of primary keys. Using the smallest primary key data type that will satisfy the requirements of the data model is a standard performance optimization in databases. It is not uncommon for the UUID that the user sees to be derived from a stored primary key that is a 32-bit or 64-bit integer.

orf 5y ago

Imagine you’re not using a storage platform that supports that access pattern. Think S3, DynamoDB or even a directory of files. Being able to encode your sort key in your primary key is a pretty nice property.

datavirtue 5y ago
Hmmm...Now I'm wondering why I never bothered to prepend a timestamp to a GUID.
- orf 5y ago
  Because then it wouldn’t be a UUID in a format that other systems might expect or work more efficiently with.

halfmatthalfcat 5y ago

Using the uuid as a PK do to cursor based pagination for one.

parhamn 5y ago

it depends what "created_at" means, if it means "persisted_at" then they're also a bit different because these sorts of UUIDs are generated before being persisted (often long before for offline-and sync systems).

dheera 5y ago

Searching records and returning the results time-sorted in O(n) time instead of O(n log n) time.

deleted 5y ago

[deleted]

junon 5y ago

FWIW the linked RFC's "Background" section is really easy to understand even for people who aren't well versed in dist-sys concepts. I suggest giving it a read - it's quite well written.

runeks 5y ago

Follow-up question: What are the advantages of sortable UUIDs with embedded timestamps over having an auto-incrementing id column, a created_at column, and using the composite primary key (created_at, id)?

rswail 5y ago
Because an auto-incrementing id column has to be coordinated between processes that are writing to the database. That means allocating ids in blocks that are large enough that processes aren't blocked in getting an allocation, but they still need to request a block to maintain writing. That sequence allocation needs to be ACID as well, so that there is no chance of any allocation being repeated.