txn: use ART as membuffer

[you06]

Feature Request

Is your feature request related to a problem? Please describe:

The membuffer stores written mutations before commit statement, it serves in-txn read also(in union scan), which is a core module of TiDB.

The current implementation is a red-black tree, which is fine, but the performance is such higher in TiDB's use case. Because the keys in TiDB usually have a long common prefix, thus performs not such good in index based on key comparation.

Describe the feature you'd like:

The ART is a radix tree in-mem index, which is friendly to long common prefix keys, in our test, it outperforms the current implementation in almost all cases.

Describe alternatives you've considered:

N/A

Teachability, Documentation, Adoption, Migration Strategy:

To be finished.

Development Tracking

• client-go
  • Refactor membuffer package membuffer: refactor the memdb to support multi implementations tikv/client-go#1426
  • Implement basic ART(simple set/get) membuffer: implement ART with basic get/set tikv/client-go#1451
  • Support staging/checkpoint for ART membuffer: support staging & checkpoint for ART tikv/client-go#1465