Atomic flushing without locking

Index pages have the following attributes:

• dirty - this page has been changed and is not on the disk at all. This page must first be written to the flush log.
• in_db - this page is has not been changed, and is in the database. It can be removed from the cache at any time.
• flush_index - the location of the page in the flush log (zero if not in the flush log)

!dirty && !in_db - this page has been written to the flush log

dirty && in_db - not possible

All dirty pages are linked together.

To change an index:

1. Lock the index
2. Remember the flush phase
3. Do all changes to index pages
4. Unlock the index

When a page is changed:

1. If the page is dirty:
2. - update the page in the cache
3. If the page is not dirty:
4. - if the page is in the flush log (flush_index != 0) and flush phase 1 (see below) is in progress:
5. * update the cache, and update the flush log
6. - else
7. * update the cache, set dirty=true, in_database=false.
8. * add the page to the dirty list

In order to flush the index:

= flush phase 1
- For each page in the dirty list:
* Write the page to flush log
* Set flush_index to the location of the page in the flush log.
* Remove the page from the dirty list
- set phase to 2
- lock the index.
- For each page in the dirty list:
* Write the page to flush log
* Set flush_index to the location of the page in the flush log.
* Remove the page from the dirty list
- unlock the index
- We now have a snapshot of the index in the flush log.

= flush phase 2
- for each page in the flush log:
* write the page to the database.
* if the page in the index is not dirty, set in_database=true
- truncate the flush log
- flush index is complete

Index recovery (on startup)
- For each flush log
* write the index pages to the database

Complete recovery of the database involves first doing index recovery.
Then we do record recovery. Recovery of the record involves creating and deleting index entries as necessary.