Fossil

Artifact [02e46328]
Login

Artifact [02e46328]

Artifact 02e46328cb1a6308a1e07a502456acf4e508d264f11942b1427bc5427a2a57eb:


<title>Fossil Repository Integrity Self-Checks</title>

<h1 align="center">Fossil Repository Integrity Self-Checks</h1>

Fossil is designed with features to give it a high level
of integrity so that users can have confidence that content will
never be mangled or lost by Fossil.
This note describes the defensive measures that
Fossil uses to help prevent information loss due to bugs.

Fossil has been hosting itself and many other projects for
years now.  Many bugs have been encountered.  But, thanks in large
part to the defensive measures described here, no data has been
lost.  The integrity checks are doing their job well.</p>

<h2>Atomic Check-ins With Rollback</h2>

The fossil repository is stored in an
<a href="http://www.sqlite.org/">SQLite</a> database file.
([./tech_overview.wiki | Addition information] about the repository
file format.)
SQLite is very mature and stable and has been in wide-spread use for many
years, so we are confident it will not cause repository
corruption.  SQLite
databases do not corrupt even if a program or system crash or power
failure occurs in the middle of the update.  If some kind of crash
does occur in the middle of a change, then all the changes are rolled
back the next time that the database is accessed.

A check-in operation in fossil makes many changes to the repository
database.  But all these changes happen within a single transaction.
If something goes wrong in the middle of the commit, even if that something
is a power failure or OS crash, then the transaction
is rolled back and the database is unchanged.

<h2>Verification Of Delta Encodings Prior To Transaction Commit</h2>

The content files that comprise the global state of a fossil repository
are stored in the repository as a tree.  The leaves of the tree are
stored as zlib-compressed BLOBs.  Interior nodes are deltas from their
descendants.  A lot of encoding is going on.  There is
zlib-compression which is relatively well-tested but still might
cause corruption if used improperly.  And there is the relatively
new delta-encoding mechanism designed expressly for fossil.  We want
to make sure that bugs in these encoding mechanisms do not lead to
loss of data.

To increase our confidence that everything in the repository is
recoverable, fossil makes sure it can extract an exact replica
of every content file that it changes just prior to transaction
commit.  So during the course of check-in (or other repository
operation) many different files
in the repository might be modified.  Some files are simply
compressed.  Other files are delta encoded and then compressed.
While all this is going on, fossil makes a record of every file
and the SHA1 or SHA3-256 hash of the original content of that
file.  Then just before transaction commit, fossil re-extracts
the original content of all files that were written, recomputes
the hash, and verifies that the recomputed hash still matches.
If anything does not match up, an error
message is printed and the transaction rolls back.

So, in other words, fossil always checks to make sure it can
re-extract a file before it commits a change to that file.
Hence bugs in fossil are unlikely to corrupt the repository in
a way that prevents us from extracting historical versions of
files.

<h2>Checksum Over All Files In A Check-in</h2>

Manifest artifacts that define a check-in have two fields (the
R-card and Z-card) that record MD5 hashes of the manifest itself
and of all other files in the manifest.  Prior to any check-in
commit, these checksums are verified to ensure that the check-in
agrees exactly with what is on disk.  Similarly,
the repository checksum is verified after a checkout to make
sure that the entire repository was checked out correctly.
Note that these added checks use a different hash algorithm (MD5)
in order to avoid common-mode failures in the hash
algorithm implementation.


<h2>Checksums On Structural Artifacts And Deltas</h2>

Every [./fileformat.wiki | structural artifact] in a fossil repository
contains a "Z-card" bearing an MD5 checksum over the rest of the
artifact.  Any mismatch causes the structural artifact to be ignored.

The [./delta_format.wiki | file delta format] includes a 32-bit
checksum of the target file.  Whenever a file is reconstructed from
a delta, that checksum is verified to make sure the reconstruction
was done correctly.

<h2>Reliability Versus Performance</h2>

Some version control systems make a big deal out of being "high performance"
or the "fastest version control system".  Fossil makes no such claims and has
no such ambition.  Indeed, profiling indicates that fossil bears a
substantial performance cost for
doing all of the checksumming and verification outlined above.
Fossil takes the philosophy of the
<a href="http://en.wikipedia.org/wiki/The_Tortoise_and_the_Hare">tortoise</a>:
reliability is more important than raw speed.  The developers of
fossil see no merit in getting the wrong answer quickly.

Fossil may not be the fastest versioning system, but it is "fast enough".
Fossil runs quickly enough to stay out of the developers way.
Most operations complete in milliseconds, faster that you can press
the "Enter" key.