How can I store the historical values of something at all prior blocks in my pallet?

Question

I want to implement a history mechanism in my pallet, so that I can access the value that something had at all prior blocks, like in this Extension of ERC20 to support Compound-like voting and delegation. That code uses the following storage layout to store the historical votes per address, delegate per address and the historical total supply of votes:

    struct Checkpoint {
        uint32 fromBlock;
        uint224 votes;
    }

    mapping(address => address) private _delegates;
    mapping(address => Checkpoint[]) private _checkpoints;
    Checkpoint[] private _totalSupplyCheckpoints;

I need the same information but for a number of different assets (to be used like vote shares in a DAO). My attempts so far have been focused on just the _totalSupplyCheckpoints (per AssetId).

At first I implemented this using a StorageMap as Checkpoint[]:

    #[pallet::storage]
    /// History for the total supply across all accounts.
    pub(super) type SupplyHistory<T: Config<I>, I: 'static = ()> = StorageDoubleMap<
        _,
        Blake2_128Concat,
        T::AssetId,
        Blake2_128Concat,
        BlockNumberFor<T>,
        AssetBalanceOf<T, I>,
    >;

But this does not allow for logarithmic search (like the binary search used in the solidity code). The best I can come up with here is to collect all keys (N) and sort (NlogN) them and then do binary search (logN), but this is dominated by the Nlog(N) of the sort. As history grows search performance would suffer.

For my second attempt I found out that it is actually possible to store a Vec if only you use the pallet::unbounded macro:

    #[pallet::storage]
    #[pallet::unbounded]
    /// History for the total supply across all accounts.
    pub(super) type SupplyHistory<T: Config<I>, I: 'static = ()> =
        StorageMap<_, Blake2_128Concat, T::AssetId, Vec<(BlockNumberFor<T>, AssetBalanceOf<T, I>)>>;

This solves the binary search issue, but now updating the values in the Vec looks like this:

    pub(super) fn append_supply_history(id: T::AssetId, supply: T::Balance) {
        let mut history = SupplyHistory::<T, I>::get(id).unwrap_or_default();
        let block = frame_system::Pallet::<T>::block_number();
        history.push((block, supply));
        SupplyHistory::<T, I>::insert(id, history);
    }

Now, every time you add a value to the history Vec, you first read the entire Vec from storage, push the new value onto it, and then store the entire thing back into storage. As the history grows more data needs to be read and more data needs to be written, growing linearly with the length of the history Vec. Extrinsics that must append to the supply history will get slower as the history grows.

My question is: is there a better way to do this?

Answer 1

Addressing your last question: It is possible to append to a vector in storage with the ::append function (also exists on StorageMap).

I would caution against having a vector that is tagged as unbounded in storage, though, especially if you don't know yourself whether it will be bounded. At a minimum you would probably want to do a FIFO history of a certain length so that the vector never becomes too big. Remember that you have to still read the whole vector when accessing (even if appending is cheaper with StorageValue::append).

A possible strategy for storing the complete history might be combining the above with binning. The storage might look something like:

    #[pallet::storage]
    /// History for the total supply across all accounts.
    pub(super) type SupplyHistory<T: Config<I>, I: 'static = ()> = StorageDoubleMap<
        _,
        Blake2_128Concat,
        T::AssetId,
        Blake2_128Concat,
        BlockNumberFor<T>,
        BoundedVec<AssetBalanceOf<T, I>, MaxHistoryBucketLength>,
    >;

Do note that this will still lead to unbounded storage usage over time - your total state will grow linearly with every balance transfer - which might become problematic.