initial commitHEADmaster

1 files changed, 407 insertions, 0 deletions

diff --git a/www/fossil-is-not-relational.md b/www/fossil-is-not-relational.md
new file mode 100644
index 0000000..ba2671a
--- /dev/null
+++ b/www/fossil-is-not-relational.md
@@ -0,0 +1,407 @@
+# Fossil is not Relational
+
+***An Introduction to the Fossil Data Model***
+
+Upon hearing that Fossil is based on sqlite, it's natural for people
+unfamiliar with its internals to assume that Fossil stores its
+SCM-relevant data in a database-friendly way and that the SCM history
+can be modified via SQL. The truth, however, is *far stranger than
+that.*
+
+This document introduces, at a relatively high level:
+
+1) The underlying enduring and immutable data format, which is
+  independent of any specific storage engine.
+
+2) The `blob` table: Fossil's single point of SCM-relevant data
+  storage.
+
+3) The transformation of (1) from its immutable raw form to a
+  *transient* database-friendly form.
+
+4) Some of the consequences of this model.
+
+
+# Part 1: Artifacts
+
+```pikchr center
+AllObjects: [
+A: file "Artifacts" fill lightskyblue;
+down; move to A.s; move 50%;
+F: file "Client" "files";
+right; move 1; up; move 50%;
+B: cylinder "blob table"
+right;
+arrow from A.e to B.w;
+arrow from F.e to B.w;
+arrow dashed from B.e;
+C: box rad 0.1 "Crosslink" "process";
+arrow
+AUX: cylinder "Auxiliary" "tables"
+arc -> cw dotted from AUX.s to B.s;
+] # end of AllObjects
+```
+
+
+The centerpiece of Fossil's architecture is a data format which
+describes what we call "artifacts." Each artifact represents the state
+of one atomic unit of SCM-relevant data, such as a single checkin, a
+single wiki page edit, a single modification to a ticket, creation or
+cancellation of tags, and similar SCM constructs. In the cases of
+checkins and ticket updates, an artifact may record changes to
+multiple files resp. ticket fields, but the change as a whole
+is atomic. Though we often refer to both fossil-specific SCM data
+and client-side content as artifacts, this document uses the term
+artifact solely for the former purpose.
+
+From [the data format's main documentation][dataformat]:
+
+> The global state of a fossil repository is kept simple so that it
+> can endure in useful form for decades or centuries. A fossil
+> repository is intended to be readable, searchable, and extensible by
+> people not yet born.
+
+[dataformat]: ./fileformat.wiki
+
+This format has the following major properties:
+
+- It is <u>**syntactically simple**</u>, easily and efficiently
+  parsable in any programming language. It is also entirely
+  human-readable.
+
+- It is <u>**immutable**</u>. An artifact is identified by its unique
+  hash value. Any modification to an artifact changes that hash,
+  thereby changing its identity.
+
+- It is <u>**not generic**</u>. It is custom-made for its purpose and
+  makes no attempt at providing a generic format. It contains *only*
+  what it *needs* to function, with zero bloat.
+
+- It <u>**holds all SCM-relevant data except for client-level file
+  content**</u>, the latter instead being referenced by their unique
+  hash values. Storage of the client-side content is an implementation
+  detail delegated to higher-level applications.
+ 
+- <u>**Auditability**</u>. By following the hash references in
+  artifacts it is possible to unambiguously trace the origin of any
+  modification to the SCM state. Combined with higher-level tools
+  (specifically, Fossil's database), this audit trail can easily be
+  traced both backwards and forwards in time, using any given version
+  in the SCM history as a starting point.
+
+Notably, the artifact file format <u>does not</u>...
+
+- Specify any specific storage mechanism for the SCM's raw bytes,
+  which includes both artifacts themselves and client-side file
+  content. The file format refers to all such content solely by its
+  unique hash value.
+
+- Specify any optimizations such as storing file-level changes as
+  deltas between two versions of that content.
+
+Such aspects are all considered to be implementation details of
+higher-level applications (be they in the main fossil binary or a
+hypothetical 3rd-party application), and have no effect on the
+underlying artifact data model. That said, in Fossil:
+
+- All raw byte content (artifacts and client files) is stored in
+  the `blob` database table.
+
+- Fossil uses delta and zlib compression to keep the storage size of
+  changes from one version of a piece of content to the next to a
+  minimum.
+
+
+## Sidebar: SCM-relevant vs Non-SCM-relevant State
+
+Certain data in Fossil are "SCM-relevant" and certain data are not. In
+short, SCM-relevant data are managed in a way consistent with
+controlled versioning of that data. Conversely, non-SCM-relevant data
+are essentially any state neither specified by nor unambiguously
+refererenced by the artifact file format and are therefore not
+versioned.
+
+SCM-relevant state includes:
+
+- Any and all data stored in the bodies of artifacts. This includes,
+  but is not limited to: wiki/ticket/forum content, tags, file names
+  and Fossil-side permissions, the name of each user who introduces
+  any given artifact into the data store, the timestamp of each such
+  change, the inheritance tree of checkins, and many other pieces of
+  metadata.
+
+- Raw file content of versioned files. These data are external to
+  artifacts, which refer to them by their hashes. How they are stored
+  is not the concern of the data model, but (spoiler alert!) Fossil
+  stores them in an SQLite database, one record per distinct hash, in
+  its `blob` table (which we will cover more very soon).
+
+Non-SCM-relevant state includes:
+
+- Fossil's list of users and their metadata (permissions, email
+  address, etc.). Artifacts themselves reference users only by their
+  user names. Artifacts neither care whether, nor guarantee that, user
+  "drh" in one artifact is in fact the same "drh" referenced in
+  another artifact.
+
+- All Fossil UI configuration, e.g. the site's skin, config settings,
+  and project name.
+
+- In short, any tables in a Fossil repository file except for the
+  `blob` table. Most, but not all, of these tables are transient
+  caches for the data specified by the artifact files (which are
+  stored in the `blob` table), and can safely be destroyed and rebuilt
+  from the collection of artifacts with no loss of state to the
+  repository. *All* of them, except for `blob` and `delta`, can be
+  destroyed with no loss of *SCM-relevant* data.
+
+## Terminology Hair-splitting: Manifest vs. Artifact
+
+We sometimes refer to artifacts as "manifests," which is technically a
+term for artifacts which record checkins. The various other artifact
+types are arguably not "manifests," but are sometimes referred to as
+such because the internal APIs use that term.
+
+
+## A Very Basic Example
+
+The following artifact, truncated for brevity, represents a typical
+checkin artifact (a.k.a. a manifest):
+
+```
+C Bug\sfix\sin\sthe\slocal\sdatabase\sfinder.
+D 2007-07-30T13:01:08
+F src/VERSION 24bbb3aad63325ff33c56d777007d7cd63dc19ea
+F src/add.c 1a5dfcdbfd24c65fa04da865b2e21486d075e154
+F src/blob.c 8ec1e279a6cd0cfd5f1e3f8a39f2e9a1682e0113
+<SNIP>
+F www/selfcheck.html 849df9860df602dc2c55163d658c6b138213122f
+P 01e7596a984e2cd2bc12abc0a741415b902cbeea
+R 74a0432d81b956bfc3ff5a1a2bb46eb5
+U drh
+Z c9dcc06ecead312b1c310711cb360bc3
+```
+
+Each line is a single data record called a "card." The first letter of
+each line tells us the type of data stored on that line and the
+following space-separated tokens contain the data for that
+line. Tokens which themselves contain spaces (notably the checkin
+comment) have those escaped as `\s`. The raw text of wiki
+pages/comments, forum posts, and ticket bodies/comments is stored
+directly in the corresponding artifact, but is stored in a way which
+makes such escaping unnecessary.
+
+The hashes seen above are a critical component of the architecture:
+
+- The `F` (file) records refer to the content of those files by the
+hash of that content. Where that content is stored is *not* specified
+by the data model.
+
+- The `P` (parent) line is the hash code of the parent version (itself
+  an artifact).
+
+- The `Z` line is a hash of all of the content of *this artifact*
+  which precedes the `Z` line. Thus any change to the content of an
+  artifact changes both the artifact's identity (its hash) and its `Z`
+  value, making it impossible to inject modified artifacts into an
+  existing artifact tree.
+
+- The `R` line is yet another consistency-checking hash which we won't
+  go into here except to say that it's an internal consistency
+  check/line of defense against modification of file content
+  referenced by the artifact.
+
+# Part 2: The `blob` Table
+
+```pikchr center
+AllObjects: [
+A: file "Artifacts";
+down; move to A.s; move 50%;
+F: file "Client" "files" fill lightskyblue;
+right; move 1; up; move 50%;
+B: cylinder "blob table" fill lightskyblue;
+right;
+arrow from A.e to B.w;
+arrow from F.e to B.w;
+arrow dashed from B.e;
+C: box rad 0.1 "Crosslink" "process";
+arrow
+AUX: cylinder "Auxiliary" "tables"
+arc -> cw dotted from AUX.s to B.s;
+] # end of AllObjects
+```
+
+
+The `blob` table is the core-most storage of a Fossil repository
+database, storing all SCM-relevant data (and *only* SCM-relevant
+data). Each row of this table holds a single artifact or the content
+for a single version of a single client-side file. Slightly truncated
+for clarity, its schema contains the following fields:
+
+- **`uuid`**: the hash code of the blob's contents.
+- **`rid`**: a unique integer key for this record. This is how the
+  blob table is mapped to other (transient) tables, but the RIDs are
+  specific to one given copy of a repository and must not be used for
+  cross-repository referencing. The RID is a private/internal value of
+  no use to a user unless they're building SQL queries for use with
+  the Fossil db schema.
+- **`size`**: the size, in bytes, of the blob's contents, or -1 for
+  "phantom" blobs (those which Fossil knows should exist because it's
+  seen them referenced somewhere, but for which it has not been given
+  any content).
+- **`content`**: the blob's raw content bytes, with the caveat that
+  Fossil is free to store it in an "alternate representation."
+  Specifically, the `content` field often holds a zlib-compressed
+  delta from a previous version of the blob's content (a separate
+  entry in the `blob` table), and an auxiliary table named `delta`
+  maps such blobs to their previous versions, such that Fossil can
+  reconstruct the real content from them by applying the delta to its
+  previous version (and such deltas may be chained). Thus extraction
+  of the content from this field cannot be performed via vanilla SQL,
+  and requires a Fossil-specific function which knows how to convert
+  any internal representations of the content to its original form.
+
+
+## Sidebar: How does `blob` Distinguish Between Artifacts and Client Content?
+
+Notice that the `blob` table has no flag saying "this record is an
+artifact" or "this record is client data." Similarly, there is no
+place in the database dedicated to keeping track of which `blob`
+records are artifacts and which are file content.
+
+That said, (A) the type of a blob can be implied via certain table
+relationships and (B) the `event` table (the `/timeline`'s main data
+source) incidentally has a list of artifacts and their sub-types
+(checkin, wiki, tag, etc.). However, given that all of those
+relationships, including the timeline, are *transient*, how can Fossil
+distinguish between the two types of data?
+
+Fossil's artifact format is extremely rigid and is *strictly* enforced
+internally, with very near zero room provided for leniency (barring a
+small handful of historical compatibility cases). Every artifact which
+is internally created is re-parsed for validity before it is committed
+to the database, making it impossible that Fossil can inject an
+invalid artifact into the repository. Because of the strictness of the
+artifact parser, the chances that any given piece of arbitrary client
+data could be successfully parsed as an artifact, even if it is
+syntactically 99% similar to an artifact, are *effectively zero*.
+
+Thus Fossil's rule of interpreting the contents of the blob table is:
+if it can be parsed as an artifact, it *is* an artifact, else it is
+opaque client-side data.
+
+That rule is most often relevant in operations like `rebuild` and
+`reconstruct`, both of which necessarily have to sort out artifacts
+and non-artifact blobs from arbitrary collections of blobs.
+
+It is, in fact, possible to store an artifact unrelated to the current
+repository in that repository, and it *will be parsed and processed as
+an artifact* (see below), but it likely refers to other artifacts or
+blobs which are not part of the current repository, thereby possibly
+introducing "strange" data into the UI. If this happens, it's
+potentially slightly confusing but is functionally harmless.
+
+
+# Part 3: Crosslinking
+
+```pikchr center
+AllObjects: [
+A: file "Artifacts";
+down; move to A.s; move 50%;
+F: file "Client" "files";
+right; move 1; up; move 50%;
+B: cylinder "blob table"
+right;
+arrow from A.e to B.w;
+arrow from F.e to B.w;
+arrow dashed from B.e;
+C: box rad 0.1 "Crosslink" "process" fill lightskyblue;
+arrow
+AUX: cylinder "Auxiliary" "tables" fill lightskyblue;
+arc -> cw dotted from AUX.s to B.s;
+] # end of AllObjects
+```
+
+Once an artifact is stored in the `blob` table, how does one perform
+SQL queries against its plain-text format? In short: *One Does Not
+Simply Query the Artifacts*.
+
+Crosslinking, as its colloquially known, is a one-way processing step
+which transforms an immutable artifact's state into something
+database-friendly. Crosslinking happens automatically every time
+Fossil generates, or is given, a new artifact. Crosslinking of any
+given artifact may update many different auxiliary tables, *all* of
+which are transient in the sense that they may be destroyed and then
+recreated by crosslinking all artifacts from the `blob` table (which
+is exactly what the `rebuild` command does). The overwhelming majority
+of individual database records in any Fossil repository are found in
+these transient auxiliary tables, though the `blob` table tends to
+account for the overwhelming majority of a repository's disk space.
+
+This approach to mapping data from artifacts to the db gives Fossil
+the freedom to change its database model, effectively at will, with
+minimal client-side disruption (at most, a call to `rebuild`). This
+allows, for example, Fossil to take advantage of new improvements in
+sqlite without affecting compatibility with older repositories.
+
+Auxiliary tables hold data mappings such as:
+
+- Child/parent relationships of checkins. (The `plink` table.)
+- Records of file names and changes to files. (The `mlink` and `filename` tables.)
+- Timeline entries. (The `event` table.)
+
+And numerous other bits and pieces.
+
+The many auxiliary tables maintained by the app-level code reference
+the `blob` table via its RID field, as that's far more efficient than
+using hashes (`blob.uuid`) as foreign keys. The contexts of those
+auxiliary data unambiguously tell us whether the referenced blobs are
+artifacts or file content, so there is no efficiency penalty there for
+hosting both opaque blobs and artifacts in the `blob` table.
+
+The complete SQL schemas for the core-most auxiliary tables can be found
+at:
+
+[](/finfo/src/schema.c?ci=trunk)
+
+Noting, however, that all database tables are effectively internal
+APIs, with no API stability guarantees and subject to change at any
+time. Thus their structures generally should not be relied upon in
+client-side scripts.
+
+
+# Part 4: Implications and Consequences of the Model
+
+*Some* of the implications and consequences of Fossil's data model
+combined with the higher-level access via SQL include:
+
+- **Provable immutability of history.** Fossil offers only one option
+  for modifying history: "shunning" is the forceful removal of an
+  artifact from the `blob` table and the creation of a db record
+  stating that the shunned hash may no longer be synced into this
+  repository. Shunning effectively leaves a hole in the SCM history,
+  and is only intended to be used for removal of illegal, dangerous,
+  or private information which should never have been added to the
+  repository.
+
+- **Complete separation of SCM-relevant data and app-level data
+  structures**. This allows the application to update its structures
+  at will without significant backwards-compatibility concerns. In
+  Fossil's case, "data structures" primarily refers to the SQL
+  schema. Bringing a given repository schema up to date vis a vis a
+  given fossil binary version simply means rebuilding the repository
+  with that fossil binary. There are exceptionally rare cases, namely
+  the switch from SHA1 to SHA3-256 ushered in with Fossil 2.0, which
+  can lead to true incompatibility. e.g. a Fossil 1.x client cannot
+  use a repository database which contains SHA3 hashes, regardless of
+  a rebuild.
+
+- **Two-way compatibility with other hypothetical clients** which also
+  implement the same underlying data model. So far there are none, but
+  it's conceivably possible.
+
+- **Provides a solid basis for reporting.** Fossil's real-time metrics
+  and reporting options are arguably the most powerful and flexible
+  yet seen in an SCM.
+
+- Very probably several more things.