MySQL  8.0.27
Source Code Documentation
rpl_replica_commit_order_manager.h
Go to the documentation of this file.
1 /* Copyright (c) 2014, 2021, 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 
36 class THD;
38 
39 /**
40  On a replica and only on a replica, this class is responsible for
41  commiting the applyed 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 schduled 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 commiting.
65  - REQUESTED GRANT: the worker thread waits on the MDL graph for the
66  preceding worker to finish commiting.
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 poping 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  */
284  void unset_rollback_status();
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
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,
315  MDL_wait_for_graph_visitor &gvisitor);
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  */
430  static bool wait_for_its_turn_before_flush_stage(THD *thd);
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 it's own instance of this class and will use
436  it's 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 targetted 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 intialized
511  @retval true Commit_order_manager object is intialized
512 */
513 bool has_commit_order_manager(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:543
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:531
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:526
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:537
uint32 get_worker_id() const
Retrieves the identifier for the underlying worker thread.
Definition: rpl_replica_commit_order_manager.cc:533
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 commiting the applyed transactions ...
Definition: rpl_replica_commit_order_manager.h:196
void report_deadlock(Slave_worker *worker)
Definition: rpl_replica_commit_order_manager.cc:346
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:330
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:377
bool get_rollback_status()
Get rollback status.
Definition: rpl_replica_commit_order_manager.cc:411
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:506
Commit_order_manager & operator=(const Commit_order_manager &)=delete
void unset_rollback_status()
Unset rollback status to false.
Definition: rpl_replica_commit_order_manager.cc:417
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:452
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:300
void set_rollback_status()
Set rollback status to true.
Definition: rpl_replica_commit_order_manager.cc:415
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:1407
An abstract class for inspection of a connected subgraph of the wait-for graph.
Definition: mdl.h:915
Abstract class representing an edge in the waiters graph to be traversed by deadlock detection algori...
Definition: mdl.h:941
Definition: rpl_rli_pdb.h:513
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
Queue to maintan 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(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:501
unsigned int uint
Definition: uca-dump.cc:29