Store Iteration with Pagination

[alexanderbez]

Currently, the SDK supports KVStorePrefixIterator and KVStoreReversePrefixIterator. These calls, internally, delegate calls to the store types package.

Many queriers call methods on their keepers to get an entire set of resources (e.g. validators or votes), where pagination is performed afterward. This can impose a big IO burden if the set is relatively large.

The SDK should also expose and support paginated versions of these constructors, where internally, the iterator will paginate. This way, we can remove direct pagination from queries and save on IO.

/cc @dshulyak

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[dshulyak]

It looks like that KVStorePrefixIterator returns a wrapper around leveldb.Iterator, with IO semantics being the same. So everything that needs to be changed in on the keepers side. I would suggest something like this:

func (k Keeper) LazyIterateEvidence(ctx sdk.Context, cb func(func() exported.Evidence) bool) {
	store := prefix.NewStore(ctx.KVStore(k.storeKey), types.KeyPrefixEvidence)
	iterator := sdk.KVStorePrefixIterator(store, nil)

	defer iterator.Close()
	for ; iterator.Valid(); iterator.Next() {
		lazyValue := func() exported.Evidence {
			var evidence exported.Evidence
			k.cdc.MustUnmarshalBinaryLengthPrefixed(iterator.Value(), &evidence)
			return evidence
		}
		if cb(lazyValue) {
			break
		}
	}
}

And pagination will look smth like:

func (k Keeper) PaginateEvidence(ctx sdk.Context, page, limit int) []exported.Evidence {
	rst := []exported.Evidence{}
	skip := (page - 1) * limit
	skipped := 0
	collected := 0
	k.LazyIterateEvidence(ctx, func(value func() exported.Evidence) bool {
		skipped++
		if skipped < skip {
			// continue moving cursor
			return false
		}
		collected++
		rst = append(rst, value())
		if collected == limit {
			// stop iterator
			return true
		}
		return false
	})
	return rst
}

Also something more generic can be made, so that each keeper won't have to reimplement same things
@alexanderbez does it sound sane to you? I would say this is a good change, it also decreases potential memory allocation per each query (all dynamically allocated slices go on heap). But i am not that familiar with a project, what do you think?

[alexanderbez]

@dshulyak not quite. Keepers should not concern themselves with pagination implementation, as we want to keep the code DRY and to allow this abstraction to automatically be handled.

Keepers will have two methods per resource (when necessary):

• Keeper#GetX will behave as normal. In other words, it'll call KVStorePrefixIterator or KVStoreReversePrefixIterator.
• Keeper#GetXPaginated is where I'm proposing we provide the abstraction. So, instead, we implement a wrapper around KVStorePrefixIterator and KVStoreReversePrefixIterator that does the pagination automatically.

e.g.

type PaginatedIterator struct {
	Iterator

	page  uint
	limit uint

	// potentially other internal state needed to track valid pagination
}

func (pi PaginatedIterator) skipAhead() {
	// skip to first resource using page and limit
}

func (pi PaginatedIterator) Next() {
	// like regular Next except where we need to handle going past last resource
}

func KVStorePrefixIteratorPaginated(kvs KVStore, prefix []byte, page, limit uint) Iterator {
	it := PaginatedIterator{kvs.Iterator(prefix, PrefixEndBytes(prefix)), page, limit}
	it.skipAhead()
	return it
}

// Iterator over all the keys with a certain prefix in descending order.
func KVStoreReversePrefixIteratorPaginated(kvs KVStore, prefix []byte, page, limit uint) Iterator {
	it := PaginatedIterator{kvs.ReverseIterator(prefix, PrefixEndBytes(prefix)), page, limit}
	it.skipAhead()
	return it
}

I haven't fully tested this out, but I see no reason why this shouldn't work. It'll keep the code in keepers DRY and provide the automated necessary abstractions.

If you agree with this proposal, we would be happy to review and accept a PR 👍

[dshulyak]

proposal looks good 👍