The current auto_increment behavior in the InnoDB engine is sub-optimal. As it currently functions, the auto_increment value is stored until the server shuts down or resets, and then is rebuilt based on values in the table when it starts up again. Furthermore, in 5.6 this ought to become even worse, because tables can be evicted from the InnoDB data dictionary cache. We may get a too low auto-increment value even without shutdown/restart. When a table is evicted, InnoDB will forget the current auto-increment value, and it will do SELECT MAX(auto_inc_column) next time when the table is accessed.