Re-work rent to not require in-order index and pubkey

[sakridge]

Problem

Rent collection is done on a set of keys with the same pubkey prefix today at the end of a slot in a blocking operation which involves potentially looking up account state from disk incurring page faults.

The in-order requirement on the index also limits the design-space to structures which can iterate the elements in-order efficiently which may impede the speed of the index for other operations such as writing new account states or doing lookups.

Proposed Solution

Find a way to collect rent from a random or pseudo-random set of keys, maybe something like an RNG seeded with the block hash which then picks N number of pubkeys which is designed to on average collect rent from each account every epoch but might not be guaranteed as it is today.

A somewhat related idea is to have some special rent update which does not write the whole account state again, but maybe references a previous update and a new lamports value to indicate that it was changed. This could keep the

[sakridge]

cc @ryoqun

[jon-chuang]

The other idea was that to prevent grinding attacks, the rent collection keeps a memory of the last pubkey it has collected rent from. Then, it collects rent from N pubkeys following that pubkey, where N = num_pubkeys_remaining / num_slots_remaining.

This implies not having a fixed schedule, but the runtime can still start reading accounts into memory preemptively on an as-needed basis, at a stable rate.

This would avoid having to reshuffle rent collection each epoch.

Why is this good enough?

• Someone trying to "bomb" this rent-collection approach would need to wait till the end of the epoch, then spam the network with transactions with keys whose prefix exceed the current rent_pubkey_pointer. Thankfully, such accounts would already be in memory during that short window. There is a tradeoff between how close to the boundary one is, and how much one can spam the network with new accounts.
• To further guard against such things, the bank can also have some spill over logic to the next epoch, after which it catches up. The rent_pubkey_pointer needs to be recoverable from snapshots.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs.