A Bounded LRU Node Cache for OSM Streaming Jump to heading#

Resolve way geometry during a streaming OSM parse while holding at most N node coordinates in RAM, evicting the least-recently-used node_id → (lon, lat) entry each time the cache is full, so a planet-scale pass never lets the location store grow without limit.

Prerequisites Jump to heading#

Verify each item before running the cache below; a wrong assumption about primitive ordering is the usual reason a small cap produces a catastrophic miss rate.

• Python 3.10+ for the dict/tuple type hints and structural syntax used here.
• pyosmium ≥ 3.6 installed (pip install osmium) — the handler callbacks and osm.Node/osm.Way types are assumed.
• A .osm.pbf extract whose primitives are in the canonical nodes-then-ways id order (the default for planet and Geofabrik files).
• Familiarity with the windowing discipline in Memory-Efficient Chunk Processing — this cache is the sibling lever that bounds the location store rather than the record buffer.
• The reference-resolution rule from the Node-Way-Relation Data Model: a way carries only integer node ids, so geometry is a deferred join.
• Optional: sys (standard library) for a rough per-entry footprint estimate during tuning.

Conceptual minimum Jump to heading#

A way in OpenStreetMap stores no coordinates of its own — it is an ordered list of node ids, and turning it into a line or polygon means looking each id up in a table of previously seen node positions. The library-managed stores that pyosmium offers (flex_mem, sparse_file_array, dense_file_array) all solve this by keeping every node’s location addressable; that is exactly what you want for random access, but it also means the store’s size is a function of the extract, not of your RAM budget. When you are willing to trade a controlled miss rate for a hard memory ceiling, a bounded least-recently-used (LRU) cache inverts that relationship: you fix the number of resident coordinates, and the cache evicts whichever id has gone longest without a lookup.

The technique only pays off because of a locality property of the PBF format. Nodes and ways are serialized in ascending id blocks, and a way’s member nodes were typically created together, so their ids cluster — which means that when the parser reaches a way, the coordinates it needs were usually seen a short time ago and are still resident. This is the same block-locality that the PBF File Structure Deep Dive describes for decode framing, reused here as a cache-hit assumption. A Python collections.OrderedDict makes the eviction O(1): move_to_end(key) promotes an entry to the most-recently-used position on every hit, and popitem(last=False) drops the least-recently-used entry from the front the moment the cap is exceeded. The cost you accept is the miss: a node evicted before its way arrives — common for long ways or interleaved editing history — forces you to either skip that way or fall back to a full store, so the cache is a deliberate trade against pyosmium’s own sparse_file_array, which never misses but never bounds itself either.

Runnable solution Jump to heading#

The NodeCache below wraps an OrderedDict and exposes just the two operations a resolver needs: put(node_id, lon, lat) when a node callback fires, and get(node_id) when a way needs a member’s coordinate. Every access reorders the entry, and a full cache evicts before it inserts, so the resident set is capped at maxsize. Hit and miss counters make the locality assumption measurable rather than a matter of faith.

from __future__ import annotations

import logging
from collections import OrderedDict

import osmium

logger = logging.getLogger(__name__)

Coord = tuple[float, float]


class NodeCache:
    """A fixed-capacity LRU cache mapping node id -> (lon, lat).

    Backed by an OrderedDict: a lookup promotes its key to the most-recently
    used end via move_to_end, and an insertion past ``maxsize`` evicts the
    least-recently used key with popitem(last=False). Peak entries never
    exceed ``maxsize``, so the location store's memory is bounded regardless
    of how many nodes the extract contains.
    """

    def __init__(self, maxsize: int = 2_000_000) -> None:
        if maxsize < 1:
            raise ValueError("maxsize must be >= 1")
        self.maxsize = maxsize
        self._store: OrderedDict[int, Coord] = OrderedDict()
        self.hits = 0
        self.misses = 0

    def put(self, node_id: int, lon: float, lat: float) -> None:
        if node_id in self._store:
            self._store.move_to_end(node_id)  # refresh recency
        self._store[node_id] = (lon, lat)
        if len(self._store) > self.maxsize:
            evicted_id, _ = self._store.popitem(last=False)  # drop the LRU entry
            logger.debug("evicted node %d (cache full)", evicted_id)

    def get(self, node_id: int) -> Coord | None:
        coord = self._store.get(node_id)
        if coord is None:
            self.misses += 1
            return None
        self._store.move_to_end(node_id)  # this access is now most-recent
        self.hits += 1
        return coord

    @property
    def hit_rate(self) -> float:
        total = self.hits + self.misses
        return self.hits / total if total else 0.0

    def __len__(self) -> int:
        return len(self._store)


class WayResolver(osmium.SimpleHandler):
    """Resolve way geometry from a bounded node cache in a single pass.

    Nodes populate the cache as they stream past; each way then reads its
    member ids back out. A way whose nodes were already evicted is counted
    as unresolved rather than crashing the stream.
    """

    def __init__(self, maxsize: int = 2_000_000) -> None:
        super().__init__()  # required by the pyosmium C++ binding
        self.cache = NodeCache(maxsize=maxsize)
        self.resolved_ways = 0
        self.unresolved_ways = 0

    def node(self, n: osmium.osm.Node) -> None:
        if n.location.valid():
            self.cache.put(n.id, n.location.lon, n.location.lat)

    def way(self, w: osmium.osm.Way) -> None:
        coords: list[Coord] = []
        for nr in w.nodes:
            coord = self.cache.get(nr.ref)
            if coord is None:
                self.unresolved_ways += 1
                return  # a member was evicted; skip this way
            coords.append(coord)
        self.resolved_ways += 1
        # coords now holds the way geometry as (lon, lat) pairs.

    def report(self) -> None:
        logger.info(
            "resolved=%d unresolved=%d cache_len=%d hit_rate=%.4f",
            self.resolved_ways, self.unresolved_ways,
            len(self.cache), self.cache.hit_rate,
        )


if __name__ == "__main__":
    logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
    resolver = WayResolver(maxsize=2_000_000)
    # No locations=True: the cache IS the location store here.
    resolver.apply_file("extract.osm.pbf")
    resolver.report()

Step-by-step walkthrough Jump to heading#

1. Cap enforced on insert, not on read — put appends first, then checks len(self._store) > self.maxsize and evicts. Doing the eviction after the insert keeps the newest entry safe even in the degenerate maxsize == 1 case.
2. Recency refresh on both paths — move_to_end runs inside put when a key already exists and inside every successful get, so an id that is looked up repeatedly stays resident even if it is old by insertion order.
3. popitem(last=False) is the LRU eviction — with last=False the first (oldest-touched) item is removed; the default last=True would pop the most-recent entry and turn the structure into a stack, which is the opposite of what you want.
4. Misses are data, not errors — get returns None and increments a counter rather than raising, so the way handler decides the policy (here: skip). This keeps the stream running across the inevitable boundary and long-way misses.
5. No locations=True on apply_file — the whole point is that this cache replaces pyosmium’s internal store, so you parse without the library location index and let the node() callback feed the cache directly.
6. hit_rate turns the locality bet into a metric — read it after the run: a healthy nodes-then-ways extract should land well above 0.9 with a few-million-entry cap. If it does not, the extract’s ordering, not your code, is the problem.

Verification Jump to heading#

Confirm the cache behaves and that the trade is paying off before you trust the resolved geometry:

• Resident set stays capped. Assert len(resolver.cache) <= resolver.cache.maxsize after the run; it can equal the cap but must never exceed it.
• Hit rate is high on well-ordered input. resolver.cache.hit_rate should print above ~0.90 for a standard Geofabrik extract; a value near 0.5 means the file is not in nodes-then-ways id order.
• Unresolved count is small and explained. unresolved_ways should be a small fraction — dominated by ways clipped at the extract boundary — not a large share, which would signal an undersized cap.
• Eviction actually fires. Run with a deliberately tiny maxsize (say 1000) and watch the evicted node debug lines appear, proving popitem is reached.
• Determinism. Two runs over the same file must report identical resolved/unresolved counts, since the ordering and cap fully determine eviction.

Common errors and fixes Jump to heading#

Specification reference Jump to heading#

The eviction order is defined by collections.OrderedDict: “The popitem() method for ordered dictionaries returns and removes a (key, value) pair. The pairs are returned in LIFO order if last is true or FIFO order if false,” and “move_to_end() moves an existing key to either end of an ordered dictionary.” See the Python collections.OrderedDict documentation. The standard library also ships a ready-made general LRU in functools.lru_cache; it is ideal for pure-function memoization but exposes no manual put for a streaming callback and no bounded-store introspection, which is why an explicit OrderedDict is the right primitive for resolving OSM way geometry.

Frequently Asked Questions Jump to heading#

Related Jump to heading#

• Memory-Efficient Chunk Processing — the parent stage; this cache bounds the location store while that page bounds the record buffer.
• Sizing PBF Chunk Batches to a Memory Budget — the companion lever for turning a RAM budget into a concrete batch size.
• Node-Way-Relation Data Model — why way geometry is a deferred join over node ids in the first place.
• PBF File Structure Deep Dive — the block and id ordering that makes the cache-hit assumption hold.
• Spatial Indexing for OSM Extracts — where resolved geometries go once the cache has reconstructed them.
• Async PBF Parsing with Pyrosm — parallel ingestion for when throughput, not location memory, is the limit.

Up one level: Memory-Efficient Chunk Processing.