パッケージ探訪: Userspace RCU

読み込みが多いシステムでのパフォーマンス向上に寄与するライブラリ

2023年6月20日
著者: 竹洞陽一郎

はじめに

並行プログラミングはコンピュータ科学の中でも特に難易度が高い領域の一つとされています。
その理由は、データ競合、デッドロック、競争状態など、複数のプロセスやスレッドが同時にアクセスするときに起こり得るさまざまな問題を適切に管理し、解決する必要があるからです。
このような問題を解決するための一つの強力なツールが、RCU（Read-Copy-Update）と呼ばれるテクニックです。

RCUはもともとLinuxカーネル内部で使用されていたものですが、このテクニックはユーザースペースでも役立つことが分かり、その結果、Userspace RCUというライブラリが生まれました。
このライブラリを利用することで、ユーザーレベルのアプリケーションでもRCUの強力な読み込み性能とスケーラビリティを享受できるようになりました。

2023年6月13日に、slackware-currentに、xfsprogs-6.3.0と依存関係があるということで、userspace-rcu-0.14.0-x86_64-1.txzが追加されました。
今回は、このUserspace RCUについて解説します。

Userspace RCUとは

Userspace RCU（Read-Copy-Update）は、カーネルスペースにおける RCU の概念をユーザースペースに適用したものです。
RCU は Linux カーネルで用いられる並行プログラミングテクニックで、リード側の性能とスケーラビリティを高め、更新（書き込み）操作を効率的に行うことができます。

RCU の基本的な概念は、データ構造を更新する際に、それを直接書き換えるのではなく、そのコピーを作成し、更新操作をそのコピーに対して行い、その後、読み込みを新しいバージョンに透過的に切り替えるというものです。
そのため、読み取り操作はロックフリーで行うことができ、同時に多数の読み取りを行うことが可能となります。

Userspace RCU ライブラリは、この RCU の原理をユーザーレベルのアプリケーションで使用できるようにし、アプリケーションが RCU の利点を享受できるようにすることを目的としています。
このライブラリは、C プログラミング言語で書かれており、様々なタイプの RCU をサポートしています。
それは、以下のようなシナリオで特に役立ちます。

データ構造が頻繁に読み取られ、しかし稀にしか更新されない場合。
リードとライトの両方が頻繁に行われるが、リードの方が圧倒的に多い場合。
ロック競合によるオーバーヘッドを減らす必要がある場合。

しかし、Userspace RCU の使用は一部の制限を伴います。
例えば、メモリ再利用の遅延（旧版のデータ構造がまだ参照されているかもしれないため）や、更新操作がやや複雑になる可能性があります。
しかし、適切に使用されると、Userspace RCU は読み取り主導の並行システムのパフォーマンスとスケーラビリティを大幅に向上させることができます。

CAP定理から見たUserspace RCU

CAP定理（Brewerの定理）は分散システムに関するもので、一貫性（Consistency）、可用性（Availability）、分断耐性（Partition Tolerance）の3つの性質のうち、同時に2つしか満たせないというものです。

一方、Userspace RCU（Read-Copy-Update）は、主に並行性と効率を改善するために使用されるプログラミング技術で、直接的には分散システムの文脈とは異なります。
しかし、RCUの思想をCAP定理の観点から考えてみることは可能です。

一貫性: 「一貫性」に関しては、RCUが保証するのは「見かけ上の一貫性」（または「結果整合性」）です。
データが更新されるとき、RCUは古いコピーのデータに対する読み込みをブロックせずに新しいコピーへの書き込みを許可します。
したがって、一部の読み込みクエリは更新前のデータを見る可能性があり、一部は更新後のデータを見る可能性があります。
これはストリクトな一貫性（全ての操作が同じ順序で全てのノードに反映される）を保証するわけではないため、RCUを使用するときはこのトレードオフを理解することが重要です。
可用性: RCUの主な特性は、読み込みをブロックせずにデータの更新（書き込み）を可能にするという点です。
これは「可用性」の観点で特に重要で、多くの読み込みクエリが同時に実行されていても、それらがブロックされることなく進行できることを意味します。
したがって、RCUはシステムの可用性を高める役割を果たします。
分断耐性: 「分断耐性」については、RCU自体はネットワークの分断に対する耐性を提供しないため、分散システムの設計者がその対応策を講じる必要があります。

結論として、Userspace RCUは、CAP定理の観点から見ると、高い可用性と一部の一貫性（見かけ上の一貫性）を提供しますが、分断耐性は直接的には提供しません。
それらの特性はRCUを非常に強力なツールにしていますが、その使用はシステムの具体的な要件とトレードオフを理解した上で行われるべきです。

ACID特性から見たUserspace RCU

ACID特性は、トランザクションデータベースシステムの主要な特性を説明するための概念であり、原子性（Atomicity）、一貫性（Consistency）、分離性（Isolation）、耐久性（Durability）の4つの頭文字を取っています。

Userspace RCU（Read-Copy-Update）は、データの読み取り（リード）と更新（ライト）を効率的に行うための並行プログラミングの技術です。
その特性をACID特性と関連付けて考えることは、一見直観的ではないかもしれませんが、以下のように解説できます。

原子性（Atomicity）: RCUの更新操作は原子的です。
つまり、データ構造の更新（コピーの作成と書き込み）は一連の不可分の操作として行われます。
しかし、それは一部のリーダーが古いデータを見続ける可能性があるという点で、データベースのトランザクションとは異なります。
一貫性（Consistency）: RCUの一貫性は、一般的なデータベースの一貫性モデルとは少し異なります。
RCUは「見かけ上の一貫性」（eventual consistency）を提供します。
更新が完了した後であれば、全てのリーダーは新しいデータを見ることができます。
しかし、更新中は一部のリーダーが古いデータを見続ける可能性があります。
分離性（Isolation）: RCUは複数のリーダーが同時にデータを読み取ることを許可しますが、それらのリーダーが他のリーダーの影響を受けることはありません。
これは、一種の「リードの分離性」を提供すると言えます。
しかし、データベースの分離性とは異なり、RCUは書き込みとリード間の分離性を保証しないため、これは完全な分離性ではありません。
耐久性（Durability）: RCU自体はデータの永続性や耐久性に対して何も保証しません。
それはあくまでメモリ内のデータ構造に対する操作を効率化する技術であり、データの保存や復元の問題は別途対応する必要があります。

以上のように、Userspace RCUの特性はACID特性とは一部異なりますが、この視点からRCUを考えることで、その強力さと同時に考慮すべきトレードオフを理解する助けになります。

XFSとRCU

XFSファイルシステムは、元々、Linuxカーネル内部でRCU（Read-Copy-Update）を利用しています。
RCUはカーネル内での読み取り専用のデータ構造に対する読み取りと更新を効率的に行うための仕組みであり、その特性はXFSが高速で効率的に動作する理由の一つです。

しかし、XFSを操作するためのユーティリティ群（xfsprogs）がUserspace RCUを必要とする理由は、カーネル空間とユーザー空間の違いに由来します。
具体的には、カーネル空間で使用されるRCUのAPIは、ユーザー空間からは直接使用できません。
しかし、XFSユーティリティ群はXFSファイルシステムのメタデータを解析したり操作したりする必要があり、その際にはRCUの特性が必要となることがあります。

そこで、ユーザー空間でRCUの機能を使用するためには、Userspace RCUのようなライブラリが必要となります。
これにより、ユーザー空間のアプリケーションでもカーネル空間のようにRCUの高いパフォーマンスと効率性を享受できます。
XFSのユーティリティ群（xfsprogs）は、効率よくユーザー空間で実行されるために、このUserspace RCUが必要というわけなのです。

Userspace RCU Project

Userspace RCUは、Userspace RCU Projectで開発されています。

RCU (Read-Copy-Update) は、2002年に初めて Linux カーネルに組み込まれました。
このアイディアを提案したのは Paul E. McKenney と John D. Slingwine で、彼らの提案は当時の Linux カーネル開発者たちによって受け入れられ、以降 Linux カーネルの重要な部分で広く利用されるようになりました。

RCU の基本的なアイディア自体は、その時点でも新しいものではなく、データベースやリアルタイムシステムの分野で以前から使われていたテクニックを、カーネルレベルでの同時実行制御の問題に適用したものです。
しかし、それが Linux カーネルの中で広く利用されるようになったのは、McKenney と Slingwine の功績と言えるでしょう。
McKenneyは、Userspace RCU Projectで、今も活動しています。

まとめ

Userspace RCUは、XFSやGluster FSのようなファイルシステム、ICU BIND、Knot DNS、gdnsdのようなDNSサーバで利用されており、特に読み込みが多いシステムでパフォーマンスを向上させるには有効なライブラリです。
しかし、こんなライブラリが存在しているということを知ってる人は少ないのではないでしょうか？
パッケージの管理のためにパッケージ更新を追っていると、知らなかったライブラリに出会える、それもSlackwareの醍醐味の一つかもしれません。