[PATCH] internals: document revlog format
Augie Fackler
raf at durin42.com
Tue Jan 5 11:06:26 CST 2016
On Sat, Jan 02, 2016 at 02:36:02PM -0800, Gregory Szorc wrote:
> # HG changeset patch
> # User Gregory Szorc <gregory.szorc at gmail.com>
> # Date 1451517717 25200
> # Wed Dec 30 16:21:57 2015 -0700
> # Node ID 71e6c0f1bd13841c126abaccf9d88a37de8efe15
> # Parent b8405d739149cdd6d8d9bd5e3dd2ad8487b1f09a
> internals: document revlog format
queued this, thanks.
>
> It seems like a good idea to document the revlog format.
>
> There is a lot more that could be added to this documentation.
> But you have to start somewhere.
>
> diff --git a/mercurial/help.py b/mercurial/help.py
> --- a/mercurial/help.py
> +++ b/mercurial/help.py
> @@ -182,16 +182,18 @@ def loaddoc(topic, subdir=None):
>
> return loader
>
> internalstable = sorted([
> (['bundles'], _('container for exchange of repository data'),
> loaddoc('bundles', subdir='internals')),
> (['changegroups'], _('representation of revlog data'),
> loaddoc('changegroups', subdir='internals')),
> + (['revlogs'], _('revision storage mechanism'),
> + loaddoc('revlogs', subdir='internals')),
> ])
>
> def internalshelp(ui):
> """Generate the index for the "internals" topic."""
> lines = []
> for names, header, doc in internalstable:
> lines.append(' :%s: %s\n' % (names[0], header))
>
> diff --git a/mercurial/help/internals/revlogs.txt b/mercurial/help/internals/revlogs.txt
> new file mode 100644
> --- /dev/null
> +++ b/mercurial/help/internals/revlogs.txt
> @@ -0,0 +1,193 @@
> +Revisions Logs
> +==============
> +
> +Revision logs - or *revlogs* - are an append only data structure for
> +storing discrete entries, or *revisions*. They are the primary storage
> +mechanism of repository data.
> +
> +Revlogs effectively model a directed acyclic graph (DAG). Each node
> +has edges to 1 or 2 *parent* nodes. Each node contains metadata and
> +the raw value for that node.
> +
> +Revlogs consist of entries which have metadata and revision data.
> +Metadata includes the hash of the revision's content, sizes, and
> +links to its *parent* entries. The collective metadata is referred
> +to as the *index* and the revision data is the *data*.
> +
> +Revision data is stored as a series of compressed deltas against previous
> +revisions.
> +
> +Revlogs are written in an append-only fashion. We never need to rewrite
> +a file to insert nor do we need to remove data. Rolling back in-progress
> +writes can be performed by truncating files. Read locks can be avoided
> +using simple techniques. This means that references to other data in
> +the same revlog *always* refer to a previous entry.
> +
> +Revlogs can be modeled as 0-indexed arrays. The first revision is
> +revision #0 and the second is revision #1. The revision -1 is typically
> +used to mean *does not exist* or *not defined*.
> +
> +File Format
> +-----------
> +
> +A revlog begins with a 32-bit big endian integer holding version info
> +and feature flags.
> +
> +This integer is logically divided into 2 16-bit shorts. The least
> +significant half of the integer is the format/version short. The other
> +short holds feature flags that dictate behavior of the revlog.
> +
> +Only 1 bit of the format/version short is currently used. Remaining
> +bits are reserved for future use.
> +
> +The following values for the format/version short are defined:
> +
> +0
> + The original revlog version.
> +1
> + RevlogNG (*next generation*). It replaced version 0 when it was
> + implemented in 2006.
> +
> +The feature flags short consists of bit flags. Where 0 is the least
> +significant bit, the following bit offsets define flags:
> +
> +0
> + Store revision data inline.
> +1
> + Generaldelta encoding.
> +
> +2-15
> + Reserved for future use.
> +
> +The following header values are common:
> +
> +00 00 00 01
> + RevlogNG
> +00 01 00 01
> + RevlogNG + inline
> +00 02 00 01
> + RevlogNG + generaldelta
> +00 03 00 01
> + RevlogNG + inline + generaldelta
> +
> +Following the 32-bit header is *index* data. Inlined revision data is possibly
> +located between index entries. More on this layout is described below.
> +
> +RevlogNG Format
> +---------------
> +
> +RevlogNG (version 1) begins with an index describing the revisions in
> +the revlog. If the ``inline`` flag is set, revision data is stored inline,
> +or between index entries (as opposed to in a separate container).
> +
> +Each index entry is 64 bytes. The byte layout of each entry is as
> +follows, with byte 0 being the first byte (all data stored as big endian):
> +
> +0-5 (6 bytes)
> + Absolute offset of revision data from beginning of revlog.
> +6-7 (2 bytes)
> + Bit flags impacting revision behavior.
> +8-11 (4 bytes)
> + Compressed length of revision data / chunk as stored in revlog.
> +12-15 (4 bytes)
> + Uncompressed length of revision data / chunk.
> +16-19 (4 bytes)
> + Base or previous revision this revision's delta was produced against.
> + -1 means this revision holds full text (as opposed to a delta).
> + For generaldelta repos, this is the previous revision in the delta
> + chain. For non-generaldelta repos, this is the base or first
> + revision in the delta chain.
> +20-23 (4 bytes)
> + A revision this revision is *linked* to. This allows a revision in
> + one revlog to be forever associated with a revision in another
> + revlog. For example, a file's revlog may point to the changelog
> + revision that introduced it.
> +24-27 (4 bytes)
> + Revision of 1st parent. -1 indicates no parent.
> +28-31 (4 bytes)
> + Revision of 2nd parent. -1 indicates no 2nd parent.
> +32-63 (32 bytes)
> + Hash of revision's full text. Currently, SHA-1 is used and only
> + the first 20 bytes of this field are used. The rest of the bytes
> + are ignored and should be stored as \0.
> +
> +If inline revision data is being stored, the compressed revision data
> +(of length from bytes offset 8-11 from the index entry) immediately
> +follows the index entry. There is no header on the revision data. There
> +is no padding between it and the index entries before and after.
> +
> +If revision data is not inline, then raw revision data is stored in a
> +separate byte container. The offsets from bytes 0-5 and the compressed
> +length from bytes 8-11 define how to access this data.
> +
> +Delta Chains
> +------------
> +
> +Revision data is encoded as a chain of *chunks*. Each chain begins with
> +the compressed original full text for that revision. Each subsequent
> +*chunk* is a *delta* against the previous revision. We therefore call
> +these chains of chunks/deltas *delta chains*.
> +
> +The full text for a revision is reconstructed by loading the original
> +full text for the base revision of a *delta chain* and then applying
> +*deltas* until the target revision is reconstructed.
> +
> +*Delta chains* are limited in length so lookup time is bound. They are
> +limited to ~2x the length of the revision's data. The linear distance
> +between the base chunk and the final chunk is also limited so the
> +amount of read I/O to load all chunks in the delta chain is bound.
> +
> +Deltas and delta chains are either computed against the previous
> +revision in the revlog or another revision (almost certainly one of
> +the parents of the revision). Historically, deltas were computed against
> +the previous revision. The *generaldelta* revlog feature flag (enabled
> +by default in Mercurial 3.7) activates the mode where deltas are
> +computed against an arbitrary revision (almost certainly a parent revision).
> +
> +File Storage
> +------------
> +
> +Revlogs logically consist of an index (metadata of entries) and
> +revision data. This data may be stored together in a single file or in
> +separate files. The mechanism used is indicated by the ``inline`` feature
> +flag on the revlog.
> +
> +Mercurial's behavior is to use inline storage until a revlog reaches a
> +certain size, at which point it will be converted to non-inline. The
> +reason there is a size limit on inline storage is to establish an upper
> +bound on how much data must be read to load the index. It would be a waste
> +to read tens or hundreds of extra megabytes of data just to access the
> +index data.
> +
> +The actual layout of revlog files on disk is governed by the repository's
> +*store format*. Typically, a ``.i`` file represents the index revlog
> +(possibly containing inline data) and a ``.d`` file holds the revision data.
> +
> +Revision Entries
> +----------------
> +
> +Revision entries consist of an optional 1 byte header followed by an
> +encoding of the revision data. The headers are as follows:
> +
> +\0 (0x00)
> + Revision data is the entirety of the entry, including this header.
> +u (0x75)
> + Raw revision data follows.
> +x (0x78)
> + zlib (RFC 1950) data.
> +
> + The 0x78 value is actually the first byte of the zlib header (CMF byte).
> +
> +Hash Computation
> +----------------
> +
> +The hash of the revision is stored in the index and is used both as a primary
> +key and for data integrity verification.
> +
> +Currently, SHA-1 is the only supported hashing algorithm. To obtain the SHA-1
> +hash of a revision:
> +
> +1. Hash the parent nodes
> +2. Hash the fulltext of the revision
> +
> +The 20 byte node ids of the parents are fed into the hasher in ascending order.
> \ No newline at end of file
> diff --git a/tests/test-help.t b/tests/test-help.t
> --- a/tests/test-help.t
> +++ b/tests/test-help.t
> @@ -870,16 +870,17 @@ Test list of internal help commands
> internals topic renders index of available sub-topics
>
> $ hg help internals
> Technical implementation topics
> """""""""""""""""""""""""""""""
>
> bundles container for exchange of repository data
> changegroups representation of revlog data
> + revlogs revision storage mechanism
>
> sub-topics can be accessed
>
> $ hg help internals.changegroups
> Changegroups
> ============
>
> Changegroups are representations of repository revlog data, specifically
> @@ -2686,16 +2687,23 @@ Sub-topic indexes rendered properly
> </td></tr>
> <tr><td>
> <a href="/help/internals.changegroups">
> changegroups
> </a>
> </td><td>
> representation of revlog data
> </td></tr>
> + <tr><td>
> + <a href="/help/internals.revlogs">
> + revlogs
> + </a>
> + </td><td>
> + revision storage mechanism
> + </td></tr>
>
>
>
>
>
> </table>
> </div>
> </div>
> diff --git a/tests/test-install.t b/tests/test-install.t
> --- a/tests/test-install.t
> +++ b/tests/test-install.t
> @@ -99,15 +99,16 @@ path variables are expanded (~ is the sa
> $ python wixxml.py help
> Not installed:
> help/common.txt
> help/hg.1.txt
> help/hgignore.5.txt
> help/hgrc.5.txt
> help/internals/bundles.txt
> help/internals/changegroups.txt
> + help/internals/revlogs.txt
> Not tracked:
>
> $ python wixxml.py templates
> Not installed:
> Not tracked:
>
> #endif
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel
More information about the Mercurial-devel
mailing list