8 ms·
Universally Unique Lexicographically Sortable Identifier in Go
- TeeWEE 10y agoNote. You cant compare ULID with UUID's - An ulid is "sortable". But the whole point of an UUID is a random unique ID. Non guessable. Sortable is not a feature you normally want from an uuid. And still UUIDs are still sortable. But it doesnt have any meaning. - An ulid also encodes Time, an uuid doesn't. - An uuid has less change of clashing: Its 128 bit vs 80 bit for ulid. - An uuid is also url safe. - An ulid is case insensitive. I don't see how this is an advantage.
- _ak 10y agoYou just compared UUIDs with ULIDs.
- cloudhead 10y agoMaybe he means programatically?
- icholy 10y agoI think he's joking.
- throwaway98237 10y agoAnd nailed it.
- sp332 10y agoThat's contrasting, not comparing.
- _ak 10y agohttps://www.google.com/search?q=to+compare+definition https://www.google.com/search?q=to+compare+definition
- tsenart 10y agoULIDs are meant to be compared with Time UUIDs in particular. See: https://www.famkruithof.net/guid-uuid-timebased.html https://www.famkruithof.net/guid-uuid-timebased.html
- tyingq 10y ago>An ulid is case insensitive. I don't see how this is an advantage. It's helpful if you've ever had to read something like a ULID over the phone. Base64 isn't fun in that situation.
- jdmichal 10y agoI've never seen a UUID in base-64 instead of hex...
- tyingq 10y agoHex is also case insensitive. Was trying to answer why case insensitive might be an advantage.
- jdmichal 10y agoSure. I just don't even understand why it's a point in a discussion about UUID (hex) vs ULID (base-32), since both are case-insensitive... Which I think is why TeeWEE was stating that it's not really an advantage for ULID.
- tyingq 10y agoMy guess is that the README was mostly copied from here: https://github.com/alizain/ulid https://github.com/alizain/ulid Which has a similar list, but presents them as features/facts, not advantages. Edit: Perhaps it was noted to specifically call out that it maintains case insensitivity, even though it's choosing a more dense approach than just hex.
- vertex-four 10y ago> An uuid has less change of clashing: Its 128 bit vs 80 bit for ulid. Actually... that's 80 bits for the "random" part of the ULID, which only disambiguates within the same millisecond.
- clinta 10y agoIf you sort a list of ULIDs they sorted by time of creation, with random order only among ULIDs created in the same millisecond. As far as guessable, you still have 80 random bits. Though I'll admit I'm not qualified to comment on whether the difference between 80 and 128 bits is significant when you're trying to make sure your identifiers are not guessable. As for less chance of clashing, 128 vs 80 bits. 80 bits is only within the same millisecond. The 128 bits is for the lifetime of your application. Based on my basic understanding of the birthday paradox, there is a 50% chance of collision if you have 2^40 ULIDs generated during the same millisecond. And there is a 50% chance of collision if you have 2^64 UUIDs generated during the lifetime of the application. Case insensitivity and the chosen character set is an advantage if you want to use this ID as a filename without having to worry about the limits of the filesystem.
- foobarian 10y ago> But the whole point of an UUID is a random unique ID. Non guessable. Sortable is not a feature you normally want from an uuid. Why so? As the name says they just need to be universally unique. Even relying purely on randomness seems bad, because you are at the mercy of the entropy source. Mess that up and you can end up with nasty problems throughout your system.
- cfv 10y ago> This alphabet excludes the letters I, L, O, and U to avoid confusion and abuse. Can anyone please ellaborate? I don't get the confusion or abuse potential
- cloudhead 10y agoI'm guessing the following pairs can be confused visually: O/0, I/l, U/V..
- _ak 10y agoNot the author, but presumably because 1, I and l are visually hard to distinguish in some fonts. Same goes for O and 0. As for U, I don't know about that, but I recently stumbled upon the issue that Google's OCR software seems to incorrectly recognize U as II relatively often.
- tsenart 10y agoDepending on the font used, 'I' and 'L' can be easily confused by humans. 'O' can be read as '0' too. This is meant to prevent that. As for the 'U', I'm not sure why the original ULID spec left it out. Thanks for raising this. I'll investigate.
- Guvante 10y agoWell you need to leave 4 characters out to get to 32, so unless there is a better character the selection is arbitrary.
- tyingq 10y agoTypically, 'U' is omitted to avoid accidentally putting the word FUCK into the generated output. No, not kidding. See http://www.crockford.com/wrmg/base32.html http://www.crockford.com/wrmg/base32.html, Ctrl-F, search for obscenity. Edit: Interestingly, since it already omits the letter I, adding U covers all of George Carlins' 7 Dirty Words: https://en.wikipedia.org/wiki/Seven_dirty_words https://en.wikipedia.org/wiki/Seven_dirty_words
- 10y ago
- pritambarhate 10y agoWill the ulid be unique even if it is generated from 2 different machines at the same millisecond?
- tsenart 10y agoYes if you use a good source of entropy. In Go, the easiest and most secure is the `crypto/rand.Reader`. But it's also slow. If you don't need the security properties, an instance of `math/rand.Rand` should suffice. Otherwise, you can implement your own. It's just an io.Reader!
- drfuchs 10y agoYes, if your source of entropy is worth its salt.
- vlowther 10y agoThat was bad and you should feel bad. :)
- lobster_johnson 10y agoI wonder why you would ever want it to be case-insensitive? Surely that increases the possibility of clashes, and violates the very good principle of least surprise (pretty much every other ID in the world is case-sensitive).
- quink 10y agoThe hex representation of GUIDs/UUIDs is case insensitive in most interpretations, I'd say that counts enough.
- lobster_johnson 10y agoI'd be surprised if many developers these days actually compared UUIDs case-insensitively, though, even if they're intended to be. Microsoft, which have relied on GUIDs for years going back to their version of DCE/RPC, probably does it right. If it's part of a spec, then it's simpler, but it's still a potential point of surprise.
- Dowwie 10y agoSeems that someone ported the javascript ulid library to Python: https://github.com/mdipierro/ulid https://github.com/mdipierro/ulid .. and it appears to be working
- aruggirello 10y agoOut of curiosity, I just wrote a PHP ulid() function. [1] It took me a little more than 5 minutes, so it wasn't that hard after all. It appears to run at only about 35% the speed of the Go version, but hopefully there's still room for some little improvement. [1] https://github.com/phptools/ulid https://github.com/phptools/ulid
- tsenart 10y agoFellow PHP implementation: https://github.com/Lewiscowles1986/ulid https://github.com/Lewiscowles1986/ulid
- joshuak 10y agoI've been working on a closely related problem of universal identification in distributed computing for a few years now. It's now in standards review and hopefully publishable soon. We came to the conclusion that universal ids should represent identity only, and explicitly not have 'metadata'. What is the use of 48 bites of time? It reduces the overall entropy, for what? If time is important then why not make the id literally time (i.e. UnixNano), if it isn't they why not make all bits rand? Also, while I think speak-ability is actually very important (many disagree), I'd assert that capitalization is better addressed from the opposite direction (i.e. UI). Instead of removing capital letters from the ID itself affecting all cases, address the human factors in the few cases it comes up. I think this is good advice in general: When spoken aloud we suggest that you don't indicate capitalization at first. In many cases, such as search, human validation etc, this is more than enough precision, then one can add capitalization for disambiguation as needed. For example: "ab2Cd3Ef1g" Spoken becomes: "a b two c d three e f one g. Capitalize 4 and 7, c and e" With the capitalization part optional depending on context.
- Glyptodon 10y agoI'm not sure how I feel about time, but I feel like case sensitivity is asking for trouble if you're expecting anything to be vocalized/shorthand-written, particularly without knowing individual use cases. It also seems like the sort of thing that might occur so infrequently nobody remembers to cover the "fringe" case, particularly for things a couple layers removed, assuming the set size is as huge as it seems intuitively.
- tsenart 10y ago> What is the use of 48 bites of time? It reduces the overall entropy, for what? If time is important then why not make the id literally time (i.e. UnixNano), if it isn't they why not make all bits rand? For some designs it's useful to have identifiers have other properties than uniqueness. In this case, this property is relative lexicographical (and binary) order based on time so that you can leverage the order between the things the identifiers identify without looking at the things. The entropy is there to satisfy the uniqueness property (with some acceptable degree of collision, application dependent). The time is there to satisfy the ordering property.
- lazulicurio 10y agoWord of caution to anybody looking to use a similar method working with SQL Server: the SQL Server uniqueidentifier type is stored differently on disk than binary(16). Instead of being ordered by bytes 0-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15, uniqueidentifier values are ordered by bytes 10-11-12-13-14-15-8-9-7-6-5-4-3-2-1.
- zamalek 10y agoMSSQL does have a similar identifier, though - NEWSEQUENTIALID.
- lazulicurio 10y agoYes, but NEWSEQUENTIALID isn't globally ordered, it's only ordered for the computer on which it was generated. For that matter, on a single computer the ordering isn't guaranteed[1]. This makes NEWSEQUENTIALID fairly useless if you're looking to merge records from disparate sources and sort them independently of origin. [1] https://connect.microsoft.com/SQLServer/feedback/details/475131/newsequentialid-is-not-sequential https://connect.microsoft.com/SQLServer/feedback/details/475...
- zamalek 10y agoAh right, I stand corrected.