ハクソク

世界を動かす技術を、日本語で。

再起動可能なシーケンス

2日前原文(justine.lol)

概要

  • restartable sequences（rseq） は、Linux 4.18+で導入された最新のシステムプログラミング技術
  • ロックやアトミック操作なし でスケーラブルなスレッドセーフデータ構造の実現
  • 高コア数CPU で大幅なパフォーマンス向上が可能
  • 現状はアセンブリ手書きが必要だが、今後は全OS・言語・ライブラリで採用される可能性
  • 具体的な利用例やパフォーマンス比較を通じて、rseqの実用性と今後の展望を解説

システムプログラミングの最先端：restartable sequences（rseq）

  • restartable sequences（rseq） は、Linux 4.18以降で提供される新しいカーネル機能
  • ロックやアトミック操作不要 でスレッドセーフなデータ構造構築を可能とする技術
  • 多コアCPU時代に最適なスケーラビリティを実現
  • 現時点ではLinuxでのみ、手書きアセンブリによる実装が必要
  • 代表的な利用例： tcmalloc、jemalloc、glibc、cosmopolitan
  • 128コア、192コアCPU の登場により、今後普及が加速する見込み

rseqのパフォーマンス比較

  • Raspberry Pi 5（4コア） ：malloc()がrseq利用で3倍高速化
  • System76 Thelio Astra（Ampere 128コア） ：malloc()が34倍高速化
  • AMD Threadripper Pro 7995WX（96コア） ：malloc()が43倍高速化
  • 高コア数CPUでの 10倍以上の最適化 が可能
  • 開発者は 高コアワークステーション を活用することで、最先端の最適化を実現可能

rseqが解決する問題

  • 従来のロック ：多コア環境では単一ロックがボトルネック
  • アトミック操作 ：ABA問題やキャッシュライン競合で遅延発生
  • データ構造のシャーディング ：CPUごとに分割しても、スレッドの移動で再びロックが必要
  • rseq は、カーネルがスレッドのクリティカルセクション進入を認識し、割り込み時は自動でリトライ処理を実行
  • ミューテックスやアトミック操作不要 で、極めて低コストな同期が実現

rseqの仕組み

  • rseq()システムコール で、カーネルがTLSメモリ（32バイト）をスレッドごとに割り当て
  • CPU番号の取得 が1ナノ秒で可能（従来はgetcpu()で1マイクロ秒）
  • rseq_csフィールド にクリティカルセクションのアドレスをセット
  • スレッドが割り込み・CPU移動時、カーネルが自動でアボートハンドラにジャンプ
  • これにより、 極小規模のトランザクション的処理 が高速かつ安全に実行可能

具体例：最速のヒットカウンター構築

  • ブログのアクセスカウンター を例に、5種類の実装方式を比較

    • ミューテックス（glibc/cosmo）
    • アトミック操作
    • シャーディング
    • rseq
    • アフィニティ固定

  • 96コアAMD Ryzen Threadripper Pro 7995WX でのベンチマーク結果

    • ミューテックス：最遅（数十万ops/sec）
    • アトミック：中速（数十万ops/sec）
    • シャーディング：高速（数千万ops/sec）
    • rseq：超高速（1億～2億ops/sec）
    • アフィニティ固定：理論値最速（rseqと同等）

  • rseqの優位性

    • ポータブルな実装ではシャーディングが最適
    • rseqはLinux限定だが、 圧倒的なスピード を実現
    • アフィニティ固定は管理コスト・リスク高く、ライブラリ用途には不向き

rseq導入の今後と課題

  • rseqは現状Linux限定、他OSや言語での普及はこれから
  • アセンブリ手書きが必要 なため、習得・実装難易度は高い
  • 将来的には 全OS・全システムプログラミング言語 でrseqがサポートされる可能性
  • データ構造ライブラリの根本的な再設計 が進む見通し
  • LLM（大規模言語モデル） による自動化は現状困難、今後の技術進化に期待

まとめ

  • restartable sequences（rseq） は、マルチコア時代の最先端同期手法
  • ロック・アトミック操作不要 で、スケーラブルかつ超高速なデータ構造実装を実現
  • 高コア数CPU で劇的なパフォーマンス向上
  • 今後の OS・言語・ライブラリ の進化により、rseqの普及が期待される
  • システムプログラマにとって、 rseqの理解と活用 は今後ますます重要となる

Hackerたちの意見

もしかしたら年を取ったせいかもしれないけど、この記事の最初にある「ワークステーションに2万ドル使わないと恐竜みたいに取り残される」っていうのがすごく読む気を失わせる。これ、著者よりもコア数が多いワークステーションを持ってる人間として言ってるんだけどね。

└

もし過剰に寛大に考えるなら、ラズベリーパイが最低限必要ってこと？そこには3倍の改善が見られるから、パターンが機能してるってことだし、それは恐竜にとっては十分だよ（この記事をざっと読むだけなら、この解釈は簡単に正当化できる…初めて読んだときの俺もそうだったし）。でも、君に同意するよ。マルチコアサーバーのために大きな最適化をやったことがあるけど（コア数は少ないけど、同じような作業）、俺のワークステーションは小さなもので、同じOSすら使ってなかった。概念を理解するために大きなマシンは必要ない。俺にとっては、チェック用の大きなマシンがあればいいんだ。俺にとって、それは常に生産機で、時には生産負荷で動かす前の事前検証のためにローテーションから外された生産機だ。ちなみに、俺は特にアプリケーションに関わっていて、アプリケーションをより良く動かすためにライブラリやカーネルも扱ってる。スレッドをCPUに固定することにも問題はないけど、俺のアプリケーションは通常、一つの大きなプログラムでシステムを埋め尽くす感じ。一般的なライブラリを書く人はもっと大変だよ。もちろん、こういう作業をしたいなら、自分の生産負荷がないときは、大きなマシンを借りたり、レンタルしたり、買ったりしないといけない。でも、それが自分のワークステーションである必要はない。クラウドの面倒なことが嫌いだけど、テストが短いなら、画像をすぐに起動できるように事前作業をすれば、テスト時にスポットインスタンスを借りることでかなりお金を節約できるかも…ただ、ベアメタルのスポットインスタンスができるかは分からないから、VMのオーバーヘッドに悩まされるかもしれないね。

└

でも、この記事はそう言ってないし、君は明らかに皮肉を見逃してるね。

└

作者は数日前にSFで家を買ったり、プライベートジェットで旅行するためのお金を募ってたみたいだね。20kのマシンを家で使ってるなら、寄付が本当に集まったんだろうね。

└

彼女は自分が提案してる最適化やアルゴリズムを利用することについて明確に主張してるし、あんまり真剣には見えないよね。逆に、これを真剣な主張として受け取るのはちょっとお花畑だと思う。

└

最後まで読んでみて。あのマシンは、彼女がllmの研究を続けられるように、企業から割引で提供されたんだよ。今の時代、"誰でも" 1024コアのワークステーションを持ってるわけじゃないって言ってるわけじゃないからね。

└

あんまり真に受けない方がいいよ。明らかにやりすぎな自己満足の買い物を冗談っぽく正当化してる感じで読んだ。

リスタート可能なシーケンスが何か全く知らなかったら、OPの中ほどにある要点が大事だよ。「これがLinuxがrseq()を提供する理由で、もっと賢い解決策なんだ。リスタート可能なシーケンスを使えば、ミューテックスやアトミックを両方とも排除できるし、OSはスケジューリングを完全に抽象化し続ける。動作の仕組みは、プログラムが中断されたくないクリティカルセクションに入ったときにカーネルに知らせること。多分、最大で10個のアセンブリ命令になると思う。最初のアセンブリ命令は、rseq_csフィールドを設定するムーブ命令であるべき。最後の命令は、グローバルデータ構造に変更を加えるものが必要。これは、すごく小さなデータベーストランザクションみたいなものだ。速く動く理由は、カーネルとの双方向通信が共有メモリを介して行われるから。」

└

それ、賢いね。ロックと完全なSTMの中間的な解決策だと思っていいのかな？カーネルレベルで実装されてて、抽象化コストがゼロってこと？

└

LWNに良い記事があるよ: https://lwn.net/Articles/1033955/

└

でも、これだけじゃあんまり説明になってない気がする。私の理解が正しければ、これは完了するまで原子的に実行されるか、そうでないかの命令のシーケンスなんだよね。もし何かに中断されると、カーネルは設定したabort/retryベクターに飛ばして、シーケンスの最後の命令が実行されていないことを保証してくれるんだ。（rwmjが投稿したLWNの記事を読んだ限りではね）

└

説明がちょっと分かりづらかったと思う。要するに、これってユーザーランドに「per-CPU」同期を持ち込むってことだよね。カーネルではper-CPUデータが普通だけど、per-threadデータは珍しくて実用的じゃないことが多い。カーネルが管理するスレッドの数は多いけど、そのほとんどはユーザーランドのプロセスに属してて、特定の同期スキームには参加してないことが多いんだ。スレッドは並列プログラミングのニーズには抽象的すぎることが多いし、例えばキャッシュ効果を隠しちゃうからね。だから、ユーザーランドプロセスでthread_localデータの代わりにper-CPUデータを使いたくなるのは自然なことだと思う。私も何度もそう思ったことがあるし。rseqを使えば、ユーザーランドプロセスごとに各CPUに対して同期データ構造のインスタンスを一つ割り当てられるんだ。ユーザーランドのコードがper-CPUデータ構造にアクセスする際、CPUからスケジュールされて他のスレッドに置き換えられるのを防げないことを理解するのが重要だよ（カーネルコードは短いクリティカルセクションのためにスケジューラーをブロックできるけど）。置き換えられたスレッドが、トランザクションの途中にあった同じデータを壊しちゃう可能性もあるんだ。でも、少なくともトランザクションの一部を安全にすることはできるよね：もしトランザクションが一つの（最終的な）原子的な命令でコミットされて、途中でスケジュールが入った場合にそのトランザクションを再起動するためのカーネルサポートがあれば、コミットの時点でスケジューラーに中断されていないことが保証されるんだ。つまり、ある種の「相互排除」の保証があるってこと。これで合ってる？

リスタート可能なウィンドウ、または一般的に言うとイントロスペクションウィンドウは、プリエンプションのソースを理解または制御できる状況で使える本当に便利なテクニックだよ。このテクニックがオペレーティングシステムで使われ始めたのは、約25年前だと思う。重要な洞察は、プリエンプターが中断されたコードのプログラムカウンターを調べて、適切に行動できること。最もシンプルなメカニズムは、クリティカルセクションにいるときにプログラムカウンターをリセットすること。もっと一般的なメカニズムは、指定されたアドレスにジャンプさせること。これにより、ハードアボートなどが可能になる。さらに、プリエンプターが中断されたコードを理解する必要をなくすために、中断されたコードが自己イントロスペクションのコードスニペットを作成し、それを中断時にプログラムカウンターと一緒に提供することができる。だから、プリエンプターは自分のコードに向かわせるだけで、そのコードが中断ポイントで自分の状態を解釈できるんだ。

└

サンの論文が、tcmallocのrseqの開発を10年以上前に予見してたんだって。https://dl.acm.org/doi/abs/10.1145/512429.512451

rseqを実装している人がメンテナンスしているlibrseqライブラリについての言及がなかったのは驚きだね: https://github.com/compudj/librseq これにはカウンターやリンクリストのような一般的なユースケースのためのヘルパーがあるよ。ほとんどのアプリケーションでrseqを使うためにアセンブリを書く必要はないはず。

└

ジャスティンは自分のlibcとmallocを作ってるから、rseqをゼロから使いたいってのも納得だね。

おそらく、CPUの内部ミューテックスは、ユーザースペースで実装したものほど良くないだろう この発言について、何か知見のある人いる？直感に反するように思えるんだけど（npi）。

└

作者はフェイクシェアリングについて言及してるんだよね（https://en.wikipedia.org/wiki/False_sharing）。CPUキャッシュはキャッシュラインの粒度（通常は64バイト）で動作するから、キャッシュラインの一部への書き込みは、同じキャッシュラインの重ならない部分への書き込みと同期が必要になることがあるんだ。これが、同じキャッシュラインで多数のコアが動作しているときにパフォーマンスを劇的に低下させることがあるんだよ。hitcounter-shard.cから64バイトのアラインメントを外せば（これが各カウンタ変数を別のキャッシュラインに強制する）、パフォーマンスの違いを自分で確認できるはずだよ。

... カーネルとの双方向通信は共有メモリを介して行われるんだ。何が起こる可能性があるっていうの？

└

詳しく？カーネルの共有メモリインターフェースは、結構合理的なことが多いよ（vdsoとかio_uringとか）。

IIUC、rseqはスレッドローカルデータに似てるけど、スレッドじゃなくてCPUコアの数に応じてスケールするっていう追加の利点があるよね。ただ、アプリケーション開発者で、アプリ内のすべてのスレッドをコントロールできるなら、rseqはそれほど優れてるわけじゃないかな。でも、rseqがLinux開発者にもっと簡単に利用できるべきだっていうのには完全に同意するよ。

これすごいね。絶対にプロジェクトで使うわ。

最近、RSEQがユーザースペースでload-link/store-conditionalの実装を作るのに良いプリミティブになるかどうか、誰かと話してたんだ。クリティカルウィンドウを提供してくれるけど、スプリアスな再起動に対処しなきゃいけないし、あるコアが別のコアを中断させる方法も用意しないといけないね。