perf(storage): improve scanning with GLSN

[ijsong]

What this PR does

This PR substantially enhances the performance of GLSN-based log scanning in
Varlog's storage layer by shifting from point lookups to an iterator approach.
While introducing a minimal overhead of one additional object allocation, this
modification significantly reduces operation times and increases throughput for
larger scan sizes. The slight increase in object allocation is a small trade-off
for the significant performance gains achieved, as demonstrated by the
benchmark.

goos: darwin
goarch: amd64
pkg: github.com/kakao/varlog/internal/storage
cpu: Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
                                    │    base     │                diff                 │
                                    │   sec/op    │   sec/op     vs base                │
Storage_ScanWithGLSN/numLogs=1-8      2.298µ ± 1%   3.088µ ± 1%  +34.36% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=10-8     9.682µ ± 1%   7.499µ ± 1%  -22.55% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=100-8    89.18µ ± 2%   49.93µ ± 0%  -44.01% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=1000-8   968.2µ ± 2%   472.4µ ± 0%  -51.21% (p=0.000 n=20)
geomean                               37.23µ        27.18µ       -26.98%

                                    │     base     │                diff                 │
                                    │     B/op     │     B/op      vs base               │
Storage_ScanWithGLSN/numLogs=1-8        120.0 ± 0%     128.0 ± 0%  +6.67% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=10-8       264.0 ± 0%     272.5 ± 0%  +3.22% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=100-8    1.669Ki ± 0%   1.676Ki ± 0%  +0.41% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=1000-8   15.78Ki ± 0%   15.77Ki ± 0%  -0.06% (p=0.000 n=20)
geomean                                 967.1          991.5       +2.53%

                                    │    base     │                diff                 │
                                    │  allocs/op  │  allocs/op   vs base                │
Storage_ScanWithGLSN/numLogs=1-8       5.000 ± 0%    6.000 ± 0%  +20.00% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=10-8      14.00 ± 0%    15.00 ± 0%   +7.14% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=100-8     104.0 ± 0%    105.0 ± 0%   +0.96% (p=0.000 n=20)
Storage_ScanWithGLSN/numLogs=1000-8   1.004k ± 0%   1.005k ± 0%   +0.10% (p=0.000 n=20)
geomean                                52.00         55.51        +6.77%

Benchmark results summary:

• Environment: Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz, goos: darwin, goarch:
  amd64
• Performance and memory efficiency both improve as the number of logs
  increases. Initial setup overhead results in a performance outlier for 1 log.
  However, significant enhancements are observed for larger log counts: 22.55%
  for 10 logs, 44.01% for 100 logs, and 51.21% for 1000 logs. These improvements
  highlight the method's scalability, with memory allocations remaining stable
  or even reducing, against expectations. The geometric mean shows only a 2.53%
  increase in bytes per operation and a 6.77% increase in allocations per
  operation, underscoring the approach's effectiveness in optimizing performance
  and memory usage.

These results demonstrate the scalability and efficiency of using a pebble
iterator for GLSN-based log scanning. The changes lead to a geomean throughput
increase of -26.98%, highlighting substantial performance improvements for
larger scan sizes without considerable memory overhead.

Additionally, the insights gained from this optimization present an opportunity
to rethink the Read RPC for more efficient log entry lookup by log sequence
number. However, this exploration is beyond the current scope of work.

[ijsong]

Current dependencies on/for this PR:

• perf(client): use transmitResultPool to reduce heap allocs #722
• perf(client): prealloc pkg/varlog.(*transmitter).transmitQueue #721
• perf(client): optimize with atomic.Int64 for lastSubscribeAt in pkg/varlog.(subscriber) #720
• perf(client): reuse snpb.SubscribeResponse in RPC handler #719
• perf(benchmark): use grpc.SharedBufferPool for grpc.DialOption #718
• feat(benchmark): use gops to diagnose benchmark tool #717
• fix(benchmark): refine the benchmark tool for log subscription #716
• perf(storage): improve scanning with GLSN #715 👈
• test(storage): add benchmark for scanning with GLSN #714
• main

This stack of pull requests is managed by Graphite.

[codecov]

Codecov Report

Attention: Patch coverage is 71.87500% with 9 lines in your changes are missing coverage. Please review.

Project coverage is 49.84%. Comparing base (2fb6b53) to head (e0ef909).
Report is 1 commits behind head on main.

❗ Current head e0ef909 differs from pull request most recent head 963d10f. Consider uploading reports for the commit 963d10f to get more accurate results

Files	Patch %	Lines
internal/storage/scanner.go	71.87%	6 Missing and 3 partials ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##             main     #715      +/-   ##
==========================================
+ Coverage   49.79%   49.84%   +0.04%     
==========================================
  Files         235      235              
  Lines       20651    20675      +24     
==========================================
+ Hits        10284    10305      +21     
- Misses       9729     9732       +3     
  Partials      638      638              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[ijsong]

Merge activity

• Feb 26, 10:00 AM EST: @ijsong started a stack merge that includes this pull request via Graphite.
• Feb 26, 10:01 AM EST: Graphite rebased this pull request as part of a merge.
• Feb 26, 10:08 AM EST: @ijsong merged this pull request with Graphite.