diff options
Diffstat (limited to 'www/delta-manifests.md')
| -rw-r--r-- | www/delta-manifests.md | 246 |
1 files changed, 246 insertions, 0 deletions
diff --git a/www/delta-manifests.md b/www/delta-manifests.md new file mode 100644 index 0000000..6899cbe --- /dev/null +++ b/www/delta-manifests.md @@ -0,0 +1,246 @@ +# Delta Manifests + +<div class="sidebar">Do not confuse these with the core [Fossil delta +format](./delta_format.wiki). This document describes an optional +feature not enabled by default.</div> + +This article describes "delta manifests," a special-case form of +checkin manifest which is intended to take up far less space than +a normal checkin manifest, in particular for repositories with +many files. We'll see, however, that the space savings, if indeed +there are any, come with some caveats. + +This article assumes that the reader is at least moderately familiar +with Fossil's [artifact file format](./fileformat.wiki), in particular +the structure of checkin manifests, and it won't make much sense to +readers unfamiliar with that topic. + +# Background and Motivation of Delta Manifests + +A checkin manifest includes a list of every file in that checkin. A +moderately-sized project can easily have a thousand files, and every +checkin manifest will include those thousand files. As of this writing +Fossil's own checkins contain 989 files and the manifests are 80kb +each. Thus a checkin which changes only 2 bytes of source code +ostensibly costs another 80kb of storage for the manifest for that +change. + +Delta manifests were conceived as a mechanism to help combat that +storage overhead. + +# Makeup of a Delta Manifest + +A delta manifest is structured like a normal manifest (called a +"baseline" manifest) except that it has *two types of parents*: the +P-card which is part of (nearly) every manifest and a so-called +baseline (denoted by a B-card). The P-card tells us which artifact(s) +is/are the parents for purposes of the SCM version DAG. The B-card +tells us which manifest to use as a basis for this delta. The B-card +need not be, and often is not, the same as the P-card. Here's an +example: + +``` +B c04ce8aaf1170966c6f8abcce8b57e72a0fa2b81 +C Minor\sdoc\supdates... +D 2021-03-11T18:56:24.686 +F bindings/s2/shell_extend.c 6d8354c693120a48cfe4798812cd24499be174b2 +<15 F-cards snipped for brevity> +F src/repo.c 2f224cb0e59ccd90ba89c597e40b8e8d87506638 +P 61d3e64e6fb1a93d4a7b0182e4c6b94d178d66d9 +R a84ec2e8e1eb37ff0d94cac262795e23 +U stephan +Z 536e6d26dd8dbe2779d9e5f52a15518e +``` + +The B-card names another manifest, by its unique ID, the same way that +a P-card does. A manifest may have multiple P-card parents (the second +and subsequent ones denoting merge parents) but B-cards always refer +to exactly one parent. + +What unambiguously distinguishes this as a delta is the existence of +the B-card. All deltas have a B-card and no other type of artifact has +one. What also, but not unambiguously, distinguishes it as a delta is +that it has only 17 F-cards, whereas a baseline manifest in that same +repository has (as of this writing) 291 F-cards. In this particular +case, the delta manifest is 1363 bytes, compared to 20627 bytes for +the next checkin - a baseline manifest. That's a significant saving in +F-cards, especially if a repository contains thousands of files. That +savings, however, comes with caveats which we'll address below. + +Trivia regarding the B-card: + +- The B-card always refers to a baseline manifest, not another delta. +- Deltas may not chain with another delta, but any number of deltas + may have the same B-card. It is quite common for a series of delta + manifest checkins, each of which derives (in the P-card sense) from + the one before it, to have the same B-card. + +A delta manifest is functionally identical to a normal manifest except +that it has a B-card and how it records F-cards. Namely, it only +records F-cards which have changed at some point between this delta +and the version represented by the delta's B-card. This recording of +F-card *differences* also means that delta manifests, unlike normal +manifests, have to explicitly record deleted F-cards. Baseline +manifests do not record deletions. Instead, they include a list of +every file which is part of that checkin. Deltas, however, record the +differences between their own version and a baseline version, and thus +have to record deletions. They do this by including F-cards which have +only a file name and no hash. + +Iterating over F-cards in a manifest is something several important +internal parts of Fossil have to do. Iterating over a baseline +manifest, e.g. when performing a checkout, is straightforward: simply +walk through the list in the order the cards are listed. A delta, +however, introduces a significant wrinkle to that process. In short, +when iterating over a delta's F-cards, code has to compare the delta's +list to the baseline's list. If the delta has an entry the parent does +not have, or which is a newer entry for the same file, the delta's +entry is used. If the delta is missing an entry which the baseline +has, the baseline's entry is used. When a deletion F-card is +discovered in the delta (recall that baselines do not record +deletions), iteration over that card is skipped - the internal +algorithms which iterate over F-cards never report deletions to the +code iterating over those cards. The reason for that is consistency: +only deltas record file deletions, but the fact that it's a delta is +an internal detail, not something which higher-level code should +concern itself with. If higher-level iteration code were shown file +deletions, they would effectively be dealing with a leaky abstraction +and special-case handling which only applies to delta manifests. The +F-card iteration API hides such details from its users (other +Fossil-internal APIs). + + +# When does Fossil Create Deltas? + +By default, Fossil never creates delta manifests. It can be told to do +so using the `--delta` flag to the [`commit` +command](/help/commit). (Before doing so in your own repositories, +please read the section below about the caveats!) When a given +repository gets a delta manifest for the first time, Fossil records +that fact in the repository's `config` table with an entry named +`seen-delta-manifest`. If, in later sessions, Fossil sees that that +setting has a true value, it will *consider* creating delta manifests +by default. + +Conversely, the [`forbid-delta-manifests` repository config +setting](/help/forbid-delta-manifests) may be used to force Fossil to +*never* create deltas. That setting will propagate to other repository +clones via the sync process, to try to ensure that no clone introduces +a delta manifests. We'll cover reasons why one might want to use that +setting later on. + +After creating a delta manifest during the commit process, Fossil +examines the size of the delta. If, in Fossil's opinion, the space +savings are not significant enough to warrant the delta's own +overhead, it will discard the delta and create a new baseline manifest +instead. (The heuristic it uses for that purpose is tucked away in +Fossil's checkin algorithm.) + + +# Caveats + +Delta manifests may appear, on the surface, to be a great way to save +a few bytes of repository space. There are, however, caveats... + +## Space Savings? + +Though deltas were conceived as a way to save storage space, that +benefit is *not truly achieved* because... + +When a manifest is created, Fossil stores its parent version as a +[fossil delta](./delta_format.wiki) (as opposed to a delta manifest) +which succinctly descibes the differences between the parent and its +new child. This form of compression is extremely space-efficient and +can reduce the real storage space requirements of a manifest from tens +or hundreds of kilobytes down to a kilobyte or less for checkins which +modify only a few files. As an example, as of this writing, Fossil's +[tip checkin baseline manifest](/artifact/decd537016bf) is 80252 bytes +(uncompressed), and the delta-compressed baseline manifest of the +[previous checkin](/artifact/2f7c93f49c0e) is stored as a mere 726 +bytes of Fossil-delta'd data (not counting the z-lib compression which +gets applied on top of that). In this case, the tip version modified 7 +files compared to its parent version. + +Thus delta manifests do not *actually* save much storage space. They +save *some*, in particular in the tip checkin version: Fossil +delta-compresses *older* versions of checkins against the child +versions, as opposed to delta-compressing the children against the +parents. The reason is to speed up access for the most common case - +the latest version. Thus tip-version delta manifests are more +storage-space efficient than tip-version baseline manifests. Once the +next version is committed, though, and Fossil deltification is applied +to those manifests, that difference in space efficiency shrinks +tremendously, often to the point of insignificance. + +We can observe the Fossil-delta compression savings using a bit of +3rd-party code which can extract Fossil-format blobs both with and +without applying their deltas: + +``` +$ f-acat tip > A # tip version's manifest +$ f-acat prev --raw > B # previous manifest in its raw fossil-deltified form +$ f-acat prev > C # previous manifest fossil-undelta'd +$ ls -la A B C +-rw-rw-r-- 1 user user 80252 Mar 12 07:09 A # tip +-rw-rw-r-- 1 user user 726 Mar 12 07:09 B # previous: delta'd +-rw-rw-r-- 1 user user 80256 Mar 12 07:09 C # previous: undelta'd +``` + +For comparison's sake, when looking at a separate repository which +uses delta manifests, a delta-compressed delta manifest takes up +approximately the same space as a delta-compressed baseline manifest +(to within 10 bytes for the test samples). + +i.e. delta manifests may not save any storage space except for the tip +version! (*Surprise!*) + +In terms of RAM costs, deltas usually cost more memory than baseline +manifests. The reason is because traversing a delta requires having +not only that delta in memory, but also its baseline version. Delta +manifests are seldom used in ways which do not require also loading +their baselines. Thus Fossil internally requires two manifest objects +for most operations with a delta manifest, whereas a baseline has but +one. The difference in RAM cost is directly proportional to the size +of the delta manifest. + +## Manifests as Proof of Code Integrity + +Delta manifests have at least one more notable caveat, this one +arguably more significant than an apparent lack of space savings: +they're useless for purposes of publishing a manifest which downstream +clients can use to verify the integrity of their copy of the software. + +Consider this use case: [the SQLite project](https://sqlite.org) +publishes source code to many thousands of downstream consumers, many +of whom would like to be able to verify that the copy they have +downloaded is actually the copy published by the project. This is +easily achieved by providing a copy of the downloaded version's +manifest, as it contains a hash of every single file the project +published and the manifest itself has a well-known hash and is +cryptographically tamper-proof. It's mathematically extremely improbable for a +malicious party to modify such a manifest and re-publish it as an +"official" one, as the various hashes (F-cards, R-card, Z-card, *and* +the hash of the manifest itself) would not line up. A collision-based +attack would have to defeat *all four of those hashes*, which is +practically impossible to do. Thus a Fossil checkin manifest can be used +to provide strong assurances that a given copy of the software has not +been tampered with since being exported by Fossil. + +*However*, that use case is *only possible with baseline manifests*. +A delta manifest is *essentially useless* for that purpose. The +algorithm for traversing F-cards of a delta manifest is not trivial +for arbitrary clients to reproduce, e.g. using a shell script. While +it *could* be done in any higher-level programming language (or some +truly unsightly shell code), it would be an onerous burden on +downstream consumers and would not be without risks of having bugs +which invalidate the strong guarantees provided by the manifest. + +It's worth noting that the core Fossil project repository does not use +delta manifests, at least in part for the same reason the SQLite +project does not: the ability to provide a manifest which clients can +easily use to verify the integrity of the code they've downloaded. The +[`forbid-delta-manifests` config +setting](/help/forbid-delta-manifests) is used to ensure that none are +introduced into the repository beyond the few which were introduced +solely for testing purposes. + |