sink to mysql (cdc) workload skew issue

[zhangjinpeng87]

Workload Skew Problem

Sink to MySQL use the conflict detector to detect potential conflicts between transactions, and build the dependency graph. When a transaction depend on other transactions, this transaction must execute after these dependent transactions. The logic is simple and straight forward. But the conflict detector introduced a fast dependencies resolving optimization: for example transaction B only depend on transaction A, and if transaction A has sent to a special worker, the conflict detector will resolve the dependency and then send B to the same worker where transaction A is, even before transaction A actually executed. This is because each worker execute received transaction one by one in order. So this optimization can guarantee the transaction B must execute after transaction A. This optimization can resolve dependency early and send transaction to worker early when a transaction just depend on another single transaction.

But this early resolve dependency optimization also can result in workload skew issue (one worker handle most transactions) in some cases, and result in the sink to MySQL has a big lag because of its throughput can't catch up with upstream QPS. For example we have A, B, C, D 4 transactions, they come into the conflict detector in order. Transaction A has no dependency on other transactions, and it has been sent to worker 1. Transaction B is a big transaction contains multiple row changes, it has dependency on transaction A because of key 1, because transaction B just depend on transaction A, so according to the above early dependency resolving optimization, transaction B should be send to worker 1 ASAP. And then transaction C contains one Key 555 and has a dependency on transaction B because of key 555, transaction D contains 2 keys [1000, 1001] and has a dependency on transaction B because of key 1000. Both transaction C and transaction D can apply the early dependency resolving optimization. The consequence is transaction A, B, C, D, all of them will be routed to the same worker 1. From the above example we can see that, the early dependency resolving optimization has a problem that will "attract" more and more transactions to a single worker. Actually after Transaction B executed, transaction C and transaction D can be run parallel in different workers.

Txn C(row555)                                         Txn D(row1000, row1001)
         |                                                       |
         |                                                       |
         ------------> Txn B(row1, row2, ..., row1000) <-------
                                          |
                                          |
                                          -------------> Txn A(row1)    worker1

New Proposal

The motivation of early dependency resolving optimization is resolve the transaction dependency as early as possible, but resolve the dependency and send the transaction to a random worker after depended transactions executed is a better choice in terms of stability and predictable throughput.

[asddongmen]

Even if the early conflict resolving mechanism is removed, the workload skew issue may still exist in some rare cases.
Let's consider two tables, t1 and t2, being replicated in a CDC node. If t1 has a lot of transactions that sequentially depend on one another, such as:

Txn N(1, 2,3,4,5, … , n) → … → Txn 3(1,2,3) -> Txn 2(1,2) -> Txn 1(1)

All the transactions that come later still need to wait for their prior dependee transactions to be executed.

This can cause the memory quota of the processor to be consumed by a single table, leading to the starving of other tables and ultimately causing the workload skew issue.

The root causes of this problem are as follows:

1. The memory quota distribution algorithm works in a "optimistic" way, as it does not track the consumed memory of a table and always allocates quota to the applicant.
2. The sinkManager prioritizes the slowest table to pull data from the sorter to the sink, exacerbating the situation.

[zhangjinpeng87]

Even if the early conflict resolving mechanism is removed, the workload skew issue may still exist in some rare cases. Let's consider two tables, t1 and t2, being replicated in a CDC node. If t1 has a lot of transactions that sequentially depend on one another, such as:

Txn N(1, 2,3,4,5, … , n) → … → Txn 3(1,2,3) -> Txn 2(1,2) -> Txn 1(1)

All the transactions that come later still need to wait for their prior dependee transactions to be executed.

This can cause the memory quota of the processor to be consumed by a single table, leading to the starving of other tables and ultimately causing the workload skew issue.

The root causes of this problem are as follows:

1. The memory quota distribution algorithm works in a "optimistic" way, as it does not track the consumed memory of a table and always allocates quota to the applicant.
2. The sinkManager prioritizes the slowest table to pull data from the sorter to the sink, exacerbating the situation.

@asddongmen In the case you described, all transactions of t1 are executed sequentially in both upstream TiDB and TiCDC since these transactions have dependencies one by one like a chain. These transactions can be routed to different workers after this PR, I don't think it can cause skew issue, it is slow CPU usage issue need other thorough solutions.

[flowbehappy]

We found the same issue on some users' environment with older versions. So will pick this enhancement back to older versions.