where is uncommitted data stored, such that a READ_UNCOMMITTED transaction can read uncommitted data from another transaction?
In order to answer your question, you need to know what the InnoDB Architecture looks like.
The following picture was created years ago by Percona CTO Vadim Tkachenko
According to MySQL Documentation on The InnoDB Transaction Model and Locking
A COMMIT means that the changes made in the current transaction are made permanent and become visible to other sessions. A ROLLBACK statement, on the other hand, cancels all modifications made by the current transaction. Both COMMIT and ROLLBACK release all InnoDB locks that were set during the current transaction.
Since COMMIT and ROLLBACK govern data visibility, READ COMMITTED and READ UNCOMMITTED would have to rely on structures and mechanisms that record changes
- Rollback Segments / Undo Space
- Redo Logs
- Gaps Locks Against the Table(s) Involved
Rollback Segments and Undo Space would know what changed data looked like before changes are applied. Redo Logs would know what changes are to be rolled forward to have data appear updated.
You also asked
why isn't it possible for a READ_COMMITTED transaction to read uncommitted data, i.e. performing a "dirty read"? What mechanism enforce this restriction?
Redo Logs, Undo Space and Locked rows are come into play. You must also considert he InnoDB Buffer Pool (where you can measure dirty pages with innodb_max_dirty_pages_pct, innodb_buffer_pool_pages_dirty and innodb_buffer_pool_bytes_dirty).
In light of this, READ COMMITTED would know what data appears like permanently. Therefore, there is no need to look for dirty pages that were not committed. READ COMMITED would be nothing more that a dirty read that has been committed. READ UNCOMMITTED would have continue to know what rows are to be locked and what redo logs has be read or ignored to make the data visible.
To fully understand the Locking of Rows to Manage Isolation, please read The InnoDB Transaction Model and Locking