Improve performance of storage::append

[bkchr]

storage::append currently works by appending the new data directly to the old data. Instead it would be better if keep appending the raw data to some Vec<u8> and keep the number of items in a separate field:

struct AppendedValue {
    num: Compact<u32>,
    data: Vec<u8>,
    materialized: Option<Vec<u8>>,
}

materialized would be used when the runtime requests the data to cache the materialized "view". When we append new data, we would reset materialized.

This new data structure would also be more optimized for storage transactions as we only need to truncate the data vector on discarding a transaction.

[burdges]

I've not checked any details, but I wonder if the "tree-hashing" in blake2 gives efficient append for Vec<u8>. We might not use blake2's tree-hashing mode now, but..

In fact, you could typically "back out" the "finalization" call to make appends efficient for any hash function, and maybe blake2 also requires doing this. I suppose blake2's "tree-hashing" would make partial reads efficient, but not really help partial writes.

[MrishoLukamba]

i would like to tackle it and get some guidance.

[bkchr]

i would like to tackle it and get some guidance.

What guidance? If you want to work on this, you should start looking into the code and coming up with a way to implement this.

[MrishoLukamba]

i would like to tackle it and get some guidance.

What guidance? If you want to work on this, you should start looking into the code and coming up with a way to implement this.

Okey

[bkchr]

I have layed out the basic idea in the initial issue description. I would recommend as I said to look into the code first. I didn't spend that much more time thinking about the actual implementation. However, this is also part of the job when wanting to tackle this. Any kind of questions you have, you can post here.

[burdges]

There is one one compress call in finalization, so an append proof could be an internal blake2b state, but this does not really jive with the hash function interface, so technically such a use case requires re-analysis. ugh..

[bkchr]

There is one one compress call in finalization, so an append proof could be an internal blake2b state, but this does not really jive with the hash function interface, so technically such a use case requires re-analysis. ugh..

I can not really follow what you are talking about. However, this issue isn't about hashing.

[MrishoLukamba]

There is one one compress call in finalization, so an append proof could be an internal blake2b state, but this does not really jive with the hash function interface, so technically such a use case requires re-analysis. ugh..

I can not really follow what you are talking about. However, this issue isn't about hashing.

Me too. I will raise the PR and iterate

[burdges]

I'm saying if all you want is a more efficient proof of appending to a hash function, to make PoV blobs smaller, then we could actually do that pretty nicely. It requires some further analysis of the has function though, so not really solvable right here. If you do care a lot about then, then ask me to find someone to work it out though.

We can move this to the research channel.

[MrishoLukamba]

I have layed out the basic idea in the initial issue description. I would recommend as I said to look into the code first. I didn't spend that much more time thinking about the actual implementation. However, this is also part of the job when wanting to tackle this. Any kind of questions you have, you can post here.

So after reading and familiarizing myself with OverlayedChanges , this issue affects almost every piece of code inside sp-state-machine. Because it only work with Vec<u8> and now we must change it to work with AppendedValue. Because its not only affecting appending functionalities but also retrieving.

So 1. Can I tackle this issue step by step and not wait untill I finish it.
2. And on what I just stated above , do you think am on the right track because I have also to change retrieving side

[bkchr]

1. Can I tackle this issue step by step and not wait untill I finish it.

I don't get this question.

And on what I just stated above , do you think am on the right track because I have also to change retrieving side

Not sure what you mean by the "retrieving side". In the end we will still output a Vec<u8>.

[tomaka]

it would be better

Maybe a random remark, but how are you sure that this is the case?

Right now, if I understand correctly, you append the new item to the storage value and update the number of elements at the start. This means that, most of the time, the operation will be very inexpensive (memcpying the new element), except when:

• The Vec needs a relocation.
• The number of elements goes from 63 to 64, or from 16383 to 16384, or from 1073741823 to more.

...in which case the entire existing data plus the new element are memcpied.

On the other hand, with what you suggest:

• The problem with Vec needing a relocation still exists (the data field).
• The entire existing data plus the new element are memcpied if they are accessed after having been appended.

So, to me, the only situation where that new solution would be better is if either you never ever read the data (in which case why is there a storage item in the first place?), or if you add more than 16384 elements in a row before reading and then never ever append to it again.
And if, for example, computing the hash of the storage item requires building materialized then you're worse every single time.

[bkchr]

• The problem with Vec needing a relocation still exists (the data field).

For every append you would not need to relocate the existing data, because the vec will allocate more data (assuming you don't use reserve_exact) to push the newly appended data.

The most important improvement here would be around storage transactions. Currently storage transactions require that you clone the entire data, while here we could prevent cloning the entire data. We would store only the old number of elements + the old length. Then on discarding a transaction it would be a simple truncate call.

[MrishoLukamba]

• The problem with Vec needing a relocation still exists (the data field).

For every append you would not need to relocate the existing data, because the vec will allocate more data (assuming you don't use reserve_exact) to push the newly appended data.

The most important improvement here would be around storage transactions. Currently storage transactions require that you clone the entire data, while here we could prevent cloning the entire data. We would store only the old number of elements + the old length. Then on discarding a transaction it would be a simple truncate call.

	pub fn modify(
		&mut self,
		key: StorageKey,
		init: impl Fn() -> StorageValue,
		at_extrinsic: Option<u32>,
	) -> &mut Option<StorageValue> {
		let overlayed = self.changes.entry(key.clone()).or_default();
		let first_write_in_tx = insert_dirty(&mut self.dirty_keys, key);
		let clone_into_new_tx = if let Some(tx) = overlayed.transactions.last() {
			if first_write_in_tx {
				Some(tx.value.clone())
			} else {
				None
			}
		} else {
			Some(Some(init()))
		};

		if let Some(cloned) = clone_into_new_tx {
			overlayed.set(cloned, first_write_in_tx, at_extrinsic);
		}
		overlayed.value_mut()
	}

[MrishoLukamba]

• The problem with Vec needing a relocation still exists (the data field).

For every append you would not need to relocate the existing data, because the vec will allocate more data (assuming you don't use reserve_exact) to push the newly appended data.
The most important improvement here would be around storage transactions. Currently storage transactions require that you clone the entire data, while here we could prevent cloning the entire data. We would store only the old number of elements + the old length. Then on discarding a transaction it would be a simple truncate call.

	pub fn modify(
		&mut self,
		key: StorageKey,
		init: impl Fn() -> StorageValue,
		at_extrinsic: Option<u32>,
	) -> &mut Option<StorageValue> {
		let overlayed = self.changes.entry(key.clone()).or_default();
		let first_write_in_tx = insert_dirty(&mut self.dirty_keys, key);
		let clone_into_new_tx = if let Some(tx) = overlayed.transactions.last() {
			if first_write_in_tx {
				Some(tx.value.clone())
			} else {
				None
			}
		} else {
			Some(Some(init()))
		};

		if let Some(cloned) = clone_into_new_tx {
			overlayed.set(cloned, first_write_in_tx, at_extrinsic);
		}
		overlayed.value_mut()
	}

this snippet function is actually appending data , and yes it is cloning the old data. What I was thinking is because the overlay storage item is a vector of InnerValue which is struct { value: Vec<u8>, extrinsic; u32 } . If I modify
the overlay storage item to be AppendedValue I think I will be getting somewhere on solving this and also I will have to modify how child storage work also.

Please any feedback on my thinking

[bkchr]

Sorry, but I don't get what you have written above.

[cheme]

I am a bit late in this conversation, but in one of my branch (https://github.com/cheme/substrate/tree/threads) I got a similar system:

• overlay store changes: https://github.com/cheme/substrate/blob/b0f194bf319472dd4ffe1211028c02bd5cdf3a77/primitives/externalities/src/lib.rs#L382 these can be successive calls to append.
• on append, if overlay is empty we just add a Change::Append entry in overlay, if overlay is already a value we append
• on read of a value containing append we resolve from all previous append https://github.com/cheme/substrate/blob/b0f194bf319472dd4ffe1211028c02bd5cdf3a77/primitives/state-machine/src/overlayed_changes/mod.rs#L1315 and write a standard value instead.
• A new host function function and externality function append_storage was added (needed). Same for child trie but no other change needed for it.
  So the system do not reach memory efficiency if there is a lot of read, but as long as only write are done it is ok.
  (the point of this branch was to allow parallel writes not really optimize foot print).

[cheme]

Another thing that was needed (but is often convenient) was to switch readonly externalities to &mut eg https://github.com/cheme/substrate/blob/b0f194bf319472dd4ffe1211028c02bd5cdf3a77/primitives/externalities/src/lib.rs#L76