boltdb/bolt — pull request #193 by benbjohnson (2014-06-13 14:04:36+00:00)
Title: Check for freelist overflow

## Overview

The freelist uses the standard page header so it is limited to a maximum of 65,565 pages (because `page.count` is a uint16). Bolt currently does not handle fragmentation caused by large overflow pages so using large values or bulk loading a large number of key/value pairs per transaction can cause this to occur.

This is only a stopgap solution to prevent database corruption.

## Long Term

As a long term solution, we need to either:

1. Compact the database.
2. Increase the page.count size.
3. Convert the freelist to a standard bucket (similar to how LMDB does it).

Option 1 is the most complicated but probably the best option considering Bolt's typical use case (e.g. small key/value pairs). Splitting nodes before commit will help prevent fragmentation from occurring during bulk load.

Option 2 will be backwards incompatible. That's not the worst thing since users can export/import if necessary, however, a 64k freelist is going to be really slow. This is not really a good option.

Option 3 will also be backwards incompatible. The bigger issue here is that managing a B+tree is more complicated than a simple array. Bolt's typically use case will usually keep the freelist small so adding this complexity is probably not worth the cost.

---

/cc @PreetamJinka