client-go
client-go copied to clipboard
[DNM] memdb: replace the current implementation with ART(adaptive radix tree)
ref pingcap/tidb#55287
This PR introduce the ART(adaptive radix tree) as a faster replacement of the current memdb. In the micro bench, this implementation outperforms the current memdb in every case, faster in single thread as well as lower total CPU utilization.
The implementation is inspired by plar/go-adaptive-radix-tree, with some additional work:
- Support memory arena, which reduces the allocation cost in GC language.
- Support vlog, and cascade transaction(aka. staging/release/cleanup)
- Support iterator.
- Support tracking memory usage.
In a word, the ART has the same interface as current memdb.
@you06 Please change it to draft PR or adding [DNM] flag on the title.
All the ART works are finished by other PRs.