Try   HackMD

Linux 核心專題: RCU 研究和實作

執行人: JUSTUSVMOS

Reviewed by jserv

如何驗證 RCU 實作行為符合預期且具備 lock-free/wait-free 特性?

  1. 先看 RCU 讀取端的程式路徑,確認沒有用 mutex 或 spinlock 把 read 包起來,這樣 reader 才不會因為其他執行緒被卡住。
  2. 可以直接開 kernel 裡的 CONFIG_PROVE_LOCKING__rcu sparse 這些工具,讓它幫你找出同步問題或 API 用錯的地方,比較保險。
  1. 直接跑 rcutorture 或 liburcu 壓力測試,把 reader 跟 writer 數量開大,看看讀端會不會被卡住,只要 writer 再怎麼寫,讀的都能順利執行就沒問題,效能數據也可以順便看一下。

理工人員測試若只憑感覺、沒辦法拿出理論和量化分析,該如何保證品質呢?
使用本課程教材對於並行處理的分析方式,來探討上述問題。

解說錄影呢?

TODO: 研讀 RCU 教材和學習 Userspace RCU

紀錄閱讀課程教材 (以第一手材料為主) 過程中遇到的疑惑,充分討論
在自己的電腦上準備 Userspace RCU (URCU) 函式庫並進行評估,注意不得使用虛擬機器

TODO: 重作第 15 週測驗題及其延伸題目

  1. 解釋給定程式碼的原理,指出其缺失並予以改進
  2. 開發得以搭配 Userspace RCU 和測驗題程式碼運作的效能評比程式,量化在高度並行場景的效能表現
  3. 改進測驗題程式碼,運用於高度並行的 Valkey 實作,並評估其效能表現,隨後指出改進方案

解釋給定程式碼的原理,指出其缺失並予以改進

1. 批次更新(Batching)

1-1 原理

writer thread(N 個)                reader thread(M 個)
───────────────────                ─────────────────────
loop {                              loop {
   ① atomic_exchange(ptr)              rcu_read_lock()
      → 舊指標丟進 batch[]              ···讀資料···
                                       rcu_read_unlock()
   ② if batch 滿 或 超時
        ┌────────────── flush ───────────────┐
        │ a) synchronize_rcu();              │
        │ b) free(batch[0..cnt-1]);          │
        │ c) batch_cnt = 0;                  │
        └────────────────────────────────────┘
}

為什麼快?

  • 舊版:每筆更新都跑一次 synchronize_rcu() → 一次 GP ≅ 0.6–1 ms。
  • 批次版:預設 256 筆或 5 ms 才跑一次 GP。
    在 20 µs 更新頻率下,GP 次數從每秒 ~800 次降到 ~40 次;寫端阻塞時間大幅減少。

為什麼安全?

  • RCU 只要求:「被淘汰的指標釋放前,所有當前 reader 都已離開臨界區」。
  • 批次版仍在 free() 前執行 一次 synchronize_rcu(),故滿足語義;
    不管累積了 2 筆還是 200 筆,只要 free 之前做過 GP,就不會出錯

1-2 程式碼

1-2-1 批次參數與 thread-local 變數
#define BATCH_SIZE   256          // 滿 256 筆就 flush
#define BATCH_USEC   5000         // 或超過 5 ms 也 flush

static __thread uint64_t *batch[BATCH_SIZE];
static __thread int       batch_cnt       = 0;
static __thread uint64_t  last_flush_us   = 0;

每個 writer thread 各自維護一組陣列與計數器,避免鎖競爭。

1-2-2 取得單調遞增時間
static inline uint64_t now_us(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (uint64_t)ts.tv_sec * 1000000ULL + ts.tv_nsec / 1000ULL;
}

CLOCK_MONOTONIC 避免被 NTP、date 調整影響。

1-2-3 批次 flush 核心
static void batch_flush(void)
{
    if (batch_cnt == 0)
        return;                         // 沒東西就跳過

    synchronize_rcu();                  // ◎ 唯一昂貴步驟:等待 GP

    for (int i = 0; i < batch_cnt; i++) // 現在 reader 全退出
        free(batch[i]);                 // 安全釋放

    batch_cnt      = 0;                 // 重置迴圈
    last_flush_us  = now_us();
}

安全性重點free() 緊跟在 synchronize_rcu() 之後,永遠不會早於 GP。

1-2-4 改寫 update_global_state()(Writer 快路徑)
static void update_global_state(void)
{
    uint64_t *new_state = malloc(sizeof(*new_state));
    *new_state = 5;                                     // 新內容

    uint64_t *old_state =
        atomic_exchange_explicit(&global_shared_state,
                                 new_state,
                                 memory_order_release); // ★ publish

    if (old_state)                                      // 舊指標進批次表
        batch[batch_cnt++] = old_state;

    if (batch_cnt == BATCH_SIZE ||                      // 數量門檻
        now_us() - last_flush_us >= BATCH_USEC)         // 時間門檻
        batch_flush();                                  // → GP+free
}
  • atomic_exchange(..., memory_order_release)

    • release:保證先寫入 *new_state,再讓其他 CPU 看到指標;
      reader 用 acquire/consume load 就能正確讀到資料。*
  • push → flush

    • 只做 O(1) 陣列 push,極輕量。
    • 進入 flush 時才真正阻塞。*
1-2-5 Writer 執行緒結束前的保險 flush
static void *updater_func(void *arg)
{
    while (!exit_flag) {
        update_global_state();
        usleep(update_interval_us);      // user-side負載節流
    }

    batch_flush();                       // 結束前把殘餘指標回收
    ...
}

確保程式結束時不留下尚待回收的記憶體。

1-2-6 Reader 臨界區(未改動)
rcu_read_lock();
uint64_t *p   = atomic_load_explicit(&global_shared_state, memory_order_acquire);
uint64_t  val = *p;                                  // 真正讀資料
asm volatile("" : : "r"(val) : "memory");            // 防 DCE
rcu_read_unlock();
  • 使用 memory_order_acquire 對應 writer 的 release,確保指標→資料順序。
  • 其餘 lock/unlock 仍僅是兩個 atomic_signal_fence(seq_cst),成本極低。*
1-2-7 Fence F 仍保留「兩半 GP 分割」
/* Fence F – closes first half of grace period. */
heavy_fence_seq_cst();   // membarrier:舊世界終點

無論批次與否,真正進入 GP 時仍需 一次 membarrier 來截斷 A/F、C/F 之間的潛在亂序。

1-2-8 從 gp_holdouts futex 等待返回後的 Fence H
/* Fence H – pairs with Fence D. */
atomic_thread_fence(memory_order_seq_cst);

確保「所有 reader 退出」→「釋放資料」有全域 SC 順序。

1-3 效能與延遲摘要

指標(32R╳8W, 20 µs) 每筆即 GP 批次 256/5 ms 說明
Updater 迴圈 /3 s ~45 ~2500 ↑約 60 倍
平均 GP 延遲 60–90 ms 0.8–1 ms ↓約 70 倍
Reader 吞吐 3–5×10⁸ 3–5×10⁸ 幾乎不變

2. 批次 + 延遲回收(Batching + Deferred Callback)

2-1 整體原理快速圖解

更新指標 ─▶┌───────────── Writer Thread (多個) ───────────────┐
           │ ① atomic_exchange() 把舊指標拿下來                │
           │ ② push 到 thread-local batch[ ]                 │
           │ ③ batch 滿 / 逾時 → batch_flush() ─────────────┐ │
           └───────────────────────────────────────────────│─┘
                                                           │
                                                           ▼
                                                      call_rcu()
                                      ┌──────────────────────────────────┐
                                      │      全域 MPSC 佇列 cb_head      │
                                      └──────────────────────────────────┘
                                                      │ (pop-all)
                                                      ▼
                          ┌────────────────────────────────────────────┐
                          │         Reclaimer Thread (唯一)            │
                          │ a. 偷走整批 callback list                   │
                          │ b. synchronize_rcu() → 1 次 GP             │
                          │ c. 逐一執行 c->func(c->arg) (free 指標)     │
                          └────────────────────────────────────────────┘

  • 批次(thread-local batch)
    把大量寫入先累積起來,一次 batch_flush() 送到全域佇列,降低每筆寫入的 CAS 次數與記憶體屏障。

  • 延遲回收(call_rcu + reclaimer)
    Writer 永遠不自己跑 GP;真正的 synchronize_rcu() 只在背景 reclaimer 執行緒中發生,寫端完全非阻塞。

2-2 程式碼

2-2-1 thread-local 批次 (L1)
#define BATCH_SIZE 256
static __thread uint64_t *batch[BATCH_SIZE];
static __thread int       batch_cnt = 0;       // 已累積幾個
static __thread uint64_t  last_flush_us = 0;   // 上次 flush 的時間戳

每位 writer 都有自己的小池子;Writer path 只有 push 陣列,無鎖、無系統呼叫。

2-2-2 更新邏輯 (writer fast-path)
static void update_global_state(void)
{
    uint64_t *new_state = malloc(sizeof(*new_state));
    *new_state = 5;                               // 示範資料

    uint64_t *old_state =
        atomic_exchange_explicit(&global_shared_state, new_state,
                                 memory_order_release);

    if (old_state)                // ≈50 ns
        batch[batch_cnt++] = old_state;

    if (batch_cnt == BATCH_SIZE ||
        now_us() - last_flush_us >= BATCH_USEC)
        batch_flush();
}

1 筆更新 → 1× atomic_exchange + 1× push;絕大多數讀者場景耗時 < 100 ns。

2-2-3 batch_flush()──把 L1 丟進 L2
static void batch_flush(void)
{
    if (batch_cnt == 0) return;

    for (int i = 0; i < batch_cnt; i++) {           // L1 → L2
        struct rcu_cb *cb = malloc(sizeof(*cb));    // callback wrapper
        call_rcu(cb, free, batch[i]);               // 延遲 free()
    }
    batch_cnt     = 0;
    last_flush_us = now_us();
}

此時 沒有 GP;Writer flush 完立即返回,繼續衝下一批。

2-2-4 call_rcu()──MPSC lock-free push
static _Atomic(struct rcu_cb *) cb_head = NULL;

static void call_rcu(struct rcu_cb *c, void (*fn)(void *), void *arg)
{
    c->func = fn;           // 通常 = free
    c->arg  = arg;

    struct rcu_cb *old;
    do {
        old       = atomic_load_explicit(&cb_head, memory_order_relaxed);
        c->next   = old;
    } while (!atomic_compare_exchange_weak_explicit(
                 &cb_head, &old, c,
                 memory_order_release, memory_order_relaxed));
}

單純「把新節點掛到頭」的 CAS;保證 push 前的寫入對 reclaimer acquire 可見。

2-2-5 reclaimer_fn()──偷走→GP→free
while (!stop_reclaimer) {
    /* pop-all : 把佇列歸零並取得舊 head */
    struct rcu_cb *list = atomic_exchange_explicit(&cb_head, NULL,
                                                   memory_order_acquire);
    if (!list) { usleep(200); continue; }

    /* reverse 為 FIFO;保持原寫入時間順序 */
    struct rcu_cb *rev = NULL, *n;
    while (list) { n=list->next; list->next=rev; rev=list; list=n; }

    synchronize_rcu();          // ----► 只跑一次 GP

    while (rev) {               // 逐一清理
        struct rcu_cb *c = rev; rev = rev->next;
        c->func(c->arg);        // free(old_state)
        free(c);                // 釋放 wrapper
    }
}

背景執行緒把所有 callback 一口氣 搬走,一次 GP 就釋放整批。
GP 數量 = callback 佇列清空次數,遠低於寫入頻率。

2-2-6 啟動與關閉 reclaimer(main() 中)
pthread_create(&reclaimer_th, NULL, reclaimer_fn, NULL);
/* … 整個壓力測試 … */
stop_reclaimer = true;
pthread_join(reclaimer_th, NULL);

2-3 記憶體順序保證

務必使用課程規範的術語,見 https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics
不要依賴大語言模型來產生內容,以課程教材和 Linux 核心第一手材料為主

路徑 主要 atomic operation 為何安全
Writer push L1 → L2 call_rcu()store-release(CAS 成功) 保證 舊指標內容 先於 cb_head 更新對 reclaimer 可見
Reclaimer 取得 list exchange-acquire 讀到最新 list 之後,能看到所有節點 arg 實體
GP 之前 不得 free synchronize_rcu() 強制等待所有 reader 離開舊世界 符合 RCU 安全定義
GP 之後 free() Reader 此時最早也看到新指標,不會再解參考舊指標 無 use-after-free

  1. Writer zero-blocking
    flush 不再 synchronize_rcu();背景 GP 與 writer 解耦。
  2. 兩級批次
    L1 (thread-local) → 降低 CAS 與共享寫流量;
    L2 (global stack) → 把 N×GP 壓成 1×GP。
  3. 單 GP 釋放一大批
    reclaimer 每秒只跑 10–50 次 membarrier,即使寫入頻率百萬級也撐得住。

3. GP Coalescing(Grace-Period 合併)

3-1 原理總覽──為何「GP 合併」能再提速

Writer (多個) ──►  call_rcu(cb)       ┌────────────┐
                                     │  全域 stack │ ← lock-free, MPSC
                                     └────────────┘
                                                │
Reclaimer (唯一) ──►  pop-all → ① 累積 batch[ ]         │
                                   ② if 256 筆 or 5 ms │
                                   ③ synchronize_rcu() │  ← 只跑一次 GP
                                   ④ 逐一 free(arg)   ▼
  • 舊法:每筆 call_rcu() 就對應一次 GP(或小批次)。
  • 改版
    reclaimer 先把 所有 callback 偷進 batch[256]
    滿 256 筆或逾 5 ms 才 一次 GP + free()
    GP 次數理論上 ≈ (寫入次數 / 256),寫端完全非阻塞。

3-2 重要參數

巨集 作用 預設
COALESCE_BATCH_SIZE 單批最多 callback 256
COALESCE_TIMEOUT_US 最長等待時間 5000 µs

3-3 程式碼

3-3-1 call_rcu() — lock-free MPSC push (L43)
do {
    old     = atomic_load_explicit(&cb_head, memory_order_relaxed);
    c->next = old;
} while (!atomic_compare_exchange_weak_explicit(
             &cb_head, &old, c,
             memory_order_release, memory_order_relaxed));
  • store-release:保證 callback 內容先寫好,再讓 reclaimer 看見新 head。
  • 單 CAS → Writer path 成本 ≈ 50 ns。

3-3-2 Reclaimer 主迴圈 (L68)
struct rcu_cb *list = atomic_exchange_explicit(&cb_head, NULL,
                                               memory_order_acquire);
  • exchange-acquire:偷走整條 stack,一次歸零;之後能讀到每個 cb->arg
  • 沒偷到東西時 usleep(200),避免忙迴圈。

3-3-3 Batch 累積 + 超時判定 (L71-77)
while (list && cnt < COALESCE_BATCH_SIZE) { ... }
bool timeout = (now_us() - last) >= COALESCE_TIMEOUT_US;
if (cnt == COALESCE_BATCH_SIZE || timeout)
    ...  // 同批執行 GP
  • 兩種門檻:數量 or 時間,保證最長延遲 ≤ 5 ms。
  • now_us()CLOCK_MONOTONIC,不受 NTP 影響。

3-3-4 批次 GP + free (L78-83)
synchronize_rcu();                /* ◎ 僅此一次昂貴 GP */
for (unsigned i = 0; i < cnt; i++) {
    batch[i]->fn(batch[i]->arg);  /* 通常 = free(ptr) */
    free(batch[i]);               /* 釋放包裝 */
}
cnt = 0;  last = now_us();
  • 安全性要點free() 永遠排在 GP 之後,符合 RCU 語意。
  • 實務上 256 筆 × 8 bytes ≈ 2 KB → 批次成本極低。

3-3-5 Reclaimer 收尾 (L87-97)
  • stop_reclaimer 置真後,再把殘餘 callback 清完;避免洩漏。

3-3-6 Updater 路徑 (L121-134)
uint64_t *oldp = atomic_exchange_explicit(&global_shared_state,
                                          newp, memory_order_release);
if (oldp) {
    struct rcu_cb *cb = malloc(sizeof(*cb));
    call_rcu(cb, free_cb, oldp);
}
  • Writer 不再自己 batch+GP,而是直接交給 call_rcu()
  • 讓「資料結構更新」與「回收舊指標」完全解耦。

3-3-7 Thread-local 統計 (L106, 139)
  • __thread unsigned long long iterations:量化每執行緒工作量,便於觀察效能。

3-3-8 測試參數解析 (L147-158)
  • -r/-u/-t/-i:可快速調換 Reader/Updater 數與更新間隔,驗證不同負載下 GP 合併效果。

3-4 記憶體順序總表(改版特有路徑)

務必使用課程規範的術語,見 https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics
不要依賴大語言模型來產生內容,以課程教材和 Linux 核心第一手材料為主

路徑 主要atomic operation 保證
Writer → cb_head CAS release callback 內容對 reclaimer 可見
Reclaimer 偷 list exchange-acquire 看到每個 cb 內 arg 的最新值
Reclaimer → free() synchronize_rcu() Reader 不再持有舊指標,避免 UAF

3-5 實測建議指標

測項 觀察重點
Avg/Max GP 間隔 應落在 5 ms 以內,除非寫入頻率極低
Updater p99 latency 理想值 ≈ atomic_exchange + malloc ≈ 200 ns
Reclaimer CPU 占用 高频寫入時大幅低於「每筆 GP」版本

寫端阻塞 ≈ 0,GP 數量取決於「匯入速度」vs 「批次門檻」。
如需再壓縮延遲,可改成 動態 BATCH_SIZE(根據 cb 積壓量調整)。


3-6 這版比上一版強在哪?

  1. 寫端零 GPsynchronize_rcu() 全在背景執行緒,不再打斷 Updater。
  2. 一次 GP 釋放 256 筆:GP 成本被 256 倍攤提
  3. 最長延遲 5 ms:兼顧高頻寫入與可控回收時限。

4. 效能評估與比較

開發環境

pkg-config --modversion liburcu
Linux carpenter666-NUC10i7FNH 6.11.0-26-generic #26~24.04.1-Ubuntu SMP PREEMPT_DYNAMIC Thu Apr 17 19:20:47 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
PRETTY_NAME="Ubuntu 24.04.2 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.2 LTS (Noble Numbat)"
VERSION_CODENAME=noble
CPU(s):                               12
On-line CPU(s) list:                  0-11
Model name:                           Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
Thread(s) per core:                   2
Socket(s):                            1
CPU(s) scaling MHz:                   16%
CPU max MHz:                          4700.0000
CPU min MHz:                          400.0000
NUMA node0 CPU(s):                    0-11
               total        used        free      shared  buff/cache   available
Mem:            23Gi       5.3Gi        12Gi       557Mi       6.8Gi        17Gi
Swap:          8.0Gi          0B       8.0Gi
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39
liburcu 0.14.0

實驗影片

4-1 實驗設計與流程

本次實驗以 32 個 reader、8 個 updater 執行緒為測試架構,統一測試時間 3000 ms,採用不同的 updater interval(-i)參數,觀察四種 RCU 優化版本的寫入與讀取效能。

測試參數 數值
Readers 32
Updaters 8
測試時間 3 秒
Updater 間隔 -i 1、2、5、20、100 μs
  • main:每筆寫入都同步一次 GP
  • main_delay:每筆寫入加上 usleep 間隔後執行 GP
  • main_batch:延遲回收,累積 256 筆或 5ms 一次 GP(寫端負責)
  • main_gpc:寫端僅送 callback,GP 由單一 reclaimer thread 合併處理

4-2 數據總表與曲線圖

4-2-1 Updater / Reader Throughput 統計(每 3 秒)

改進以下:

  1. 實驗環境的描述
  2. 實驗方法
  3. 實驗的檢討
  4. 附上對應的展示影片,確保是自己進行的實驗
版本 -i=1 μs -i=2 μs -i=5 μs -i=20 μs -i=100 μs
main ~107 / 3.27e9 ~107 / 2.96e9 ~104 / 2.96e9 ~95 / 2.96e9 ~103 / 2.96e9
delay 120,147/2.69e9 118,031/2.67e9 113,834/2.70e9 93,502/2.72e9 48,012/2.80e9
batch 7,604/2.94e9 7,870/2.95e9 7,244/2.94e9 6,313/2.96e9 2,868/2.95e9
gpc 118,740/2.67e9 117,447/2.66e9 112,167/2.68e9 91,890/2.71e9 47,948/2.79e9

(單位:Updater 次/3秒 / Reader 次/3秒;科學記號 e.g. 2.96e9 = 2,960,000,000)

throughput_both

圖:各 RCU 策略下,隨 updater 間隔 -i 改變,Updater 與 Reader 吞吐量的變化(橫軸 log 標示)

4-2 重點觀察

  1. main(每筆都同步 GP)

    • Updater throughput 長期受限,每 3 秒僅能做數十次更新,主因為每筆都要同步一個長 GP(60–90ms)。
    • Reader throughput 維持高水準,受寫端影響極小。
    • 嚴重不適合高頻寫入。
  2. main_delay(每筆 usleep + GP)

    • Updater throughput 明顯提升(達數萬等級),因 usleep 休眠遠大於 GP 時間,GP 開銷被藏在排程延遲內。
    • Reader throughput 與 main 類似。
    • 若 usleep(-i)縮短到小於系統定時粒度,updater 速度會再被 OS 實際排程限制(如 2μs 實際睡 60μs)。
  3. main_batch(累積批次 GP)

    • Updater throughput 約落在數千級,明顯優於 main,但低於 main_delay/gpc。
    • 原因:每累積 256 筆才做一次 GP,但 flush、malloc 等仍有 overhead。
    • Reader throughput 穩定。
  4. main_gpc(延遲回收+reclaimer 合併 GP)

    • Updater throughput 可逼近 main_delay,甚至更高(因 GP 全部由背景 reclaimer 集中執行)。
    • Reader throughput 保持高檔。
    • 在 -i 極小時,main_gpc 才能進一步展現高頻寫端效能上限。

4-4 各機制比較與適用場景

機制 Updater 吞吐 Reader 吞吐 GP 開銷主控點 適用場景
main 最差 每筆更新後執行 低頻寫,高頻讀
main_delay 極佳(看 -i) usleep > GP 寫端負載中等
main_batch 普通 256 筆合併一次 GP 間歇高頻寫
main_gpc 最佳 寫端僅送 callback 高頻寫、低延遲
  • 若寫端很密集、要求可擴展性,建議採用 main_gpc。
  • 若系統以讀端為主、寫端較少,可用 main 或 main_batch 。
  • main_delay 僅適合在更新頻率本就低、usleep 延遲大於 GP 延遲的場合。

開發得以搭配 Userspace RCU 和測驗題程式碼運作的效能評比程式,量化在高度並行場景的效能表現

5-1. 實驗設計與方法

承接前章 mini-RCU 四個版本(main、delay、batch、gpc)的測試架構,本章新增參考實務界廣泛應用的 Userspace RCU (liburcu) 進行同場壓力測試。
測試條件完全一致(32 reader、8 updater、3 秒、-i 1/2/5/20/100),確保能直接比較不同實作的真實吞吐極限與行為。

5-1-1 測試版本摘要
版本 實現方式簡述
main 每筆寫入即同步 GP
delay 每筆寫入前 usleep,仍每筆 GP
batch 累積 256 筆/5ms,批次 GP
gpc 寫端僅送 callback,集中合併 GP
liburcu 官方 API,call_rcu 與 rcu_read_lock 典型用法

5-2. 測試結果總表

版本 -i=1 -i=2 -i=5 -i=20 -i=100 讀端吞吐 (範例)
main 109 106 106 116 104 3.2e9
delay 119,716 119,010 113,491 92,655 47,925 2.7e9
batch 7,786 8,101 7,410 5,515 2,720 2.9e9
gpc 117,598 115,839 111,514 91,508 47,741 2.6e9
liburcu 116,591 116,232 111,783 91,775 47,807 3.99e8

單位:Updater 次/3秒,Reader 次/3秒(科學記號 e.g. 3.2e9 = 3,200,000,000)

throughput_both_professional

文字訊息不要用圖片展現,確認圖片的存取權限

5-3. 主要觀察
  1. 寫端效能比較

    • liburcu 與 gpc 兩者寫入吞吐極為接近,尤其在 -i 1/2/5/20/100 µs 各級都能維持在十萬級別,說明只要將 GP 徹底 decouple,user-level 實作亦能達到專業函式庫極限。
    • main 版僅百次等級,batch 僅數千,效能落差明顯。
    • delay 在 usleep 主導下也能達到極高寫入效能,但理論上限受排程粒度影響。
  2. 讀端效能比較

    • liburcu 讀端吞吐量明顯高於所有自製版本,最高約 3.99e8,反映其 QSBR/MEMBARRIER 等高效讀端設計。
    • mini-RCU 各版本讀端雖也維持 2.5e9 以上,但在極高並發下可能受到臨界區、鎖存、fence 等機制影響而有微幅落差。
  3. 寫入/讀取雙極限情境

    • 若同時要求寫入高頻與讀端超高吞吐,liburcu 仍有整體最佳可擴展性與穩定性。
    • gpc 版雖已充分 decouple GP,但在部分排程與記憶體同步細節上仍可能落後 liburcu 一小段距離。

改進測驗題程式碼,運用於高度並行的 Valkey 實作,並評估其效能表現,隨後指出改進方案

1. 目標

編號 目標敘述
G1 把自製 mini-URCU hash table 以 Module 方式植入 Valkey,驗證「讀多寫少」場景能否 降低延遲、提升吞吐
G2 與 Valkey 原生 SET/GET 進行 定量比較(ops/sec、avg / p95 / p99 latency)。
G3 探索 桶數GP 批次回收 (GPC) 對寫入效率的影響,提出最佳化指引。

2 核心實作

2-1 mini-URCU Hash-Table(rcu_ht.c

/* ① 建表:2^pow2 個 bucket,各自一把 mutex */
struct rcu_ht *ht_create(unsigned pow2)
{
    size_t n = 1ULL << pow2;
    struct rcu_ht *ht = calloc(1, sizeof *ht);
    ht->nb = n;
    ht->b  = calloc(n, sizeof(struct bucket));
    for (size_t i = 0; i < n; i++)
        pthread_mutex_init(&ht->b[i].mtx, NULL);
    return ht;
}

/* ② 寫入:Copy-Update → rcu_assign_pointer → call_rcu() 延遲 free */
int ht_insert(struct rcu_ht *ht, const char *k, const char *v)
{
    struct node *n = malloc(sizeof *n);
    n->k = strdup(k);
    n->v = strdup(v);

    size_t i = hash(k) & (ht->nb - 1);
    pthread_mutex_lock(&ht->b[i].mtx);
    n->next = rcu_dereference(ht->b[i].head);
    rcu_assign_pointer(ht->b[i].head, n);
    pthread_mutex_unlock(&ht->b[i].mtx);
    return 0;
}

/* ③ 刪除:unlink 後 call_rcu() 回收 */
static void free_node_cb(struct rcu_head *rh)
{
    struct node *n = caa_container_of(rh, struct node, rh);
    free(n->k); free(n->v); free(n);
}
  • 讀側rcu_read_lock/unlock(),零鎖、零系統呼叫。
  • 寫側:Copy-Update + GPC —— 單一 reclaimer 執行緒每 5 ms / 256 node 觸發一次 synchronize_rcu()

2-2 Valkey 模組(rcuht_module.c

#define HT_BUCKET_POW2 17          /* 131 072 bucket  ⇒  load-factor ≈0.75 */
static struct rcu_ht *HT;

/* RCU.HT.SET key val */
int RCUHT_Set(RedisModuleCtx *ctx, RedisModuleString **argv, int argc)
{
    if (argc != 3) return RedisModule_WrongArity(ctx);
    size_t klen,vlen;
    const char *k = RedisModule_StringPtrLen(argv[1], &klen);
    const char *v = RedisModule_StringPtrLen(argv[2], &vlen);
    ht_insert(HT, k, v);
    return RedisModule_ReplyWithSimpleString(ctx, "OK");
}

/* RCU.HT.GET key */
int RCUHT_Get(RedisModuleCtx *ctx, RedisModuleString **argv, int argc)
{
    if (argc != 2) return RedisModule_WrongArity(ctx);
    size_t klen; const char *k = RedisModule_StringPtrLen(argv[1], &klen);
    char *val = ht_lookup(HT, k);
    if (!val) return RedisModule_ReplyWithNull(ctx);
    return RedisModule_ReplyWithStringBuffer(ctx, val, strlen(val));
}

/* Module 初始化 */
int RedisModule_OnLoad(RedisModuleCtx *ctx, RedisModuleString **argv, int argc)
{
    RedisModule_Init(ctx, "rcu.ht", 1, REDISMODULE_APIVER_1);
    HT = ht_create(HT_BUCKET_POW2);
    RedisModule_CreateCommand(ctx, "rcu.ht.set", RCUHT_Set, "write", 0,0,0);
    RedisModule_CreateCommand(ctx, "rcu.ht.get", RCUHT_Get, "readonly", 0,0,0);
    return REDISMODULE_OK;
}

3 實驗環境與流程

項目 規格
CPU Intel® NUC 10 i7 (8c/16t)
OS Ubuntu 24.04 LTS × Linux 6.8
Valkey commit 293be3e3 + rcuht.so
liburcu 0.14 (memb)
測試工具 valkey-benchmark (500 k req / 500 conn / pipeline 16 / key space 100 k)

啟動 command

# native 6379
./src/valkey-server --port 6379 &
# RCU-HT 6380
./src/valkey-server --loadmodule ./src/modules/rcuht.so --port 6380 &

注意用語!

4 量測結果(最終)

實作 (port) 指令 Throughput (ops/s) Avg Latency (ms)
RCU-HT :6380 GET 902 527 7.95
SET 145 349 0.70
Native :6379 GET 1 179 245 6.01
SET 970 874 7.48

(吞吐取 rps;延遲取 avg_latency_ms,皆來自 valkey-benchmark --csv 輸出)

Throughput (ops/sec) Average latency (ms)
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

修正圖片的存取權限