How to select n random keys from a `StorageMap`?

Question

Assume I have the following storage map:

ZAccounts: StorageMap(AccountId -> AccountInfoOf<T>)

Is there a simple way to draw n AccountId's randomly. I assume that I already have a secure random source (BABE or VRF).

I mean if I use let accounts: Vec<_> = ZAccounts::<T>::iter().collect(); (to select a random subset later) I have the flaw of an unbounded vector. And additionally I have a storage read for every iteration (pretty expensive).

Then there is the possibility to have a BoundedVec. That would be easy, but I have the constraint that there is no limit (unbounded).

So maybe you know a possibility to know beforehand the key to query for a storage map based on internal storage structure with hasher.

Can I somehow calculate a key from storage and then map some index to it. Then I could map an index to a storage key. Like for example:

StorageMap(u128 -> AccountId)

It could be done like that, but what if one (index -> AccountId) is deleted. Then there are missing indices. At the end this leads to a list of active indices again (like [0, 2, 3, 4 ...] where 1 got removed for some dynamic use-case in which an AccountId should be deleted).

On Zeitgeist a court system needs to get implemented. This requires to select n random jurors from an unbounded list of possible jurors. What would you propose?

Answer 1

Maybe you need a StorageValue<Vec<(Index, AccountId)>>.

let v = StorageValue::get();
let index = v[random % v.len()];
let account_id = v[i];

---

Or StorageMap<Index, AccountId> + StorageValue<Count>.

let count = StorageValue::get();
let index = random % count;
let account_id = StorageMap::get(index);

Note you must not delete the middle item in this map(actually, it looks like a link list structure). You should use swap and delete the item from the tail (also, update the counter correctly).