Message Passing

karino2 が 並列プログラムから見たFuture というビデオを作って公開していたので、引っ越しの荷造りをしながら眺めた。

長いのでここにざっくりとした主張をまとめると:

• Future/Promise (およびその後釜の async/await) は非同期プログラミングで callback hell にならない発明という見方をされているが、 そもそもなぜ callback hell が必要だったかの時代背景が十分に理解されていない。
• 背景の一つはブラウザ JavaScript のプログラミングモデルにシングルスレッド・ノンブロッキング(イベントループ)という制限があったから。 これは(特にフロントエンド開発者の間では)よく理解されている。
• もう一つの視点は SEDA みたいなマルチスレッド・ノンブロッキング環境の必要性で、 こっちはいまいち広く理解されていないように思える。
• 結果としてサーバやデスクトップなどで C++ (なんで?) を書いているプログラマに Future/Promise の重要性を説明する良い資料がない。 なぜ Twitter が Finable を、 Facebook が Folly Future を、 Netflix が ReactiveX を、 Apple が Dispatch を、 Google が ListenableFuture ã‚’ (一個だけダサいのが混じってるぞ!) 持っているのかが伝わらない。

ので俺が説明してやんよ、という内容。

いいたいことに大きな異論はないのだけれど、 先のビデオは準備不足なのか色々わかりにくい部分もあって議論を続けるのが難しい。 そこでまずは話を整理し、そのあと仕事のコードとかだと実際どうなんですかと人々に聞いてみる回です。

20 年前のデスクトップ: スレッドは雑に作る。UI スレッドはブロックする。

というわけでおっさんの昔話から始まるのだよ・・・。

スレッドの使い方という点でいちばんしょうもない例を見るには、15-25 年くらい前のデスクトップアプリを見ると良い。 この世界ではみんな基本的にシングルスレッドでコードを書いている。 のみならず、UI スレッドをブロックしないという現代の常識すらあまり守られていない。 容赦なくダイアログボックスとかを表示して UI スレッドを止める。 厳密にいうと UI スレッド (イベントループ) は止まっておらず、かわりにネストしている。 ただ細かいことなのでブロックしていると思っておけばだいあいあってる。

非同期なはずの JavaScript の世界で alert() とかがブロックするのは、 こういうプログラミングモデルを前提としたデスクトップ OS の API を使って実装されていたから。 (逆にそういう前提を捨てたモダンブラウザの実装をみると alert() をはじめとする blocking call 周辺はかなりの mess になっている。)

20 年くらいの PC も高いやつだと CPU は 2-4 コアくらいあったので、 すごく時間のかかる計算はスレッドを作って並列化されていた。 ただスレッドの使い方はアドホック。必要なときに新しいスレッドを欲しいだけ作って、タスクを動かして、おしまい。

同時代のサーバサイド: 1 リクエスト 1 スレッド

同じ時代、Web サーバのようなサーバサイドのソフトウェアも同じように素朴だった。 クライアントのリクエストを accept() するスレッドがいて、そのスレッドがリクエストを受け取るたびに新しいスレッドを作り、 ソケットを渡して処理を任せる。 ソケット入門みたいな記事は今でもそういう説明をすることが多いと思う。 概念的にわかりやすいからね。

ただ現実のサーバーでリクエスト単位に新しいスレッドを作るとオーバーヘッドがでかいなど色々と都合が悪いので、 一度作ったスレッドは使いまわすのが普通。 スレッドプールというやつ。 この「都合の悪さ」や「オーバーヘッド」は karino2 の議論で重要なトピックなのだけれど、 今はスルーして先に進もう。

ノンブロッキングサーバ: シングルスレッド

リクエスト単位でスレッドをつくるアプローチの対極に、一つのスレッドで全てのリクエストをさばくアプローチもある。 こうしたサーバはノンブロッキング I/O の API, 古いところだと select() とか、を使って書かれている。 これだとスレッドが一個しかないので、スレッドを沢山つくる「オーバーヘッド」がない。

この「オーバーヘッド」がなんなのかはやはり議論の余地があるが、 シングルスレッド・ノンブロッキングなサーバではそもそもスレッドが一つしかないので気にしなくていい。 オーバーヘッドの少なさ、並列プログラミングの難しさ（ロックとか）を避けられるある種の単純さもあって、 特にコネクションの寿命が長いチャットみたいなアプリのサーバとして伝統的に割と人気。

一方でマルチコアの CPU では２つ目以降のコアを使い切れない欠点もあり、そのへんは工夫を要する。

がんばるサーバ: SEDA

リクエスト単位でスレッドを作るかシングルスレッドか。 上で議論したこのトレードオフはどう考えても雑すぎで、 実際はノンブロッキングだけどマルチスレッドにできるのが望ましい。 そういう実装は色々あるが、中でも SEDA という 2001 年の研究が有名だと思う。 SEDA は I/O を待つメインスレッドもワーカーも全部ノンブロッキングにしてメッセージキューでやり取りする。 具体的にはタスク (“Stage”) 毎にスレッドプールを作り、そのスレッドプール同士をメッセージキューで繋ぐ。 ノンブロッキングにできない処理(Linux だとファイルの読み書きとか)は、ブロッキング専用のスレッドプールをつくって閉じ込める。

ステージ間の通信に使うキューに小細工することで、従来なら OS のスケジューラががやっていた仕事の一部を アプリケーションで実装できるようになる。おかげで OS の制限、すなわちオーバーヘッドを避けられるし、 スケジューリングにアプリの都合を加味できる。だから良い。 それが SEDA の主張 (をかなり雑に解釈したもの) である。

スレッド数 = コア数

SEDA のデザインは、ある意味では現在でも割と生き延びている。 つまり、用途に応じたスレッドプールを事前に用意し、アプリケーションのコードはみなでそれを使う。 ブロッキングコールは遠慮する。

SEDA では複数のスレッドプールをつくりスループットを調整していたが、そこまでがんばるケースは少ない。 CPU のコア数ぶんだけスレッドがあるデフォルトのスレッドプールをひとつだけ用意するほうが普通。 おまけでファイル操作のようなブロッキング IO 用のスレッドプールがついてくる場合もある。 Kotlin の Dispatchers, RxJava の Schedulers, Tokio, GOMAXPROCS, などなど。

がんばるデスクトップアプリ

karino2 のビデオでは、二千ゼロ年代中盤の巨大な Windows アプリの開発が同様の問題（OS スレッドのスケーラビリティ不足）にぶつかり、 同様の解決に至った経緯を紹介している。すなわちコア数にあわせたスレッドプールをつくってノンブロッキングにがんばる。

ゼロ年代の世の中は割とウェブ全盛で、クライアントサイドというかフロントエンドの人々は 多くがシングルスレッドなブラウザの JS で暮らしていた。けれどデスクトップネイティブ勢はがんばっていたらしい。 言われてみると C# は async/await をメインストリームにもってきた最初の言語だし、 RX(Reactive Extension) も Microsoft 生まれ。 Windows は色々やっていたのだろう。

ノンブロッキング・スレッドプールという合意

こうしてマルチコア環境での高性能、高並列アプリケーションの実行モデルはだいたい合意ができた: OS のスレッドはコア数ぶんだけしかつくらず、スケジューリングとかはユーザ空間でがんばろうではないか。

もちろん OS 自体も進化しており、昔の「オーバーヘッド」の常識は当てはまらない。 たとえば SEDA の書かれた 2001 年に Linux CFS はなかった。 (Wikipedia によれば 2010 年くらいに有効化されたらしい。) そんなモダン実装 OS のスレッドに頼ってばんばんブロッキングコールをする作る人々もいる。 たとえ Hadoop のようなバッチ分散コンピューティングはスレッドをじゃんじゃかつくる印象。 伝統的なデータベースの実装も割と OS のスレッドだのみな気がする。 ファイル I/O がブロックするときに非同期とか言われてもやりようがないせいだろうか。

そんなわけで「ノンブロッキング・スレッドプール」が唯一の正解というわけではない。 とはいえメインストリームの一つになったのは間違いない。 プログラミング・ポップカルチャーでは “Reactive” という呼び名を獲得した。 厳密に Reactive がなんなのかには色々議論の余地があるけれど、近似としてはあってると思う。

よりよい抽象を求めて

ノンブロッキングのコード、高性能なのはいいけれど書くのがだいぶかったるい問題があった。 かったるさの代表例としては JS の calback hell がよく知られている。 でも JS のように first class function がある言語はまだマシで、lambda が入る前の Java や C++ とかマジだるかった。

今でも相変わらずシングルスレッドな JS だけれど (Web Workers とか他の言語からみたら冗談みたいなもんです) ノンブロッキング、非同期プログラミングのよりよいプログラミングモデルを幅広いプログラマに届けたのも JS だった。 つまり Promise と async/await である。 どちらも JS 以前からあったといえばあったとはいえ、さほどメジャーでなかった。 一方 JS (というか ES6) 以降の世代の言語は、だいたい似たような仕組みをもっている。

しかし… と karino2 は言う。こういう素敵な抽象の恩恵を受けそびれているプログラマがいる。 それは、本来こういう素敵抽象の恩恵を一番うけてしかるべき高性能システム/アプリを書き続けてきた苦難の C++ プログラマたちである。

C++ に限らず他の言語、たとえば Java とかでも非同期の世界に行きそびれてしまった人はそれなりにいる。 とはいえ C++ はそもそも標準にスレッドプールすらないので、広く使われる抽象を作りようがない。 一方で Facebook のように体力のある会社は独自に Future を実装している。なんたる格差社会。 そうしたかわいそうな一部プログラマを啓蒙すべく karino2 は冒頭のビデオを作った。

Where Is The Free Lunch

ところでここまでの議論は問題領域が intrinsic な平行性をもっている前提だった。 サーバなり大規模デスクトップなり、彼らは平行して処理するタスク(リクエストとか)が多すぎて困っていた。

ゼロ年代の同じ頃、あまり平行でない世の中の別の場所で、人々が別の問題に頭を悩ませていた: 最近の CPU はコアばかり増えてシングルスレッド性能が上がらない！なんとかコードを並列化して最新 CPU を活用しなければ！ そうした声のなかでたぶん一番有名なのが 2005 年に書かれた “The Free Lunch Is Over” という記事。当時はまだ割と元気だった C++ の有名人が世間を煽っている。

この頃からなんとか手元のコードを並列化したい人々の努力が始まり、 たとえば … 例をあげるとキリがないけど色々なライブラリ、フレームワーク、ツール、言語などなどがでてきた。 わかりやすいところだと Scala の Parallel Collection とかね。Erlang がもてはやされはじめたのも同じ頃だった記憶。

更に同じ頃別の場所で、手元にあるすごい速いチップ… つまり GPU …を持て余している人たちが GPGPU というのをはじめた。 GPU をうまくつかうのは CPU 以上に難しいが、上手く使うと CPU が足元にもおよばない速さで計算できる。 そんなんじで CUDA が登場したのは 2007 年らしい (Wikipedia 調べ)。

で、最近どうしてる?

というかんじで 10 年くらい前に並列や並列ってすごい活発に議論されてたのを、 karino2 のビデオをみたおっさんである森田は思い出したのだった。

今の計算機、たしかにまあまあマルチコアになってる。 ラップトップも 4-16 論理コア/HT くらいあるし、スマホは 8 コア。 クラウドのサーバとか仮想化されてて見えないけど bare-metal なら高いやつだと 96 vCPU とかある。 AI 人材は暗号通貨人材と GPU を奪い合っている。

そんなコア余りっぽい昨今、みなさんちゃんとコア使ってる？余ってる？足りない？