Background
Motion 18337, which was adopted by the NNS over a year ago (September 3, 2021), proposes to increase the stable memory available to canisters from 4GiB to the full capacity of each subnetwork - currently around 350GiB. The first step towards implementing this proposal was to provide a 64-bit API for stable memory and increase the available stable memory to 8GiB. These changes were made generally available already on September 30, 2021. More recently, in October 2022, the size of stable memory available to a canister was quadrupled, from 8GiB to 32GiB.
In November 2021, DFINITY’s engineers discovered some performance issues that made it difficult to continue to increase the stable memory available to canisters. DFINITY’s new thinking was further clarified in a March 31, 2022 forum post. This forum post gives two reasons for the pause.
- Performance. Accessing stable memory has large overhead, as each call to the system API involves a context switch between the Wasm runtime (Wasmtime) and the replica code. Thus, stable memory better be backed by Wasm’s multiple memory and 64-bit features before increasing it further.
- Tooling. Developers need libraries and tools to make efficient use of stable memory. Different options are explored in this post.
Performance
DFINITY’s engineering teams are working on modifying stable memory to make use of Wasm’s proposed multiple memory functionality as explained in a recent Forum post. Multiple memories are already supported by Wasmtime, the Wasm runtime used by the IC. This change will be completely transparent to developers on the Internet Computer, i.e., the current interface to stable memory, namely ic0.stable[64]_{read|write|grow|size}
, will remain unchanged.
Stable memory will be mapped to Wasm memory number one, and this memory will typically be a 64-bit memory accessed using System API methods ic0.stable64_*
. Calls to these methods are translated into their Wasm bytecode equivalents (memory.copy), directly accessing memory number one. This translation happens when an IC-compatible Wasm module is installed in a canister. That is, the format of the Wasm module installed by developers will not change and will not make direct use of Wasm’s multiple memory facility. This is a good thing, as most programming languages that are used to generate Webassembly (e.g., Rust) are not able to generate code to access multiple memories.
In addition, if the change to multiple memories is adopted, the stable memory interface may be extended with methods to load and store individual bytes from stable memory locations. For example, a method ic0.stable64_loadi64 : (offset : i64) -> i64
could be added to load data from an offset to stable memory directly onto the Wasm stack.
Tooling
We now have two Wasm memories: the main Wasm heap (memory zero), which is cleared on upgrade, and stable memory (soon Wasm memory one), whose lifetime is the same as the canister’s. When the changes described above are implemented, the performance of using these memories will be similar, except for the performance difference between 32- and 64-bit memories. Developers are now faced with several choices regarding where to keep data and how and when to move data between memories. Some of the choices are described in this picture (describing the situation after stable memory is backed by Wasm’s multiple memory feature).
- The simplest approach (red) is simply keep data in Wasm memory zero using the native datatypes of the programming language compiler. The downside is that the canister cannot be upgraded. This method is (only) suitable for canisters that must never be upgraded, such as example code and very simple services.
- Another approach (blue), which is used by most canisters today, is to operate on data in Wasm memory zero using the native datatypes of the programming language compiler, serialize the values of all global variables to stable memory before upgrading the canister, and deserialize after the upgrade. Motoko uses this approach for its “stable” variables. The NNS canisters, written in Rust, also use this approach, with Protobuf as the stable format.
The naive (red) approach is typically ruled out as developers need to be able to upgrade their canisters. There are also several downsides to the save/restore approach.
- A canister cannot use more than 4GiB of memory unless 64-bit Wasm is enabled for main memory. However, enabling 64-bit Wasm for memory zero would be a big change to Motoko. Moreover, for all languages, the overhead of bounds checking would be incurred for every operation when using a 64-bit heap.
- The time spent serializing and deserializing during an upgrade is proportional to the size of the canister’s memory footprint. Thus, the serialization/deserialization steps, which happen in the pre- and post-upgrade hooks, can run out of cycles or main memory.
- Data structures with sharing or cycles are cumbersome to preserve across serialization and deserialization, and, thus, difficult to deal with during the upgrade.
- Developers that don’t use Motoko need to manually code the serialization and deserialization logic and make sure that the schema of the serialized data is compatible across upgrades. Bugs is this logic will likely lead to data loss.
Already today, developers can use the low-level API to access stable memory directly, and use this memory for any purpose. Some canisters have decided to keep all their persistent data in stable memory, e.g., the Internet Identity canister. Thereby, they do not require any pre- or post-upgrade hooks. This option is represented by green and yellow in the above picture. Improving the performance of stable memory access and increasing its size makes these approaches even more appealing. Thus, it is natural to ask the following question:
What is the best way to structure the raw bytes of stable memory?
The problem is not surprisingly similar to the problem faced by a traditional database when storing data to a file. The Internet Computer uses orthogonal persistence, so the lower level issues of mapping the file to memory, recovery and redundancy, synchronization and locking, etc., are taken care of by the protocol layer and the runtime, but the problem of how to organize structured data into linear memory remains the same.
One key decision is what data model to use for data stored in stable memory. This is a difficult choice, as it is not clear that there is a single data model that is optimal, or even suitable, for all applications. Moreover, it is a controversial topic and debates tend to degenerate into flame wars. Thus, I like to tread this ground carefully… For example, do we want to use
- a plain key-value store (e.g., Google Bigtable, Amazon DynamoDB), or
- the relational model (and SQL), or
- a graph model (like for the semantic web), or
- document model (e.g., used by MongoDB, often using JSON or XML),
- etc.
At the lowest implementation level, most data models are implemented on top of B-trees. A good example is the file format of SQLite. Thus, regardless of the data model preferred by canister developers, one good answer to the question is likely to be a collection of B-trees. Higher level abstractions can be built on top of this foundation. For this reason, DFINITY has developed a first version of a library (ic_stable_structures
) that helps developers organize a canister’s stable memory as a B-tree.
What will the canister programming model look like?
First, a canister’s global variables would be mapped to either Wasm globals or to stable memory through some indirection (e.g., pointers) that are stored in Wasm globals or main memory. Wasm globals are limited to Wasm’s native data types (i32
and i64
), and of limited utility on their own. Global variables are often containers (e.g., a plain key value store), and these map nicely to B-trees stored in stable memory. A similar approach can be used for more abstract data models. For example, if the relational model is adopted, a global variable would represent a relvar which, in turn, is backed by a B-tree, or several B-trees if the relvar is indexed. Similarly, in the graph model, global variables would probably correspond to verbs, each backed by a B-tree, or by two B-trees if the underlying binary relation is navigable in both directions.
What happens to global variables (containers stored in stable memory) when a canister is upgraded? I propose the following lifecycle of global variables and their backing B-trees.
- The canister is upgraded and the new version starts using a new global variable, which starts as an empty container (or relvar, verb, etc.).
- Developers decide that the variable is no longer needed in its current form. It is deprecated and made read only. Perhaps the canister has a field for user address that started as a free form string and must be migrated to structured form with street address, number, and postal code. The old address field can be deprecated and only read by the upgraded canister, but never written.
- When a variable has been deprecated for a while, the canister may stop using it entirely. For example, once the addresses of all users have been to the new format, the address field is no longer used.
- Finally, once it has been confirmed that the new address solution is satisfactory, the old address field can be permanently removed from the canister’s stable memory. This would be a manual step; that is, the state of the variable is not automatically removed just by upgrading the canister code to a version that no longer uses it.
This lifecycle works when all (container) global variables of a canister are stored in stable memory, but it also extends to the case when each global variable is stored in its own Wasm memory. That is, as a future extension of stable memory, the Internet Computer may provide a canister with any number of memories, each containing a single global variable. This would simplify some operations, but it is also more difficult to implement in the replica software.
In summary, global variables are backed by B-trees (perhaps with a layer of abstraction in between) stored in stable memory, ought to be key components of the programming model. The set of global variables used by a canister can evolve according to the lifecycle described above.
What to store in B-tree cells?
The key of a global (container) variable is usually a simple data type, like an integer or a string, but the value can often be a more complex data structure, like a record representing a user or some other entity.
Option #1 (yellow above). Copy data between the main Wasm heap (0) and stable memory (1) when reading or writing cell values. The format of values can be Candid, Protobuf, or even JSON. That is, any format that supports schema evolution.
Option #2. Avoid copying data between the main Wasm memory and stable memory. If the stable memory interface is extended with methods to load and store individual bytes, data can be moved directly from stable memory to the Wasm stack, without going through the main Wasm heap.
- Option #2A. Use a format, such as flatbuffers, that supports both schema evolution and access paths with minimal indirection.
- Option #2B (green above). Store data directly in the cell values without support for schema evolution. For example, this method is used when the cell value is a single fixed size integer (like Rust’s u64) or a struct of such values.
Ease of implementation | Performance | Supports schema evolution of the value | |
---|---|---|---|
Option #1 | Better | Good | Yes |
Option #2A | Good | Better | Yes |
Option #2B | Best | Best | No |
The comparison table shows that there is no obvious best choice. The problem with Option #2B is that it does not support schema evolution of the value type. This can be alleviated by replacing a single global variable which is a collection of structs with several global variables each being collections of simple data types. For example, instead of one global variable which is a map from user ID to a struct consisting of a name and an age, use two global variables, one map from user ID to name and one from user ID to age. That is, store data by column instead of by row. This way, schema evolution of the value is no longer necessary. On the other hand, performance may suffer, depending on the access pattern.
How to avoid problems when upgrading canisters?
To safely upgrade a canister, the developers must ensure that the data schema (A) pre-upgrade and the data schema (B) post-upgrade are compatible. In most cases, developers would want the compatibility to be in both directions so that a rollback is possible if issues are detected post-upgrade.
Developing the necessary tooling is not a small task, even for the simple key-value store. And it becomes increasingly more complex for more complex data models. For example, the tooling could check schema compatibility in the post-upgrade hook to ensure that an upgrade doesn’t go through if schema (B) is not compatible with schema (A).
Here we also face the dilemma of standardization vs. adaptation: with a standard schema language, developers can have greater confidence that their canisters can be upgraded in the future; with many competing standards, novel features are likely to reach developers faster.
One approach is to directly use SQLite to access stable memory, as was proposed on this Forum in December 2021. This would imply specific answers to all questions raised in this post: bytes in stable memory would verbatim follow SQLite’s file format; the programming model would most likely use sqlite3_{prepare|bind*|step|reset}
to interact with stable memory; and the format of cells/columns is also specified by SQLite. Data would be moved between stable and main memory by the page cache of SQLite and, thus, employ a variant of Option #1 (yellow).
Questions to the community:
- Are there additional concerns that I have overlooked?
- What data model or data models do developers want to see supported for canister development?
- Is SQLite backed by stable memory something that the community is interested in exploring further?
- Would the community like to see NNS Motions on topics relating to stable memory and data models on the Internet Computer?