AIMD Queue Server

​

Overview

Chalk’s AIMD Queue Server is a pull-based query processing system that decouples request ingestion from query execution. Instead of each query server directly accepting gRPC traffic, a lightweight Rust frontend receives requests, enqueues them into a Redis Stream, and query server pods consume work at a rate governed by an AIMD concurrency controller.

The goal is straightforward: maximize throughput given a particular latency budget. The AIMD controller continuously adjusts how many queries each consumer processes concurrently. When p99 latency is well below the SLO, concurrency increases. When p99 latency exceeds the SLO, concurrency drops. The result is a system that self-tunes to the capacity of the underlying hardware without manual concurrency tuning.

​

Architecture

Requests flow through three stages: the Rust frontend, a Redis Stream, and the C++ consumer running inside each query server pod.

                          ┌──────────────────────┐
                          │     gRPC Clients      │
                          └──────────┬───────────┘
                                     │
                          ┌──────────▼───────────┐
                          │   AIMD Queue Server   │
                          │       (Rust)          │
                          │                       │
                          │  Receives gRPC RPCs,  │
                          │  encodes to protobuf, │
                          │  XADD → Redis Stream  │
                          └──────────┬───────────┘
                                     │ XADD
                          ┌──────────▼───────────┐
                          │     Redis Stream      │
                          │  (consumer group:     │
                          │   "query_servers")    │
                          └───┬──────┬──────┬────┘
                  XREADGROUP  │      │      │  XREADGROUP
                 ┌────────────┘      │      └────────────┐
                 │                   │                    │
      ┌──────────▼──────┐ ┌─────────▼───────┐ ┌─────────▼───────┐
      │  Query Server 0 │ │  Query Server 1 │ │  Query Server N │
      │  (C++ consumer) │ │  (C++ consumer) │ │  (C++ consumer) │
      │                 │ │                 │ │                 │
      │  AIMD controls  │ │  AIMD controls  │ │  AIMD controls  │
      │  concurrency    │ │  concurrency    │ │  concurrency    │
      └────────┬────────┘ └────────┬────────┘ └────────┬────────┘
               │ SET                │ SET                │ SET
               └───────────┐       │       ┌────────────┘
                           │       │       │
                  ┌────────▼───────▼───────▼────────┐
                  │           Redis (results)        │
                  │   pull_query_result:{query_id}   │
                  └────────────────┬─────────────────┘
                                   │ GET (poll)
                          ┌────────▼─────────────┐
                          │   AIMD Queue Server   │
                          │  polls for result,    │
                          │  returns gRPC response│
                          └──────────────────────┘

1. Ingestion. The Rust AIMD Queue Server implements the full QueryService gRPC interface. When a request arrives (e.g. OnlineQuery, OnlineQueryBulk), the server serializes it to protobuf, generates a unique query_id, and publishes the message to a Redis Stream via XADD. The message includes the serialized request, the query method name, and forwarded metadata (environment, deployment, project, team IDs, and OpenTelemetry trace headers).

2. Distribution. Query server pods form a Redis consumer group. Each pod calls XREADGROUP to pull messages in batches. Redis guarantees that each message is delivered to exactly one consumer within the group, so work is automatically load-balanced across pods. If a consumer crashes, unacknowledged messages are reclaimed by other consumers after a configurable idle timeout.

3. Execution. When a query server pod receives a message, it first attempts to acquire an AIMD concurrency slot. If the slot is acquired, the query executes. On completion, the result (a status byte + serialized protobuf) is written to a Redis key at pull_query_result:{query_id} with a TTL. The Rust frontend polls this key and returns the response to the original gRPC caller.

​

AIMD concurrency control

Each query server pod runs an independent AIMD controller that governs how many queries it will process concurrently. The controller maintains a sliding window of recent query latencies and adjusts the concurrency window on a periodic evaluation interval.

The algorithm:

• Additive increase: If the observed p99 latency is below p99_headroom × latency_slo and there was demand pressure (i.e., a try_acquire call was rejected), the window increases by alpha.
• Multiplicative decrease: If the observed p99 latency exceeds latency_slo, the window is multiplied by beta (typically 0.7).
• Fast circuit breaker: If any single query takes longer than fast_decrease_multiplier × latency_slo, the window is immediately multiplied by beta, without waiting for the next evaluation interval.

The demand pressure requirement prevents the window from growing when there is no backlog — concurrency only increases when the queue has more work than the current window can handle.

​

AIMD parameters

These parameters are configured on the gRPC query servers that consume from the queue:

​

Redis Streams consumer configuration

The consumer group on each query server pod is configured with:

​

Failure modes

​

Queries exceeding the latency budget

When individual queries consistently take longer than latency_slo, the AIMD controller will continuously decrease the concurrency window. In the extreme case, the window drops to min_concurrency (default 1), meaning the pod processes queries one at a time.

This is by design — the controller prioritizes latency over throughput. However, if queries are inherently slower than the configured SLO (e.g. the SLO is 100ms but the query itself takes 200ms at minimum), the system will operate at minimum concurrency permanently. In this situation you should either increase the latency_slo to a realistic target, or optimize the underlying query to fit within the budget.

The fast circuit breaker provides an additional safeguard: if a single query takes longer than fast_decrease_multiplier × latency_slo (default 3x), the controller immediately reduces concurrency without waiting for the next evaluation interval.

​

Queue overload

When the rate of incoming queries exceeds the aggregate processing capacity of all consumer pods, the Redis Stream will grow. The Rust frontend polls for each query’s result with a configurable timeout (CHALK_AIMD_QS_RESULT_TIMEOUT_MS, default 30 seconds). If the result is not written before this timeout, the frontend returns a gRPC DEADLINE_EXCEEDED error to the caller.

When the consumer pods are at capacity and the AIMD controllers have all been driven down to their minimum concurrency windows, the consumers will nack messages they cannot accept, causing Redis to redeliver them. At this point, the system is saturated and callers will see elevated latency and timeout errors.

To mitigate queue overload:

• Scale the consumer pool. Add more query server replicas so the consumer group has more aggregate capacity.
• Lower the batch size. Smaller batch_size values reduce per-pod queuing depth.
• Set max_concurrency appropriately. This caps each pod’s contribution. If pods are resource-constrained, a lower ceiling prevents them from accepting more work than they can handle.

​

Consumer failures

If a query server pod crashes or becomes unresponsive, its pending messages in the consumer group will go unacknowledged. After claim_timeout (default 60 seconds), other consumers in the group will reclaim these messages via XCLAIM. If a message exceeds max_delivery_count delivery attempts across all consumers, it is routed to a dead letter queue for inspection.

​

Queue server configuration

The Rust AIMD Queue Server is configured via configuration variables:

​

Metrics

The AIMD Queue Server and its consumers publish metrics to Datadog:

Queue server (Rust):

• aimd_queueserver.open_connections — gauge of in-flight requests, tagged by method.
• aimd_queueserver.request_duration_ms — end-to-end latency distribution, tagged by method, status, and reason.
• aimd_queueserver.requests_total — request count, tagged by method, status, and reason (ok, backpressure, enqueue_failed, timeout, result_error, decode_error).
• aimd_queueserver.redis.used_memory_bytes / used_memory_rss_bytes / maxmemory_bytes / available_memory_bytes — Redis memory usage gauges polled from INFO memory.
• aimd_queueserver.redis.cpu_sys_seconds_total / cpu_user_seconds_total — cumulative Redis CPU seconds polled from INFO cpu.
• aimd_queueserver.redis.cpu_usage_ratio — Redis CPU seconds consumed per wall-clock second since the previous poll (~1.0 == one fully-used core).

Consumer (C++ AIMD controller):

• chalk.engine.pull_query.aimd.concurrency — current concurrency window size.
• chalk.engine.pull_query.aimd.p99_latency — observed p99 latency from the sliding window.
• chalk.engine.pull_query.in_flight — number of queries currently being processed.
• chalk.engine.pull_query.aimd.adjustments — counter of window adjustments, tagged by direction (increase, decrease, fast_decrease).
• chalk.engine.pull_query.completed — counter of completed queries, tagged by status (success, rejected, transient_error, permanent_error).