Obsstore Format

This page is intended for developer

This an archive page extracted from ChangesetEvolutionDevel. It contains data related to discussion and design of the obsstore format. V2 of the format have been implemented for a couple of year so this page is kept for historical purpose.

Markers are stored in an append-only file stored in '.hg/store/obsstore'.

V1 (old) Format

(see in line document for latest data)

quick summary

• <number-of-successors(=N)><metadata-lenght(=M)><bits-field><precursor>(<successor>*N)<metadata>

• B, I, B, 20s, (20s*N), s*M

longer explanation

The file starts with a version header:

• 1 unsigned byte: version number, starting at zero.

The header is followed by the markers. Each marker is made of:

• 1 unsigned byte: number of new changesets "N", can be zero.
• 1 unsigned 32-bits integer: metadata size "M" in bytes.
• 1 byte: a bit field. It is reserved for flags used in common
  • obsolete marker operations, to avoid repeated decoding of metadata entries.
• 20 bytes: obsoleted changeset identifier.
• N*20 bytes: new changesets identifiers.
• M bytes: metadata as a sequence of nul-terminated strings. Each
  • string contains a key and a value, separated by a colon ':', without additional encoding. Keys cannot contain '\0' or ':' and values cannot contain '\0'.

V2 (current) Format

motivation

There is two extra information we would like to see in a second version of the format:

• date: There is currently *always* a date in the meta data. So storing it explicitly would be more space efficient. It would also open the way to quickly access the date for sorting purpose (no use case yet but not crazy to think about it)
• parents: When a changesets is pruned (obsoleted, no successors) we needs to records its parents. This is necessary to link the markers chain to the push/pull operation it is relevant to.
• We may want to extend the bit field to 2 bytes. We currently use 1 and can see use case for 3-5 others (tracking the type of changes introduce by the rewriting (desc, patches, content, etc) so we are running short
• We may also want to explicitly store the username of the marker's creator are they will always be ones. however there is no need for quick access of such information so it could stay in the metadata field.

possibles change

Date:

• The date will be a 64bits float (for seconds since epoch) followed by a 16 bits integer (time zone)
• It will make sense to put the date in front of the markers. that would give markers sorting some semantic.

Parents:

We have multiple option for storing parents:

1. Having an explicite field similar to successors (one byte to know how many parents, then parents)
2. Having an explicite field but store the number of parent in the bit fields (since we never have more than 2 parents)
3. Using the successors field. Having negative number of successors mean it is a prune.

Option (3) is the most space saving but prevent use to store parent information for more changesets if needed in the future (We do not have a final exchange plan yet).

Option (1) and (2) takes 2 to 8 bits more than (3) but are more flexible.

bit field

If we extend the bit field to 2 Bytes, it makes sense to use option (2) for storing parent.

proposed V2 Format

• <date><timezone><number-of-successors(=N)><metadata-lenght(=M)><bits-field+nb-parents(=P)><precursor>(<successor>*N)(<parents>*P)<metadata>

• d, h, B, I, H, 20s, (20s*N), (20s*P), s*M

The P number would be hidden in the bit field. We need to store 4 possible values here: 0 parents, 1 parent, 2 parents, ø parents information stored. Possible assignement is 00, 01, 10, 11. this let both 0 parent and ø parent info to be 0 module 3.

V3 (future) format

Motivation

• provide a scalable format, that can be used "in place" (eg: with mmap),
  • without having to parse the full data for each runs.
• unify the handling of split and fold (and prune).
  • Split have been tracked for a long time and use a single marker with multiple successors. Fold are tracked since hg-4.8, they use multiple 1-1

    markers with fold-id identifier, fold-size and fold-idx metadata.

• binary encode recurrent data that have been added (eg: effect flag, fold-id
  • fold-idx, etc)

proposed changes

• Current plan would be to unify on 1-1 markers. It seems simpler, and more
  • extensible. It possibly open the way to having unified split+fold. The same 1-1 markers could be used for prune. Either by using nullrev for

    the second parent, or by storing the parent in the "successors" node. That last variant would requires two markers to be created on prune, but it could also simplify the linked-list approach.

• The binary format need update to integrate new data, actual details are to
  • be specified (but this ain't rocket science)
• Using a multi-files (docket, index, data) approche, similar to what we did
  • for Nodemap. See next section for details.
• Providing "in place" mapping for the common set (successors-markers,
  • predecessors-markers, children-prune-markers). Using a system of linked list, each new item added to a set would point to the previously last item in the list. See next section for details.

Architecture overview

• .hg/obstore.op: a docket file containing obstore ID, index size and other metadata

• .hg/obstore-ID.oi: index file, matching changesets nodes to actual data

• .hg/obstore-ID.od: the data file containing the actual markers

docket file

The principle and content is similar to the persistent Nodemap Docket.

• current data ID
• size of the index
• number of "dead" bytes currently in the index.

The docket is updated at each transaction (that adds obsmarker)

index file

The index file is mostly similar to the persistent nodemap. A radix tree allow lookup using node prefix. However the data stored is a bit different. The nodemap store a revision number, while the obstore-index store a triplet of addresses of one obsmarker block within the data file. The three value stored address:

• the latest obsmarker block using this node as a predecessor (or None)
• the latest obsmarker block using this node as a successors (or None)
• the latest obsmarker block using this node as a parents (or the pruned changesets) (or None)

Same as for persistent nodemap, once a non-ambiguous prefix has been found, we need to validate that it match the full node we are looking for. To do so, we will have to check the node stored in one of the pointed markers.

Same as for persistent nodemap, after a transaction, the necessary new radix-tree block are appended to the file. When the dead-block / all-block ratio becomes too high, the index file is rewritten from scratch and a new ID is used.

data file

The data file contains marker blocks. A marker block starts with a triplet (or more likely tuple) of other block address (or None), then an obsmarker. The address in the initial triplet (more likely tuple) point to:

• the previous obsmarker block using this node as a predecessor (or None)
• the previous obsmarker block using this node as a successors (or None)
• the previous obsmarker block using this node as a parents (or the pruned changesets (or None)

CategoryDeveloper CategoryEvolution