b3-stable-structures 0.5.9

A collection of data structures for fearless canister upgrades.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

<p>
  <a href="https://crates.io/crates/b3-stable-structures"><img alt="Crate Info" src="https://img.shields.io/crates/v/b3-stable-structures.svg"/></a>
  <a href="https://github.com/dfinity/stable-structures/blob/master/LICENSE"><img alt="Apache-2.0" src="https://img.shields.io/github/license/dfinity/stable-structures"/></a>
  <a href="https://docs.rs/b3-stable-structures"><img alt="API Docs" src="https://img.shields.io/badge/docs.rs-ic--stable--structures-blue"/></a>
  <a href="https://forum.dfinity.org/"><img alt="Chat on the Forum" src="https://img.shields.io/badge/help-post%20on%20forum.dfinity.org-blue"></a>
</p>

# Stable Structures

A collection of scalable data structures for the [Internet Computer](https://internetcomputer.org) that persist across upgrades.

Stable structures are designed to use stable memory as the backing store, allowing them to grow to gigabytes in size without the need for `pre_upgrade`/`post_upgrade` hooks.

## Background

The conventional approach to canister state persistence is to serialize the entire state to stable memory in the `pre_upgrade` hook and decode it back in 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.

This library aims to simplify managing data structures directly in stable memory.
For more information about the philosophy behind the library, see [Roman's tutorial on stable structures](https://mmapped.blog/posts/14-stable-structures.html).

## Available Data Structures

- [BTreeMap]: A Key-Value store
- [Vec]: A growable array
- [Log]: An append-only list of variable-size entries
- [Cell]: A serializable value
- [MinHeap]: A priority queue.

## How it Works

Stable structures are able to work directly in stable memory because each data structure manages
its own memory.
When initializing a stable structure, a memory is provided that the data structure can use to store its data.

Here's a basic example:

```rust
use b3_stable_structures::{ BTreeMap, DefaultMemoryImpl };
let mut map: BTreeMap<u64, u64, _> = BTreeMap::init(
  DefaultMemoryImpl::default()
);

map.insert(1, 2);
assert_eq!(map.get(&1), Some(2));
```

Memories are abstracted with the [Memory] trait, and stable structures can work with any storage
backend that implements this trait.
This includes stable memory, a vector ([VectorMemory]), or even a flat file ([FileMemory]).

The example above initializes a [BTreeMap] with a [DefaultMemoryImpl], which maps to stable memory when used in a canister and to a [VectorMemory] otherwise.

Note that **stable structures cannot share memories.**
Each memory must belong to only one stable structure.
For example, this fails when run in a canister:

```no_run
use b3_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.
```

It fails because both `map_1` and `map_2` are using the same stable memory under the hood, and so changes in `map_1` end up changing or corrupting `map_2`.

To address this issue, we make use of the [MemoryManager](memory_manager::MemoryManager), which takes a single memory and creates up to 255 virtual memories for our disposal.
Here's the above failing example, but fixed by using the [MemoryManager](memory_manager::MemoryManager):

```rust
use b3_stable_structures::{
  memory_manager::{ MemoryId, MemoryManager },
  BTreeMap,
  DefaultMemoryImpl,
};
let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
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))
);

map_1.insert(1, 2);
map_2.insert(1, 3);
assert_eq!(map_1.get(&1), Some(2)); // Succeeds, as expected.
```

## Example Canister

Here's a fully working canister example that ties everything together.

Dependencies:

```toml
[dependencies]
ic-cdk = "0.6.8"
ic-cdk-macros = "0.6.8"
b3-stable-structures = "0.5.6"
```

Code:

```rust
use b3_stable_structures::memory_manager::{
  MemoryId,
  MemoryManager,
  VirtualMemory,
};
use b3_stable_structures::{ DefaultMemoryImpl, StableBTreeMap };
use std::cell::RefCell;

type Memory = VirtualMemory<DefaultMemoryImpl>;

thread_local! {
  // The memory manager is used for simulating multiple memories. Given a `MemoryId` it can
  // return a memory that can be used by stable structures.
  static MEMORY_MANAGER: RefCell<MemoryManager<DefaultMemoryImpl>> =
    RefCell::new(MemoryManager::init(DefaultMemoryImpl::default()));

  // Initialize a `StableBTreeMap` with `MemoryId(0)`.
  static MAP: RefCell<StableBTreeMap<u128, u128, Memory>> = RefCell::new(
    StableBTreeMap::init(
      MEMORY_MANAGER.with(|m| m.borrow().get(MemoryId::new(0)))
    )
  );
}

// Retrieves the value associated with the given key if it exists.
#[ic_cdk::query]
fn get(key: u128) -> Option<u128> {
  MAP.with(|p| p.borrow().get(&key))
}

// Inserts an entry into the map and returns the previous value of the key if it exists.
#[ic_cdk::update]
fn insert(key: u128, value: u128) -> Option<u128> {
  MAP.with(|p| p.borrow_mut().insert(key, value))
}
```

### More Examples

- [Basic Example](https://github.com/dfinity/stable-structures/tree/main/examples/src/basic_example) (the one above)
- [Quickstart Example](https://github.com/dfinity/stable-structures/tree/main/examples/src/quick_start): Ideal as a template when developing a new canister
- [Custom Types Example](https://github.com/dfinity/stable-structures/tree/main/examples/src/custom_types_example): Showcases storing your own custom types

## Combined Persistence

If your project exclusively relies on stable structures, the memory can expand in size without the requirement of `pre_upgrade`/`post_upgrade` hooks.

However, it's important to note that if you also intend to perform serialization/deserialization of the heap data, utilizing the memory manager becomes necessary. To effectively combine both approaches, refer to the [Quickstart Example](https://github.com/dfinity/stable-structures/tree/main/examples/src/quick_start) for guidance.