Tool · Elixir library

dwrr: Deficit Weighted Round Robin for Elixir

A cost-aware scheduler with an immutable core and an optional caller-owned server.

README.md

Deficit weighted round robin (DWRR) scheduler for Elixir. The core is a set of pure functions over immutable values. Dwrr.Server is an optional, caller-owned wrapper that keeps one scheduler in one process.

Published release: 0.1.0 on Hex. The Hex package and application are dwrr. HexDocs for 0.1.0 are public, with a getting-started guide and API reference. Documentation was published separately; the package is unchanged. To build locally, run MIX_ENV=dev mix docs --warnings-as-errors and open doc/index.html.

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 the fixed-quantum core through immutable values; Dwrr.Server and Elixir-domain validation are local API choices, not shared requirements. Fixtures and the main CI retain historical revision 8a0e3cf9ae860ba207213590c00feeb822bdd8f2, rather than automatically following upstream. Separate current-source checks must identify their revision and results; see TESTING.md. The standalone example CI does not change that historical conformance-tool pin.

The need

When several queues share one resource, such as a link, a packet path or a job pool, each queue should get a share in proportion to its quantum. DWRR does this with small integer bookkeeping, and it measures work by the cost callers declare, not by elapsed time. This library gives you that scheduler as plain values you can store, branch and test.

At a glance

  • Dwrr is pure: no process, no I/O, no hidden state. Each successful operation returns a new scheduler value.
  • Dwrr.Server is a serialized GenServer around one scheduler. You start and supervise it; the library starts nothing for you.
  • Requires Elixir >= 1.18 and OTP >= 27. No runtime dependencies. StreamData is a test-only dependency.
  • MIT licensed.

Quick start

Add the published package to your application’s mix.exs dependency list:

text
1{:dwrr, "~> 0.1.0"}

Then run mix deps.get in your application. This selects the 0.1.x series; use {:dwrr, "== 0.1.0"} if you need that exact release.

For development against a local source checkout, use this instead:

text
1{:dwrr, path: "../dwrr-elixir"}

Adjust the path for your application. The core has no dependencies to fetch; this repository’s own tests additionally require StreamData.

Examples

Each example is an independent history. Each one binds result to what the operations actually returned.

Byte sharing

Queue 0 has quantum 2 and queue 1 has quantum 3. Queue 0 serves packet_a, then blocks on packet_b. Queue 1 cannot yet afford packet_x (cost 4), so it keeps its 3 credit. Queue 0 then serves packet_b, and queue 1 serves packet_x and packet_y.

elixir
 1s = Dwrr.new(2)
 2{:ok, s} = Dwrr.set_quantum(s, 0, 2)
 3{:ok, s} = Dwrr.set_quantum(s, 1, 3)
 4
 5{:ok, s} =
 6  Dwrr.enqueue(s, 0, [
 7    %Dwrr.Item{value: :packet_a, cost: 2},
 8    %Dwrr.Item{value: :packet_b, cost: 2}
 9  ])
10
11{:ok, s} =
12  Dwrr.enqueue(s, 1, [
13    %Dwrr.Item{value: :packet_x, cost: 4},
14    %Dwrr.Item{value: :packet_y, cost: 1}
15  ])
16
17{:ok, served, _s} = Dwrr.take(s, 10)
18result = Enum.map(served, &{&1.queue, &1.value, &1.cost})

Expected result:

text
1[{0, :packet_a, 2}, {0, :packet_b, 2}, {1, :packet_x, 4}, {1, :packet_y, 1}]

Fair file-transfer simulation

The standalone example uses Basic/Team/Business byte quanta of 1024/2048/4096 and repeated take(s, 1) calls. Its twelve pretend records, selection order and cumulative totals match the Python example; the Go README uses a different backlogged dataset. Final totals are Basic=5120, Team=6656 and Business=12288 bytes: finite offered demand, not a promised 1:2:4 split. There is no real transfer I/O, timing, bandwidth pacing or preemption. Use bounded chunks as items in a real sender for finer interleaving. The example requires a source checkout; it is not shipped in the Hex package.

Caller-owned worker orchestration

The Server only decides the order of jobs. It does not run them. The caller receives the jobs and runs them itself. This example stops the server it started, even if an operation fails.

elixir
 1{:ok, server} = Dwrr.Server.start_link(1)
 2
 3result =
 4  try do
 5    {:ok, _scheduler} =
 6      Dwrr.Server.enqueue(server, 0, [
 7        %Dwrr.Item{value: :job_a, cost: 1},
 8        %Dwrr.Item{value: :job_b, cost: 1}
 9      ])
10
11    {:ok, served, _scheduler} = Dwrr.Server.take(server, 2)
12    Enum.map(served, & &1.value)
13  after
14    GenServer.stop(server)
15  end

Pure withdrawal

remove_head/2 withdraws the first item without spending credit. drain_queue/2 then withdraws the rest in FIFO order.

elixir
 1s = Dwrr.new(1)
 2
 3{:ok, s} =
 4  Dwrr.enqueue(s, 0, [
 5    %Dwrr.Item{value: :cancelled, cost: 5},
 6    %Dwrr.Item{value: :kept, cost: 1}
 7  ])
 8
 9{:ok, cancelled, s} = Dwrr.remove_head(s, 0)
10{:ok, kept, _s} = Dwrr.drain_queue(s, 0)
11result = {[cancelled.value], Enum.map(kept, & &1.value)}

Atomic error

Enqueue checks every item before it adds any. The valid item is not kept when the zero-cost item fails. A later take on the original scheduler returns nothing.

elixir
1s = Dwrr.new(1)
2
3result =
4  Dwrr.enqueue(s, 0, [
5    %Dwrr.Item{value: :valid, cost: 1},
6    %Dwrr.Item{value: :invalid, cost: 0}
7  ])
8
9{:ok, [], _s} = Dwrr.take(s, 10)

Public API

Dwrr.new(count) creates count empty queues (zero is valid), each with quantum 1 and credit 0. %Dwrr.Item{value: value, cost: cost} is the enqueue record; take/2 returns %Dwrr.Scheduled{queue: index, value: value, cost: cost} records.

OperationSuccessful result
enqueue(s, index, items){:ok, scheduler}
set_quantum(s, index, quantum){:ok, scheduler}
add_queue(s){index, scheduler}
remove_queue(s)scheduler (unchanged when no queues exist)
remove_head(s, index){:ok, item_or_nil, scheduler}
drain_queue(s, index){:ok, items, scheduler} in FIFO order
take(s, n){:ok, scheduled_items, scheduler}

Dwrr.Server exposes the same operations against a caller-started server and returns the same results, including immutable scheduler snapshots.

Behavior worth knowing

  • Results. Most operations return {:ok, scheduler}, {:ok, value, scheduler} or {:error, code}. add_queue/1 returns {index, scheduler}. remove_queue/1 returns the scheduler alone.
  • Six tagged errors. :invalid_index, :negative_take, :zero_cost, :cost_too_large, :zero_quantum and :quantum_too_large. A tagged error returns no new scheduler; it retains the input unchanged, so keep using the scheduler you passed in.
  • ArgumentError. A non-integer index or count, a negative count, or a negative or noninteger cost or quantum, or a batch that is not a proper list of Dwrr.Item structs raises ArgumentError. Domain validation precedes shared error ordering: enqueue validates the integer index and entire batch first; set_quantum validates the integer index and nonnegative integer quantum first. Only for domain-valid arguments does :invalid_index win, followed by the first zero/oversized cost or the zero/oversized quantum. No items are appended on either kind of failure.
  • Immutable storage. Old snapshots stay valid. One snapshot can be branched into separate histories, and branches do not share writes. Values are stored and returned without being inspected.
  • Visits. Nonempty queues earn their quantum at the start of a visit in cyclic index order. Credit carries across visits while backlogged; empty queues hold no credit. Whole unproductive rounds are skipped exactly, so a huge cost with quantum 1 does not require one iteration per grant.
  • FIFO, no overtaking. Items leave a queue in order. A queue whose head costs more than its credit waits, and later items in that queue do not jump ahead.
  • Take is a retrieval limit, not a fairness cap. take/2 returns up to n items in service order. If it stops at n in the middle of a visit, that visit stays paused with its remaining credit, and the next take continues it without another quantum grant. It returns fewer than n only when every queue is empty.
  • Enqueue joins the visit. Items added to the queue being visited join that visit; they do not start a new grant.
  • Reweight affects the next grant. set_quantum/3 changes only the quantum used for the next grant. Credit is kept.
  • Withdrawal. remove_head/2 and drain_queue/2 do not spend credit. Emptying a queue resets its credit to 0.
  • Last-queue deletion and index reuse. remove_queue/1 deletes only the last queue, with its items. add_queue/1 may then reuse that index.
  • Limits. Costs and quanta are limited to 2^63-1. Each queue’s credit stays within 2^64-3. These are shared scheduler limits, not BEAM integer limits.
  • Fairness is by declared cost. While queues stay backlogged, each queue’s served cost at closed visit boundaries stays within one maximum item cost of its fixed quantum times the number of its visits. A paused active visit is not a closed visit. This is not an unrestricted fairness promise for dynamic backlogs. The scheduler does not measure time.
  • Server. Each call is one GenServer.call/2 with the default 5000 ms timeout. A timeout does not prove that the operation was rolled back. There are no retries and no backpressure. An argument outside the Dwrr domain raises ArgumentError inside the server, which then terminates. The caller sees an exit, not a tagged error. A restarted server starts fresh from its original count, so queued items, quantum changes and added queues are lost. Nothing is persisted.

There are no built-in queue capacity limits, admission control or resource-exhaustion recovery guarantees. Large counts, batches and retained immutable snapshots still consume memory. Pure histories need no shared lock; callers coordinate which snapshot to retain. The Server serializes its own history, not caller-owned branches. Neither interface waits for producers when empty; take(s, 0) or an empty scheduler returns {:ok, [], s}. Selection still costs CPU and memory.

How we know it’s correct

  • The behavior follows a written spec, pinned in the sibling dwrr-spec repository, with a shared conformance corpus. The corpus responses were recorded from the Go implementation github.com/version2beta/dwrr v0.10.1.
  • Property tests (StreamData 1.3.0, test-only) run generated operation sequences against a naive reference model. They compare every result and state, and check item conservation, FIFO order, state after errors, branching and deterministic replay.
  • The conformance driver replays that corpus through the Elixir implementation.
  • Focused tests cover each operation and the Dwrr.Server behavior.

Historical local verification ran on Elixir 1.20.4 / OTP 29. The minimum Elixir 1.18 / OTP 27 and the full CI matrix (Elixir 1.18.4 / OTP 27.3 and Elixir 1.20.4 / OTP 29.1.2) are configured but not verified by this README. See TESTING.md.

Check it yourself

Run these from the repository root:

sh
1MIX_ENV=test mix deps.get --check-locked
2mix format --check-formatted
3mix compile --warnings-as-errors
4MIX_ENV=test mix test --warnings-as-errors --no-color

The conformance replay needs a sibling dwrr-spec checkout at the pinned commit. TESTING.md lists the exact commands.

How it compares

  • Go dwrr. The spec maps each operation to the Go library (SPEC section 11). Go panics on invalid_index and negative_take. Here they are tagged errors, {:error, :invalid_index} and {:error, :negative_take}.
  • BEAM storage. Scheduler values are ordinary immutable Erlang terms. There is no shared memory and no mutable state. Old snapshots stay valid, and the cost and credit limits are the same in every language, not the BEAM’s integer limits.
  • Pure coordination, not a worker pool. Dwrr decides which item is served next. It does not start processes, run jobs or manage a pool of workers. The caller does the work. Dwrr.Server is a serialized mailbox around one scheduler, not a pool.

Current implementation and shared-source status

The pure core, driver, optional Server, public docs and package metadata are implemented in this checkout. Hex package dwrr 0.1.0 was released from source commit 88c8dc7; the driver is checkout-only. Versioned HexDocs are public, verified on 2026-11-21. Source links remain pinned to that release, not these later documentation edits.

Vendored SPEC/PROTOCOL/corpus and their hash guards deliberately retain the historical 8a0e3cf9ae860ba207213590c00feeb822bdd8f2 snapshot. Sibling working-tree corrections clarify that negative costs/quanta are language-local and wire integers have no signed-32-bit protocol cap, add language mappings, and repair the Go adapter/checker; no scheduler semantics or corpus bytes changed. They do not silently repin these historical fixtures or CI. Historical verification records report that Elixir was also checked against the expanded sibling checker: 41/41, plus all 1,839 cases / 44,728 steps. Python now has a working mutable, internally locked implementation; its public API and language-domain validation differ from Elixir’s immutable core. Go’s callable-quantum/result API and generation-exhaustion restriction are not shared fixed-core requirements. The sibling protocol now permits native count-representation exhaustion as a resource failure, not malformed input: Go detects counts above native int before allocation, emits stderr and exits 1 with no response or later processing; prior responses stand. This adds no shared count cap or Elixir rejection requirement, and guarantees no controlled recovery from actual allocation limits/OOM. Frozen vendored documents and identities above remain unchanged.

Colophon