Guidance on setting the max values for the key/value in the stable-structures?

Please add some guidance on what these values should be set to, especially providing some examples of custom structs with different primitive types and providing reasoning for the choice of setting a certain value?

Tagging @ielashi since he’s the author on the repo.

P.S. Also curious why the implementation isn’t able to figure this out by itself if it knows at compile time what types are being used for the key and value types.

1 Like

Hey @saikatdas0790,

I agree with you that figuring out a suitable max key/value can be confusing. The reason that a StableBTreeMap currently requires it is because it helped simplify the implementation. The current implementation uses a constant-size allocator that is both simple to reason about its correctness and avoids fragmentation in memory. Prioritizing simplicity over usability felt appropriate for the initial implementation, especially that the Bitcoin integration is the primary driver behind this work.

Medium-term, we’d ideally replace the constant-size allocator in StableBTreeMap with something more flexible (e.g. a segregated list allocator), and at that point users won’t need to specify a key/value size. I’m occupied at the moment with the Bitcoin integration work, so I’m not sure if/when I’d be able to get to that. However, the stable-structures repo does accept external contributions, so anyone who’d like to improve this is more than welcome to contribute directly :slight_smile:

As for what sizes to set, here are some guidelines I can share:

  • If the type is a fixed size, then you should use that size as your max key/value. In the example you shared, a u64 is given a size of 8, and that’s because the Storable implementation of u64 encodes it as an 8-byte blob.
  • If the type is variable in size, such as a String, you’ll need to think of an appropriate upper bound for your use-case. For example, if you’re storing usernames, consider what would be a reasonable upper bound for usernames, and use that. The trade-off of choosing a larger size than you need is giving yourself more flexibility but at the expense of more memory.
  • If the type is variable in size, but that size can vary significantly, (e.g. storing assets ranging from a few bytes to a few MiBs), then I’d recommend splitting your data into different buckets. We do this in the Bitcoin implementation.

And that brings me to your question of why the implementation isn’t able to know the size of the keys/value at compile-time. We can’t determine the size at compile-time because types like String and Vec<u8> don’t have a fixed-size.

5 Likes

Thank you for the detailed explanation.

I apologize, but I’m not skilled enough, YET :slight_smile:, to contribute the flexible allocator required

Essentially, I was wondering why we can’t just store references to the types whose sizes cannot be known beforehand, and then allocate for the space required for them at runtime, but you sort of answered it. We need a stable memory allocator that can do it, and the current implementation doesn’t support that yet?

Yes, exactly. Even if we only store references, we’ll still need to store the data somewhere in stable memory, and that will require a dynamic allocator if we want variable sizes.