NumaRing: Topology-Aware Routing for NUMA-Local MPMC Queues, and What Broke When We Optimized It

現代のコンピュータは、それぞれ独自の処理能力とメモリを収容する複数の地区（ディストリクト）を持つ、賑やかな都市のように構築されています。プログラムが作業を行う必要があるとき、それは特定の地区にリクエストを送信します。もし必要なデータがその地区のローカルメモリ内に既にあるならば、そのタスクは瞬時に実行されます。しかし、情報を取得するために別の地区まで移動しなければならない場合、その旅路は著しく長くなります。これらの地区間の物理的な距離によって引き起こされるこの遅延は、これらのマシンがどのように構築されているかという根本的な限界です。数十年にわたり、ソフトウェアエンジニアは、データの移動や遠回りの旅を避けるために、データとそれを使用するワーカーを同じ地区内に留めておくようなプログラムを書こうと試みてきました。課題は、多くのワーカーが共有されたタスクリストに同時にアクセスしようとするとき、彼らが作り出す交通渋滞が、距離そのものと同じくらい有害になる可能性があることです。

ある研究者が、特に2つの異なる地区を持つコンピュータのための、より優れた共有リストの管理方法を構築しようと着手しました。彼らは、可能な限りワーカーとそのデータを自身の地区内に留めるように設計された「NumaRing」と呼ばれるシステムを作成しました。そのアイデアは単純でした。もしワーカーが第1の地区にいるならば、そのワーカーは第1の地区にあるリストのみを見るべきである、というものです。もしそのリストがいっぱいになるか空になった場合には、タスクを一つずつ移動させるのではなく、一度にまとめて別の地区へ移動させます。このアプローチは、高速なローカルのトラフィックを維持しつつ、低速な長距離移動を最小限に抑えることを約束するものでした。しかし、研究者がこのシステムをテストしたとき、彼らの最善の意図には隠れた罠があったことが判明しました。システムを極めて精密に測定した結果、彼らは、ハードウェア自体よりもソフトウェアの2つの特定の間違いが速度を低下させていること、そして、コンピュータの低速化を解決するための一般的なアドバイスが、実際には状況を悪化させていることを発見しました。

研究者はまず、16個の仮想プロセッサを含む2つの地区を持つクラウドコンピュータ上に、彼らのシステムを構築することから始めました。彼らはそこに一定の流れのタスクを流し込み、タスクが列の始点から終点に到達するまでにどれくらいの時間がかかるかを観察しました。最初、システムは驚くほど遅いものでした。研究者は、ワーカーがタスクを追加または削除しようとするたびに、ソフトウェアが「自分は今どの地区にいるのか？」という質問を投げかけていることに気づきました。この質問は無害に見えましたが、その答えを計算するのに時間がかかっていました。ソフトウェアは、ワーカーの場所がめったに変わらないにもかかわらず、毎回ゼロから場所を再計算していたのです。この繰り返される計算は、まるでドライバーがどこへ行くべきか正確に分かっているにもかかわらず、あらゆる交差点で立ち止まっては道を聞いているようなものでした。この質問のコストは非常に高く、データの移動という実際のタスクにかかる労力の11倍以上の手間を要していました。

研究者が、場所を記憶し、必要なときにのみチェックするように修正すると、システムは劇的にスピードアップしました。1秒間に処理されるタスクの数は6倍から7倍に跳ね上がりました。しかし、物語はそこで終わりませんでした。マシンにさらに多くのワーカーを追加すると、システムは新たな壁に突き当たりました。特にシステムが高負荷の状態にあるとき、ワーカーは依然として待ち時間が長すぎました。深く掘り下げて調査した結果、彼らは、ワーカーが地区間でタスクを共有する方法における第2の問題を発見しました。ワーカーが別の地区からタッチのバッチ（塊）を取得しようとする際、すべてのワーカーが次に誰が行くべきかを決定するための、同じ小さなカウンターを巡って争っていました。これがゲートでの大規模な交通渋滞を生み出していました。各ワーカーに専用のプライベートなカウンターを与えることで、研究者はこのボトルネックを取り除きました。この変更はさらに劇的で、ワーカーが列の中ほどで待機する時間を200倍以上削減しました。

これら2つの主要な修正を行った後、研究者は自分のシステムがチャンピオンになると期待していました。彼らは、速度を抑制していたソフトウェアのエラーを排除したのです。しかし、32人のワーカーでマシンを絶対的な限界まで押し進めたとき、システムは当初の設計目標のスピードには到底達しませんでした。研究者は、コンピュータの低速化を解決するために用いられる「バックオフ」と呼ばれる標準的な手法をテストしました。バックオフの背後にある考え方は、もしワーカーがタスクを掴むことに失敗した場合、列が解消されるのを期待して、ほんの少しの間待機すべきであるというものです。多くの状況において、この一時停止は役に立ちます。しかし、この特定の高圧的な環境においては、その停止は間違いでした。研究者は、待機することが実際に総速度の15%から30%を損なっていることを測定しました。最も早い経路は、すぐに試行を続けることでした。なぜなら、ハードウェアがすでに衝突を効率的に処理できていたため、待機することは時間の無駄にしかならなかったからです。

最終的に浮かび上がったのは、成功と硬い限界の両面を併せ持つ姿でした。研究者は、データをローカルに保持するシステムを構築し、大幅な遅延を引き起こしていた2つの主要なソフトウェアのバグを修正することに成功しました。彼らは、一般的な最適化戦略が、特定の高速シナリオにおいては有害になり得ることを証明しました。それにもかかわらず、システムは依然として元の設計目標ほどの速度でタスクを処理することはできませんでした。研究者は、残された低速化の原因は、修正可能なソフトウェアのエラーではなく、マシン自体の物理的な限界であると結論付けました。2つの地区間の距離と、それらを結ぶ道路の帯域幅が、いかなる巧妙なコーディングをもってしても突破できない天井を作り出していたのです。彼らは、システムがどこで成功し、どこで失敗し、なぜハードウェア自体が最終的な審判となるのかを正確に示すことで、その知見を正直に報告しました。彼らの研究は、高速コンピューティングの世界においては、物理的なマシンを理解することが、コードを書くことと同じくらい重要であることを思い出させてくれます。