storing "replaced" records
You could add one more field in your table, something like parent_id where you could store the primary key from which the new record is derived. And primary key will continue to auto-increment. I hope this will fix your confusion.