Limit the maximum length of the document identifier

[loiclec]

At the moment, we have not defined the maximum allowed length for a document's identifier.
For example, it is possible to add the following document, with a document id weighing 632 bytes:

{
 "id": "c2ecfe3c-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28-djn0-4fe0-8555-1lceef28"
}

Since Meilisearch v1 will be released soon, with a promise of no breaking changes, we need to decide now whether it is sustainable for us to keep accepting very large document ids.

Technically, I could see this lack of limitation causing some problems. For example, at the moment it is not possible to create any LMDB database where the key is the document id, since LMDB keys are limited to 511 bytes (I think). Therefore, to manage the correspondence between user document identifier (String) and internal docid (32-bit unsigned integer), we resort to using two FSTs (finite state transducers), which are difficult to work with and slow to update incrementally (we have at least one issue related to it).

Therefore, I'd like to propose a limit to the length of the document id to something close to 500 bytes, which would be easy to remember and would fit into an LMDB key with a few bytes of extra space for potential metadata. This would give us a lot of freedom to work with document ids and allow us to offer better performance guarantees as well.

[dureuill]

Hello, a few thoughts about this proposal, from a newcomer's perspective:

1. In case of doubt, it is better to put a limitation right now so as to avoid over-promising for v1, so in that case, I'd be in favor of adding a limitation to 500 bytes now since we'll be able to remove it backward-compatibly in the future.
2. That said I'm not a huge fan of putting arbitrary (from a user's point of view) size limitations on user data. This is not user-discoverable, and we will have little recourse to offer to people whose document ids do exceed 500 bytes (which is already a lot, though). I would prefer a "compatibility layer" such that we can use the optimal storage strategy if the key fits, and otherwise rely on a secondary, slower strategy (if FSTs are too complex, maybe a standard hashmap or Btree would be a better fit? I'm not sure at all). Of course, it is always a trade-off, in particular, if the performance is too degraded in the compatibility layer then maybe we really need to impose the size restriction.
3. Do we have any data on document id length?

Keep in mind I could be missing some aspects of the trade-off, though 🙏

[gmourier]

3. Do we have any data on document id length?

Negative!

[dureuill]

Some more context I found: it occurred to me that we already have limits in place that I already think are more restrictive than a size limit: https://docs.meilisearch.com/learn/core_concepts/primary_key.html#formatting-the-document-id

I'm not sure that adding a size limit of 500 bytes will be felt as an additional constraint in this context.

[gmourier]

Trying to consider the pros/cons of limiting to 500 bytes first (because no real gains were given to limit it to something more restrictive, so I’m not even considering it right now):

Pros:

• Easier/more maintenable code base?
• Read speed gain for everyone?

Cons:

• URLs can't be used as primary key (2048 chars max), but the current format does not catch every possible URL format.
  • If the id is a string, it can only contain alphanumeric characters (a-z, A-Z, 0-9), hyphens (-), and underscores (_).
• We can’t know the percentage of the actual user base for which it will be a hard breaking when upgrading to v1.0. It probably represents a small user base given an example of a 500 bytes primary key size 👇

abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef

[curquiza]

Do we know if our competitors have this kind of limitation?

[gmourier]

Algolia

Algolia limits objetID to the maximum size for a record.

For Standard and Premium plans:

• 100 KB for any individual record
• 10 KB average record size across all records

For legacy plans (before July 1, 2020):

• 10 KB for Pro, Starter, or Free accounts
• 20 KB for Essential and Plus

Business and Enterprise accounts have a 100 KB customizable limit.

https://www.algolia.com/doc/guides/sending-and-managing-data/prepare-your-data/in-depth/what-is-in-a-record/#acceptable-characters-for-objectids

objectID strings can:
Contain any character
Be of any length as long as it fits the size limit for your plan.

SQL DB (may be vendor dependent)

Primary columns have a maximum length of 900 bytes. (The information I've found with a quick search).

MongoDB

https://www.mongodb.com/docs/manual/reference/bson-types/#objectid

ObjectIds are small, likely unique, fast to generate, and ordered. ObjectId values are 12 bytes in length, consisting of:

• A 4-byte timestamp, representing the ObjectId's creation, measured in seconds since the Unix epoch.
• A 5-byte random value generated once per process. This random value is unique to the machine and process.
• A 3-byte incrementing counter, initialized to a random value.

[dureuill]

Worth noting that MongoDB object ids appear to be generated, rather than user-provided.

SQL DB is very vendor dependent I think. I can't seem to find a limit to String rows that would serve as primary keys in sqlite DB WITHOUT ROWID (and there is a general limit to the size of one string in sqlite, but it can be changed at compile time and the default value is 1,000,000,000 (1 billion bytes))

[irevoire]

Also, there is something we should keep in mind when we're looking at this kind of issue. It's that we're not really a competitor of *sql or MongoDB because we're not a primary database.
Thus, it may be ok for MongoDB to autogenerate its IDs when it's definitely not for us since we're going to interface with MongoDB or something else and wants to use its keys.