ic-stable-memory Under The Hood
In this article we'll discuss, how does the ic-stable-memory library work internally. For the introduction to this rust library, please check this article.
Memory allocation
First of all, it is important to say, that ic-stable-memory does not only provide you with stable collections, but it also provides you with a complete stable memory management system. The core of this system is a custom stable memory allocator.
This allocator is responsible for allocating, accounting and deallocating of stable memory for the application. Technically speaking, this allocator is a segregated free-list allocator - all the free blocks of memory are stored in multiple lists, where each such a list is responsible for only storing free blocks of some particular size.
What's interesting about this allocator is that it can address 64-bits of space, while only using 32-bits blocks of data. This means that we can use it even in 32-bit environment, like wasm32.
When you want to allocate a new stable memory block of some size, it will first look into the free-list that may already contain an appropriate block.
- If there is such a free block, then it will just mark this block as allocated, remove it from the free-list and return a smart-pointer to that block.
- If there is no such a free block, then it will search for any free-block of bigger size.
- If there is such a bigger block, the allocator will split it in two smaller blocks and repeat the process.
- There is always such a bigger block, since the allocator will always make sure there is at least some amount (10MB by default) of memory available to your canister. If, during this pre-allocation procedure, the allocator discovers that the canister is short on stable memory (stable::grow() returned the OutOfMemory error), it will call a special on_low_stable_memory() function of your canister and continue to work as before. It is your responsibility to define this function in order to react to memory shortage.
When you want to deallocate a block of stable memory, the allocator will mark this block as free and try to merge it with it's neighbors.
- If there are free neighbor blocks, they will be merged into a block of bigger size and maybe reassigned to another free-list.
- If there are no free neighbor blocks, our free block will just be placed to the appropriate free-list.
While this allocator does some work to make fragmentation less significant, it does not prevent it completely. So, keep in mind, that you may loose some of your stable memory after some time of active usage (but if you don't delete your data ever - you're fine).
ic-stable-memory exposes a set of basic functions so you could use this allocator in your application:
- init_allocator(u64) - initializes the allocator at the provided index in the stable memory; this function is intended to be called only once in the init() method of your canister; the stable memory index you provide should be already available to the canister (see stable::grow() documentation);
- reinit_allocator(u64) - re-initializes the allocator after canister upgrade; this function is intended to be called in each post_upgrade() hook of the canister;
- allocate<T>(usize) -> Result<SSlice<T>, OutOfMemory> - allocates a single memory block; note that max size of each such block is 2^32; returns an unsafe smart-pointer to this memory block;
- deallocate<T>(SSlice<T>) - frees a memory block, making the underlying memory available for the allocator;
- reallocate<T>(SSlice<T>, usize) -> Result<SSlice<T>, OutOfMemory> - tries to make a memory block bigger than it is now;
- get_allocated_size() -> u64 - tells, how many bytes of available stable memory is used for storing data;
- get_free_size() -> u64 - tells, how many bytes of available stable memory is free; basically, it tells you how much data you can store, before the allocator will try to stable::grow() again.
You can use these low-level functions in order to build anything you want - for example, custom data collections. But there is a simpler way to interact with stable memory in order to build something on top of it - smart-pointers.
Smart-pointers
In ic-stable-memory, you use smart-pointers in order to access the stable memory. At this moment, there are only two of them:
SSlice
This is a simple abstraction over a stable memory block (a slice of stable memory, basically). With this smart-pointer you are only able to read/write byte arrays. It is absolutely unsafe, and all of it's APIs are protected. Don't use this smart-pointer, unless you know what you're doing.
SUnsafeCell
This smart-pointer is basically the same as common UnsafeCell from Rust's standard library. It allows you to allocate any Speedy-serializable struct to stable memory and then read and update this struct. Also, this smart-pointer is Speedy-serializable itself, so you can store it in stable memory as any other data. In that case, it will be serialized as a simple pointer (u64 number).
Reading the data from SUnsafeCell is safe (since it returns a fresh copy each time you read it), updating is unsafe, but you still can update it, if you ensure that there is no other copy of this smart-pointer exists (including copies which are stored in stable memory). This is crucial, because during an update, the new data can be too big for a memory block, so a reallocation would occur. A reallocation can change the pointer to your data (since it can reallocate a memory block in some other random location). If that happens, and you have a copy of this smart-pointer stored somewhere else (for example, in some stable collection), this copy won't point to the correct location anymore, so you have to update all copies of it to match a new pointer. If you do update these copies (or you have no copies at all) - it is safe to update the data that the smart-pointer holds.
Here is the API list of this SUnsafeCell:
- new(&T) -> SUnsafeCell<T> - stores the provided data to stable memory; T implements speedy::Readable and speedy::Writable basically this function just serializes the provided data with candid-encoding, allocates a new memory block big enough for this encoded data, stores the encoded data and returns back the pointer to the memory block;
- get_cloned() -> T - returns a copy of underlying data;
- unsafe set(&T) -> bool - tries to update the data; returns true if a reallocation happened and you have to update all the copies of this smart-pointer, if you have them;
- drop() - frees the underlying memory block (deallocates it).
Stable collections
So, stable collections (SVec and SHashMap) are just data structures implemented using stable smart-pointers. What's important is that since these collections are intended to store a lot of data, they are implemented sacrificing performance in favor of scalability in conditions of message gas limits. It means, that if there was a choice between "make it faster" and "make it so it never crashes because of gas limits", this choice was always made in favor of the latter. Here is an overview of some of the implementation's limits.
SVec
For example, unlike a standard Vec, SVec does not reallocate itself, when its capacity is reached. Instead, SVec just allocates a new memory block (which is called SVecSector) and stores new data there. So, basically, SVec is just a concatenation of multiple sectors.
In order to provide constant time search, SVec constraints sizes of its sectors to some pre-defined ones (powers of 2 starting from 2^2 up to 2^29, 27 sectors total; each next sector has a constant size of 2^29). This constraint allows constant time formula-based internal index calculation.
This means that SVec is implemented without a compromise - we have the same performance characteristics as in standard Vec. But it works a bit slower still, because of serialization and some additional calculations.
SHashMap
This collection is implemented with a compromise. SHashMap internally is more like Java's HashMap - with a table and buckets. It never reallocates - elements are just pushed to buckets (which internally are SVec's).
So, basically, when you insert something into a SHashMap, the key just gets hashed, then the element is added to the end of the bucket. When you search for a key, it gets hashed and then a linear search over the bucket is performed. So, for such a hash map the table size (capacity) is an essential parameter, since it greatly affects the performance of this collection. For small hash maps you want some small table size, for big maps, you want big table size. It is hard to say exact numbers, but the default capacity is 8k elements, which is more towards "big".
But in a nutshell, the rule is simple: set the capacity of your hash map to the average number of elements, this hash map will hold. If the number of elements is unbound, then don't use a hash map - use a B-tree map instead.
SBTreeMap
This is a classic B-tree map, that is implemented following this tutorial I found online. The implementation is pretty slow at the moment and I'm looking forward to find some spare time in order to profile it. What's good about a B-tree map is that it can efficiently work with huge amounts of data, which is exactly what we seek with stable memory empowered canisters.
SBinaryHeap
This is a SVec-based binary heap. It stores a binary tree in a SVec (there is an algorithm for that) and operates over this tree using basic SVec API (e.g. .push(), .pop() and .swap()).
Since SVec is pretty fast, SBinaryHeap is also pretty fast and does it's job as good as possible.
SHashSet & SBTreeSet
Sets are implemented on top of the maps. The key is stored as usual, but the value for each key is Rust's void value - (). This is only a tiny bit of overhead and it helps with the implementation a lot.
Also, since we're dealing with arbitrary data serialization here, there is another level of indirection involved - collections do not store data; instead they store a pointer to this data. So each time you, for example, push to SVec, the value gets stored separately and only the pointer is stored to the collection itself.
By the way, if you're interested in contributing to this project - feel free to open a PR.
Stable variables
So, there is only one undiscovered topic left - how stable variables do exactly work? How are they remembered between canister upgrades? And this is pretty simple.
The allocator has a special API that allows you to persist 32 bytes (or 4 pointers of 64-bit) of any custom data you want between upgrades:
- _set_custom_data_ptr(usize, u64) - saves a raw pointer to any custom data in a special location;
- _get_custom_data_ptr(usize) -> u64 - retrieves a raw pointer to previously saved custom data.
You can save anything in it and you can always access it. This data is never removed and will be persisted as long as the allocator itself.
Stable variables are actually just a SHashMap with pointer persisted using this mechanism. And a couple of utility functions. That's it.
Note, that stable variables are persisted with index 0, so if you ever use this "custom data API", you are only allowed to update indices from 1 to 3. Otherwise you may lose your stable variables and introduce a stable memory leak.
Conclusion
I hope this article was helpful. If you have any questions, you can reach me out via Github issues or via TG: @joinu14
Don't forget to check project's Github repo, if you didn't!