14 ms·

Sortable Collision-Free UUIDs

94 points by kpdemetriou 5y ago

dralley 5y ago
What is the difference between this and ULID? The latter is implemented in dozens of languages already, and many ULID libraries support conversion into UUID format. https://github.com/ulid/spec https://github.com/ulid/spec "Universally Unique Lexicographically Sortable Identifier"
natch 5y ago
Cool. I don’t see the readme warning about this, so: Use wisely and with full awareness. Revealing creation sequence can leak information which can be an issue in scenarios where such information might compromise security.
sroussey 5y ago
Is this a time swapped version of UUID v1? Like what MySQL will do when converting v1 uuid to binary for use in an index (when using the swap flag)?
pkulak 5y ago
Are they sortable as a string or as binary? Once you deploy something like this, that becomes important because you'll end up storing binary and string representations in different spots, unless you're _really_ careful (and DBs can insert way faster if you're always doing so near the end of the primary key sorting). And unless you use a totally custom string function, you can't have both, since base64 has letters before numbers, and ASCII is vice versa. It can be a real pain.
- munk-a 5y ago
  The examples use both letters and numbers in the ID composition so I would guess not - in all honesty though your question needs some clarification because the string representation of UUIDs is pretty fluid - there's the generally expressed version like `01324332-f66a-054a-76e4-fbdc7f772cd1` which appears to be what this generator favors - but for indexing UUIDs are usually considered to be their binary values so it's highly unlikely that a DB would see anything beyond a coincidental marginal benefit from using this package. It's hard to tell since the package says "sortable using UNIX sort" so it's not a format agnostic sorter - but it's also not conclusive whether the author meant the common human-readable strings can be sorted using UNIX sort or the binary strings can be sorted using UNIX sort.
- hamandcheese 5y ago
  I think if you store as hex, which is the traditional string representation of a UUID, then the string and binary representation will sort identically.
  - deleted 5y ago
    [deleted]
the_mitsuhiko 5y ago
4 byte timestamp is brave. int(time() - 16 * 10 ** 8)
- diath 5y ago
  Python's integers are unbounded.
  - the_mitsuhiko 5y ago
    The format only reserves for bytes
rekwah 5y ago
Looks similar to ULID[0] (I am the author of a popular python implementation[1]). It appears to have a similar constraint that two ID's generated within the same timestamp (ms, ns) have no strong guarantee of ordering. That might not be a deal breaker depending on your use case but something to consider. * https://github.com/ulid/spec https://github.com/ulid/spec * https://github.com/ahawker/ulid https://github.com/ahawker/ulid
laurent123456 5y ago
I think the issue with a lib like this is that people might use it, thinking they don't need the IDs to be secure... until they need to be. But by then plenty would have been generated, and a lot of code would rely on this sortable property. In fact, I don't see the point of a library like this, it's trying to encode two pieces of information into one string. Why is that? Why not encode geolocation or IP while they're at it. If some data is important, like the order, then a separate database column can easily be used and that would make for a much more durable and reliable solution.
- Jiejeing 5y ago
  I agree, to an extent, with your comment. But having sortable/chronological IDs on a single column is a really nice feature to have. Obviously, if you rely on the IDs to be unguessable/brute-forceable as part of your access control, then it is certainly bad to use such IDs. But I have not yet seen a case where I need both sortable and secure IDs. Being collision-free is what we want in a database context, and if it can hold some more information for the order, all the better.
- koolba 5y ago
  Sortable IDs have pleasant properties on insertion in traditional btree indexes as all the new values are on one edge of the tree. Truly random IDs end up with random I/O on the index tree. With a database like postgres with full page writes enabled, it can blow out quite quickly at scale.
  - sroussey 5y ago
    It’s worse with clustered indexes — all of the data experiences this issue, not just the index.
    - munk-a 5y ago
      At least in Postgres you have the advantage/disadvantage that real-time clustered tables aren't a feature on offer - so that re-clustering cost is eaten on a periodic basis whenever you invoke a re-cluster operation on the table in question. Additionally re-reading things closely I believe this package wouldn't benefit databases at all since the "sortable" form appears to be the common string representation while postgres will internally store UUIDs (at least in a UUID column) as their binary values - leading to indexing still being out of order unless you specify a ::TEXT casting.
swyx 5y ago
i have a loosely curated list of "State of the Art of UUIDs" here: https://github.com/sw-yx/uuid-list/ https://github.com/sw-yx/uuid-list/ just added FUUIDs, thanks OP
js2 5y ago
I'd advise UUID v6 over this which is at least an RFC 4122 extension. As coded, this isn't UUID compatible other than being 128 bits. http://gh.peabody.io/uuidv6/ http://gh.peabody.io/uuidv6/ Also some recent similar submissions: Timeflake is a 128-bit, roughly-ordered, URL-safe UUID. https://news.ycombinator.com/item?id=25870482 https://news.ycombinator.com/item?id=25870482 https://github.com/anthonynsimon/timeflake https://github.com/anthonynsimon/timeflake ULIDs: https://news.ycombinator.com/item?id=18768909 https://news.ycombinator.com/item?id=18768909 Sonyflake: https://news.ycombinator.com/item?id=25592325 https://news.ycombinator.com/item?id=25592325 KSUIDs (can't find any discussion here): https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid This comment lists other prior art: https://github.com/bradleypeabody/gouuidv6/issues/3 https://github.com/bradleypeabody/gouuidv6/issues/3
- ineedasername 5y ago
  Is there a reason or need to be UUID compatible? I honestly don't know. I use them in databases and know they're pretty safe to use when integrating data across multiple databases because collisions are astronomically unlikely, if implemented properly.
  - js2 5y ago
    So here's a real-world use case that having an RFC 4122 UUID was useful for me. I have a server which accepts reports and stores them in S3. For each new report, a v4 UUID is generated that that is used as the base of the S3 object name. This UUID becomes the report ID. An entire system has been built around the report ID, expecting a hex UUID. Recently, I needed to change how the objects are stored in S3 in order to partition them into multiple S3 prefixes. Instead of storing every object in a single place in the S3 bucket, I needed to do something like: "reports/%s/%s" % (report_id[:2], report_id[2:]) The issue was that I had one component that was writing the reports, and a second component reading the reports. And somehow, the reader needed to know whether a report was stored using the old path layout: "reports/%s" % (report_id,) Or the new path layout. I took advantage of the fact that RFC 4122 UUIDs have four bits set aside for version. After generating a v4 UUID, I update its version to 5. The reader can then check the report UUID version to know which path layout to use. Once all the reports stored using the old path layout expire, I can undo this hack. Of course, I could have made the reader try the new path layout, then fall back to the old path layout. Or I could have updated the entire system to have a better way of communicating the path layout, but that would've been less efficient or have meant touching a lot more code. I guess the moral of the story is: you never know when you're going to need to change something in a backwards compatible way, and having a few bits set aside even for something as simple as an object ID can be useful. I'm fortunate the UUID designers thought of that.
halfmatthalfcat 5y ago
I started looking into TSID/KSUID/ULID in order to support cursor based pagination schemes in GraphQL against non-integer based unique id fields (such as uuids or unique string ids). A couple of notable Java libs: https://github.com/f4b6a3/ulid-creator https://github.com/f4b6a3/ulid-creator https://github.com/f4b6a3/tsid-creator https://github.com/f4b6a3/tsid-creator https://github.com/akhawaja/ksuid https://github.com/akhawaja/ksuid
- cratermoon 5y ago
  Please don't use the akhawaja ksuid generator for Java unchanged. We used it at my last job until we realized 1. the Base62 code is not thread-safe (it uses a static StringBuilder) and more importantly 2. The epoch used is different from the standard, so the generated ksuid aren't portable. Use https://github.com/ksuid/ksuid https://github.com/ksuid/ksuid insteads
  - halfmatthalfcat 5y ago
    Good to know, thanks.
lilyball 5y ago
This really needs an explanation of how the “UUID” is generated. What properties does it have? How secure is it against attackers?
edoceo 5y ago
also this https://news.ycombinator.com/item?id=27004098 https://news.ycombinator.com/item?id=27004098 w3c distributed id spec/primer
ForHackernews 5y ago
Hold on, aren't UUIDv1 already generated based on a timestamp? What's the point of this?
punnerud 5y ago
The Python-code behind this: ts = int(time() - 16 \* 10 \*\* 8) return ts.to_bytes(4, "big") + os.urandom(12)
Lazare 5y ago
First, for something like this, the details matter a lot. How many bits of randomness is this, how many bits used for the timestamp, what's the format, why does it yield the advantages claimed, and most of all, how does it provide collision resistance? Is it using a MAC address (like UUID v1/v6) or a custom namespace (like UUID v5), or what? In this case...looking at the code.... It exposes two formats. Format 1: 4 bytes to store the number of seconds since a custom epoch of... Sep 13 2020 12:26:40, and 12 bytes of randomness. Puzzling choice. Format 2: 8 bytes to store the number of nanoseconds since the same custom epoch, and 8 bytes of randomness. And the collision resistance...doesn't exist at all; it's just relying on 12 (or 8) bytes of randomness and a time prefix. Which seems like it'll be totally fine in practice, but if you actually care about collisions (and in my experience, almost everyone who thinks they do really doesn't), this is unlikely to be an optimal choice. Functionally, I think this is closest to KSUIDs (https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid) which are also the result of combining a timestamp (with a custom epoch) and some randomness, and then concatenating them in a way which is not a valid UUID, will work efficiently as a DB index, and is extremely unlikely to collide. But KSUIDs are much more widely adopted and better documented.
- YetAnotherNick 5y ago
  Umm.. 12 bytes of randomness has 7*10^28 unique uuid per second. We generally take order of square root of this due to birthday paradox which means that if you generate less than something like 10^10 UUID per second you couldn't get collision.
  - Lazare 5y ago
    Well, yes. As I said, it'll be "totally fine". :) The problem is, the submission said "collision-free". This isn't "collision-free", it's "collisions are so unlikely you don't need to worry even under extremely conservative assumptions, assuming you have a decent source of randomness". And that's good enough for me, absolutely. But...if that's good enough, then really, any of the common UUID and UUID-like schemes will be good enough. I'm taking the submission title to mean either "guaranteed collision-free" or, failing that, as "more collision resistant than some alternatives", or maybe "guaranteed collision-free in some specific use cases". But this doesn't seem to be any of those; it's just a timestamp and enough randomness that you'll be safe under reasonable assumptions. In short, I'm not saying "don't use this because you'll get collisions", I'm saying "even though as a practical matter you won't see any collisions, I don't think the collision free label is appropriate".
karmakaze 5y ago
OT: Github READMEs have got to the point where they don't say what it actually does, how it does it, things you can depend on or not. They are now QUICKSTART.md. With the dependency insecurities going around, why would anyone think this is okay?
tester756 5y ago
Why UUIDs were designed in such a way that collides?
joeyh 5y ago
Regular old v1 UUIDs contain 60 bits of the system time and are sortable by it, all you need is a uuid library to extract that information from them. Eg, in haskell: ghci> sortOn Data.UUID.Util.extractTime (map (fromJust . Data.UUID.fromString) ["8fca290c-ac63-11eb-9e74-79cdba6ee3eb", "8d543a32-ac63-11eb-9e74-79cdba6ee3eb"]) [8d543a32-ac63-11eb-9e74-79cdba6ee3eb,8fca290c-ac63-11eb-9e74-79cdba6ee3eb]
- hamandcheese 5y ago
  Not having the leading bits be the timestamp limits the utility, though, because then you don't get sorting "for free" just by having an index on the ID. At least for me, that is the primary appeal of a time-base UUID.
  - saurik 5y ago
    I always just define a custom comparison operator, which is easy enough in both C++ and PostgreSQL.
cratermoon 5y ago
Prefer https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid
NicoJuicy 5y ago
There's also deterministic Guids ( .net) . Useful in some cases when you want to make them consistent. Eg. https://github.com/Informatievlaanderen/deterministic-guid-generator https://github.com/Informatievlaanderen/deterministic-guid-g...
kpdemetriou 5y ago
Hi everyone, OP here. Let me offer some background. fuuids are designed to be sortable and collision-free (for most practical purposes, details below) IDs within a 16-byte footprint making them interpretable as UUIDs. Lazare very helpfully detailed the internals of the two available formats but I'll summarize them here and I'm happy to answer any questions: Format A (fuuid) consists of a 4-byte second timestamp concatenated with a 12-byte random tag. Format B (fuuid_ns) consists of an 8-byte nanosecond timestamp concatenated with an 8-byte random tag. As far as collision resistance is concerned, here's a list of probabilities at various production rates for Format A. Collisions for Format B are only relevant when the production rate begins to approach 10^9 IDs per second (assuming IDs are produced uniformly in time). - 2^-90.51 at 10 IDs/second - 2^-83.73 at 100 IDs/second - 2^-77.07 at 1,000 IDs/second - 2^-70.42 at 10,000 IDs/second - 2^-63.78 at 100,000 IDs/second - 2^-57.14 at 1,000,000 IDs/second Hope this helps!
emidln 5y ago
I've used something very similar in the past, called SimpleFlake[0], which is essentially a 64 bit version with the same principles. I've used it in Lisp, C, C++, Clojure, Python, and Rust. It's conceptually simple, and fits in a 64bit int, which is natively available in a lot of databases. [0] SimpleFlake - https://github.com/SawdustSoftware/simpleflake/blob/f2b51f762a4f073a68fdd39a34732ebf5ec99967/simpleflake/simpleflake.py#L42 https://github.com/SawdustSoftware/simpleflake/blob/f2b51f76...
SPBS 5y ago
Given that time-ordered UUIDs are hardly a new concept, it would be nice if the author did a comparison with the current state of the art rather than let such a bland README do the talking.
globular-toast 5y ago
I don't get why anyone would need to sort them. Just store a timestamp if you want to sort records by order of creation. If this was about efficient indexing or something I would get it. But the only justification is "you can run it through sort".
mro_name 5y ago
putting meaning into the on-purpose meaningless bit sequence of UUID sounds IMO like a recipe for desaster. The result mimics a UUID but isn't.
SeriousM 5y ago
Here we go again. Why do we invent sortable uuids every single year?

94 points by kpdemetriou 5y ago

What is the difference between this and ULID? The latter is implemented in dozens of languages already, and many ULID libraries support conversion into UUID format. https://github.com/ulid/spec https://github.com/ulid/spec "Universally Unique Lexicographically Sortable Identifier"

natch 5y ago

Cool. I don’t see the readme warning about this, so: Use wisely and with full awareness. Revealing creation sequence can leak information which can be an issue in scenarios where such information might compromise security.

sroussey 5y ago

Is this a time swapped version of UUID v1? Like what MySQL will do when converting v1 uuid to binary for use in an index (when using the swap flag)?

pkulak 5y ago

Are they sortable as a string or as binary? Once you deploy something like this, that becomes important because you'll end up storing binary and string representations in different spots, unless you're _really_ careful (and DBs can insert way faster if you're always doing so near the end of the primary key sorting). And unless you use a totally custom string function, you can't have both, since base64 has letters before numbers, and ASCII is vice versa. It can be a real pain.

munk-a 5y ago
The examples use both letters and numbers in the ID composition so I would guess not - in all honesty though your question needs some clarification because the string representation of UUIDs is pretty fluid - there's the generally expressed version like `01324332-f66a-054a-76e4-fbdc7f772cd1` which appears to be what this generator favors - but for indexing UUIDs are usually considered to be their binary values so it's highly unlikely that a DB would see anything beyond a coincidental marginal benefit from using this package. It's hard to tell since the package says "sortable using UNIX sort" so it's not a format agnostic sorter - but it's also not conclusive whether the author meant the common human-readable strings can be sorted using UNIX sort or the binary strings can be sorted using UNIX sort.
hamandcheese 5y ago
I think if you store as hex, which is the traditional string representation of a UUID, then the string and binary representation will sort identically.
- deleted 5y ago
  [deleted]

the_mitsuhiko 5y ago

4 byte timestamp is brave. int(time() - 16 * 10 ** 8)

diath 5y ago
Python's integers are unbounded.
- the_mitsuhiko 5y ago
  The format only reserves for bytes

rekwah 5y ago

Looks similar to ULID[0] (I am the author of a popular python implementation[1]). It appears to have a similar constraint that two ID's generated within the same timestamp (ms, ns) have no strong guarantee of ordering. That might not be a deal breaker depending on your use case but something to consider. * https://github.com/ulid/spec https://github.com/ulid/spec * https://github.com/ahawker/ulid https://github.com/ahawker/ulid

laurent123456 5y ago

I think the issue with a lib like this is that people might use it, thinking they don't need the IDs to be secure... until they need to be. But by then plenty would have been generated, and a lot of code would rely on this sortable property. In fact, I don't see the point of a library like this, it's trying to encode two pieces of information into one string. Why is that? Why not encode geolocation or IP while they're at it. If some data is important, like the order, then a separate database column can easily be used and that would make for a much more durable and reliable solution.

Jiejeing 5y ago
I agree, to an extent, with your comment. But having sortable/chronological IDs on a single column is a really nice feature to have. Obviously, if you rely on the IDs to be unguessable/brute-forceable as part of your access control, then it is certainly bad to use such IDs. But I have not yet seen a case where I need both sortable and secure IDs. Being collision-free is what we want in a database context, and if it can hold some more information for the order, all the better.
koolba 5y ago
Sortable IDs have pleasant properties on insertion in traditional btree indexes as all the new values are on one edge of the tree. Truly random IDs end up with random I/O on the index tree. With a database like postgres with full page writes enabled, it can blow out quite quickly at scale.
- sroussey 5y ago
  It’s worse with clustered indexes — all of the data experiences this issue, not just the index.
  - munk-a 5y ago
    At least in Postgres you have the advantage/disadvantage that real-time clustered tables aren't a feature on offer - so that re-clustering cost is eaten on a periodic basis whenever you invoke a re-cluster operation on the table in question. Additionally re-reading things closely I believe this package wouldn't benefit databases at all since the "sortable" form appears to be the common string representation while postgres will internally store UUIDs (at least in a UUID column) as their binary values - leading to indexing still being out of order unless you specify a ::TEXT casting.

swyx 5y ago

i have a loosely curated list of "State of the Art of UUIDs" here: https://github.com/sw-yx/uuid-list/ https://github.com/sw-yx/uuid-list/ just added FUUIDs, thanks OP

js2 5y ago

I'd advise UUID v6 over this which is at least an RFC 4122 extension. As coded, this isn't UUID compatible other than being 128 bits. http://gh.peabody.io/uuidv6/ http://gh.peabody.io/uuidv6/ Also some recent similar submissions: Timeflake is a 128-bit, roughly-ordered, URL-safe UUID. https://news.ycombinator.com/item?id=25870482 https://news.ycombinator.com/item?id=25870482 https://github.com/anthonynsimon/timeflake https://github.com/anthonynsimon/timeflake ULIDs: https://news.ycombinator.com/item?id=18768909 https://news.ycombinator.com/item?id=18768909 Sonyflake: https://news.ycombinator.com/item?id=25592325 https://news.ycombinator.com/item?id=25592325 KSUIDs (can't find any discussion here): https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid This comment lists other prior art: https://github.com/bradleypeabody/gouuidv6/issues/3 https://github.com/bradleypeabody/gouuidv6/issues/3

ineedasername 5y ago
Is there a reason or need to be UUID compatible? I honestly don't know. I use them in databases and know they're pretty safe to use when integrating data across multiple databases because collisions are astronomically unlikely, if implemented properly.
- js2 5y ago
  So here's a real-world use case that having an RFC 4122 UUID was useful for me. I have a server which accepts reports and stores them in S3. For each new report, a v4 UUID is generated that that is used as the base of the S3 object name. This UUID becomes the report ID. An entire system has been built around the report ID, expecting a hex UUID. Recently, I needed to change how the objects are stored in S3 in order to partition them into multiple S3 prefixes. Instead of storing every object in a single place in the S3 bucket, I needed to do something like: "reports/%s/%s" % (report_id[:2], report_id[2:]) The issue was that I had one component that was writing the reports, and a second component reading the reports. And somehow, the reader needed to know whether a report was stored using the old path layout: "reports/%s" % (report_id,) Or the new path layout. I took advantage of the fact that RFC 4122 UUIDs have four bits set aside for version. After generating a v4 UUID, I update its version to 5. The reader can then check the report UUID version to know which path layout to use. Once all the reports stored using the old path layout expire, I can undo this hack. Of course, I could have made the reader try the new path layout, then fall back to the old path layout. Or I could have updated the entire system to have a better way of communicating the path layout, but that would've been less efficient or have meant touching a lot more code. I guess the moral of the story is: you never know when you're going to need to change something in a backwards compatible way, and having a few bits set aside even for something as simple as an object ID can be useful. I'm fortunate the UUID designers thought of that.

halfmatthalfcat 5y ago

I started looking into TSID/KSUID/ULID in order to support cursor based pagination schemes in GraphQL against non-integer based unique id fields (such as uuids or unique string ids). A couple of notable Java libs: https://github.com/f4b6a3/ulid-creator https://github.com/f4b6a3/ulid-creator https://github.com/f4b6a3/tsid-creator https://github.com/f4b6a3/tsid-creator https://github.com/akhawaja/ksuid https://github.com/akhawaja/ksuid

cratermoon 5y ago
Please don't use the akhawaja ksuid generator for Java unchanged. We used it at my last job until we realized 1. the Base62 code is not thread-safe (it uses a static StringBuilder) and more importantly 2. The epoch used is different from the standard, so the generated ksuid aren't portable. Use https://github.com/ksuid/ksuid https://github.com/ksuid/ksuid insteads
- halfmatthalfcat 5y ago
  Good to know, thanks.

lilyball 5y ago

This really needs an explanation of how the “UUID” is generated. What properties does it have? How secure is it against attackers?

edoceo 5y ago

also this https://news.ycombinator.com/item?id=27004098 https://news.ycombinator.com/item?id=27004098 w3c distributed id spec/primer

ForHackernews 5y ago

Hold on, aren't UUIDv1 already generated based on a timestamp? What's the point of this?

punnerud 5y ago

The Python-code behind this: ts = int(time() - 16 \* 10 \*\* 8) return ts.to_bytes(4, "big") + os.urandom(12)

Lazare 5y ago

First, for something like this, the details matter a lot. How many bits of randomness is this, how many bits used for the timestamp, what's the format, why does it yield the advantages claimed, and most of all, how does it provide collision resistance? Is it using a MAC address (like UUID v1/v6) or a custom namespace (like UUID v5), or what? In this case...looking at the code.... It exposes two formats. Format 1: 4 bytes to store the number of seconds since a custom epoch of... Sep 13 2020 12:26:40, and 12 bytes of randomness. Puzzling choice. Format 2: 8 bytes to store the number of nanoseconds since the same custom epoch, and 8 bytes of randomness. And the collision resistance...doesn't exist at all; it's just relying on 12 (or 8) bytes of randomness and a time prefix. Which seems like it'll be totally fine in practice, but if you actually care about collisions (and in my experience, almost everyone who thinks they do really doesn't), this is unlikely to be an optimal choice. Functionally, I think this is closest to KSUIDs (https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid) which are also the result of combining a timestamp (with a custom epoch) and some randomness, and then concatenating them in a way which is not a valid UUID, will work efficiently as a DB index, and is extremely unlikely to collide. But KSUIDs are much more widely adopted and better documented.

YetAnotherNick 5y ago
Umm.. 12 bytes of randomness has 7*10^28 unique uuid per second. We generally take order of square root of this due to birthday paradox which means that if you generate less than something like 10^10 UUID per second you couldn't get collision.
- Lazare 5y ago
  Well, yes. As I said, it'll be "totally fine". :) The problem is, the submission said "collision-free". This isn't "collision-free", it's "collisions are so unlikely you don't need to worry even under extremely conservative assumptions, assuming you have a decent source of randomness". And that's good enough for me, absolutely. But...if that's good enough, then really, any of the common UUID and UUID-like schemes will be good enough. I'm taking the submission title to mean either "guaranteed collision-free" or, failing that, as "more collision resistant than some alternatives", or maybe "guaranteed collision-free in some specific use cases". But this doesn't seem to be any of those; it's just a timestamp and enough randomness that you'll be safe under reasonable assumptions. In short, I'm not saying "don't use this because you'll get collisions", I'm saying "even though as a practical matter you won't see any collisions, I don't think the collision free label is appropriate".

karmakaze 5y ago

OT: Github READMEs have got to the point where they don't say what it actually does, how it does it, things you can depend on or not. They are now QUICKSTART.md. With the dependency insecurities going around, why would anyone think this is okay?

tester756 5y ago

Why UUIDs were designed in such a way that collides?

joeyh 5y ago

Regular old v1 UUIDs contain 60 bits of the system time and are sortable by it, all you need is a uuid library to extract that information from them. Eg, in haskell: ghci> sortOn Data.UUID.Util.extractTime (map (fromJust . Data.UUID.fromString) ["8fca290c-ac63-11eb-9e74-79cdba6ee3eb", "8d543a32-ac63-11eb-9e74-79cdba6ee3eb"]) [8d543a32-ac63-11eb-9e74-79cdba6ee3eb,8fca290c-ac63-11eb-9e74-79cdba6ee3eb]

hamandcheese 5y ago
Not having the leading bits be the timestamp limits the utility, though, because then you don't get sorting "for free" just by having an index on the ID. At least for me, that is the primary appeal of a time-base UUID.
- saurik 5y ago
  I always just define a custom comparison operator, which is easy enough in both C++ and PostgreSQL.

cratermoon 5y ago

Prefer https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid

NicoJuicy 5y ago

There's also deterministic Guids ( .net) . Useful in some cases when you want to make them consistent. Eg. https://github.com/Informatievlaanderen/deterministic-guid-generator https://github.com/Informatievlaanderen/deterministic-guid-g...

kpdemetriou 5y ago

Hi everyone, OP here. Let me offer some background. fuuids are designed to be sortable and collision-free (for most practical purposes, details below) IDs within a 16-byte footprint making them interpretable as UUIDs. Lazare very helpfully detailed the internals of the two available formats but I'll summarize them here and I'm happy to answer any questions: Format A (fuuid) consists of a 4-byte second timestamp concatenated with a 12-byte random tag. Format B (fuuid_ns) consists of an 8-byte nanosecond timestamp concatenated with an 8-byte random tag. As far as collision resistance is concerned, here's a list of probabilities at various production rates for Format A. Collisions for Format B are only relevant when the production rate begins to approach 10^9 IDs per second (assuming IDs are produced uniformly in time). - 2^-90.51 at 10 IDs/second - 2^-83.73 at 100 IDs/second - 2^-77.07 at 1,000 IDs/second - 2^-70.42 at 10,000 IDs/second - 2^-63.78 at 100,000 IDs/second - 2^-57.14 at 1,000,000 IDs/second Hope this helps!

emidln 5y ago

I've used something very similar in the past, called SimpleFlake[0], which is essentially a 64 bit version with the same principles. I've used it in Lisp, C, C++, Clojure, Python, and Rust. It's conceptually simple, and fits in a 64bit int, which is natively available in a lot of databases. [0] SimpleFlake - https://github.com/SawdustSoftware/simpleflake/blob/f2b51f762a4f073a68fdd39a34732ebf5ec99967/simpleflake/simpleflake.py#L42 https://github.com/SawdustSoftware/simpleflake/blob/f2b51f76...

SPBS 5y ago

Given that time-ordered UUIDs are hardly a new concept, it would be nice if the author did a comparison with the current state of the art rather than let such a bland README do the talking.

globular-toast 5y ago

I don't get why anyone would need to sort them. Just store a timestamp if you want to sort records by order of creation. If this was about efficient indexing or something I would get it. But the only justification is "you can run it through sort".

mro_name 5y ago

putting meaning into the on-purpose meaningless bit sequence of UUID sounds IMO like a recipe for desaster. The result mimics a UUID but isn't.

SeriousM 5y ago

Here we go again. Why do we invent sortable uuids every single year?