search

tikv / pd

Placement driver for TiKV
Apache License 2.0
1.04k stars 716 forks source link

Compare tidwall/btree vs google/btree #4455

Open nolouch opened 2 years ago

nolouch commented 2 years ago

Task

the benchmark shows tidwall/btree has a better performance. We can consider use tidwall/btree If generic is stable. We can benchmark performance to see if it can improve our current meta-information maintenance performance in PD.

Related issue

AndreMouche commented 2 years ago

Step1: Simply replace btree in server/core/region: no difference

I've tried to simply replace btree in server/core/region in this PR, and the performance is similar to the master

➜  core git:(tidwallbtree) ✗ go test  -bench BenchmarkRegion
OK: 21 passed
goos: darwin
goarch: amd64
pkg: github.com/tikv/pd/server/core
cpu: VirtualApple @ 2.50GHz
BenchmarkRegionTreeUpdate-8              1000000              1242 ns/op
BenchmarkRegionTreeUpdateUnordered-8     2488128               579.9 ns/op
PASS
ok      github.com/tikv/pd/server/core  28.450s
➜  core git:(master) go test -bench BenchmarkRegion
OK: 23 passed
goos: darwin
goarch: amd64
pkg: github.com/tikv/pd/server/core
cpu: VirtualApple @ 2.50GHz
BenchmarkRegionTreeUpdate-8              1000000              1262 ns/op
BenchmarkRegionTreeUpdateUnordered-8     2857729               502.2 ns/op
PASS
ok      github.com/tikv/pd/server/core  27.978s
AndreMouche commented 2 years ago

Step 2: Thread-safe

So maybe the next step to test tidwall is remove the lock, let me try later.

AndreMouche commented 2 years ago

Step3: go version to 1.18 and so on

If step 2 goes well, then we need to update pd to go 1.18 since tidwall/btree support for Generics (Go 1.18). Also we need to fork it to pkg/btree and define some function in it as google/btree did now(to support function regionTree.RandomRegion).

AndreMouche commented 2 years ago

Step 0: Test tidwall/btree VS google/btree directly

tidwall/btree is slower in set/insert operation because the write operation is thread-safe. However tidwall/btree does well in read operations, I prefer to use tidwall/btree in pd once the go version of pd is up to 1.18.

Here is the test code, the result

Func tidwall/btree google/btree
go test -bench="BenchmarkInsert" 231.6 ns/op 215.2 ns/op
go test -bench="BenchmarkInsert" 229.6 ns/op 198.3 ns/op
go test -bench="BenchmarkSeek" 128.6 ns/op 221.9 ns/op
go test -bench="BenchmarkSeek" 127.4 ns/op 202.5 ns/op
go test -bench="BenchmarkDelet" 205.7 ns/op 210.4 ns/op
go test -bench="BenchmarkDelet" 212.5 ns/op 235.9 ns/op
go test -bench="BenchmarkGet" 150.9 ns/op 173.5 ns/op
go test -bench="BenchmarkGet" 147.5 ns/op 172.2 ns/op
go test -bench="BenchmarkAscendGreaterOrEqual" 37669 ns/op 57381 ns/op
go test -bench="BenchmarkAscendGreaterOrEqual" 37254 ns/op 56140 ns/op
go test -bench="BenchmarkDescendLessOrEqual" 34492 ns/op 81551 ns/op
go test -bench="BenchmarkDescendLessOrEqual" 35603 ns/op 81346 ns/op
tidwall commented 2 years ago

In case you want to disable the thread-safe feature with tidwall/btree:

For a traditional interface{} BTree:

btree.NewNonConcurrent(less)

For the new Generic BTree:

btree.NewGenericOptions(lessFunc, btree.Options{NoLocks: true})
nolouch commented 2 years ago

Benchmark (1M Regions Data)

google/btree master(Go 1.17.6)

PR: https://github.com/tikv/pd/pull/4711

➜  core git:(master) go test  -bench BenchmarkRegionTree -benchtime=1000000x  -count=3
goos: darwin
goarch: arm64 (mbp M1)
pkg: github.com/tikv/pd/server/core
BenchmarkRegionTreeSequentialInsert-8            1000000              1795 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000              1763 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000              1772 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              4221 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              4451 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              4248 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               445.1 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               439.1 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               434.7 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5717 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5729 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5700 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               565.9 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               581.9 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               561.6 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3344 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3401 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3302 ns/op
BenchmarkRegionTreeScan-8                        1000000                40.76 ns/op
BenchmarkRegionTreeScan-8                        1000000                30.46 ns/op
BenchmarkRegionTreeScan-8                        1000000                32.28 ns/op

google/btree master (Go 1.18 rc1)

PR: https://github.com/tikv/pd/pull/4711

➜  core git:(master) go test  -bench BenchmarkRegionTree -benchtime=1000000x  -count=3
goos: darwin
goarch: arm64 (mbp M1)
pkg: github.com/tikv/pd/server/core
BenchmarkRegionTreeSequentialInsert-8            1000000              1071 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000              1083 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000              1079 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              3842 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              3838 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              3708 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               332.5 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               328.4 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               338.8 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5074 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5443 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              5103 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               328.4 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               321.3 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               328.9 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3246 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3253 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              3547 ns/op
BenchmarkRegionTreeScan-8                        1000000                28.39 ns/op
BenchmarkRegionTreeScan-8                        1000000                28.11 ns/op
BenchmarkRegionTreeScan-8                        1000000                28.14 ns/op

tidwall/btree (Go 1.18 rc1)

PR https://github.com/tikv/pd/pull/4627

➜  core git:(pr/4627) go test  -bench BenchmarkRegionTree -benchtime=1000000x  -count=3
goos: darwin
goarch: arm64 (mbp M1)
pkg: github.com/tikv/pd/server/core
BenchmarkRegionTreeSequentialInsert-8            1000000               786.6 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000               769.2 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000               775.3 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2777 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2829 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2767 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               373.3 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               383.7 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               387.3 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              4126 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              3980 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              3921 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               216.5 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               211.1 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               208.2 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2034 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2272 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2110 ns/op
BenchmarkRegionTreeScan-8                        1000000                 9.644 ns/op
BenchmarkRegionTreeScan-8                        1000000                11.14 ns/op
BenchmarkRegionTreeScan-8                        1000000                 9.710 ns/op

tidwall/btree with generic(Go 1.18 rc1)

PR: https://github.com/tikv/pd/compare/master...nolouch:pr/4627-with-generic?expand=1

➜  core git:(pr-4627-with-generic) go test  -bench BenchmarkRegionTree -benchtime=1000000x  -count=3
goos: darwin
goarch: arm64  (mbp M1)
pkg: github.com/tikv/pd/server/core
BenchmarkRegionTreeSequentialInsert-8            1000000               751.9 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000               730.2 ns/op
BenchmarkRegionTreeSequentialInsert-8            1000000               732.8 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2694 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2638 ns/op
BenchmarkRegionTreeRandomInsert-8                1000000              2750 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               346.7 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               344.2 ns/op
BenchmarkRegionTreeRandomOverlapsInsert-8        1000000               358.0 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              3834 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              3776 ns/op
BenchmarkRegionTreeRandomUpdate-8                1000000              3637 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               188.6 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               190.1 ns/op
BenchmarkRegionTreeSequentialLookUpRegion-8      1000000               189.2 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2023 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2056 ns/op
BenchmarkRegionTreeRandomLookUpRegion-8          1000000              2272 ns/op
BenchmarkRegionTreeScan-8                        1000000                 8.733 ns/op
BenchmarkRegionTreeScan-8                        1000000                 8.812 ns/op
BenchmarkRegionTreeScan-8                        1000000                 8.788 ns/op
nolouch commented 2 years ago

As shown above: tidwall/btree(G) (1.18) ← tidwall/btree (1.18) > google/btree(1.18) >> google/btree (1.17)