RFC: Change Storage::clear_prefix, DefaultChildStorage::clear_prefix and DefaultChildStorage::storage_kill

[bkchr]

Proposal

We would like to add the third version of the clear_prefix function for the top trie and child trie:

fn Storage_clear_prefix_version_3(u64, u64, u64) -> u64;
fn DefaultChildStorage_clear_prefix_version_3(u64, u64, u64) -> u64;

We also would like to add the third version of storage_kill for the child trie:

fn DefaultChildStorage_storage_kill_version_3(u64, u64, u64) -> u64;

To make the function better understandable, here the high level rust representation of the function:

fn clear_prefix(prefix: &[u8], maybe_limit: Option<u32>, maybe_cursor: Option<Vec<u8>>) -> MultiRemovalResults;

pub struct MultiRemovalResults {
	/// A continuation cursor which, if `Some` must be provided to the subsequent removal call.
	/// If `None` then all removals are complete and no further calls are needed.
        /// Must be the key in the state after the last deleted key.
	pub maybe_cursor: Option<Vec<u8>>,
	/// The number of items removed from the state.
        /// 
        /// Keys are are already in the overlay do not count towards keys being removed from state. E.g. the overlay already has
       /// key `AB`, the state also has `AB` and you are deleting with `prefix` `A`. `AB` would not be counted for `state`.
	pub state: u32,
	/// The number of unique keys removed, taking into account both the state and the overlay.
	pub unique: u32,
	/// The number of processed keys from the state. Should in maximum be `limit`.
	pub loops: u32,
}

The important changes being here the introduction maybe_cursor and the change of the return value to MultiRemovalResults.

DefaultChildStorage::storage_kill only differs in the way that it doesn't provide any prefix to clear_prefix, besides that the implementation is exactly the same.

Implementation of clear_prefix

Clear keys from the state and the overlay of the currently modified keys that are starting with prefix. If there is no maybe_limit set, all keys under the given prefix are deleted. If maybe_limit is set, in maximum limit keys are being deleted from the state. The keys that are deleted in the overlay aren't counted towards the limit. If maybe_cursor is given, the implementation needs to seek the given cursor and start the iteration with cursor (or the first key in lexicographical order after cursor if not present). Returns MultiRemovalResults to inform the caller about the operation.

Examples

Let's assume our state looks like this (only showing keys, as values are not important):

Key
A
B
C
CA
CB
CC
CD
D
E

The overlay of currently modified keys looks like this (again only keys):

Key
A
CB
CD
CE
F

1. Call clear_prefix("A", None, None):

Expected result:
MultiRemovalResults { maybe_cursors: None, state: 0, unique: 1, loops: 1 }

Keys deleted: [ A ]

2. Call clear_prefix("C", None, None):

Expected result:
MultiRemovalResults { maybe_cursors: None, state: 2, unique: 6, loops: 5 }

Keys deleted: [ C, CA, CB, CC, CD, CE ]

3. Call clear_prefix("C", Some(2), None):

Expected result:
MultiRemovalResults { maybe_cursors: Some("CB"), state: 2, unique: 5, loops: 2 }

Keys deleted: [ C, CA, CB, CD, CE ]

4. Call clear_prefix("C", Some(2), Some("CB")):

Expected result:
MultiRemovalResults { maybe_cursors: Some("CD"), state: 1, unique: 4, loops: 2 }

Keys deleted: [ CB, CC, CD, CE ]

5. Call clear_prefix("F", None, None):

Expected result:
MultiRemovalResults { maybe_cursors: None, state: 0, unique: 1, loops: 0 }

Keys deleted: [ F ]

Motivation

Currently multiple calls to clear_prefix in the same context with the same set of parameters always leads to the same keys being deleted. It is assumed that seeking for a particular key is cheaper than taking all deleted keys for a given prefix from the overlay than to ignore them in subsequent calls to clear_prefix. So, adding maybe_cursor to move the accounting of already deleted keys to the runtime that should know best any way what was already deleted instead of letting the host guess on what should be deleted next.

[tomaka]

Random small remark:

maybe_limit could be just u32, as u32::max_value() can be considered big enough to be equivalent to "no limit". Right now it's unclear what you would put in limit if there were ever more than 2^32 billion keys to remove, but if you pass just a u32 for maybe_limit then what happens is clear.
Similarly, maybe_cursor could be just &[u8] and instead of passing None you pass the same value as for prefix.

It seems a bit "cleaner" to me to do it this way.

[lamafab]

See #592

[bkchr]

w3f/PPPs#7 continued here.