[HN Gopher] We chose NanoIDs for PlanetScale's API
___________________________________________________________________
We chose NanoIDs for PlanetScale's API
Author : s4i
Score : 62 points
Date : 2022-12-29 14:38 UTC (8 hours ago)
(HTM) web link (planetscale.com)
(TXT) w3m dump (planetscale.com)
| joshmgross wrote:
| oh wow Mike is so smart
| mnutt wrote:
| 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.
| charcircuit wrote:
| Those are not cryptographically secure. It would not be hard
| for someone to figure out how to decode it.
| Vt71fcAqt7 wrote:
| 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.
| charcircuit wrote:
| You don't need to keep them in sync. You can create a
| partition for each server to use.
| Vt71fcAqt7 wrote:
| 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?
| mnutt wrote:
| Yes, if you outgrow autoincremented ints then hashids may not
| be a great fit I think?
| mdaniel wrote:
| the previous submission had good points:
| https://news.ycombinator.com/item?id=30856703
| dang wrote:
| Thanks! Macroexpanded:
|
| _We Chose NanoIDs for PlanetScale 's API_ -
| https://news.ycombinator.com/item?id=30856703 - March 2022 (6
| comments)
|
| Related:
|
| _Nano ID: A tiny, secure URL-friendly unique string ID
| generator for JavaScript_ -
| https://news.ycombinator.com/item?id=15225158 - Sept 2017 (78
| comments)
| mdaniel wrote:
| I deeply appreciate the seemingly limitless amount of help
| you provide here, and hope you and yours are happy and
| healthy
| Jarwain wrote:
| 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?
| gobengo wrote:
| 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)
| wereHamster wrote:
| 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.
| thaumaturgy wrote:
| 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.
| skeeter2020 wrote:
| "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.
| nickvanw wrote:
| 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.
| ripperdoc wrote:
| 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.
| dpkirchner wrote:
| If making the urls easy to copy saves them even a handful of
| support requests, it's worthwhile.
| counttheforks wrote:
| Having IDs that can't be represented cleanly in a hyperlink
| makes them pretty useless if you're building a web facing
| service.
| actinium226 wrote:
| 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?
| v0idzer0 wrote:
| Are you actually curious? It's called marketing.
| UncleEntity wrote:
| 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".
| survirtual wrote:
| 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.
| keredson wrote:
| if you have a cryptographically secure random function, just
| use that. no need to hash it!
| survirtual wrote:
| Good point!
|
| Hashing is so magical I may overdo it.
| mihaic wrote:
| 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.
| andrewstuart wrote:
| Just look out for this issue:
|
| https://github.com/ai/nanoid/issues/365
| vlmutolo wrote:
| 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.
| throwaway2016a wrote:
| 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.
| vlmutolo wrote:
| Good point. "Checksum" is probably the more common word here.
| I updated my comment.
| keredson wrote:
| looks like there's an impl already:
| https://github.com/cbschuld/uuid-base58
| irq-1 wrote:
| 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@+-*<>
| ezekg wrote:
| > 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.
| hangonhn wrote:
| 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.
| jeremyw wrote:
| 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...
| ksbrooksjr wrote:
| 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).
| janus wrote:
| 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
| FrancoisBosun wrote:
| In PostgreSQL, if a DB exception is raised (unique_violation),
| the whole transaction will abort: there is no way to retry.
| danbruc wrote:
| Don't expose your internal IDs, expose some identifier
| specifically made to be exposed.
| s4i wrote:
| 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.
| davidcelis wrote:
| 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.
___________________________________________________________________
(page generated 2022-12-29 23:02 UTC)