Replace google/btree with tidwall/btree

[amyangfei]

Is your feature request related to a problem?

Given benchmark in https://github.com/tikv/pd/issues/4455, tidwall/btree has better performance than google/btree

Describe the feature you'd like

Since PD has replaced google/btree with tidwall/btree after https://github.com/tikv/pd/pull/5335, we can observe the stability for sometime (maybe half a year) and determine whether to replace it in TiCDC.

TiCDC uses google/btree in three packages, and all of them are quite hot path.

• cdc/entry/schema/snapshot.go
• pkg/causality/internal/node.go
• pkg/regionspan/region_range_lock.go

Describe alternatives you've considered

No response

Teachability, Documentation, Adoption, Migration Strategy

No response

[crelax]

Hi, I noticed that PD didn't replace google/btree with tidwall/btree for now, but they upgraded the version they use of google/btree to use the latest generic version.

Also, I also noticed previous tests that compared google/btree and tidwall/btree and endorsed the latter one have some flaws. They either missed to test the generic veriosn of google/btree(new and only for go 1.18), or failed to use the same tree degree in experiments. The configration of tree degreegoogle/btree is 16 by deafult but can be specified by input, while it’s a constant 128 for tidwall/btree.

My benchmark test results are attached below. The results suggest that

• Generic implementations of each excels their counterpart. Specifically, for google's version, the generic version is approx 3 times faster in random get/set and range tasks than the previous version.
• With the same degree (tested 128), these two have no significant performance differences. Google's generic version performs better than tidwall's except in the task of the sequential set.
• Higher degree gives better performance and yields faster operations than lower ones when N is big.

In addition, given that the APIs of google/btree are much more complete and more straightforward to use, i.e., a series of range functions of generic google/btree, I think, for now, google's version is a better choice. A second thought is needed before replacing the google/btree.

** sequential set, N = 1000000 **
google:     set-seq(d=16)   1,000,000 ops in 247ms, 4,050,349/sec, 246 ns/op, 77.8 MB, 81 bytes/op
google(G):  set-seq(d=16)   1,000,000 ops in 117ms, 8,566,606/sec, 116 ns/op, 21.4 MB, 22 bytes/op
google:     set-seq(d=128)  1,000,000 ops in 160ms, 6,250,362/sec, 159 ns/op, 39.0 MB, 40 bytes/op
google(G):  set-seq(d=128)  1,000,000 ops in 86ms, 11,626,211/sec, 86 ns/op, 16.0 MB, 16 bytes/op
tidwall:    set-seq(d=128)  1,000,000 ops in 114ms, 8,766,213/sec, 114 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): set-seq(d=128)  1,000,000 ops in 75ms, 13,289,816/sec, 75 ns/op, 8.2 MB, 8 bytes/op

** sequential get, N = 1000000 **
google:     get-seq(d=16) 	1,000,000 ops in 149ms, 6,718,302/sec, 148 ns/op
google(G):  get-seq(d=16)	1,000,000 ops in 100ms, 10,017,915/sec, 99 ns/op
google:     get-seq(d=128)	1,000,000 ops in 139ms, 7,184,899/sec, 139 ns/op
google(G):  get-seq(d=128)	1,000,000 ops in 79ms, 	12,699,279/sec, 78 ns/op
tidwall:    get-seq(d=128)	1,000,000 ops in 107ms, 9,318,864/sec, 107 ns/op
tidwall(G): get-seq(d=128)	1,000,000 ops in 91ms, 	10,990,641/sec, 90 ns/op

** random set, N = 1000000 **
google:     set-rand(d=16)	1,000,000 ops in 462ms, 2,165,450/sec, 461 ns/op, 44.6 MB, 46 bytes/op
google(G):  set-rand(d=16)	1,000,000 ops in 188ms, 5,328,115/sec, 187 ns/op, 14.3 MB, 15 bytes/op
google:     set-rand(d=128)	1,000,000 ops in 452ms, 2,210,621/sec, 452 ns/op, 29.7 MB, 31 bytes/op
google(G):  set-rand(d=128)	1,000,000 ops in 155ms, 6,432,629/sec, 155 ns/op, 11.2 MB, 11 bytes/op
tidwall:    set-rand(d=128)	1,000,000 ops in 402ms, 2,490,557/sec, 401 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): set-rand(d=128)	1,000,000 ops in 198ms, 5,056,264/sec, 197 ns/op, 11.2 MB, 11 bytes/op

** random get, N = 1000000 **
google:     get-rand(d=16)   1,000,000 ops in 756ms, 1,323,002/sec, 755 ns/op
google(G):  get-rand(d=16)   1,000,000 ops in 218ms, 4,584,982/sec, 218 ns/op
google:     get-rand(d=128)  1,000,000 ops in 818ms, 1,222,634/sec, 817 ns/op
google(G):  get-rand(d=128)  1,000,000 ops in 164ms, 6,100,468/sec, 163 ns/op
tidwall:    get-rand(d=128)  1,000,000 ops in 669ms, 1,495,205/sec, 668 ns/op
tidwall(G): get-rand(d=128)  1,000,000 ops in 218ms, 4,576,780/sec, 218 ns/op

** range, N = 1000000 **
google:     ascend(d=16)    1,000,000 ops in 23ms, 44,185,874/sec, 22 ns/op
google(G):  ascend(d=16)    1,000,000 ops in 9ms, 116,566,528/sec, 8 ns/op
google:     ascend(d=128)   1,000,000 ops in 13ms, 75,670,153/sec, 13 ns/op
google(G):  ascend(d=128)   1,000,000 ops in 5ms, 200,618,587/sec, 4 ns/op
tidwall:    ascend(d=128)   1,000,000 ops in 11ms, 87,936,246/sec, 11 ns/op
tidwall(G): iter(d=128)     1,000,000 ops in 5ms, 182,990,987/sec, 5 ns/op
tidwall(G): scan(d=128)     1,000,000 ops in 5ms, 211,627,133/sec, 4 ns/op
tidwall(G): walk(d=128)     1,000,000 ops in 6ms, 176,838,568/sec, 5 ns/op
go-arr:     for-loop        1,000,000 ops in 2ms, 597,639,324/sec, 1 ns/op