Motoko B-Tree, for efficient ordered key-value data

[jzxchiang]

@matthewhammer

@paulyoung

Don’t mean to derail, but curious about using StableBTreeMap vs the approach taken here:

cdk-rs/examples/asset_storage/src/asset_storage_rs/lib.rs at d056a9cc8a0eee4a2adda2dd60285d0c8ee1061c · dfinity/cdk-rs · GitHub

Perhaps someone who has touched that code can comment more (@chenyan ?), but my first guess is that they indeed do look similar in purpose (the asset one uses text keys, as opposed to byte strings, but that seems minor). The non-asset-specific one also seems to be engineered differently, in terms of its expression as Rust code. Without comparing them in a lot more detail, it’s hard to say more.

What’s strange is that @paulyoung’s example uses the ic_cdk storage API to read/write to stable memory, but StableBTreeMap doesn’t.

Can canisters even use that data structure then? It appears to me that it relies on replica internals, which makes it replica-specific and not canister-general. I’d like to be wrong though.

By contrast, using the stable keyword affects upgrade behavior (persisting the data in these vars using stable memory, and but incurring much less overhead during upgrade, due to “bulk operations” used then). Outside of upgrades, stable data structures in Motoko use ordinary memory read and writes, happening in the ordinary Wasm memory, and do not incur any system call overhead.

This sounds correct to me, but there is one huge drawback to Motoko stable variables: they are limited by the size of ordinary wasm memory, which is 4 GB (and in practice much less due to GC).

Compare this to a stable data structure in the mold of StableBTreeMap, which can access the entire 8 GB (and soon to be increased) stable memory address space.

I think @icme’s point about multi-canister scaling is valid, but I think any data structure developed from here onwards should be “multi-canister-aware”. Would an eventual (or even current) BigMap replace this? Developers don’t want to think about storage restrictions. They just want to read and write data to a data structure that abstracts all of that away. In 2022, I think any newly developed data structure that aims to be scalable should try to be as forward compatible as possible in light of all the changes going on.

---

With respect to Merkle trees, witnesses, and root hashes, I think it’s a great idea to make this library at least optionally “crypto-aware”. Certified variables are an incredibly powerful feature of the IC, and right now the biggest barrier to more widespread adoption of certified variables is a lack of simple libraries. Perhaps @nomeata could chime in on whether this would be the right place to do it.