Server
******

The term ``server'' is ambiguous, because it has at least two different meanings: it can refer to a powerful computer which offers services to users on a network, or it can refer to a CPU process designed to receive network requests.

In Subversion, however, the server is just a set of libraries that implements repositories and makes them available to other programs.  No networking is required.

There are two main libraries: the Subversion Filesystem library, and the Subversion Server library.

Filesystem
==========

Filesystem Overview
-------------------

  * Requires:

       * some writable disk space

  * Provides:

       * a repository for storing files

       * support for multiple concurrent accesses (via a lock manager)

       * enforcement of user & group permissions (via ACLs)

This library implements a hierarchical filesystem which supports atomic changes to directory trees, and records a complete history of the changes.  In addition to recording changes to file and directory contents, the Subversion Filesystem records changes to file meta-data (see discussion of properties in Model).

API
---

This is almost the same API that the client calls, but now prefixed with fs_.  For a full explanation, see The repository access library.

The only differences are the lack of the status() and update() routines.  Instead of receiving and returning entire skeltas or deltas, the filesystem provides the ability to inquire about only one node at a time via fs_cmp() and fs_get_delta().

ver_t fs_latest (repos, user)

prop_t fs_get_ver_prop (repos, user, ver, propname)

proplist_t fs_get_ver_proplist (repos, user, ver)

proplist_t fs_get_ver_propnames (repos, user, ver)

node_t fs_read (repos, user, ver, path)

str_t fs_get_node_prop (repos, user, ver, path, propname)

str_t fs_get_dirent_prop (repos, user, ver, path, propname)

proplist_t fs_get_node_proplist (repos, ver, path)

proplist_t fs_get_dirent_proplist (repos, user, ver, path)

proplist_t fs_get_node_propnames (repos, user, ver, path)

proplist_t fs_get_dirent_propnames (repos, user, ver, path)

diff_t fs_get_diff (repos, user, ver1, path1, ver2, path2)

token_t fs_submit (repos, user, skelta)

ver_t fs_write (repos, user, delta, token)

bool_t fs_abandon (repos, user, token)

bool_t fs_cmp (repos, user, ver1, path1, ver2, path2)
     Compare two nodes in the repository, return whether they are identical.

delta_t fs_get_delta (repos, user, ver1, path1, ver2, path2)
     Compare two nodes in the repository, return the difference between them.

Note that in addition to checking against concurrent commits, fs_submit() also protects against committing changes from out-of-date base versions, that is, the situation where the node in the repository has changed since the base version mentioned in the skelta.

Repository Structure
--------------------

Schema
......

To begin, please be sure that you're already casually familiar with Subversion's ideas of files, directories, and version histories.  If not, see Model.  We can now offer precise, technical descriptions of the terms introduced there.

     A text string is a string of Unicode characters which is canonically decomposed and ordered, according to the rules described in the Unicode standard.

     A string of bytes is what you'd expect.

     A property list is an unordered list of properties.  A property is a pair (NAME, VALUE), where NAME is a text string, and VALUE is a string of bytes. No two properties in a property list have the same name.

     A file is a property list and a string of bytes.

     A node is either a file or a directory.  (We define a directory below.)  Nodes are distinguished unions --- you can always tell whether a node is a file or a directory.

     A node table is an array mapping some set of positive integers, called node numbers, onto nodes.  If a node table maps some number I to some node N, then I is a valid node number in that table, and node I is N.  Otherwise, I is an invalid node number in that table.

     A directory entry is a triple (NAME, PROPS, NODE), where NAME is a text string, PROPS is a property list, and NODE is a node number.

     A directory is an unordered list of directory entries, and a property list.

     A version is a node number and a property list.

     A history is an array of versions, indexed by a contiguous range of non-negative integers containing 0.

     A repository consists of node table and a history.

Now that we've explained the form of the data, we make some restrictions on that form.

Every version has a root directory.  Every version's node number is a valid node number, and the node it refers to is always a directory. We call this the version's root directory.

Version 0 always contains an empty root directory.  This baseline makes it easy to check out whole projects from the repository.

Directories contain only valid links. Every directory entry's NODE is a valid node number.

Directory entries can be identified by name. For any directory D, every directory entry in D has a distinct name.

There are no cycles of directories.  No node is its own child.

Directories can have more than one parent.  The Unix file system does not allow more than one hard link to a directory, but Subversion does allow the analogous situation.  Thus, the directories in a Subversion repository form a directed acyclic graph (DAG), not a tree.  However, it would be distracting and unhelpful to replace the familiar term ``directory tree'' with the unfamiliar term ``directory DAG'', so we still call it a ``directory tree'' here.

There are no dead nodes.  Every node is a child of some version's root directory.

Bubble-Up Method
................

This section provides a conversational explanation of how the repository actually stores and versions file trees.  It's not critical knowledge for a programmer using the Subversion Filesystem API, but most people probably still want to know what's going on ``under the hood'' of the repository.

Suppose we have a new project, at version 1, looking like this (using CVS syntax):

        prompt$ svn checkout myproj
        U myproj/
        U myproj/B
        U myproj/A
        U myproj/A/fish
        U myproj/A/fish/tuna
        prompt$

Only the file tuna is a regular file, everything else in myproj is a directory.

Let's see what this looks like as an abstract data structure in the repository, and how that structure works in various operations (such as update, commit, and branch).

In the diagrams that follow, lines represent parent-to-child connections in a directory hierarchy.  Boxes are "nodes".  A node is either a file or a directory -- a letter in the upper left indicates which kind.  A file node has a byte-string for its content, whereas directory nodes have a list of dir_entries, each pointing to another node.

Parent-child links go both ways (i.e., a child knows who all its parents are), but a node's name is stored only in its parent, because a node with multiple parents may have different names in different parents.

At the top of the repository is an array of version numbers, stretching off to infinity.  Since the project is at version 1, only index 1 points to anything; it points to the root node of version 1 of the project:

                         ( myproj's version array )
            ______________________________________________________
           |___1_______2________3________4________5_________6_____...
               |
               |
            ___|_____
           |D        |
           |         |
           |   A     |      /* Two dir_entries, `A' and `B'. */
           |    \    |
           |   B \   |
           |__/___\__|
             /     \
            |       \
            |        \
         ___|___   ___\____
        |D      | |D       |
        |       | |        |
        |       | | fish   |   /* One dir_entry, `fish'. */
        |_______| |___\____|
                       \
                        \
                      ___\____
                     |D       |
                     |        |
                     | tuna   |  /* One dir_entry, `tuna'. */
                     |___\____|
                          \
                           \
                         ___\____
                        |F       |
                        |        |
                        |        |   /* (Contents of tuna not shown.) */
                        |________|

What happens when we modify tuna and commit?  First, we make a new tuna node, containing the latest text.  The new node is not connected to anything yet, it's just hanging out there in space:

                              ________
                             |F       |
                             |        |
                             |        |
                             |________|

Next, we create a new version of its parent directory:

                      ________
                     |D       |
                     |        |
                     | tuna   |
                     |___\____|
                          \
                           \
                         ___\____
                        |F       |
                        |        |
                        |        |
                        |________|

We continue up the line, creating a new version of the next parent directory:

                   ________
                  |D       |
                  |        |
                  | fish   |
                  |___\____|
                       \
                        \
                      ___\____
                     |D       |
                     |        |
                     | tuna   |
                     |___\____|
                          \
                           \
                         ___\____
                        |F       |
                        |        |
                        |        |
                        |________|

Now it gets more tricky: we need to create a new version of the root directory.  This new root directory needs an entry to point to the ``new'' directory A, but directory B hasn't changed at all.  Therefore, our new root directory also has an entry that still points to the old directory B node!

            ______________________________________________________
           |___1_______2________3________4________5_________6_____...
               |
               |
            ___|_____             ________
           |D        |           |D       |
           |         |           |        |
           |   A     |           |   A    |
           |    \    |           |    \   |
           |   B \   |           |   B \  |
           |__/___\__|           |__/___\_|
             /     \               /     \
            |    ___\_____________/       \
            |   /    \                     \
         ___|__/   ___\____              ___\____
        |D      | |D       |            |D       |
        |       | |        |            |        |
        |       | | fish   |            | fish   |
        |_______| |___\____|            |___\____|
                       \                     \
                        \                     \
                      ___\____              ___\____
                     |D       |            |D       |
                     |        |            |        |
                     | tuna   |            | tuna   |
                     |___\____|            |___\____|
                          \                     \
                           \                     \
                         ___\____              ___\____
                        |F       |            |F       |
                        |        |            |        |
                        |        |            |        |
                        |________|            |________|

Finally, after all our new nodes are written, we finish the ``bubble up'' process by linking this new tree to the next available version in the history array.  In this case, the new tree becomes version 2 in the repository.

            ______________________________________________________
           |___1_______2________3________4________5_________6_____...
               |        \
               |         \__________
            ___|_____             __\_____
           |D        |           |D       |
           |         |           |        |
           |   A     |           |   A    |
           |    \    |           |    \   |
           |   B \   |           |   B \  |
           |__/___\__|           |__/___\_|
             /     \               /     \
            |    ___\_____________/       \
            |   /    \                     \
         ___|__/   ___\____              ___\____
        |D      | |D       |            |D       |
        |       | |        |            |        |
        |       | | fish   |            | fish   |
        |_______| |___\____|            |___\____|
                       \                     \
                        \                     \
                      ___\____              ___\____
                     |D       |            |D       |
                     |        |            |        |
                     | tuna   |            | tuna   |
                     |___\____|            |___\____|
                          \                     \
                           \                     \
                         ___\____              ___\____
                        |F       |            |F       |
                        |        |            |        |
                        |        |            |        |
                        |________|            |________|

Generalizing on this example, you can now see that each ``version'' in the repository history represents a root node of a unique tree (and an atomic commit to the whole filesystem.)  There are many trees in the repository, and many of them share nodes.

Many nice behaviors come from this model:

 1. Easy reads.  If a filesystem reader wants to locate version X of file foo.c, it need only traverse the repository's history, locate version X's root node, then walk down the tree to foo.c.

 2. Writers don't interfere with readers.  Writers can continue to create new nodes, bubbling their way up to the top, and concurrent readers cannot see the work in progress.  The new tree only becomes visible to readers after the writer makes its final ``link'' to the repository's history.

 3. File structure is versioned.  Unlike CVS, the very structure of each tree is being saved from version to version.  File and directory renames, additions, and deletions are part of the repository's history.

Let's demonstrate the last point by renaming the tuna to book.

We start by creating a new parent ``fish'' directory, except that this parent directory has a different dir_entry, one which points the same old file node, but has a different name:

            ______________________________________________________
           |___1_______2________3________4________5_________6_____...
               |        \
               |         \__________
            ___|_____             __\_____
           |D        |           |D       |
           |         |           |        |
           |   A     |           |   A    |
           |    \    |           |    \   |
           |   B \   |           |   B \  |
           |__/___\__|           |__/___\_|
             /     \               /     \
            |    ___\_____________/       \
            |   /    \                     \
         ___|__/   ___\____              ___\____
        |D      | |D       |            |D       |
        |       | |        |            |        |
        |       | | fish   |            | fish   |
        |_______| |___\____|            |___\____|
                       \                     \
                        \                     \
                      ___\____              ___\____      ________
                     |D       |            |D       |    |D       |
                     |        |            |        |    |        |
                     | tuna   |            | tuna   |    | book   |
                     |___\____|            |___\____|    |_/______|
                          \                     \         /
                           \                     \       /
                         ___\____              ___\____ /
                        |F       |            |F       |
                        |        |            |        |
                        |        |            |        |
                        |________|            |________|

From here, we finish with the bubble-up process.  We make new parent directories up to the top, culminating in a new root directory with two dir_entries (one points to the old ``B'' directory node we've had all along, the other to the new version of ``A''), and finally link the new tree to the history as version 3:

            ______________________________________________________
           |___1_______2________3________4________5_________6_____...
               |        \        \_________________
               |         \__________               \
            ___|_____             __\_____        __\_____
           |D        |           |D       |      |D       |
           |         |           |        |      |        |
           |   A     |           |   A    |      |   A    |
           |    \    |           |    \   |      |    \   |
           |   B \   |           |   B \  |      |   B \  |
           |__/___\__|           |__/___\_|      |__/___\_|
             /  ___________________/_____\_________/     \
            |  / ___\_____________/       \               \
            | / /    \                     \               \
         ___|/_/   ___\____              ___\____      _____\__
        |D      | |D       |            |D       |    |D       |
        |       | |        |            |        |    |        |
        |       | | fish   |            | fish   |    | fish   |
        |_______| |___\____|            |___\____|    |___\____|
                       \                     \             \
                        \                     \             \
                      ___\____              ___\____      ___\____
                     |D       |            |D       |    |D       |
                     |        |            |        |    |        |
                     | tuna   |            | tuna   |    | book   |
                     |___\____|            |___\____|    |_/______|
                          \                     \         /
                           \                     \       /
                         ___\____              ___\____ /
                        |F       |            |F       |
                        |        |            |        |
                        |        |            |        |
                        |________|            |________|

For our last example, we'll demonstrate the way ``tags'' and ``branches'' are implemented in the repository.

In a nutshell, they're one and the same thing.  Because nodes are so easily shared, we simply create a new directory entry that points to an existing directory node.  It's an extremely cheap way of copying a tree; we call this new entry a clone.

Let's go back to our original tree, assuming that we're at version 6 to begin with:

            ______________________________________________________
         ...___6_______7________8________9________10_________11_____...
               |
               |
            ___|_____
           |D        |
           |         |
           |   A     |
           |    \    |
           |   B \   |
           |__/___\__|
             /     \
            |       \
            |        \
         ___|___   ___\____
        |D      | |D       |
        |       | |        |
        |       | | fish   |
        |_______| |___\____|
                       \
                        \
                      ___\____
                     |D       |
                     |        |
                     | tuna   |
                     |___\____|
                          \
                           \
                         ___\____
                        |F       |
                        |        |
                        |        |
                        |________|

Let's ``tag'' directory A.  To make the clone, we create a new dir_entry T in our root, pointing to A's node:

            ______________________________________________________
           |___6_______7________8________9________10_________11_____...
               |        \
               |         \
            ___|_____   __\______
           |D        | |D        |
           |         | |         |
           |   A     | |    A    |
           |    \    | |    |    |
           |   B \   | |  B |  T |
           |__/___\__| |_/__|__|_|
             /     \    /   |  |
            |    ___\__/   /  /
            |   /    \    /  /
         ___|__/   ___\__/_ /
        |D      | |D       |
        |       | |        |
        |       | | fish   |
        |_______| |___\____|
                       \
                        \
                      ___\____
                     |D       |
                     |        |
                     | tuna   |
                     |___\____|
                          \
                           \
                         ___\____
                        |F       |
                        |        |
                        |        |
                        |________|

Now we're all set.  In the future, the contents of directories A and B may change quite a lot.  However, assuming we never make any changes to directory T, it will always point to a particular pristine version of directory A.  (We can use ACLs to prevent anyone from writing to directory T.)  Thus, T is a tag.

However, if we do decide to allow commits in directory T, and now our repository tree increments to version 8, then T becomes a branch. Specifically, it's a branch of directory A which ``broke off'' from the main line at version 8.

Diffy Storage
.............

You may have been thinking, ``Gee, this bubble up method seems nice, but it sure wastes a lot of space.  Every commit to the repository creates an entire line of new directory nodes!''

Like many other version control systems, Subversion stores changes as differences.  It doesn't make complete copies of nodes; instead, it stores the latest version as a full text, and previous versions as a succession of reverse diffs (the word "diff" is used loosely here -- for files, it means vdeltas, for directories, it means a format that expresses changes to directories).

Locking
-------

The Subversion Filesystem uses a locking mechanism to handle concurrency issues.  In the Subversion locking scheme, readers never wait for writers, and writers only wait for other writers whose changes conflict with theirs.

Reading
.......

Reading is easy; if a server process wants to execute a read() call into the filesystem, it goes right through.  The design of the versioning filesystem allows a reader to simply skip down the version history, locate the correct "root" node, and then follow the particular tree downwards to the file or directory it wishes to read.  Any number of readers can follow this algorithm without interfering with one another; and because writers don't link to the version history until they're finished writing everything, there's no way for a reader to accidentally stumble upon an unfinished tree.

The Lock Manager
................

Each Subversion filesystem has a process called a lock manager. When a server process wishes to write to the filesystem, it must first contact a lock manager, and submit() a skelta:

                       S              /
                        \            /
                         \          /
                          |        /
                          v       /
            +--------------------|--------------+
            |                    v              |
            |             Approved?             |
            |                |                  |
            |                |                  |
            |                v                  |
            |          Concurrency Pool         |
            |       +--------------------+      |
            |       |     S            S |      |
            |       |  S        S   S    |      |
            |       +--------------------+      |
            +-----------------------------------+

The lock manager contains a pool of "approved but uncompleted changes". After receiving a new skelta from submit(), the lock manager determines if it is safe to apply it at the same time as the other ones in the pool. (This rule is actually quite simple: a set of skeltas may be concurrently written if and only if the order in which they are applied does not matter!)

If the lock manager decides that the requested skelta conflicts, it returns a failure to the server (this usually means the client must do an update).  Else, the lock manager returns a transaction token to the server.  The server then uses this token to execute a write() on the filesystem.

After the write() is completed, the skelta is removed from the lock manager's concurrency pool, and the server closes its connection.

Write Locking
.............

Although it is safe for multiple commits to write their new leaf nodes simultaneously, the next step -- bubbling up the directory hierarchy and linking to the next version number -- must be done one commit at a time. Otherwise, a tree representing a mixture of various commits might appear in the repository.

Therefore, as soon as a commit finishes writing new leaf nodes, it locks the version array, creates the bubble-up hierarchy, links to the next available version number, and only then releases the lock.  Fortunately, the first, non-locking stage (writing data to new leaf nodes) is usually the more time-consuming part of a commit anyway.

Implementation
--------------

For the initial release of Subversion,

  * The filesystem will be implemented as a library on Unix.

  * The lock manager will communicate with other processes via Unix domain sockets.

  * The filesystem's data will probably be stored in a collection of .db files, using the Berkeley Database library. (In the future, of course, contributors are free modify the Subversion filesystem to operate with more powerful SQL database.)  (For more information, see Sleepycat Software (http://www.sleepycat.com).)

Server Library
==============

Server Library Overview
-----------------------

  * Requires:

       * the Subversion Filesystem interface

  * Provides:

       * the ability to interact with any repository on a system

       * the ability to enforce server-side policies

       * the ability to load server-side plug-ins

Multiplexing
------------

The Subversion Server Library (svn_svr), in its simplest sense, acts a basic multiplexer for the repository API calls coming from the Subversion client.  (see The repository access library.)  The Subversion Server Library provides the exact same API as the client repository library, prefixed now by svr_:

ver_t svr_latest (repos, user)

prop_t svr_get_ver_prop (repos, user, ver, propname)

proplist_t svr_get_ver_proplist (repos, user, ver)

proplist_t svr_get_ver_propnames (repos, user, ver)

node_t svr_read (repos, user, ver, path)

str_t svr_get_node_prop (repos, user, ver, path, propname)

str_t svr_get_dirent_prop (repos, user, ver, path, propname)

proplist_t svr_get_node_proplist (repos, ver, path)

proplist_t svr_get_dirent_proplist (repos, user, ver, path)

proplist_t svr_get_node_propnames (repos, user, ver, path)

proplist_t svr_get_dirent_propnames (repos, user, ver, path)

skelta_t svr_get_status (repos, user, skelta)

delta_t svr_get_update (repos, user, skelta)

delta_t svr_get_delta (repos, user, ver1, path1, ver2, path2)

diff_t svr_get_diff (repos, user, ver1, path1, ver2, path2)

token_t svr_submit (repos, user, skelta)

ver_t svr_write (repos, user, delta, token)

bool_t svr_abandon (repos, user, token)

These routines are ``wrappers'' that execute filesystem calls against a particular repository.

Most of the wrappers map directly to filesystem calls, except for the svr_get_status() and svr_get_update() routines. svr_get_status() actually iterates over a skelta structure and makes repeated calls to fs_cmp(), while svr_get_update() makes repeated calls to fs_get_delta(), composing the returned deltas into a single final delta.

Policy Enforcement
------------------

When starting up, svn_svr will read a configuration file svn.conf (much like Apache's httpd.conf) which, among other things, will specify a list of server policies to implement.

Because filesystem calls are ``wrappered'' by svn_svr, it has the opportunity to intercept and interpret them according to policy.

For example, an administrator may wish to take a repository ``off-line'' for backup purposes.  She can specify this in the svn.conf file, and any filesystem calls to that repository are then intercepted and (kindly) rejected by svn_svr.

Plug-Ins
--------

It's important that svn_svr be extensible;  by allowing users to write their own server-side libraries, the server's abilities can potentially grow forever.

We define the term plug-in to refer to a library designed to be loaded into svn_svr's address space.  This term is used intentionally (instead of "module") so as not to be confused with either Apache modules or ``CVS-like'' modules.  Each plug-in potentially implements a new set of server "methods".

The svn.conf file specifies a list of available plug-ins, the new methods they provide, and the real shared-object pathnames on disk. When a client requests a particular method, svn_svr then knows which plug-in to "auto-load".

For ideas on future server-side plug-ins, see Future.