decl_storage: storage the key alongside the value to be able to iterate on key/value

[gui1117]

as follow up of #4185 (comment)

It would be interesting to introduce a way in decl_storage to tell to store the key alongside the value.
at the end the storage will have the data: (value, key).
This way when iterating on prefix we could actually iterate on (key, value) instead of just value.

This could be just a new attribute.

Implementing the StorageMap and other trait is not straightforward, here are some difficultyies:

• StorageMap::append is implementing to work on the raw not decoded value. If the raw value is (value, key) we can't call scale_codec::EncodeAppend::append on it because we need to give only the raw data for the value.
  multiple solution here:

  • store actually (key, value), decode the key, the remaining byte are the raw value.
    not very good because get function will also have to decode the key.
  • store (value, key, key_length), so we can use key_length to split the raw data.
    (key_length is encoded on 4 byte or in a compact encoding but reversed so we can decode from the end)
  • implement a new EncodeAppendPreserving which does append on a raw data while preserving the suffix.
  • store (value, key) and just decode the value, thus there won't be any optimisation anymore, it will be same as using mutate.

• StorageMap::swap: we can't swap the raw data anymore, solutions:

  • if we store (key, value) then we have to decode the key only and then we can swap split and swap the raw values
  • if we store (value, key) we have to decode the value and then we can split and swap the raw value
  • if we store (value, key, key_length) then we decode key_length and then we can split and swap the raw value.

[bkchr]

for encode_append, we can't append on the raw data anymore as encode_append support only having the data as input.
we could extend encode_append to be able to append on some value while keeping the data in suffix.

I don't understand this. Could you explain it better? Why can we not append (key, value)?

[gui1117]

indeed I updated the message for more clarity, the initial idea was to store (value, key) so we don't have to decode the key on operation such as get and mutate (, similarly to what linked_map does by just putting the linkage in suffix).
If we store indeed (key, value) then append operation can work easily just decoding key and working on the raw value.

[bkchr]

Ahh, yeah, now I understand :) We could maybe thing of a skip() method for skipping data in the encoded blob. So, we could use (key, data), skip the key and use data to append the stuff. Or we just prepend the length of the key.

[gui1117]

I think this should be close as we are now storing keys in hash