fstree: optimize `GetRange` operation by End-rey · Pull Request #3438 · nspcc-dev/neofs-node

End-rey · 2025-07-01T16:10:58Z

Closes #1724.

goos: linux
goarch: amd64
pkg: github.com/nspcc-dev/neofs-node/pkg/local_object_storage/blobstor/fstree
cpu: AMD Ryzen 7 PRO 4750U with Radeon Graphics
BenchmarkFSTree_GetRange
BenchmarkFSTree_GetRange/Small_range_from_big_object/old-16     	             122	  11002864 ns/op
BenchmarkFSTree_GetRange/Small_range_from_big_object/new-16     	            3067	    386705 ns/op
BenchmarkFSTree_GetRange/Read_full_big_object/old-16            	             100	  10463748 ns/op
BenchmarkFSTree_GetRange/Read_full_big_object/new-16            	             322	   3945272 ns/op
BenchmarkFSTree_GetRange/Read_full_big_object_with_zero_length/old-16     	     100	  10160456 ns/op
BenchmarkFSTree_GetRange/Read_full_big_object_with_zero_length/new-16     	      34	  34044581 ns/op
BenchmarkFSTree_GetRange/Small_object,_full_read/old-16                   	   13506	     82181 ns/op
BenchmarkFSTree_GetRange/Small_object,_full_read/new-16                   	   13040	     93928 ns/op
BenchmarkFSTree_GetRange/Small_object,_full_read_with_zero_length/old-16  	   14584	     85471 ns/op
BenchmarkFSTree_GetRange/Small_object,_full_read_with_zero_length/new-16  	   10000	    109674 ns/op
BenchmarkFSTree_GetRange/Small_object,_partial_read/old-16                	   14809	     81357 ns/op
BenchmarkFSTree_GetRange/Small_object,_partial_read/new-16                	   13521	     89282 ns/op
BenchmarkFSTree_GetRange/Big_object,_small_range_at_the_end/old-16        	     100	  10042648 ns/op
BenchmarkFSTree_GetRange/Big_object,_small_range_at_the_end/new-16        	     621	   2001676 ns/op

Do we need to leave the benchmark test for the old and new Range? Or should I remove it from the commit?

codecov · 2025-07-01T16:13:42Z

Codecov Report

Attention: Patch coverage is 64.51613% with 11 lines in your changes missing coverage. Please review.

Project coverage is 21.49%. Comparing base (de0d6c0) to head (c475a6b).
Report is 14 commits behind head on master.

Files with missing lines	Patch %	Lines
pkg/local_object_storage/blobstor/fstree/fstree.go	60.00%	4 Missing and 2 partials ⚠️
pkg/local_object_storage/blobstor/fstree/head.go	73.33%	4 Missing ⚠️
...ct_storage/blobstor/internal/storagetest/common.go	0.00%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #3438      +/-   ##
==========================================
+ Coverage   21.24%   21.49%   +0.24%     
==========================================
  Files         707      704       -3     
  Lines       53069    52447     -622     
==========================================
- Hits        11275    11272       -3     
+ Misses      40959    40338     -621     
- Partials      835      837       +2

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

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

roman-khimov · 2025-07-01T18:00:53Z

pkg/local_object_storage/blobstor/fstree/fstree.go

+		n, err = seeker.Seek(int64(from), io.SeekStart)
 	} else {
-		to = pLen
+		n, err = io.CopyN(io.Discard, reader, int64(from))


I think you can implement proper Seek() for payloadReader, it'll be faster (position the buffer reader and/or seek in the file) and it can be useful in future as well (think of resetting the stream after transmission).

roman-khimov · 2025-07-01T18:02:59Z

pkg/local_object_storage/blobstor/fstree/fstree.go

-	if length != 0 {
-		to = from + length
+	var n int64
+	if seeker, ok := reader.(io.Seeker); ok {


If from is zero it's not needed.

pkg/local_object_storage/blobstor/fstree/fstree.go

pkg/local_object_storage/blobstor/fstree/range_bench_test.go

cthulhu-rider

@End-rey we lack unit tests. How about adding them?

End-rey · 2025-07-03T18:50:46Z

we lack unit tests.

And which ones are missing? The tests for range are in get_range.go.

cthulhu-rider · 2025-07-04T08:24:36Z

we lack unit tests.

And which ones are missing? The tests for range are in get_range.go.

oh, missed that tests are packaged separately. Then ok

cthulhu-rider

tests are good lookin now, easy to analyse 👍

noticable thing is 4K with ~10% lower speed and memory space

FSTree_GetRange/size=4KB,off=Empty,len=4KB/regular-16            17.62Ki ± 0%   48.31Ki ± 0%  +174.24% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=Empty,len=4KB/compressed-16         17.62Ki ± 0%   48.31Ki ± 0%  +174.24% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=Empty,len=4KB/combined-16           17.90Ki ± 0%   48.08Ki ± 0%  +168.60% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=Empty,len=Empty/regular-16          17.77Ki ± 0%   47.95Ki ± 0%  +169.80% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=Empty,len=Empty/compressed-16       17.77Ki ± 0%   47.95Ki ± 0%  +169.80% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=Empty,len=Empty/combined-16         17.91Ki ± 0%   48.13Ki ± 0%  +168.81% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=1KB,len=1KB/regular-16              17.92Ki ± 0%   44.77Ki ± 0%  +149.83% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=1KB,len=1KB/compressed-16           17.92Ki ± 0%   44.77Ki ± 0%  +149.83% (p=0.000 n=10)
FSTree_GetRange/size=4KB,off=1KB,len=1KB/combined-16             17.95Ki ± 1%   45.13Ki ± 0%  +151.45% (p=0.000 n=10)

have u tested 1M or 4M? It's too big step b/w 4K and 10M imo

btw off=Empty,len=Empty: unlike len, off=Empty is understandable but looks a bit weird to me

pkg/local_object_storage/blobstor/fstree/fstree.go

pkg/local_object_storage/blobstor/fstree/head.go

pkg/local_object_storage/blobstor/fstree/fstree.go

Signed-off-by: Andrey Butusov <andrey@nspcc.io>

pkg/local_object_storage/blobstor/fstree/fstree.go

Since #3383 and #3431, it is now not necessary to unmarshal the object to get its payload, and we can read the payload from reader to find the data. ``` goos: linux goarch: amd64 pkg: github.com/nspcc-dev/neofs-node/pkg/local_object_storage/blobstor/fstree cpu: AMD Ryzen 7 PRO 4750U with Radeon Graphics │ old.txt │ new.txt │ │ sec/op │ sec/op vs base │ FSTree_GetRange/size=10MB,off=1MB,len=4KB/regular-16 8027.9µ ± 9% 264.8µ ± 5% -96.70% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/compressed-16 7608.3µ ± 5% 270.5µ ± 6% -96.45% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/combined-16 7391.8µ ± 6% 360.6µ ± 8% -95.12% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/regular-16 7.876m ± 4% 4.134m ± 3% -47.52% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/compressed-16 7.989m ± 6% 4.170m ± 3% -47.80% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/combined-16 7.530m ± 2% 4.038m ± 8% -46.37% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/regular-16 8.220m ± 6% 4.164m ± 4% -49.35% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/compressed-16 8.183m ± 6% 4.703m ± 6% -42.53% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/combined-16 7.508m ± 5% 4.325m ± 5% -42.40% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/regular-16 822.54µ ± 6% 83.04µ ± 4% -89.90% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/compressed-16 884.94µ ± 7% 92.61µ ± 5% -89.53% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/combined-16 1346.99µ ± 11% 84.62µ ± 10% -93.72% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/regular-16 908.2µ ± 15% 817.8µ ± 9% ~ (p=0.165 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/compressed-16 946.3µ ± 3% 806.2µ ± 4% -14.80% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/combined-16 1290.4µ ± 9% 914.6µ ± 11% -29.12% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/regular-16 955.0µ ± 3% 863.4µ ± 4% -9.60% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/compressed-16 948.7µ ± 4% 869.5µ ± 5% -8.35% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/combined-16 1318.8µ ± 13% 955.9µ ± 7% -27.52% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/regular-16 79.55µ ± 5% 89.11µ ± 2% +12.01% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/compressed-16 78.48µ ± 5% 87.90µ ± 2% +12.01% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/combined-16 79.15µ ± 4% 92.59µ ± 3% +16.98% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/regular-16 81.78µ ± 4% 92.22µ ± 4% +12.77% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/compressed-16 79.80µ ± 11% 90.99µ ± 3% +14.02% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/combined-16 92.39µ ± 9% 92.73µ ± 2% ~ (p=0.280 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/regular-16 92.11µ ± 1% 89.30µ ± 2% -3.06% (p=0.002 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/compressed-16 80.11µ ± 17% 91.34µ ± 2% ~ (p=0.105 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/combined-16 79.40µ ± 5% 90.61µ ± 4% +14.12% (p=0.000 n=10) geomean 871.6µ 399.9µ -54.12% │ old.txt │ new.txt │ │ B/op │ B/op vs base │ FSTree_GetRange/size=10MB,off=1MB,len=4KB/regular-16 20495.77Ki ± 0% 43.65Ki ± 0% -99.79% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/compressed-16 20495.77Ki ± 0% 43.65Ki ± 0% -99.79% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/combined-16 20496.00Ki ± 0% 43.81Ki ± 0% -99.79% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/regular-16 20.02Mi ± 0% 10.04Mi ± 0% -49.84% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/compressed-16 20.02Mi ± 0% 10.04Mi ± 0% -49.84% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/combined-16 20.02Mi ± 0% 10.04Mi ± 0% -49.84% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/regular-16 20.02Mi ± 0% 10.04Mi ± 0% -49.84% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/compressed-16 20.02Mi ± 0% 10.04Mi ± 0% -49.84% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/combined-16 20.02Mi ± 0% 10.04Mi ± 0% -49.85% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/regular-16 2063.83Ki ± 0% 43.65Ki ± 0% -97.89% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/compressed-16 2063.83Ki ± 0% 43.65Ki ± 0% -97.88% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/combined-16 2063.98Ki ± 0% 43.89Ki ± 0% -97.87% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/regular-16 2.015Mi ± 0% 1.039Mi ± 0% -48.45% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/compressed-16 2.015Mi ± 0% 1.039Mi ± 0% -48.45% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/combined-16 2.016Mi ± 0% 1.039Mi ± 0% -48.46% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/regular-16 2.015Mi ± 0% 1.039Mi ± 0% -48.44% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/compressed-16 2.015Mi ± 0% 1.039Mi ± 0% -48.44% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/combined-16 2.016Mi ± 0% 1.039Mi ± 0% -48.46% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/regular-16 17.97Ki ± 0% 47.68Ki ± 0% +165.35% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/compressed-16 17.97Ki ± 0% 47.68Ki ± 0% +165.35% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/combined-16 17.91Ki ± 0% 48.13Ki ± 0% +168.71% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/regular-16 18.12Ki ± 0% 48.09Ki ± 0% +165.42% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/compressed-16 18.12Ki ± 0% 48.09Ki ± 0% +165.42% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/combined-16 17.90Ki ± 1% 48.12Ki ± 0% +168.78% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/regular-16 18.15Ki ± 0% 45.07Ki ± 0% +148.34% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/compressed-16 18.15Ki ± 0% 45.07Ki ± 0% +148.34% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/combined-16 17.92Ki ± 1% 45.11Ki ± 0% +151.67% (p=0.000 n=10) geomean 913.5Ki 306.3Ki -66.47% │ old.txt │ new.txt │ │ allocs/op │ allocs/op vs base │ FSTree_GetRange/size=10MB,off=1MB,len=4KB/regular-16 135.0 ± 0% 138.0 ± 0% +2.22% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/compressed-16 135.0 ± 0% 138.0 ± 0% +2.22% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=1MB,len=4KB/combined-16 140.0 ± 1% 140.5 ± 1% +0.36% (p=0.038 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/regular-16 142.0 ± 0% 145.0 ± 0% +2.11% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/compressed-16 142.0 ± 0% 145.0 ± 0% +2.11% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=10MB/combined-16 138.0 ± 1% 140.5 ± 2% ~ (p=0.063 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/regular-16 139.0 ± 0% 148.0 ± 0% +6.47% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/compressed-16 139.0 ± 0% 148.0 ± 0% +6.47% (p=0.000 n=10) FSTree_GetRange/size=10MB,off=Empty,len=Empty/combined-16 139.0 ± 2% 139.0 ± 1% ~ (p=0.773 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/regular-16 135.0 ± 0% 134.0 ± 0% -0.74% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/compressed-16 135.0 ± 0% 134.0 ± 0% -0.74% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=1KB,len=4KB/combined-16 139.5 ± 2% 140.5 ± 2% +0.72% (p=0.030 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/regular-16 127.0 ± 0% 141.0 ± 0% +11.02% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/compressed-16 127.0 ± 0% 141.0 ± 0% +11.02% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=1MB/combined-16 138.0 ± 2% 139.5 ± 1% ~ (p=0.195 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/regular-16 127.0 ± 0% 144.0 ± 0% +13.39% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/compressed-16 127.0 ± 0% 144.0 ± 0% +13.39% (p=0.000 n=10) FSTree_GetRange/size=1MB,off=Empty,len=Empty/combined-16 139.0 ± 1% 140.0 ± 2% ~ (p=0.146 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/regular-16 139.0 ± 0% 129.0 ± 0% -7.19% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/compressed-16 139.0 ± 0% 129.0 ± 0% -7.19% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=4KB/combined-16 138.0 ± 1% 140.5 ± 1% +1.81% (p=0.001 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/regular-16 142.0 ± 0% 140.0 ± 0% -1.41% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/compressed-16 142.0 ± 0% 140.0 ± 0% -1.41% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=Empty,len=Empty/combined-16 137.5 ± 3% 140.0 ± 2% ~ (p=0.091 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/regular-16 143.0 ± 0% 140.0 ± 0% -2.10% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/compressed-16 143.0 ± 0% 140.0 ± 0% -2.10% (p=0.000 n=10) FSTree_GetRange/size=4KB,off=1KB,len=1KB/combined-16 138.0 ± 1% 140.5 ± 2% +1.81% (p=0.030 n=10) geomean 137.1 139.9 +2.01% ``` Closes #1724. Signed-off-by: Andrey Butusov <andrey@nspcc.io>

End-rey self-assigned this Jul 1, 2025

End-rey requested review from carpawell, cthulhu-rider and roman-khimov as code owners July 1, 2025 16:10

roman-khimov reviewed Jul 1, 2025

View reviewed changes

cthulhu-rider reviewed Jul 2, 2025

View reviewed changes

pkg/local_object_storage/blobstor/fstree/range_bench_test.go Outdated Show resolved Hide resolved

cthulhu-rider reviewed Jul 2, 2025

View reviewed changes

End-rey force-pushed the 1724-optimize-getrange-in-blobstor-components branch 2 times, most recently from 7e35fc9 to 692e131 Compare July 3, 2025 18:42

End-rey force-pushed the 1724-optimize-getrange-in-blobstor-components branch from 692e131 to 7f1a8b7 Compare July 3, 2025 18:51

End-rey requested review from cthulhu-rider and roman-khimov July 4, 2025 08:18

cthulhu-rider reviewed Jul 4, 2025

View reviewed changes

fstree: add bench test to GetRange

fd0307d

Signed-off-by: Andrey Butusov <andrey@nspcc.io>

End-rey force-pushed the 1724-optimize-getrange-in-blobstor-components branch from 7f1a8b7 to 766d39b Compare July 4, 2025 11:20

End-rey requested a review from cthulhu-rider July 4, 2025 11:23

roman-khimov approved these changes Jul 7, 2025

View reviewed changes

pkg/local_object_storage/blobstor/fstree/fstree.go Show resolved Hide resolved

End-rey force-pushed the 1724-optimize-getrange-in-blobstor-components branch from 766d39b to c475a6b Compare July 7, 2025 13:37

carpawell approved these changes Jul 7, 2025

View reviewed changes

cthulhu-rider approved these changes Jul 7, 2025

View reviewed changes

roman-khimov mentioned this pull request Jul 7, 2025

S3 tests failure because of missing wallet nspcc-dev/neofs-testcases#1097

Closed

roman-khimov merged commit 18b16e8 into master Jul 7, 2025
20 of 23 checks passed

roman-khimov deleted the 1724-optimize-getrange-in-blobstor-components branch July 7, 2025 14:22

Conversation

End-rey commented Jul 1, 2025

Uh oh!

codecov bot commented Jul 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

roman-khimov Jul 1, 2025

Choose a reason for hiding this comment

Uh oh!

roman-khimov Jul 1, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

cthulhu-rider left a comment

Choose a reason for hiding this comment

Uh oh!

End-rey commented Jul 3, 2025

Uh oh!

cthulhu-rider commented Jul 4, 2025

Uh oh!

cthulhu-rider left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

codecov bot commented Jul 1, 2025 •

edited

Loading