Performance: prefetch data from S3

[hzxa21]

To improve performance and reduce cost (S3 charges money per GET request), it is time to think about a better prefetch strategy instead of only reading one block at a time from S3.

For compactor, I think we can always prefetch the whole SST since we will read all its data anyway. #2630 has implemented simple prefetch for compaction.

For compute node, I think we need some heuristic to do the prefetch (e.g. size based with some exponential factors). Can the prefetch strategy adjust to the workload?

[fuyufjh]

For small point queries, I think LRU is enough, and it may be hard to predict incoming data or user's query 🤔

So we may start from big range queries?

[Little-Wallace]

We can not fetch the whole SST because it may hold the whole data of this compaction task in memory....

[Little-Wallace]

for big range queries, it's hard for hummock to judge how much data we shall prefetch....
If the executor could know how large range it will read, it can pass prefetch flag to hummock and hummock could read this data

[lmatz]

Another form of prefetch:
if an SST/block named X that is going to be compacted has already been in the cache, then after compaction, the SST/blocks that overlap SST/block X can be used directly to replace X in the cache with some heuristics.

[hzxa21]

Another form of prefetch: if an SST/block named X that is going to be compacted has already been in the cache, then after compaction, the SST/blocks that overlap SST/block X can be used directly to replace X in the cache with some heuristics.

Exactly. What I am thinking of is: after compaction, block cache (and disk-based secondary cache in the future) is refilled by some heuristics while the blocks of pre-compacted SSTs are still usable until the prefetch finish. In this way, we can reduce cache miss caused by compaction.

[hzxa21]

We can not fetch the whole SST because it may hold the whole data of this compaction task in memory....

Yes, we should bound the working set of compactor to avoid OOM but try to prefetch as much as possible.

[Little-Wallace]

Another form of prefetch: if an SST/block named X that is going to be compacted has already been in the cache, then after compaction, the SST/blocks that overlap SST/block X can be used directly to replace X in the cache with some heuristics.

we can refill this cache just after we pinned a new version.

[jon-chuang]

If the executor could know how large range it will read, it can pass prefetch flag to hummock and hummock could read this data

There is actually count min sketch for this to do so space efficiently...

Feels like this is related to prefix bloom filter as well. And we need e.g. table schema for the variable length prefix here too.

[skyzh]

If we can enable prefetch, we can set block size back to 64KB. Related PR: #3463