Affinity Tailor: Dynamic Locality-Aware Scheduling at Scale

Affinity Tailor is a userspace-guided kernel scheduling system that improves locality and throughput on large multicore systems by treating dynamic, demand-sized CPU sets as soft affinity hints rather than hard partitions, thereby balancing resource utilization with microarchitectural efficiency.

The Gist

Imagine a massive, high-tech kitchen with hundreds of chefs (the CPU cores) and a limited number of stoves, ovens, and prep stations (the caches and memory). In a modern data center, this kitchen is incredibly crowded. To get the most out of the expensive equipment, the head chef (the operating system scheduler) tries to keep every single stove burning by constantly shuffling different cooks between them.

This is the problem Google's paper, "Affinity Tailor," addresses. Here is the story of how they fixed it, explained simply.

The Problem: The "Hot Potato" Shuffle

In the old way of doing things (called Linux CFS), the scheduler's main rule was: "Never let a stove sit idle if there is a cook waiting to work."

To follow this rule, the scheduler would constantly grab a cook from one stove and drop them onto another one that just became free. While this kept the stoves busy, it caused a massive mess:

• The "Cold Stove" Effect: Every time a cook moved to a new stove, they had to forget the recipe they were memorizing, throw away their pre-chopped ingredients (cached data), and re-learn the layout of the new station.
• The Traffic Jam: Because cooks were constantly running back and forth across the kitchen to grab ingredients from a central pantry, the hallways got clogged. The pantry (memory bandwidth) couldn't keep up with the rush.
• The Result: Even though the stoves were "busy," the food was taking longer to cook because the chefs were wasting time resetting their stations and fighting over the pantry.

The Solution: Affinity Tailor

Google introduced a new system called Affinity Tailor. Instead of forcing cooks to jump around to keep stoves busy, they gave each cooking team a "Preferred Zone."

Think of it like this:

1. The "Soft" Fence: Instead of locking a team into a specific set of stoves (which would be a hard wall), Affinity Tailor paints a "Preferred Zone" on the floor. The system says, "Team A, please try to stay in this red zone. Team B, stay in this blue zone."
2. The Prediction: A smart manager (a userspace controller) watches how much work each team is doing. If a team usually needs 3 stoves, the manager gives them a zone with 3 or 4 stoves. If they suddenly get a huge order (a "burst"), the manager lets them spill over into the neighboring zones temporarily, but only if necessary.
3. The Benefit: Because the cooks stay in their "warm" zones, they keep their chopped ingredients and memorized recipes. They don't have to run across the kitchen to the pantry as often. The "hot" stove stays hot, and the "cold" stove stays cold for the next team that needs it.

How It Works in Real Life

The system uses two different strategies depending on the kitchen layout:

• For "Chiplet" Kitchens (Split Pantries): Some modern processors are built like a city of small neighborhoods (chiplets), each with its own pantry. Moving between neighborhoods is slow and expensive. Affinity Tailor tries to keep entire teams inside a single neighborhood so they never have to cross the bridge.
• For "Monolithic" Kitchens (One Big Pantry): In other processors, everyone shares one giant pantry. Here, the system focuses on keeping teams on specific stoves so they don't keep wiping each other's counters clean.

The Results: Speed vs. Waiting

The paper tested this in Google's real-world data centers (thousands of machines). Here is what they found:

• Faster Cooking: The system made applications run 3% to 12% faster per CPU.
• Less Waste: Because the cooks were more efficient, they needed less memory bandwidth, leading to 3% to 7% more throughput per gigabyte of memory.
• The Trade-off: There was a small downside. Sometimes, a cook had to wait a tiny bit longer in line to get into their "Preferred Zone" instead of jumping to the nearest empty stove. This increased the "scheduling latency" (the time spent waiting) by up to 17% in the worst cases.

The Big Takeaway:
The paper argues that the old rule of "never let a stove sit idle" is actually hurting performance on modern, complex hardware. It is better to let a stove sit idle for a microsecond so the cook can stay in their "warm" zone and cook faster, rather than shuffling them to a "cold" zone to keep the stove busy.

In short: Affinity Tailor stops the chaotic shuffle, lets teams stay in their comfort zones, and lets the kitchen run smoother and faster.

Technical Summary

1. Problem Statement

Modern hyperscale datacenters face a fundamental conflict between economic efficiency and microarchitectural performance:

• Overcommitment & Multi-tenancy: To minimize Total Cost of Ownership (TCO), cloud providers aggressively overcommit resources, running hundreds of disparate workloads on a single machine. Individual applications often request fewer CPUs than the massive core counts available (e.g., 256 cores/socket), but they are bursty and unpredictable.
• The Failure of Work-Conservation: Traditional OS schedulers (like Linux CFS) prioritize "work-conservation"—ensuring no CPU sits idle if a thread is runnable. This leads to aggressive load balancing, constantly migrating threads across the entire processor socket.
• Microarchitectural Interference: Frequent thread migration destroys "spatial locality."
  • State Pollution: Threads lose "warm" execution history, causing spikes in branch mispredictions and L1/L2 cache misses.
  • LLC Fragmentation: On chiplet-based architectures, migrating threads across chiplet boundaries forces data to traverse shared interconnects, increasing latency and saturating memory bandwidth.
  • Prefetcher Degradation: Unstable execution patterns confuse hardware prefetchers, and high memory traffic often forces the system to disable them to avoid saturation.
• Limitations of Existing Solutions:
  • Hard Partitioning (cpusets): Strictly binding threads to specific cores preserves locality but fails in overcommitted environments (causing queueing during bursts) and cannot handle the "pigeonhole" problem where requested resources exceed physical capacity.
  • Hardware-Assisted Partitioning: Existing mechanisms manage shared resources (like cache ways) but do not govern thread-to-core placement.

2. Methodology: Affinity Tailor

Affinity Tailor is a userspace-guided kernel scheduling system that treats locality as a "soft" constraint rather than a hard partition. It consists of three main components:

A. Preferred Cores (Kernel Mechanism)

A new Linux kernel mechanism that provides soft affinity via a cgroup interface.

• Core-Aware Scheduling (CAS): Inserted into the thread wakeup and load-balancing paths.
• Fast Path: When a thread wakes up, the scheduler first scans the container's dynamically assigned "Preferred Cores" mask for an idle core. If found, the thread is enqueued there immediately.
• Slow Path: If no idle core exists in the preferred set, the scheduler falls back to scanning the broader runnable cpuset (preserving work-conservation).
• Load Balancing: The kernel actively migrates threads toward idle preferred cores and prevents them from being migrated out of preferred cores unless necessary.

B. Demand-Based Dynamic Sizing (Userspace)

A userspace controller (integrated into the Borglet agent) estimates short-term CPU demand to size the Preferred Cores masks.

• Prediction Model: Instead of long-horizon ML models, it uses a trailing 5-minute p99 CPU utilization metric. This ensures the affinity region is sized to handle the vast majority of traffic without hitting the pigeonhole problem.
• Burst Buffer: The algorithm intentionally over-allocates cores slightly (scaling factor) to create a buffer for microsecond-scale bursts, preventing threads from spilling immediately to shared regions.

C. Topology-Aware Allocation Algorithms

Two distinct algorithms assign disjoint affinity regions based on hardware architecture:

1. Algorithm 1 (Split-LLC/Chiplet Systems):
   • Granularity: Allocates in units of chiplets.
   • Strategy: Minimizes the number of chiplets required to satisfy demand. It uses a combinatorial search to find the smallest set of chiplets that fits a workload, prioritizing sets with the most residual capacity for bursting.
   • Goal: Eliminate cross-chiplet memory traffic.
2. Algorithm 2 (Monolithic-LLC Systems):
   • Granularity: Allocates in units of individual cores.
   • Strategy: Calculates a per-socket scaling factor based on the ratio of available cores to total predicted demand. It assigns disjoint sets of cores to applications to maximize L1/L2 cache and branch predictor retention.

3. Key Contributions

• Preferred Cores Mechanism: A novel Linux kernel feature enabling cgroup-based soft affinity that maintains work-conservation while biasing placement toward locality.
• Dynamic Sizing System: A userspace system that dynamically sizes affinity regions using short-horizon demand predictions (p99 utilization) rather than static limits.
• Production Deployment: Successful deployment across Google's global fleet on four distinct server platforms (three split-LLC, one monolithic-LLC).
• Paradigm Shift: Empirical evidence that aggressive load balancing is detrimental on modern hardware, and that accepting minor queueing delays to preserve microarchitectural state yields net performance gains.

4. Evaluation Results

Deployed on thousands of machines over one week, Affinity Tailor showed significant improvements:

• Throughput Gains:
  • Per-CPU: Geometric mean throughput increase of 12% on chiplet-based systems and 3% on non-chiplet systems compared to Linux CFS.
  • Per-GB Memory: Throughput gains of 3–7%, attributed to reduced memory residency and footprints.
• Microarchitectural Improvements:
  • Branch Prediction: Reduced Branch MPKI (Misses Per Kilo-Instruction) by up to 2.2%.
  • LLC Efficiency: On split-LLC systems, LLC Miss Rates dropped by 7–26%. On monolithic systems, LLC RPKI (References) decreased, indicating better L1/L2 retention.
  • Memory Bandwidth: Reduced high-percentile (P90/P99) memory bandwidth utilization. This allowed hardware prefetchers to remain active longer (instead of being disabled due to saturation), further improving performance.
• Preferred Core Residency (PCR):
  • On chiplet systems, 72% of CPU time achieved >60% residency, and 60% achieved >80% residency.
• Trade-off (Scheduling Latency):
  • P99 scheduling latency increased by up to 17% due to threads waiting for preferred cores to become free. However, the paper argues this "queueing penalty" is outweighed by the execution speedup gained from a "warm" microarchitectural state.

5. Significance and Future Directions

• Rethinking Scheduling Goals: The paper challenges the dogma that "work-conservation" (zero idle time) is the primary goal of schedulers. It argues that for modern, stateful hardware, spatial locality should be a first-class objective, even at the expense of immediate queueing.
• Scalability: Unlike previous microsecond-scale schedulers that require custom runtimes or kernel bypass, Affinity Tailor works transparently within the standard Linux kernel, making it viable for warehouse-scale deployment.
• Future Work:
  • Unified Algorithms: Combining the chiplet-granularity and core-granularity approaches into a hierarchical allocator.
  • Semantic Awareness: Leveraging userspace metadata to apply locality heuristics only to state-heavy, compute-bound workloads, while allowing stateless/network-bound services to load-balance aggressively.
  • Hardware Evolution: Suggesting future hardware designs might need to support rapid state recovery or explicitly accommodate OS scheduling realities.

In conclusion, Affinity Tailor demonstrates that by dynamically steering threads to "warm" cores based on short-term demand, datacenters can significantly improve throughput and efficiency without sacrificing the flexibility required for overcommitted, multi-tenant environments.