Evaluation of Prefetching changes

[torao]

Summary

Reconsideration of prefetching behavior. This is a mechanism to increase OS and DB cache hit rates by performing reads in advance of subsequent API calls when an API is executed.

• Report on the differences between current lbm-sdk and cosmos-sdk.
  • Aim of the change to lbm-sdk style implementation.
  • The actual effect of the lbm-sdk style implementation.
  • Consideration of the impact of this change on future cosmos-sdk merge task (e.g., how many changes are needed).
• Decision whether to keep the lbm-sdk implementation or revert to the cosmos-sdk implementation.
• If revert to a cosmos-sdk implementation, plan and progress of completing that work.

This task is to sort out useful features in order to reduce the differences between lbm-sdk and cosmos-sdk.

Parent: #549

---

For Admin Use

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

[torao]

Prefetch Mechanism

The Prefetch mechanism of LBM SDK is invoked when a balance inquiry is made for a particular account. By accessing the account in parallel with responding to the balance inquiry, it aims to put the record to be returned in the account inquiry request, which is expected shortly thereafter, on the cache or buffer pool on memory.

Preliminaries

This mechanism is implemented in the following layers:

1. Interface: KVStore.Prefetch()
2. Storage Layer: Store.Prefetch() for each cachekv, gaskv, listenkv, prefix, tracekv.
3. Keeper: Prefetch() for each BaseViewKeeper, AccountKeeper.
4. gRPC Endpoint: A prefetch operation in BankKeeper.Balance().

Their respective calling relations are as follows:

Note that the storage layer is a wrapper structure and calls KVStore.Prefetch() of the lower layer. The code-ware added to the top layer BankKeeper.Balance() in LBM SDK as follows:

https://github.com/line/lbm-sdk/blob/becec650b0839f660c63a422a900b8571e93c6f5/x/bank/keeper/grpc_query.go#L37-L45

Therefore, by measuring benchmarks in cases with and without such prefetch behavior before AccountKeeper.Account(), we can see the effect of the Prefetch mechanism added to LBM SDK.

Method

I benchmark the case of executing AccountKeeper.Account() directly and the case of performing the prefetch operation and then executing AccountKeeper.Account().

https://github.com/torao/lbm-sdk/blob/feature/benchmark/x/bank/types/query_bench_test.go

1. With/Without Prefetch: Perform benchmark for two cases: one in which only Account() is executed without prefetch, and the other in which AccountKeeper.Account() is executed after the prefetch operation.
2. Random Access: Perform AccountKeeper.Account() randomly for a large number of addresses. The real-world usage is close to random access and minimizes the impact of hardware, OS page cache, and KVS buffer pools.
3. Eliminate External Cache Factor: Use tm-db (not memdb). The database is completely initialized with the new accounts before both cases begin so that later cases aren't affected by the cache of the earlier case.
4. Synchronize Prefetch: It's changed to prefetch synchronously because asynchnorous prefetching cannot reliably measure the object.

Result

The following table is the performance of AccountKeeper.Account() run with and without prefetch for the number of accounts (ACCOUNTS const above). It can be seen that the case of AccountKeeper.Account() with prefetch is 1.5 to 1.7 times slower than that without prefetch.

Case	1	1,000	10,000	100,000
AccountDirect	2,749 ns/op	3,589 ns/op	3,995 ns/op	105,509 ns/op
AccountAfterPrefetch	19,978 ns/op	55,911 ns/op	94,369 ns/op	490,435 ns/op
Prefetch	11,611 ns/op	51,559 ns/op	86,505 ns/op	368,179 ns/op
Background	14.31 ns/op	17.84 ns/op	17.23 ns/op	17.31 ns/op

The following is a calculation of the AccountKeeper.Account() execution time with and without prefetching.

Case	1	1000	10000	100000	Calculation
AccountKeeper.Account() direct	2,735 ns/op	3,571 ns/op	3,978 ns/op	105,492 ns/op	AccountDirect - Background
AccountKeeper.Account() after Prefetch	8,353 ns/op	4,334 ns/op	7,847 ns/op	122,239 ns/op	AccountAfterPrefetch - Prefetch - Background
Increase Ratio	305%	121%	172%	197%	after Prefetch ÷ direct

Note that this result shows the same trend when the order of execution is switched.

Conclusion

I can think of no good reason why the prefetch case would be so slow 🤔