client-go icon indicating copy to clipboard operation
client-go copied to clipboard

[DNM] memdb: replace the current implementation with ART(adaptive radix tree)

Open you06 opened this issue 1 year ago • 1 comments

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 avatar Jul 29 '24 11:07 you06

@you06 Please change it to draft PR or adding [DNM] flag on the title.

cfzjywxk avatar Aug 21 '24 03:08 cfzjywxk

All the ART works are finished by other PRs.

you06 avatar Nov 18 '24 04:11 you06