Gateway-Level Query Queue for Trino Gateway

[jalpan-randeri]

Summary

Add support for a gateway-level query queue in Trino Gateway to manage and control the flow of incoming queries before routing them to backend clusters.

Motivation

Currently, Trino Gateway routes queries directly to clusters based on routing logic and resource groups. In high-traffic scenarios, this can lead to backend overload, uneven resource utilization, or dropped queries. A gateway-level queue would allow for better traffic management, prioritization, and smoother handling of bursts.

Proposed Solution

Implement a configurable queue at the gateway level to hold incoming queries.

• Support queue policies (FIFO, priority, max queue size, etc.).
• Integrate with existing routing and resource group logic.
• Provide metrics and monitoring for queue status.
• Expose queue configuration and status via API and/or UI.

Benefits

• Prevent backend overload by controlling query admission rate.
• Enable prioritization and fairness across users or workloads.
• Improve reliability and user experience during peak loads.
• Ability to move idempotent queries across clusters
• Automated query retries across clusters
• Safe rollout out new version/ shadow testing

While we relying solely on backend cluster-level queuing (less visibility/control at gateway). We are running into very brittle
Implementing custom throttling logic outside the gateway.

I am willing to create detailed specifications and participate in design reviews to help move this feature forward. Please let me know how best to proceed with further review and collaboration

[xkrogen]

cc @vishalya I think you said you were exploring something similar?

[xkrogen]

@jalpan-randeri re:

Integrate with existing routing and resource group logic.

IMO -- the admission control logic should be pluggable. In our case, we want to integrate with external rate limiting mechanisms. Other organizations may have their own logic and/or want to use something similar to Trino's resource groups, though I suspect an exact re-implementation of resource groups may not work well at the Gateway layer -- and will be a substantial undertaking regardless.

Point being, let's leave the actual admission control logic out of scope of this issue and just focus on the framework necessary to enforce the admission control policy and maintain a queue.

[oneonestar]

To provide scalability and high availability, multiple gateway instances are typically deployed. We could store the queue locally in each gateway and use external rate-limiting mechanisms to coordinate consumption across multiple gateways, or we could store the queue in a database to create a centralized queue. Both approaches have pros and cons and require thoughtful discussion.

I am willing to create detailed specifications and participate in design reviews to help move this feature forward. Please let me know how best to proceed with further review and collaboration.

We can start the discussion here and see how it progresses.

[xkrogen]

store the queue in a database to create a centralized queue

IMO, a centralized queue is a hard requirement (and the crux of this functionality). If we store separate queues per GW instance, we really haven't solved the problem -- the core problem that needs solving is that multiple queues don't provide a consistent/predictable load balancing experience, and multiple queues at the GW layer (one per instance) is not really any better than multiple queues at the Trino layer (one per cluster).

The only two cons I can see with a centralized queue are complexity and performance overhead (though please let me know if you have other thoughts @oneonestar). My suspicion is that the performance won't be an issue, given we already make plenty of DB calls on a per-query basis (write query history, look up backend status, etc). If we do find that performance is an issue, we could still maintain a centralized queue while reducing performance overhead by using techniques like batching (e.g. wait for up to N queries or X seconds, submit them all to the central queue, fetch M queries from the queue to submit). Regarding complexity, I think it is a necessary evil for this feature.

[oneonestar]

Simplified Query Gateway Design with External Rate Limiting

Design:
Queries are submitted to different gateways. Each gateway holds and queues the incoming queries, awaiting a "go signal" before submission to a Trino cluster. The HTTP connection for the client request is held open until the query is sent to Trino.

Rate Limiting:
The rate limiting logic is offloaded to an external system (e.g., Redis or a custom service). This external system is responsible for providing the "go signals" to ensure a consistent and predictable load balancing experience (e.g., per-user rate limits). It can also gather real-time resource usage data from multiple Trino clusters to inform its decision-making.

Client Perspective:
From the client's viewpoint, this system functions as a centralized queue.

Handling Gateway Failures:
Gateway crashes do not require special handling. Since the initial request has not yet received a response, the client will lose the connection and can simply retry the query.

Concern:
Clients may have difficulty determining the state of their request—whether the query is queued, the gateway has crashed, or a general network issue has occurred.
The implementation burden is shifted to the external system, which itself is tightly coupled to gateway and Trino.

---

An alternative approach, we implement the above rate limit logic in the gateway. We could even try to handle gateway crashes by store the queries into database, provide async query submission, auto retry on failed queries, etc. But the complexity could grow exponentially and we might need to modify Trino Client/Server in order to achieve it.

I’m not worried about performance ATM.

[jalpan-randeri]

Thanks for the discussion around the current queuing approach. The in-memory + DB-backed design is attractive for its simplicity and works reasonably well at low to moderate scale. However, it breaks down under sustained or bursty high load.

Key concerns:

• Operational risk: In-memory queues require sticky sessions, complicating failover and rolling restarts.
• Scalability limits: Transient in-memory state risks OOMs under peak load and constrains horizontal scaling.
• Database contention: Using a general-purpose DB for high-churn queue operations (INSERT / SELECT … FOR UPDATE) quickly becomes a bottleneck due to lock contention, I/O pressure, and added latency.
• Feature ceiling: Local queue state makes it hard to support enterprise needs like centralized visibility, cross-cluster retries, and coordinated failover.

To achieve high reliability and scalability at larger scale, I believe we need a pluggable architecture with a clear growth path.

One possible design (for large deployments):

• Stateless gateways that durably enqueue requests to Kafka
• External rate-limiting / admission service that issues “go signals” based on real-time Trino cluster capacity
• Async client API (202 Accepted + reservation ID + status polling) to avoid long-held connections

This adds operational complexity, but provides a proven path for enterprise-scale, multi-cluster deployments while still allowing a simpler default for smaller setups. Happy to iterate on this or help define a clean abstraction that supports both models.

[oneonestar]

It looks like a more complete solution is preferable, and I agree that it will be more scalable and future-proof. Let's move in that direction.

We'd like to avoid HTTP long polling so that gateways can remain stateless. However, the current Trino client protocol doesn't support async operations. Clients expect a JSON response containing a QueryID after submitting a query. We can't provide a QueryID without actually submitting the query to Trino, but we don't want to submit the query yet because it's being queued at the gateway.

One approach is to propose a change to the protocol and convince Trino maintainers to accept it. This would require a document explaining the motivation and design for adding async support to the protocol, while maintaining backward compatibility.

Alternatively, we could take a "hacky" approach by generating a QueryID in the gateway. We could emulate the protocol so that the client believes the query has been submitted and queued by a Trino coordinator, when in reality, it's being queued at the gateway. The gateway would then be responsible for mapping the client’s request to the actual request sent to Trino, as well as for handling all additional query state.

Client <-- (QueryID created by gateway) --> Gateway <-- (QueryID created by Trino) --> Trino

[xkrogen]

Database contention: Using a general-purpose DB for high-churn queue operations (INSERT / SELECT … FOR UPDATE) quickly becomes a bottleneck due to lock contention, I/O pressure, and added latency.

I disagree with this pretty strongly. At least at all scales of Trino GW deployment I am aware of, a traditional RDBMS (MySQL/Postgres/etc) is more than capable of handling the throughput. Many thousands of writes per second is common on such systems. Of course the storage backend itself should be pluggable, and if/when installations do grow beyond this scalability limitation they can implement storage schemes that are more complex and/or make other tradeoffs (such as higher typical scheduling latency or lack of perfect scheduling guarantees). But it does not make sense to prematurely optimize for such a case.

[xkrogen]

Alternatively, we could take a "hacky" approach by generating a QueryID in the gateway. We could emulate the protocol so that the client believes the query has been submitted and queued by a Trino coordinator, when in reality, it's being queued at the gateway. The gateway would then be responsible for mapping the client’s request to the actual request sent to Trino, as well as for handling all additional query state.

I don't think this is hacky; it is simply putting an abstraction layer in place btwn the GW and Trino.

I think it is indeed the right way to solve this problem, because there are a few other bits of functionality that I would like to see in the GW which require the GW to have a distinct concept of a query (i.e., its own query ID distinct from Trino's):

• Query result caching in GW
• Query-level retries in GW
  (More background on both in this comment: Consider Adding Cache Layer to Reduce Requests to Trino and Improve Response Time #606 (comment))

Result caching needs an abstracted query ID because a single Trino query can map to multiple queries in the GW, and query-level retries need an abstracted query ID because a single GW query can map to multiple Trino queries.

[oneonestar]

I understand that the ultimate goals are result caching and query retries. Given the one-to-many nature of this functionality, the gateway needs to generate an abstract query ID.

I describe the approach as "hacky" because we are essentially trying to implement asynchronous functionality using the existing protocol, which could lead to considerable confusion in the future.

• We generate an abstract query ID and inform the client that the queue is in the QUEUED status before submitting the query to Trino. Later, when we actually submit the query to Trino, authentication could fail, and by that point, we've already passed the stage where we could inform the client that their request is 401 Unauthorized. Although it’s possible to implement authentication at the gateway level to address this, it does complicate the workflow.
• We would be overloading the term QueryID for multiple purposes: the abstract query ID from the gateway and the query ID from Trino. This means clients would no longer be able to use their query ID to look up their query history in the audit log system (we currently implement audit logging via an event listener). Explaining to users why their "QueryID" is not actually the Trino QueryID could be challenging. Using a dedicated term such as Admission ID, Reservation ID, or QueryExecutionId would be clearer and less error-prone.
• It is important to consider how clients can control query caching behavior.

P.S. I also have no idea how to handle transactions (START TRANSACTION / COMMIT / ROLLBACK).

---

I did a deep research using Gemini to compare Trino and Athena protocol. There are several design elements in Athena that could be beneficial if we want to improve the Trino client protocol:

• ClientRequestToken: A unique string used to ensure the idempotency of the request.
• ResultReuseConfiguration: Controls the query caching behavior.
• "QueryExecutionId: Upon successful submission, the API returns a ID indicates only that the request was syntactically valid JSON and that the user has athena:StartQueryExecution permissions.

Athena vs. Trino Query Protocols.pdf

[Chaho12]

I think if we want to move toward a queue-based approach, it would make sense to leverage Trino’s existing resource group concept rather than inventing a completely new abstraction.

In Trino, resource groups are centrally managed by a single coordinator per cluster, so state consistency is not a concern. However, in Trino Gateway, multiple replicas can exist, which means we need an external state store (e.g., a DB) to coordinate queue state across replicas. From that perspective, introducing a DB-backed state layer seems reasonable.

As xkrogen mentioned, the exact DB choice and performance characteristics matter, but in general, modern databases can handle tens of thousands of TPS without being a bottleneck. For example, HMS commonly uses MySQL, and handling tens of thousands of operations per second is not unusual in practice. Given that, the DB overhead should be acceptable.

Regarding queryId generation, I agree that it can become more complex if tightly coupled with queuing logic. My preference would be to keep the initial implementation lightweight and defer more sophisticated queryId handling to a follow-up improvement once the core behavior is validated.

Finally, I strongly believe this functionality should be implemented in a pluggable way. As Trino Gateway evolves, we should avoid making it overly heavy or tightly coupled to a single scheduling/queueing strategy. A pluggable design would allow users to opt in to more advanced behavior without forcing additional complexity into the core Gateway.

[xkrogen]

We generate an abstract query ID and inform the client that the queue is in the QUEUED status before submitting the query to Trino. Later, when we actually submit the query to Trino, authentication could fail, and by that point, we've already passed the stage where we could inform the client that their request is 401 Unauthorized. Although it’s possible to implement authentication at the gateway level to address this, it does complicate the workflow.

Fair point, though especially for caching, we would probably need to implement authorization in the Gateway regardless.

We would be overloading the term QueryID for multiple purposes: the abstract query ID from the gateway and the query ID from Trino. This means clients would no longer be able to use their query ID to look up their query history in the audit log system (we currently implement audit logging via an event listener). Explaining to users why their "QueryID" is not actually the Trino QueryID could be challenging. Using a dedicated term such as Admission ID, Reservation ID, or QueryExecutionId would be clearer and less error-prone.

Also fair. As long as we maintain the Gateway's concept of QueryID in the query metadata (e.g. as a tag), it should still be queryable in the audit logs. At least in our ecosystem, we have a query layer our users use to access the query history events, so we could simply instruct the service to look up based on the GW QueryID instead of Trino QueryID, and users would not need to know. Similarly we have discussed making the GW UI the only web UI a user would access (e.g. #354), so again we could hide the Trino QueryID behind the scenes. But yes it does add complexity.

P.S. I also have no idea how to handle transactions (START TRANSACTION / COMMIT / ROLLBACK).

Some discussion on this point can be found here: trinodb/trino#11602 (comment)