GPU Credit Ledgers And Schedulers

What's being tested

This tests concurrent resource accounting: maintaining a correct GPU-credit ledger under reservations, usage commits, refunds, expirations, and duplicate requests. The core skill is combining hash maps, heaps, ordered maps, and atomic state transitions to support balance checks, top-K queries, and fair scheduling with clear complexity guarantees.

Patterns & templates

• Ledger-as-events, balance-as-index — append immutable events, maintain per-user cached balance; O(1) updates, rebuildable from log after crash.

• Idempotency-key table — store request_id -> result for reserve, commit, refund; return prior result on retry, not double-apply credits.

• Expiration min-heap — keep (expires_at, grant_id, user_id, amount); lazily pop expired grants before reads/writes, O(log n) per grant.

• Per-user grant buckets — consume credits FIFO by expiration using deque or min-heap; prevents spending long-lived credits before soon-expiring credits.

• Atomic check-and-decrement — implement try_reserve(user, cost) under a mutex, CAS loop, or transaction; never split balance check from mutation.

• Scheduler priority queue — rank runnable jobs by priority, submit_time, credit_balance, or fairness score; use stable tie-breakers to avoid nondeterminism.

• Top-K users/jobs — maintain heap or balanced tree keyed by balance/usage; heap is cheaper for approximate/top query, tree supports deletes/updates cleanly.

Common pitfalls

Pitfall: Treating balance as a single integer fails when credits have different expirations, grant sources, or refund semantics.

Pitfall: Retrying reserve() without an idempotency key can double-charge users during client timeouts or scheduler failover.

Pitfall: Using a heap for mutable priorities without lazy invalidation creates stale entries; store version numbers and discard obsolete heap nodes.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.