Making Tile Output Deterministic

This page makes a tiling pipeline produce byte-identical output from identical inputs — pinning tool versions, sorting every input collection, removing embedded timestamps and hostnames, controlling floating-point rounding and thread non-determinism, and proving it with a double build that compares hashes, for a city tiled from EPSG:25832 into EPSG:4978.

Why you hit this

Determinism sounds like a purity concern and is the foundation of three practical things. Incremental builds rely on it: if re-tiling an unchanged shard produces different bytes, the content hash changes, the CDN cache is invalidated and “incremental” means rebuilding the city. Caching relies on it, because an immutable URL whose content varies is a lie. And debugging relies on it — a difference between two builds is either a real change or noise, and a pipeline with noise cannot tell you which. The incremental machinery that depends on this is in incremental retiling of changed city blocks.

Prerequisites

• Python 3.10+ with numpy>=1.24; the tiling pipeline itself and whatever encoders it calls.
• A container image for the build, or at least a lock file pinning every dependency.
• A shard whose inputs you can hold fixed, for the double-build test.

Step-by-Step

1. Find the sources of non-determinism

import hashlib
import json
import os
import subprocess
from pathlib import Path

def file_digest(path, chunk=1 << 20):
    h = hashlib.sha256()
    with open(path, "rb") as f:
        while block := f.read(chunk):
            h.update(block)
    return h.hexdigest()

def tree_digests(root):
    return {str(p.relative_to(root)): file_digest(p)
            for p in sorted(Path(root).rglob("*")) if p.is_file()}

def diff_digests(a, b):
    keys = sorted(set(a) | set(b))
    return [{"path": k, "a": a.get(k, "missing")[:12], "b": b.get(k, "missing")[:12]}
            for k in keys if a.get(k) != b.get(k)]

first = tree_digests("build/run_a/shards/120210233010")
second = tree_digests("build/run_b/shards/120210233010")
differences = diff_digests(first, second)
print(f"{len(differences)} of {len(first)} files differ between two builds of the same shard")
for d in differences[:6]:
    print(f"  {d['path']:<32}{d['a']}  {d['b']}")

Running the same shard twice and diffing the hashes is the whole diagnostic. Almost every pipeline fails it the first time, and the files that differ point straight at the cause: a tileset.json that differs means a timestamp or a key order, a .glb that differs means the encoder or the geometry order, and a difference in every file means a tool version or a path baked into the output.

2. Sort every input, by a key that cannot change

def stable_feature_order(features):
    """Deterministic order: by identifier, which is stable across runs and deliveries."""
    return sorted(features, key=lambda f: (str(f["feature_id"]),))

def stable_shard_order(shard_keys):
    return sorted(shard_keys)                         # quadkeys sort lexicographically

def stable_file_list(root, pattern="*.laz"):
    return sorted(Path(root).glob(pattern), key=lambda p: p.name)

Filesystem iteration order is not defined — Path.glob and os.listdir return entries in whatever order the filesystem provides, which differs between ext4 and XFS, between a local disk and object storage, and sometimes between two runs on the same directory. Sorting by name is one call and removes the whole class of problem.

Sorting features by identifier rather than by position matters for a subtler reason: a spatial sort is stable only if the coordinates are identical, and a delivery that shifts one building by a millimetre reorders everything after it. An identifier sort survives that, so a shard whose contents did not change produces the same vertex order even when a neighbour moved.

3. Remove the timestamps and the environment

def deterministic_tileset(root_tile, dataset_version, geometric_error):
    """No build time, no hostname, no absolute paths — only inputs."""
    return {
        "asset": {
            "version": "1.1",
            "tilesetVersion": dataset_version,          # the data's version, not the build's time
        },
        "geometricError": round(geometric_error, 6),
        "root": root_tile,
    }

def write_json_deterministic(path, obj):
    text = json.dumps(obj, sort_keys=True, separators=(",", ":"), ensure_ascii=True,
                      allow_nan=False)
    Path(path).write_text(text, encoding="utf-8", newline="\n")
    return file_digest(path)

def deterministic_zip(out_path, files):
    """A zip with fixed timestamps and order, for packaged outputs."""
    import zipfile
    with zipfile.ZipFile(out_path, "w", compression=zipfile.ZIP_DEFLATED) as z:
        for arcname, src in sorted(files.items()):
            info = zipfile.ZipInfo(arcname, date_time=(1980, 1, 1, 0, 0, 0))
            info.compress_type = zipfile.ZIP_DEFLATED
            info.external_attr = 0o644 << 16
            z.writestr(info, Path(src).read_bytes())
    return file_digest(out_path)

sort_keys=True fixes JSON key order, which in CPython is insertion order and therefore depends on the code path that built the dictionary. allow_nan=False turns a NaN — which would serialise as the non-standard NaN token — into an error, which is better than a tileset that some parsers reject.

The version string is the substantive change: replacing a build timestamp with the data’s version means two builds of the same data produce the same file, while a new delivery still changes it. Where a build time is genuinely needed, the standard approach is to honour SOURCE_DATE_EPOCH from the environment so a rebuild can reproduce an earlier one.

4. Control the arithmetic

import numpy as np

def deterministic_bounds(points):
    """Min/max are exact; means and sums need a fixed reduction order."""
    lo = points.min(axis=0)
    hi = points.max(axis=0)
    centre = (lo + hi) / 2.0                        # from extremes, not from a mean
    half = (hi - lo) / 2.0
    return np.round(centre, 6), np.round(half, 6)

def deterministic_mean(values):
    """Pairwise summation in a fixed order, independent of thread count."""
    v = np.sort(np.asarray(values, dtype=np.float64))   # sorting makes the order reproducible
    return float(v.sum() / len(v)) if len(v) else 0.0

def quantise(values, scale=1e-3):
    """Round to a fixed grid so tiny input differences cannot flip a rounding decision."""
    return np.round(np.asarray(values, dtype=np.float64) / scale).astype(np.int64) * scale

Floating-point addition is not associative, so a sum computed by four threads and a sum computed by one differ in the last bits, and a bounding volume derived from a mean differs between runs on machines with different core counts. Deriving the centre from the extremes avoids the reduction entirely. Where a mean is genuinely needed, sorting before summing makes the order reproducible at a small cost.

Quantising before writing is the other half. Two runs that compute a coordinate as 12.000000000000002 and 11.999999999999998 write different bytes unless the value is snapped to a grid first — and the grid is the tile’s quantisation step anyway, so nothing is lost.

def set_deterministic_env():
    """Environment variables that remove thread and hash non-determinism."""
    os.environ.setdefault("PYTHONHASHSEED", "0")
    for var in ("OMP_NUM_THREADS", "OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS",
                "NUMEXPR_NUM_THREADS", "GDAL_NUM_THREADS"):
        os.environ.setdefault(var, "1")
    os.environ.setdefault("SOURCE_DATE_EPOCH", "1758067200")
    return {k: os.environ[k] for k in ("PYTHONHASHSEED", "OMP_NUM_THREADS", "SOURCE_DATE_EPOCH")}

print(set_deterministic_env())

PYTHONHASHSEED matters because set iteration order depends on it, and a pipeline that iterates a set of feature identifiers anywhere produces a different order on every run. Setting the thread counts to one is a blunt instrument that guarantees reproducible reductions; the alternative is to keep threads and make every reduction order-independent, which is more work and faster.

5. Record what produced the output

def provenance(params, tool_versions, inputs):
    """Everything that affects the bytes, hashed into one value."""
    payload = {
        "params": params,
        "tools": tool_versions,
        "inputs": {name: file_digest(path) for name, path in sorted(inputs.items())},
    }
    canonical = json.dumps(payload, sort_keys=True, separators=(",", ":"))
    return {"provenance": payload,
            "provenance_hash": hashlib.sha256(canonical.encode()).hexdigest()}

TOOLS = {
    "python": subprocess.run(["python", "-VV"], capture_output=True, text=True).stdout.strip(),
    "tiler": "twin-tiler 4.2.1",
    "draco": "1.5.6",
    "gltf-transform": "4.0.1",
    "image": "ghcr.io/example/twin-tiler@sha256:3f0a…",
}
prov = provenance({"max_per_tile": 2000, "quantize_position": 14},
                  TOOLS, {"footprints": "source/footprints.gpkg"})
print(prov["provenance_hash"][:16], "…")

The provenance hash is what makes determinism useful rather than merely satisfying. Two tiles with the same provenance hash and different content hashes mean the pipeline is non-deterministic; the same content hash with a different provenance hash means something irrelevant changed. Storing it per shard turns the incremental build’s “is this shard up to date?” into a comparison of two strings.

6. Prove it with a double build in CI

def double_build_check(build_fn, shard, work_root="build/determinism"):
    digests = []
    for run in ("a", "b"):
        out = Path(work_root) / run
        if out.exists():
            import shutil
            shutil.rmtree(out)
        out.mkdir(parents=True)
        build_fn(shard, out)                        # the real pipeline, twice
        digests.append(tree_digests(out))
    diffs = diff_digests(*digests)
    return {"files": len(digests[0]), "differing": len(diffs), "deterministic": not diffs,
            "first_differences": diffs[:5]}

result = double_build_check(build_shard_to, "120210233010")
print(json.dumps(result, indent=2))
assert result["deterministic"], "tiling is not deterministic; see first_differences"

Running the check on one representative shard in CI, on every merge, is enough: non-determinism is almost never shard-specific, and one shard takes seconds. Adding a second shard with textures is worthwhile, because image encoders are a common source — several JPEG and Basis encoders embed a library version or vary with thread count.

Expected Output & Verification

3 of 5 files differ between two builds of the same shard
  tileset.json                    a41f0c2b9e14  7d2e88b41c03
  content/0/0/0.glb               9b02c4e7f1aa  1c8e4470a9d2
  content/0/0/1.glb               44a1e0b9c83f  2fe70c1ab884
{'PYTHONHASHSEED': '0', 'OMP_NUM_THREADS': '1', 'SOURCE_DATE_EPOCH': '1758067200'}
c41d9f8a2b703e55 …
{
  "files": 5,
  "differing": 0,
  "deterministic": true,
  "first_differences": []
}

The first block is the before state and the last is the after. Three of five files differed: tileset.json from a build timestamp, and the two .glb files from unsorted feature iteration — which is the typical pair, and both are fixed by the changes above.

Verify that determinism survives the things that legitimately vary, which is the property that makes it useful:

def determinism_matrix(build_fn, shard):
    """Same inputs must give the same bytes across worker counts and working directories."""
    import shutil
    cases = {
        "baseline": {"workers": 1, "cwd": "build/case_a"},
        "more_workers": {"workers": 8, "cwd": "build/case_b"},
        "other_cwd": {"workers": 1, "cwd": "build/case_c/nested/deeper"},
    }
    digests = {}
    for name, cfg in cases.items():
        out = Path(cfg["cwd"]) / "out"
        if out.exists():
            shutil.rmtree(out)
        out.mkdir(parents=True)
        build_fn(shard, out, workers=cfg["workers"])
        digests[name] = tree_digests(out)
    base = digests["baseline"]
    return {name: {"identical": d == base, "differing": len(diff_digests(base, d))}
            for name, d in digests.items()}

print(json.dumps(determinism_matrix(build_shard_to, "120210233010"), indent=2))

Worker count and working directory are the two variables that differ between a developer’s laptop and the build server, so a pipeline that is deterministic only at one worker count will still produce cache-invalidating output in production. Testing the matrix rather than a single repeat is what catches the parallel-reduction and absolute-path cases.

Then verify that a real change does change the bytes, which is the other half of the contract:

def change_detection_check(build_fn, shard, out_root="build/change"):
    base = Path(out_root) / "base"; base.mkdir(parents=True, exist_ok=True)
    build_fn(shard, base)
    moved = Path(out_root) / "moved"; moved.mkdir(parents=True, exist_ok=True)
    build_fn(shard, moved, nudge_one_building_m=0.02)      # 2 cm on one building
    diffs = diff_digests(tree_digests(base), tree_digests(moved))
    return {"differing_files": len(diffs), "detects_change": len(diffs) > 0}

print(change_detection_check(build_shard_to, "120210233010"))

A pipeline so aggressively quantised that a 2 cm move produces identical bytes is deterministic and useless, because the incremental build will never notice the change. The quantisation grid has to be finer than the smallest change the twin must reflect.

Performance Notes

• Determinism costs a few percent, almost all of it in sorting inputs and in single-threaded reductions. On a city job that is minutes against hours, and it is repaid the first time an incremental build skips 4,000 unchanged shards.
• Sorting is cheap; re-sorting is not. Sort once, at the point the collection is formed, and keep the order through the pipeline.
• Single-threaded native libraries are the expensive part. Where a stage is reduction-heavy, prefer an order-independent algorithm over disabling threads.
• Hash with sha256 and be done. Hashing a 1 MB tile takes microseconds, and a faster non-cryptographic hash saves nothing measurable while making collisions a conversation.
• Run the double-build check on one shard, not the city. It is a property of the code, not of the data.

Common Errors

Only the tileset JSON differs. A timestamp, a hostname or a key order. The three fixes in step 3 cover all of them.

Only the compressed geometry differs. The encoder is non-deterministic, or its version changed. Pin the encoder in the image and check whether it has a deterministic flag; several accept a fixed random seed.

Output differs between the laptop and CI but not between two CI runs. An absolute path, a locale, or a different library build. The pinned image removes all three, which is why the double build must run in the same image the pipeline uses.

Everything is identical and the incremental build still rebuilds everything. The provenance hash includes something that changes per run — a build timestamp, a run identifier, an absolute path. It should contain only inputs, parameters and tool versions.

A textured tile is deterministic on one machine and not another. Image encoders vary with SIMD availability. Either pin the encoder’s instruction-set level or accept per-machine variation and always build on one class of runner.

Frequently Asked Questions

Is bit-for-bit determinism necessary, or is “semantically equal” enough?

For caching and incremental builds it must be bit-for-bit, because the comparison is a hash. For validation, semantic equality is enough — and a pipeline that can only manage the second cannot have immutable URLs.

What about SOURCE_DATE_EPOCH?

It is the reproducible-builds convention for injecting a fixed timestamp, and honouring it is the right way to keep a build time in the output without losing determinism. Any format with a mandatory timestamp field — zip archives, some image containers — should read it.

Does quantisation hide real changes?

It can, which is why the change-detection check exists. Choose the grid from the smallest change the twin must reflect — a centimetre for building geometry — and verify that a change at that scale alters the bytes.

Related Guides

• Incremental Retiling of Changed City Blocks — what determinism makes possible
• Resuming Failed Tiling Runs from Checkpoints — the manifest that records the hashes
• Versioning Tilesets with Immutable Prefixes — the caching contract this underwrites

Back to 3D Tiles Batch Tiling Pipelines.