MySQL Bugs: #31477: Transaction atomicity not as expected between insert and scan

Bug #31477	Transaction atomicity not as expected between insert and scan
Submitted:	9 Oct 2007 13:02	Modified:	2 Mar 2008 9:19
Reporter:	David Shrewsbury	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Cluster: Cluster (NDB) storage engine	Severity:	S2 (Serious)
Version:	5.1.11	OS:	Linux
Assigned to:	Pekka Nousiainen	CPU Architecture:	Any

Description:
To work-around MySQL Cluster not supporting foreign key integrity constraints, we have added some checks to our application to enforce constraints of the form :

For every row in table X, column N must refer to the primary key of an entry in table Y. (i.e. there cannot be any values in column N of table Y which are not rows in table Y).

To enforce this sort of constraint, our application performs the following checks :

1) When inserting into / updating table X, first ensure that the value referenced in column N exists in table Y, by performing a PK operation on it with a Shared lock.
2) When deleting from table Y, first ensure that there are no references to this tuple by :
2a) Taking an exclusive lock on the row to be deleted (and executing)
2b) Performing a table scan of table X, looking for rows whose column N refers to the row to be deleted.

The crux of the algorithm is in the locking of the referred-to rows in table Y. If one transaction is adding a reference (a row to table X with the to-be-deleted value in column N), and another is deleting the referenced value from table Y, then we expect that either :

A) Adder wins, Deleter loses
1) The Adder gets the shared lock on the row in table Y
2) The Adder inserts their row in table X, with column N referring to the to-be-deleted row in table Y
3) The Adder commits
4) The Deleter gets their exclusive lock on the row in table Y
5) The Deleter scans table X, observes the referring row, and aborts the delete.

b) Deleter wins, Adder loses
1) The Deleter gets the exclusive lock on the row in table Y
2) The Deleter performs a scan of table X and observes no referring rows
3) The Deleter deletes the row in table Y and commits
4) The Adder fails to get the shared lock on the row in table Y as it has been deleted

Due to the incompatibility of shared and exclusive locks, no other outcomes (i.e. Both win, Neither win) should be possible.

However, when we run this in a test-setup, where two threads are repeatedly raced against each other, we occasionally see a scenario where the Adder wins, and then the Deleter wins. This leaves us with an inconsistent database (A row in table X, whose column N refers to a non-existant row in table Y).

How to repeat:
See uploaded files.

Verified in 5.1

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/41287

ChangeSet@1.2584, 2008-01-27 16:41:29+01:00, pekka@sama.ndb.mysql.com +7 -0
  ndb - bug#31477 - 5.0

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/41296

ChangeSet@1.2664, 2008-01-28 13:03:27+01:00, pekka@sama.ndb.mysql.com +3 -0
  ndb - bug#31477 post-merge fixes in 5.1

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/41535

ChangeSet@1.2704, 2008-02-01 00:15:06+01:00, pekka@sama.ndb.mysql.com +1 -0
  ndb - handler - error code fix related to bug#31477

Documented in the 5.1.23-ndb-6.3.9 changelog as follows:

        Transaction atomicity was sometimes not preserved between reads
        and inserts under high loads.

Left in PP status.

Also documented for 5.1.23-ndb-6.2.12.

Pushed into 5.0.58

Pushed into 5.1.24-rc

Pushed into 6.0.5-alpha

Also documented for 5.0.58, 5.1.24, and 6.0.5. Closed.