Spatial Partitioning Strategies for Event Streams

Partitioning a spatial event stream well means choosing a key that pulls geographically related events onto the same partition — so they stay ordered and warm in the same cache — without letting one busy region overwhelm a single consumer. This page sits under Core Event Fundamentals & Architecture and covers how to turn a geometry into a partition key, how to choose grid resolution, and how to re-partition when the load shifts. Where Sensor Data Routing Patterns decides which consumers an event reaches, partitioning decides which partition it lands on — the layer that governs ordering and locality once the broker is in the picture.

Prerequisites

Before you commit to a partition key, confirm your environment and assumptions:

• Python 3.11+ — pattern matching and modern typing for the keying helpers below
• h3 4.x — the current h3-py API (latlng_to_cell, cell_to_parent) used throughout
• shapely 2.0+ — validity checks and representative_point() for boundary-safe centroids
• A partitioned broker — Kafka topic partitions or Redis Streams shards you can key deterministically
• A skew baseline — per-cell event-rate metrics so resolution choices are measured, not guessed
• EPSG:4326 (WGS84) inputs — all grid encoders expect latitude/longitude; reproject at ingestion
• GeoJSON conformance — geometries validate against RFC 7946 before keying

Why a partition key is a spatial decision

A message broker distributes events across partitions by hashing a key. Consumers scale by claiming partitions, and a broker guarantees ordering only within a partition. For non-spatial data the key is obvious — a user ID, an order ID. For a spatial stream the key encodes a policy: it decides whether two events that happened fifty metres apart are processed in order by the same worker, or scattered across the cluster with no ordering relationship at all.

The naive choices both fail. Keying on a raw coordinate string gives near-infinite cardinality — every event lands on an effectively random partition, destroying locality and any hope of a warm spatial cache. Keying on a coarse label like a country code collapses the whole stream onto a handful of partitions, so one busy region saturates one consumer while the rest idle. What you want sits between these extremes: a key with enough distinct values to spread load, but coarse enough that neighboring events share a value. That is exactly what a discrete global grid system provides.

A discrete global grid system (DGGS) tiles the Earth into addressable cells at a fixed resolution. Encoding a point returns a cell identifier; nearby points return the same identifier, and the number of distinct identifiers is bounded and tunable. Four families dominate in practice — H3 hexagons, S2 cells, Quadkey tiles, and plain geohash — and the full trade study of which to pick lives in the dedicated comparison, H3 vs S2 vs Quadkey for Spatial Partitioning. The short version: H3 hexagons give uniform neighbor distance (every neighbor is equidistant, which matters for radius queries and skew smoothing); S2 offers many fine levels and clean hierarchical containment; Quadkey and geohash are trivially prefix-truncatable, so you can coarsen a key by chopping characters. Admin-boundary keys (a county or postal code) and bounding-box centroid keys are the non-grid alternatives — human-meaningful but unevenly sized, which makes their skew hard to reason about.

The diagram below shows the same region under two schemes mapped onto the same three partitions: H3 hexagons on the left, an S2/Quadkey square grid on the right. The point is not that one is correct — it is that the cell-to-partition assignment is what you are actually designing.

Architecture

The keying path is a four-layer contract. Each layer hands the next a stricter, smaller object, and the partition key is fixed exactly once — at layer three — so it can never drift downstream.

1. Normalization — the raw GeoJSON geometry is validated and, if needed, reprojected to EPSG:4326 (WGS84). Grid encoders assume latitude/longitude degrees; feeding them EPSG:3857 (Web Mercator) metres silently produces wrong cells.
2. Reduction to a representative point — polygons, lines, and MultiPolygons are collapsed to a single point. This is where boundary-straddling is resolved: one point means one cell, deterministically.
3. Cell encoding and partition mapping — the point is encoded to a grid cell at the chosen resolution, then the cell string is hashed to a partition index. The hash, not the cell, is what the broker sees, so partition count and grid resolution stay independent.
4. Dispatch with ordering — the event is written to the partition with the cell recorded in its envelope. Consumers claim partitions and process each partition’s events in offset order, giving per-cell ordering for free.

Only layer three may compute the key. If a downstream stage recomputes it — at a different resolution, or after a reprojection — the event can land on a different partition than its neighbors, and the ordering guarantee quietly evaporates.

Step-by-step implementation

Step 1 — Validate the geometry before touching the grid

Purpose: Guarantee the encoder only ever sees a valid, EPSG:4326 geometry, so cell assignment cannot be corrupted by bad topology.

An invalid geometry — a self-intersecting polygon, a null coordinate, a NaN — will either raise deep inside the encoder or, worse, encode a garbage point. Validate first and reject early.

from shapely.geometry import shape
from shapely.validation import explain_validity

def validated_geom(geojson_geometry: dict):
    """Parse a GeoJSON geometry (RFC 7946) and return a valid Shapely object.

    Raises ValueError on empty, unparseable, or invalid input so the caller
    can quarantine the event before any cell is assigned.
    """
    try:
        geom = shape(geojson_geometry)
    except Exception as exc:                       # malformed structure
        raise ValueError(f"unparseable geometry: {exc}") from exc
    if geom.is_empty:
        raise ValueError("geometry is empty")
    if not geom.is_valid:
        # Do not silently repair a partition-key input: a repaired shape can
        # shift the representative point across a cell boundary.
        raise ValueError(f"invalid geometry: {explain_validity(geom)}")
    return geom

Step 2 — Reduce any geometry to one representative point

Purpose: Turn a polygon, line, or MultiPolygon into the single point that will determine the cell — safely, even for concave and multi-part shapes.

A centroid is the intuitive choice, but the centroid of a C-shaped boundary or a MultiPolygon of two islands can fall in empty space between the parts, landing in a cell the feature does not even touch. Shapely’s representative_point() is guaranteed to lie on the geometry.

from shapely.geometry.base import BaseGeometry

def representative_latlng(geom: BaseGeometry) -> tuple[float, float]:
    """Return (lat, lng) in EPSG:4326 for the point used to derive the cell.

    - Point: itself.
    - Polygon/Line: point-on-surface, never a centroid that could fall in a hole.
    - MultiPolygon: point-on-surface of the largest part, a stable representative
      choice that stays put as smaller parts are added or removed.
    """
    if geom.geom_type == "Point":
        pt = geom
    elif geom.geom_type == "MultiPolygon":
        largest = max(geom.geoms, key=lambda g: g.area)
        pt = largest.representative_point()
    else:
        pt = geom.representative_point()
    # GeoJSON is (lng, lat); H3/S2 want (lat, lng).
    return pt.y, pt.x

Step 3 — Encode the point to a cell and map it to a partition

Purpose: Produce the deterministic partition key that fixes both spatial locality and ordering.

Encode the representative point with h3.latlng_to_cell at your chosen resolution, then hash the cell string into the partition range. Keeping the hash separate from the cell lets you change partition count without re-keying, and lets you coarsen the cell (via cell_to_parent) without touching the broker.

import hashlib
import h3

PARTITION_COUNT = 12
KEY_RESOLUTION = 6          # H3 res 6 ~ 36 km^2 cells; tune against measured skew

def partition_key(lat: float, lng: float, resolution: int = KEY_RESOLUTION) -> str:
    """Deterministic H3 cell used as the broker partition key."""
    return h3.latlng_to_cell(lat, lng, resolution)

def partition_index(cell: str, partitions: int = PARTITION_COUNT) -> int:
    """Stable cell -> partition mapping, independent of Python's salted hash()."""
    digest = hashlib.sha256(cell.encode()).digest()
    return int.from_bytes(digest[:8], "big") % partitions

def key_event(geojson_geometry: dict) -> tuple[str, int]:
    geom = validated_geom(geojson_geometry)            # Step 1
    lat, lng = representative_latlng(geom)             # Step 2
    cell = partition_key(lat, lng)                     # Step 3
    return cell, partition_index(cell)

Step 4 — Dispatch with the cell recorded for ordering and re-routing

Purpose: Write the event to its partition and preserve the cell so consumers can order per-cell and coarsen later without re-deriving keys.

import json

def build_record(geojson_geometry: dict, payload: dict) -> dict:
    cell, part = key_event(geojson_geometry)
    return {
        "partition": part,
        "key": cell,                       # H3 cell string, for per-cell ordering
        "scheme": "h3",                    # scheme + resolution stamp enables safe migration
        "resolution": KEY_RESOLUTION,
        "value": json.dumps(payload),
    }

Spatial validation and error handling

Keying is only as trustworthy as the geometry feeding it, so validation belongs before the encoder, never after. Step 1 rejects empty, unparseable, and invalid geometries; the deliberate choice there is to reject rather than repair. A make_valid() repair can nudge a polygon’s boundary enough to move its representative point across a cell edge, silently reassigning the event to a different partition than its true neighbors — a locality bug that never raises. Repair, if you want it, belongs in a separate validation stage whose output is re-validated, following the patterns in Geometry Validation Pipelines.

CRS mistakes are the other silent killer. Every grid encoder expects EPSG:4326 (WGS84) degrees. Hand it EPSG:3857 (Web Mercator) metres and latlng_to_cell will not error — it will treat a coordinate like -13627665 as a latitude, wrap it, and return a plausible-looking but entirely wrong cell. Normalize at ingestion and validate that coordinates fall in [-90, 90] and [-180, 180] before keying. A Pydantic model at the boundary makes this enforceable:

from pydantic import BaseModel, field_validator

class KeyableEvent(BaseModel):
    geometry: dict          # GeoJSON geometry, RFC 7946
    crs: str = "EPSG:4326"

    @field_validator("crs")
    @classmethod
    def must_be_wgs84(cls, v: str) -> str:
        # Reproject upstream; the keyer only accepts EPSG:4326.
        if v.upper() != "EPSG:4326":
            raise ValueError("partition keying requires EPSG:4326 (WGS84)")
        return v.upper()

Resolution, skew, and re-partitioning

Resolution is the single most consequential knob. It trades three quantities against each other: locality (coarser cells keep more neighbors together), partition-key cardinality (finer cells create more distinct keys), and skew (coarser cells concentrate more events per key). Pick the coarsest resolution whose distinct-cell count comfortably exceeds your partition count and whose busiest cell stays under one consumer’s throughput ceiling. For city-scale streams that band is often H3 resolution 5-7 or the equivalent S2 level 8-11, but the only honest way to set it is against measured per-cell rates.

Skew is inherent to spatial data — events cluster in cities, along roads, around sensors — so a uniform grid never yields uniform load. Two mitigations help. First, salt hot cells: append a bounded random suffix to the key for cells above a rate threshold, spreading one cell across several partitions at the cost of per-cell ordering for that cell only. Second, use a finer resolution in dense regions via a mixed-resolution scheme, keeping coarse cells where the stream is sparse. Detecting when a cell has gone hot is a monitoring problem covered in Consumer Lag & Partition Skew Monitoring; the broker-side mechanics of assigning keys to partitions are in Broker Selection & Partitioning for Spatial Streams.

Re-partitioning — changing resolution, grid family, or partition count — is a migration, not an edit. Never re-hash a live topic in place: a resolution-6 cell and a resolution-7 cell are different keys for the same point, so re-keying in flight shatters per-cell ordering and duplicates state. Instead, stamp every event with a scheme and resolution version (as Step 4 does), dual-write to old and new topics during the cutover, and move consumers to the new topic only once its offsets have caught up.

def coarsen_key(cell: str, target_resolution: int) -> str:
    """Roll an H3 cell up to a coarser parent without re-deriving from geometry.

    Lets a consumer group aggregate at a coarser grain than the producer keyed
    at — the basis of a zero-downtime resolution migration.
    """
    current = h3.get_resolution(cell)
    if target_resolution > current:
        raise ValueError("target must be coarser than the source cell")
    return h3.cell_to_parent(cell, target_resolution)

Because a boundary-straddling feature is resolved to exactly one representative point (Step 2), it always maps to exactly one cell and one partition. If a downstream consumer genuinely needs every cell a large polygon overlaps — to invalidate several regional caches, say — compute that covering set separately with h3.polygon_to_cells and carry it in the payload as routing hints. It must never become the partition key: a key that maps to multiple partitions cannot be ordered.

Delivery and ordering

A broker orders events only within a partition, so per-cell ordering is a direct consequence of a stable cell-to-partition mapping. Keep that mapping pure — sha256 of the cell modulo the partition count, as in Step 3, not Python’s hash(), which is salted per process and would scatter the same cell across partitions on restart. With a stable map, at-least-once delivery is the practical target: an event is never lost, but a consumer may see a cell’s events more than once after a rebalance or retry, so writes must be idempotent (keyed on a deterministic event ID). Exactly-once across a spatial cluster is rarely worth its cost. Ordering only holds within a cell; two events in adjacent cells that hash to different partitions have no ordering relationship, which is the correct and expected behavior.

Verification

This test confirms the two properties partitioning must guarantee: nearby points share a partition (locality), and a MultiPolygon keys to a cell that actually contains its representative point (boundary safety).

import h3
from shapely.geometry import shape

def test_nearby_points_share_partition():
    # Two points ~200 m apart in San Francisco (EPSG:4326).
    a = {"type": "Point", "coordinates": [-122.4194, 37.7749]}
    b = {"type": "Point", "coordinates": [-122.4174, 37.7752]}
    cell_a, part_a = key_event(a)
    cell_b, part_b = key_event(b)
    assert cell_a == cell_b            # same H3 res-6 cell
    assert part_a == part_b            # therefore same partition

def test_multipolygon_keys_to_a_contained_cell():
    mp = {
        "type": "MultiPolygon",
        "coordinates": [
            [[[-122.42, 37.77], [-122.41, 37.77],
              [-122.41, 37.78], [-122.42, 37.78], [-122.42, 37.77]]],
            [[[-122.30, 37.80], [-122.29, 37.80],
              [-122.29, 37.81], [-122.30, 37.81], [-122.30, 37.80]]],
        ],
    }
    cell, _ = key_event(mp)
    lat, lng = h3.cell_to_latlng(cell)
    # The chosen point-on-surface must lie inside the larger part.
    largest = max(shape(mp).geoms, key=lambda g: g.area)
    assert largest.buffer(0.02).contains(shape(
        {"type": "Point", "coordinates": [lng, lat]}))

Troubleshooting

FAQ

Related

• Core Event Fundamentals & Architecture — the parent section covering spatial event modeling, delivery semantics, and pipeline architecture
• H3 vs S2 vs Quadkey for Spatial Partitioning — the head-to-head comparison of grid systems as partition keys, with cell geometry and cardinality trade-offs
• Sensor Data Routing Patterns — how routing decides which consumers an event reaches before it is partitioned
• Broker Selection & Partitioning for Spatial Streams — the broker-side mechanics of mapping keys to Kafka and Redis Streams partitions
• Consumer Lag & Partition Skew Monitoring — detecting hot cells and unbalanced partitions before they cause lag

Explore this section