Hacker News Reader

Comment by CharlesW | Hacker News Reader

> There are a few compact representations you can use in URLs which make it a bit less ugly…

Any thoughts on where to find best-practices guidance? I need to create an external ID scheme for several million items. hashids (hashids.org) seems interesting, but I have anxiety about choosing a solution with weaknesses that I can't identify given my current level of experience in regards to this.

View on HN

I took a shot at the math behind this at https://www.codepasta.com/databases/2020/09/10/shorter-uniqu...

Using the equation listed in the article I couldn't generate a collision so far. Yet, I still check (in code) for id collision, and pick new id, just to be 100% sure.

This article mostly just says: "If your data is small, then 56 bits is fine". Which is true. But if you are at 56 bits in your UUID, then just use an integer PK with 64 bits and you'll be fine a good deal longer. If your data might get large, an extra 64 bits to get a full 128bit UUID isn't expensive, and encoding in Base36 still yields 25 character UUIDs, which are pretty manageable: "abcdef-01234-56789-ghi-jklmno" (6-5-5-3-6, or max of a u16 for digits). I'm honestly shocked no UUID library makes it easy to export in Base36 with that grouping, it's very neat and tidy and easy to remember.

Why base36 in particular? That implies that you're worried you might lose case information but you're not worried about characters that look the same?

You may consider encoding the uuid in base58 as it is shorter, safe to use in URLs, and easier to debug as it doesn't use characters that can be confused such as 0, 0, I, and l.

I'll add a voice for base58 representation of UUIDs on the wire, it's my preferred solution as well.

Not only for debugging: by being compact, unambiguous, and URL-safe, the helpdesk is also spared a cringeworthy source of PEBCAK incidents since misquoting the identifiers is simply harder.

Caveat programmer, though, there is a hazard, occurring when someone is glib about the usage and relies on randomly generated fixed-length base58 values directly. It happens readily because some popular frameworks include such generation as a utility function. However, 58^22 > 2^128 > 58^21, so a 22-character base58 representation is expected for UUIDs but carelessly random 22-character base58 values may exceed the capacity of UUID's familiar hexadecimal serialization, effectively an integer overflow. We never generate base58 identifiers as a PK, for example, for this reason (they would of course not be UUIDs either). Alas, there is no conventional base encoding more compact than hexadecimal that is robust to the general problem. And I mention it because this issue was observed in the wild.

If I'm not mistaken base64 should not cause an integer overflow (i.e. it will always be a 128-bit integer) if you limit it to 22 characters (and append two = characters to pad it when you actually decode it).

It may not be as URL-safe as base58 though.

Yes. I think of base64 as an unconventional encoding, in that regard, since it's more than just an alphabet for powers of the base but also communicates properties of the output octet length in the serialized form. To do that it's relying on an elegant alignment of bit values to that base58 doesn't have. Perhaps there could be a means to inject the same confluence of form and function into base58, albeit I can't see it after a couple minutes of staring at the algorithm¹.

And also yes: the equals sign is potentially hazardous in a query string, and the use of non-alphanumeric symbols in base64 also creates line-break and double-click/double-tap traps when passed around in an ad-hoc fashion, even in the url-safe variant.

[1] https://datatracker.ietf.org/doc/html/draft-msporny-base58

Reply on news.ycombinator.com