Percona MySQL 5.5 Unique key is duplicated

I'm totally out from ideas, so maybe somebody else could answer my question.
We have a MySQL 5.5 server from Percona with high traffic. The application is in PHP and writes always to master. We have at the same time 4 slaves from which we only read. Basically it is a standard master-slave configuration.
Last week happened that the replication was broken on all slaves, so I checked, what is wrong with the database.
What I found out is basically my question, how can this happen:
The unique key column (not the primary key) from one of the tables has the same value in 2 rows. I tried to find out if this happened more then one time, but not. It is happened only one time, but I would understand why or how can this happen.
For better understanding here are some real data from our database:

``
show create table registeredUsers;
| registeredUsers | CREATE TABLE registeredUsers (
id bigint(20) unsigned NOT NULL AUTO_INCREMENT,
userId varchar(32) NOT NULL,
client varchar(200) NOT NULL,
osVersion varchar(10) NOT NULL,
deviceGroup varchar(50) NOT NULL,
registrationDate datetime NOT NULL,
lastAction datetime NOT NULL,
cultureLanguage varchar(2) NOT NULL,
cultureRegion varchar(2) NOT NULL,
cultureCode varchar(5) NOT NULL DEFAULT 'de-de',
lastPush datetime DEFAULT NULL,
pushToken mediumtext,
permaToken varchar(74) DEFAULT NULL,
accessCount int(11) NOT NULL DEFAULT '0',
access varchar(1) NOT NULL DEFAULT '1',
provider varchar(255) NOT NULL,
providerTld varchar(5) NOT NULL,
environment tinyint(1) DEFAULT '0',
udidMd5 varchar(32) NOT NULL,
development tinyint(1) DEFAULT '0',
PRIMARY KEY (id),
UNIQUE KEY userId_2 (userId),
UNIQUE KEY permaAccessToken_2 (permaToken),
KEY client (client),
KEY lastAction (lastAction),
KEY deviceGroup (deviceGroup),
KEY osVersion (osVersion),
KEY cultureCode (cultureCode),
KEY udidMd5 (udidMd5`)
) ENGINE=InnoDB AUTO_INCRE

This looks like you might have hit a bug logged against Percona Server 5.5:

Concurrent duplicate inserts can violate a unique key constraint in InnoDB tables.

There is no fix and no reproducible test case for this bug yet. It has only been observed in a production environment.

The pattern described is:

• INSERT a value into a column with a unique constraint.

• DELETE that row.

• Two concurrent sessions INSERT new rows that have the same value as in the deleted row.

• Both sessions commit, and both of their INSERTs succeed.

The root cause might be related to unfinished purging of the deleted row. In InnoDB, deleting an entry from an index is a multi-step process. First, the entry is "delete-marked" which leaves the entry in the index so as to postpone the physical removal from the index. Then later, the purge thread performs the final removal, which may include some rebalancing of the B-tree.

If you try to insert the same value as one which is delete-marked, it simply removes its delete mark, and associates the value with the new row you insert.

Based on the bug report, it seems that while the deleted entry is merely delete-marked, but not yet purged, two concurrent sessions can insert the same value. This probably happens all the time on non-unique indexes, and it's no problem. But of course this is a problem if the index is a unique index.

Sorry, there's no resolution to this bug yet. I encourage you to log into launchpad and register that this bug affects you. If you can post additional information about how the bug occurs in your environment, that would be helpful too. Best of all is if you can help create a reproducible test case!

Also, this might be related to a bug against stock MySQL: Bug #69979 columns with unique key gets intermittent duplicate values! although some details are different. That MySQL bug was closed as "not a bug" because the developers apparently concluded that in InnoDB's MVCC architecture, it's acceptable for some conflicts to occur and produce invalid results based on race conditions. IMHO, this should earn them a resounding "WTF?!"

StackExchange Database Administrators Q#71522, answer score: 7