18.2 Explicit-Join Repository Graph

February 2008

This chapter preserves the first of two repository-graph designs developed in February 2008. It uses explicit root, check-in and join nodes. The following Check-in-Only Repository Graph replaces this representation with a graph containing only check-in nodes.

Site identifiers and vector times

Each site is uniquely identified by a site identifier. Let S be the set of site identifiers and let ℕ be the set of non-negative integers. A vector time is a map v : S → ℕ.

The operations ↑ and ↓ are idempotent, commutative and associative. Each distributes over the other. The empty vector time is the least element; ↓ produces a lower bound and ↑ produces an upper bound. The relation ≤ is reflexive, antisymmetric and transitive. These definitions and properties are developed in Vector Time.

Identification of operations

Every operation is generated at exactly one site. Each site independently assigns a zero-based sequence number t to each operation it generates.

Introduction

The repository graph records all operations that have ever been checked into the repository.

There are three node types:

An empty repository contains only its root node. A vector time shown beside a node records the number of operations from each site applied to reach that node. The root has v = (0,0,0). A check-in node stores only c = (s,t); its vector time can be calculated while traversing the graph.

A join node is created only when a subsequent check-in supplies a base vector time that does not correspond to an existing node. The repository need not establish that the site previously merged the branches, because that merge could have occurred through another repository. A join node is completely characterised by its input nodes.

Overall vector time

The graph records an overall vector time v_r(G) whose extent contains every check-in. In the example, v_r(G) = (4,2,1). There need not be a graph node corresponding to this vector time. Checking in c = (s,t) advances v_r(s) to t+1.

Validation and scalability

The graph validates causality in check-ins and can validate the two vector times supplied to GetDiff. This allows the repository to reject malformed external requests.

Storing every check-in is practical when a project has only a few thousand check-ins per year.

Representation

class ReposNode
{
public:
    vector<ReposNode*> outNodes;
};

class ReposRootNode : public ReposNode {};

class ReposCheckInNode : public ReposNode
{
    ReposNode* inNode;
    SiteId s;
    int t;
};

class ReposJoinNode : public ReposNode
{
    vector<ReposNode*> inNodes;
};

class ReposGraph
{
    ReposRootNode* rootNode;
    VectorTime vr;
};

Growing the graph for a check-in

A check-in supplies c = (s,t) and a base vector time v. Starting at R, traverse a check-in node iff its (s,t) belongs to χ(v), and always traverse a join node. A visited set prevents processing a node more than once.

If none of a visited node's out-nodes continues the traversal, that node is a branch tip. If there is one branch tip, append the new check-in to it. If there are several, create a join whose in-nodes are those tips and append the check-in to the join.

ReposNode* FindContextNode(VectorTime v)
{
    TraverseGraphToFindBranchNodes(rootNode, v);
    if (failed || NumCheckinsVisited() != v.GetCount()) return nullptr;

    if (branchNodes.size() == 1) return branchNodes[0];

    ReposJoinNode* join = NewJoinNode();
    for (ReposNode* branch : branchNodes) join->AddInNode(branch);
    return join;
}

Causality violation

Suppose the example graph receives a check-in with v = (4,0,0). It must be rejected: the fourth operation from s₁ follows a join involving two operations from s₂, although those operations are absent from χ(v).

The original paper notes that this definition requires more careful treatment when an input or output is itself a join node. The implementation resolves this operationally: a join recursively tests all its in-nodes and recursively tests whether any out-node is in the extent.

Validating a check-in

The checks are performed in the following order:

Validation algorithms

A brute-force validation counts the visited check-in nodes and compares that count with the sum of the components of v. This proves that no node in χ(v) was missed, but checking causality also requires establishing that every predecessor of a visited node was visited.

A proposed faster validation shrinks a copy of v as nodes are visited, leaving the empty vector time at completion. Causality fails if a path starts and ends inside χ(v) but leaves it in between. With in-nodes recorded, this can be detected locally by finding a node in χ(v) with an in-node outside χ(v).

The paper also proposes an independent test model: store the vector time supplied with every check-in and use those stored contexts to validate v. This idea becomes the reference model tested in the following check-in-only design.

Linear-chain optimisation

Long linear branches can contain hundreds of check-ins. The paper proposes replacing individual nodes along such branches with a chain and strictly alternating check-in chains with joins:

class CheckInChainNode : public ReposNode
{
    ReposNode* inNode;
    list<CheckIn> checkIns;
};

A check-in chain has one in-node and any number of out-nodes; a join can have any number of both.

Tests

The deterministic tests create two concurrent check-ins and then check in an operation whose context contains both branches. They require exactly one explicit join and verify the numbers of join and check-in nodes. They then submit the causally invalid vector time from the paper and require its rejection, and separately test duplicate and missing operations.

The randomized test performs 10,000 simulations. Each simulation has three sites and 30 check-ins. A site either continues from its local vector time or updates to the complete repository vector time. Every generated context is valid, so every check-in must succeed. This exercises linear histories, concurrent branches, updates and repeated joins.

All deterministic cases and all 10,000 simulations pass.

Browse the test files.