Zenn
🐻

Day 1: RCUとは何か

2024/12/02に公開
Rust
ポエム
並行処理
rcu
ロックフリー
tech

1. イントロダクション

これはsanoが一人でRCU(Read Copy Update)に関する話をまとめてRustでRCUを実装をしていくアドベントカレンダーである。

25日間の記事をRCUの話題だけで書き切れるか不安だが、一つ一つの記事を読者が「面白い」「勉強になる」「わかりやすい」と思えるようなものにしていこうと思う。

以下のような流れでRCUについて深く掘り下げていく：
まずRCUとは何かという基本的な説明から入り、次に実装の土台となる並行処理の知識を解説する。
その後、これらの知識を組み合わせてRCUの動作原理を理解し、最後にRustによる実装に取り組んでいく。

12月1日の時点でsanoはRCUの実装を終えているので興味があれば実装を先取りして読んでほしい。

完成したRCUの実装:
https://github.com/ie-Yoshisaur/qsbr-rcu

また、何か質問や指摘があったらXにて指摘をしていただければ、加筆修正をするつもりなのでどうぞよろしくお願いします。

2. RCUとは何か

Read-Copy-Update(RCU)は、読み取り操作を行うスレッドをブロックすることなくデータを更新できる技術のことを指す。

元々RCUは主にLinuxのカーネル空間で広く使われている技術で、カーネル空間のRCUはカーネル空間でしかできない実装になっている。

ユーザー空間でもアルゴリズムの力でカーネル空間のRCUを再現することができる。そして、ユーザー空間で実装されたRCUは「user-space RCU」として区別されることもある。
参考: https://lwn.net/Articles/573424/

今回のアドベントカレンダーで実装するRCUは無論、user-space RCUである。

2.1. RCUの特徴

RCUの特徴をまとめると以下のようになる。

  • 読み込みの際にロックを必要としない
  • 読み込みと書き込みが互いにブロックしない

RCUでは、図のようなデータの読み書きができる。

MutexやRwLockではできない挙動がいくつもある。特にt2, t4, t5からt6までの挙動がRCUにしかできないものとなっている。

まとめるとこうなる。

時刻 状態 Mutex RwLock RCU (Read-Copy-Update)
t2 スレッド1がxを読んでいる最中にスレッド2が書き込み操作を開始する 不可能
(読み書きは排他)		 不可能
(読み取りと書き込みは排他)		 可能
(読み取りと書き込みは排他ではない)
t4 スレッド2がxを書き込んでいる最中にスレッド1が読み込み操作を開始する 不可能
(読み書きは排他)		 不可能
(読み取りと書き込みは排他)		 可能
(読み取りと書き込みは排他ではない)
t5~t6 スレッド2がxを0から1に書き換えた後でも、スレッド1がxを0として扱っている 不可能
(データは常に一貫性を保つ)		 不可能
(データは常に一貫性を保つ)		 可能
(古いデータへのポインタが維持されるため、一時的な不一致が許容される)

2.2 Mutex、RwLockとの比較

MutexとRwLockとRCUの挙動をテーブルに表現するとこうなる。

特性 Mutex RwLock RCU (Read-Copy-Update)
同時にアクセスできるスレッド数 1 （排他制御） 複数（読み取り時）
1（書き込み時）		 複数（読み取り、書き取り時）
(更新時は一つのスレッドしか更新に成功しない)
読み書きの排他性 読み取り・書き込みともに排他 読み取りは共有可能
書き込みは排他		 読み取りと書き込みは排他しない
Blocking/Non-Blocking Blocking Blocking 基本的な読み書きはNon-Blocking
(GCではBlocking)

BlockingやNon-Blockingという用語については、「Day 6: ブロッキング処理とノンブロッキング処理 ~並行処理の基礎~」で触れる予定。

丸括弧で囲われた部分も実装フェーズで必ず触れるので今はわからなくても問題なし。

※「MutexやRwLockとは？」という人は、おそらくマルチスレッドプログラミング初心者かと思われる。このアドベントカレンダーでは、MutexやRwLockの説明は省くので、一度それらの並行プリミティブでアトミックカウンタを実装してみることをお勧めする。

2.3 RCUが同時に読み書きできる理由

RCUが読み書きを同時に行えるのは、古いデータを保持し続ける仕組みがあるからである。


© 2023 Mara Bos Licensed under CC BY-NC-ND 4.0 Source: https://marabos.nl/atomics/inspiration.html#rcu

RCUの更新は以下の手順で行われる：

  1. Readでデータを読む
  2. Copyでデータをコピーする
  3. Modifyでコピーに変更を加える
  4. Updateでポインタを新しいデータに向け直す

この時、読み込みスレッドは更新中も一貫した（古い）データを参照し続けることができ、更新完了後の新しい読み取りは更新されたデータにアクセスすることになる。
ただし、この手順では古いデータの扱いが問題となる。データの更新をするごとに古いデータのポインタを作ることになるので、4までのステップだとメモリーリークが起こる。どこかのタイミングで、5. Deallocateに相当する古いデータを解放する処理をしたいが、その解放したいデータがまだ読み込まれている可能性もある。そこで、古いデータを適切なタイミングで解放する仕組み（ガベージコレクション：GC）が必要となる。

RCUのGCについては多様な実装アプローチが存在する。
先ほどの画像の引用元のページでは、GCの実装方法の候補の一つに参照カウンタ(古いデータを参照しているスレッドの数)を使って０になったら解放するといった手法が挙げられていたが、結論から話すとパフォーマンスがスケールしなくなるのでお勧めしない。詳しいGCの実装に関しては「Day 8: Garbage Collectionのデザイン ~RCUの動作原理~」で解説する。

RCUの概要が掴めたところで今日は終わりとする。
明日からは「並行処理の基礎」に移る。→「Day:2 アトミック操作」

ここまで読んでくださってありがとうございます！！
大感謝！！頑張って記事書きます！！

Discussion