README
¶
Ordering Policies
Ordering policies determine which request from a specific flow's queue is selected for dispatch when that flow is picked by a Fairness Policy.
This corresponds to Tier 3 of the strict 3-Tier Dispatch Hierarchy in the Flow Control system:
- Priority (Band Selection): Selects the highest-priority Band that has pending work.
- Fairness (Flow Selection): Determines which Flow within that band gets the next dispatch opportunity.
- Ordering (Item Selection): [Implemented by this package] Determines which Request from that specific flow's queue is dispatched.
Available Implementations
- First-Come, First-Served (FCFS) (
fcfs-ordering-policy): Selects requests based on their arrival order. This is the default policy. - Earliest Deadline First (EDF) (
edf-ordering-policy): Selects requests based on their absolute deadline, derived from TTL. - SLO Deadline (
slo-deadline-ordering-policy): Selects requests based on a deadline derived from an SLO header (e.g., target TTFT).
Conformance Testing
This directory contains a functional test suite (functional_test.go) that verifies OrderingPolicy implementations against the expected contract.
To run the conformance tests:
go test ./pkg/epp/framework/plugins/flowcontrol/ordering/...
To include a new ordering policy in these tests, add its factory to the local policies map inside TestOrderingPolicyConformance within functional_test.go.
Related Documentation
Documentation
¶
Overview ¶
Package ordering provides the standard implementations of the OrderingPolicy interface.
Context: The 3-Tier Dispatch Hierarchy ¶
The Flow Control system manages traffic using a strict three-tier decision hierarchy. This package implements Tier 3.
Priority (Band Selection): The system first strictly selects the highest-priority Band that has pending work.
Fairness (Flow Selection): Once a Band is selected, the FairnessPolicy (interflow) determines which Flow within that band gets the next dispatch opportunity.
Ordering (Item Selection) - [THIS PACKAGE]: Once a Flow is selected, the OrderingPolicy determines which Request from that specific flow's queue is dispatched. This governs the "internal discipline" of the flow (e.g., whether to serve oldest requests first or most urgent).
Architecture: The Flyweight Pattern ¶
Ordering Policies are Singletons. A single instance handles the ordering logic for all queues in a Priority Band. To support this efficiently, the policy follows the Flyweight pattern:
- The Plugin Instance (e.g., FCFS) is a Singleton. It defines the Logic (Less).
- The Logic (Less) acts as a pure function (or comparator) that operates on the queue's items.
Standard Implementations ¶
This package includes the following core strategies:
FCFS ("First-Come, First-Served") ("fcfs-ordering-policy"): Orders requests by their logical arrival time. This is the default and most "intuitive" ordering.
EDF ("Earliest Deadline First") ("edf-ordering-policy"): Orders requests by their absolute deadline (EnqueueTime + TTL). This maximizes the number of requests served before their deadlines expire.
SLO Deadline ("slo-deadline-ordering-policy"): Orders requests by an SLO-based (service level objective) deadline computed as ReceivedTimestamp + x-llm-d-slo-ttft-ms header (interpreted as milliseconds). Requests without a valid header are scheduled after SLO-bound requests. This maximizes the number of requests served before the deadlines computed on the defined SLO expire.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package edf implements an ordering policy that selects requests based on their absolute deadlines (Earliest Deadline First).
|
Package edf implements an ordering policy that selects requests based on their absolute deadlines (Earliest Deadline First). |
|
Package fcfs implements an ordering policy that selects requests based on their arrival order at the Flow Control layer (First-Come, First-Served).
|
Package fcfs implements an ordering policy that selects requests based on their arrival order at the Flow Control layer (First-Come, First-Served). |
|
Package slodeadline implements an ordering policy that selects requests based on an SLO-based deadline derived from request headers.
|
Package slodeadline implements an ordering policy that selects requests based on an SLO-based deadline derived from request headers. |