Allow iteration over contract storage

[athei]

The contracts pallet does not allow contracts to iterate over storage. The reason for that is that we expected contracts to store their own metadata in order to be able to iterate. The solution of ink! was to come up with elaborate high level data structures that allowed such iteration without any support from pallet-contracts. However, it turned out that those data structure are complex in terms of code size and computation. The solution to big contract sizes was to come up with a simple Mapping data structure that is just a thin wrapper around functionality provided by pallet-contracts. In order to have iteration using this data structure we need some new functionality:

API

We just need some API to get the next lexicographic key:

seal_next_key(key)

RPC

No RPCs needed. Clients can just query the child trie id of a contract and then call:

childState_getKeys
childState_getKeysPages
childState_getEntries

Currently, we have contracts_getStorage which is redundant. It can just be replaced by childState_getStorage.

Requirements

We need paritytech/substrate#11029 to make this functionality useful. Otherwise querying the keys wouldn't give us access to the pre image of the key which is what we are interested in most cases.

[xiyu1984]

Hey @athei,
I'm sorry to bother you for a moment.

I found if I use mapping, then I cannot use Vec<User-defined structure> as another member of the contract.
Like this:

#[ink(storage)]
    #[derive(SpreadAllocate, ::scale_info::TypeInfo)]
    pub struct DProtocalStack {
        /// Stores a single `bool` value on the storage.
        value: bool,
        account: AccountId,

        sim_routers: ink_prelude::vec::Vec<SimNode>,

        msg_2_verify: ink_storage::Mapping<ink_prelude::string::String, ink_storage::Mapping<u128, RecvedMessage>>,
    }

and the SimNode is:

 #[derive(SpreadLayout, PackedLayout, SpreadAllocate, PackedAllocate, Debug, PartialEq, Eq, scale::Encode, scale::Decode)]
    #[cfg_attr(feature = "std", derive(::scale_info::TypeInfo, StorageLayout))]
    pub struct SimNode(u16, u32);

The error is: cannot find derive macro PackedAllocate in this scope

I need to iterate sim_routers, even if I put it in mapping it is not allowed.

So currently, is the only way we can implement things like this is that putting SimNode in mapping and storing the index in a Vec?

[athei]

Yes. You need to manually keep track of keys you are interested in. Please keep in mind that even with this feature iteration is almost never the right solution for a contract. It is basically unbounded and most probably not what you want.

[xiyu1984]

Yes. You need to manually keep track of keys you are interested in. Please keep in mind that even with this feature iteration is almost never the right solution for a contract. It is basically unbounded and most probably not what you want.

Thanks a lot. I get it~

[donkey-donkey]

If you are using a tuple as a key how do recommend keeping track of all the keys of each tuple?
thanks

[athei]

Moving into blocked because I am not sure if this is the best way forward or how to design this API. Right now we just have Mapping in ink! which is a thin wrapper around the offered key value storage API.

Going forward we want to implement a iterable Vec in ink! which allows storing its element over a number of storage items. While doing so we should explore which APIs would help implementing this. Relying on full on iteration will be way to slow. So there will be some user space state in those data structures. Question is if and how much support from the pallet is needed to implement those.

@xermicus We should design this API along the new StorageVec data structure.

[goastler]

As a user of the Mapping data structure, having the keys available would be a nice option to avoid having to store them myself. However, I think there's a couple of situations at play here:

1. I don't need a list of keys
   This is when I simply need the Mapping to act as a cache. The keys are known ahead of time / stored elsewhere. I'd prefer to keep Mapping as thin as possible for this scenario to reduce contract size.
2. I need key lookup
   I need to test whether a key is in the Mapping or not. Currently, I store keys in a BTreeSet to give log(n) lookup times.
3. I need key search
   I need to search for a key or find the nearest key (e.g. numerical comparison). I use a BTreeSet again with a binary search.
4. I need key enumeration
   I simply need to get all the keys for the Mapping. I use a Vec to store the keys for this unless already using a BTreeSet due to above.

A note about using a Vec to store keys: it's only helpful if you never remove keys / do so infrequently, as the removal is O(n) complexity so doesn't scale well. We transitioned to using BTreeSet for this.

It's also worth noting that the more BTreeSets I added to the contract, the larger the contract size. We were using these in a Mapping<u8, BTreeSet> which may have contributed to the size due to the nested BTreeSet, but it's a consideration nonetheless.

I would advise against using a linked-list like structure on top of the keys in a Mapping as this makes the lookup and search case painfully slow.

tldr; it's almost always best to use a BTreeSet to store the keys. It would be nice to have this built-in to Mapping but it is also necessary to have a Mapping without this to keep contract size down.

[xiyu1984]

Hey @athei , according to the information from @goastler, I found the BTreeMap seems to satisfy everything, which can be a member of the contract itself to store states, easily lookup, get all the keys immediately, and iterate.

So what are the drawbacks of the BTreeMap being used as a member compared to Mapping?

Here's my example code

[athei]

So what are the drawbacks of the BTreeMap being used as a member compared to Mapping?

That the whole BTreeMap is loaded from storage into contract memory even if you only want to access a single item. Just like using a Vec.

[TomaszWaszczyk]

Hey @athei , according to the information from @goastler, I found the BTreeMap seems to satisfy everything, which can be a member of the contract itself to store states, easily lookup, get all the keys immediately, and iterate.

So what are the drawbacks of the BTreeMap being used as a member compared to Mapping?

Here's my example code

BTreeMap is not well optimized, generally imho BTreeMap is not recommended to use in ink! smart contract.

[athei]

@goastler For key lookup (2) why don't you use Mapping::contains?