Designing Conflict-Free Identifiers for Offline Capture

Everything about offline sync depends on identity, and identity has to be minted where the observation happens — which rules out every scheme that needs a server to agree. This page is a focused companion to offline field collection and sync reconciliation.

Concept & Context

An identifier in a field workflow is not only a database key. It is written in a field book, spoken over a radio, photographed on a whiteboard beside the feature, and referenced in a sketch. When a sync process renumbers it, all of those links break at once, and the breakage is discovered weeks later when someone tries to match a photograph to a parcel.

That constraint — the identifier the crew recorded must be the identifier the feature keeps — is what disqualifies the obvious approach. A database sequence cannot be consulted from a valley with no signal, and any scheme that mints a temporary identifier for later replacement is a renumbering scheme with extra steps.

Four schemes come up in practice. Two of them fail offline, and the failure is silent in both cases.

Core Algorithmic Pipeline

1. Eliminate coordinated schemes. A database sequence and a central allocator both require connectivity at capture time.
2. Decide on human readability. If crews quote identifiers aloud, a 36-character UUID is a real ergonomic cost; if only machines read them, it is free.
3. Add the new column beside the existing key, populate it for the whole layer, and index it.
4. Migrate consumers one at a time — joins, exports, published services — while both keys work.
5. Demote the legacy key to a non-authoritative column rather than dropping it, so external references keep resolving.

The four candidate schemes:

Working Implementation

"""Mint, validate and migrate offline-safe feature identifiers."""
from __future__ import annotations

import os
import re
import secrets
import time

# Crockford base32: no I, L, O or U, so 1/I and 0/O cannot be misread or misheard.
ALPHABET = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
ID_RE = re.compile(r"^[A-Z]{2,8}-[0-9A-HJKMNP-TV-Z]{16}$")


def _encode(value: int, length: int) -> str:
    out = []
    for _ in range(length):
        out.append(ALPHABET[value & 31])
        value >>= 5
    return "".join(reversed(out))


def mint(crew_prefix: str, when_ms: int | None = None) -> str:
    """Crew-prefixed ULID: 48-bit millisecond timestamp + 32 bits of randomness.

    Sortable by creation time, safe to mint on a disconnected device, and short
    enough to read over a radio without mistakes.
    """
    if not re.fullmatch(r"[A-Z]{2,8}", crew_prefix):
        raise ValueError(f"crew prefix {crew_prefix!r} must be 2-8 uppercase letters")

    ms = when_ms if when_ms is not None else int(time.time() * 1000)
    stamp = _encode(ms, 10)                     # 50 bits of capacity, 48 used
    entropy = _encode(secrets.randbits(30), 6)
    return f"{crew_prefix}-{stamp}{entropy}"


def is_valid(identifier: str) -> bool:
    return bool(ID_RE.fullmatch(identifier))


def minted_at_ms(identifier: str) -> int:
    """Recover the creation timestamp — useful for ordering an operation log."""
    body = identifier.split("-", 1)[1][:10]
    value = 0
    for ch in body:
        value = (value << 5) | ALPHABET.index(ch)
    return value

Migrating a layer that already uses integers is a schema change plus a backfill, and it is deliberately additive:

-- 1. Add beside the existing key; nothing breaks yet.
ALTER TABLE parcels ADD COLUMN parcel_uid text;

-- 2. Backfill deterministically, so a repeated migration is a no-op.
UPDATE parcels
   SET parcel_uid = 'LEGACY-' || upper(substr(md5('parcel:' || gid::text), 1, 16))
 WHERE parcel_uid IS NULL;

-- 3. Constrain only once the backfill is complete and verified.
ALTER TABLE parcels
  ALTER COLUMN parcel_uid SET NOT NULL,
  ADD CONSTRAINT parcels_uid_unique UNIQUE (parcel_uid),
  ADD CONSTRAINT parcels_uid_shape CHECK (parcel_uid ~ '^[A-Z]{2,8}-[0-9A-HJKMNP-TV-Z]{16}$');

CREATE INDEX parcels_uid_idx ON parcels (parcel_uid);

-- 4. Keep gid as a non-authoritative legacy reference, documented as such.
COMMENT ON COLUMN parcels.gid IS
  'Legacy sequence key. Non-authoritative: retained so external references resolve. '
  'Joins and exports use parcel_uid.';

Deriving the backfill from a hash of the existing key rather than from random bytes means the migration can be re-run — on a copy, on a replica, on a restored backup — and produce identical identifiers every time. A random backfill makes the migration a one-shot event that cannot be reproduced if anything goes wrong halfway.

Validation & Output Verification

-- Every feature has a well-formed, unique identifier
SELECT count(*) FILTER (WHERE parcel_uid IS NULL)                    AS missing,
       count(*) - count(DISTINCT parcel_uid)                         AS duplicated,
       count(*) FILTER (WHERE parcel_uid !~ '^[A-Z]{2,8}-[0-9A-HJKMNP-TV-Z]{16}$')
                                                                     AS malformed
  FROM parcels;
-- expected: 0, 0, 0

# Minting is collision-free at field rates, and sortable by capture time
from identifiers import mint, minted_at_ms, is_valid

ids = [mint("EAST") for _ in range(200_000)]
assert len(set(ids)) == len(ids), "collision at field capture volume"
assert all(is_valid(i) for i in ids)

# Two devices minting concurrently must not collide either
a = {mint("EAST") for _ in range(50_000)}
b = {mint("WEST") for _ in range(50_000)}
assert not (a & b)

# Ordering by identifier orders by capture time
sample = sorted(ids[:1000])
stamps = [minted_at_ms(i) for i in sample]
assert stamps == sorted(stamps)
print("identifiers unique, well-formed and time-ordered")

Run the SQL check on a schedule, not only at migration. A collision that appears months later means a device is minting with a prefix it was not assigned, and that is worth knowing before the affected package is reconciled.

Failure Modes

• Two features arrive with one identifier — symptom: a unique-constraint violation during sync, or worse, a silent overwrite. Root cause: sequential or block-allocated integers minted on disconnected devices. Fix: move to device-minted identifiers; quarantine affected packages rather than renumbering.

• A re-imaged device reuses a block — symptom: collisions confined to one crew. Root cause: block allocation held only on the device. Fix: record allocations centrally, or abandon blocks for prefixed ULIDs.

• Crews transcribe identifiers wrongly — symptom: field notes that do not match any feature. Root cause: an alphabet containing visually ambiguous characters. Fix: use Crockford base32 as above, which omits I, L, O and U.

• The migration cannot be re-run — symptom: a half-finished backfill leaves the layer in a state nobody can reproduce. Root cause: randomly generated backfill values. Fix: derive backfill identifiers deterministically from the legacy key.

Related

• Offline Field Collection and Sync Reconciliation — the parent guide and the sync protocol these identifiers make possible
• Reconciling Offline Edits from Field Collection Apps — where the prefix validation runs
• Hashing Spatial Datasets for Reproducible Fingerprints — the fingerprint that refuses to run without a stable key
• Best Practices for Branching GeoPackage Projects — why the same key requirement appears in branch-level diffs

Back to Offline Field Collection and Sync Reconciliation