|
|
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 shared with the first revision
|
|
|
entry.
|
|
|
|
|
|
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 the remainder of the first index entry.
|
|
|
Following that are remaining *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-3 (4 bytes) (rev 0 only)
|
|
|
Revlog header
|
|
|
0-5 (6 bytes)
|
|
|
Absolute offset of revision data from beginning of revlog.
|
|
|
6-7 (2 bytes)
|
|
|
Bit flags impacting revision behavior. The following bit offsets define:
|
|
|
0: REVIDX_ISCENSORED revision has censor metadata, must be verified.
|
|
|
1: REVIDX_EXTSTORED revision data is stored externally.
|
|
|
8-11 (4 bytes)
|
|
|
Compressed length of revision data / chunk as stored in revlog.
|
|
|
12-15 (4 bytes)
|
|
|
Uncompressed length of revision data. This is the size of the full
|
|
|
revision data, not the size of the chunk post decompression.
|
|
|
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.
|
|
|
|
|
|
The first 4 bytes of the revlog are shared between the revlog header
|
|
|
and the 6 byte absolute offset field from the first revlog entry.
|
|
|
|
|
|
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.
|
|
|
|
