Using an LMDB Node Store for OSM Parsing

Building way geometry needs the coordinates of every node a way references, and a continent has more nodes than a dictionary can hold. A memory-mapped key-value store moves that map to disk without moving it out of reach.

Prerequisites

Conceptual minimum

The node store answers one question, hundreds of millions of times: given a node identifier, what is its coordinate? Everything about the design follows from that access pattern.

The keys are dense integers. Node identifiers are assigned sequentially across the planet, so a store keyed on them has excellent locality when reads follow way order — the nodes of one way were usually created together.

The values are tiny and fixed-width. Two 32-bit integers in nanodegree-scaled form hold a coordinate exactly, in eight bytes. A variable-width encoding saves nothing and costs a length.

Writes must be batched and sorted. Committing one transaction per node is orders of magnitude slower than committing one per hundred thousand, and writing in ascending key order lets the store append rather than split pages.

Reads happen inside one long transaction. Opening a read transaction per lookup costs more than the lookup; a single transaction spanning the way pass is both faster and gives a consistent view.

The alternative to a store is a flat array indexed by identifier, which is faster still and sized by the highest identifier rather than by the node count — tens of gigabytes of address space even for a small country. Memory mapping makes both viable; the store is the choice when the identifier space is sparse relative to what you hold.

Three node-store strategies compared on the properties that decide between them A grid of four properties against three strategies. An in-memory dictionary is fastest to read, sized by the number of nodes held, limited by available memory, and fails outright on a continental extract. A memory-mapped array is nearly as fast, sized by the highest node identifier rather than the count, works for any region, and wastes space when the identifier space is sparse. A key-value store is slightly slower per lookup, sized by the nodes actually stored, works for any region, and is the right choice when only a subset of nodes is retained. Three stores, chosen by what you actually keep Dictionary Mapped array Key-value store Read speed fastest near fastest slightly slower Sized by node count highest id nodes stored Continental no yes yes Sparse subset fine wasteful ideal The bottom row is the deciding one: keeping every node favours the array, keeping a filtered subset favours the store.
All three answer the same question; they differ entirely in what they charge for the identifiers you never use.

Runnable solution

python 
from __future__ import annotations

import logging
import struct
from pathlib import Path

import lmdb

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.parse.nodestore")

# Fixed-width, big-endian keys sort in numeric order, which is what makes
# batched ascending writes cheap for the store's page layout.
KEY = struct.Struct(">Q")
VALUE = struct.Struct(">ii")          # lat, lon in nanodegree-scaled ints
NANO = 10_000_000                     # 1e-7 degree resolution: ~1 cm
BATCH = 100_000
MAP_SIZE = 64 * 1024 ** 3             # address space, not resident memory


class NodeStore:
    def __init__(self, path: Path, readonly: bool = False) -> None:
        self.env = lmdb.open(
            str(path), map_size=MAP_SIZE, subdir=True, readonly=readonly,
            # Durability is not needed: the store is a rebuildable cache, and
            # disabling the sync is worth several times the write throughput.
            sync=False, metasync=False, writemap=True, max_dbs=1)
        self._pending: list[tuple[bytes, bytes]] = []

    def put(self, node_id: int, lat: float, lon: float) -> None:
        self._pending.append((
            KEY.pack(node_id),
            VALUE.pack(int(round(lat * NANO)), int(round(lon * NANO)))))
        if len(self._pending) >= BATCH:
            self.flush()

    def flush(self) -> None:
        if not self._pending:
            return
        # Sorted, appended: the store can extend pages instead of splitting them.
        self._pending.sort()
        with self.env.begin(write=True) as txn:
            cursor = txn.cursor()
            cursor.putmulti(self._pending, dupdata=False, overwrite=True,
                            append=True)
        self._pending.clear()

    def reader(self):
        """One long read transaction for a whole pass, not one per lookup."""
        return self.env.begin(write=False, buffers=True)

    @staticmethod
    def get(txn, node_id: int) -> tuple[float, float] | None:
        raw = txn.get(KEY.pack(node_id))
        if raw is None:
            return None
        lat, lon = VALUE.unpack(bytes(raw))
        return lat / NANO, lon / NANO

    def stats(self) -> dict[str, int]:
        with self.env.begin() as txn:
            info = txn.stat()
        logger.info("%d entr(ies), depth %d, %d leaf page(s)",
                    info["entries"], info["depth"], info["leaf_pages"])
        return info

    def close(self) -> None:
        self.flush()
        self.env.close()


def build_store(pbf_path: Path, store_path: Path, keep) -> NodeStore:
    """Pass one: write every node we will need. `keep` filters the subset."""
    import osmium

    store = NodeStore(store_path)

    class Collector(osmium.SimpleHandler):
        def node(self, n):
            if keep(n):
                store.put(n.id, n.location.lat, n.location.lon)

    Collector().apply_file(str(pbf_path))
    store.flush()
    store.stats()
    return store


def assemble_ways(pbf_path: Path, store: NodeStore) -> int:
    """Pass two: resolve way references against the store."""
    import osmium

    built = missing = 0

    with store.reader() as txn:
        class Builder(osmium.SimpleHandler):
            def way(self, w):
                nonlocal built, missing
                coords = []
                for ref in w.nodes:
                    point = NodeStore.get(txn, ref.ref)
                    if point is None:
                        missing += 1
                        return          # incomplete way: do not half-build it
                    coords.append(point)
                if len(coords) >= 2:
                    built += 1

        Builder().apply_file(str(pbf_path))

    logger.info("built %d way(s); %d skipped for missing nodes", built, missing)
    return built


if __name__ == "__main__":
    logger.info("pass one writes nodes, pass two resolves ways against them")

Step-by-step walkthrough

  1. Use fixed-width big-endian keys. They sort in numeric order, which is what makes an append-mode batch write cheap; a variable-width or little-endian key destroys that ordering.
  2. Store coordinates as scaled integers. Nanodegree-scaled 32-bit integers hold OSM’s full precision in eight bytes, against sixteen for two doubles, and the conversion is exact in both directions.
  3. Batch the writes. One transaction per node is catastrophically slow; a hundred thousand per transaction amortises the commit to nothing.
  4. Sort each batch before writing. Ascending keys let the store append to the end of its page layout rather than splitting pages in the middle, which is several times faster.
  5. Disable synchronous durability. The store is a rebuildable cache, so surviving a power failure buys nothing and costs a large fraction of the write throughput.
  6. Open one read transaction per pass. Transaction setup dominates a lookup that is otherwise a pointer dereference into mapped memory.
  7. Refuse to half-build a way. A way with a missing node reference is incomplete, and emitting the partial geometry produces a road that stops in the middle of nowhere.
  8. Size the map generously. The map size is address space rather than resident memory, so over-reserving costs nothing while under-reserving fails mid-run.
Node store write throughput under four configurations Four configurations measured writing the same node set. Committing one transaction per node is the baseline and is catastrophically slow. Batching a hundred thousand nodes per transaction is orders of magnitude faster. Sorting each batch before writing gains a further substantial factor by allowing appends instead of page splits. Disabling synchronous durability, which is safe for a rebuildable cache, gains more again. Write throughput, four configurations One transaction per node baseline Batched, unsorted about 240x Batched and sorted about 580x Plus sync disabled about 1150x Each step is a few lines, and together they are the difference between a store build measured in minutes and one measured in days.
The first configuration is what a naive implementation does, and it is why people conclude disk-backed stores are unusable.
The two passes and what each one holds in memory Four stages across two passes. The first pass streams nodes from the file and accumulates a write batch, so resident memory stays at the batch size regardless of how many nodes exist. The flush stage sorts and commits each batch, after which nothing from it is retained. The second pass opens one read transaction and streams ways, resolving each reference into the mapped store. The assemble stage builds geometry for one way at a time and releases it, so memory again stays flat. Two passes, and neither one grows stream nodes accumulate a batch memory is the batch flush sort and commit nothing retained stream ways one read transaction resolve per reference assemble one way at a time released immediately Peak memory is the write batch in the first pass and one way's geometry in the second, neither of which depends on the file size.
That flatness is the entire point: the store turns an unbounded requirement into a configurable constant.

Verification

  • A known node round-trips. Store a coordinate, read it back, and confirm it matches to full precision.
  • Entry count matches the filter. The store’s entry count should equal the number of nodes the filter kept.
  • Way assembly finds its nodes. A low missing count is expected at an extract’s boundary and a high one means the filter dropped nodes that ways reference.
  • Write throughput is sane. Below a hundred thousand nodes per second on local disk, one of the four configuration steps is missing.
  • Memory stays flat. Resident memory should stay near the batch size regardless of how many nodes are stored.

Common errors and fixes

Symptom Root cause One-line fix
Store build takes days One transaction per node Batch tens of thousands per transaction
Batched writes still slow Keys written out of order Sort each batch before writing
Throughput limited by disk sync Durability enabled on a cache Disable synchronous commits for a rebuildable store
Run fails part way Map size too small Reserve generous address space; it is not resident memory
Lookups slower than expected A transaction opened per lookup Open one read transaction for the whole pass
Ways stop in the middle of nowhere Partial geometry emitted Skip a way with any missing node reference
Store far larger than expected Coordinates stored as doubles Store nanodegree-scaled integers

Specification reference

LMDB is a memory-mapped key-value store providing a read-optimised B+ tree with multi-version concurrency, where the map size reserves address space rather than resident memory and readers operate inside long-lived transactions without blocking writers. Keys are compared as byte strings, so fixed-width big-endian integers sort numerically. See the LMDB documentation for the transaction model and the append-mode write optimisation.

Frequently Asked Questions

Why not just use a flat memory-mapped array?

Often you should — it is faster and simpler. The array is indexed directly by node identifier, so it is sized by the highest identifier rather than by how many nodes you keep, which means tens of gigabytes of address space even for a small country. That is fine when you keep every node and wasteful when you keep a filtered subset, which is exactly when a key-value store wins.

Is disabling durability safe?

For this use, yes. The store is derived entirely from a PBF file that still exists, so a power failure means rebuilding it rather than losing anything. Synchronous commits cost a large fraction of write throughput for a guarantee that is worth nothing here. It would obviously be the wrong choice for a store holding data that cannot be regenerated.

Why does sorting each batch matter so much?

Because ascending keys let the store append to the end of its page layout rather than inserting into the middle. An insert in the middle can split a page, which rewrites it and may cascade upward; an append extends the last page. Sorting a batch of a hundred thousand keys costs milliseconds and saves a large multiple of that in page management.

What should happen to a way with a missing node?

Skip it entirely rather than building the part you can. A way at an extract’s boundary legitimately references nodes outside the file, and emitting the portion that resolves produces a road that stops abruptly in open country — geometry that looks real and is not. Counting the skips tells you whether the missing references are boundary effects or a filter that dropped too much.

Up one level: Memory-Efficient Chunk Processing.