Documentation
¶
Overview ¶
Package queue provides the factory and registration mechanism for all SafeQueue implementations. It allows new queues to be added to the system and instantiated by name.
Package listqueue provides a high-performance, concurrent-safe FIFO (First-In, First-Out) implementation of the SafeQueue based on the standard library's `container/list`.
Package maxminheap provides a concurrent-safe, priority queue implementation using a max-min heap.
A max-min heap is a binary tree structure that maintains a specific ordering property: for any node, if it is at an even level (e.g., 0, 2, ...), its value is greater than all values in its subtree (max level). If it is at an odd level (e.g., 1, 3, ...), its value is smaller than all values in its subtree (min level). This structure allows for efficient O(1) retrieval of both the maximum and minimum priority items.
The core heap maintenance logic (up, down, and grandchild finding) is adapted from the public domain implementation at https://github.com/esote/minmaxheap, which is licensed under CC0-1.0.
Index ¶
Constants ¶
const ListQueueName = "ListQueue"
ListQueueName is the name of the list-based queue implementation.
This queue provides a high-performance, low-overhead implementation based on a standard `container/list`. It advertises the `CapabilityFIFO`.
Behavioral Guarantees ¶
The core guarantee of this queue is strict physical First-In, First-Out (FIFO) ordering. It processes items in the exact order they are added to the queue on a specific shard.
Performance and Trade-offs ¶
Because the physical insertion order may not match a request's logical arrival time (due to the `controller.FlowController`'s internal "bounce-and-retry" mechanic), this queue provides an*approximate FCFS behavior from a system-wide perspective.
Given that true end-to-end ordering is non-deterministic in a distributed system, this high-performance queue is the recommended default for most FCFS-like policies. It prioritizes throughput and efficiency, which aligns with the primary goal of the Flow Control system.
For workloads that require the strictest possible logical-time ordering this layer can provide, explicitly using a queue that supports `CapabilityPriorityConfigurable` is the appropriate choice.
const MaxMinHeapName = "MaxMinHeap"
MaxMinHeapName is the name of the max-min heap queue implementation.
Variables ¶
var ( // RegisteredQueues stores the constructors for all registered queues. RegisteredQueues = make(map[RegisteredQueueName]QueueConstructor) )
Functions ¶
func MustRegisterQueue ¶
func MustRegisterQueue(name RegisteredQueueName, constructor QueueConstructor)
MustRegisterQueue registers a queue constructor, and panics if the name is already registered. This is intended to be called from init() functions.
func NewQueueFromName ¶
func NewQueueFromName(name RegisteredQueueName, policy flowcontrol.OrderingPolicy) (contracts.SafeQueue, error)
NewQueueFromName creates a new SafeQueue given its registered name and the OrderingPolicy that will be optionally used to configure the queue (provided it declares CapabilityPriorityConfigurable). This is called by the FlowRegistry during initialization of a flow's ManagedQueue.
Types ¶
type QueueConstructor ¶
type QueueConstructor func(policy flowcontrol.OrderingPolicy) (contracts.SafeQueue, error)
QueueConstructor defines the function signature for creating a SafeQueue.
type RegisteredQueueName ¶
type RegisteredQueueName string
RegisteredQueueName is the unique name under which a queue is registered.
Source Files