INSERT ... ON DUPLICATE KEY UPDATE + innodb_autoinc_lock_mode=1 is broken

Concurrent INSERT ... ON DUPLICATE KEY UPDATE statements on a table with
an AUTO_INCREMENT column may result in spurious duplicate key errors
(and, as a result, lost data due to some rows being updated rather than
inserted) with the default value of innodb_autoinc_lock_mode=1.

The problem only appears with concurrently executing INSERT ... ON
DUPLICATE KEY UPDATE statements and is time-sensitive. Consider the
following table:

CREATE TABLE t(
       id INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
       k INT,
       c CHAR(1),
       UNIQUE KEY(k)) ENGINE=InnoDB;

and the following two statements:

INSERT INTO t(k) VALUES (1), (2), (3) ON DUPLICATE KEY UPDATE c='1'; /* (1) */
INSERT INTO t(k) VALUES (2), (4), (5) ON DUPLICATE KEY UPDATE c='2'; /* (2) */

When statements (1) and (2) are executed sequentially, table 't'
contains the following rows as a result:

id k c
1 1 NULL
2 2 2
3 3 NULL
4 4 NULL
5 5 NULL

(the non-NULL value of the 'c' column depends on the order of execution)

However, if both statements are executed concurrently, and statement (2)
starts and finishes while statement (1) execution is in progress, the
result of both statements may become as follows:

id k c
1 1 NULL
4 2 1
5 4 1
6 5 NULL

The attached .test file uses DEBUG_SYNC points to demonstrate that.

The workaround is to use innodb_autoinc_lock_mode=0, i.e. serialize such
statements with the InnoDB AUTO-INC lock. For example, try running the test
case with --mysqld=--innodb_autoinc_lock_mode=0

Naturally, this bug also breaks statement-based replication and results
in inconsistent slaves.

The root cause is that when the statements are executed concurrently in
such a way, InnoDB will correctly reserve non-overlapping AUTO_INCREMENT
intervals for each statement, but when the server encounters the first
duplicate key error on the secondary key in statement (1) and performs
an UPDATE, it also updates the internal AUTO_INCREMENT value to the one
corresponding to the row inserted by statement (2), even though it is
not specified explicitly in the UPDATE part. It will then proceed with
using AUTO_INCREMENT values for statement (1) from the range reserved
previously by statement (2), causing duplicate key errors on the
AUTO_INCREMENT column.