[PATCH] internals: document revlog format
Gregory Szorc
gregory.szorc at gmail.com
Sat Jan 2 22:36:02 UTC 2016
# 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
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
More information about the Mercurial-devel
mailing list