Haskell Persisted Allocator Thoughts

persisted_allocator.txt

Borrow ideas from LMDB. LMDB starts with two pages at the very beginning of the memory-mapped file.
Writing to either page indicates that a transaction has completed. In LMDB, each of these pages
has pointers to two b-trees. One of those trees is a free page list (there is no garbage collection).
The other is the root page of the database.

In building a database with haskell, my first goal is to implement this approach to transactions.
It should be its own library. The interface is:

    -- A wrapper around int, just an increasing id.
    data Transaction 
    
    -- A wrapper around a Ptr to the begginning of mmapped memory 
    data Database

    -- The beginning of the list of free nodes. Also, the last-used page.
    -- This should be consumed linearly.
    data Metadata

    -- Wrapper around a pointer to the beginning of a page. The first
    -- machine word in here is the size.
    data Page
    
    open :: FilePath -> IO Database

    transaction :: Database -> (Metadata -> IO a) -> IO a
    
    -- Remove a page from the free list or bump the last used page. The
    -- user can specify a size.
    allocate :: Metadata -> Int -> IO (Page,Metadata)

    -- Adds the page to the free list.
    deallocate :: Metadata -> Page -> IO Metadata

This should work. One performance problem that comes to mind is that bulk page allocation
may be desired. Doing this one at a time would be slow though, so it may be useful to
provide:

    allocateMany :: Metadata -> Int -> Int -> IO (PrimArray Page,Metadata)

We may also want:

    data Page4K
    allocate4K :: Metadata -> IO (Page4K,Metadata)
    deallocate4K :: Metadata -> Page4K -> IO Metadata

A Page4K does not need to include the size of the page. The free list can also be
much more simple since it does not need to coalesce adjacent pages.