pingcap / pingcap/tidb

Proposal: Make MemBuffer Simple and Robust

Open
#58,289 6 comments 0 reactions 0 assignees View on GitHub
type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

[MemBuffer](https://github.com/tikv/client-go/blob/06d7f4b9233b248ea3760aa3caea1a8a51424124/internal/unionstore/union_store.go#L165-L170) stores staging mutations before a transaction is committed. It offers a rich interface to meet TiDB's requirements.

- A high-performance, single-threaded in-memory indexing data structure, supporting set/get operations and iterators.
- Cascading transactions to support statement or row-level rollback.
- Checkpointing functionality.
- Snapshot reads/scans to provide historical versions.

The current usage in TiDB exceeds the capabilities `MemBuffer` was designed for. This issue identifies improper usages and tracks improvements.

## Unsafe Concurrent Opearations

- #56178

`MemBuffer` is not thread-safe, meaning it may panic due to data races if TiDB attempts concurrent operations.

Even with mutexes to avoid data races, TiDB cannot guarantee correctness, as explained in [this comment](https://github.com/tikv/client-go/pull/1479#issuecomment-2421864800).

There is already an [`RWMutex`](https://github.com/tikv/client-go/blob/0e4728cfaac415785c60dfd213f3dff329f4ee38/internal/unionstore/memdb_art.go#L29-L31) in `MemBuffer`, used to prevent `SnapshotGetter` races with write operations. While it feels unusual to have an `RWMutex` in a single-threaded data structure, at least the write operations will not affect snapshot read results.

## Improper Snapshot Usage

Consider a simple scenario: we have a B-tree, and how do we update it during iteration?

```go
package main

import (
"fmt"

"github.com/tidwall/btree"
)

func main() {
// create a map
var tree btree.Map[int, int]

// init
for i := 0; i < 10; i++ {
tree.Set(i, i)
}

// iterate while updating
tree.Scan(func(key, value int) bool {
fmt.Printf("%d %d\n", key, value)
tree.Set(2*key, 2*key) // this can be considered as a UB
return true
})
}
```

`MemBuffer` provides [`SnapshotIter` and `SnapshotIterReverse`](https://github.com/tikv/client-go/blob/0e4728cfaac415785c60dfd213f3dff329f4ee38/internal/unionstore/union_store.go#L200-L203) methods. However, during iteration over a snapshot, TiDB does not fully drain it at once and may write new data into `MemBuffer` midway. To ensure the correctness of the snapshot iterator, `ART` introduces a complex node retention mechanism (tikv/client-go#1503). This seems overly complex for an in-memory data structure. IMO, the iterator should fully drain the data in a single call, as `MemBuffer` is not designed to support MVCC.

Little changes.

```diff
type MemBuffer interface {
...
+ // deprecated
SnapshotIter([]byte, []byte) Iterator
+ // deprecated
SnapshotIterReverse([]byte, []byte) Iterator

+ SnapshotScan([]byte, []byte) [][]byte
+ SnapshotScanReverse([]byte, []byte) [][]byte
```

More changes.

```diff
type MemBuffer interface {
...
+ // deprecated
SnapshotIter([]byte, []byte) Iterator
+ // deprecated
SnapshotIterReverse([]byte, []byte) Iterator
+ // deprecated
SnapshotGetter() Getter

+ Snapshot() MemBufferSnapshot
...
}

// TiDB might read from a snapshot across multiple concurrent threads. Each operation within `MemBufferSnapshot` is guarded by an `RWMutex` to prevent data races with writes to the `MemBuffer`.
+type MemBufferSnapshot interface {
+ Scan([]byte, []byte) [][]byte
+ ScanReverse([]byte, []byte) [][]byte
+ Get(ctx context.Context, k []byte) ([]byte, error)
+}
```

During each statement execution, TiDB should using the snapshot following this procedure:

1. Check if the `MemBuffer` is dirty, if so, create a `MemBufferSnapshot` by `Snapshot` method.
2. When need to read snapshot data, always read from the `Snapshot` fetched in step1, it's thread safe.
3. When the statement ends, should drop the snapshot and never use it anymore.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.