Simpler

[4kimov]

Since the initial library has been out for a few weeks, I got to mess around with it a bit more and realized there are a few rough edges we could iron out:

1. Lower reserved characters count from 3 to 1 (more data packing into generated IDs)
2. As a side-effect of number one, min alphabet length can decrease from 5 to 3
3. Decrease blocklist-related re-generation attempts from almost-unlimited to the length of the alphabet (cc @tzvetkoff)
4. As a result of number three, re-generated IDs don't have to grow in length (try blocking "SrIu" in the playground to see what I'm talking about)
5. Also as a result of number three, min length padding is smoother now (cc @joviczarko)
6. Sounds like minValue and maxValue are not that useful, let's remove? (cc @peterhellberg)
7. Increase min length limit from alphabet-length to an arbitrary value (1_000 for example)

Pros:

• Less code; spec (with comments, etc) went from 336 to 301
• Limited (but still sufficient it seems) number of re-generation attempts, as opposed to currently almost-unlimited / less-predictable
• Smoother blocklist and min length handling
• Packing more data into IDs + smaller alphabet allowed

Cons:

• More dev work for maintainers to re-adjust code (you + me)
• IDs change, which means users that might have current libs in production would have breaking prod changes (although most of our libs are pre-production version (v0.x) ...so comes with the territory)

Unknowns:

• Are there any use-cases we don't test for since changing reserved chars from 3 to 1?

---

Current: https://sqids.org/playground (algorithm code / explanation)
Proposed: https://sqids.org/playground/simpler (algorithm code / explanation)

---

P.S: Also worth noting that I have no intention of changing the algorithm over and over; I figured this might be cleaner + address some current issues/questions, while we're still technically mostly pre-prod.

Thoughts/feedback?

cc @laserpants @vinkla @niieani @antimon2

[peterhellberg]

6. 👍🏻 I'm fully on board with removing minValue and maxValue

[miquelfire]

I think maxValue should be an optional function. If a library is using, for example, 32-bit integers, having maxValue return a value that will not break the library would be nice to know how big a number can be before an overflow error occurs. For libraries that use a number system that is a bit insane (the PHP library has BCMath and GMP, and JavaScript could use BigInt whose max value would require over 2KB of memory to store!), they don't need maxValue

[laserpants]

This sounds reasonable. I am 🆗 with those changes.

I am wondering about something, though: Since each language implementation defines its own maxValue (even if it is implicit), you can currently encode a sequence of numbers in one language, into an ID which then subsequently fails to decode from another language implementation (using the same alphabet and configuration). Could this be a problem?

For example, using the default config in the Haskell version I can generate an ID:

sqids (encode [9223372036854775807])
Right "Ack7vOaIrINC"

But Ack7vOaIrINC is an invalid ID in the JS version.

[laserpants]

Update: The below idea probably doesn't solve anything, since the fundamental problem here is more about integer precision, i.e., unless the number is encoded as a string, there would need to be a suitable data type (BigInt) to hold the number in the first place, in which case that type can probably be used directly for encoding/decoding. Not sure how this would work otherwise.

encode(int)
encodeBig(BigInt)

So maybe not. 🤔 But nevertheless, it could be nice to distinguish, when decoding, between invalid IDs, and IDs that are (technically) valid, but too large for the language to handle.

---

Would it be possible, and useful, to support arbitrarily large numbers by introducing a preliminary step such as the following:

1. Remove one character from the alphabet and use this as a separator character.
2. Split the number into groups of, say, 9 digits each. (Based on an assumption that all languages can handle integers <= 999999999.)
3. Encode each of these groups (as before) using the remaining characters of the alphabet.
4. Join the encoded IDs into one ID, separated by the character from step 1.

The number in my previous example, 9223372036854775807, would then be partitioned as:

922337203 685477580 7

With the default alphabet, a becomes the separator and the remaining characters bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 are then used to encode these numbers. With the old algorithm, we get:

9DVndvc OSFDIQz 6B

These IDs are then combined into the final ID, intercalating the a:

9DVndvcaOSFDIQza6B

[4kimov]

@peterhellberg Cool

---

@miquelfire Question for you. For PHP version, either one of the two extensions are required, but we still use PHP_INT_MAX for max value. Is my understanding correct that the value will dynamically change based on the system/extensions? If yes, sounds like maxValue() would be useful. And maybe you're right - perhaps it's worth making that function optional.

---

@laserpants Yeah, good thought process. This was actually considered in the very first version of Hashids - what if we split up large numbers and use a dedicated separator. But then the cost slowly started outweighing the benefit:

• By adding an additional reserved character, we'd be taking away from encoding alphabet (shorter encoding alphabet = longer IDs)
• We'd also have to decide on what's the most universally supported large number to pack it in better (is there even one? there's so many languages)
• We'd also have to make sure the splitting up didn't leave the numeric chunks starting with a "0"
• Finally, as a minor point, we'd be introducing a cost of an additional reserved char for which everybody would pay, but not everybody might need

That's why we kinda rolled back into keeping the lib clean and simple, and letting the user handle upper limits of ints.

Edit: And to answer your question about Haskell version generating an ID that JS can't decode, to me it doesn't feel like it should be a library's issue because if the user has two systems (one running encoding via Haskell, the other decoding via JS), they should account for scenarios like these on their end. It would be our problem if we didn't communicate clearly what each language supports.

[antimon2]

Good morning everyone (it's morning here in Japan).

Regarding maxValue().
I agree with "making that function optional". In fact, in my Julia implementation, by default, it processes within the range of the system's Int type (Int64) and maxValue() is set to return typemax(Int) (the maximum value of the Int type). However, with a custom extension, passing the option strict=false during configuration will remove the upper limit (using number types like Int128 or BigInt) and the implementation will throw a NoMethodError for maxValue().

As a further extension, I had considered it might be interesting to "specify a switch that represents the maximum value or range of values during configuration". For example, if you set mode=:compatible, it would handle only integers within the range JS(TS) can handle (53bits), and with mode=:default (the default setting), it would handle the range of integer types that language can handle (not extended precision). With mode=:unlimited, it would utilize BigInt to remove the upper limit (this would be invalid for languages that don't support it), and so on.

I will check the new code and specifications when I have time.

[miquelfire]

PHP_INT_MAX is from before Hashids required one of the two extensions. What it's defined as depends on if you compiled it as 32-bit or 64-bit. None of the bcmath or GMP code will even need to look at it. Though, if the value passed to the encode function is above PHP_INT_MAX it might convert to float and lose precision if it wasn't a string value to begin with.

[laserpants]

That's why we kinda rolled back into keeping the lib clean and simple, and letting the user handle upper limits of ints.

Thanks for clarifying this @4kimov. I had a feeling that this is something you'd thought about already. I agree that it should be up to the user to account for these inconsistencies. But doesn't this mean that we still need to make it possible to distinguish between invalid IDs and IDs that fail to decode because of overflow. What if the implementation of toNumber had something like the following:

private toNumber(id: string, alphabet: string): number {
  const chars = alphabet.split('')
  return id.split('').reduce((a, v) => {
    const u = a * chars.length + chars.indexOf(v);
    if (u > this.maxValue()) {
      throw 'Number out of range';
    }
    return u;
  }, 0)
}

In client code, one could then do:

function checkId(id: string) {
  try {
    const numbers = sqids.decode(id);
    if (!numbers.length) {
      console.log('Invalid ID')
    } else {
      console.log(numbers)
    }
  } catch (e) {
    // Number out of range
    console.error('Error: ', e);
  }
}

checkId("8QRLaD")          // [ 1, 2, 3 ]
checkId("adfadsfa")        // Invalid ID

// ID from my previous example, encoded via Haskell
checkId("Ack7vOaIrINC")    // Error:  Number out of range

If this creates a performance hit, then another option is to not do this check in toNumber, and instead introduce a new method canDecode(id). Users can then choose to test their IDs for overflow prior to decoding, if this is relevant to their use-case. For example;

if (sqids.canDecode(id)) {
  const numbers = sqids.decode(id);
  // Do stuff with numbers
} else {
  // At least one number in the sequence is too large for this language. 
}

[peterhellberg]

I'm a bit concerned about this turning into an XY-problem, do we even want to be able to decode from any unknown source? My understanding is that you are primarily meant to decode "your own" ids, making the cross language argument a bit less critical. (Since you then fully control what numbers you are encoding into your ids)

Also, we are still talking about unsigned integers, right? From the point of view of Go that would be being able to encode/decode []uint64, which might not be fully representable in let's say JavaScript. (Without resorting to BigInt that is)

Another approach would be to decide (in the spec) on some lowest common denominator for the maximum value all implementations should be able to encode/decode, and then not support languages with smaller (unsigned) integer types. This is not an avenue I'd prefer to go down, but thought I should mention it at least.

[laserpants]

@peterhellberg: One example would be if you have a solution stack where the back-end application generates IDs from (potentially) large integers, and these IDs are then passed via the URL down to a front-end app, written in another language. Clearly, there is a bug here if the back-end is generating IDs from integers that are too large for the front-end to handle, but it is still useful to be able to distinguish between this situation and IDs that are algorithmically invalid.

[aradalvand]

This is absolutely genius and perfect. I'm totally on board. Solves precisely the few qualms I had with the previous algorithm (i.e. rough min length handling and growing blocked ID re-generation); and does so brilliantly. Thank you @4kimov! Pure perfection.

Removing minLength and maxLength (or at least making them optional) also sounds like a good idea; having worked on the .NET implementation, I would say it did feel like they were quite useless.

I'll start re-working sqids-dotnet as soon as this gets finalized.

[4kimov]

@antimon2 Ok, I see. Yes, it sounds like minValue/maxValue should be optional, so looks like we're leaning in the direction of leaving them out of the spec. Introducing a compatibility mode might be tricky, because JS is not the leading implementation (it's just one of many), so then you'd have to either pick one "to look up to" or assume there is a max limit in the spec (and there's not). IMO ideally each implementation would either a) support the highest int possible or b) support a range of ints, if the language allows.

---

@miquelfire I see, makes sense. Sounds like from 32/64 argument alone, PHP implementation might benefit from exposing maxValue to the user (again, voluntarily). Thank you for elaborating.

---

@laserpants Before we discuss overflow, I figured it's important to clarify: In the playground when it says "Error: Invalid ID" - it's a very poor description of a message that comes from re-encoding decoded numbers, and seeing that it doesn't match the input ID. Basically a simple way of saying "something went wrong, but we don't know what".

@peterhellberg Like @laserpants has mentioned, I've also seen people talk about how they might encode with one language, and decode with another. I wouldn't be surprised to find these use-cases in larger systems.

@laserpants Thanks for the code samples, they were helpful. First of all, I don't think the maxValue check would be that big of a performance hit (at least in js). Second of all, right now in JS, only encode could throw an error, and decode never does (it just returns an empty array), so I do like the fact that this would make two APIs more uniform. Also, a fan of giving more descriptive error messages. At the same time, not all languages would be able to throw that error because in many, you don't have access to "max value + 1", so that extra check is not an option.

If I were to design a split system like above, and if my decoding microservice would get the "Number out of range" error message, there's nothing I'd be able to programmatically do to address the issue (other than notifying APM / DevOps). That means my encoding microservice went over the boundaries of what my decoding microservice is capable of handling, which theoretically should be my fault for designing it this way. IMO, the proper way to design it would be to set an upper limit on the encoding microservice outside of the library - up to the number the decoding microservice can support.

So, the above makes me think that it'd be helpful in finding out what the error is, but not much else. Which kind of circles me back to proper documentation on int limits. I'd appreciate some feedback on this in case I'm missing the point.

---

@aradalvand Thank you for the kind words, and the efforts.

[peterhellberg]

@4kimov My point was not that you would use a single language, but rather that you would be able to control the range of numeric values encoded into ids used in your own system, even if using more than one language.

[miquelfire]

With the logic we're using for the PHP library (I just looked at the code), JavaScript might want the maxValue function to return Number.MAX_SAFE_INTEGER even if it used BigInt to avoid overflow issues.