11 ms·

Show HN: 128-bit, roughly-ordered, URL-safe UUIDs

205 points by amzans 6y ago

abhishekjha 6y ago
Query : For people who recommend UUIDs as a unique identifier in a distributed sytem, does the above satisfy the need? In the SO answer[0] uuid v4 is being recommended but that is the most random version of uuid. Isn't that going to hurt the b-tree performance by having a very high fanout? How does it help the primary index? [0] : https://stackoverflow.com/questions/33274291/postgresql-uuid-or-sequence-for-primary-key https://stackoverflow.com/questions/33274291/postgresql-uuid... EDIT : Apologies. I meant low fanout. What I meant was that you need something ordered to have a better organised b-tree node. If all values are random, each node will have a lot of children, increasing the search space. It might turn into Linked list in the worst case scenario.
- tomsmeding 6y ago
  Excuse my possible ignorance, but how is more entropy in a primary key going to hurt index performance? The fanout in a b-tree is completely in control of the database, and not dependent at all on properties of the data — apart, of course, from the size of the data, since typically the node fanout is precisely the number of fields that fit in one disk page. Randomness does not influence the size of a UUID on disk.
  - rapidlua 6y ago
    With random keys updates are going to touch way more pages than with sequential ones. It increases IO due to more dirty buffers and journaling.
    - tomsmeding 6y ago
      Point taken. Quite true.
      - Tostino 6y ago
        More reading on this for Postgres: https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/ https://www.2ndquadrant.com/en/blog/sequential-uuid-generato...
- mytailorisrich 6y ago
  > Isn't that going to hurt the b-tree performance by having a very high fanout? High fanout helps minimise the depth of the tree and therefore helps performance as it minimises the number of nodes to check.
  - abhishekjha 6y ago
    Sorry, I meant low fan out, as in a b-tree node will end up have having a lot of singular valued children ultimately degrading to linked list.
    - mytailorisrich 6y ago
      I think random binary keys are pretty good for B trees because they also lead to shallow depth and a balanced tree instead of potentially degrading to a linked list.
- StreamBright 6y ago
  We moved away from UUIDs for different reasons. It is hard to work with UUIDs when multiple entities have them. You do not know if you are looking at a user or a group if both is just a UUID. We created our own IDs with prefixes and using base58 encoding for the random part, for example: user-AhnPpn7CbbwPykmux11LJ39Jk. It has the same amount of randomness in it and we can understand what we are looking at.
  - DJBunnies 6y ago
    Uuid v5 is namespaced.
    - skissane 6y ago
      But given a v3 or v5 UUID, you can’t tell what namespace it belongs to. Both are one way functions from (namespace,name) -> uuid. The gp is asking for a way to tell user uuid apart from group uuid just by looking at the uuid. That is actually possible with the v2 uuids used with DCE. But, since just about nobody uses DCE any more, just about nobody uses v2 uuids either
      - pbronez 6y ago
        What is DCE?
        skissane 6y ago
        https://en.m.wikipedia.org/wiki/Distributed_Computing_Environment https://en.m.wikipedia.org/wiki/Distributed_Computing_Enviro...
  - globular-toast 6y ago
    Why would you ever be in a situation where you have a UUID but don't know what it refers to?
    - seppel 6y ago
sltkr 6y ago
This isn't strictly speaking a UUID. It's just a 128-bit identifier. It's "compatible with UUID" only in the sense that both are 128 bits wide, but this scheme doesn't have the structure of a UUID. To summarize the scheme, a 128-bit id is generated by concatenating: - 48 bits timestamp (milliseconds since UNIX epoch) - 80 bits of random data These ids have the property that they're ordered by generation time (ids generated at the same millisecond are ordered randomly). The result can then be encoded in base 16 or base 62 to make it URL-compatible. By the way, encoding timestamps into an id is not always desirable. It has some privacy implications, since now you can tell from the id when the resource was created. If this corresponds with user activity (e.g. a user filling out a form or uploading an image) having this information encoded in a URL is possibly undesirable.
- skissane 6y ago
  You are talking about a v1 UUID. A random number is a valid v4 UUID, provided you set the version and variant bits to the correct value. A random 128-bit number won’t have those bits correctly set (except by chance). Set them, and you’ve made a valid v4 UUID
  - sltkr 6y ago
    As you say, you need to set certain bits to special values to encode a v4 UUID, leaving less than 128 bits for the payload, which means a random 128 bit number is not a valid UUID except by chance. Second, a v4 UUID should set all remaining bits randomly. Encoding a timestamp in some of the bits is not random. Sure, you could argue these could have been randomly generated by chance, so any such UUID is not invalid, strictly speaking. Still, a collection of these v4 UUIDs don't have the properties that you would expect of random UUIDs. As specificed, the scheme satisfies neither of these two requirements.
    - withinboredom 6y ago
      There’s always the expired v6 proposal: https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/ https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-...
sudhirj 6y ago
There’s a spec called ULID that’s pretty much this with default base32 encoding https://github.com/ulid/spec https://github.com/ulid/spec I’ve also worked on a UUID-ULID bridge for Go https://github.com/sudhirj/uulid.go https://github.com/sudhirj/uulid.go And seeing as this is just 128 bits it’s quite easy to move seamlessly between formats and representations. I’ve found this concept especially useful in nosql stores like DynamoDB, where using a ULID primary key makes objects time sortable automatically. It’s also quite easy to query for items by zeroing out the random component and setting only the time stamp bytes.
- mfollert 6y ago
  This is super useful and exactly what I need for a current project. Thanks you for that hint!
- mgkimsal 6y ago
  I've been using ULID on a couple projects. In one case, we're trying to convert an existing project to use them, and... it's a bit of a pain, but it's not ULID's fault as much as just... changing primary keys all over the place is time consuming and not simple. The biggest pushback (and it's not a terribly big one, imo) I've read on ULID is that the time portion is sold as 'sortable' but is 'only ms-level resolution'. Apparently the critics I was initially reading on ULID needed sub millisecond accuracy, and somehow thought this made ULIDs bad. Seemed a non-useful criticism, as needing that level of time granularity isn't a day to day issue for most people, but might be something to be aware of if the idea of overloading one field with multiple uses is a requirement you have.
  - techdragon 6y ago
    If you’re an edge case you’re an edge case. It’s frustrating when people start assuming their use case is normal without any considerations of the wider world. Sub millisecond precision sorting of high speed database inserts is hardly a normal requirement. At that point even the size of your transaction can matter (depending on the database) and you have to start asking questions like do I want ordering by the time the transaction starts or the time it ends? And if your loading existing data from other sources and care about date ordering you should just be using the a dedicated column with the database appropriate time/date time/time stamp field anyway.
calpaterson 6y ago
One of the issues this is trying to resolve is that v4 UUIDs wholly random nature makes them less than brilliant in the b-trees that SQL databases use for indices (I am actually not sure how much that really matters in practice for most projects). However, Postgres has an alternate index implementation that uses a hash function. It is crash-safe now (previously wasn't) but you still can't use it to enforce a unique constraint. If you can use that, I suspect it might resolve the problem and would be easier than switching UUID generation algorithm.
- withinboredom 6y ago
  It’s a shame v6 uuids didn’t become a thing[1]. It’s the entire reason they were invented. 1: https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/ https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-...
caleblloyd 6y ago
This approach has become my preferred way of generating IDs for database rows. It is relatively space efficient and doesn't require a round trip to the database to generate an ID like auto increment does. While working on a C# implementation for MySQL and we found that when the DB uses Little Endian Binary that the GUID must be reversed to store in order: https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCore.MySql/blob/bd1f8369e73a2555eef989e0c4503d84a5180fa0/src/EFCore.MySql/ValueGeneration/Internal/MySqlSequentialGuidValueGenerator.cs https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCo...
- abhishekjha 6y ago
  Does random UUID work as well as lets say an ordered integer id or ordered uuid? I thought the ids should have a definite order(not necessarily sequential) so that a binary search can be performed on the primary index. Similar for b-trees.
  - masklinn 6y ago
    Random uuids are perfectly ordered, there’s no issue looking up a single record by uuid. The problems are that they’re scattered during reads and writes, and will require updating old pages.
    - kevincox 6y ago
      Note that scattering can actually be beneficial if you have too much load for a single node when the data is hot. Of course you can solve this with weird sharding such as sharding on the least significant byte.
      - SigmundA 6y ago
        Seems like this point is not understood very well by many. Ordered keys can create hot spots on insert and read, this can be good or bad depending on backend.
        6y ago
Ellipsis753 6y ago
I'd worry a bit about the chance of collisions. They correctly state you can generate 50 million of them per millisecond with only a one in a billion chance of a collision (per millisecond). Unfortunately this means the chance of a collision in a year is 99.999999999998% which isn't great! (I think they've given too many bits to the timestamp.) Also, the uuid format it creates isn't a valid uuid which is a pity. If you want to have "only" a one in a billion chance of a collision a year, you can only generate about 300 a millisecond.
- doersino 6y ago
  > Unfortunately this means the chance of a collision in a year is 99.999999999998% which isn't great! How was this computed? My intuition begs to differ.
  - jychang 6y ago
    There are 31,536,000,000 milliseconds in a year. If you do (1-1E-9)^3.1536E10, you get a 2E-14 chance of no collision in a year.
    - hoseja 6y ago
      I think the presumption is you will not be generating 50 million of them each millisecond.
      - alpaca128 6y ago
        Which is a pretty safe assumption, considering just generating those 128bits 50 million times a millisecond results in over 20 million TB of data in a year. I think it's safe to say this is not a common scenario.
  - onetoo 6y ago
    Probability of no collision in a single millisecond: p_1 = 999999999/1000000000 Milliseconds in a year: t = 1000 * 60 * 60 * 24 * 365 Probability of no collision happening for every millisecond of a year: p_2 = p_1^t Probability of a collision happening for at least one millisecond of a year: p_3 = 1 - p_2 https://www.wolframalpha.com/input/?i=1+-+%28999999999%2F1000000000%29%5E%281000+*+60+*+60+*+24+*+365%29 https://www.wolframalpha.com/input/?i=1+-+%28999999999%2F100...
rafaelturk 6y ago
This is really nice, anyone aware of a NodeJs alternative?
- mgkimsal 6y ago
  https://github.com/ulid/spec https://github.com/ulid/spec isn't timeflake, but is a good spec, and there are implementations in multiple languages. there are 2 listed for js. https://github.com/aarondcohen/id128 https://github.com/aarondcohen/id128 and https://github.com/ulid/javascript https://github.com/ulid/javascript
- audionerd 6y ago
  @thi.ng/ksuid https://github.com/thi-ng/umbrella/tree/develop/packages/ksuid https://github.com/thi-ng/umbrella/tree/develop/packages/ksu...
sparkling 6y ago
> Roughly ordered (K-sortable), incremental timestamp in most significant bits enables faster indexing and less fragmentation on database indices (vs UUID v1/v4). What does this mean for database performance in simple CRUD scenarios?
- theta_d 6y ago
  Using an ordered ID prevents index fragmentation. Inserts will be slower and ultimately so will reads. In a database like MS SQL Server this is especially true since data is physically stored on disk based on the clustering key which is the PK by default.
hankchinaski 6y ago
not quite sure why the requirement of being compatible with the UUID 128-bit representation. i personally try to use KSUID (160bit) when possible and can’t see any downside so far
- deleted 6y ago
  [deleted]
- Tostino 6y ago
  Being 128-bits allows you to utilize the same database/object types as UUID. That's the main benefit IMO. I couldn't stick a KSUID into my Postgres UUID column, i'd have to write a new data type to store that.
chrisacky 6y ago
Can someone expand on this please. > They should be random, but roughly-ordered over time so that your MySQL/Postgres indices stay fast and efficient as the dataset grows. I'm currently facing an issue where the chosen uuid format was v4. From my understanding this is the least preferable because it's true random, which causes hell for mysql indices. What I don't quite udnerstand however, is why is sorted random better if I'm using an index in both cases? I'd like to know what I should be doing and if there is a way to move/migrate if possible
- kijin 6y ago
  In MySQL and some other database systems, primary keys are clustered indexes. A clustered index defines the order in which data is physically stored on disk. If you have an auto-incrementing primary key like most sane people do, new rows will be sorted to the very end of the table. Inserting data to this table essentially becomes an append-only operation, which is very fast. On the other hand, inserting random values all over the place is like inserting data in the middle of a file and pushing back everything that comes afterward, over and over again. Even on modern SSD's, this is much slower than simply appending data to the end of a file. For best performance, your primary keys should be as close as possible to auto-incrementing integers. In other words, each new value should be greater than all the values that currently exist in the table. Timestamps are quite useful for this purpose.
  - pas 6y ago
    This is an InnoDB thing for MySQL. (The old MyISAM was a simple append only thing with separate index file.)
- masklinn 6y ago
  > What I don't quite udnerstand however, is why is sorted random better if I'm using an index in both cases? Data locality. The default index in most RDBMS is a btree which is ordered and clustered so when you look up items in an index if they sort similarly they’ll be in the same index page(s) and thus cheaper to retrieve. For PKs that means when you go through your records it’s cheap to get siblings. When the ids are randomly distributed it’s way more expensive to add them because they get added at random positions (writes are scattered which is bad) and when you retrieve them you have to jump through the index at random loading a bunch of pages to get just one or two records from it. Things are even worse if the table itself is clustered after the PK because now your scattered index is also ducking with your actual data reads.
deleted 6y ago
[deleted]
varispeed 6y ago
This is assuming that the time is linearly increasing, but what if you have a service running on a fast moving object between planets or in alternative dimension where time is not linear or not monotonic?
solicode 6y ago
I like ordered UUIDs, but if you care about 100% strict and accurate ordering you need to be careful about generating them in app code vs. on the DB side. With the former + using multiple app servers, server clock drift can become an issue. Which is why I still generate my ordered UUIDs on my Postgres server. It means writing some funky PL/pgSQL (or however you decide to do it... I think you can run Python too), but it gets the job done. I wish ordered UUIDs were built-in to more DBs natively. I remember seeing UUIDv6 being proposed, but I don't know if/when that will be standardised.
- httgp 6y ago
  How does one generate ordered UUIDs right on the PostgreSQL server?
  - solicode 6y ago
    There's probably a nicer way (or more performant at least), but I created a function that uses the built-in `uuid_generate_v1mc` and then reverse the order of the time component so that high values come first.
  - Tostino 6y ago
    Use this: https://github.com/tvondra/sequential-uuids https://github.com/tvondra/sequential-uuids If you cannot install extensions, I just wrote a PL/PGSQL implementation for the time-based generator I could share.
    - Sytten 6y ago
      Please do I have been looking for that. Posting it in the repo would help a few people k am guessing.
      - Tostino 6y ago
        https://gist.github.com/Tostino/ca104bff40e704b6db70b9af492664ef https://gist.github.com/Tostino/ca104bff40e704b6db70b9af4926... Posted it to the repo as well.
techdragon 6y ago
The biggest thing I can highlight after having used Standard UUIDs and heavily using ULID values including building my own library and testing compatibility and behavioural compliance of the library with other database variants than the big 4 (MySQL, MS SQL, SQLite and PostgreSQL) ... is that no PK format should ever be considered suitable for all use cases its all about trade offs. If you care about the order of something you shouldn’t expect any PK to handle that alone, even auto-incremented integers will start to fail you once you have to scale your write workload horizontally. If there’s a property of your data that you want to be able to order it by then you just need to make a column of the appropriate data type and store it. If I had a nickel for every time someone has look at a schema and said something like “Do we really need this date for ordering? The table is already sorted by insert order...” I’d have a lot more nickels than I want.
m45t3r 6y ago
Datomic uses a similar approach by default. They called it squuid: https://docs.datomic.com/on-prem/identity.html#squuids https://docs.datomic.com/on-prem/identity.html#squuids
amzans 6y ago
For those interested, here's (IMO) a good explanation on why completely random UUIDs hurt performance, and can lead to database fragmentation issues down the road (on MySQL): https://www.percona.com/blog/2019/11/22/uuids-are-popular-but-bad-for-performance-lets-discuss/ https://www.percona.com/blog/2019/11/22/uuids-are-popular-bu... It's part of what Timeflake aims to solve, but there's plenty alternatives too depending on your exact requirements.
- ForHackernews 6y ago
  This is not universally true. It depends on the database engine and how its indexes are implemented.
  - amzans 6y ago
    Thanks, I updated the comment to mention that the link is in the context of MySQL's case.
  - fastball 6y ago
    Is this applicable to postgres?
    - calpaterson 6y ago
      It's applicable to the indexes that postgres uses. Postgres does not put rows in the heap in order of primary key so the issue is less serious than in innodb.
  - zerd 6y ago
    It's pretty much true for any B-tree based index. You could get around it by using a combined index on another timestamp value, but that's going to be a very large index. Or reduce it by partitioning by e.g. year-month. Even hash-based indices would be slightly impacted due to less locality.
- deleted 6y ago
  [deleted]
j-pb 6y ago
Have you considered using a 32 bit time value with second resolution? That way you still get sort-ability, you get 16 bit more entropy, fare better on 32 bit systems, and still get 130 years of usage, out of them. Also you actively discourage people from trying funny stuff like synchronisation and conflict resolution via the time component. Because 1ms "that sounds kinda good enough :?", while 1s "that'll never work!!!" Ammendment: Thinking about it. Using a 16bit timestamp prefix with second resolution and rollover should probably provide a good tradeoff between improving insertion performance (most expensive in terms of index touching), a 112 bit random value, and a dense usage of the timstamp field. It also allows you to do thing like "forgetting" old values, within a 18h timeframe.
- Tostino 6y ago
  I personally use: https://github.com/tvondra/sequential-uuids https://github.com/tvondra/sequential-uuids The time component resolution is configurable, and you can make it wrap around every so often, filling in gaps left by page splits, updates, deletes, etc.
  - j-pb 6y ago
    Nice! This is kinda what I had in mind, while writing that ammendum! Thanks for sharing :D
  - Sytten 6y ago
    Its just a bit annoying because it is a C extension and that can't be used in most managed DB in the cloud.
    - Tostino 6y ago
      I had to re-write the time based function from that extension in PL/PGSQL earlier in the week for someone on my team who couldn't work with the C extension: https://gist.github.com/Tostino/ca104bff40e704b6db70b9af492664ef https://gist.github.com/Tostino/ca104bff40e704b6db70b9af4926... This can be used in RDS, etc.
- 6y ago
advisedwang 6y ago
Just be careful if you use these as keys for a distributed system that is susceptible to hotspotting. GCP's Cloud Spanner [1] has this problem and has a good document explaining it. As always - understand what is going on in your stack and apply design with that in mind. There are no universals! [1] https://cloud.google.com/spanner/docs/schema-design#primary-key-prevent-hotspots https://cloud.google.com/spanner/docs/schema-design#primary-...
- crescentfresh 6y ago
  I had to pause when they use the term "anti-pattern". It may be an anti-pattern for cloud spanner but it's not an anti-pattern in other distributed systems, for example cassandra.
  - zug_zug 6y ago
    Right. This spanner thing is new to me, but looking at it, I don't see why spanner doesn't/couldn't shard by modulo / checksum to reduce this risk. And I think other systems do
    - electricshampo1 6y ago
      It shards it this way (by primary key ranges) to support efficient range scans.
      - zug_zug 6y ago
        Good point. I guess it would be cool if you could choose the sharding method per-table. I haven't put too much thought into this, but off the top of my head I can imagine a number of different methods suitable for different situations.
  - majormajor 6y ago
    The very next word after "anti-pattern" is if. "The following table definition that uses a timestamp-based primary key as the first key part is an anti-pattern if the table will see a high rate of insertion:" Once your data gets big enough there's no easy one-size-fits-all. You gotta look at how you're going to be using the system.
Dylan16807 6y ago
Base62? That seems strictly worse than base64 to me. Why that choice?
- zamalek 6y ago
  The two (or three if you retain padding) additional characters are symbols and can cause issues in many places. Base64-url and other variants exist for this reason, but there is no single base64 that works everywhere.
  - Dylan16807 6y ago
    There's no "single base62 that works everywhere" either. So while there's valid criticism to be had of base64, I still don't see how this choice is better.
- cuspycode 6y ago
  62 is the number of letters and digits in ASCII, so it's the most compact encoding that doesn't need special punctuation characters (which aren't always safe to use).
  - Dylan16807 6y ago
    How many situations don't let you use _ and -? URLs certainly do.
josephernest 6y ago
Just to see the big picture, what are the main differences between this and Snowflake, or ULID (https://github.com/ulid/spec https://github.com/ulid/spec)?
mleonhard 6y ago
I filed an issue on the project, "Point out the privacy risks of timestamps in object IDs" [0]. ---- Non-random object IDs have privacy issues. Developers need to learn about these before they choose to use non-random IDs over simple random IDs. How about adding a PRIVACY section to the readme? Timeflake encodes the precise time that a user created an object. Timestamps in IDs can reveal: User timezone. Geographic location: If the client software creates multiple associated IDs at the same time (like an article and embedded media), then the differences in timestamps of the IDs can reveal the latency of the client's network connection to the server. This reveals user geographic location. This can also happen if the client creates a single ID and the server adds an additional timestamp to the object. User identity (de-anonymizing) - Most Android apps include Google's libraries for working with push notifications. And some iOS apps that use Google Cloud services also load the libraries. These Google libraries automatically load Google Analytics [1] which records the names of every screen the users view in the app, and sends them to Google. So Google knows that userN switched from screen "New Post" to screen "Published Post" at time K. - Some ISPs record and sell user behavior data. For example, SAP knows [2] that userN made a request to appM's API at time K. - Even if the posting app does not share its user behavior data with third-parties, the user could post and then immediately switch to an app that does share user behavior data. This provides data points like "userN stopped using an app that does not record analytics at time K". - Operating Systems (Android [3], Windows [4], macOS [5]) send user behavior data to their respective companies. - Browsers and Browser Extensions send user behavior data to many companies. Data points like "userN visited a URL at example.com at time K" can end up in many databases and sold. - Posting times combined with traffic analysis can perfectly de-anonymize users. How long the user took to write the post. This can happen if the app creates the ID when the user starts editing the post and also shares a timestamp of the publication or save time. Whether or not the user edited the post after posting it. This can happen if the posts's displayed time doesn't match the timestamp in the ID. Whether or not the user prepared the post in advance and set it to post automatically. If the timestamp is very close to a round numbered time like 21:00:00, it was likely posted automatically. If the posting platform does not provide such functionality, then the user must be using some third-party software or custom software to do it. This information can help de-anonymize the user. ---- [0] https://github.com/anthonynsimon/timeflake/issues/3 https://github.com/anthonynsimon/timeflake/issues/3 [1] https://firebase.google.com/docs/cloud-messaging/android/client#prevent-auto-init https://firebase.google.com/docs/cloud-messaging/android/cli... [2] https://www.eff.org/deeplinks/2017/03/five-creepy-things-your-isp-could-do-if-congress-repeals-fccs-privacy-protections https://www.eff.org/deeplinks/2017/03/five-creepy-things-you... [3] https://digitalcontentnext.org/wp-content/uploads/2018/08/DCN-Google-Data-Collection-Paper.pdf https://digitalcontentnext.org/wp-content/uploads/2018/08/DC... [4] https://www.eff.org/deeplinks/2016/08/windows-10-microsoft-blatantly-disregards-user-choice-and-privacy-deep-dive https://www.eff.org/deeplinks/2016/08/windows-10-microsoft-b... [5] https://www.eff.org/deeplinks/2020/11/macos-leaks-application-usage-forces-apple-make-hard-decisions https://www.eff.org/deeplinks/2020/11/macos-leaks-applicatio...
epakai 6y ago
UUIDs in URLs reminds me of dakboard's use of UUIDs for accessing their user customizable displays. There isn't any auth, just guess the right $uuid in dakboard.com/screen/uuid/$uuid and you've got access to whatever info people put on their board (lots of calendars). You can find several (mostly public churches/community/sports) just by googling the base url.
qwerty456127 6y ago
IMHO for small projects where entities are generated in response to a manual action of a user (i.e. relatively rare - the chance 2 users on different machines do it in exactly same moment is very low) or everything is done in one thread on one machine a nanosecond/microsecond timestamp makes a practical unique identifier.
Too 6y ago
How does this compare to Mongodbs ObjectId? They have roughly the same structure of timestamp+random but an additional incrementing counter-field at the end, sec-resolution rather than ms, and some drivers use something host-dependent in the random component. 96bit total.

205 points by amzans 6y ago

Query : For people who recommend UUIDs as a unique identifier in a distributed sytem, does the above satisfy the need? In the SO answer[0] uuid v4 is being recommended but that is the most random version of uuid. Isn't that going to hurt the b-tree performance by having a very high fanout? How does it help the primary index? [0] : https://stackoverflow.com/questions/33274291/postgresql-uuid-or-sequence-for-primary-key https://stackoverflow.com/questions/33274291/postgresql-uuid... EDIT : Apologies. I meant low fanout. What I meant was that you need something ordered to have a better organised b-tree node. If all values are random, each node will have a lot of children, increasing the search space. It might turn into Linked list in the worst case scenario.

tomsmeding 6y ago
Excuse my possible ignorance, but how is more entropy in a primary key going to hurt index performance? The fanout in a b-tree is completely in control of the database, and not dependent at all on properties of the data — apart, of course, from the size of the data, since typically the node fanout is precisely the number of fields that fit in one disk page. Randomness does not influence the size of a UUID on disk.
- rapidlua 6y ago
  With random keys updates are going to touch way more pages than with sequential ones. It increases IO due to more dirty buffers and journaling.
  - tomsmeding 6y ago
    Point taken. Quite true.
    - Tostino 6y ago
      More reading on this for Postgres: https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/ https://www.2ndquadrant.com/en/blog/sequential-uuid-generato...
mytailorisrich 6y ago
> Isn't that going to hurt the b-tree performance by having a very high fanout? High fanout helps minimise the depth of the tree and therefore helps performance as it minimises the number of nodes to check.
- abhishekjha 6y ago
  Sorry, I meant low fan out, as in a b-tree node will end up have having a lot of singular valued children ultimately degrading to linked list.
  - mytailorisrich 6y ago
    I think random binary keys are pretty good for B trees because they also lead to shallow depth and a balanced tree instead of potentially degrading to a linked list.
StreamBright 6y ago
We moved away from UUIDs for different reasons. It is hard to work with UUIDs when multiple entities have them. You do not know if you are looking at a user or a group if both is just a UUID. We created our own IDs with prefixes and using base58 encoding for the random part, for example: user-AhnPpn7CbbwPykmux11LJ39Jk. It has the same amount of randomness in it and we can understand what we are looking at.
- DJBunnies 6y ago
  Uuid v5 is namespaced.
  - skissane 6y ago
    But given a v3 or v5 UUID, you can’t tell what namespace it belongs to. Both are one way functions from (namespace,name) -> uuid. The gp is asking for a way to tell user uuid apart from group uuid just by looking at the uuid. That is actually possible with the v2 uuids used with DCE. But, since just about nobody uses DCE any more, just about nobody uses v2 uuids either
    - pbronez 6y ago
      What is DCE?
      - skissane 6y ago
        https://en.m.wikipedia.org/wiki/Distributed_Computing_Environment https://en.m.wikipedia.org/wiki/Distributed_Computing_Enviro...
- globular-toast 6y ago
  Why would you ever be in a situation where you have a UUID but don't know what it refers to?
  - seppel 6y ago

sltkr 6y ago

This isn't strictly speaking a UUID. It's just a 128-bit identifier. It's "compatible with UUID" only in the sense that both are 128 bits wide, but this scheme doesn't have the structure of a UUID. To summarize the scheme, a 128-bit id is generated by concatenating: - 48 bits timestamp (milliseconds since UNIX epoch) - 80 bits of random data These ids have the property that they're ordered by generation time (ids generated at the same millisecond are ordered randomly). The result can then be encoded in base 16 or base 62 to make it URL-compatible. By the way, encoding timestamps into an id is not always desirable. It has some privacy implications, since now you can tell from the id when the resource was created. If this corresponds with user activity (e.g. a user filling out a form or uploading an image) having this information encoded in a URL is possibly undesirable.

skissane 6y ago
You are talking about a v1 UUID. A random number is a valid v4 UUID, provided you set the version and variant bits to the correct value. A random 128-bit number won’t have those bits correctly set (except by chance). Set them, and you’ve made a valid v4 UUID
- sltkr 6y ago
  As you say, you need to set certain bits to special values to encode a v4 UUID, leaving less than 128 bits for the payload, which means a random 128 bit number is not a valid UUID except by chance. Second, a v4 UUID should set all remaining bits randomly. Encoding a timestamp in some of the bits is not random. Sure, you could argue these could have been randomly generated by chance, so any such UUID is not invalid, strictly speaking. Still, a collection of these v4 UUIDs don't have the properties that you would expect of random UUIDs. As specificed, the scheme satisfies neither of these two requirements.
  - withinboredom 6y ago
    There’s always the expired v6 proposal: https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/ https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-...

sudhirj 6y ago

There’s a spec called ULID that’s pretty much this with default base32 encoding https://github.com/ulid/spec https://github.com/ulid/spec I’ve also worked on a UUID-ULID bridge for Go https://github.com/sudhirj/uulid.go https://github.com/sudhirj/uulid.go And seeing as this is just 128 bits it’s quite easy to move seamlessly between formats and representations. I’ve found this concept especially useful in nosql stores like DynamoDB, where using a ULID primary key makes objects time sortable automatically. It’s also quite easy to query for items by zeroing out the random component and setting only the time stamp bytes.

mfollert 6y ago
This is super useful and exactly what I need for a current project. Thanks you for that hint!
mgkimsal 6y ago
I've been using ULID on a couple projects. In one case, we're trying to convert an existing project to use them, and... it's a bit of a pain, but it's not ULID's fault as much as just... changing primary keys all over the place is time consuming and not simple. The biggest pushback (and it's not a terribly big one, imo) I've read on ULID is that the time portion is sold as 'sortable' but is 'only ms-level resolution'. Apparently the critics I was initially reading on ULID needed sub millisecond accuracy, and somehow thought this made ULIDs bad. Seemed a non-useful criticism, as needing that level of time granularity isn't a day to day issue for most people, but might be something to be aware of if the idea of overloading one field with multiple uses is a requirement you have.
- techdragon 6y ago
  If you’re an edge case you’re an edge case. It’s frustrating when people start assuming their use case is normal without any considerations of the wider world. Sub millisecond precision sorting of high speed database inserts is hardly a normal requirement. At that point even the size of your transaction can matter (depending on the database) and you have to start asking questions like do I want ordering by the time the transaction starts or the time it ends? And if your loading existing data from other sources and care about date ordering you should just be using the a dedicated column with the database appropriate time/date time/time stamp field anyway.

calpaterson 6y ago

One of the issues this is trying to resolve is that v4 UUIDs wholly random nature makes them less than brilliant in the b-trees that SQL databases use for indices (I am actually not sure how much that really matters in practice for most projects). However, Postgres has an alternate index implementation that uses a hash function. It is crash-safe now (previously wasn't) but you still can't use it to enforce a unique constraint. If you can use that, I suspect it might resolve the problem and would be easier than switching UUID generation algorithm.

withinboredom 6y ago
It’s a shame v6 uuids didn’t become a thing[1]. It’s the entire reason they were invented. 1: https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/ https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-...

caleblloyd 6y ago

This approach has become my preferred way of generating IDs for database rows. It is relatively space efficient and doesn't require a round trip to the database to generate an ID like auto increment does. While working on a C# implementation for MySQL and we found that when the DB uses Little Endian Binary that the GUID must be reversed to store in order: https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCore.MySql/blob/bd1f8369e73a2555eef989e0c4503d84a5180fa0/src/EFCore.MySql/ValueGeneration/Internal/MySqlSequentialGuidValueGenerator.cs https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCo...

abhishekjha 6y ago
Does random UUID work as well as lets say an ordered integer id or ordered uuid? I thought the ids should have a definite order(not necessarily sequential) so that a binary search can be performed on the primary index. Similar for b-trees.
- masklinn 6y ago
  Random uuids are perfectly ordered, there’s no issue looking up a single record by uuid. The problems are that they’re scattered during reads and writes, and will require updating old pages.
  - kevincox 6y ago
    Note that scattering can actually be beneficial if you have too much load for a single node when the data is hot. Of course you can solve this with weird sharding such as sharding on the least significant byte.
    - SigmundA 6y ago
      Seems like this point is not understood very well by many. Ordered keys can create hot spots on insert and read, this can be good or bad depending on backend.
      - 6y ago

Ellipsis753 6y ago

I'd worry a bit about the chance of collisions. They correctly state you can generate 50 million of them per millisecond with only a one in a billion chance of a collision (per millisecond). Unfortunately this means the chance of a collision in a year is 99.999999999998% which isn't great! (I think they've given too many bits to the timestamp.) Also, the uuid format it creates isn't a valid uuid which is a pity. If you want to have "only" a one in a billion chance of a collision a year, you can only generate about 300 a millisecond.

doersino 6y ago
> Unfortunately this means the chance of a collision in a year is 99.999999999998% which isn't great! How was this computed? My intuition begs to differ.
- jychang 6y ago
  There are 31,536,000,000 milliseconds in a year. If you do (1-1E-9)^3.1536E10, you get a 2E-14 chance of no collision in a year.
  - hoseja 6y ago
    I think the presumption is you will not be generating 50 million of them each millisecond.
    - alpaca128 6y ago
      Which is a pretty safe assumption, considering just generating those 128bits 50 million times a millisecond results in over 20 million TB of data in a year. I think it's safe to say this is not a common scenario.
- onetoo 6y ago
  Probability of no collision in a single millisecond: p_1 = 999999999/1000000000 Milliseconds in a year: t = 1000 * 60 * 60 * 24 * 365 Probability of no collision happening for every millisecond of a year: p_2 = p_1^t Probability of a collision happening for at least one millisecond of a year: p_3 = 1 - p_2 https://www.wolframalpha.com/input/?i=1+-+%28999999999%2F1000000000%29%5E%281000+*+60+*+60+*+24+*+365%29 https://www.wolframalpha.com/input/?i=1+-+%28999999999%2F100...

rafaelturk 6y ago

This is really nice, anyone aware of a NodeJs alternative?

mgkimsal 6y ago
https://github.com/ulid/spec https://github.com/ulid/spec isn't timeflake, but is a good spec, and there are implementations in multiple languages. there are 2 listed for js. https://github.com/aarondcohen/id128 https://github.com/aarondcohen/id128 and https://github.com/ulid/javascript https://github.com/ulid/javascript
audionerd 6y ago
@thi.ng/ksuid https://github.com/thi-ng/umbrella/tree/develop/packages/ksuid https://github.com/thi-ng/umbrella/tree/develop/packages/ksu...

sparkling 6y ago

> Roughly ordered (K-sortable), incremental timestamp in most significant bits enables faster indexing and less fragmentation on database indices (vs UUID v1/v4). What does this mean for database performance in simple CRUD scenarios?

theta_d 6y ago
Using an ordered ID prevents index fragmentation. Inserts will be slower and ultimately so will reads. In a database like MS SQL Server this is especially true since data is physically stored on disk based on the clustering key which is the PK by default.

hankchinaski 6y ago

not quite sure why the requirement of being compatible with the UUID 128-bit representation. i personally try to use KSUID (160bit) when possible and can’t see any downside so far

deleted 6y ago
[deleted]
Tostino 6y ago
Being 128-bits allows you to utilize the same database/object types as UUID. That's the main benefit IMO. I couldn't stick a KSUID into my Postgres UUID column, i'd have to write a new data type to store that.

chrisacky 6y ago

Can someone expand on this please. > They should be random, but roughly-ordered over time so that your MySQL/Postgres indices stay fast and efficient as the dataset grows. I'm currently facing an issue where the chosen uuid format was v4. From my understanding this is the least preferable because it's true random, which causes hell for mysql indices. What I don't quite udnerstand however, is why is sorted random better if I'm using an index in both cases? I'd like to know what I should be doing and if there is a way to move/migrate if possible

kijin 6y ago
In MySQL and some other database systems, primary keys are clustered indexes. A clustered index defines the order in which data is physically stored on disk. If you have an auto-incrementing primary key like most sane people do, new rows will be sorted to the very end of the table. Inserting data to this table essentially becomes an append-only operation, which is very fast. On the other hand, inserting random values all over the place is like inserting data in the middle of a file and pushing back everything that comes afterward, over and over again. Even on modern SSD's, this is much slower than simply appending data to the end of a file. For best performance, your primary keys should be as close as possible to auto-incrementing integers. In other words, each new value should be greater than all the values that currently exist in the table. Timestamps are quite useful for this purpose.
- pas 6y ago
  This is an InnoDB thing for MySQL. (The old MyISAM was a simple append only thing with separate index file.)
masklinn 6y ago
> What I don't quite udnerstand however, is why is sorted random better if I'm using an index in both cases? Data locality. The default index in most RDBMS is a btree which is ordered and clustered so when you look up items in an index if they sort similarly they’ll be in the same index page(s) and thus cheaper to retrieve. For PKs that means when you go through your records it’s cheap to get siblings. When the ids are randomly distributed it’s way more expensive to add them because they get added at random positions (writes are scattered which is bad) and when you retrieve them you have to jump through the index at random loading a bunch of pages to get just one or two records from it. Things are even worse if the table itself is clustered after the PK because now your scattered index is also ducking with your actual data reads.

deleted 6y ago

[deleted]

varispeed 6y ago

This is assuming that the time is linearly increasing, but what if you have a service running on a fast moving object between planets or in alternative dimension where time is not linear or not monotonic?

solicode 6y ago

I like ordered UUIDs, but if you care about 100% strict and accurate ordering you need to be careful about generating them in app code vs. on the DB side. With the former + using multiple app servers, server clock drift can become an issue. Which is why I still generate my ordered UUIDs on my Postgres server. It means writing some funky PL/pgSQL (or however you decide to do it... I think you can run Python too), but it gets the job done. I wish ordered UUIDs were built-in to more DBs natively. I remember seeing UUIDv6 being proposed, but I don't know if/when that will be standardised.

httgp 6y ago
How does one generate ordered UUIDs right on the PostgreSQL server?
- solicode 6y ago
  There's probably a nicer way (or more performant at least), but I created a function that uses the built-in `uuid_generate_v1mc` and then reverse the order of the time component so that high values come first.
- Tostino 6y ago
  Use this: https://github.com/tvondra/sequential-uuids https://github.com/tvondra/sequential-uuids If you cannot install extensions, I just wrote a PL/PGSQL implementation for the time-based generator I could share.
  - Sytten 6y ago
    Please do I have been looking for that. Posting it in the repo would help a few people k am guessing.
    - Tostino 6y ago
      https://gist.github.com/Tostino/ca104bff40e704b6db70b9af492664ef https://gist.github.com/Tostino/ca104bff40e704b6db70b9af4926... Posted it to the repo as well.

techdragon 6y ago

The biggest thing I can highlight after having used Standard UUIDs and heavily using ULID values including building my own library and testing compatibility and behavioural compliance of the library with other database variants than the big 4 (MySQL, MS SQL, SQLite and PostgreSQL) ... is that no PK format should ever be considered suitable for all use cases its all about trade offs. If you care about the order of something you shouldn’t expect any PK to handle that alone, even auto-incremented integers will start to fail you once you have to scale your write workload horizontally. If there’s a property of your data that you want to be able to order it by then you just need to make a column of the appropriate data type and store it. If I had a nickel for every time someone has look at a schema and said something like “Do we really need this date for ordering? The table is already sorted by insert order...” I’d have a lot more nickels than I want.

m45t3r 6y ago

Datomic uses a similar approach by default. They called it squuid: https://docs.datomic.com/on-prem/identity.html#squuids https://docs.datomic.com/on-prem/identity.html#squuids

amzans 6y ago

For those interested, here's (IMO) a good explanation on why completely random UUIDs hurt performance, and can lead to database fragmentation issues down the road (on MySQL): https://www.percona.com/blog/2019/11/22/uuids-are-popular-but-bad-for-performance-lets-discuss/ https://www.percona.com/blog/2019/11/22/uuids-are-popular-bu... It's part of what Timeflake aims to solve, but there's plenty alternatives too depending on your exact requirements.

ForHackernews 6y ago
This is not universally true. It depends on the database engine and how its indexes are implemented.
- amzans 6y ago
  Thanks, I updated the comment to mention that the link is in the context of MySQL's case.
- fastball 6y ago
  Is this applicable to postgres?
  - calpaterson 6y ago
    It's applicable to the indexes that postgres uses. Postgres does not put rows in the heap in order of primary key so the issue is less serious than in innodb.
- zerd 6y ago
  It's pretty much true for any B-tree based index. You could get around it by using a combined index on another timestamp value, but that's going to be a very large index. Or reduce it by partitioning by e.g. year-month. Even hash-based indices would be slightly impacted due to less locality.
deleted 6y ago
[deleted]

j-pb 6y ago

Have you considered using a 32 bit time value with second resolution? That way you still get sort-ability, you get 16 bit more entropy, fare better on 32 bit systems, and still get 130 years of usage, out of them. Also you actively discourage people from trying funny stuff like synchronisation and conflict resolution via the time component. Because 1ms "that sounds kinda good enough :?", while 1s "that'll never work!!!" Ammendment: Thinking about it. Using a 16bit timestamp prefix with second resolution and rollover should probably provide a good tradeoff between improving insertion performance (most expensive in terms of index touching), a 112 bit random value, and a dense usage of the timstamp field. It also allows you to do thing like "forgetting" old values, within a 18h timeframe.

Tostino 6y ago
I personally use: https://github.com/tvondra/sequential-uuids https://github.com/tvondra/sequential-uuids The time component resolution is configurable, and you can make it wrap around every so often, filling in gaps left by page splits, updates, deletes, etc.
- j-pb 6y ago
  Nice! This is kinda what I had in mind, while writing that ammendum! Thanks for sharing :D
- Sytten 6y ago
  Its just a bit annoying because it is a C extension and that can't be used in most managed DB in the cloud.
  - Tostino 6y ago
    I had to re-write the time based function from that extension in PL/PGSQL earlier in the week for someone on my team who couldn't work with the C extension: https://gist.github.com/Tostino/ca104bff40e704b6db70b9af492664ef https://gist.github.com/Tostino/ca104bff40e704b6db70b9af4926... This can be used in RDS, etc.
6y ago

advisedwang 6y ago

Just be careful if you use these as keys for a distributed system that is susceptible to hotspotting. GCP's Cloud Spanner [1] has this problem and has a good document explaining it. As always - understand what is going on in your stack and apply design with that in mind. There are no universals! [1] https://cloud.google.com/spanner/docs/schema-design#primary-key-prevent-hotspots https://cloud.google.com/spanner/docs/schema-design#primary-...

crescentfresh 6y ago
I had to pause when they use the term "anti-pattern". It may be an anti-pattern for cloud spanner but it's not an anti-pattern in other distributed systems, for example cassandra.
- zug_zug 6y ago
  Right. This spanner thing is new to me, but looking at it, I don't see why spanner doesn't/couldn't shard by modulo / checksum to reduce this risk. And I think other systems do
  - electricshampo1 6y ago
    It shards it this way (by primary key ranges) to support efficient range scans.
    - zug_zug 6y ago
      Good point. I guess it would be cool if you could choose the sharding method per-table. I haven't put too much thought into this, but off the top of my head I can imagine a number of different methods suitable for different situations.
- majormajor 6y ago
  The very next word after "anti-pattern" is if. "The following table definition that uses a timestamp-based primary key as the first key part is an anti-pattern if the table will see a high rate of insertion:" Once your data gets big enough there's no easy one-size-fits-all. You gotta look at how you're going to be using the system.

Dylan16807 6y ago

Base62? That seems strictly worse than base64 to me. Why that choice?

zamalek 6y ago
The two (or three if you retain padding) additional characters are symbols and can cause issues in many places. Base64-url and other variants exist for this reason, but there is no single base64 that works everywhere.
- Dylan16807 6y ago
  There's no "single base62 that works everywhere" either. So while there's valid criticism to be had of base64, I still don't see how this choice is better.
cuspycode 6y ago
62 is the number of letters and digits in ASCII, so it's the most compact encoding that doesn't need special punctuation characters (which aren't always safe to use).
- Dylan16807 6y ago
  How many situations don't let you use _ and -? URLs certainly do.

josephernest 6y ago

Just to see the big picture, what are the main differences between this and Snowflake, or ULID (https://github.com/ulid/spec https://github.com/ulid/spec)?

mleonhard 6y ago

I filed an issue on the project, "Point out the privacy risks of timestamps in object IDs" [0]. ---- Non-random object IDs have privacy issues. Developers need to learn about these before they choose to use non-random IDs over simple random IDs. How about adding a PRIVACY section to the readme? Timeflake encodes the precise time that a user created an object. Timestamps in IDs can reveal: User timezone. Geographic location: If the client software creates multiple associated IDs at the same time (like an article and embedded media), then the differences in timestamps of the IDs can reveal the latency of the client's network connection to the server. This reveals user geographic location. This can also happen if the client creates a single ID and the server adds an additional timestamp to the object. User identity (de-anonymizing) - Most Android apps include Google's libraries for working with push notifications. And some iOS apps that use Google Cloud services also load the libraries. These Google libraries automatically load Google Analytics [1] which records the names of every screen the users view in the app, and sends them to Google. So Google knows that userN switched from screen "New Post" to screen "Published Post" at time K. - Some ISPs record and sell user behavior data. For example, SAP knows [2] that userN made a request to appM's API at time K. - Even if the posting app does not share its user behavior data with third-parties, the user could post and then immediately switch to an app that does share user behavior data. This provides data points like "userN stopped using an app that does not record analytics at time K". - Operating Systems (Android [3], Windows [4], macOS [5]) send user behavior data to their respective companies. - Browsers and Browser Extensions send user behavior data to many companies. Data points like "userN visited a URL at example.com at time K" can end up in many databases and sold. - Posting times combined with traffic analysis can perfectly de-anonymize users. How long the user took to write the post. This can happen if the app creates the ID when the user starts editing the post and also shares a timestamp of the publication or save time. Whether or not the user edited the post after posting it. This can happen if the posts's displayed time doesn't match the timestamp in the ID. Whether or not the user prepared the post in advance and set it to post automatically. If the timestamp is very close to a round numbered time like 21:00:00, it was likely posted automatically. If the posting platform does not provide such functionality, then the user must be using some third-party software or custom software to do it. This information can help de-anonymize the user. ---- [0] https://github.com/anthonynsimon/timeflake/issues/3 https://github.com/anthonynsimon/timeflake/issues/3 [1] https://firebase.google.com/docs/cloud-messaging/android/client#prevent-auto-init https://firebase.google.com/docs/cloud-messaging/android/cli... [2] https://www.eff.org/deeplinks/2017/03/five-creepy-things-your-isp-could-do-if-congress-repeals-fccs-privacy-protections https://www.eff.org/deeplinks/2017/03/five-creepy-things-you... [3] https://digitalcontentnext.org/wp-content/uploads/2018/08/DCN-Google-Data-Collection-Paper.pdf https://digitalcontentnext.org/wp-content/uploads/2018/08/DC... [4] https://www.eff.org/deeplinks/2016/08/windows-10-microsoft-blatantly-disregards-user-choice-and-privacy-deep-dive https://www.eff.org/deeplinks/2016/08/windows-10-microsoft-b... [5] https://www.eff.org/deeplinks/2020/11/macos-leaks-application-usage-forces-apple-make-hard-decisions https://www.eff.org/deeplinks/2020/11/macos-leaks-applicatio...

epakai 6y ago

UUIDs in URLs reminds me of dakboard's use of UUIDs for accessing their user customizable displays. There isn't any auth, just guess the right $uuid in dakboard.com/screen/uuid/$uuid and you've got access to whatever info people put on their board (lots of calendars). You can find several (mostly public churches/community/sports) just by googling the base url.

qwerty456127 6y ago

IMHO for small projects where entities are generated in response to a manual action of a user (i.e. relatively rare - the chance 2 users on different machines do it in exactly same moment is very low) or everything is done in one thread on one machine a nanosecond/microsecond timestamp makes a practical unique identifier.

Too 6y ago

How does this compare to Mongodbs ObjectId? They have roughly the same structure of timestamp+random but an additional incrementing counter-field at the end, sec-resolution rather than ms, and some drivers use something host-dependent in the random component. 96bit total.