boltdb/bolt — pull request #20 by benbjohnson (2014-02-10 23:58:08+00:00)
Title: Freelist

## Overview

Bolt previously used an append-only B+tree (AOBT) and would only allocate new pages at the end of the file. AOBTs are good because they preserve old data that other transactions may need while letting the writer transaction continue to make progress lock-free. The downside is that it fills up your hard disk _really_ fast.

The **freelist** keeps track of what pages are no longer used by old transactions and allows those pages to be reused by the database. This preserves the copy-on-write semantics of AOBT while preventing the database from constantly growing and it only uses a quick lock when a transaction is created.

## How it works

The `DB` holds a single freelist that is shared across `RWTransactions`. Whenever the writer writes a node, it will add the node's previous page id to the freelist and associate it with the transaction's id. The page will initially be in a "pending" state.

When the next writer transaction is created it will find the lowest transaction id of any open reader transactions and release all pending pages for older transactions. This ensures that pages used by old transactions cannot be overwritten.

The freelist is saved to a special page type called the "freelist" page. This page simply contains a count of pages and a sorted list of free page ids. When the freelist is saved it saves all pending and released pages. In the event of a program crash, all transactions are automatically closed so all pending pages are automatically released.

## Other Notes

This pull request also includes some housekeeping and I added pending test cases. Test coverage is at ~87% but once the pending test cases are completed then coverage should be around 100%.

I also added the writer lock so there can only be one open `RWTransaction` at a time. If another writer transaction is requested then it will hang until the first one is committed or rolled back.

/cc: @snormore