It is only when a new edge is added, that a new cycle can be formed, and moreover this new edge must be the missing link that closes the cycle. How can we find deadlocks in an automatic way? There are many possible algorithms, but one has to take into account that the graph is potentially huge (many concurrent transactions, many possessed resources) and constantly changing as new edges and nodes appear and disappear.ĭealing with these dynamic changes can be simplified by an observation that removing an edge or a node can not introduce a deadlock cycle. And this is why a cycle is impossible: it would have to somehow get back from a later resource to an earlier resource, but all edges lead forward only. In general, if everybody follows a rule to acquire resources in the same order, the picture will always look like all the paths follow this order. This picture can be interpret as two paths leading from file A to file B. If we cut ABe’s transaction into two independent transactions, then the server would be allowed to behave as if the order was:īut this is not a deadlock cycle – note the direction of arrows, they do not form a cycle! 🙂Īlso, this picture depicts a violation of assumption that Write access to file A should be exclusive, as we can see two arrows going out of file A, so we have a contradiction with our assumptions. Remember that to achieve the promised serializability server has to come up with a convincing lie about the order of all transactions. Perhaps it is instructive to first answer a lingering question: Why can’t one of them simply release the Read access right as soon as they are done reading the first file and before requesting the Write access right for next file? For example, why not let ABe release his Read access right to file A, so that BAsil can obtain the Write access right to file A, finish his work, releasing all held access rights and thus letting ABe continue without any further delays? This would surely eliminate the deadlock, so why not do this seemingly smart thing? The short answer is: that would effectively be undistinguishable from cutting a transaction into two smaller ones, which might have surprising results. In InnoDB Data Locking – Part 1 “Introduction” we’ve seen a simple example of scenario in which two people can not finish what they’ve started, because one is waiting for the other to release a resource which is currently in use by the other and vice-versa: ABe already had Read access to file A and requested Write access to file B, but had to wait for BAsil to first release his Read access rights for this file, however BAsil can not do that until he finishes what he planned, which was to obtain Write access to file A, currently in use by ABe. Summary of this post: In this post I’ll describe how deadlock detection works in InnoDB 8.0.18, and thus introduce following concepts : deadlocks caused by granularity, and ways to overcome them by lock ordering.granularity of a lock (access right to everything vs.read views (read-only snapshots which allow stale reads concurrent to new writes).starvation (permanent inflow of readers starving a writer waiting for its turn).reader-writer lock (shared/exclusive access rights).timeouts (for misbehaving lock owners, and to resolve deadlocks).
serializability of transactions (ability to explain states observed over time with a convincing story about relative order of parallel operations).databases, tables, rows (like files on a shared drive, spreadsheets inside a file, and rows inside a spreadsheet).
In InnoDB Data Locking – Part 1 “Introduction” I’ve introduced basic concepts required to understand current post: In this blog series, I’m describing how InnoDB locks data (tables and rows) in order to provide illusion to clients that their queries are executed one after another, and how this was improved in recent releases.
0 kommentar(er)
