Implementing a Version Vector for Spatial Features

Give each writer a stable identifier and a per-feature counter, then compare vectors to classify an incoming edit as newer, older or concurrent — a timestamp orders every pair of edits including ones made independently, so last-write-wins discards work without anybody being told it happened.

This guide sits under Conflict Resolution Strategies, within Idempotency & Spatial Deduplication. It provides the detection half; the geometric resolution half is Merging Overlapping Zone Edits with Shapely.

When to use this pattern

  • More than one service or region can edit the same feature, and they do not coordinate through a single lock.
  • Edits can arrive out of order, either because of retries or because a client was offline — the case covered in Handling Out-of-Order Pings from Intermittent Devices for positions and here for edits.
  • Silently discarding an edit is unacceptable, which for anything a human typed it usually is.

What a timestamp cannot see

Same timestamps, different truths Two scenarios are drawn side by side, and a timestamp cannot tell them apart. In the first, editor A saves a change at twelve oh one, editor B loads that change and refines it, saving at twelve oh three. B's edit is causally after A's: it incorporates A's work, and applying it while discarding A's is exactly right. In the second, both editors load version four at twelve hundred hours. A saves at twelve oh one and B, who never saw A's change, saves at twelve oh three. The timestamps are identical to the first scenario, but B's edit does not incorporate A's — applying B and discarding A destroys A's work with no record that anything was lost. A version vector separates them: in the first case B's vector dominates A's, because B's counter for A's writer identity was advanced by having read A's edit. In the second, neither vector dominates, and the pair is flagged as concurrent so a resolution step can run instead of a clock comparison. sequential — B read A's edit A saves 12:01 {A:5, B:0} B loads, refines 12:03 {A:5, B:1} B's vector dominates A's — B has seen everything A had applying B and discarding A is correct: B's edit already contains A's work last-write-wins gets this case right, by luck concurrent — neither saw the other A saves 12:01 {A:5, B:0} B saves 12:03 {A:4, B:1} both from v4 neither vector dominates — flagged concurrent identical timestamps to the left-hand case, and a completely different meaning last-write-wins destroys A's work, silently The difference is whether B's counter for A was advanced by reading A's edit. That fact is available to the writer and absent from the clock, which is why no amount of clock precision fixes the right-hand case.
Figure 1. Better clocks do not help. The missing information is causal — whether one editor had seen the other's work — and only the writer knows it.

Complete runnable implementation

python 
from dataclasses import dataclass, field
from enum import Enum


class Relation(Enum):
    NEWER = "newer"           # incoming dominates stored — apply it
    OLDER = "older"           # stored dominates incoming — drop it
    EQUAL = "equal"           # the same edit, redelivered
    CONCURRENT = "concurrent" # neither dominates — a real conflict


@dataclass(slots=True)
class VersionVector:
    """One counter per writer that has edited this feature."""
    counters: dict[str, int] = field(default_factory=dict)

    def advance(self, writer: str) -> "VersionVector":
        """Called when `writer` makes an edit having seen everything in self."""
        merged = dict(self.counters)
        merged[writer] = merged.get(writer, 0) + 1
        return VersionVector(merged)

    def merge(self, other: "VersionVector") -> "VersionVector":
        """Pointwise maximum — the knowledge of both, after a resolution."""
        writers = set(self.counters) | set(other.counters)
        return VersionVector({
            w: max(self.counters.get(w, 0), other.counters.get(w, 0))
            for w in writers
        })

    def compare(self, other: "VersionVector") -> Relation:
        """Classify self (incoming) against other (stored).

        Domination is pointwise: self is newer only if it is >= other for
        EVERY writer and > for at least one. If each has a counter the other
        does not dominate, the edits are concurrent — which is the case a
        timestamp comparison cannot represent at all.
        """
        writers = set(self.counters) | set(other.counters)
        self_ahead = any(self.counters.get(w, 0) > other.counters.get(w, 0)
                         for w in writers)
        other_ahead = any(other.counters.get(w, 0) > self.counters.get(w, 0)
                          for w in writers)

        if self_ahead and other_ahead:
            return Relation.CONCURRENT
        if self_ahead:
            return Relation.NEWER
        if other_ahead:
            return Relation.OLDER
        return Relation.EQUAL

    def prune(self, active_writers: set[str]) -> "VersionVector":
        """Drop retired writers so the vector stays bounded.

        Safe only once no in-flight edit can still carry the retired writer's
        counter — in practice, after the topic's retention has passed.
        """
        return VersionVector({w: n for w, n in self.counters.items()
                              if w in active_writers})


@dataclass(slots=True)
class FeatureEdit:
    feature_id: str
    writer: str
    vector: VersionVector
    geometry: dict
    crs: str = "EPSG:4326"


def apply_edit(stored: FeatureEdit | None, incoming: FeatureEdit,
               resolve) -> FeatureEdit:
    """Apply one edit, routing genuine conflicts to `resolve`."""
    if stored is None:
        return incoming

    match incoming.vector.compare(stored.vector):
        case Relation.NEWER:
            return incoming
        case Relation.OLDER | Relation.EQUAL:
            return stored
        case Relation.CONCURRENT:
            # The transport layer must NOT decide this. `resolve` knows about
            # geometry and about what the feature means; the comparison above
            # only knows that a decision is needed.
            merged_geometry = resolve(stored, incoming)
            return FeatureEdit(
                feature_id=stored.feature_id,
                writer=incoming.writer,
                vector=stored.vector.merge(incoming.vector).advance(incoming.writer),
                geometry=merged_geometry,
                crs=stored.crs,
            )

The EQUAL case is what makes this idempotent: a redelivered edit carries exactly the vector already stored, so it is dropped without any comparison of geometry or timestamps.

Four relations, four actions, one of which needs a human decision An incoming edit's vector is compared pointwise against the stored one, producing four possible relations. If the incoming vector is greater than or equal at every writer and strictly greater at one, it is newer and is applied — the writer had seen everything the stored version contained. If the stored vector dominates in the same way, the incoming edit is older, which happens on a delayed redelivery, and it is dropped. If the two vectors are identical the edit is a duplicate of what is already stored, and dropping it is what makes the whole scheme idempotent under at-least-once delivery. If each vector is ahead of the other at some writer, the edits are concurrent: no ordering exists between them, and any rule that picks one is discarding work. Only the fourth case needs a resolution step, and in a well-behaved system it is rare — which is the point, because a rare case that is visible can be given a careful answer, while a rare case that is invisible gets last-write-wins forever. incoming vector compared pointwise against stored NEWER ≥ everywhere, > somewhere the writer had seen everything the stored version contained apply it OLDER stored dominates a delayed redelivery, or an edit overtaken in flight drop it EQUAL identical vectors the same edit arriving twice this case is what makes the scheme idempotent drop it CONCURRENT each ahead somewhere no ordering exists · any rule that picks one discards work resolve, with geometry Only the fourth needs a decision, and in a healthy system it is rare. That is the point: a rare case that is visible gets a careful answer, while a rare case that is invisible gets last-write-wins forever.
Figure 2. Three of the four are mechanical. The value of the scheme is that it isolates the one that is not, instead of resolving it by accident.

Parameter reference

Name Type Spatial constraint Default
Writer identity str The service accepting the edit, not the device making it —
counters dict[str, int] One entry per writer that has ever touched this feature {}
advance call Only after reading the current state — advancing blind fabricates causality —
merge call Pointwise max; used after a resolution to record that both are known —
prune call Safe only after the retention window has passed —
resolve callable Must be geometry-aware; the comparison layer must never decide —

Gotchas and spatial edge cases

  1. Advancing a vector without having read the current state fabricates causality. A writer that increments its counter from a cached copy claims to have seen edits it has not, so a genuine conflict is classified as NEWER and the other edit is discarded — with the vector now asserting that this was correct. Read-then-advance must be atomic, in the same transaction as the write.

  2. Writer identity must be stable across restarts and deploys. A service that generates a fresh identity on boot adds a new entry to every feature it touches, so vectors grow without bound and every edit after a restart looks concurrent with everything before it. Use a configured name, not a hostname or a process identifier.

  3. Per-device writer identity does not scale. Ten thousand mobile editors produce vectors with ten thousand entries on popular features, which is larger than the geometry. Assign identity at the service that accepts the edit; the device identity belongs in the audit trail, not in the vector.

  4. Pruning too early resurrects conflicts. Removing a retired writer’s counter while an edit carrying it is still in the log means that edit, on replay, compares as concurrent with everything. Prune only after the retention window has passed, and treat the prune as a schema change rather than a cleanup.

  5. Concurrency is not the same as overlap. Two concurrent edits to a feature may touch entirely different parts of it — one changing a name and one moving a vertex — and merging those is trivial. Classify by what changed before invoking a geometric merge, or a simple attribute edit ends up resolved by a union of polygons.

  6. A conflict that reaches a merge should be counted. The rate of CONCURRENT outcomes per feature class is the signal that two teams are editing the same data without knowing it, which is an organisational problem the pipeline can detect before anyone reports it.

Who counts as a writer decides how big the vector gets The same feature is edited by field staff over a year, under two definitions of writer identity. With per-device identity every phone, tablet and laptop that ever touched the feature gains an entry, so a popular parcel accumulates hundreds of counters and the vector eventually exceeds the geometry it describes in size — and because devices are replaced, most of those entries belong to hardware that no longer exists and can never advance again. With per-service identity, the four regional services that accept edits are the writers, so the vector holds four entries however many people edit through them; the device that made each edit is recorded in the audit trail, where it belongs, and where its cardinality costs nothing. The comparison semantics are identical in both cases: what changes is only how many counters have to be compared, stored and carried on every event. one parcel, one year of field edits writer = the device {phone-a1:3, tablet-7:1, phone-c9:2, …} hundreds of counters on a popular feature eventually larger than the geometry it describes most entries name hardware that no longer exists writer = the service accepting the edit {edit-svc-north:14, edit-svc-south:9, …} four entries, however many people edit the device goes in the audit trail, where it belongs and where its cardinality costs nothing The comparison semantics are identical. What changes is how many counters must be compared, stored, and carried on every event.
Figure 3. Writer identity is the one design choice here that cannot be revisited cheaply, because changing it invalidates every vector already stored.

Verification

python 
import pytest

SQUARE = {"type": "Polygon", "coordinates": [[[0, 0], [0, 1], [1, 1], [1, 0], [0, 0]]]}


def vec(**counters) -> VersionVector:
    return VersionVector(dict(counters))


def test_sequential_edit_is_newer():
    """B read A's edit, so B's vector dominates."""
    assert vec(A=5, B=1).compare(vec(A=5, B=0)) is Relation.NEWER


def test_concurrent_edits_are_detected():
    """Both branched from A=4; neither saw the other."""
    assert vec(A=5, B=0).compare(vec(A=4, B=1)) is Relation.CONCURRENT


def test_redelivery_is_equal_and_dropped():
    """The property that makes at-least-once delivery safe."""
    stored = FeatureEdit("f-1", "A", vec(A=5), SQUARE)
    incoming = FeatureEdit("f-1", "A", vec(A=5), SQUARE)
    assert apply_edit(stored, incoming, resolve=_never) is stored


def test_resolution_records_both_lineages():
    """After a merge, the vector must dominate BOTH inputs."""
    stored = FeatureEdit("f-1", "A", vec(A=5, B=0), SQUARE)
    incoming = FeatureEdit("f-1", "B", vec(A=4, B=1), SQUARE)
    result = apply_edit(stored, incoming, resolve=lambda a, b: a.geometry)

    assert result.vector.compare(stored.vector) is Relation.NEWER
    assert result.vector.compare(incoming.vector) is Relation.NEWER


def _never(a, b):
    raise AssertionError("resolve must not be called for non-concurrent edits")

The last test is the one that catches an incomplete resolution. Merging the geometries but forgetting to merge the vectors leaves the result concurrent with one of its own inputs, so the same conflict is rediscovered on every subsequent edit and the merge runs forever.