To summarize:

1. Given a set of threads that may wait on each other acquired locks.
2. Given a sequence of more that two threads waiting on each other acquired locks.
3. A circularity is found if the above sequence starts and ends in the same thread.

Translating the previously provided deadlock example into the above described formalization:

Let it be N = {C1, C2, W1, W2} where C1 and C2 are the client connection threads and W1 and W2 are the worker threads, the graph being formed for the above scenario is:

1. G = {(C1, W1)}
2. G = {(C1, W1), (W1, W2)}
3. G = {(C1, W1), (W1, W2), (W2, C2)}
4. G = {(W1, W2), (W2, C2)}
5. G = {(W1, W2), (W2, C2), (C2, W1)}

As per the definition of circularity, a sequence s can be extracted from the last state of the graph that belongs to C, meaning, where the second component of the last pair is the first component of the first pair:

  s = ((W1, W2), (W2, C2), (C2, W1))

The MySQL server already has an implementation of a dependency graph, used to track metadata locks requests and acquisitions: the MDL infra-structure.

ACL locks, Global locks and the MDL infra-structure

Both ACL related statements and statements exclusively acquiring Global locks use the MDL infra-structure to acquire the ACL related table locks and the global locks, respectively. Therefore, by integrating the commit order serialization with the MDL infra-structure one is implicitly enabling deadlock detection between the commit order serialization mechanism and ACL and global locks.

Therefore, the overall proposed approach is to integrate the commit order serialization with the MDL infra-structure in order to full-fill the enumerated requirements.

One graph to rule them all

As the main issue with the current architecture is the lack of communication between the commit order signaling mechanism and the MDL infra-structure, we propose the use of the MDL infra-structure as the signaling mechanism to serialize the commit order.

By submitting an MDL wait ticket for each worker thread when it needs to wait and releasing the worker by granting the ticket, we are adding the wait request to the MDL graph, allowing for the MDL deadlock detection mechanism to take into account the commit serialization when finding possible deadlocks. Enclosed within the wait ticket is the logic that will allow for any threads searching for a deadlock, to check if the holder of each active wait ticket is part of a circular graph path.

The commit queue should be kept to determine the worker commit order, conceptually no changes are needed to that part of the architecture, we should still have a coordinator that populates the queue and each committing worker should be able to release the following worker to commit.

Re-writing the commit order serialization algorithm, it could be synthesized in the following manner.

Each applier worker:

1. Checks if it's at the head of the queue.
2. If at the head of the queue or the ticket is granted:
   1. Commit the worker processed transaction or rollback in case a deadlock was found.
   2. Pop the head of the queue, moving it to the next node.
   3. Grant the ticket held by the worker at the new head.
3. If not at the head of the queue:
   1. Adds an MDL wait ticket, holding a request to proceed to commit.
   2. Processes the MDL graph for possible deadlocks, searching the nodes in the graph that belong to the graph paths starting at the worker node.
   3. Waits on the requested ticket.
   4. If the ticket isn't granted, it means that the worker should back-off the transaction.

The wait ticket

One of the central pieces in the MDL infra-structure is the MDL wait ticket, materialized in the MDL infra-structure code by the class MDL_wait_for_subgraph.

We need to specialize MDL_wait_for_subgraph in order to allow any other thread trying to find a deadlock, to assert if a given worker's graph node, already waiting on the commit order wait ticket, is part of a graph path that forms a circularity.

Since the position in the commit order queue implies a dependency between threads, where the thread occupying a higher index in the queue depends on the threads occupying a lower index, while traversing the graph searching for a circularity and when a commit order queue wait_for ticket is reached, we need to:

1. match the ticket's graph node against the initial node, to check if a circularity as become full-circle and, if so, stop the search
2. allow the search to proceed to the commit order queue wait_for ticket for the worker with the immediate lower index (the dependency represented in the commit order queue)

In theory, there is no possibility of deadlock between worker threads if they are just waiting on the commit order queue ticket, since the commit order dependencies form a linear order, any circularity must contain also other dependencies. Therefore, we don't need to search for deadlocks with workers that appear first in the commit order queue and are already waiting on the commit order ticket, meaning, the above algorithm can be optimized to allow the graph search to process to the worker with the immediate lower index that isn't waiting already on a commit order wait_for ticket.

Avoid unnecessary work & algorithmic complexity

Taking the algorithm described in the previous section, one could argue that in terms of graph traversing heuristics it would be enough to recursively search for the worker Wi that immediately appears before V. That is correct and would keep the order of complexity of the algorithm closer to being linear and not dependent of the number of worker threads. On the other hand, one wouldn't find deadlocks affecting worker threads appearing previously in the commit queue and would be relinquishing that responsibility for future deadlock searches.

A deadlock stemming from the commit order that could be identified earlier would force the workers to back-off earlier and prevent work that we know will be discarded. So, by taking advantage of the linear dependency of the worker threads in the commit queue and trying to find deadlocks earlier, we're increasing the order of complexity of the algorithm but we're also trying to decrease the amount of unnecessary work.

Analyzing the order of complexity of the proposed algorithm in a possible worst-case scenario:

• Let n be the number of worker threads in the commit order queue and n is always an even number.
• Let Wi be the ith worker thread in the commit order queue.

• W1, W3, ... Wk, k = 2i + 1, 0 <= i < n / 2 are already waiting on a commit order ticket (COT = commit order ticket):

    W0    W1    W2    W3          Wn-4  Wn-3  Wn-2  Wn-1  Wn
  +-----+-----+-----+-----+     +-----+-----+-----+-----+-----+
  |     | COT |     | COT | ... | COT |     | COT |     | COT |
  +-----+-----+-----+-----+     +-----+-----+-----+-----+-----+
  

• W2, W4, ... Wk, k = 2i, 1 <= i < n / 2 are already waiting on an MDL lock ticket (MLT = MDL lock ticket), where the lock is held by the worker immediately on the left, Wk-1:

    W0    W1    W2    W3          Wn-4  Wn-3  Wn-2  Wn-1  Wn
  +-----+-----+-----+-----+     +-----+-----+-----+-----+-----+
  |     | COT | MLT | COT | ... | COT | MLT | COT | MLT | COT |
  +-----+-----+-----+-----+     +-----+-----+-----+-----+-----+
  

• Worker W0 isn't waiting, yet.

• Worker Wn creates and adds a new commit order wait ticket and starts a search for a deadlock.
• Worker Wn executes the described algorithm and starts iterating over the commit order queue to visit higher priority worker's sub-graph.
• The search initiated by Wn will, recursively, execute the search algorithm (n - 1) / 2 + (n - 3) / 2 + ... + 1 <=> Sum[k=0..(n/2)-1] (n - (2k + 1)) / 2 times for a single deadlock search.
• For worker m that waits on the commit order queue, the number of paths being traversed in sub-sequent search will be increased by m. The mathematical expression that represents the order of complexity for the n workers (where m is the amount of workers waiting on the commit order queue) is: n = 2*m, P(m) = 1 + Sum[k=1..m-1] T(k), m >= 1.

This amounts to an exponential complexity order with an exponential factor of n / 2 - 1, which can be proven by induction:

    Hip:
        P(m) = 1 + Sum[k=1..m-1] P(k), m >= 1 <=> P(m) = 2^(m - 1)

    Proof:

    For 1
    -----
        P(1) = 1 + Sum[k=1..1-1] P(k)
             = 1 + Sum[k=1..0] P(k)
             = 1 + 0
             = 1
             = 2^0
             = 2^(1 - 1)

    For m + 1
    ---------
        P(m + 1) = 1 + Sum[k=1..m+1-1] P(k)
                 = 1 + Sum[k=1..m] P(k)
                 = 1 + Sum[k=1..m-1] P(k) + P(m)
     per hip ->  = 2^(m - 1) + 2^(m - 1)
                 = 2 . 2^(m - 1)
                 = 2^m
                 = 2^(m + 1 - 1)
                                 QED

Since n = 2*m, the order of complexity or O(2^(n/2 - 1)).

The decision to parallelize transactions and distribute them amongst applier worker threads is based on a parallelization algorithm running in the source of replication that identifies and tracks dependencies between transactions. Because of that, the above scenario could be dimmed impossible due the nonexistence of worker thread inter-dependency other than the commit order queue. However, the parallelization heuristics is based on the data received through the replication channel (logical timestamps) that may be generated by a flawed dependency tracking system or by a malicious replication source.

Therefore, all comes down to weighing the probability of the worst case scenario against the advantages of early deadlock detection and deciding which is more fruitful. For now, our assessment is that, given the type of statements that can interfere with dependency tracking and the specific sequence of the statements being applied by the worker threads in the commit queue, the worst case scenario should be uncommon and hard to observe.

Nonetheless, this is a scenario we should keep an eye on and, if needed, revisit this assessment and find alternative paths.

A lock-free commit order queue

Since there is no longer a thread condition to wait on, there is no longer the need for a mutex that protects that condition. Hence, the only reason to keep the mutex would be to serialize the access to the commit order queue. But, in that case, we would have two different serialization mechanisms, again, and other deadlock scenarios could stem from that.

One possible solution would be to exchange a mutex by a read-write lock and optimizing a bit for readers, since our queue is a single-producer single-consumer multiple-observers queue. But then again, the lock could become a contention point where threads may be scheduled out when everything that they need is to read a value. The main problem that may rise from using a read/write lock is the pushing and poping operations being left to wait for a long time because of readers wanting to iterate over the queue. In a read-write lock protecting a normal queue scenario, push and pop will need write access and iteration will need read access. If some thread requests read access to the lock just before the last reader finishes iterating and this scenario occurs consecutively several times, it will keep the lock in read mode for a large amount of time, leaving push and pop waiting too much.

A more suitable solution would be to provide a lock-free queue and a shared-exclusive access lock that allows for: a concurrent push and pop with shared access on the lock; a non-concurrent iteration operation with exclusive access on the lock. A spin-lock can be used for the described scenario, minimizing the possibility of the threads being scheduled out while waiting.

Since the only thing we need to keep in the queue is the identifier of the workers, we can build a lock-free queue on top of a size-bounded circular queue that only keeps integral elements. By doing so, we avoid the memory management constraints of a lock-free linked list, the usual architecture for a more generic purpose lock-free queue.

If the lock-free circular queue is size-bounded to the number of workers plus one, it should be enough to never run out of space, since the implemented algorithm will never add to the queue the identifier of a worker that is already in the queue.

To summarize, in order to remove the need for a mutex or a common read-write lock guarding the commit order queue (removing a contention point), the following should be provided:

1. A size-bounded, integral element only, lock-free circular queue.
2. A shared-exclusive spin-lock to protect queue iterations from inconsistent views of the data.
3. An implementation that:
   1. Acquires shared access for push and pop, allowing for these operations to occur concurrently.
   2. Acquires exclusive access for iterating over the queue, allowing for a consistent view of the data.

IMPACT ANALYSIS

Performance

The above described changes may have an impact in performance since we will need to search the MDL graph for each worker that needs to wait for it's turn. Performance testing should be extensive and a focus when optimizing the code patch.

Storage engines

No special concerns storage engines.

Security context

No special concerns regarding security.

Upgrade/Downgrade

No special concerns regarding upgrade/downgrade.

Cross-version replication

No special concerns regarding cross-version replication.

User interface

No foreseeable changes regarding user-interface.

Observability

The current implementation already has observability instrumentation in place regarding worker executing stages. The added functionality MUST keep that instrumentation intact.

Deployment / installation

No changes to deployment or installation processes.

Protocol

No foreseeable changes to the MySQL protocol.