GPU Credit Ledgers And Schedulers

What's being tested

Candidates must show practical mastery of designing a multi-tenant, real-time resource accounting and scheduling system that prevents double-spend, enforces budgets, and schedules heterogeneous GPUs. Interviewers probe distributed-systems primitives (consistency, partitioning, idempotency), APIs and failure modes (retries, node failure, clock skew), and scheduler algorithms (gang scheduling, bin-packing, fairness). Expect the interviewer to evaluate clear tradeoffs between strict correctness (no overspend) and scalable, low-latency allocation paths.

Core knowledge

• Credit ledger data model: per-tenant balance, per-transaction idempotency key, monotonic sequence or vector timestamp to order updates; store in a strongly consistent partition (etcd, Spanner, Postgres with SELECT FOR UPDATE) when linearizability is required.

• Idempotency: clients must send an idempotency key; server stores (key -> result) for retry-safe semantics; eviction policy based on TTL and transaction finality to bound storage.

• Reservation vs commit: implement a two-phase flow: reserve (temporary lease reducing available balance) then commit (final deduction), supporting rollback on node failure; leases expire automatically to avoid stuck resources.

• Fast-path local checks: use a cached bucket/token (leaky token-bucket) per tenant for sub-second approvals; reconcile with authoritative ledger periodically to bound over-commit risk.

• Distributed partitioning: partition ledger by tenant-id or account-hash; scale to millions by sharding and routing RPCs to the shard owner, minimizing cross-shard transactions.

• Heterogeneous GPU costing: normalize GPUs using cost-rate (credits/sec) per device type; billing = sum(cost_rate_i * seconds_used_i). Support preemption and partial refunds with precise time accounting.

• Scheduler algorithms: for multi-GPU jobs use gang scheduling + bin-packing heuristics (best-fit decreasing) or Dominant Resource Fairness (DRF) for fairness; backfilling reduces fragmentation for short jobs.

• Atomicity & concurrency control: for strict correctness prefer linearizable updates (compare-and-set, serializable DB txns); for higher throughput consider optimistic allocation with bounded reconciliation windows.

• Failure modes: handle node crashes (leases expire), network partitions (reject writes if quorum not available for linearizability), and clock skew (use server timestamps or monotonic counters).

• Observability & SLAs: track p99 allocation latency, double-spend incidents, reconciliation drift, and per-tenant throttles; emit events to Kafka/ingestion pipeline for billing pipeline.

• Security & multi-tenancy: authenticate calls via strong identity (mTLS, IAM), enforce RBAC for transfers, and audit every ledger mutation for dispute resolution.

• Scaling numbers: for N tenants ~10M, keep per-tenant metadata in a scalable KV store; avoid multi-tenant cross-shard txns—they kill throughput. Use asynchronous reconciliation and incremental snapshots for export.

Worked example — "Design GPU credit allocator"

First 30 seconds: ask expected scale (tenants/sec, concurrent allocs), consistency SLA (strict no-overspend vs eventual), GPU heterogeneity, and whether allocations are preemptible. Declare assumptions: target 100k allocs/sec, strict per-tenant no-overspend, heterogeneous GPUs with known cost rates.

Skeleton of an answer:

1. API design: Reserve(tenant, amount, idempotency_key), Commit(reservation_id), Release(reservation_id); synchronous response for Reserve.

2. Ledger implementation: shard by tenant; each shard owner provides linearizable reservations via SELECT FOR UPDATE or etcd CAS. Store reservations with TTL.

3. Fast-path: local token-bucket cache for micro-requests; falls back to authoritative Reserve RPC when cache misses.

4. Scheduler integration: scheduler requests reservations for GPU set (gang), scheduler commits when job starts, releases on preemption.

Explicit tradeoff: using strong linearizability prevents double-spend but requires cross-shard coordination for transfers—choose to ban cross-shard atomic transfers or implement async transfer with temporary credit holds. Closing: if more time, prototype shard-split logic, run chaos-testing (node failures, retries), and design reconciliation jobs to detect and correct drift.

A second angle — "Design credit balance with vector-clock expirations"

This variant emphasizes concurrent updates from multiple disconnected clients and expiry semantics. Use vector clocks or per-shard monotonic counters to track causality of credit events; model balance as an eventually-consistent CRDT only if occasional overspend is acceptable. To support expirations, attach expiry metadata to each credit delta and garbage-collect with causal ordering to avoid prematurely dropping recent updates. The primary shift: when strict single-source ordering is impossible, rely on deterministic merge functions and compensation transactions, and be explicit about allowed windows for inconsistency.

Common pitfalls

Pitfall: Relying solely on a cheap local cache for immediate approvals without any authoritative reconciliation. This leads to silent double-spend when many nodes grant allocations simultaneously; prefer bounded fast-path windows and periodic reconciliation or pessimistic reservations for high-value ops.

Pitfall: Forgetting idempotency keys and storing results only transiently. Retries will create duplicated charges; store idempotency mapping with TTL and ensure idempotent handlers are deterministic.

Pitfall: Designing the scheduler independently from credit semantics. Scheduling multi-GPU jobs requires atomic reservations across multiple GPUs (gang scheduling); otherwise partial allocations result in wasted resources and complex refunds. Flag the need for a coordinated reserve-and-commit for multi-device jobs.

Connections

Interviewers may pivot to adjacent topics: designing the billing/export pipeline and offline reconciliation (data engineering), or to fine-grained scheduler optimization (resource management research like Borg/Omega). They may also ask about monitoring and alerting thresholds (SRE concerns).

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann — strong treatment of consistency, partitioning, and CRDTs for ledger-like systems.

• Dynamo: Amazon’s Highly Available Key-value Store — background on partitioning, eventual consistency, and vector-clock techniques.

• Stripe: Idempotency keys — practical pattern and tradeoffs for retry-safe financial operations.