Struct pallet_paged_list::StoragePagedList

pub struct StoragePagedList<Prefix, Value, ValuesPerNewPage> { /* private fields */ }

A paginated storage list.

Motivation

This type replaces StorageValue<Vec<V>> in situations where only iteration and appending is needed. There are a few places where this is the case. A paginated structure reduces the memory usage when a storage transactions needs to be rolled back. The main motivation is therefore a reduction of runtime memory on storage transaction rollback. Should be configured such that the size of a page is about 64KiB. This can only be ensured when V implements MaxEncodedLen.

Implementation

The metadata of this struct is stored in [StoragePagedListMeta]. The data is stored in [Page]s.

Each [Page] holds at most ValuesPerNewPage values in its values vector. The last page is the only one that could have less than ValuesPerNewPage values. Iteration happens by starting at [first_page][StoragePagedListMeta::first_page]/ [first_value_offset][StoragePagedListMeta::first_value_offset] and incrementing these indices as long as there are elements in the page and there are pages in storage. All elements of a page are loaded once a page is read from storage. Iteration then happens on the cached elements. This reduces the number of storage read calls on the overlay. Appending to the list happens by appending to the last page by utilizing [sp_io::storage::append]. It allows to directly extend the elements of values vector of the page without loading the whole vector from storage. A new page is instantiated once [Page::next] overflows ValuesPerNewPage. Its vector will also be created through [sp_io::storage::append]. Draining advances the internal indices identical to Iteration. It additionally persists the increments to storage and thereby ‘drains’ elements. Completely drained pages are deleted from storage.

Further Observations

• The encoded layout of a page is exactly its [Page::values]. The [Page::next] offset is stored in the [StoragePagedListMeta] instead. There is no particular reason for this, besides having all management state handy in one location.
• The PoV complexity of iterating compared to a StorageValue<Vec<V>> is improved for “shortish” iterations and worse for total iteration. The append complexity is identical in the asymptotic case when using an Appender, and worse in all. For example when appending just one value.
• It does incur a read overhead on the host side as compared to a StorageValue<Vec<V>>.

Trait Implementations

impl<Prefix, Value, ValuesPerNewPage> StorageList<Value> for StoragePagedList<Prefix, Value, ValuesPerNewPage>

where Prefix: StorageInstance, Value: FullCodec, ValuesPerNewPage: Get<u32>,

type Iterator = StoragePagedListIterator<Prefix, Value, ValuesPerNewPage>

Iterator for normal and draining iteration.

type Appender = StoragePagedListMeta<Prefix, Value, ValuesPerNewPage>

Append iterator for fast append operations.

fn iter() -> Self::Iterator

List the elements in append order.

fn drain() -> Self::Iterator

Drain the elements in append order.

fn appender() -> Self::Appender

A fast append iterator.

fn append_one<EncodeLikeValue>(item: EncodeLikeValue)

where EncodeLikeValue: EncodeLike<V>,

Append a single element.

fn append_many<EncodeLikeValue, I>(items: I)

where EncodeLikeValue: EncodeLike<V>, I: IntoIterator<Item = EncodeLikeValue>,

Append many elements.

impl<Prefix, Value, ValuesPerNewPage> StoragePrefixedContainer for StoragePagedList<Prefix, Value, ValuesPerNewPage>

where Prefix: StorageInstance, Value: FullCodec, ValuesPerNewPage: Get<u32>,

fn pallet_prefix() -> &'static [u8]

Pallet prefix. Used for generating final key.

fn storage_prefix() -> &'static [u8]

Storage prefix. Used for generating final key.

fn final_prefix() -> [u8; 32]

Final full prefix that prefixes all keys.