Allowing non-u64 values as Document IDs

[ecton]

I've started a pull request which aims to offer the ability to use any arbitrary Key implementing type as a document ID.

This is done by introducing a DocumentId type, which tries to bring a level of sanity to using a byte-based value as a document's ID. Internally, the moment a DocumentId is constructed, the source value is converted into the memcmp-able byte representation. If it requires more than 64 bytes, it currently returns a DocumentIdTooLong error. We could remove Copy from Header -- it currently isn't Copy in v0.1.1, and by doing so we could allow larger document IDs using an approach like tinyvec to keep smaller IDs stack-based.

Surprisingly, none of the examples changed. Even the doctests remained largely unchanged. The Commerce benchmark shows the first sets of changes that are interesting -- see that benchmark uses u32s in its source dataset, so converting to u64 was actually wasteful. Here's an example:

https://github.com/khonsulabs/bonsaidb/pull/200/files#diff-e1507ddea9cfec8164d979bfda42d4aa6077da4512e8fdd283c7dbf51c197242R261-R268

Other than the name of the function deserialize, I'm actually pretty happy with how this works out.

My current questions are:

• What does everyone else think about the general approach taken? Any ideas on alternate ways to solve this? I specifically wanted to avoid requiring Header to have a generic.
• Displaying IDs is tricky. My proposal to displaying them (not implemented this way currently):
  • myid: If an ID contains bytes that are all alphanumeric, the ID will be displayed as-is.
  • #1234: If an ID is <= 8 bytes long, render it as a numerical ID with a preceding #
  • %FFFF: If an ID is > 8 bytes long, render it as hexadecimal with a preceding %
  • DocumentId will be able to parse a rendered ID. The goal being that a CollectionName + DocumentId pair uniquely identifies a document within a database, and DatabaseName + CollectionName + DocumentId uniquely identifies a document within a Storage/Server. A fully qualified ID might look like admin.khonsulabs.users.#1 is user ID 1 in the admin database. I'm not sold on how the document ID display works when combined as part of a larger "identifier". Perhaps even the string representation should have a prefix char?
• By adding an Id associated type to SerializedCollection, CollectionDocument could be able to use a new Header type that allows the deserialized ID type.

[ecton]

I'm going to attempt to use Github Discussions for ad-hoc development updates, especially on larger features like this one.

Since the last update, I've simplified the Display implementation of DocumentId:

• If all the bytes are alphanumeric, display it as a string. This could be expanded to include a subset of printable unicode characters.
• Otherwise, render as hexadecimal with a preceding '#'

I've pushed a new set of changes to this branch that adds a PrimaryKey associated type to Collection. This change ends up undoing several API changes -- for example, the create_user API returns a u64 again instead of a DocumentId.

NamedReference was a little tricky, but it now supports custom primary keys as well through a new trait, Nameable.

This branch still needs a lot of cleanup, and a lot of documentation is outdated/broken doctests. Still, given that the result of Monday's explorations were git checkout -f, I'm feeling a lot better at the state of things today.

[colelawrence]

I really like this extended functionality and where you're taking this. One initial idea that comes to mind (which might not be compatible at all, but I'll mention anyways) is to have prefixable IDs, so on display a user's id could be u_8239823 while a message's id could be m_912376 etc (This is seen in Slack APIs and in Stripe APIs). The advantage to having this at the database level is that errors with IDs like Revision out of date (u_643278) become a copyable artifact which can be pasted into a support channel with all context necessary.

I implemented a custom ID type for PostgreSQL in Rust which is a concrete example of how I went about my own custom ID.

It appears this would kinda work exactly out of the box like I'm describing, right?

[ecton]

A PrimaryKey value isn't enough to uniquely identify which collection an ID comes from. However, combining the CollectionName with the Id does uniquely identify a document within a database. Prefix that with the database name, and now you have a unique ID that can resolve a document across the entire Storage. There's a built-in function document_resource_name which will create this fully-qualified ID for a document. Currently the only use case for this is identifying a document within a permission statement, but there's no reason it has to be limited that way.

That ID ends up being pretty verbose, however. If you're wanting a simpler solution that is custom, you can easily implement this as a custom Key type like this (untested):

struct PrefixedId {
    prefix: char,
    id: u64
}

impl<'a> Key<'a> for PrefixedId {
    type Error = Infallible; // should do real error handling instead of panicking
    const Length: Option<usize> = Some(9);


    fn as_ord_bytes(&'k self) -> Result<Cow<'k, [u8]>, Self::Error> {
        let mut bytes = vec![0; 9];
        bytes[0] = u8::try_from(prefix).unwrap();
        bytes[1..].copy_from_slice(&self.id.to_be_bytes());
        Ok(Cow::Owned(bytes))
    }

    fn from_ord_bytes(bytes: &[u8]) -> Result<Self, Self::Error> {
        assert_eq!(bytes.len(), 9);
        let prefix = char::from(bytes[0]);
        let id = u64::from_be_bytes(bytes[1..].try_into().unwrap());
        Ok(Self { prefix, id })
    }
}

And now in your Rust code, you interact with PrefixedId everywhere instead of u64. An enum instead of a prefix byte could be another great approach -- it depends on how the ID is going to be used in the app.

[colelawrence]

Oh great! Yes, I understand that you'd need the combination of collection name + id to be able to identify the fully qualified key. This generally makes sense, and I like this feature.

By the looks of it, it seems like it might be easiest to even just make struct PrefixedId([u8; 10]); so then implementing Serialize/Deserialize from a string like p_febcd, or whatever. Then, the first 8 bytes would be for the u64, and the remaining 16 bits could encode 3 distinct lowercase letters (5 bits enough for a-z) + an extra bit for something...

I suppose the 8 bytes could be extended or shortened still if you suspected needing a larger or a smaller ID space.

As you might guess, this is more-so an exercise for fun to see how we might cram the most out of our bytes without sacrificing speed.

I am assuming we ought to optimize for reading and comparison over writing / formatting, is that fair?

[ecton]

The most important part of implementing Key is that the bytes produced by as_ord_bytes() must be able to be memcmped. BonsaiDb doesn't actually require the Key implementor to be Ord, just that the bytes it produces are Ord. That being said, it would be strange to not implement Ord on the type, since you almost certainly will want to compare them in their deserialized form.

If you're wanting to compact a potentially large number into as few bytes as possible, while still being ordered, check out the ordered-varint crate that I wrote for exactly that purpose.

The binary representation doesn't necessarily need to match the "string" representation. For that reason, I'd suggest using ordered-varint to encode the numerical portion, and prepend it by the prefix. If the prefix is variable length, separate the two by a null byte.

The string representation can visualize the numerical representation using any format that also preserves sort order (if that's important for the string representation).

If my idea isn't very clear, I'd be happy to whip up a quick example.

[colelawrence]

Very helpful and interesting, thanks!