English | 中文

pick_fast : Lock-Free Weighted Load Balancer for Low-Latency Selection

English | 中文

Navigation

• Features
• Usage Demonstration
• Design Rationale
• API Reference
• Tech Stack
• Directory Structure
• Historical Anecdote

Features

• Lock-Free Updates: Uses AtomicU32 and Compare-And-Swap (CAS) for thread-safe weight updates without locks
• Adaptive Weighting: Implements Exponential Moving Average (EMA) to smooth latency fluctuations
• Cache Friendly: Struct alignment (#[repr(align(64))]) prevents false sharing in multi-core environments
• Flexible Strategies: Supports custom ranking strategies via the Rank trait
• Zero Allocation: All operations are allocation-free after initialization

Usage Demonstration

Typical DNS server load balancing scenario where the balancer automatically favors nodes with lower latency:

use std::net::IpAddr;
use std::sync::Arc;
use pick_fast::{PickFast, Inverse};

struct DnsServer {
  ip: IpAddr,
}

let servers = [
  DnsServer { ip: "8.8.8.8".parse().unwrap() },
  DnsServer { ip: "1.1.1.1".parse().unwrap() },
  // ... more nodes
];

// Initialize load balancer with 8 nodes and Inverse strategy
let lb = Arc::new(PickFast::<DnsServer, 8, Inverse>::new(servers));

// Select node (probabilistically favors low-latency nodes)
let node = lb.pick();
println!("Selected node: {}", node.ip);

// Update node performance (e.g., observed 50ms latency)
lb.set(node.index, 50_000); // 50ms = 50,000μs

Design Rationale

Architecture focuses on minimizing synchronization overhead and maximizing throughput.

Call Flow

graph TD
  A[Client Request] --> B["pick()"]
  B --> C[Atomic Load Total Weight]
  C --> D[Random Target Selection]
  D --> E["Linear Scan Nodes O(N)"]
  E --> F[Return Handle]

  G[Performance Feedback] --> H["set()"]
  H --> I[Calculate Target Weight via Rank]
  I --> J[CAS Update Node Weight with EMA]
  J --> K[Atomic Update Total Weight]

Core Algorithms

EMA Smoothing Formula:

New Weight = (Old Weight + Target Weight) / 2

Inverse Strategy (default):

Weight = (1 << 22) / max(Latency, 1)

This ensures:

• 256 nodes at 1μs latency won't overflow u32
• Sufficient precision to differentiate node performance

API Reference

Core Types

Key Methods

Custom Rank Implementation

use pick_fast::Rank;

pub struct MyRank;

impl Rank for MyRank {
  fn calc(latency_us: u32) -> u32 {
    // Custom weight calculation
    1_000_000 / latency_us.max(1)
  }

  fn init() -> u32 {
    1 // Initial weight for slow-start
  }
}

Tech Stack

Directory Structure

.
├── Cargo.toml          # Project configuration
├── src/
│   └── lib.rs          # Core implementation
├── tests/
│   └── main.rs         # Integration tests and chart generation
└── readme/
    ├── en.md           # English documentation
    ├── zh.md           # Chinese documentation
    ├── rank-en.svg     # English performance chart
    └── rank-zh.svg     # Chinese performance chart

Historical Anecdote

Weighted load balancing has roots in network packet scheduling. The "Weighted Round Robin" (WRR) concept was formalized in 1991 for ATM (Asynchronous Transfer Mode) networks, where heterogeneous link speeds required differential treatment.

The evolution from WRR to modern weighted random selection represents a paradigm shift: instead of deterministic slot allocation, probabilistic approaches like pick_fast offer natural load distribution. Combined with EMA smoothing—a technique borrowed from stock market technical analysis dating back to the 1960s—the algorithm adapts gracefully to varying network conditions.

Interestingly, the Compare-And-Swap primitive used here traces back to IBM System/370 in 1970, making lock-free programming concepts over 50 years old—yet they remain the cornerstone of modern high-performance concurrent systems.

About

This project is an open-source component of js0.site ⋅ Refactoring the Internet Plan.

We are redefining the development paradigm of the Internet in a componentized way. Welcome to follow us:

• Google Group
• js0site.bsky.social

pick_fast : 无锁加权负载均衡，优选低延迟节点

English | 中文

目录

• 项目特性
• 使用演示
• 设计思路
• API 介绍
• 技术堆栈
• 目录结构
• 历史小故事

项目特性

• 无锁更新：基于 AtomicU32 和 CAS 实现线程安全的权重更新，无需互斥锁
• 自适应权重：集成指数移动平均 (EMA) 算法，平滑延时波动
• 缓存友好：结构对齐 (#[repr(align(64))]) 避免多核环境下的伪共享
• 灵活策略：通过 Rank 特性支持自定义权重计算逻辑
• 零分配：初始化后所有操作无内存分配

使用演示

典型 DNS 服务器负载均衡场景，均衡器自动倾向选择延迟更低的节点：

use std::net::IpAddr;
use std::sync::Arc;
use pick_fast::{PickFast, Inverse};

struct DnsServer {
  ip: IpAddr,
}

let servers = [
  DnsServer { ip: "8.8.8.8".parse().unwrap() },
  DnsServer { ip: "1.1.1.1".parse().unwrap() },
  // ... 更多节点
];

// 初始化负载均衡器，包含 8 个节点，使用 Inverse 策略
let lb = Arc::new(PickFast::<DnsServer, 8, Inverse>::new(servers));

// 选择节点（概率性倾向低延迟节点）
let node = lb.pick();
println!("选中节点: {}", node.ip);

// 更新节点性能（例如观测到 50ms 延时）
lb.set(node.index, 50_000); // 50ms = 50,000μs

设计思路

架构核心：最小化同步开销，最大化吞吐量。

调用流程

graph TD
  A[客户端请求] --> B["pick()"]
  B --> C[原子加载总权重]
  C --> D[随机目标选择]
  D --> E["线性扫描节点 O(N)"]
  E --> F[返回 Handle]

  G[性能反馈] --> H["set()"]
  H --> I[通过 Rank 计算目标权重]
  I --> J[CAS 更新节点权重 含EMA]
  J --> K[原子更新总权重]

核心算法

EMA 平滑公式：

新权重 = (旧权重 + 目标权重) / 2

倒数策略 (默认)：

权重 = (1 << 22) / max(延时, 1)

设计保证：

• 256 节点在 1μs 延时下不会溢出 u32
• 精度足够区分节点性能差异

API 介绍

核心类型

关键方法

自定义 Rank 实现

use pick_fast::Rank;

pub struct MyRank;

impl Rank for MyRank {
  fn calc(latency_us: u32) -> u32 {
    // 自定义权重计算
    1_000_000 / latency_us.max(1)
  }

  fn init() -> u32 {
    1 // 慢启动初始权重
  }
}

技术堆栈

目录结构

.
├── Cargo.toml          # 项目配置
├── src/
│   └── lib.rs          # 核心实现
├── tests/
│   └── main.rs         # 集成测试与图表生成
└── readme/
    ├── en.md           # 英文文档
    ├── zh.md           # 中文文档
    ├── rank-en.svg     # 英文性能图表
    └── rank-zh.svg     # 中文性能图表

历史小故事

加权负载均衡起源于网络数据包调度。1991 年，"加权轮询" (Weighted Round Robin, WRR) 概念在 ATM (异步传输模式) 网络中被正式提出，用于处理异构链路速度的差异化调度需求。

从 WRR 到现代加权随机选择，代表着范式转变：从确定性槽位分配，转向概率方法实现自然的负载分布。结合指数移动平均 (EMA) 平滑——该技术源自 1960 年代的股票市场技术分析——算法能优雅地适应网络条件变化。

有趣的是，这里使用的 CAS (Compare-And-Swap) 原语可追溯至 1970 年的 IBM System/370，使得无锁编程概念已有 50 余年历史——但它仍是现代高性能并发系统的基石。

关于

本项目为 js0.site ⋅ 重构互联网计划 的开源组件。

我们正在以组件化的方式重新定义互联网的开发范式，欢迎关注：

• 谷歌邮件列表
• js0site.bsky.social