Benchmarking Random Executor Strategies for High-Concurrency Workloads### Overview
High-concurrency workloads—those that require managing many simultaneous tasks or requests—are common in modern systems: web servers, real-time analytics, distributed databases, and large-scale background-processing pipelines. Executors (also called schedulers or task runners) decide which tasks run when and on which threads or workers. A “Random Executor” uses randomness to choose tasks, workers, or scheduling order as part of its strategy. Randomization can reduce contention, avoid pathological scheduling patterns, and simplify design. This article examines the principles, design choices, benchmarking methodology, and practical findings for different Random Executor strategies under high-concurrency conditions.
Why randomness?
Randomness in scheduling has several practical benefits:
- Simplicity: Random selection requires little bookkeeping compared with complex priority queues or work-stealing mechanisms.
- Load smoothing: Random assignment can spread work across workers without costly global coordination.
- Avoiding adversarial cases: Deterministic schedulers can be gamed or fall into pathological patterns; randomness makes worst-case sequences harder to construct.
- Probabilistic fairness: Over time, random selection approximates fair sharing without heavy locking.
Types of Random Executor Strategies
Below are several approaches that use randomness at different decision points:
- Random task selection from a global queue.
- Random worker selection for incoming tasks (push model).
- Random victim selection in a work-stealing model.
- Hybrid approaches: random within a locality set, combined with deterministic fallback.
- Randomized backoff and contention-window selection for lock-free queues.
Each choice impacts contention, throughput, latency, fairness, and implementation complexity.
Design variables and implementation considerations
- Queue organization: global queue vs per-worker queues.
- Global queue: simple but becomes a contention hotspot at high concurrency.
- Per-worker queue: reduces contention; requires stealing to balance load.
- Random source: pseudo-random number generator (PRNG) choice matters. Fast, thread-local PRNGs (xorshift, xoshiro) avoid contention.
- Task size distribution: uniform small tasks vs a heavy-tailed mix dramatically changes behavior.
- Worker affinity and cache locality: random assignment may harm cache locality; hybrid approaches restrict randomness to nearby workers.
- Backpressure and queue capacity: how executors handle overflow shapes latency and throughput.
- Fairness metrics: measure starvation probability and variance in task completion times.
- Instrumentation: counters for steals, retries, queue lengths, and latencies are essential.
Benchmarking methodology
Goals: measure throughput, tail latency (95th/99th percentile), fairness, and scalability across concurrency levels and workload types.
Benchmark dimensions:
- Concurrency sweep: 1 to N workers/threads (N chosen based on hardware, e.g., 1–128).
- Workload types:
- Microtasks: very short tasks (e.g., 1–10 µs).
- Medium tasks: 100–1000 µs.
- Macro tasks: 1–100 ms.
- Mixed/heavy-tailed: Pareto or Zipfian distributions.
- Blocking vs non-blocking tasks.
- Arrival patterns: steady, bursty (Poisson with bursts), and adversarial patterns.
- Task locality: tasks accessing shared data vs independent tasks.
- Hardware: document CPU model, cores, hyperthreading, memory, OS, and compiler.
Measurement:
- Warm-up runs to stabilize JIT / caches.
- Multiple runs with medians and confidence intervals.
- Track throughput (tasks/sec), average latency, p95/p99 latency, and fairness (variance/stddev of per-worker completed tasks).
- Instrumentation overhead must be low or sampled.
Example executor implementations (conceptual)
- Global Random Queue
- Single shared queue; scheduler randomly picks from the front K items (reservoir sampling-like) or randomly picks an index in a bounded circular buffer.
- Pros: simple; randomness reduces head-of-line effects.
- Cons: contention on queue head/tail; scalability limited.
- Per-Worker Queue with Random Stealing
- Each worker pushes tasks to its local queue. When idle, a worker picks a random victim and attempts to steal from its queue.
- Variants: steal half, steal 1, or steal batch.
- Pros: reduces contention; scales well.
- Cons: potential for uneven load without effective stealing; randomness might pick empty victims more often.
- Random Push with Bounded Locality
- Incoming tasks choose a random worker within a small neighborhood (e.g., within same socket), improving cache locality while retaining randomness benefits.
- Pros: better cache use; less cross-socket traffic.
- Cons: needs topology awareness.
- Randomized Work Distribution with Deterministic Fallback
- Try random placement; if queue depth exceeds threshold, use deterministic balancing (round-robin or size-aware).
- Pros: combines benefits.
- Cons: added complexity.
- Lock-free Random Queue with Randomized Backoff
- Multiple producers/consumers use lock-free ring buffers; when contention detected, thread backs off using random delays.
- Pros: low-latency under low contention; backoff prevents livelock.
- Cons: tuning backoff parameters is workload-specific.
Expected performance characteristics
- Microtasks: per-task overhead dominates. Per-worker queues with random stealing typically win because they avoid global locks. Random selection from a global queue shows high contention and poor scaling.
- Medium/large tasks: randomness in placement often suffices; global queue contention is lower because tasks run longer, reducing enqueue/dequeue rate.
- Heavy-tailed workloads: stealing strategies with batch steals reduce tail latency by moving large jobs rather than many tiny ones.
- Bursty arrival: randomized backoff and randomized admission control smooth spikes.
Example benchmark results (illustrative)
| Strategy | Throughput (tasks/s) | Avg Latency | p99 Latency | Scalability |
|---|---|---|---|---|
| Global Random Queue | Low | Low→High variance | High | Poor |
| Per-Worker + Random Steal | High | Low | Moderate | Good |
| Random Push (locality) | High | Low | Low-Moderate | Very Good |
| Random + Deterministic Fallback | High | Low | Low | Very Good |
| Lock-free + Backoff | Moderate | Low | Moderate | Good |
Practical tuning tips
- Use thread-local PRNGs (xoshiro/xorshift) seeded at start to avoid contention.
- For per-worker queues, prefer dequeues from head and local pushes to tail to support LIFO for locality and FIFO for steals.
- Adjust steal batch sizes based on task size distribution: larger batches for heavy tasks.
- Limit global queue operations under high concurrency; prefer local-first strategies.
- Monitor and adapt: dynamically switch strategies when queue depths or latencies cross thresholds.
Observability and diagnostics
Key metrics to expose:
- Queue lengths per worker
- Steal attempts vs successes
- Task completion counts per worker
- Per-task latencies (histograms)
- CPU and cache-miss counters (if available)
Use these to detect hotspots, frequent empty-victim selection, or starvation.
Case studies
- Web server with short request handlers: per-worker queues with random stealing reduced 99th-percentile latency by ~3x compared with a global random queue.
- Background job processor with heavy-tailed jobs: batch stealing reduced task completion variance and cut tail latency for large jobs.
- NUMA system: random push within socket neighborhoods preserved cache locality and improved throughput by 20% over fully random placement.
When not to use randomness
- Real-time systems with strict deterministic guarantees.
- Workloads that require strict priority ordering.
- When cache-affinity and data locality override benefits of randomized load distribution (unless locality-aware randomness is used).
Conclusions
Random Executor strategies provide a lightweight, robust way to distribute work under high concurrency. Their success depends on careful engineering: choosing the right queue layout, PRNG, steal policy, and locality-awareness. Benchmarks should cover diverse workloads and use robust metrics (p99 latency, fairness, steal success) to guide tuning. In practice, hybrids — combining random selection with locality constraints and deterministic fallbacks — often deliver the best balance of throughput, low tail latency, and fairness.
Leave a Reply