Reducing double spend latency from 40 ms to < 1 ms on privacy proxy

When a "big rock" turned out to be a small packet

Cloudflare's privacy proxy infrastructure, which powers services like Apple's Private Relay and Microsoft's Edge Secure Network, relies on Privacy Pass tokens for authentication. Before a user's request is allowed through, our proxy must verify the token hasn't already been spent—a "double-spend" check. These proxies handle millions of requests per second, so that check must be fast. Our traces and metrics revealed median latencies around 40 ms for these checks, which was far longer than expected. The backing data store (memcached, accessed via mcrouter) typically responds in under 1 ms. We needed to find the bottleneck.

Systematic problem solving

We approached the investigation methodically, using data to test and reject hypotheses about the code's behavior. The double-spend check logic has two high-level steps: get a usable connection, then send a memcached get command on it. Getting a connection involves sending a memcached version command as a health check, and either acquiring the existing connection or establishing a new one.

Our first theory—that the health check itself was slow—was quickly disproven. The version command had median latency under 1 ms.

Our second theory concerned connection pool limits. Each server had a pool limit of 20 connections. Given a server processing 5,000 requests per second with a 45 ms request duration, Little's Law suggests an average of 225 in-flight requests. With a pool limit of 20, the other 205 requests would be waiting for a connection. However, even servers with as few as 20 requests per second showed the same ~40 ms latency, which disproved this theory.

A subtle interaction

With our first two theories rejected, we consulted an LLM for ideas. One suggestion stood out: check if TCP_NODELAY was set in our code. If not, Nagle's algorithm would be active. Nagle's algorithm alone isn't problematic, but when it interacts with delayed ACKs, significant latency can emerge.

Nagle's algorithm batches small outgoing messages into a single larger one, but only allows one small message to be sent before waiting for an ACK. Delayed ACKs, on the other hand, postpone sending an ACK for up to 40 ms hoping to piggyback it on response data. When a client sends a partial command consisting of several small writes, Nagle's algorithm buffers all but the first write. The server receives an incomplete command, cannot process it, and its delayed ACK timer starts. The client waits for that ACK before Nagle's algorithm permits sending the rest of the buffered data. When the 40 ms delayed ACK timer finally fires, the client receives it, flushes the remaining command, and the server responds immediately.

This is exactly what our Wireshark captures showed. We were sending a memcached get command as three separate small TCP messages: the "get " prefix, the token, and the trailing \r\n. Our code, which used the memcache-async crate, wrote these to the TcpStream individually, and each write_all call sent its own message. The 40 ms number was traced to our Linux kernel's minimum delayed ACK timer, defined as TCP_DELACK_MIN.

The fix: coalesce the writes

The solution was straightforward once we identified the root cause: instead of writing the command parts directly to the TcpStream, we wrapped it in a BufWriter<TcpStream>. This buffers the small writes in user-space memory, and a single flush sends the entire memcached command as one TCP message.

Wireshark confirmed the cleaner result: one message sent, one response received, no waiting. After deploying the fix, median double-spend check latencies dropped to the expected sub-millisecond range across all our proxies.

This investigation demonstrated the importance of combining observability data with a systematic, hypothesis-driven approach. The root cause wasn't in network infrastructure or connection handling, but in how a third-party dependency's API was used. Every millisecond saved on this critical path contributes to a faster, more private browsing experience, and we're continuing to look for similar opportunities.