Really interested by this. If we could manage schema migration in motoko this would greatly benefit the builders.
Random thought: should we even try to port legacy database systems onto the IC?
With orthogonal persistence, application developers no longer need to worry about disk block and file system requirements, and can instead write to and read from data structures in RAM (periodically and transparently snapshotted to disk).
Maybe this is a good opportunity to “reinvent the wheel” and hopefully say goodbye to impedance mismatch…? 
Orthogonal persistence and upgrades don’t mix. If you write an immutable canister (no upgrades ever), then OP is great. For anyone else, stable memory is your persistence, and all the “old” problems around persistence are still around (backward compat, schema changes, efficient access), and need to be solved. Yes, there are multiple ways of solving it (data bases, file systems, custom formats; maybe those writing software for non-volatile RAM have clever ideas). But unfortunately the IC does not magically make all these complexities disappear…
1 Like
Has anyone looked at FoundationDB? It looks like a good first persistence layer that you can build SQL-like or doc-db on the key value store. The C++ → WASM story is good right?
https://www.foundationdb.org/
Hello everyone.
I was working on the solution for stable memory in rust canisters for some time.
And I took a different approach. The core idea is, what if we somehow could allocate memory on stable storage. Yes, this won’t work with native std’s collections (since we want to allocate 64-bit pointers, but wasm is 32-bit), but if we also manage to build some collections on top of this allocator from scratch, this will do both:
- Save us from expensive pre-/post-upgrade procedures, since all of our data is already stored in a structured way.
- Respect the Orthogonal Persistence paradigm, since a user would store their data in a collections, not in a database.
I’ve managed to build such a memory allocator.
I didn’t tested it on a real canister yet, but I’ve abstracted the stable memory away with an interface and tested it on a raw Vec.
Then I got promoted on my main work, and now I have no free time to implement the collections. I’ve tried to find a freelancer (I thought, for some CS student it could be a nice practice), but it seems like the amount of money I can afford to spend on this is not enough to motivate anybody.
So, then I thought, maybe someone here, on this forum, would be interested in this thing?
The main goal is to build two collections:
- A Java-like HashMap that would be able to efficiently manage at least 500GB of data.
- A Dynamic Array on top of that HashMap, that would use indexes instead of keys (so we could iterate).
But for efficient HashMap of this size one would also need to implement classic Dynamic Array (to store the table) and some kind of self-balancing binary tree, like RBTree (for buckets).
So there is actually a lot of work.
What do you think, guys? Is it worth trying?
2 Likes
The memory allocator also supports 4 (this can be extended if needed) words of “global pointers”.
Such a pointer could point to some kind of “variable definition map” - a hashmap that stores named pointers to other collections.
Such a definition map could be abstracted away with some handy functions so the end-user would get an interface like this:
static mut SOME_DATA_MAP: Option<StableMap<SomeData>> = None;
static mut OTHER_DATA_VEC: Option<StableVec<OtherData>> = None;
#[init]
fn init() {
let alloc = StableMemoryAllocator::init();
let def_map = VariableDefinitionMap::init(alloc);
let some_data = StableMap::<SomeData>::init(def_map, "some_data_map");
let other_data = StableVec::<OtherData>::init(def_map, "other_data_vec");
unsafe {
SOME_DATA_MAP = Some(some_data);
OTHER_DATA_VEC = Some(other_data);
}
}
#[post_upgrade]
fn post_upgrade() {
let alloc = StableMemoryAllocator::reinit();
let def_map = VariableDefinitionMap::reinit(alloc);
let some_data = StableMap::<SomeData>::reinit(def_map, "some_data_map");
let other_data = StableVec::<OtherData>::reinit(def_map, "other_data_vec");
unsafe {
SOME_DATA_MAP = Some(some_data);
OTHER_DATA_VEC = Some(other_data);
}
}
// update functions work with SOME_DATA_MAP and OTHER_DATA_VEC variables
What’s also great with the approach of custom collections is that one could build a collection like AutoCertifiedHashMap which would automatically update a merkle-tree (or any other structure) and call set_certified_data() function. Such a collection could be used to store anything that needs to be verified somewhere else.
And with a great user experience.
Another way to use such a big HashMap is to make canister stable memory work much like Ethereum memory does. Just a big kv storage to use.
By the way, I don’t know if motoko is written in Rust, but if it is, it could use this same allocator to make seamless stable variables, which could hold not only sized data, but also any other data.
This is really interesting, thanks for sharing.
Given that stable memory will always be limited by per-subnet hardware and software requirements (currently 8 GB but supposed to be 300 GB one day), I wonder if it’s worth investing a bunch of effort down this route or whether it’s better to invest in multi-canister approaches, most notably an upgrade-tolerant BigMap.
The example I linked doesn’t show it, but theoretically you could have some index canister dynamically spin up a bunch of data bucket canisters (that clients can directly query), and have those data bucket canisters store their data in stable memory using high-level primitives like Motoko stable variables (not sure if there’s an equivalent of that in Rust).
That way, you’re not limited by 300 GB. You’re not even limited by a subnet so theoretically your BigMap could scale “infinitely” as the blockchain grows, and your data bucket canisters would be spun up on any subnet.
But IMO the difficulty here is managing cycles for multiple canisters and doing multi-canister upgrades. If your BigMap schema changes, how would you upgrade the canisters atomically and in what order? The problem is avoided with the stable memory allocator you started building here.
@diegop @akhilesh.singhania I wonder if you guys know why a more mature BigMap solution was deprioritized on DFINITY’s end? The stable memory increase does help but is only a stopgap. Does DFINITY expect the community to figure this out, or does the foundation have any plans to resume work on storage solutions that can scale infinitely? It seems pretty important. Thanks!
I believe Motoko is implemented in OCaml, so I don’t think it could use this same allocator unfortunately.
BTW what’s the difference between a “small stable vec” and “stable vec”? You mention per-message cycle limits, but I’m not sure I understand. Is the issue when a vector needs to be resized that the data needs to be copied over from the old memory to the new memory, and that copy operation is expensive?
Small vec is what I called the classic dynamic array. These arrays work because of reallocation. But since we’re limited by cycles for each message, large reallocations are not good for us. So these arrays could work, but only if they stay small.
Stable vec is a dynamic array based on a big hash map, but uses indices instead of keys. So this array should be able to handle much more data, than it’s small version.
What about BigMap - yea, it was a dream that never came true, unfortunately.
I haven’t read the whole thread yet, but based on my work on Sudograph GitHub - sudograph/sudograph: GraphQL database for the Internet Computer I believe SQLite would work pretty well within a canister.
Even without any indexing yet (so really bad O(n) searches) GraphQL queries with Sudograph don’t hit the query execution limit too easily. I don’t have benchmarks yet, but my intuition tells me SQLite would be able to scale to storing and efficiently querying through many many records.
Keep in mind that Sudograph is basically SQLite but using GraphQL as a query language. It uses an underlying simple relational database called Sudodb. IMO GraphQL provides a superior DX to traditional relational databases using SQL.
But, we will probably be implementing many database architectures on the IC. I think a robust SQLite implementation would be useful (and Sudograph could swap out Sudodb for it possibly, though probably wouldn’t).
The biggest problem we need to solve with our databases on the IC is scaling beyond the single canister limit.
6 Likes
Whoever makes native database on the IC Is going to make bank.
1 Like
does Sudograph already leverage stable memory?
Not yet, that’s the path we will probably pursue before any kind of multi-canister architecture.
Well, it leverages stable memory as in you can store the database in stable memory in a pre_upgrade and get it back in a post_upgrade, but it doesn’t use stable memory as the main memory for the database.
Thanks! yeah, I meant leveraging stable memory directly to be able to use more than 4GB and without expensive (de-) serialization on upgrades.
1 Like