view release on metacpan or  search on metacpan

src/subversion/subversion/libsvn_fs_base/notes/structure  view on Meta::CPAN

Subversion on Berkeley DB                                    -*- text -*-

There are many different ways to implement the Subversion filesystem
interface.  You could implement it directly using ordinary POSIX
filesystem operations; you could build it using an SQL server as a
back end; you could build it on RCS; and so on.

This implementation of the Subversion filesystem interface is built on
top of Berkeley DB (http://www.sleepycat.com).  Berkeley DB supports
transactions and recoverability, making it well-suited for Subversion.



Nodes and Node Revisions

In a Subversion filesystem, a `node' corresponds roughly to an
`inode' in a Unix filesystem:

   * A node is either a file or a directory.

   * A node's contents change over time.

   * When you change a node's contents, it's still the same node; it's
     just been changed.  So a node's identity isn't bound to a specific
     set of contents.

   * If you rename a node, it's still the same node, just under a
     different name.  So a node's identity isn't bound to a particular
     filename.

A `node revision' refers to a node's contents at a specific point in
time.  Changing a node's contents always creates a new revision of that
node.  Once created, a node revision's contents never change.

When we create a node, its initial contents are the initial revision of
the node.  As users make changes to the node over time, we create new
revisions of that same node.  When a user commits a change that deletes
a file from the filesystem, we don't delete the node, or any revision
of it --- those stick around to allow us to recreate prior revisions of
the filesystem.  Instead, we just remove the reference to the node
from the directory.



ID's

Within the database, we refer to nodes and node revisions using a
string of three unique identifiers (the "node ID", the "copy ID", and
the "txn ID"), separated by periods.

    node_revision_id ::= node_id '.' copy_id '.' txn_id

The node ID is unique to a particular node in the filesystem across
all of revision history.  That is, two node revisions who share
revision history (perhaps because they are different revisions of the
same node, or because one is a copy of the other, e.g.) have the same
node ID, whereas two node revisions who have no common revision
history will not have the same node ID.

The copy ID is a key into the `copies' table (see `Copies' below), and
identifies that a given node revision, or one of its ancestors,
resulted from a unique filesystem copy operation.

The txn ID is just an identifier that is unique to a single filesystem
commit.  All node revisions created as part of a commit share this txn
ID (which, incidentally, gets its name from the fact that this id is
the same id used as the primary key of Subversion transactions; see
`Transactions' below).

A directory entry identifies the file or subdirectory it refers to
using a node revision ID --- not a node ID.  This means that a change
to a file far down in a directory hierarchy requires the parent
directory of the changed node to be updated, to hold the new node
revision ID.  Now, since that parent directory has changed, its parent
needs to be updated, and so on to the root.  We call this process
"bubble-up".

src/subversion/subversion/libsvn_fs_base/notes/structure  view on Meta::CPAN

   (KIND TXN [MD5 [SHA1]])

The KIND is "fulltext" or "delta".  TXN is the txn ID for the txn in
which this representation was created.  MD5 is a checksum of the
representation's contents, that is, what the representation produces,
regardless of whether it is stored deltified or as fulltext.  (For
compatibility with older versions of Subversion, MD5 may be
absent, in which case the filesystem behaves as though the checksum is
there and is correct.) An additional kind of checksum, SHA1, is present
in newer formats, starting with version ...
### TODO

The TXN also serves as a kind of mutability flag: if txn T tries to
change a representation's contents, but the rep's TXN is not T, then
something has gone horribly wrong and T should leave the rep alone
(and probably error).  Of course, "change a representation" here means
changing what the rep's consumer sees.  Switching a representation's
storage strategy, for example from fulltext to deltified, wouldn't
count as a change, since that wouldn't affect what the rep produces.

KIND-SPECIFIC varies considerably depending on the kind of
representation.  Here are the two forms currently recognized:

   (("fulltext" TXN [MD5 [SHA1]]) STRING-KEY)
       The data is at STRING-KEY in the `strings' table.

   (("delta" TXN [MD5 [SHA1]]) (OFFSET WINDOW) ...)
       Each OFFSET indicates the point in the fulltext that this
       element reconstructs, and WINDOW says how to reconstruct it:

       WINDOW ::= (DIFF SIZE REP-KEY [REP-OFFSET]) ;
       DIFF   ::= ("svndiff" VERSION STRING-KEY)

       Notice that a WINDOW holds only metadata.  REP-KEY says what
       the window should be applied against, or none if this is a
       self-compressed delta; SIZE says how much data this window
       reconstructs; VERSION says what version of the svndiff format
       is being used (currently only version 0 is supported); and
       STRING-KEY says which string contains the actual svndiff data
       (there is no diff data held directly in the representations
       table, of course).

       Note also that REP-KEY might refer to a representation that
       itself requires undeltification.  We use a delta combiner to
       combine all the deltas needed to reproduce the fulltext from
       some stored plaintext.

       Branko says this is what REP-OFFSET is for:
       > The offsets embedded in the svndiff are stored in a string;
       > these offsets would be in the representation. The point is that
       > you get all the information you need to select the appropriate
       > windows from the rep skel -- without touching a single
       > string. This means a bit more space used in the repository, but
       > lots less memory used on the server.

       We'll see if it turns out to be necessary.

In the future, there may be other representations, for example
indicating that the text is stored elsewhere in the database, or
perhaps in an ordinary Unix file.

Let's work through an example node revision:

   (("file" REV COUNT) PROP-KEY "2345")

The entry for key "2345" in `representations' is:

   (("delta" TXN CHECKSUM) (0 (("svndiff" 0 "1729") 65 "2343")))

and the entry for key "2343" in `representations' is:

   (("fulltext" TXN CHECKSUM) "1001")

while the entry for key "1729" in `strings' is:

   <some unprintable glob of svndiff data>

which, when applied to the fulltext at key "1001" in strings, results
in this new fulltext:

   "((some text) (that looks) (deceptively like) (directory entries))"

Et voila!  Subversion knew enough, via the `representations' and
`strings' tables, to undeltify and get that fulltext; and knew enough,
because of the node revision's "file" type, to interpret the result as
file contents, not as a directory entry list.

(Note that the `strings' table stores multiple DB values per key.
That is, although it's accurate to say there is one string per key,
the string may be divided into multiple consecutive blocks, all
sharing that key.  You use a Berkeley DB cursor to find the desired
value[s], when retrieving a particular offset+len in a string.)

Representations know nothing about ancestry -- the `representations'
table never refers to node revision id's, only to strings or to other
representations.  In other words, while the `nodes' table allows
recovery of ancestry information, the `representations' and `strings'
tables together handle deltification and undeltification
*independently* of ancestry.  At present, Subversion generally stores
the youngest strings in "fulltext" form, and older strings as "delta"s
against them (unless the delta would save no space compared to the
fulltext).  However, there's nothing magic about that particular
arrangement.  Other interesting alternatives:

   * We could store the N most recently accessed strings as fulltexts,
     letting access patterns determine the most appropriate
     representation for each revision.

   * We could occasionally store deltas against the N'th younger
     revision, storing larger jumps with a frequency inverse to the
     distance covered, yielding a tree-structured history.

Since the filesystem interface doesn't expose these details, we can
change the representation pretty much as we please to optimize
whatever parameter we care about --- storage size, speed, robustness,
etc.

Representations never share strings - every string is referred to by
exactly one representation.  This is so that when we change a
representation to a different form (e.g. during deltification), we can