Introduction

Background

Smart contracts on the Internet Computer are referred to as canisters.

Canisters, compared to traditional smart contracts, have some unique properties including:

Mutability: A canister can have a set of controllers, and controllers are able to upgrade the code of the canister (e.g., to add new features, fix bugs, etc.)

Scale: Canisters have access to hundreds of gigabytes of memory and ample amounts of compute, allowing developers to build fully functioning dapps without relying on external cloud providers.

The Challenge of Upgrades

When upgrading a canister, the canister's code is replaced with the new code. In Rust, the new version of the code is not guaranteed to understand the memory layout established by the previous version. This is because Rust's memory layout can change between different versions of the code, making it unsafe to directly access the old memory layout. Therefore, by default, when a canister is upgraded and a new module is installed, the canister's main memory is wiped.

To persist state, the Internet Computer provides canisters with an additional memory called stable memory. The conventional approach to canister state persistence follows these steps:

1. Serialize and store the state of the canister just before the upgrade using the pre_upgrade hook.
2. Install the new Wasm module of the canister (and wipe out the canister's main memory).
3. Deserialize the data that was stored in stable memory in step 1 using the post_upgrade hook.

This approach is easy to implement and works well for relatively small datasets. Unfortunately, it does not scale well and can render a canister non-upgradable.

The Solution: Stable Structures

Rather than using standard Rust data structures, which store their data in the canister's main memory, you can use stable structures. Stable structures are designed to use stable memory as the primary storage, allowing them to grow to gigabytes in size without the need for pre_upgrade/post_upgrade hooks. This is the key characteristic that distinguishes stable structures from Rust's standard data structures.

Design Principles

The library is built on several key principles:

• Radical simplicity: Each data structure follows the most straightforward design that solves the problem at hand. This makes the code easier to understand, debug, and maintain.

• Backward compatibility: Upgrading the library version must preserve the data. All data structures have a metadata section with the layout version, ensuring that new versions can read data written by old versions.

• No pre_upgrade hooks: A bug in the pre_upgrade hook can make your canister non-upgradable. The best way to avoid this issue is not to have a pre_upgrade hook at all.

• Limited blast radius: If a single data structure has a bug, it should not corrupt the contents of other data structures. This isolation helps prevent cascading failures.

• No reallocation: Moving large amounts of data is expensive and can lead to prohibitively high cycle consumption. All data structures must manage their memory without costly moves.

• Compatibility with multi-memory WebAssembly: The design should work when canisters have multiple stable memories. This ensures future compatibility with upcoming IC features.

Available Data Structures

The library provides several stable data structures:

• Cell: For small single values that change rarely
• BTreeMap: A key-value store that maintains keys in sorted order
• BTreeSet: A set of unique elements
• Vec: A growable array
• Log: An append-only list of variable-size entries
• MinHeap: A priority queue

Concepts

This section covers fundamental concepts for understanding how stable structures work and how they can be used effectively and safely.

The Memory Trait

Stable structures are responsible for managing their own memory. To provide maximum flexibility, the library introduces the Memory trait:

#![allow(unused)]
fn main() {
pub trait Memory {
    /// Equivalent to WebAssembly memory.size.
    fn size(&self) -> u64;

    /// Equivalent to WebAssembly memory.grow.
    /// Returns the previous size, or -1 if the grow fails.
    fn grow(&self, pages: u64) -> i64;

    /// Copies bytes from this memory to the heap (in Wasm, memory 0).
    /// Panics or traps if out of bounds.
    fn read(&self, offset: u64, dst: &mut [u8]);

    /// Writes bytes from the heap (in Wasm, memory 0) to this memory.
    /// Panics or traps if out of bounds.
    fn write(&self, offset: u64, src: &[u8]);
}
}

The Memory trait intentionally models a WebAssembly memory instance. This design choice ensures consistency with the interface of memories available to canisters. It also provides future compatibility with potential multi-memory support in canisters.

Panics

⚠️ read and write assume the caller will not access memory outside the current size.

If the range [offset … offset + len) exceeds available memory, the call panics (in native tests) or traps (in a Wasm canister). Callers must store and check data lengths themselves or use higher-level containers such as StableVec.

Available Memory Implementations

The library provides several implementations of the Memory trait, each designed for specific use cases:

• Ic0StableMemory: Stores data in the Internet Computer's stable memory
• VectorMemory: An in-memory implementation backed by a Rust Vec<u8>
• DefaultMemoryImpl: A smart implementation that automatically selects the appropriate memory backend:
  • Uses Ic0StableMemory when running in an Internet Computer canister (wasm32 target)
  • Falls back to VectorMemory in other environments (like tests or non-IC contexts)

Additional implementations such as FileMemory and RestrictedMemory exist but are less commonly used.

Usage Example

Here's how to initialize a stable BTreeMap using DefaultMemoryImpl:

#![allow(unused)]
fn main() {
use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};
let mut map: BTreeMap<u64, u64, _> = BTreeMap::init(DefaultMemoryImpl::default());
}

While the above example works correctly, it demonstrates a potential issue: the BTreeMap will use the entire stable memory. This becomes problematic when trying to use multiple stable structures. For example, the following code will fail in a canister:

#![allow(unused)]
fn main() {
use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};
let mut map_1: BTreeMap<u64, u64, _> = BTreeMap::init(DefaultMemoryImpl::default());
let mut map_2: BTreeMap<u64, u64, _> = BTreeMap::init(DefaultMemoryImpl::default());

map_1.insert(1, 2);
map_2.insert(1, 3);
assert_eq!(map_1.get(&1), Some(2)); // This assertion fails.
}

The code fails because both map_1 and map_2 are using the same stable memory. This causes changes in one map to affect or corrupt the other.

To solve this problem, the library provides the MemoryManager, which creates up to 255 virtual memories from a single memory instance. We'll explore this solution in the next section.

Memory Manager

As mentioned in the previous section, each stable structure requires its own dedicated Memory instance. This is an intentional design decision that limits the blast radius of potential bugs, ensuring that issues only affect the specific stable structure and its associated memory, not other stable structures.

Overview

The Memory Manager enables the creation of up to 255 virtual memories from a single underlying memory instance. When used with stable memory, this allows you to maintain up to 255 separate stable structures, each with its own isolated memory space.

Usage Example

The following example demonstrates how to use the Memory Manager to create multiple stable structures:

#![allow(unused)]
fn main() {
use ic_stable_structures::{
   memory_manager::{MemoryId, MemoryManager},
   BTreeMap, DefaultMemoryImpl,
};

// Initialize a MemoryManager with DefaultMemoryImpl as the underlying memory
let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());

// Create two separate BTreeMaps, each with its own virtual memory
let mut map_1: BTreeMap<u64, u64, _> = BTreeMap::init(mem_mgr.get(MemoryId::new(0)));
let mut map_2: BTreeMap<u64, u64, _> = BTreeMap::init(mem_mgr.get(MemoryId::new(1)));

// Demonstrate independent operation of the two maps
map_1.insert(1, 2);
map_2.insert(1, 3);
assert_eq!(map_1.get(&1), Some(2)); // Succeeds as expected
}

Schema Upgrades

Stable structures store data directly in stable memory and do not require upgrade hooks. Since these structures are designed to persist throughout the lifetime of the canister, it's nearly inevitable that developers would want to make modifications to the data's schema as the canister evolves.

Let's say you are storing assets in your canister. The declaration of it can look something like this:

#![allow(unused)]
fn main() {
#[derive(Serialize, Deserialize, CandidType)]
struct Asset {
    // The contents of the asset.
    contents: Vec<u8>,
}

impl Storable for Asset {
    fn to_bytes(&self) -> std::borrow::Cow<'_, [u8]> {
        let mut bytes = vec![];
        ciborium::ser::into_writer(&self, &mut bytes).unwrap();
        Cow::Owned(bytes)
    }

    fn into_bytes(self) -> Vec<u8> {
        let mut bytes = vec![];
        ciborium::ser::into_writer(&self, &mut bytes).unwrap()
    }

    fn from_bytes(bytes: std::borrow::Cow<[u8]>) -> Self {
        ciborium::de::from_reader(&*bytes).expect("deserialization must succeed.")
    }

    const BOUND: Bound = Bound::Unbounded;
}
}

Note: Stable structures do not enforce a specific data format. It's up to the developer to use the data format that fits their use-case. In this example, CBOR is used for encoding Asset.

Adding an attribute

Adding a new field can be as simple as adding the field, like this:

#![allow(unused)]
fn main() {
#[derive(Serialize, Deserialize)]
struct Asset {
    // The contents of the asset.
    contents: Vec<u8>,

    // The timestamp the asset was created at.
    #[serde(default)]
    created_at: u64,
}
}

If the new attribute being added doesn't have a sensible default value, consider wrapping it in an Option:

#![allow(unused)]
fn main() {
#[derive(Serialize, Deserialize, CandidType)]
struct Asset {
    // The contents of the asset.
    contents: Vec<u8>,

    // The timestamp the asset was created at.
    #[serde(default)]
    created_at: u64,

    // The username of the uploader.
    uploaded_by: Option<String>,
}
}