MySQL 8.0.33
Source Code Documentation
rpl_replica_commit_order_manager.h
Go to the documentation of this file.
1/* Copyright (c) 2014, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef RPL_REPLICA_COMMIT_ORDER_MANAGER
24#define RPL_REPLICA_COMMIT_ORDER_MANAGER
25#include <stddef.h>
26#include <memory>
27#include <vector>
28
29#include "my_dbug.h"
30#include "my_inttypes.h"
33#include "sql/changestreams/apply/commit_order_queue.h" // Commit_order_queue
34#include "sql/rpl_rli_pdb.h" // get_thd_worker
35
36class THD;
38
39/**
40 On a replica and only on a replica, this class is responsible for
41 committing the applied transactions in the same order as was observed on
42 the source.
43
44 The key components of the commit order management are:
45 - This class, that wraps the commit order management, allowing for API
46 clients to schedule workers for committing, make workers wait for their
47 turn to commit, finish up a scheduled worker task and allow for others
48 to progress.
49 - A commit order queue of type `cs::apply::Commit_order_queue` that holds
50 the sequence by which worker threads should commit and the committing
51 order state for each of the scheduled workers.
52 - The MDL infra-structure which allows for: one worker to wait for
53 another to finish when transactions need to be committed in order;
54 detect deadlocks involving workers waiting on each other for their turn
55 to commit and non-worker threads waiting on meta-data locks held by
56 worker threads.
57
58 The worker thread progress stages relevant to the commit order management
59 are:
60 - REGISTERED: the worker thread as been added to the commit order queue
61 by the coordinator and is allowed to start applying the transaction.
62 - FINISHED APPLYING: the worker thread just finished applying the
63 transaction and checks if it needs to wait for a preceding worker to
64 finish committing.
65 - REQUESTED GRANT: the worker thread waits on the MDL graph for the
66 preceding worker to finish committing.
67 - WAITED: the worker thread finished waiting (either is the first in the
68 commit order queue or has just been grantted permission to continue).
69 - RELEASE NEXT: the worker thread removes itself from the commit order
70 queue, checks if there is any worker waiting on the commit order and
71 releases such worker iff is the preceding worker for the waiting
72 worker.
73 - FINISHED: the worker marks itself as available to take on another
74 transaction to apply.
75
76 The progress of the worker within the stages:
77
78 +-------------------------+
79 | |
80 v |
81 [REGISTERED] |
82 | |
83 v |
84 [FINISHED APPLYING] |
85 | |
86 Worker is |
87 first in the queue? |
88 / \ |
89 yes / \ no |
90 / v |
91 \ [REQUESTED GRANT] |
92 \ / |
93 \ / |
94 \ / |
95 | |
96 v |
97 [WAITED] |
98 | |
99 v |
100 [RELEASE NEXT] |
101 | |
102 v |
103 [FINISHED] |
104 | |
105 +-------------------------+
106
107 Lock-free structures and atomic access to variables are used to manage
108 the commit order queue and to keep the worker stage transitions. This
109 means that there is no atomicity in regards to changes performed in the
110 queue or in the MDL graph within a given stage. Hence, stages maybe
111 skipped and sequentially scheduled worker threads may overlap in the
112 same stage.
113
114 In the context of the following tables, let W1 be a worker that is
115 scheduled to commit before some other worker W2.
116
117 The behavior of W2 (rows) towards W1 (columns) in regards to
118 thread synchronization, based on the stage of each thread:
119+------------+-----------------------------------------------------------------+
120| \ W1 | REGISTERED | FINISHED | REQUESTED | WAITED | RELEASE | FINISHED |
121| W2 \ | | APPLYING | GRANT | | NEXT | |
122+------------+------------+----------+-----------+--------+---------+----------+
123| REGISTERED | | | | | | |
124+------------+------------+----------+-----------+--------+---------+----------+
125| FIN. APPL. | | | | | | |
126+------------+------------+----------+-----------+--------+---------+----------+
127| REQ. GRANT | WAIT | WAIT | WAIT | WAIT | WAIT | |
128+------------+------------+----------+-----------+--------+---------+----------+
129| WAITED | | | | | | |
130+------------+------------+----------+-----------+--------+---------+----------+
131| REL. NEXT | | | | | WAIT | |
132+------------+------------+----------+-----------+--------+---------+----------+
133| FINISHED | | | | | | |
134+------------------------------------------------------------------------------+
135
136 The W2 wait when both worker threads are in the RELEASE NEXT stage
137 happens in the case W2 never entered the REQUESTED GRANT stage. This case
138 may happen if W1 being in RELEASE NEXT removes itself from the queue
139 before W2 enters FINISHED APPLYING and then W2 reaches the RELEASE NEXT
140 stage before W1 exits it:
141
142 [W1] [W2]
143
144 stage = RELEASE NEXT stage = REGISTERED
145 | |
146 v |
147 queue.pop() v
148 | stage = FINISHED_APPLYING
149 | |
150 v v
151 next_worker.stage queue.front() == W2
152 == FINISHED_APPLYING |
153 | |
154 | v
155 | stage = WAITED
156 | |
157 | v
158 | stage = RELEASE NEXT
159 | |
160 v v
161 next_worker.release() queue.pop()
162
163 The commit order queue includes mechanisms that block the popping until
164 the preceding worker finishes the releasing operation. This wait will
165 only be active for the amount of time that takes for W1 to change the
166 values of the MDL graph structures needed to release W2, which is a very
167 small amount of cycles.
168
169 The behavior of W1 (rows) towards W2 (columns)in regards to thread
170 synchronization, based on the stage of each thread:
171+------------+-----------------------------------------------------------------+
172| \ W2 | REGISTERED | FINISHED | REQUESTED | WAITED | RELEASE | FINISHED |
173| W1 \ | | APPLYING | GRANT | | NEXT | |
174+------------+------------+----------+-----------+--------+---------+----------+
175| REGISTERED | | | | | | |
176+------------+------------+----------+-----------+--------+---------+----------+
177| FIN. APPL. | | | | | | |
178+------------+------------+----------+-----------+--------+---------+----------+
179| REQ. GRANT | | | | | | |
180+------------+------------+----------+-----------+--------+---------+----------+
181| WAITED | | | | | | |
182+------------+------------+----------+-----------+--------+---------+----------+
183| REL. NEXT | | GRANT | GRANT | | | |
184+------------+------------+----------+-----------+--------+---------+----------+
185| FINISHED | | | | | | |
186+------------------------------------------------------------------------------+
187
188 The W1 grant to W2 may happen when W2 is either in the FINISHED APPLYING
189 or REQUESTED GRANT stages. W1 must also signal the grant when W2 is in
190 FINISHED APPLYING because W1 has no way to determine if W2 has already
191 evaluated the first element of the queue or not, that is, W1 can't
192 determine if W2 will proceed to the REQUESTED GRANT or to the WAITED
193 stage. Therefore, W1 will signal in both cases.
194
195 */
197 public:
198 Commit_order_manager(uint32 worker_numbers);
199 // Copy logic is not available
202
203 // Copy logic is not available
205
206 /**
207 Initializes the MDL context for a given worker in the commit order queue.
208
209 @param worker The worker to initialize the context for
210 */
211 void init_worker_context(Slave_worker &worker);
212
213 /**
214 Register the worker into commit order queue when coordinator dispatches a
215 transaction to the worker.
216
217 @param[in] worker The worker which the transaction will be dispatched to.
218 */
219 void register_trx(Slave_worker *worker);
220
221 private:
222 /**
223 Determines if the worker passed as a parameter must wait on the MDL graph
224 for other workers to commit and, if it must, will wait for it's turn to
225 commit.
226
227 @param worker The worker to determine the commit waiting status for.
228
229 @return false if the worker is ready to commit, true if not.
230 */
231 bool wait_on_graph(Slave_worker *worker);
232 /**
233 Wait for its turn to commit or unregister.
234
235 @param[in] worker The worker which is executing the transaction.
236
237 @retval false All previous transactions succeed, so this transaction can
238 go ahead and commit.
239 @retval true One or more previous transactions rollback, so this
240 transaction should rollback.
241 */
242 bool wait(Slave_worker *worker);
243
244 /**
245 Unregister the thread from the commit order queue and signal
246 the next thread to awake.
247
248 @param[in] worker The worker which is executing the transaction.
249 */
250 void finish_one(Slave_worker *worker);
251
252 /**
253 Unregister the transaction from the commit order queue and signal the next
254 one to go ahead.
255
256 @param[in] worker The worker which is executing the transaction.
257 */
258 void finish(Slave_worker *worker);
259
260 /**
261 Reset server_status value of the commit group.
262
263 @param[in] first_thd The first thread of the commit group that needs
264 server_status to be updated.
265 */
266 void reset_server_status(THD *first_thd);
267
268 /**
269 Get rollback status.
270
271 @retval true Transactions in the queue should rollback.
272 @retval false Transactions in the queue shouldn't rollback.
273 */
274 bool get_rollback_status();
275
276 /**
277 Set rollback status to true.
278 */
279 void set_rollback_status();
280
281 /**
282 Unset rollback status to false.
283 */
285
286 void report_deadlock(Slave_worker *worker);
287
288 std::atomic<bool> m_rollback_trx;
289
290 /* It stores order commit order information of all workers. */
292
293 /**
294 Flush record of transactions for all the waiting threads and then
295 awake them from their wait. It also calls gtid_state->update_commit_group()
296 which updates both the THD and the Gtid_state for whole commit group to
297 reflect that the transaction set of transactions has ended.
298
299 @param[in] worker The worker which is executing the transaction.
300 */
302
303 public:
304 /**
305 Determines if the worker holding the commit order wait ticket
306 `wait_for_commit is in deadlock with the MDL context encapsulated in
307 the visitor parameter.
308
309 @param wait_for_commit The wait ticket being held by the worker thread.
310 @param gvisitor The MDL graph visitor to check for deadlocks against.
311
312 @return true if a deadlock has been found and false otherwise.
313 */
314 bool visit_lock_graph(Commit_order_lock_graph &wait_for_commit,
316
317 /**
318 Check if order commit deadlock happens.
319
320 Worker1(trx1) Worker2(trx2)
321 ============= =============
322 ... ...
323 Engine acquires lock A
324 ... Engine acquires lock A(waiting for
325 trx1 to release it.
326 COMMIT(waiting for
327 trx2 to commit first).
328
329 Currently, there are two corner cases can cause the deadlock.
330 - Case 1
331 CREATE TABLE t1(c1 INT PRIMARY KEY, c2 INT, INDEX(c2)) ENGINE = InnoDB;
332 INSERT INTO t1 VALUES(1, NULL),(2, 2), (3, NULL), (4, 4), (5, NULL), (6,
333 6)
334
335 INSERT INTO t1 VALUES(7, NULL);
336 DELETE FROM t1 WHERE c2 <= 3;
337
338 - Case 2
339 ANALYZE TABLE t1;
340 INSERT INTO t2 SELECT * FROM mysql.innodb_table_stats
341
342 Since this is not a real lock deadlock, it could not be handled by engine.
343 slave need to handle it separately.
344 Worker1(trx1) Worker2(trx2)
345 ============= =============
346 ... ...
347 Engine acquires lock A
348 ... Engine acquires lock A.
349 1. found trx1 is holding the lock.
350 2. report the lock wait to server code by
351 calling thd_report_row_lock_wait().
352 Then this function is called to check
353 if it causes a order commit deadlock.
354 Report the deadlock to worker1.
355 3. waiting for trx1 to release it.
356 COMMIT(waiting for
357 trx2 to commit first).
358 Found the deadlock flag set
359 by worker2 and then
360 return with ER_LOCK_DEADLOCK.
361
362 Rollback the transaction
363 Get lock A and go ahead.
364 ...
365 Retry the transaction
366
367 To conclude, The transaction A which is waiting for transaction B to commit
368 and is holding a lock which is required by transaction B will be rolled
369 back and try again later.
370
371 @param[in] thd_self The THD object of self session which is acquiring
372 a lock hold by another session.
373 @param[in] thd_wait_for The THD object of a session which is holding
374 a lock being acquired by current session.
375 */
376 static void check_and_report_deadlock(THD *thd_self, THD *thd_wait_for);
377
378 /**
379 Wait for its turn to commit or unregister.
380
381 @param[in] thd The THD object of current thread.
382
383 @retval false All previous transactions succeed, so this transaction can
384 go ahead and commit.
385 @retval true The transaction is marked to rollback.
386 */
387 static bool wait(THD *thd);
388
389 /**
390 Wait for its turn to unregister and signal the next one to go ahead. In case
391 error happens while processing transaction, notify the following transaction
392 to rollback.
393
394 @param[in] thd The THD object of current thread.
395 @param[in] error If true failure in transaction execution
396 */
397 static void wait_and_finish(THD *thd, bool error);
398
399 /**
400 Get transaction rollback status.
401
402 @param[in] thd The THD object of current thread.
403
404 @retval true Current transaction should rollback.
405 @retval false Current transaction shouldn't rollback.
406 */
407 static bool get_rollback_status(THD *thd);
408
409 /**
410 Unregister the thread from the commit order queue and signal
411 the next thread to awake.
412
413 @param[in] thd The THD object of current thread.
414 */
415 static void finish_one(THD *thd);
416
417 /**
418 Determines whether current thread needs to wait for its turn to commit and
419 unregister from the commit order queue. The sql commands ALTER TABLE, DROP
420 TABLE, DROP DB, OPTIMIZE TABLE, ANALYZE TABLE and REPAIR TABLE are allowed
421 to wait for its turn to commit and unregister from the commit order queue as
422 exception in MYSQL_BIN_LOG::ordered_commit(), as these transactions have
423 multiple commits and so not determined if the call is ending transaction.
424
425 @param[in] thd The THD object of current thread.
426
427 @retval true Allow thread to wait for it turn
428 @retval false Do not allow thread to wait for it turn
429 */
431};
432
433/**
434 MDL subgraph inspector class to be used as a ticket to wait on by worker
435 threads. Each worker will create its own instance of this class and will use
436 its own THD MDL_context to search for deadlocks.
437 */
439 public:
440 /**
441 Constructor for the class.
442
443 @param ctx The worker THD MDL context object.
444 @param mngr The Commit_order_manager instance associated with the current
445 channel's Relay_log_info object.
446 @param worker_id The identifier of the worker targeted by this object.
447
448 */
450 uint32 worker_id);
451 /**
452 Default destructor.
453 */
454 virtual ~Commit_order_lock_graph() override = default;
455
456 /**
457 Retrieves the MDL context object associated with the underlying worker.
458
459 @return A pointer to the MDL context associated with the underlying worker
460 thread.
461 */
462 MDL_context *get_ctx() const;
463 /**
464 Retrieves the identifier for the underlying worker thread.
465
466 @return The identifier for the underlying worker thread.
467 */
468 uint32 get_worker_id() const;
469 /**
470 Determines if the underlying worker is in deadlock with the MDL context
471 encapsulated in the visitor parameter.
472
473 @param dvisitor The MDL graph visitor to check for deadlocks against.
474
475 @return true if a deadlock was found and false otherwise,
476 */
477 bool accept_visitor(MDL_wait_for_graph_visitor *dvisitor) override;
478 /**
479 Retrieves the deadlock weight to be used to replace a visitor victim's, when
480 more than one deadlock is found.
481 */
482 uint get_deadlock_weight() const override;
483
484 private:
485 /** The MDL context object associated with the underlying worker. */
487 /**
488 The Commit_order_manager instance associated with the underlying worker
489 channel's Relay_log_info object.
490 */
492 /** The identifier for the underlying worker thread. */
494};
495
496/**
497 Determines whether current thread shall run the procedure here
498 to check whether it waits for its turn (and when its turn comes
499 unregister from the commit order queue).
500
501 The sql commands ALTER TABLE, ANALYZE TABLE, DROP DB, DROP EVENT,
502 DROP FUNCTION, DROP PROCEDURE, DROP TRIGGER, DROP TABLE, DROP VIEW,
503 OPTIMIZE TABLE and REPAIR TABLE shall run this procedure here, as
504 an exception, because these transactions have multiple intermediate
505 commits. Therefore cannot predetermine when the last commit is
506 done.
507
508 @param[in] thd The THD object of current thread.
509
510 @retval false Commit_order_manager object is not initialized
511 @retval true Commit_order_manager object is initialized
512*/
513bool has_commit_order_manager(const THD *thd);
514
515#endif /*RPL_REPLICA_COMMIT_ORDER_MANAGER*/
MDL subgraph inspector class to be used as a ticket to wait on by worker threads.
Definition: rpl_replica_commit_order_manager.h:438
uint get_deadlock_weight() const override
Retrieves the deadlock weight to be used to replace a visitor victim's, when more than one deadlock i...
Definition: rpl_replica_commit_order_manager.cc:544
virtual ~Commit_order_lock_graph() override=default
Default destructor.
MDL_context * get_ctx() const
Retrieves the MDL context object associated with the underlying worker.
Definition: rpl_replica_commit_order_manager.cc:532
Commit_order_lock_graph(MDL_context &ctx, Commit_order_manager &mngr, uint32 worker_id)
Constructor for the class.
Definition: rpl_replica_commit_order_manager.cc:527
bool accept_visitor(MDL_wait_for_graph_visitor *dvisitor) override
Determines if the underlying worker is in deadlock with the MDL context encapsulated in the visitor p...
Definition: rpl_replica_commit_order_manager.cc:538
uint32 get_worker_id() const
Retrieves the identifier for the underlying worker thread.
Definition: rpl_replica_commit_order_manager.cc:534
uint32 m_worker_id
The identifier for the underlying worker thread.
Definition: rpl_replica_commit_order_manager.h:493
MDL_context & m_ctx
The MDL context object associated with the underlying worker.
Definition: rpl_replica_commit_order_manager.h:486
Commit_order_manager & m_mngr
The Commit_order_manager instance associated with the underlying worker channel's Relay_log_info obje...
Definition: rpl_replica_commit_order_manager.h:491
On a replica and only on a replica, this class is responsible for committing the applied transactions...
Definition: rpl_replica_commit_order_manager.h:196
void report_deadlock(Slave_worker *worker)
Definition: rpl_replica_commit_order_manager.cc:347
void init_worker_context(Slave_worker &worker)
Initializes the MDL context for a given worker in the commit order queue.
Definition: rpl_replica_commit_order_manager.cc:52
bool wait(Slave_worker *worker)
Wait for its turn to commit or unregister.
Definition: rpl_replica_commit_order_manager.cc:142
void register_trx(Slave_worker *worker)
Register the worker into commit order queue when coordinator dispatches a transaction to the worker.
Definition: rpl_replica_commit_order_manager.cc:56
Commit_order_manager(uint32 worker_numbers)
Definition: rpl_replica_commit_order_manager.cc:45
static void check_and_report_deadlock(THD *thd_self, THD *thd_wait_for)
Check if order commit deadlock happens.
Definition: rpl_replica_commit_order_manager.cc:331
static void wait_and_finish(THD *thd, bool error)
Wait for its turn to unregister and signal the next one to go ahead.
Definition: rpl_replica_commit_order_manager.cc:378
bool get_rollback_status()
Get rollback status.
Definition: rpl_replica_commit_order_manager.cc:412
void finish_one(Slave_worker *worker)
Unregister the thread from the commit order queue and signal the next thread to awake.
Definition: rpl_replica_commit_order_manager.cc:262
static bool wait_for_its_turn_before_flush_stage(THD *thd)
Determines whether current thread needs to wait for its turn to commit and unregister from the commit...
Definition: rpl_replica_commit_order_manager.cc:507
void unset_rollback_status()
Unset rollback status to false.
Definition: rpl_replica_commit_order_manager.cc:418
cs::apply::Commit_order_queue m_workers
Definition: rpl_replica_commit_order_manager.h:291
Commit_order_manager(const Commit_order_manager &)=delete
bool visit_lock_graph(Commit_order_lock_graph &wait_for_commit, MDL_wait_for_graph_visitor &gvisitor)
Determines if the worker holding the commit order wait ticket `wait_for_commit is in deadlock with th...
Definition: rpl_replica_commit_order_manager.cc:453
bool wait_on_graph(Slave_worker *worker)
Determines if the worker passed as a parameter must wait on the MDL graph for other workers to commit...
Definition: rpl_replica_commit_order_manager.cc:70
void flush_engine_and_signal_threads(Slave_worker *worker)
Flush record of transactions for all the waiting threads and then awake them from their wait.
Definition: rpl_replica_commit_order_manager.cc:200
std::atomic< bool > m_rollback_trx
Definition: rpl_replica_commit_order_manager.h:288
void finish(Slave_worker *worker)
Unregister the transaction from the commit order queue and signal the next one to go ahead.
Definition: rpl_replica_commit_order_manager.cc:301
Commit_order_manager & operator=(const Commit_order_manager &)=delete
void set_rollback_status()
Set rollback status to true.
Definition: rpl_replica_commit_order_manager.cc:416
void reset_server_status(THD *first_thd)
Reset server_status value of the commit group.
Definition: rpl_replica_commit_order_manager.cc:254
Context of the owner of metadata locks.
Definition: mdl.h:1410
An abstract class for inspection of a connected subgraph of the wait-for graph.
Definition: mdl.h:918
Abstract class representing an edge in the waiters graph to be traversed by deadlock detection algori...
Definition: mdl.h:944
Definition: rpl_rli_pdb.h:497
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:33
Queue to maintain the ordered sequence of workers waiting for commit.
Definition: commit_order_queue.h:54
Some integer typedefs for easier portability.
uint32_t uint32
Definition: my_inttypes.h:66
Instrumentation helpers for conditions.
ABI for instrumented mutexes.
bool has_commit_order_manager(const THD *thd)
Determines whether current thread shall run the procedure here to check whether it waits for its turn...
Definition: rpl_replica_commit_order_manager.cc:502
unsigned int uint
Definition: uca9-dump.cc:74