Branch reflog vs branch history

[jbms]

I'm starting work on adding icechunk support to Neuroglancer.

For ocdbt there is support for selecting either the HEAD version or a past version by generation number or commit timestamp.

It would be nice to add similar support for icechunk. Certainly adding support for an explicit snapshot id is easy, but for interactive use it would be nice to give users a way to select a past version explicitly.

It appears that for branches, icechunk essentially stores two parallel types of history: the sequence numbers of the ref files (basically equivalent to the reflog in git) and the "snapshot ancestry" linked list of parent references in a snapshot (equivalent to git commit DAG).

Git has syntax for accessing both types of history, though reflogs are ephemeral and local only.

As far as I can see, the icechunk python API provides access to the "snapshot ancestry" but not to the sequence number history. Perhaps the intention is that the sequence number history is just an implementation detail and may be eliminated/pruned at some point in the future? In particular, now that Amazon S3 supports full conditional writes, I think a major motivation for the sequence numbers rather than a single ref file that gets atomically updated is now gone.

In any case, the problem with the snapshot ancestry is that, being a linked list, it requires a separate sequential request per level of depth, which means with a long history it will be very slow to access.

In contrast, the sequence number history supports random access, which means accessing it is much more efficient, and if we assume timestamps are monotonically increasing could even do binary search to lookup a version by timestamp.

OCDBT solves this issue by storing a B+tree of versions, and requires commit times to be monotonically increasing, in order to allow efficient access to past versions. You might consider doing the same thing in icechunk if efficient access to past versions is desired.

[paraseba]

Perhaps the intention is that the sequence number history is just an implementation detail

Yes, as you pointed out, this was written to get consistency in a world before conditional writes.

which means with a long history it will be very slow to access.

Yes, this is not ideal, but we see a few paths for future improvement. History is very cacheable, but we do support expiration of snapshots, which edits history, so it has to be done very carefully.

OCDBT solves this issue by storing a B+tree of versions, and requires commit times to be monotonically increasing, in order to allow efficient access to past versions.

I don't see this as a real world Icechunk use case, at the moment. For a few reasons:

• people tend to prefer short histories, to save on storage. That was the motivation to write expiration in IC. It has been a feature request coming from many users of Arraylake.
• IC offers tags and branches, which usually alleviate the need for long traversal through the ancestry
• IC is optimized for large "jobs" more than for small low latency queries. The cost of the ancestry traversal gets amortized quickly

All that said, we are evaluating the possibility of switching branches to conditional updates. There are many things to think about though, like object store support, and consistency in the presence of expiration. It would also have other advantages too, like alowing us to resolve a branch without a list operation, which is faster and demands less from the object store.