Abstract away the 4GB canister memory limit

Developers
#1

The 4GB memory limit on canisters is one of the major complications I’m running into while building on top of the Internet Computer, especially while building fundamental infrastructural tools.

Orthogonal persistence is a beautiful dream, but the memory limit and the necessity of splitting data structures and apps across multiple canisters for scaling…somewhat hinders that dream.

I’m wondering if it would be possible for this limit to be abstracted away below the canister level, so that it is not exposed to developers. Considering that the limit has to be dealt with somewhere, it seems an explicit choice was made to let the developers deal with it. If we can deal with it as developers, then couldn’t the platform also deal with it, but perhaps in a more generalized manner?

If this is at all possible, I believe it would truly simplify so many things for developers for years to come.

I of course don’t know much about the internals of the system, but couldn’t something like virtual memory on our operating systems work for canisters? Instead of canisters directly accessing Wasm module memory, perhaps a virtual memory system could be created that automatically scales up and down according to the needs of canisters, and canisters could interact directly with that virtual memory system.

It would just be such a dream to create something like a HashMap, and just keep pumping values into it forever without any thought to 4GB limits and cross-canister calls and managing all of that craziness.

14 Likes
"No databases" vs BigMap vs orthogonal persistence
What needs to be done to ensure the scalability of Internet Computer apps?
#2

That limit is imposed by the state of affair in WebAssembly, and we might find a solution there, too, in the future. All of these proposals might allow a canister to store more than fits in to a single 32 bit memory somehow:

Although it will take a while until the IC supports a new Wasm feature, as we have to wait for all our dependencies that deal with Wasm to support it.

5 Likes
#3

It seems like the limit could still be abstracted away by DFINITY. Are you saying that because this limit will likely be addressed by a future Wasm feature, DFINITY is choosing to wait for that and not to abstract it away in the meantime?

In the days of 32-bit operating systems, the 4GB process address space limitation could be worked around (e.g., spawn a separate process), but it was a pain. But that was merely a memory limit, you still had the whole hard drive to store data on. A 4GB limit for both memory and storage (persistent memory), if you require more than that, is even more of a challenge to deal with.

3 Likes
#4

In the days of 32-bit operating systems, the 4GB process address space limitation could be worked around (e.g., spawn a separate process), but it was a pain. But that was merely a memory limit, you still had the whole hard drive to store data on.

Sounds like how I interpret the point of BigMap: to be the ‘hard drive’/filesystem where you have the ‘whole internet computer to store data on’. i.e. how the filesystem for that hard drive is a bit like a Map with keys like /path/to/file.

One important difference: a physical hard drive still has a relatively low size limit, and I/O limitations as long as its on the same physical disk. A distributed data structure on IC will likely have different performance characteristics/limitations than a hard drive, for better or worse.

1 Like
#5

It would just be such a dream to create something like a HashMap, and just keep pumping values into it forever without any thought to 4GB limits and cross-canister calls and managing all of that craziness.

IMO everyone should depend on an abstract Map type that can be satisfied by a HashMap for now and BigMap when ready for primetime. The exact Map can be dependency injected with various implementations in the future (depending on tradeoffs desired, e.g. redundancy/cost/latency).

#6

I don’t think BigMap works well for @lastmjs’s use case.

#7

I guess I’m talking more about the development experience when implementing something like BigMap. There are many other scalable data structures we’ll need in the future for the IC to support many varying use cases, and the developers of each of those data structures will always have to deal with the canister limit. But, if the memory was scaled automatically for the user by the system, then that complexity would disappear for the developer to a large extent (hopefully).

3 Likes
#8

I guess it’s expected that authors of low-level libraries (e.g. a BigMap like thing) will have to deal with certain complexities so that their users don’t have to – if there weren’t these complexities, you woudn’t need someone to write a library, right? :slight_smile:

Even if the system would allow you to scale your memory beyond 4GB (actually 8GB if you count the stable memory, which is in a way an anticipation of the world with multiple memories), this would still be limited by the capacity of a subnet. Only scaling across multiple canisters will give you something that could possibly be considered “infinitely scaleable”.

5 Likes
#9

The 4GB memory limit is becoming more and more of an issue: https://twitter.com/lastmjs/status/1402652679889899526?s=20

I really think the IC needs to implement some form of infinite or unbounded virtual memory.

I guess it’s expected that authors of low-level libraries (e.g. a BigMap like thing) will have to deal with certain complexities so that their users don’t have to – if there weren’t these complexities, you woudn’t need someone to write a library, right?

Exactly, and I believe that the IC protocol developers have an amazing opportunity to do low-level work that deals with certain complexities so that their users don’t have to. The canister memory limit is a major complexity that all developers (the users) of the IC now have to deal with.

And if we have the opportunity to not require library developers to deal with the complexity of multi-canister scaling, then that will be a major win. Library developers should deal with the necessary issues that underlying platforms and environments don’t address, and I would just like to press for the IC devs to address the memory limits of canisters.

What’s sad is that because no general-purpose multi-canister scaling solution exists, I have to limit the potential of Sudograph in people’s minds as I’m explaining it to them. And to make Sudograph scale across canisters it is going to take me or others a significant amount of work. I doubt even something like BigMap will be sufficient, though it could help.

wasm64 and multiple memories may help to increase the canister memory limit, but I also believe we could implement virtual memory that the protocol takes care of itself. This would really help us achieve the original vision of deploying apps to an infinitely scalable virtual machine with the best developer experience possible. the 4GB canister limit hinders that vision in a major way.

4 Likes
#10

Hi @lastmjs, I’m Sasha, I wrote the first (and the latest) Rust implementation of BigMap.
Can you please provide a bit more details on why do you feel that BigMap wouldn’t be sufficient for Sudograph (also, what is Sudograph?). If you have a link to a doc or a post, that would also work.
This way we might be able to come up with a design that works better for you.

Thanks!

2 Likes
#11

Oh, just found this link GitHub - sudograph/sudograph: GraphQL database for the Internet Computer, but more info on the perceived limitations of BigMap would be great.

#12

Let me know if I am getting any of this wrong, but BigMap will be a simple key-value store. What type of ordering will be possible with BigMap? Can you order the keys? Even without different types of ordering, BigMap will be excellent for some use cases, but not for many others.

Sudograph needs a scalable relational database under-the-hood, and thus it needs data structures beyond simple key-value stores. I am using Rust BTreeMap’s right now, and to implement indexing to get efficient querying I believe BTree or B+Trees will be required. Other data structures will probably be required for other use cases, to get the required efficiency based on the read/write requirements of applications. I am focusing on simple relational data for now, but you can imagine use cases that require other data structures.

Basically a simple key-value store without many different ways to order keys is very limiting. We are going to have to come up with a variety of “Big” libraries to get the scalability that we want with the data structures that we need. Virtual memory I am hoping would address all of these issues without requiring application developers to come up with libraries for every unique need.

2 Likes
#13

Also, BigMap provides no complex querying nor relational capabilities, it is inadequate for anything but the simplest key-value experience. Sudograph uses a relational database called Sudodb under-the-hood, that’s where I’ve taken BTreeMap’s to create the relational capabilities i.e. give me all users where the username startsWith foo…not possible with BigMap or BigSearch unless I am mistaken.

2 Likes
#14

@lastmjs Totally agree that BigMap has a limited use case, and that doing anything that requires relating data stored in the DB will require a relational approach. I also think that storing sequential data (very huge logs, as an example) is a compelling use case that BigMap doesn’t naturally address either.

I’m interested to see how well the GraphQL model fits different applications.

As a person who expects to produce a lot of Candid data in the future, I’m doing a side project here (slowly) that tries to support that niche use case, with plans of supporting relational queries and other things one would expect from a database with search, join, and indexes-as-data. I will continue to watch what happens with your sudograph and sudodb projects, for inspiration.

4 Likes
#15

You are right, BigMap is supposed to be a simple key-value store. In the current implementation the objects are ordered (using BTreeMap) but based on the sha256 of the key, so the keys themselves are not ordered. And I agree that ordered keys can be useful for some applications.

Virtual memory is appealing (just as the orthogonal persistence model), but it also has some serious issues. For instance, to avoid reinventing the wheel developers will likely rely on stdlib data structures, just as you did – e.g. use BTreeMap. It’s robust, relatively performant, general enough etc. However, these stdlib data structures are not built with the orthogonal persistence use, and their implementation may change between Rust versions. There is absolutely no guarantee (or information) on the bit-wise operations and behind-the-scenes implementation of these data structures. So these data structures cannot be safely used for Orthogonal Persistence and we will have to come up with all sorts of libraries. Essentially re-inventing the stdlib for Rust.
And that brings us to another problem, which is the forwards and backwards compatibility of these libraries. And testing. It will be fun.

Anyway, that’s the background of why we have only a simple key-value store so far. That’s easy to implement and applicable in many use cases and many domains. We will likely add more data structures in the future. But the easiest IMHO would be to build them on top of BigMap, if possible, to leverage the BigMap scaling functionality.

Is it possible? How applicable BigMap really is? We’ll have to see as time goes.
In BigMap the objects can be read or written at a given offset. Like files. Would that be enough to build a VM abstraction that you need?
Something like the following: You map the [0…1) GB of your VM indirection layer to a BigMap object called “chunk00”, then [1…2) GB to object called “chunk01”, and so on. That already gives us a 100GB address space, and would scale to an arbitrary size.

1 Like
#16

I’ve seen various discussions about BigMap but I was under the impression that it’s not publicly available.

This thread suggests that it’s available somewhere but I’ve come across other threads where people are asking where it find it too.

Is anyone able to comment on that?

#17

It’s not (yet) publicly available. The code needs to be cleaned up before open sourcing.

2 Likes
#18

I posted on the wasm64 github asking about an ETA;

To which it was said that

Rust Wasm seems to support it now, but that’s just the compiler, probably not in any bindings yet.

Not sure what IC tools it relies on but perhaps someone can reply to the github issue.

1 Like
#19

I believe the IC uses wasmtime, and I’ve asked on the repo: wasm64 support · Issue #572 · bytecodealliance/wasmtime · GitHub

Seems like someone needs to just implement wasm64!

#20

Disclaimer: the opinions below are my own, not official DFINITY position.

I think Wasm32 has some benefits:

  1. Your program might end up using significantly less memory because all the pointers and sizes occupy 4 bytes, not 8 bytes. At least that’s what people observed when they started to recompile old 32bit applications for 64bit platforms a decade ago.
  2. The Wasm compiler can generate much more efficient code because there is no need to do bounds checking on every memory access. This only works because the replica can fully embed canister memory into its address space. This won’t fly with Wasm64. For developers, efficient execution = cheaper gas on average. This point might become less important once Wasm bulk memory operations proposal is adopted.

64-bit address space would indeed allow you to store more, but probably not orders of magnitude more. I don’t think there can be a general solution that would allow one to scale linear memory across multiple subnets, for example, that would require some very complicated and expensive mechanisms.

Upgrades are another big factor. When you deploy a new version of your canister, the whole linear memory is discarded. We do it because if you change your program a bit and recompile, the effects on the memory layout are unpredictable. We experimented with deploying minimal changes (add one function call) without discarding the linear memory, with no success. Upgrade instruction limit will not allow one to shift around gigabytes of data when you deploy a new version of your canister, so using linear memory only for transient data is probably the way to go for canisters that need to handle large amounts of data.

Scaling stable memory to larger sizes is straightforward with the current implementation of the replica and I won’t be surprised if this happens quite soon. This will require new efficient approaches to working with stable memory directly instead of using canister linear memory as the main data storage. We’re working hard to provide an efficient and easy to use solution to that problem.

As a canister developer myself (I worked, e.g., on certified assets canister and internet identity backend), I’m not particularly concerned about the 4GiB linear memory limit. If the stable memory restrictions are lifted, you’ll be able to utilize most of the subnet TPS capacity with just a single canister. And if you need more capacity, you’ll probably have to plan for a multi-subnet multi-canister setup anyways, and a huge address space won’t help you much here.

9 Likes