concurrencyパフォーマンスrust

読み取り中心のワークロードにおけるRwLockのパフォーマンスオーバーヘッド

読み取り中心のワークロードではRwLockはロックフリーのアトミック操作に敗れた。記事は2つのバージョンを構築し、ベンチマークを行い、そのコストがロック自体よりも同期がどこでどれだけ頻繁に発生するかにある理由を説明する。

pranitha.devPranitha Madapathi約 8 分

日本語
中文日本語
コピー

2026-10-05

以前インターンの面接で、自分がやったプロジェクトの話をした。あるサービスでロックフリーなデータ構造を使った、と伝えたとき、面接官がこう返してきた。みんなロックフリーって言うけど、それがどれくらい効くのかは分からないんだよね。

もっともな指摘だ。ロックを使うかロックフリーにするかに正解はない。何を同期するのか、データをどれくらい頻繁に更新するのか、読み取りのパターンがどうなっているのかで決まる。

以下は、自分が両方を試したある場面を単純化したものだ。

データモデル

当時、それなりに複雑なリレーショナルデータモデルを扱っていた。その中で読み書きが必要だった最小のコアデータ構造がこれだ。

struct Data {
    index: u32,
    metrics: Metrics, // mutable
    // other mutable/immutable fields
}

type Store = HashMap<u32, Arc<Data>>; 
type Block = Vec<Arc<Data>>; // Arc<Data> is a ref of data in `Store`

Store は ID ごとに Data を保持し、各 Block は一部の ID への参照を持つ。

このサービスは読み取りが多く、書き込みは少ない。読み取りリクエストはどれも Block の全要素を走査し、その上で何らかの計算をする。読み取りは並行して行われる。

書き込みはスレッドが1本だけで、Store の中のデータを更新し続ける。

データを書き換える

書き込みのたびに、Metrics の値を丸ごと差し替える必要がある。方法は2つ考えられた。RwLock で包むか、値をアトミックに差し替えるかだ。

RwLock

読み取りが多く書き込みが1本という場面では、読み書きロックがまず最初に浮かぶ。

use parking_lot::RwLock;

struct Data {
    index: u32,
    metrics: RwLock<Metrics>,
}

fn read(block: &Block) -> u32 {
    let mut max_count = 0;

    for data in block {
        max_count = max_count.max(data.metrics.read().count);
    }

    max_count
}

fn write(store: &Store, index: u32, metrics: Metrics) {
    *store[&index].metrics.write() = metrics;
}

std や Tokio にも別の RwLock 実装はあるが、parking_lot を選んだ。std::sync::RwLock は読み取りと書き込みの優先順位を OS に委ねる。一方 tokio::sync::RwLock は非同期で、取得時に yield する可能性がある。こちらの走査は同期的な計算で、要素を取るたびに yield したくはなかった。だから parking_lot のほうが適していた。

Crossbeam Atomic

もう一つの方法は、イミュータブルな Metrics の値をアトミックポインタの後ろに置くことだ。読み取り側は現在のポインタをロードし、書き込み側は新しく確保した値でそれを差し替える。

use crossbeam_epoch::{Atomic, Owned};
use std::sync::atomic::Ordering;

struct Data {
    index: u32,
    metrics: Atomic<Metrics>,
}

fn read(block: &Block) -> u32 {
    let guard = crossbeam_epoch::pin();
    let mut max_count = 0;

    for data in block {
        let metrics = data.metrics.load(Ordering::Acquire, &guard);

        // SAFETY: The epoch guard ensures the pointer remains valid
        if let Some(metrics) = unsafe { metrics.as_ref() } {
            max_count = max_count.max(metrics.count);
        }
    }

    max_count
}

fn write(store: &Store, index: u32, metrics: Metrics) {
    let guard = crossbeam_epoch::pin();
    let data = &store[&index];

    let old = data.metrics.swap(
        Owned::new(metrics),
        Ordering::AcqRel,
        &guard,
    );

    if !old.is_null() {
        // SAFETY: `old` is no longer stored in the atomic and is protected by the epoch guard
        unsafe {
            guard.defer_destroy(old);
        }
    }
}

読み取り側が Metrics をロードしている間、epoch guard がその値を読み取り側が使い終わるまで生かし続ける。

書き込み側が metrics を新しい値に差し替えても、古い値はすぐには解放されない。defer_destroy が古い値に後で drop する印を付け、まだそれを参照している読み取り側がすべて終わってから解放する。

ベンチマーク

この単純化した例のベンチマークコードはすべて Git にある。

設定

  • 読み取りスレッド：50 個の並行 Tokio タスク
  • 書き込みスレッド：1 個、毎秒 500 回の書き込み
  • ブロックサイズ：16,384
  • CPU ウォームアップ：2 秒
  • 計測時間：10 秒、5 回の実行の平均
  • マシン：Apple Silicon 搭載の MacBook Air

各読み取りタスクはループの中で read() を呼び、呼び出しごとに yield_now() を実行する。書き込みタスクは決まったレートで write() を呼び、毎秒 500 回書き込む。

結果

ベンチマーク読み取り/秒書き込み/秒p50p95p99
RwLock15.93k499.97441.42µs910.18µs1.81ms
Atomic229.07k500.0022.44µs49.84µs241.97µs

RwLock と比べて、ロックフリー版は読み取りスループットが明らかに高く、p50、p95、p99 の読み取りレイテンシもずっと低い。

一見すると、RwLock のスループットが低いのは読み書きの競合のせいに見える。だが書き込みスレッドを止めても、読み取りスループットはほとんど変わらなかった。

ベンチマーク読み取り/秒書き込み/秒p50p95p99
RwLock（書き込みあり）15.93k499.97441.42µs910.18µs1.91ms
RwLock（書き込みなし）16.01k0.00431.50µs905.85µs1.87ms

読み取りロックの取得

parking_lot は内部で AtomicUsize を使い、アクティブな読み取りスレッドの数を追跡している。読み取りロックを取得するときは、アトミックな compare-and-swap でアクティブな読み取りスレッドのカウントを増やす。解放するときは、アトミックな減算でそのカウントを減らす。

つまり、Block の1エントリに対する読み取りを単純化するとこうなる。

        reader
          |
          | read lock: readers_count + 1
          v
        read Metrics.count
          |
          | read unlock: readers_count - 1
          v
        continue

1回の論理ブロック読み取りは、これを 16,384 回繰り返す。

read one Block
  |
  +-- Block[0]      lock -> read -> unlock
  +-- Block[1]      lock -> read -> unlock
  +-- Block[2]      lock -> read -> unlock
  |
  |   ...
  |
  +-- Block[16_383] lock -> read -> unlock

ここでは、1回の走査だけで 16,384 回の読み取りロック取得と 16,384 回のロック解放が起きる。毎秒およそ 16k 回の走査だと、RwLock の内部では毎秒約 5.24 億回の更新が行われていることになる。

CPU は毎秒数十億回の演算をこなせるが、compare-and-swap やアトミックな減算といったアトミック操作は、通常の読み書きより高くつくことが多い。これらのアトミック操作は、並行更新の下でもアクティブな読み取りスレッドの数を正確に追跡しなければならず、競合がなくてもオーバーヘッドを持ち込む。

Crossbeam のアトミック読み取りが安い理由

Crossbeam の pin() 関数は、Block の走査の間ずっと現在のスレッドをある epoch に固定する。これは Crossbeam に、このスレッドが共有データにアクセスしている可能性があり、そのスレッドが使うかもしれない値は回収してはならない、と伝えていることになる。

こうすると、Block の各要素はアトミックなポインタロード1回で済み、要素ごとにアクティブリーダー数をアトミックに増減させる必要がなくなる。

pin epoch once
  |
  +-- Block[0]      atomic pointer load
  +-- Block[1]      atomic pointer load
  +-- Block[2]      atomic pointer load
  |
  |   ...
  |
  +-- Block[16_383] atomic pointer load
  |
drop epoch guard

Epoch の固定と回収自体にも簿記のオーバーヘッドはあるが、Crossbeam の epoch guard 1回とアトミックなポインタロードで RwLock のリードガード16,384個を置き換えるとなれば、効果は大きく違う。

他の選択肢

ArcSwap：ArcSwap は読みが多く書きが少ない場面でのもう一つの選択肢だ。この読み取りパターンでは、Block の各要素に ArcSwap::load() を使うと依然として要素ごとのオーバーヘッドがかかるが、Crossbeam なら Block 全体で1回固定すれば済む。

left-right：left-right は状態を2份保持し、より多くの仕事を書き側に移すことで読みスループットを大幅に高められる。我々のサービスでは、本番データセットがメモリ上で約4GBあり、この状態を複製するとメモリ使用量が目に見えて増える。Crossbeam を使う場合、スループットとレイテンシの要件はすでに満たしているので、このトレードオフを取る必要はない。

可変ブロック

我々の Metrics は頻繁に変わるが、新しいエントリが Block に追加されるのは毎秒1、2回程度だ。そこで、Vec の外側に単純な RwLock を1つかませれば十分となる。

use parking_lot::RwLock;

type Block = RwLock<Vec<Arc<Data>>>;
BenchmarkReads/sWrites/sInserts/secp50p95p99
Locked block204.40k500.011.0626.17µs52.59µs258.83µs

ここでも、Data の各 Metrics 値は Crossbeam の Atomic ポインタを使っている。挿入は頻繁ではないので、Block 自体までロックフリーにする必要はないと判断した。

結論

これらの結果は我々のワークロードに限ったもので、ロックフリーが常に速いという意味ではない。

ロックフリーにしたことで、何千もの読みロックを取得・解放するオーバーヘッドを省けた。だが、単純な RwLock を Block の外側にかぶせるだけでも同じようにうまくいくことは、我々自身が確認している。

結局のところ、問題はロックありかロックフリーかだけではない。同期がどこで、どれくらいの頻度で起きるかも同じくらい重要だ。

出典: pranitha.dev← ホームへ戻る