18.3 Check-in-Only Repository Graph

February 2008

Introduction

This chapter assumes the definitions of vector time, sites S and op(s,t) from Vector Time. It revises the Explicit-Join Repository Graph by eliminating the artificial root and join nodes. Every node in the revised graph represents one check-in.

A repository graph is a directed acyclic graph that records all operations ever checked into a repository.

Repository graph containing only check-in nodes

Each node corresponds to the check-in of one operation and is uniquely identified by (s,t). Let node(s,t) denote the node for op(s,t). For a node n, α(n) is its set of direct in-nodes and β(n) is its set of direct out-nodes.

The vector time shown beside a node records the number of operations from each site that have been applied on reaching the node, including the node itself. The implementation stores (s,t), but does not store this vector time; traversal algorithms derive the required extent from their supplied vector time.

Overall vector time, validation and scalability

The graph records an overall vector time vr whose extent is every check-in in the repository. In the example vr = (4,2,1), although no node need correspond to it. Checking in op(s,t) advances vr(s) to t+1.

The graph validates causality in check-ins and the vector times passed to GetDiff, so the repository can reject malformed external requests. Storing all check-ins is practical for the anticipated rate of a few thousand per year.

Roots and representation

Definition:
roots(G) = { n ∈ G | α(n) = ∅ }.
struct ReposNode
{
    vector<ReposNode*> inNodes;
    vector<ReposNode*> outNodes;
    SiteId s;
    int t;
};

class ReposGraph
{
    vector<ReposNode*> roots;
    VectorTime vr;
};

The precedes relation

Definition:
For nodes n1 and n2, n1 precedes n2, written n1 → n2, iff there is a path from n1 to n2. A path of length zero is allowed.

The relation is reflexive and transitive, so it is a preorder. Since the graph is acyclic it is also antisymmetric, hence a partial order. The graph records this ordering without transitively redundant edges: if n1 → n2 → n3, it does not store a direct edge from n1 to n3.

Extent of a vector time

Definition:
χ(v) = { node(s,t) | t < v(s) }.
  • χ(v∅) = ∅;
  • χ(v1 ↑ v2) = χ(v1) ∪ χ(v2);
  • χ(v1 ↓ v2) = χ(v1) ∩ χ(v2);
  • v1 ≤ v2 iff χ(v1) ⊆ χ(v2).

Causality violation

Definition:
The valid vector times for graph G are V(G) = { v | v ≤ vr(G) and, for all n1,n2 ∈ G, n2 ∈ χ(v) and n1 → n2 imply n1 ∈ χ(v) }.

Thus χ(v) must be a subset of G that is downward closed under the precedes relation. A vector time v ≤ vr(G) breaks causality iff there are nodes n1 ∉ χ(v) and n2 ∈ χ(v) with n1 → n2.

A precedence path from a node outside the extent to a node inside it
Claim:
If v1,v2 ∈ V(G), then v1 ↓ v2 ∈ V(G).
Proof:

Let v = v1 ↓ v2. Since v ≤ v1 ≤ vr, the extent is a subset of G. If n2 ∈ χ(v) and n1 → n2, then n2 belongs to both χ(v1) and χ(v2). Validity of each operand puts n1 in both extents, hence in their intersection χ(v).

Claim:
If v1,v2 ∈ V(G), then v1 ↑ v2 ∈ V(G).
Proof:

Let v = v1 ↑ v2. Both operands are bounded by vr, so their union is also bounded by it. If n2 ∈ χ(v), it belongs to at least one operand's extent. Validity of that operand places every predecessor n1 in the same extent, and therefore in χ(v).

Claim:
v breaks causality iff there is a node n ∈ χ(v) for which α(n) \ χ(v) ≠ ∅.
Proof:

If an immediate predecessor of n is outside χ(v), the definition of causality violation applies directly. Conversely, suppose a path begins outside χ(v) and ends inside it. Moving along the path, there is a first node inside χ(v); its immediately preceding node is outside χ(v). Thus it is sufficient to inspect direct in-nodes during traversal.

Growing the graph for a check-in

A check-in supplies (s,t) and its base vector time v. Starting from every root in χ(v), traverse only nodes in χ(v), using a visited set to avoid repeated work. At each visited node, require all in-nodes to belong to χ(v).

A visited node n is a maximal element of χ(v) precisely when β(n) ∩ χ(v) = ∅. These maximal nodes become the direct in-nodes of the new check-in. If χ(v) is empty, the new node becomes a root. This stores the transitive reduction needed by the precedes relation.

ReposError ReposGraph::CheckIn(OpId opId, const VectorTime& v)
{
    if (opId.t < vr(opId.s)) return OperationAlreadyPresent;
    if (opId.t > vr(opId.s)) return OperationMissing;
    if (!(v <= vr)) return VectorTimeNotASubset;

    vector<ReposNode*> inNodes;
    if (!FindMaximalNodesInExtent(v, inNodes))
        return VectorTimeViolatesCausality;

    ReposNode* node = NewNode(opId);
    for (ReposNode* in : inNodes) node->AddInNode(in);
    if (inNodes.empty()) roots.push_back(node);
    vr.Add(opId.s, opId.t + 1);
    return Ok;
}

The traversal also compares the number of visited nodes with the sum of v's components. This detects a claimed operation in χ(v) that could not be reached from the roots.

Validating a check-in

Error conditionMeaningResult
v(s) ≠ tThe operation was not generated after all preceding operations from its site.Assertion failure
t < vr(s)The operation is already present.REPOS_OPERATION_ALREADY_PRESENT
t > vr(s)An earlier operation from the site is missing.REPOS_OPERATION_MISSING
¬(v ≤ vr)The repository lacks part of the execution context.REPOS_VECTOR_TIME_NOT_A_SUBSET
∃n ∈ χ(v): α(n) \ χ(v) ≠ ∅The extent is not causally closed.REPOS_VECTOR_TIME_VIOLATES_CAUSALITY

The conditions are not mutually exclusive and are checked in the displayed order.

Fast validation

The paper proposes avoiding the visited set by decrementing a copy of v as its nodes are processed. A successful traversal consumes precisely χ(v), leaving the empty vector time.

Linear-chain optimisation

Since a branch may contain hundreds of sequential check-ins, a later representation can store a whole linear chain in one object and split chains when necessary:

class CheckInChain
{
    vector<CheckInChain*> inNodes;
    vector<CheckInChain*> outNodes;
    vector<OpId> checkIns;
};

Tests

The deterministic tests create two concurrent roots, merge them with a third check-in and verify the direct predecessor edges. A further causal successor must have an edge only from the merged node, not redundant edges from its transitive predecessors. The tests also exercise rejection of a causally invalid vector time, a duplicate operation, a missing operation and an execution context not contained by the repository.

The randomized test compares the graph algorithm with the independent definition-based model suggested by the 2008 implementation. The reference model stores the generation context with every accepted check-in. For a proposed vector time v, it directly checks that the context of every included operation is a subset of v.

There are 10,000 simulations of 2,000 attempted check-ins across three sites. Each attempt uses a random vector time that may be valid, violate causality, claim unavailable operations, repeat an operation or omit the next expected operation. The graph and reference model must return the same result and retain identical repository vector times after every attempt.

All deterministic cases and all 20,000,000 randomized comparisons pass. The number and variety of cases covered by this testing provide very high confidence in the correctness of the algorithms.

Browse the test files.

References

  1. David Barrett-Lennard, Vector Time, February 2008.