Tool · Python library
dwrr: Deficit Weighted Round Robin for Python
A cost-aware FIFO scheduler with mutable state and whole-operation locking.
README.md
A cost-aware FIFO scheduler for Python applications sharing a consumer among
producers. Version 0.1.0 is published on
PyPI from source commit 717737c.
Other languages
These libraries share fixed-quantum scheduling semantics, with language-specific APIs and additional features. See each library’s README for its supported contract.
Shared specification
dwrr-spec defines the shared fixed-quantum contract, conformance corpus and driver protocol / conformance tools. They let implementations with different APIs check the same service order, errors and numeric limits rather than rely on similar-looking algorithms. This is a development/conformance resource, not a runtime dependency. Pinned revisions and vendored snapshots make checks reproducible; they do not automatically track current spec source or establish all-sequences conformance.
This implementation targets draft 0.1.1 using the vendored snapshot from
243dd125470365df2c52a6ce72de3ee8ecfce3fe; see
vendor provenance and the local mapping.
Mutable state, whole-operation locking and Python-domain exceptions are local
API choices, not requirements imposed on Go or Elixir. CI replays the vendored
corpus/tools, not an automatically refreshed upstream checkout.
The need
Python application authors sharing a consumer among producers get a cost-aware FIFO scheduler: each backlogged queue receives service in proportion to its quantum, measured in caller-declared bytes, tokens, estimated work, or unit costs. The application retrieves work and executes it itself. The scheduler does not measure execution time or run jobs.
At a glance
- Import:
dwrr; published distribution:dwrr-python0.1.0. - Python >= 3.11; standard library only at runtime. The actual implementation passed the frozen checks on CPython 3.11.15 and 3.15.0 (Darwin arm64).
- A mutable, generic
Scheduler[T]with explicitItem[T]inputs andScheduled[T]outputs. No immutable scheduler snapshots or implicit server. - Internal locking serializes every complete operation, including validation and result creation. No async wrapper; the lock does not protect caller payload mutations or concurrent edits to an input batch.
- Implements language-neutral dwrr-spec 0.1.1 (draft): all eight operations, all six errors, exact limits and service order. Finite conformance checks pass; they are not proof for every possible operation sequence.
- MIT license; no runtime dependencies. Published version
0.1.0.
Requirements and installation
Install the published package in your environment (Python >= 3.11):
1python3 -m pip install dwrr-python==0.1.0For development, clone the repository and install from its root instead:
1git clone https://github.com/version2beta/dwrr-python.git
2cd dwrr-python
3python3 -m pip install .Setuptools builds an ordinary pure-Python wheel/sdist. The dev/test driver and verification tools are checkout-only, not installed CLI entry points. Links to checkout-only documentation below point to GitHub because those files are not included in the installed distribution. The core needs no Go, Elixir, credentials, configuration or network service.
First useful example
Queue 0 earns 2 credit per visit and queue 1 earns 3. Queue 1’s head costs 4, so it must carry credit across visits before serving it:
1from dwrr import Item, Scheduler
2
3scheduler = Scheduler[str](2)
4scheduler.set_quantum(0, 2)
5scheduler.set_quantum(1, 3)
6scheduler.enqueue(0, [Item("a", 2), Item("b", 2)])
7scheduler.enqueue(1, [Item("x", 4), Item("y", 1)])
8
9served = scheduler.take(10)
10print([(item.queue, item.value, item.cost) for item in served])Expected output:
1[(0, 'a', 2), (0, 'b', 2), (1, 'x', 4), (1, 'y', 1)]Fair file-transfer example
Standalone simulator: pretend FIFO transfers
with Basic/Team/Business byte quanta of 1024/2048/4096. It prints selection order
and cumulative bytes using repeated take(1) calls, with no real transfer I/O.
The example explains byte fairness, head blocking and why finite totals need not
be 1:2:4. Run it against a locally installed checkout; it is not packaged.
Public API
T is the opaque payload type. Item(value, cost) and
Scheduled(queue, value, cost) are frozen dataclass records with those public
fields. They are shallowly immutable: the payload is retained and returned by
reference, not copied, hashed, compared or explicitly executed by scheduling operations.
Item construction does not validate costs; enqueue does, preserving batch error
precedence. Costs cannot be changed after acceptance through the supported API.
| Call | Successful result |
|---|---|
Scheduler[T](count: int) | New mutable scheduler with count queues |
enqueue(queue: int, items: list[Item[T]] | tuple[Item[T], ...]) | None; appends the whole batch |
set_quantum(queue: int, quantum: int) | None; changes the next grant |
add_queue() | int; index of the appended queue |
remove_queue() | None; discards only the last queue and its items |
remove_head(queue: int) | Item[T] | None; withdraws without scheduling |
drain_queue(queue: int) | list[Item[T]]; withdraws everything FIFO |
take(n: int) | list[Scheduled[T]]; removes up to n items in service order |
Exports also include SchedulerError, MAX_COST and MAX_QUANTUM. There is no
public state-editing, inspection, copying, reset, iterator or persistence API in
this library. Lists returned by operations are independent containers. Record
identity is not promised; payload identity is.
Withdrawal and recovery
Independent example, including a whole-batch rejection:
1from dwrr import Item, Scheduler, SchedulerError
2
3scheduler = Scheduler[str](1)
4try:
5 scheduler.enqueue(0, [Item("not retained", 1), Item("invalid", 0)])
6except SchedulerError as error:
7 print(error.code)
8print(scheduler.take(10))
9
10scheduler.enqueue(0, [Item("cancelled", 5), Item("ready", 1)])
11removed = scheduler.remove_head(0)
12remaining = scheduler.drain_queue(0)
13print(removed.value, [item.value for item in remaining])Expected output:
1zero_cost
2[]
3cancelled ['ready']Behavior worth knowing
- Queues are indexed
0..count-1, initially empty with quantum 1 and credit 0. Adding a queue preserves existing indices; removing affects only the last. An added queue may reuse a removed index. Indices are not permanent IDs. - Visits cycle in index order. A nonempty queue receives its quantum once at the start of a visit, then spends credit on FIFO heads. A blocked head ends the visit; later cheaper items never overtake it. Empty queues hold no credit.
- Take is a retrieval limit, not a fairness cap. Stopping at
npreserves a nonempty active visit and its credit. The next take resumes without another grant, even if that resumed head will block. Fewer thannresults means all queues are empty. Zero queues, all empty, ortake(0)return[]; zero and already-empty takes change no state. - Enqueued items join an active visit without another grant. Reweighting preserves credit and the visit; its quantum applies at the next grant, not on resume.
- Withdrawals do not spend credit. Emptying a queue resets its credit and closes its active visit, advancing the cursor. Removing the active last queue cancels that visit and repairs the cursor as defined in SPEC.
MAX_COST = MAX_QUANTUM = 2**63 - 1. Every integer from 1 through the limit is accepted, including values beyond2**53. Credit is exact through2**64 - 3; no float arithmetic, saturation or wrapping is allowed.- Long runs of idle rounds are computed directly while preserving exact order.
A maximum-cost item with quantum 1 must not require
2**63loop iterations. No throughput, latency, allocation, sparse-queue complexity or Go speed-parity claim is made. No result allocation is proportional merely to requestedn. - Fairness concerns declared cost while queues stay backlogged with fixed quanta, not item counts, elapsed time or arbitrary changing backlogs. The scheduler is nonblocking in the queueing sense: it never waits for producers, but a large batch still takes CPU time and memory to select.
Failures and recovery
SchedulerError subclasses ValueError; its stable .code is one of:
| Code | Condition |
|---|---|
invalid_index | Negative queue index or index beyond the current last queue |
zero_cost / cost_too_large | First invalid item has cost 0 / greater than MAX_COST |
zero_quantum / quantum_too_large | Quantum is 0 / greater than MAX_QUANTUM |
negative_take | Retrieval limit is negative |
Queue validation precedes costs/quantum validation, including an empty batch. Enqueue validates in item order before appending anything. These failures leave all scheduler state unchanged; catch the exception, correct the input, and reuse the same scheduler. Exception messages are not a stable interface.
Numeric arguments must be built-in int, not bool, floats or coerced
numeric objects. Count must be nonnegative. Negative costs/quanta and negative
count raise ordinary ValueError, not a new shared error code. Wrong argument
or batch-element types raise TypeError. All documented validation failures
preserve state. Precise validation order is in SPEC §3.
These Python-domain rules are local additions where the language-neutral
spec does not define an input. Arbitrary iterables/generators are not accepted
as batches. Resource exhaustion, process termination, forged private state,
bypassing record immutability and concurrent input-batch mutation are outside
the atomicity guarantee; there is no crash-recovery promise.
Effects, privacy and non-goals
The core only mutates its own in-memory scheduling state. It performs no file, network, subprocess, environment/configuration, logging, telemetry, model or credential access. It starts no thread, task or process. It retains payload references while queued; returned items belong to the caller. Removing/draining releases scheduler-owned references to removed payloads, but is not secure erasure and cannot free references held elsewhere. Normal Python reference release may run finalizers/weakref callbacks; discarded queues are retained until the operation lock is released and state is coherent. This does not promise safety for arbitrary GC, signal handlers or asynchronous same-thread callback reentry. Caller mutation of a shared payload is visible; the scheduler neither protects nor deep-copies it.
Not included: job execution, worker pools, blocking dequeue, backpressure, queue
capacity/admission policy, keyed queues, priority levels, deadlines, persistence,
distributed fairness, async wrappers or a production CLI. The dev/test
conformance driver is the only protocol stdio interface; it is not a general
command tool. The checkout-only fair-transfer example prints a simulation.
No configuration precedence, secrets management or doctor command is needed.
Compatibility and verification
SPEC.md is subordinate to this README and pins the shared draft 0.1.1
behavior and inspected sources. The implementation at
b97fc29 passed the historical verification gates on CPython 3.11.15 and 3.15.0 on 2026-11-19:
- All 31 Python tests, including native replay of 1,839 cases / 44,728 steps in seven files, an independent bounded naive oracle and concurrency checks.
- Unchanged external corpus replay and all 41 protocol checks.
- Wheel/sdist metadata, isolated wheel/sdist/checkout installs, and both README examples executed against installed code.
Independent read-only code review reported no issues; it was not an independent test rerun. KIT-VERIFICATION.md separates historical kit reachability from actual implementation evidence and its limitations. TESTING.md records reproducible checks and the historical pre-publication gate. Hosted CI subsequently passed on Python 3.11 and 3.14 for the released source (run). Other runtimes/platforms, universal thread fairness, resource-exhaustion recovery and performance parity are not demonstrated.
Compatibility is with the shared fixed-integer-quantum contract, not every sibling feature: no Go callable quanta, floats or speculative scheduling; no Elixir immutable branching or GenServer wrapper. See SPEC §8 for historical source and adapter qualifications.