Handling multiple writes to a given byte from the same process

Thinking about this more since our call, if we allow a process to write to a given byte more than once, there are several interesting approaches we’ll have to pick from. Just a few that come to mind:

Return all keys and sort through them on read
include a timestamp of some sort in key/value pair, could be actual time-of-day or logical clock
given a byte range during a read(), return all keys referring to bytes in that range, sort resulting key/value pairs by timestamp to find most recent key/value pair for each byte, then finally fetch data for each byte

Flatten index during lamination:
Under the lamination model, a process cannot add more data once laminated. We could flatten the key/value index to precompute the most recent key/value pair for each byte at lamination time and then discard/rewrite key/values that correspond to obsolete data. With that, the added complexity in the read logic above can be avoided. If we just allow a single process to overwrite a byte, this flattening step can be done on the local index before we insert keys in the global distributed index.

Flatten index on first read:
In the case that reading the file back is unlikely (e.g., checkpoint data), we could delay the flatten step until the first read. That could speed up the write operation.

Finally, if all of this sorting/flattening adds overhead, it’d be nice to have a mode where it can be avoided so long as the app asserts that it does not need it. Sounds like HDF5 needs it, so we should aim to support HDF5 first, but we can keep this optimization in mind.

I’m sure we’ll think of yet more variations…. Fun problem.

The issue names no files, tests, or entry points to begin with. Read the proposed write, read, lamination, and index-flattening approaches with the maintainers before starting; the desired behavior and completion criteria still need to be decided.