kuan butts

Integration Tradeoffs Between MCPs and Plugins

Sun, 12 Apr 2026 00:00:00 +0000

The Integration Layer: Why MCPs “Blow Up” Context

I wrote this post primarily to dig into why the Model Context Protocol (MCP) is often blamed for consuming massive context windows and driving out-of-control token costs in online discussions.

The main complaint I see of MCP centers on its tendency to create massive context windows, leading to higher costs and increased latency. This isn’t necessarily a bug, but a side effect of a fundamental difference in how data moves into the model. Traditional Plugins and Skills treat tools as functions with strict schemas: the model calls a defined tool and receives a targeted, concise response that keeps the context window small.

MCPs, in contrast, treat tools as data providers that stream any information (be it files, logs, or database rows) directly into the prompt. In this philosophy, the model acts as the primary interpreter: So it gets a huge blob of raw data and reasons about it in an entirely flexible manner, treating it purely as unstructed text at the onset. This means that even if only 5% of a document is relevant, often 100% of it is loaded into the context, turning the context window itself into the integration layer.

But this is also a product of how MCPs are designed - if you have an MCP that provides large unsorted blobs of data like this, you end up getting that flexibility. If you didn’t and you previously had more scoped MCPs, there are other considerations vs. a plugin for example, that need to be considered. Those will be discussed later.

Local Execution and the Permission Model

The architectural shift in MCP is most apparent when looking at local execution. Thus, one of the most important distinctions in MCP architectures is where execution happens and under whose identity.

Consider a scenario where an AI agent needs to perform an AWS Athena query.

The MCP Model: “Run as You”

In an MCP setup, the “server” is frequently just a local script (Python or Node) running on your machine. When the LLM invokes an MCP tool to run a query, the script executes as a local process.

Flow Diagram

flowchart LR
  subgraph LocalEnv["Local Environment"]
    direction LR
    A[Claude/Client]
    B[MCP Script]
    C["~/.aws/credentials"]
  end
  D[("AWS Athena")]
  
  A --> B
  B --> C
  C --> D

What this means

Because this script lives in your environment, it implicitly inherits your identity, utilizing your local credentials and active SSO sessions. This provides immense flexibility but introduces a significant permissions risk. That is, the model effectively gains a “remote control” for your environment. It will execute any query you are personally authorized to run unless your code explicitly blocks it. That is, event if your prompt says not to do something, there is a risk that it may be done regardless - there is no guarantee against those hazards.

The tradeoff

Pros

Extremely flexible
Easy to iterate
Powerful local integrations

Cons

High permission risk
The model can indirectly trigger any action you are authorized to perform
Safety depends entirely on your code (not the prompt)

The Plugin Model: “Call a Service”

Conversely, a plugin calls a remote hosted service via an API. The execution happens on an external server using service-side credentials. This creates a very explicity and hard control boundary; the model is confined to defined endpoints and schemas, and the backend enforces security rules that the model cannot bypass through prompt manipulation alone.

flowchart LR
  A[Claude / Client]
  B[Plugin API Endpoint]
  C[Backend Service]
  D[(AWS Athena)]

  A --> B
  B --> C
  C --> D

Memory, the Harness, and Identity

There is additional consideration to be had regarding reliance on memory when evaluating data from an MCP response and holding it in raw, blob text form for evaluation and downstream flow reference. Specifically, you are relying on the behavior of the agent/harness and how it manages memory to ensure the important elements from your MCP response are preserved. This is subject to the agent’s interpration during runtime and not explicitly handled like in a plugin.

A helpful insight that further expands on this comes from this blog post “Your harness, your memory” is that memory is not a plugin: it lives in the harness. The “harness” is the system managing the context lifecycle, such as Cursor or a managed chat interface (Opus, Codex, etc.). It is the harness that makes “invisible decisions” about what to summarize, truncate, or delete as the conversation progresses.

While MCP assumes memory is external data we can supply, the reality is that memory is whatever survives the context management of the harness. This creates a form of “state dependency”. If the harness owns the memory, you cannot easily move your agent’s learned patterns or history between different platforms.

Skills: The Behavioral Layer

To complete the hierarchy, skills act as a third layer that sits above execution. While MCPs and plugins provide the capabilities (e.g. “What code or services can I run?”), skills provide the policies (e.g. “How should I behave?”).

So we can see how the two aforementioned concepts can exist in parallel and interact with the same remote resources, but with plugins and MCPs existing as different intermediaries with different potential permissions scopes and degrees of flexibility. Then, skills provide guidance on how to use either of these (or any other available tooling).

flowchart TB
  Skill["Skills (Behavioral Policy Layer)"]
  LLM["LLM Reasoning Layer"]
  MCP["MCP (Local Execution Tools)"]
  Plugin["Plugins (Remote APIs)"]
  System["External Systems (AWS, DBs, etc.)"]

  Skill --> LLM
  LLM --> MCP
  LLM --> Plugin
  MCP --> System
  Plugin --> System

A skill does not directly access AWS or run queries. Instead, it biases the model’s decision-making process—for instance, instructing it to always inspect a schema or, for example, apply a LIMIT 1000 before invoking the Athena DWH query tool. The tool then, can exist in entities such as the more deterministic MCP and plugin layer described prior.

Conclusion

Ultimately, the choice between these architectures is a trade off. MCPs provide the most flexibility for reasoning by operating directly within your local environment, yet they inherit the risk of lower explicit control, especially as they are running with your full identity rather than as a sandboxed agent. Plugins are on the other end of the spectrum in this sense: they are strictly scoped by design, both in their permission sets and in how the agent harness prioritizes their structured responses within its memory. Above both these execution layers sit skills, acting as the behavioral guide. They don’t handle the mechanics of the query, but instead set preferences for agents on when to lean into the flexible stream of an MCP and when to rely on the predictable boundaries of a plugin.

Streaming When Your Cache Becomes the Bottleneck

Tue, 07 Apr 2026 00:00:00 +0000

Introduction

With many real-time systems, there’s a pretty standard shape:

ingest from a high-volume event stream
assign those events to some entity
periodically recompute derived state from recent observations

At small to medium scale, a shared cache (Redis/Valkey) works great as the boundary between ingestion and aggregation. However, at a large enough scale, this same cache configuration can become this biggest bottleneck to both a performant data pipieline and developer velocity in terms of attaching to it or spinning up parallel pipelines.

This post walks through a tradeoff I ran into: using a distributed cache vs a streaming system (Kinesis) as the interface between live data ingestion and downstream computation.

Above: Last attempt at a Gemini AI-generated diagram for this just on a whim, attempting to show how Kinesis enables multi-tenant consumption of a high-read resource that, as a cache, would be overwhelmed or trigger excessive queuing, as represented by the well.

System Overview

Stripping away from my domain specifics (live probe data from real-world telemetry map matched onto a road network and then generating real-time speeds), the system looks like this:

~100M events per minute (~1.6M/sec)
each event is assigned to one of hundreds of millions of possible entities
at any moment, ~250–500M entities are “active”

There are two main stages:

1. Ingestion + Assignment

clean raw events
run compute-heavy assignment (classification / matching)
emit output data with pairing metadata (entity_id, event)

2. Aggregation / Estimation

group entities into partitions
periodically recompute derived state using all qualifying recent events

flowchart TD
    A[Event Stream] --> B[Ingestion + Assignment]
    B --> C["(entity_id, event)"]
    C --> D[Cache]
    D --> E[Aggregation Workers]

The Initial Design: Cache-Centric

After assignment, all events are written into a distributed cache (Redis/Valkey). Aggregation workers then:

scan all relevant keys for a partition
load everything into memory
compute derived state
repeat frequently (potentially sub-minutely - so high rate of revolution)

This had worked well enough for a while. But a problem in the design was present that kept rising up: aggregation is stateless. That means every run starts from scratch - reading all of the cache for its respective partition.

The Problem: Read Amplification

At this scale, the system isn’t just write-heavy; it is also extremely read-heavy. So, in practice, the cache layer was handling:

~660K operations/sec (reads + writes)
~510 MB/sec sustained network throughput
~1.6 KB average payload size
across 24 shards

Each aggregation cycle:

re-reads large portions of recent data
across many partitions
often in parallel

The consquence of this was a few major issues:

1. Read amplification

The same data is read repeatedly, even when only a small fraction has changed.

2. Synchronized load spikes

Many workers scanning the same partitions at the same time:

flowchart TB
  subgraph workers["Aggregation workers"]
    direction LR
    W1[scan]
    W2[scan]
    W3[scan]
    W4[scan]
    W5[scan]
  end
  Cache[("Cache")]
  W1 --> Cache
  W2 --> Cache
  W3 --> Cache
  W4 --> Cache
  W5 --> Cache

3. Contention

ingestion writes
aggregation reads

…all competing for the same resource.

Interestingly, the system settled into roughly a 1:1 read-to-write ratio—but that hides the real issue that the reads are large, repeated scans, not incremental updates.

Naive Solution: Scale the Cache

The first fix is the obvious one which was taken first:

add more nodes
increase memory
scale throughput

This works and bought us lots of time, but it’s expensive and doesn’t address the underlying inefficiency.

In our case:

~24 shards
node type: cache.r7g.4xlarge
~$13,500/month

And more importantly the system must be provisioned for peak load at all times. Furthermore, every time a developer wants to work with the same data, we can’t just add a new consumer to the cache - that would cause the cache to fall over. So we need to create a new pipeline to feed a new cache. This is a lot of pipeline duplicate and very expensive. The developer time involved in doing this is often prohibitively high, not to mention the operational complexity of accomplishing it.

A subtle scaling problem

Unlike compute systems (Lambda, ECS, etc.), cache scaling is not elastic:

scaling out (adding shards) is manual and slow
scaling in (removing shards) is risky and disruptive
no true autoscaling based on load

The result, in reality, is that you provision for peak and pay for it even at trough. In a production system, where you want to buy a lot of headroom (literally), this can get pricey on serious workload caches very fast.

Next solution: Make Consumers Stateful

One idea was to flip the model; so, instead of repeatedly scanning the cache:

make aggregation workers stateful
assign each worker a stable partition
maintain local in-memory state
update incrementally via pub/sub

Redis (and Valkey) support keyspace notifications, which can be used as a lightweight pub/sub mechanism.

flowchart TD
  Cache[("Cache")]
  Cache -->|"pub/sub updates"| Workers["Stateful Aggregation Workers"]
  Workers --> Outputs["Derived State Outputs"]

The main advantages of this approach are that it avoids repeated full scans of the data and significantly reduces read pressure on the cache. However, this approach comes with its own set of tradeoffs:

requires stable partition ownership
introduces stateful workers
harder failure recovery (e.g. handling cold starts)
still tied to shared cache
does not solve multi-consumer needs (lots of cold starts, deploys are all stampeding herd situations, can destabilize prod stack)

So, while this solution has merit and does incrememntally help, it doesn’t solve the bigger problem.

The Bigger Problem: Coupling

The cache bottleneck exposes a deeper problem that the ingestion pipeline and aggregation logic are tightly coupled. If someone wants to try a new model or experiment they had to re-run ingestion and including the expensive assignment step; as noted prior. In practice this means:

duplicate pipelines
high compute cost
backpressure on shared services
slow iteration

At this scale, recomputing upstream work is often more expensive than storing and distributing it.

The Constraint: Unsafe Multi-Tenancy

So, fundamentally, this architecture of a shared cache cannot safely support multiple consumers. Adding experimental workloads meant:

increased read pressure
unpredictable latency
risk to production systems

So experimentation required isolated infrastructure for the entire data pipeline - very expensive and hard to set up and manage.

The Shift: Introduce a Stream

The solution was to decouple ingestion from consumption using a stream. After assignment, events are written to a Kinesis stream:

flowchart TD
  ES[Event Stream]
  IA[Ingestion + Assignment]
  KS[("Kinesis Stream")]
  Prod[Prod]
  ExpA[Experiment A]
  ExpB[Experiment B]
  ES --> IA
  IA --> KS
  KS --> Prod
  KS --> ExpA
  KS --> ExpB

Why Kinesis Works Better Here

With on the order of ~100 shards, throughput scales roughly linearly and parallelism stays predictable: No guessing how much headroom a single shared reader needs.

Enhanced Fan-Out (EFO) gives each consumer its own dedicated throughput, so consumers do not contend with each other and production workloads stay isolated from experiments. The bigger structural win is decoupling: ingestion runs once, downstream consumers can evolve independently, and the architecture drops the shared read bottleneck that hamstrung the previous cache-centric design.

Cost Comparison

Cache (Redis / Valkey)

~$13,500/month
scales with memory + read load
provisioned for peak

Kinesis

~$1,500/month base (100 shards)
~$500–1,000 per consumer
~$3k per EFO consumer

Even with multiple consumers, total costs remain significantly lower than scaling the cache or duplicating ingestion pipelines.

Tradeoffs

Dimension	Cache (Redis)	Stream (Kinesis)
Read efficiency	Poor (scan-heavy)	High (push-based)
Multi-consumer	No bueno	Excellent
Cost scaling	High	Moderate
Latency	Very low	Slightly higher

The stream is not a strict upgrade on every axis: you give up a little of the sub-millisecond read profile you get from a hot cache, and you take on streaming operations (shards, consumers, EFO) as a first-class part of the bill. Here that was an explicit trade I can make. That is, aggregation is periodic and bounded by read amplification and multi-consumer safety well before raw cache latency would be an issue.

Conclusion

The shared cache served its purpose and even handled the high volume scale of a single consumer well enough for long enough to get us here. But, with the following contraints:

high read amplification
stateless consumers
multiple downstream use cases
need for experimental stacks to have safe read access

That design had run its course and become a bottleneck not just in performance, but in our ability to develop and evolve our overall system into the future. Moving to a streaming model shifts the system from being pull-based, tightly coupled, and read-heavy to more push-based and decoupled enabling the multi-consumer paradigm we want. So we don’t solve for just performance, but also gain key aspects of flexibility:

new consumers without recomputation
isolation between production and experiments
(more) predictable scaling costs

When multiple consumers need the same high-volume data, a stream is often a better abstraction than a shared cache; especially when recomputing that data is expensive.

Dynamically Rebalancing Geo-Constrained Stream Processing

Thu, 01 Jan 2026 00:00:00 +0000

Context

One of the more common failure modes in real-time geospatial systems has nothing to do with algorithms being wrong. It’s that the real world refuses to stay still.

This post walks through a practical pattern for handling high-volume, real-time location data where part of your pipeline is explicitly geo-constrained (map matching, spatial joins, routing lookups, etc.), while the rest of the system is not. We’ll look at why static geographic partitioning breaks down, and how to use real-time monitoring plus fast redeploys to continuously rebalance work instead of over-allocating forever.

The canonical pipeline shape

Most real-time geo pipelines look roughly like this:

┌─────────────────┐         ┌──────────────────────┐         ┌─────────────────┐
│   Aspatial      │         │  Geo-Constrained     │         │   Downstream    │
│  Data Stream    │────────>│    Transformer       │────────>│    Consumers    │
│ (ex: Kinesis)   │         │                      │         │                 │
└─────────────────┘         └──────────────────────┘         └─────────────────┘

You ingest a jumbled, global stream of location events.
You pass it through a geo-constrained transformer (map matching is a common example).
After enrichment, the data fans out to downstream consumers that generally don’t care about geography anymore.

The critical detail is that only one section of the pipeline has strict geographic constraints. That section is where everything gets interesting — and unstable.

Why geo-partitioning is inherently unstable

The issue isn’t poor engineering; it’s that real-world spatial data is non-stationary.

Volume changes come from:

Day/night cycles
Commute peaks
Weather
Local events
Virality and feedback loops

Above image is a generic example showing how even with the best partitioning strategy, various partitions are subject to time-of-day resource demand fluctuations.

Even if global throughput is stable, regional load never is. One city lights up while another goes quiet. Then they swap.

A common mitigation is “smart” partitioning:

Pair cities on opposite sides of the globe
Mix antipodal time zones (Johannesburg + Honolulu, etc.)
Try to smooth diurnal cycles statistically

This helps — but it never solves the problem. You still end up with:

Hot partitions you must size for worst-case load
Cold partitions wasting compute most of the day
A few megacities that remain pathological outliers no matter how clever your scheme is

At scale, this means systematic over-allocation.

Real goal: rebalance, don’t predict

Instead of trying to design the perfect static partitioning algorithm, the goal shifts: Continuously rebalance the geo-constrained service based on observed load.

That means:

Monitoring real-time spatial volume
Recomputing partitions from current conditions
Redeploying the geo-service frequently enough to track reality

This post assumes a few important properties:

Fast startup: New partition workers can come online in seconds to minutes.
Blue-green deploys: You can stand up a new geo-partitioned service in parallel and flip traffic.
No instantaneous spikes: Because this is real-world geo data, even “viral” events ramp over minutes (at least, if not longer), and definitely not less (not milliseconds).

Under those assumptions, dynamic rebalancing becomes not only possible, but practical.

A miniaturized example

To make this concrete, we’ll shrink the problem down to a single metro area instead of the globe. We define:

Two system states: before and after
The “after” state has:
- ~2× the total points - and thus higher overall activity
- More hotspots of dense activity vs. the prior state

Each partition is capped at 2,500 points. The goal is to build contiguous geographic partitions that get as close to that limit as possible.

State 1: before

Here’s a representative partitioning outcome:

Total partitions: 12
Max points per partition: 2500

Partition   0:   2272 points (90.9%)
Partition   1:   2265 points (90.6%)
Partition   2:   2257 points (90.3%)
Partition   3:   2254 points (90.2%)
Partition   4:    396 points (15.8%)
Partition   5:    371 points (14.8%)
Partition   6–11: < 200 points each

A few things jump out: First; hot areas pack efficiently. Secondly, cold regions fragment into many tiny partitions that are not contiguous. These tail partitions can safely be merged later. So far, so good.

State 2: naive preservation breaks down

Now activity doubles and new hotspots appear. If we try to preserve existing partitions and only split the ones that overflow, we get something like this:

Partition   0: 3243 points (129.7%)
Partition   2: 3689 points (147.6%)
...
Total partitions: 21

We’ve avoided redoing everything, but introduced a new problem:

Weird “edge” partitions appear
Shapes shrink inward awkwardly
Utilization becomes noisy and uneven

These liminal partitions are artifacts of trying to respect history that no longer matters.

Resolution: rebuild from scratch

If your deploys are fast, there’s no reason to preserve old partitions at all. Instead:

Ignore the previous state
Repack all quadkeys based on current load
Blue-green swap the new configuration in

The result is cleaner, fewer partitions, and higher average utilization:

Total partitions: 13
Mean utilization: 61.5%
Median utilization: 90.1%

Cold tail partitions still exist, but they’re smaller in number, they’re easy to group together, they don’t pollute the hot path. This turns partitioning into a stateless optimization problem, not a migration problem.

Why this matters: allocation mismatch

To see the cost of not rebalancing, apply State-2 data to State-1 partitions:

Partition 2: 2257 → 6602 points (264% utilized)
Partition 0: 2272 → 4510 points (180% utilized)

You’d need to provision 2–3x the resources just to survive peak load in a single partition — and every other partition would sit idle most of the time. Dynamic rebalancing converts that worst-case sizing problem into a steady-state one.

System architecture

At a high level, the control plane for this looks like:

Kinesis Stream

   → Managed Flink (Kinesis Data Analytics / EKS)
       - Job Manager
       - Task Managers
       - State backend (S3)
       - Checkpoints (S3)

   → DynamoDB / S3

Managed Flink on AWS makes this pattern pretty easy to implement. You get a continuously running, stateful streaming job without having to own the cluster lifecycle, and can still retain enough control to make dynamic reconfiguration viable.

Flink’s execution model lines up well with what is needed:

It has native keyed aggregation: Counting by quadkey is a first-class operation (keyBy → window / process)
Continuous output: do not need to wait for batch windows to close. Emit rolling aggregates on a cadence (e.g. every 30–60 seconds) that’s fast enough to drive rebalancing.
Operational slack: The system tolerates a few minutes of lag between “things changed” and “partitions updated,” which matches real-world geo dynamics well.

On AWS specifically, this is easiest to run as Kinesis Data Analytics for Apache Flink (fully managed).

This leads to a modified pipeline architecture from the canonical one shown originally:

                   ┌────────────────────────┐
                   │   Managed Flink Job    │
                   │ (Kinesis → Flink)      │
                   │                        │
                   │  • lat/lon → quadkey   │
                   │  • counts by quadkey   │
                   │  • checkpointed state  │
                   └───────────┬────────────┘
                               │
                               │ periodic snapshot
                               ▼
              ┌──────────────────────────────────┐
              │   Spatial Control / Partitioner  │
              │                                  │
              │  • reads quadkey counts          │
              │  • builds contiguous partitions  │
              │  • enforces max load per shard   │
              └────────────┬─────────────────────┘
                           │
            new partition  │ spec
                           ▼
              ┌──────────────────────────────────┐
              │   Geo Processing Service (NEW)   │
              │   Blue / Green Deployment        │
              │                                  │
              │  • one worker per partition      │
              │  • warmed up off to the side     │
              └───────────┬──────────────────────┘
                          │
                   traffic swap
                          ▼
              ┌──────────────────────────────────┐
              │        Downstream Consumers      │
              │  (post-geo, no spatial aspect)   │
              └──────────────────────────────────┘

Triggering new geo-service versions

Can achieve this in multiple ways:

CI/CD pipelines (GitHub Actions / CodePipeline) that kick off deployment once new partition specs land in S3/DynamoDB
Kubernetes operators that watch a config map or annotation and perform a blue-green swap
AWS ECS / EKS webhook triggers from your partitioner process

Example: quadkey aggregation job

At a conceptual level, the Flink job does something very simple:

Read events from Kinesis
Derive a quadkey for each point
Maintain a running count per quadkey
Periodically flush those counts to an external store

Pseudocode-wise, this looks like:

stream
  .map(event => (quadkey(event.lat, event.lon), 1L))
  .keyBy(_._1)
  .process(new QuadkeyCountProcessFn)
  .addSink(countSink)

Where QuadkeyCountProcessFn:

Keeps per-quadkey counters in keyed state
Emits updated counts on a timer (e.g. every 60s)

Partition construction

1. Start from the hottest locations

We always seed new partitions from peak quadkeys first:

sorted_qks = sorted(qk_counts.items(), key=lambda x: -x[1])

This ensures:

Dense areas get first claim on capacity
Hotspots don’t get fragmented across partitions

2. Grow partitions by adjacency

Contiguity matters. We explicitly grow partitions using neighboring quadkeys:

def get_quadkey_neighbors(self, qk: str) -> Set[str]:  
    tile = mercantile.quadkey_to_tile(qk)  
    neighbors = set()

    for dx in [-1, 0, 1]:  
        for dy in [-1, 0, 1]:  
            if dx == 0 and dy == 0:  
                continue  
            neighbor_tile = mercantile.Tile(tile.x + dx, tile.y + dy, tile.z)  
            neighbors.add(mercantile.quadkey(neighbor_tile))

    return neighbors

This guarantees partitions are spatially contiguous, necessary for map matching (you would use this area plus a buffer to end up with a contiguous region to safely ensure all edges needed to match to the points are present).

3. Prefer “square-ish” growth

When expanding a partition, neighbors are ranked by how many edges they share with the current component:

adjacency_score = len(neighbor_neighbors & component)

We then sort by adjacency (favor compact shapes) and point count (fill efficiently). This produces partitions that are both well-packed and geometrically sane.

Why this works in practice

This works because it matches how the system behaves in reality. Instead of predicting a stable future, it responds to current conditions, sizes capacity to what’s actually happening, and keeps geographic complexity confined to a single stage. The cost is a bit of redeploy churn, but the payoff is far less wasted compute.

Most importantly, it accepts that geo load balancing is not a one-time design problem. It’s a continuous control problem.

Triaging Heuristics for Erronous Matches

Fri, 26 Dec 2025 00:00:00 +0000

Handling Noisy Probes and Unrealistic Paths

This is a follow up to my last post; discussing issues I saw when map matching and some notes on improving against those problems. One issue that became increasingly obvious after running the matcher against real probe data is how noisy probes interact with dense road networks.

In urban environments especially (as shown in above example), a single probe can be spatially close to multiple candidate ways: a main road, a frontage road, a service alley, or even a perpendicular side street. When the scoring model is too permissive, the matcher will occasionally “snap” to one of these intersecting roads even though the vehicle never really traveled down it.

Context: From Naive Viterbi to Practical Heuristics

None of the strategies described below are novel. In fact, they’re fairly standard ideas in map matching and routing systems more broadly.

In my previous post, Lightweight HMM Map Matching in Go, I intentionally started from a very naive place: a straightforward Viterbi implementation over candidate road segments, with minimal transition logic and few guardrails. That was useful as a baseline, but it also made the failure modes extremely obvious once real probe data entered the picture.

This follow-up is really about identifying the minimum set of logical checks needed to make the matcher behave plausibly, without turning it into a heavy, compute-intensive routing engine. The goal isn’t to perfectly model driver behavior or handle every edge case — it’s to avoid the most common and most egregious matching errors while preserving simplicity, performance, and operational clarity.

Everything that follows can be thought of as adding just enough structure around the HMM to constrain it to realistic paths, rather than letting it “mathematically” solve the problem in ways that no real vehicle ever would.

The Problem: Intersections + Noise = Bad Matches

When this happens, the downstream effect is worse than just a single bad segment. The HMM will often try to recover by immediately transitioning back to the original road. The resulting matched path looks something like:

main road
sudden turn onto a side street, go down to next intersection
immediate u-turn (no matter how unrealistic)
back onto the main road (could have just proceeded straight)

From a routing perspective, this is clearly unrealistic. From a scoring perspective, however, the original model didn’t strongly discourage this behavior. Short segments, small distances, and weak penalties made these transitions look acceptable.

Over longer traces, these errors compound into paths that zig-zag through intersections in ways no real vehicle would.

First Fix: Penalize U-Turns

The most obvious initial fix was to explicitly penalize u-turns.

If a transition implies a near-180° change in heading between consecutive matched ways, that transition should be costly. In real driving, u-turns are rare, deliberate, and usually constrained to specific locations. They should not be the default recovery mechanism for noisy probes.

Adding a u-turn penalty immediately reduced the most egregious back-and-forth behavior.

But once that was in place, a broader issue became clear.

Generalizing the Idea: Penalize Turns, Not Just U-Turns

U-turns are just the extreme case. In practice, many bad matches involve sharp turns that aren’t full reversals but are still implausible given the trace.

This led to a more general approach: add a turn cost based on heading change.

Instead of a binary “u-turn or not” check, transitions are penalized proportionally to how sharp the turn is. Small heading changes are cheap. Large heading changes get increasingly expensive.

This makes the matcher prefer smooth, continuous motion unless the probes strongly indicate otherwise.

Road Class Matters

Even with turn penalties, another pattern showed up repeatedly: many of the accidental detours were happening on low-class roads.

Alleys, service roads, and tiny access lanes are often geometrically close to major roads. A single noisy probe can easily fall closer to an alley than to the primary road the vehicle is actually on.

What made these cases especially bad was the sequence:

primary road → alley
short travel
u-turn
back to primary road

From a modeling standpoint, this should be extremely unlikely.

To address this, transition costs now also consider road class. Transitions from higher-class roads (e.g. primary or secondary roads) to much lower-class roads (e.g. alleys or service roads) are penalized heavily, especially when followed by sharp turns or u-turns.

This reflects real behavior: drivers don’t casually dip into alleys and immediately reverse course unless they are intentionally accessing something there.

Distance and Probe Coverage

Another important signal is how much evidence there is that a candidate way was actually traveled.

If a candidate road is only supported by a single probe, especially when neighboring probes align well with another road, the matcher should be skeptical. A single noisy observation should not be enough to justify a detour.

To capture this, transition scoring now incorporates:

Distance traveled on the candidate way
Probe coverage: how well the trace aligns with the geometry over multiple points

Short, weakly supported segments get penalized relative to longer, well covered ones. This makes it much harder for the matcher to justify hopping onto a side road for just one probe.

Cleanup Pass: Fixing What Still Slips Through

Even with improved scoring, some unrealistic paths can still sneak through—especially in dense downtown grids or highly noisy traces.

To address this, I added a lightweight cleanup step that runs after the main matching pass. This step walks back through the matched result and looks for obvious anomalies:

extremely short detours
rapid back-and-forth transitions
isolated low-class road segments sandwiched between higher class roads

When detected, these segments can be collapsed or replaced with more plausible alternatives from the surrounding context.

This cleanup isn’t meant to “fix everything,” but it acts as a final sanity check to smooth out pathological cases that the probabilistic model occasionally produces.

Performance Impact of the Added Heuristics

After adding these heuristics, I re-ran the exact same benchmark harness used in the previous post to sanity-check whether match quality improvements came with a performance cost.

Updated Results

Total routes:   10000
Successful:     10000 (100%)
Total time:     19.82s
Throughput:     ~504.6 routes/sec

Median latency: ~136ms
P95 latency:    ~321ms
P99 latency:    ~392ms

Compare this to the old results from the last blog post:

Total routes:   10000
Successful:     10000 (100%)
Total time:     34.29s
Throughput:     ~291.6 routes/sec

Median latency: ~294ms
P95 latency:    ~913ms
P99 latency:    ~980ms

Observations

At face value, the updated matcher is noticeably faster and has significantly better tail latencies. That said, I want to be careful not to over-interpret this result.

These changes were primarily about constraining the state space — discouraging implausible transitions early rather than allowing them and “fixing” them later. It’s entirely possible that the improved performance is partially due to the Viterbi pass having fewer viable transitions to consider, rather than any intentional optimization.

It’s also possible some of this improvement is simply noise or an artifact of how the benchmark exercises the matcher. Either way, the important takeaway is not that the matcher got faster, but that it did not get meaningfully slower.

Given that these heuristics are lightweight (simple arithmetic, heading comparisons, and metadata checks), they appear to improve match quality without introducing noticeable computational overhead. For the intended use case — high-volume, short traces — that’s exactly the tradeoff I was hoping for.

Final thoughts

None of these changes are particularly complex on their own. The improvement comes from stacking multiple weak signals:

turn cost
u-turn penalties
road class awareness
distance and coverage weighting
post-processing cleanup

All these need to work together to produce reliable results. These are all heuristics in the end - need to also understand the quality of the input data. Helps to know what the input data looks like - if it fits a common pattern, then we are better suited to optimize for that versus a more general purpose use case.

Lightweight HMM Map Matching in Go

Thu, 25 Dec 2025 00:00:00 +0000

Introduction

Over the past few weeks I’ve been digging into a small, self-contained map matcher written in Go. The goal was simple: explore whether it’s possible to build a lightweight Hidden Markov Model (HMM) map matching service that doesn’t rely on external routing engines, yet still handles high concurrency and good throughput for short GPS traces.

The use case I had in mind is one where a service might need to process many short GPS traces (think under 5 minutes and only a few miles), at high volume (think on the order of hundreds of thousands per hour) and do so with minimal infrastructure fuss.

The prototype lives here: https://github.com/kuanb/gorouter

What the Router Does

You start the router like this:

go run ./cmd/router -pbf district-of-columbia-251222.osm.pbf

On launch it parses the specified OSM PBF, builds an in-memory road graph, indexes road segments with an R-tree, and exposes a simple HTTP endpoint for map matching.

Each incoming trace is matched using a straightforward HMM approach:

It finds nearby segment candidates using the spatial index.
It scores emission likelihoods based on distance.
It scores transitions using graph connectivity and simple heuristics.
It runs a Viterbi pass over the sequence to find the most likely path.

This isn’t a full routing engine (it doesn’t do traffic modeling or turn penalties, for example) but for short traces it gets the job done.

Go and Concurrency: Reasoning for Language Selection

One of the reasons this project feels “Go-ish” is that concurrency comes almost for free with the standard library. The router uses Go’s built-in HTTP server, and each request is already handled in its own goroutine by default.

Here’s the core HTTP handler:

http.HandleFunc("/match", func(w http.ResponseWriter, r *http.Request) {
    result, err := matcher.Match(r.Context(), trace)
    if err != nil {
        http.Error(w, err.Error(), http.StatusBadRequest)
        return
    }
    json.NewEncoder(w).Encode(result)
})

There’s no worker pool or thread scheduler in user code: Go’s net/http does the heavy lifting. The shared graph and spatial index are read-only after initialization, and per-request state is short-lived. That pattern maps well to workloads where requests are independent and bursts are expected.

Libraries for Spatial Indexing and Geospatial Work

One area where I had more hesitation than usual was around geospatial libraries. My familiarity with Go’s geospatial ecosystem is at this time limited, going into this project.

For spatial indexing, I used github.com/tidwall/rtree, which provides a simple in-memory R-tree implementation. That underpins the nearest-neighbor lookups used to find candidate road segments for each GPS point. I also used github.com/tidwall/geoindex, which wraps common spatial indexing patterns in a slightly higher-level API. Together, these handled the core spatial lookup needs without introducing much complexity.

For geometry primitives and distance calculations, I relied on github.com/paulmach/orb. Orb provides clean representations for points and line strings and enough geometric operations to avoid reinventing basic math, while still being easy to reason about.

For OpenStreetMap ingestion, I used github.com/qedus/osmpbf to parse PBF files and stream OSM primitives into my own graph structures.

Just thinking out loud: I was initially uneasy building this on top of libraries with only a few hundred stars. In ecosystems like Python, geospatial tooling tends to be backed by much larger and more established communities. Go’s geo ecosystem feels smaller and more fragmented, and there isn’t an obvious “standard” stack. It could also just be me being naive, though.

That said, once I read through the source of the libraries I was considering, I felt comfortable moving forward. The code is small, readable, and fairly direct. There’s very little abstraction or magic, which made it easier to reason about correctness and performance.

Tradeoffs I also wonder about: The ecosystem is clearly smaller, but it’s also a pragmatic and composable language. For this project, assembling a solution from a handful of focused building blocks ended up being a reasonable tradeoff.

Load Testing

To get a sense of performance, I wrote a small Python harness that sends concurrent requests against a locally running router and measures throughput and latency.

I ran it locally on a MacBook Pro (M2, 32 GB RAM) with a Washington, DC PBF. The test sent 10,000 total requests with about ~250 concurrent in-flight requests.

Here are the results:

Total routes:   10000
Successful:     10000 (100%)
Total time:     34.29s
Throughput:     ~291.6 routes/sec

Median latency: ~294ms
P95 latency:    ~913ms
P99 latency:    ~980ms

A few things jump out. Throughput stays close to ~300 requests per second, the median latency is under 300 ms even under load, and tail latencies sit below a second without any tuning. For a small, single-process prototype, that’s a solid baseline.

Batch Size and Concurrency Observations

I also experimented with the effect of batch size on throughput and latency. Using the same 10,000-route test set, I compared three scenarios: high concurrency with 250 in-flight requests, moderate concurrency with batch size 100, and effectively no concurrency with batch size 1.

Two interesting results stood out:

Batch Size 100

Total routes: 10000
Successful: 10000 (100%)
Total time: 32.62s
Throughput: 306.6 routes/sec

Median latency: 102.8ms
P95 latency: 494.0ms
P99 latency: 537.1ms

With a moderate batch size, throughput improved slightly over the earlier 250-concurrency test. Median latency dropped to ~103ms, although tail latency (P95/P99) remained near half a second.

Batch Size 1 (No Concurrency)

Total routes: 10000
Successful: 10000 (100%)
Total time: 47.38s
Throughput: 211.05 routes/sec

Median latency: 3.0ms
P95 latency: 4.8ms
P99 latency: 6.0ms

Processing requests sequentially drastically reduces per-request latency. Each individual match is extremely fast - single-digit milliseconds - but overall throughput suffers: the total run time increases because requests are not processed in parallel.

Implications

For a high-volume service like the one this router is targeting, moderate concurrency (e.g., batch sizes of 100–250) hits a sweet spot: high aggregate throughput while keeping most latencies under 0.5s. The results also suggest that for very small traces, the core matching algorithm itself is extremely fast; the limiting factor for throughput is mostly concurrency management and resource contention rather than the algorithm. I would need to look into how to manage concurrency in Go – potentially limiting additional requests from being processed (so some queueing mechanism).

I added a metrics health-checker to the benchmarking logic to hit a background metrics endpoint to track the following stats:

Metric	Description
goroutines	Current number of goroutines
alloc_mb	Currently allocated heap memory
sys_mb	Total memory obtained from OS
heap_objects	Number of allocated heap objects
num_gc	Number of completed GC cycles

Re-running our benchmarker with this new metrics health-checker and a “sweet-spot” concurrency of 200:

python benchmark_mapmatch.py synthetic_routes.geojsonl  --batch-size 200 --metrics-output benchmark

With this, I was able to track a few internal metrics while running the benchmarks to get a sense of memory usage, goroutine count, and garbage collection behavior. Summary results were as follows:

Server Metrics Summary
Collection duration: 31.7s
Samples collected: 26

Memory (Allocated MB):
Min: 19.48 MB
Max: 299.10 MB
Mean: 41.99 MB

Goroutines:
Min: 103
Max: 115
Mean: 105.2

General observations from the results:

Memory usage is modest. Even at peak, the router allocated ~300MB (upon the initial request, it immediately dropped down to the about the median). The average was around 42MB. This confirms that the in-memory graph and R-tree are lightweight.
Goroutine count stays predictable. Between 103–115 goroutines, the server handles concurrency without spawning excessive threads. Most of these goroutines might also be the HTTP server, worker routines, and GC activity.
Garbage collection is frequent but cheap. 204 GC cycles occurred during the ~32s benchmark, reflecting the allocation and deallocation of per-request state. The low impact on throughput and latency suggests that Go’s GC handles this workload efficiently.

Overall, these internal metrics reinforce the earlier observations: the router is lightweight, scales with concurrency, and does not impose significant memory or GC overhead under realistic load.

Back-of-the-Envelope Capacity

At roughly 292 requests per second, a single instance translates to:

~17,500 requests per minute
~1 million requests per hour

In practice, it’s safer to discount this a bit. Larger graphs, cloud overhead, and garbage collection will all eat into headroom. Even with a conservative estimate of ~10k requests per minute per instance, we can start to think about what it takes to reach very high throughput.

If the target is 250k requests per minute, then:

250,000 / 10,000 ≈ 25 instances

Add headroom for regional load variability, burstiness, and failure domains, and you’re likely in the ballpark of 30–40 routers. Note based on the above metrics these don’t need to be particularly beefy instance types.

Importantly, you wouldn’t load the entire continental U.S. graph into a single process. You’d partition regionally, allocating more capacity to dense metros and fewer resources to sparser areas.

Why This Matters

Just to recap why I am doing this versus using something like Valhalla or OSRM. Those tools are very mature and stable, but they’re also large, complex, and optimized for general routing tasks/very flexible.

If your workload mostly consists of short, independent traces as my use case does, then you do not need full route planning, and you want minimal dependencies and simple scaling. So in this case, a small Go service can be a very practical alternative.

Go’s standard library gives you concurrency, a production-ready HTTP server, and predictable performance characteristics out of the box. Combined with a focused HMM implementation and spatial indexing, that’s enough to solve this class of problems.

What’s Next

There’s more work to do here to flesh this out: real regional sharding, smarter batching, memory profiling, benchmarking on larger PBFs, and exploring batch matching APIs. It’s also quickly apparently the matching model needs tweaks to more strongly penalize u-turns to prevent erroneous in/out patterns for side roads when performing a map match on a road network.

But even in its current form, this prototype suggests that a lightweight, Go-based map matcher can handle serious volume when scoped appropriately. Not the Github repo may be updated after this blog post is published if I find more time to tinker on this.

Full stack map control

Tue, 13 Jun 2023 00:00:00 +0000

Introduction

I went to State of the Map US this past weekend in Richmond, VA and learned more about Protomaps which makes self-serving your own static map tiles dead simple. This is the area of the web mapping ecosystem I am furthest away from, so I often rely on 3rd party vendors (as do most), such as Mapbox or Maptiler. Protomaps makes it possible to control this component and generate tiles from a PBF I own/manipulated and serve it all from, for example, the same Github page that I might be hosting my simple site under.

The Protomaps website contains sufficient document, I will just make some notes about gotchas that I hit when working on this to get up and running under my personal website kuanbutts.com. The reference repository for this work is on Github here.

Generate PMTiles

Protomaps uses a vector tile format called PMTiles. It has nifty features that allows the API to use HTTP range requests to query a single file containg the compressed basemap information.

Simple PMTiles for a custom area can be generated with this offered PMTiles service from Protomaps. Working with a Shapefile or some other custom data source? PM allows for export from Tippecanoe to PMTiles.

For me, I downloaded a bounding box around Oakland from the simple PM service and the resulting file was about 15mb. PM will extend the map rendering functionality to support HTTP range requests thereby enabling a direct query from the map rendering engine to the single hosted PMTile.

Protomaps also provides a tile inspector that will load the exported PMTiles into a viewport that will help to expose the various layer and contents that have been packaged up. If further file size efficiency is desired; this is a great tool with which to additionally trim down the pacakged OSM data to just what is needed for a specific use case.

Hosting locally for development

Once you have your PMTile file, you can start a simple SPA React app with the create-react-app command. I then chose to place the file within the public/ directory so that published builds would roll up and deliver the file to Github published static sites. You can see the file there here. This also prevents gotchas where the file is requested from the main/ branch but your personal site has a custom domain, which will cause a CORS cross-domain request headache.

Once held in a steady location, use your desired method to serve the file over local host (for ex: python -m http.server or with JS: http-server . -p 8020 --cors).

Rendering the map

Once a simple app has been created, a Map component can be introduced to the main App.js script. The entirety of the map-from-local-Github-pages-files concept will be encapsulated in that new Map component.

First, a conditional for development vs. deploy needs to be set so that when published, we can read from appropriate endpoint:

const basePmUrl = process.env.NODE_ENV === 'development' ? 'http://127.0.0.1:8080/public' : 'https://kuanbutts.com/pm-maps-oak';

Next, we will create a new instance of a MapLibre map instance. However, before we do that, there is a configuration setting that needs to be set:

import { Protocol } from 'pmtiles';
import layers from 'protomaps-themes-base';

let protocol = new Protocol();
maplibregl.addProtocol("pmtiles", protocol.tile);

This added protocol will allow Protomaps to query with the aforementioned range requests. Once set, all that is left to do is to create a new MapLibre map instance with the requisite style settings for Protomaps + MapLibre to use to query from the static file (instead of a traditional tiling service):

new maplibregl.Map({
  container: mapContainer.current,
  style: {
    version: 8,
    glyphs:'https://cdn.protomaps.com/fonts/pbf/{fontstack}/{range}.pbf',
    sources: {
      protomaps: {
            type: 'vector',
            url: `pmtiles://${basePmUrl}/oakland.pmtiles`,
            attribution: '<a href="https://protomaps.com">Protomaps</a> © <a href="https://openstreetmap.org">OpenStreetMap</a>'
        }
    },
    layers: layers('protomaps', 'light')
  },
  center: [lng, lat],
  zoom: zoom,
  maxBounds: [[-122.36159, 37.71505], [-122.12976, 37.88092]]
});

Conclusion

That’s about it. The simple web site is up on Github here. The webapp queries the PMTiles raw file, which is exposed via the public/ bucket in the final custom domain/path endpoint the same as the rest of the site JS, static files. With this pattern, I am able to publish a simple website without any external resource requirements outside what is delivered and available from the single site.

Fast de/serialization with numerical arrays

Thu, 06 Apr 2023 00:00:00 +0000

Introduction

This post demonstrates two tasks. First, it shows how slow string parsing is with Python and why more efficient serialization patterns are necessary for packing and unpacking an array of numerical values. Secondly, it demonstrates two methods - one that works within a “contained” Python-specific ecosystem and one that is more flexible and language and package agnostic.

The impetus for this evaluation was the need to serialize an array of numerical values to be passed through a Redis cache and read by a subsequent Python microservice.

Python array serialization and unpacking

Imagine a condition where you need to pass through an array of values from one service to another. For example, you need to xadd some value scores to a Redis cache which is represented as an array of values: [1.1, 2.4, 12.2 ... 2.3]. Attempting to write a list to a Redis cache will fail: redis.exceptions.DataError: Invalid input of type: 'list'. Convert to a bytes, string, int or float first.. Instead, it will be necessary to serialize and deserialize it on the comsuming service’s end.

We can first assume some array a defined as:

a = [round(random.random() * 100, 2) for _ in range(10)]

A naive serialization can be to just convert this list to a string. For example: ",".join(map(str, a)).

However, Python is quite slow at parsing strings and converting them back to numerical types. We can write a little test of this to explore the time cost of this conversion:

import random

data = [[round(random.random() * 100, 2) for _ in range(100)] for _ in range(10_000)]
data_serialized = [",".join(map(str, a)) for a in data]

times = []
for i in range(100):
    start = time.time()
    res = [list(map(float, n.split(","))) for n in data_serialized]
    stop = time.time()
    times.append(round(stop-start, 3))
    
np.mean(times).round(3), np.percentile(times, 0.5).round(3), np.percentile(times, 0.9).round(3)
# (0.333, 0.302, 0.303)

This will demonstrate that it takes about 0.3 seconds to parse a typical set of arrays that we’ve generated. However, when dealing with 100s of thousands of these array, this performance becomes problematic within a larger pipeline that is expecting all these values to be ingested “quickly” (e.g. the entire half million arrays processed within a second or two).

Python array serialization optimization with numpy

numpy allows for an out-of-the box optimization to address this by allowing arrays of numbers to be serialized with an easy to/from pattern. A given array can be serialized with the tobytes() method: np.array([1.1,2.2,3.3]).tobytes(). It can then be read back with frombuffer such that:

raw = [1.1,2.2,3.3]
a = np.array(raw).tobytes()
parsed = np.frombuffer(a)
assert parsed.tolist() == raw  # true

We can then redesign our test from earlier but replace the serialization and deserialiation pattern with the numpy library’s utility:

import random

data = [[round(random.random() * 100, 2) for _ in range(100)] for _ in range(10_000)]
data_serialized = [np.array(a).tobytes() for a in data]

times = []
for i in range(100):
    start = time.time()
    res = [np.frombuffer(a) for a in data_serialized]
    stop = time.time()
    times.append(round(stop-start, 3))
    
np.mean(times).round(3), np.percentile(times, 0.5).round(3), np.percentile(times, 0.9).round(3)
# (0.009, 0.008, 0.008)

We can of course see major improvements. We have gone from 0.3 seconds per 10k to 0.008 seconds or 8 ms. This acheives about a 35x speed up.

However, with this method there is a downside in that both the service producing the binary and the service consuming the binary need to have Python and numpy available. What is the producing service is instead a NodeJS service for example?

Base64 encoded binaries

Imagine a condition where the service writing new entries to is a NodeJS service. A Python service then reads from the Redis cache. In order to address the deserialization performance issues while also avoiding reliance on convenience utilities like tobytes in numpy that tie us to that ecosystem, we can create the binaries ourself and write the encoded binaries to Redis instead.

We can utilize built-in libraries in NodeJS (Buffer) to create a binary representation of the list, and then convert it to a string using base64 encoding. Redis can store the resulting string as a value associated with a key, which can then be retrieved in Python and deserialized back into a list of floats using the base64 and struct modules.

function listAsBinary(arrNums, size) {
    // generate binary
    const b = Buffer.alloc(arrNums.length * size);

    for (let i = 0; i < arrNums.length; i++) {
        // write number to each paired slot
        b.writeFloatLE(arrNums[i], i * size);
    }

    // encode
    return b.toString('base64');
}

Once written to Redis, the Python step can, instead from using numpy.frombuffer, deserialize the list using Python’s struct library:

def _deserialize_arr(str_arr: str, size: int) -> Tuple[float]:
    decoded = base64.b64decode(str_arr)
    l = len(decoded) // size
    return struct.unpack(f"<{l}f", decoded)

First, the base64-encoded string is decoded. Next, the entries for each slot are accessed via the unpack method in struct to generate an array of numerical values assocaited with each entry.

Performance results should be broadly in line with numpy (with numpy often performing slightly better due to various optimizations). However, the order of magnitude of completion time is in line with numpy and addresses the severe performance costs of string conversion.

Simultaneously explode multiple array cells in SQL

Mon, 28 Nov 2022 00:00:00 +0000

Introduction

The purpose of this post is to document the pattern for utilizing the UNNEST pattern for multiple arrays. UNNEST can be useful for “exploding” a row with an array to multiple rows (where the row count is equal to the number of values in each array), each paired with the other desired information from the original row adjacent to the array. However, it is not immediately clear that the same can be performed with multiple arrays.

In fact, documentation may lead one to think that the zip method would be the appropriate pattern here:

SELECT zip(ARRAY[1, 2], ARRAY['1b', null, '3b']); -- [ROW(1, '1b'), ROW(2, null), ROW(null, '3b')]

In fact, it is not. Instead, UNNEST can take multiple arrays and transform the results into multiple exploded columns.

Example

Imagine the following case, where there are 3 rows of data desired to be “exploded” alongside the id column:

select
    1 as ref_id,
    array['a', 'b', 'c'] as a1,
    array['d', 'e', 'f'] as a2,
    array['g', 'h', 'i'] as a3

The dataframe for the above selection looks like:

#   ref_id  a1          a2          a3
1   1       [a, b, c]   [d, e, f]   [g, h, i]

The UNNEST functin can be applied here to explode all 3 columns in fact, at the same time:

with base as (
    select
        1 as ref_id,
        array['a', 'b', 'c'] as a1,
        array['d', 'e', 'f'] as a2,
        array['g', 'h', 'i'] as a3
)

cross join unnest(
    a1, a2, a3
) as t(c1, c2, c3)

The resulting dataframe looks like:

#   ref_id  c1   c2   c3
 1       a    d    g
 1       b    e    h
 1       c    f    i

This pattern can be used to explode and pair any number of rolled-up array cells against their adjacent desired column values.

Trino/Presto spherical distance capabilities

Thu, 10 Nov 2022 00:00:00 +0000

Introduction

AWS has been incrementally releasing some geospatial functionality on Athena over the past few years. Athena engine version 2 released a series of major quality of life improvements (see blog post) that allowed for the assembly of geospatial primitive spatial types.

With version 3, new operators allow for more advanced spatial operations to be performed and expressed just through Athena’s SQL interface (rather than, say, needing to spin up a Spark stack and run user-defined functions over the coordinate data).

In this blog post, I will demonstrate a quick example of using these features to calculate attributes from more “complex” spatial types. The Trino documentation already describes how to use a to_spherical_geography to calculate great circle distance between two points cast as ST_Point() objects:

ST_Distance(to_spherical_geography(ST_Point(-71.0882, 42.3607)), to_spherical_geography(ST_Point(-74.1197, 40.6976)))

Example length calculation

Let’s say your data is stored in the following format with a coordinate array representing the path of a line. If you want to calculate, say, the length of this linestring, you can do so by building up from the sum of the pairwise coordinates using the same pattern of ST_Distance() shown in the Trino documentation sampled above.

First, the start data:

select '[[130.266523,33.317762],[130.265568,33.317536],[130.263366,33.317021],[130.262584,33.316808],[130.261858,33.316611]]' as coords

This data can then be parsed as a JSON string:

select cast(json_parse(coords) as array(array(double))) as coords

From this point, we can use this (extremely handy) to_spherical_geometry method to recast each coordinate as a point on a globe, which will allow for spherical distance calculation (as opposed to Euclidean distance):

transform(coords, x -> to_spherical_geography(ST_Point(x[1], x[2]))) as points

Now that we have an array of points that are in spherical projection, we need to pair them with their predecessor to enable a distance calculation:

select
    array [element_at(points, 1)] || points as points_fr,
    points || array [element_at(points, -1)] as points_to

Distances can now be defined between each pairing, once zipped together. For each pair, a distance can be measured.

select
    reduce(
        zip_with(points_fr, points_to,
            (x, y) -> ST_Distance(x, y)
        ),
        0,
        (s, x) -> s + x,
        s -> s
    ) as dist_meters
from paired

The final step will output, for that single example input, a column dist_meters with a value of 452.05113745459886 meters.

Conclusion

Thanks to the ability to project as a spherical geography, distance measures can now be expressed directly in Athena SQL queries. Wrapping together the above steps into a single defined query outputting the results described above can look like this:

with base as (
    select '[[130.266523,33.317762],[130.265568,33.317536],[130.263366,33.317021],[130.262584,33.316808],[130.261858,33.316611]]' as coords
),
parsed_base as (
    select cast(json_parse(coords) as array(array(double))) as coords
    from base
),
as_geoms as (
    select
        transform(coords, x -> to_spherical_geography(ST_Point(x[1], x[2]))) as points
    from parsed_base
),
paired as (
    select
        array [element_at(points, 1)] || points as points_fr,
        points || array [element_at(points, -1)] as points_to
    from as_geoms
),
distances as (
    select
        reduce(
            zip_with(points_fr, points_to,
                (x, y) -> ST_Distance(x, y)
            ),
            0,
            (s, x) -> s + x,
            s -> s
        ) as dist_meters
    from paired
)

select * from distances

Running Selenium on AWS Lambda

Thu, 27 Oct 2022 00:00:00 +0000

Introduction

About a year and a half ago or so, AWS announced support for custom Lambda images. This unlocks a number of new advantages - namely the ability to create images that have complex install requiremnents prior to runtime. A perfect example of this is running Selenium on a Lambda to screenshot a website in-browser. One can quickly imagine the use cases (and related conveniences) of a Lambda-based Selenium screenshotting tool. In my case, I sought to take multiple screenshots of a mapping tool at multiple geographic locales every N minutes in perpetuity for QA purposes.

Challenges

While AWS suggests that defining a local image and running a container to test your logic locally is straightforward (as in this blog post), it’s not in practice. In my case, I was able to build an image from a Dockerfile with Selenium and Chrome and, while it would run fine locally, it would fail to either initialize the chromedriver or would have the browser itself crash when running on AWS Lambda infrastructure.

Lesons learned

Two key lessons I learned from this effort:

Chrome running headless simply does not appear to work at this time on Lambda - always use Chromium. Chrome attempts to initialize user accounts and profiles which cannot be created or written to as the AWS Lambda file system is read only. This creates a series of cascading issues (I suspect) that leads Chrome to close unexpectedly / in an unhandled manner. Thus, chromedriver is unable to initialize successfully and Selenium exits early without being able to actually get the target website.
Installing the Chrome or Chromium browser via wget or curl versus apt-get seems to cause issues with how the binary is stored and made available in PATH. Even when the location of the browser binary was specified, there remained issues with browser initialization or getting the chromedriver to play nice with the browser. Ultimately, installing via apt-get circumvented these issues and resulted in a clean install and, in conjunction with 1 above, allowed successful headless browser operation within the Lambda infrastructure.

In both of the above cases, the Docker container ran fine with the AWS Runtime Interface Emulator locally - I was able to simulate Lambda invocations and they would complete successfully within the container. In such cases, I would then deploy to AWS infrastructure only to experience random chromedriver initialization failures during invocation. This was a deeply frustrating and time-consuming process.

Selenium initialization

The settings I used for Lambda use of Selenium with Chromium via the options class are as shown:

from selenium.webdriver.chrome.options import Options

options = Options()
options.add_argument("window-size=1400,1200")
options.add_argument("--headless")

# other parameters for running headless in Lambda I used
options.add_argument("--no-sandbox")
options.add_argument("--disable-dev-shm-usage")
options.add_argument("--disable-extensions")
options.add_argument("--disable-gpu")
options.add_argument("--disable-dev-tools")
options.add_argument("--no-zygote")
options.add_argument("--single-process")
options.add_argument("--user-data-dir=/tmp/chrome-user-data")
options.add_argument("--remote-debugging-port=9222")

# INFO: update if binary location needs to be set
# options.binary_location = "/other/location"

Note the final line in the above code block. The binary location setting is what could be adjusted if one were to try and install the browser and driver manually as described above. However, I remained unsuccessful at this and ultimately went with apt-get to install the driver and browser.

Also note that the user-data-dir parameter was set to the tmp directory. Because Lambda has a read only file system, we need to ensure that any write activity is scoped specifically to the tmp directory which is the sole location that allows intermediate writes during a Lambda’s runtime (not preserved). Also keep this in mind when saving your screen captures to local during a Lambda invocation. Saved images can then be moved from tmp to S3 for future retrieval or use.

Initialization of the Selenium WebDriver occured by incorporating those setting options alongside the driver location:

# install location as a result of apt-get install
driver_path = "/usr/lib/chromium-browser/chromedriver"

# return this initialized driver
webdriver.Chrome(
    chrome_options=options,
    executable_path=driver_path,
)

Dockerfile

Without further ado, here’s the Dockerfile that I found successfully installed Selenium, Chromium, and the related Chromedriver:

FROM ubuntu:18.04

SHELL ["/bin/bash", "-c"]

RUN apt update && apt-get install -y software-properties-common
RUN apt update && add-apt-repository ppa:deadsnakes/ppa
RUN apt update && apt-get install -y \
    make \
    curl \
    python3.7 \
    python3.7-distutils \
    g++ \
    cmake \
    unzip \
    libcurl4-openssl-dev \
    git
RUN apt-get update && apt-get install -y \
    fonts-liberation libappindicator3-1 libasound2 libatk-bridge2.0-0 \
    libnspr4 libnss3 lsb-release xdg-utils libxss1 libdbus-glib-1-2 \
    autoconf cmake curl libtool unzip wget \
    xvfb


# install chromedriver and google-chrome

RUN apt update && apt-get install -y chromium-browser chromium-chromedriver


# install amazon RIE for lambda testing

RUN curl -L https://github.com/aws/aws-lambda-runtime-interface-emulator/releases/latest/download/aws-lambda-rie -o aws-lambda-rie-x86_64 && \
    mv aws-lambda-rie-x86_64 /usr/local/bin/aws-lambda-rie && \
    chmod +x /usr/local/bin/aws-lambda-rie


# install pip and set up virtualenv

RUN curl -o /tmp/get_pip.py https://bootstrap.pypa.io/get-pip.py && \
    python3.7 /tmp/get_pip.py && \
    python3.7 -m pip install virtualenv


# generate working directory locations

RUN mkdir -p /code
WORKDIR /code
ENV PATH="${PATH}:/code:/usr/lib"

COPY requirements.txt /code/requirements.txt
COPY entry_script.sh /code/entry_script.sh
COPY lib/ /code/lib/

RUN make install

ENTRYPOINT [ "sh", "/code/entry_script.sh" ]

The Makefile install method simply installs the available requirements and creates a virtual environment to operate within:

venv:
    virtualenv --python=python3.7 venv

install: venv
    source venv/bin/activate &&\
    pip install -r requirements.txt

The entry_script.sh similarly is adapted the suggested pattern from AWS Lambda’s docs which allows for a conditional RIE entrance that runs in “local” mode if certain OS environment variables are not present, otherwise it executes with the expectation that it is in AWS Lambda infrastructure:

#!/bin/sh
if [ -z "${AWS_LAMBDA_RUNTIME_API}" ]; then
  exec /usr/local/bin/aws-lambda-rie /code/venv/bin/python -m awslambdaric lib.snapshot_lambdas.handler
else
  exec /code/venv/bin/python -m awslambdaric lib.snapshot_lambdas.handler
fi

At this point, you should be able to create a .py file (in the above case, snapshot_lambdas) that contains a handler for receiving Lambda invocations (or simulated ones in local run cases).

Good luck screen capturing on Lambda!