The current embedded header should be able to be read from the database.

When committing a write session, a new grain id for the embedded header should be able to be specified. An error should be raised if an attempt to commit a write session occurs while another write session is queued that also modifies the header.

Currently it's possible to read GrainIds that haven't been committed. This really isn't a big deal the way this file format is designed and its limited API -- the only way to get a GrainId to read is by writing to it. However, by allowing the read to succeed isn't true isolation.

The read operation should check the batch id and ensure it's been committed before returning.

A new function to WriteSession should be added that allows reading grains that were written during the session.

The Committer builds a list of structure write operations that all need to happen before the fsync command is issued. Currently, these are written serially, but these should be able to be written using different strategies depending on the IO backend.

Two ways I have envisioned this so far:

• A function that takes a list of IoBuffers and the offsets to write them at. It returns when all writes are completed.
• Moving file IO to a thread pool and allowing write operations to be queued with a handle to wait for completion.

The latter sounds like it could be better, but it also is going to be more complex juggling the file handles with multiple threads.

Either way, one last goal of this is that Database should implement Clone, and currently the File abstraction is preventing this.

Internally, we need this to implement recovery/validation (#1). Externally, access to the commit log would allow users to build a replication log.

We need APIs for:

• Querying the current range of BatchIds in the commit log.
• Querying for individual commit log entries.

Checkpointing is the process that allows Sediment to release archived data and reuse the storage space. To allow for a flexible MVCC paradigm, Sediment does not immediately free data, but rather marks the grain as archived during a commit.

Checkpointing the database is easy: provide the BatchId of the commit that you are ready to allow data to be released from. Using this BatchId (the checkpoint id):

• Blocked by #2
• Find all commit log entries that are for BatchIds less than or equal to the checkpoint id
  • Note each archived grain in each commit log entry.
• Initiate a commit that:
  • Updates all grain maps and grain maps pages to reflect all archived grains are now free
  • Updates the header with the new checkpoint id
  • Marks any disk space used by commit log pages that are older than the checkpoint as free

We need the ability to archive one or more GrainIds. This will mark the data as ready to archive, but the grain will not be reused until the database "checkpoint" (#3) has moved to or beyond the BatchId of the archive operation.

All headers except the GrainMap have a way to be toggled from the root. But for grain maps, we want to be able to change grain allocations without rewriting basins or stratum.

This means that when we're recovering a file and rolling back the last change, we must mark the bad version of the GrainInfo as incorrect, probably by clearing its sequence. This will ensure when loading information in the future that we can always assume the highest sequence is the current sequence.

To finish recovery, we should probably do a two-stage fsync on recovery:

• Delete broken GrainInfos, forcing the use of the current GrainInfo.
• fsync
• Roll FileHeader back, allowing the next load to not enter recovery mode.
• fsync
• Proceed with opening the database.

Rolling back a GrainInfo is safe because a grain's contents are immutable. So, the state change is either going from:

• Free to Assigned: The revert just changes the status back to Free.
• Assigned to Archived: The revert just changes the status back to Free. Because archiving does not alter the stored data, the existing data will still be available.
• Archived to Free: Again, the revert just changes the status. Because the data will not be able to be used until the next commit after the grain is marked as free, the existing data will still be intact.

One of the downsides of the current approach to grain allocation is that a value can only be split into 255 consecutive grains. The result of this is that a 4GB write must be done in a grain map that is 2^24 or larger.

Another downside (or benefit when spun in a different light) is that each grain map page contains 4,084 grains. That means to store a 4GB value in a 16MB grain size, a total of 65 gigs will be allocated for the grain map page's contents.

This sounds completely egregious, but it is simply a 1:16 ratio. At smaller sizes, it doesn't sound that crazy. On larger sizes, it's definitely overkill. Rather than let users shoot themselves in the foot with these massive allocations, while discussing with @daxpedda the other day, we thought combining these two things would be a good approach:

• Implement a configuration option for maximum grain size. This would prevent grain maps being allocated larger than a specified size.
• Implement a large blob storage that allocates ranges of pages for values larger than the maximum grain size. The stratum needs to be configured such that it can be recognized as a special type of stratum. This can encode page ranges and number of pages in 10 bytes, allowing for 409 oversized blobs per page.

The downside of this approach to oversized blobs is that each page of these blob headers will need to be scanned on load to understand what regions of the file are currently allocated.

If a lot of data is written and then removed, currently Sediment will never shrink the file. We should implement a function that attempts to relocate blocks of data from the end of the file to earlier locations in the file, allowing us to truncate the file once everything is copied.

We may want to tackle #8 before this, as it would enable even more space reclamation.

This process may require multiple commits to proceed, and reservations cannot be made against grain maps that are in the process of being relocated.

Currently sediment is limited to one grain map per stratum, and each grain map is currently hard-coded to 1 page of grains. These two restrictions limiting Sediment to ~11 million grains per file.

The format is designed to support two approaches for growing to larger sizes:

1. Expand a stratum to have more pages per grain map
2. Add another grain map to the stratum

My current vision is to grow the page count first until a sensible limit, and then switch to adding more grain maps.

Challenges in solving this:

• Expanding a stratum to have more pages will always require copying the data to a new location in the file, due to needing to have additional space for the extra grain data and page data. We need to ensure that no reservations are made for this grain map while this operation is happening.
• Unit testing these situations is going to be fun. Best idea I've come up with is to allow an artificial limit to the number of strata and basins a file can contain, specifically to be able to test these algorithms on smaller databases.

Pretend someone fills a database such that many grain maps are allocated in a single stratum. Now, imagine all except one grain is freed, and the grain is in the last page of the last map.

If we support an operation to rewrite the database to reclaim disk space, we would currently be limited by not being able to skip all of the freed grains.

The easiest implementation is to allow storing 0 for a grain map offset. When encountered, all grains will be assumed to be free.

This does not solve how to reduce the number of pages in a stratum -- but that may not be solvable. But realistically, who is going to grow a database to such a high order of magnitude, then delete all that data and be unlikely to reload a large amount of data again?

Just implementing the ability to deallocate grain maps when they're completely free seems like a big win that will likely be enough for all practical use cases.

The file header is pretty tightly packed already, and I want to include at least a version number. A magic code would be excellent as well.

It seems wasteful to add an entire page at the start of the file for this, however, and I don't want other structures to not be page-aligned. So I had the idea to call it a metadata header to try to inspire some ideas of what might be stored in it.

My thoughts are to add a single page at the start of the file that contains two copies of this metadata header. By counting on powersafe overwrite, we can just rewrite the page whenever it changes. The format could be simple:

• 4 bytes magic code
• 4 bytes version code
• 4 bytes CRC of following bytes
• Repeated for remaining 2036 bytes:
  • 1 byte: metadata tag
  • 1 byte: metadata length
  • [metadata]

This would limit metadata entries to 255 bytes, but the type of metadata I'm thinking of wanting to store would work just fine in there. For example, a unique database ID probably wouldn't be more than 16 bytes of random data.

The current grain reservation "algorithm" is basically a brute force algorithm.

There should be a better way to keep track of free blocks on a per-grain-size basis. This solution should scale to a large number of grain maps such that only a handful of maps need to be kept in memory per grain size.

Having such a structure also makes it more likely that allocations will come from the same grain maps, minimizing the number of writes per commit.

Another problem to potentially solve: Reserving a grain is one location where currently there is no parallelism: each writer reserving a grain will block others from reserving a grain. Once the reservation is complete, each writer can write simultaneously. It would be amazing if the refactor could remove this synchronization point.