We chose NanoIDs for PlanetScale’s API | Hacker News Reader

We chose NanoIDs for PlanetScale’s API

planetscale.com

79 pointss4i53 comments

If you want pseudo-random counters for something that are guaranteed to not have collisions, consider using a "linear feedback shift register". LFSRs allow you to choose the number of bits in your id, and "complete" LFSRs use a starting seed [+] value that guarantee they will exhaust the entire bit space before repeating. They are very cool.

In distributed environments, you can assign different seeds to individual nodes, include the seed in the id, and guarantee no collisions across your entire network.

[+]: edit: sorry, I meant "taps". It's been a minute since I got to do something new with an LFSR. LFSR output is determined by "taps" & "seed" & algorithm. Galois LFSR is an easy algorithm to implement. There are publicly available references and datasets for full-cycle LFSR taps for different bit sizes.

I have a php implementation at https://github.com/robsheldon/asinius-lfsr, but the code is absurdly simple and trivial to translate into any other language. Some references and further notes are included.

From TFA: > We knew that we wanted to avoid using integer IDs so that we wouldn’t reveal the count of records in all our table

In order to attain that property the seed must be kept secret, right? A secret that cannot be rotated is hard to work with.

The seed for an LFSR is just the starting value for its cycle; it can be any value in the cycle, and it's public anyway in that you can think of each output of an LFSR as the "seed" for the next output.

But in the case of the "taps", yes, you would want to treat those as a secret if you didn't want someone to predict the next value in the cycle. An LFSR by itself might not be a complete solution for IDs for public consumption, but it does neatly solve the need for pseudo-random non-colliding IDs. Whereas NanoIDs are able to generate values with a ~1% probability of collision over some time period, LFSRs can generate values with a 0% probability of collision over their entire bit space. (And they're composable!)

It looks like NanoIDs are entirely random values reduced to a specific alphabet (https://github.com/ai/nanoid/blob/main/index.js) -- which is approximately similar to:

    tr -dc _A-Z-a-z-0-9 < /dev/urandom | tr -d '/+oO0lLiI1\n\r' | head -c $num_chars

...but with a really nice collision estimation tool attached.

So if you want randomness in your IDs and you still also want to guarantee 0 collisions, then you can always just append a randomly-generated value to the output of the LFSR, and then feed that into whatever widget you want to use to convert it into a public ID, if you think it's necessary.

But the edge case of collision prevention at really large scales has always seemed to me to be much harder to solve than the edge case of ID enumeration giving up anything valuable (in a well-designed application).

Most implementations of generating non-sequential(-appearing) IDs have the property that they generate keys uniformly at random in a different keyspace. An attacker that can gather a large number of IDs can get an arbitrarily-good guess at the number of IDs you've generated.

If the attacker can only check whether certain keys exist, they can just pick a 2^N-sized range of your keyspace, look up whether all those keys exist, and extrapolate from that an increasingly good (with higher N) guess of how many IDs you've generated.

I wonder how this might compare to just storing regular autoincrementing ints in the database, and converting to/from hashids (https://hashids.org/) at the edge. It eliminates the collision concern and stores more compactly at the cost of a tiny amount of encode/decode when processing requests. You’d want to push it down as close to the database layer as possible to avoid inadvertent int ID leaks; I added native hashids support to clickhouse but I’m not sure what other database support might entail.

Aren't INTs cumbersome in a distributed database? For example If I have two servers running one database, now I have to keep the autoincrement in sync between both before I generate a new one. That's why UUIDs are generally used here if I understand correctly.

You don't need to keep them in sync. You can create a partition for each server to use.

Right, but now you've added more complexity. So, true, autoint doesn't fail at multiple servers, but it becomes a hassle. Is there a usecase of having ordered IDs in the first place?

Yes, if you outgrow autoincremented ints then hashids may not be a great fit I think?

Those are not cryptographically secure. It would not be hard for someone to figure out how to decode it.

Hashids is worse than you think, and should be treated as easily-reversed obfuscation only. It doesn’t encrypt IDs, but instead shuffles the alphabet. When encoding an number, it rotates the alphabet by that number, recording that as the first character of the output, and then converts the number to a string using this rotated alphabet. This is so bad it’s basically negligence. (In its early days, it made claims of security that seem to me bald-faced lies, or staggering and fairly implausible incompetence.) In its default configuration, 44 sequential IDs gives you the key to decode all IDs, and that’s not the only way of breaking it.

I don’t know what they said before, but they now say:

“Do you have a question or comment that involves "security" and "hashids" in the same sentence? Don't use Hashids.”

Still, I can see the temptation that these generated strings “look random so people can’t guess them”. Possibly good enough to obfuscate the number of db records from the casual onlooker but not good protection against enumerating accessible records.

Can someone clarify this statement from the original nanoID site (https://github.com/ai/nanoid) for me? "random % alphabet is a popular mistake to make when coding an ID generator. The distribution will not be even; there will be a lower chance for some symbols to appear compared to others."

If random is picked such that it's in the range of alphabet (i.e. 0 to 25), then the bias should not exist, right? Is that what he's alluding to? Thanks in advance.

Yes, you must match your RNG values to an integer multiple of your alphabet size, or there will be bias on modulo. Filter, smear bits, etc.

More explanation here: https://stackoverflow.com/questions/10984974/why-do-people-s...

Javascript random number generators don't let you choose an arbitrary range. So if you have an alphabet of 26 characters (0-25) you would have to generate a random number by running:

  crypto.getRandomValues(new Uint8Array(1))[0] % 32

And then filter out the value if it falls outside of your range (0-25).

> This gives us a 1% probability of a collision in the next ~35 years if we are generating 1,000 IDs per hour.

Yes, but that's for 1,000 IDs per hour. That is not a large workload. If you generate 10 IDs per second (which, again, is not a lot), your time frame shrinks to just over 1 year. With 100 IDs per second, a mere 36 days. With your reduced alphabet, I would at the very least bump your ID length to 16 characters.

That's why there are no silver bullets.

They have a problem (long IDs in links), they have a scenario (no more than 1000 entities, databases, I suppose, created every hour), and they found something simple that solves their problem under the requirements derived from their scenario. YMMV

the previous submission had good points: https://news.ycombinator.com/item?id=30856703

Thanks! Macroexpanded:

We Chose NanoIDs for PlanetScale's API - https://news.ycombinator.com/item?id=30856703 - March 2022 (6 comments)

Nano ID: A tiny, secure URL-friendly unique string ID generator for JavaScript - https://news.ycombinator.com/item?id=15225158 - Sept 2017 (78 comments)

I deeply appreciate the seemingly limitless amount of help you provide here, and hope you and yours are happy and healthy

"User friendly, clickable in the browser, api urls" seems like... a made-up user requirement? Have they nailed their product so well that this is the highest value work outstanding? There's some neat technical details in there but to me this is the definition of engineering procrastination.

Choosing ID strategy is one of those early architecture decisions that has to be done upfront and that can give a lot of headache later if the choice was wrong. So I wouldn't call it procrastination if it's made before starting development. To change it later in the process, just for vanity purposes, would certainly be risking wasting time on the wrong thing.

Having IDs that can't be represented cleanly in a hyperlink makes them pretty useless if you're building a web facing service.

If making the urls easy to copy saves them even a handful of support requests, it's worthwhile.

Hi! I'm the VP of Engineering at PlanetScale and was at the company when we made this decision.

We had the advantage of being able to decide to do this up front when we were first building the current product. The marginal work for this was nearly zero because we did not have to migrate anything existing, we just decided to address our resources using this strategy. In that way, there was nothing procrastinated -we just decided this was a good idea, and did it.

I can speak from firsthand experience, however, how useful it is to be able to copy/paste links and references to resources. It makes support, collaboration and work much easier when you can easily share links to resources.

Couldn't you just remove the `-` dashes from the uuid and wouldn't that make it clickable? I dunno, I think I'll stick with using uuid's.

This is great, except for the additional query each time a record is instantiated in the rails concern. That might cause some performance problems in high traffic.

Perhaps it’d be better to attempt the insertion and change the id only if there’s a colission detected with a uniqueness constraint

In PostgreSQL, if a DB exception is raised (unique_violation), the whole transaction will abort: there is no way to retry.

Kind of curious as to why they publish this. It's interesting, but if I did think I would just see it as an implementation detail and not something particularly worthy of an article. Should I maybe change my standards for what's publishable?

Just don’t click the link.

I clicked it, read the article and it has absolutely no bearing on my daily life aside from a way to waste a couple minutes before going driving in this snowstorm.

I, in fact, welcome anyone to publish whatever they want besides yet another “we made this wrapper around chatGPT like a billion other people and used it to, gasp, get you to click on this link”.

Are you actually curious? It’s called marketing.

We should consider the following properties when evaluating ID formats and generation algorithms:

1. Private: you shouldn’t be able to gain information about the system using the IDs from an ID alone. E.g. document enumeration attacks like what happened with Parler (https://www.wired.com/story/parler-hack-data-public-posts-im...)

2. B-tree/cache friendly: newly created IDs should all exist in a narrow range of values. This is helpful for databases.

3. Stateless: ideally you shouldn’t need to know the current state of the system to create a new ID.

4. Human-friendly: IDs should be easily dictated, copied, pasted, etc. This means they should be encodable as text that is short and does not include ambiguous characters. Bonus points for error detection like with credit cards.

Some of the these properties are in conflict. Statelessness is achieved by randomly generating long IDs, but people don’t like reading or typing long IDs.

Different use cases will need these properties in varying amounts. If you don’t intend to expose the IDs to users, (4) doesn’t matter. Just use long, randomly generated byte strings prepended with the date. Most databases have a UUID type that fits the bill.

If users are going to be working with IDs, that’s more complicated. If not every document has a user-facing ID, just go with the non-user-facing ID like before, and generate a shorter, random, stateful ID as needed.

I don’t think NanoID prepends the date, which means it won’t be efficient when inserting large numbers of IDs into a large index. They also default to using ambiguous characters like 1 and I and l. Also no error code. But they are shorter than UUIDs. So it doesn’t meet property (2), and it only kind of meets property (4). NanoIDs are random, so you’re probably safe from enumeration attacks (1). NanoIDs mostly leave statelessness as a decision for the user. They have a nice tool that helps estimate how long the IDs should be (https://zelark.github.io/nano-id-cc/) for a given collision resistance.

I think we can do better overall. Bitcoin uses a good encoding scheme called base58check (https://en.bitcoin.it/wiki/Base58Check_encoding). It generates fairly short strings and uses a checksum at the end. I think it could be refined for non-bitcoin purposes, but it’s already pretty good.

A 128-bit value like the ASCII string “hackernewstestid” is encoded as “Dtajqjz5pptWcmGrNcwBx7”. It’s about 2/3 the size of the equivalent UUID, even with the (unnecessarily long for this use case) checksum. It also has no punctuation.

I’d like to see a small ID standard that meets the above requirements and has a choice for either stateless and long or stateful and short. Maybe another choice for secure random or insecure. But all options would have binary form and a text form. The text form would use something similar to base58check, but probably with a smaller (or user-determined) length for the checksum.

It took me a bit to realize that what you're referring to as "error code" in many other contexts is "checksum"... this may just be the domain I work in but for me, "error code" usually means an "id that signifies a specific error happened"

Another thought is that UUID V4 (which is the most common UUID implementation I've seen in the wild) also does not have a checksum. Though I think in general a checksum is probably a good idea if you want to help prevent people from mistyping the code or an optical reader from making an error.

Good point. “Checksum” is probably the more common word here. I updated my comment.

I want a set of symbols which are commonly used in most native languages and easily accessible from the keyboard. Numbers and math/common symbols should be mostly universal. @ from email. Plus, minus, multiply. Less and greater and HTML brackets. Hex without the english characters, and works in URLs.

    0123456789@+-*<>

looks like there's an impl already: https://github.com/cbschuld/uuid-base58

That’s pretty cool. I still think it would be nice to have a checksum at the end. That way, applications could return nicer errors to the user than 404.

ULID hits most of these, and can be converted to UUID for use with databases supporting this datatype (not a strong column): https://github.com/ulid/spec

I'm curious as to why they didn't decide on using UUIDs with the `-` stripped for URLs, and readding them for queries. It would accomplish the same goals wouldn't it?

NanoIDs are shorter than UUIDs because they have a bigger alphabet. That's probably why.

It's not very important for putting IDs in URL paths. But it can matter when using them in DNS subdomains because often there are surprisingly short max character lengths for domain names in e.g. LetsEncrypt SSL certs (iirc 63 characters)

The 63 character limit is in the DNS spec, not invented by Let's Encrypt.

See https://stackoverflow.com/questions/32290167/what-is-the-max... for one explanation.

oh wow Mike is so smart

Just look out for this issue:

https://github.com/ai/nanoid/issues/365

Don't expose your internal IDs, expose some identifier specifically made to be exposed.

The post covers this:

> Our API is a Ruby on Rails application. For all public-facing models, we have added a `public_id` column to our database. We still use standard auto-incrementing BigInts for our primary key. The `public_id` is only used as an external identifier.

I assume you mean internal IDs == primary keys in your database. If that's the case, and if your primary keys are UUIDv4's, ULIDs, KSUIDs, Cuids or similar... then why not? There are a lot of benefits, such as simpler SQL queries in your backend. You can also merge data from different databases into one as collissions are highly unlikely, which is not possible with numeric IDs.

Why not just do a SHA2/3 hash + b58 & truncate as desired? Seems pretty simple.

For immutable data, that sort of identifier has an added benefit of deduping data.

For mutable data, just take a hash of a cryptographically secure random function.

if you have a cryptographically secure random function, just use that. no need to hash it!

Good point!

Hashing is so magical I may overdo it.

How many bits is this?

After reading this article, my impression of Planetscale as a brand actually got worse. It seem to miss most of the essential bits of information:

* The basic concept is that they just want to use a bigger alphabet to encode more information in fewer characters. The efficiency ratio of NanoID is log 36/log 16, or ~30% better since it has a bigger alphabet. You could get more if you went for instance with base 58 (includes uppercase, except I and O to remove ambiguity with the digits 1 and 0).

* UUID can remove those dashes, that's just cosmetic. There are multiple UUID specs though, and some include a timestamp that actually might be useful for certain purposes.

Overall the article seem to get lost in overly specific code snippets and explaining details without explaining essentials.

After reading this comment, my impression is that you didn't actually read the article as you have apparently missed all the arguments for not using uuids that it presents

I did, it just was poorly written with second order ideas and non sequitors, instead of trying to identify the primary concepts.

> Try double clicking on that ID to select and copy it. You can’t. The browser interprets it as 5 different words.

After reading that, shouldn't my first thought be: "Have you though about simply removing the dashes from your string?"

To me these are the questions that you should ask about a uid function:

1. How much randomness do you want to add to prevent collisions?

2. What characters are allowed? If you want to dictate it, maybe avoid 0,1,o,l and keep lowercase. If you can paste it, allow uppercase characters.

3. Can you precisely describe the algorithm in case you want it in another programming language?

4. Do you want any non-random information encoded? Maybe a sharding id or a timestamp?

Only the first question was actually addressed, and even that without doing the math, by simply referencing another website. Doing estimation calculation is something that an engineer should have a good intuitive understanding of, so I think it's slightly damaging for industry mentality when even these articles don't do this themselves.

Reply on news.ycombinator.com