令和にふりかえる C10K 問題
C10K 問題 (the C10K problem) は1999年に Dan Kegel が発表した文章、ならびにそこで提示された「問題」です。文章はその後も2000年代前半に何度か更新されているのですが、さすがに令和に読み返すと、当初の問題意識がわかりにくいところがあります。
2000年からの10年は、
- ソフトウェア面では、select(2), poll(2) にかわる新しいシステムコールの実装と、それを使ったアプリケーションの普及
- ハードウェア面では、x86 アーキテクチャの64ビット移行、仮想化命令の追加と、マルチコア化
さらにそこにクラウドも登場する、面白い時代でした。ここでは、それらの出来事を中心に、さらに、当時の雰囲気をつたえるような日本国内のブログやインタビュー記事をまとめることで、C10K 問題が、さまざまな側面から解決されていく流れを説明したいと思います。
書き足したいところ
- マルチコア時代以前の人々のスレッド観: シングルコアでマルチプロセスな OS を動かしていたんだから、スレッドも大量に建てるつもりだったのか?
- epoll がはいったのは 2.5.44 or 2.5.45? man とかには 2.5.44 と書いてあるんだけど、Linus のリリースメールでふれられているのは 2.5.45 なのが謎。
- Xen vs. KVM: VT-x 以降にもみんな Xen つかっているのはなんなのか。Xen 経由で KVM つかってる?
タイムライン
1999
Dan Kegel, The C10K Problem を公開
It's time for web servers to handle ten thousand clients simultaneously, don't you think? After all, the web is a big place now.
C10K 問題として名前がつけられ、広く知られるようになる。
ただし、同年にリリースされている Solaris に select() /dev/poll が実装されているからもわかるように、これ以前にも一部で問題自体は認識されていたのだろう。
What's New in the Solaris 8 Operating Environment
/dev/poll is a second form of polling for the completion of I/O events that provides much higher performance when a very large number of events must be polled for on file descriptors that remain open for a long time. This feature supplements poll(2); it does not replace poll(2).
For more information, see the System Interface Guide.
This feature was first available in the Solaris 7 5/99 release.
また、無料の Unix 系 OS を使って安価な x86 マシンを水平にならべることの有用性も、当時すでに認識されていたと思われる。
たとえば、NASA の Linux クラスタ、Beowulf が発表されたカンファレンスは1995年の ICPP (International Conference on Parallel Processing),
BEOWULF: A parallel workstation for scientific computation
The Beowulf parallel workstation project is driven by a set of requirements for high performance scientific workstations in the Earth and space sciences community and the opportunity of low cost computing made available through the PC related mass market of commodity subsystems. This opportunity is also facilitated by the availability of the Linux operating system, a robust Unix-like system environment with source code that is targeted for the x86 family of microprocessors including the Intel Pentium.
また、1998年創業の Google も最初から Linux を使っていた。
Red Hat Linux Powers Google's Award-Winning Search Engine
Google has used Red Hat Linux for all its Internet computing functions since its inception in 1998. To generate the necessary power for its in-depth searching capabilities, Google needed a large cluster with the dependability and scalability of UNIX, but without the prohibitive cost.
2000
kqueue を実装した FreeBSD 4.1 がリリースされる
A new event notification facility called kqueue was added to the FreeBSD kernel. This is a new interface which is able to replace poll/select, offering improved performance, as well as the ability to report many different types of events. Support for monitoring changes in sockets, pipes, fifos, and files are present, as well as for signals and processes.
select(2), poll(2) にかわる新しいシステムコール kqueue(2) が FreeBSD に実装される。
翌年の USENIX Annual Technical Conference 2001 で発表された Kqueue: A generic and scalable event notification facility では、/dev/poll についても
This system appears to come closest to the design outlined in this paper, but has some limitations as com- pared to kqueue.
と言及されている。
Niels Provos, libevent 0.1.0 をリリース
Currently, libevent supports kqueue(2) and select(2). Support for poll(2) and /dev/poll is being planned. The internal event mechanism is completely independent of the exposed event API, and a simple update of libevent can provide this new functionality without having to redesign the server applications.
libevent は、後に memcached などでも使われる。
2001
Intel, IA-64 命令セットを実装した最初の CPU, Itanium をリリース
Intel's Itanium finally arrives
The announcement last week that systems based on Intel Corp.'s long-delayed Itanium processor should start shipping this month was welcome news to users hoping to run large enterprise applications on commodity hardware, users and analysts said.
スレッドを多くたてる、たとえばリクエスト毎にスレッドをたてる場合、そのメモリ使用量が32ビットマシンのメモリ空間 (4GiB) を超えてしまうと、それ以上メモリを追加することすらかなわないという問題があった。64ビットへの移行は、その意味でも重要である。
なお、命令セットとしての IA-64 は、商業的にはふるわず、AMD の x86-64 に負けることとなる。
2002
epoll が Linux カーネルにマージされる
The epoll patch is ready, and Linus has indicated that he wants to merge it. For now, epoll only works for pipes and sockets (its initial use is likely to be network services that manage large numbers of connections). Expanding its scope to other types of I/O should just be a matter of doing the work, however.
10-30-2002 - The epoll patch merged inside the Linux Kernel.
select(2), poll(2) にかわる 新しいシステムコール epoll_create(2) をはじめとする一連のシステムコールが Linux に実装される。マージされた最初のバージョン 2.5.45 も同年にリリース。
Development kernel 2.5.45 released
Device mapper (LVM2), crypto/ipsec stuff for networking, epoll and giving the new kernel configurator a chance. Big things.
ただし、当時の Linux カーネルの開発では「マイナーバージョンが奇数は開発版」なため、実際に安定版のカーネルにはいるのは2003年の 2.6.0 以降となる。
JSR 51 ファイナルリリース
JSR 51: New I/O APIs for the Java Platform
The scalable I/O API will make it easier to write production-quality web and application servers that scale well to thousands of open connections and can easily take advantage of multiple processors;
エキスパートグループに Dan Kegel が参加している。
2003
Xen 最初のリリース
[Xen-devel] [ANNOUNCE] Xen high-performance x86 virtualization
We are pleased to announce the first stable release of the Xen virtual machine monitor for x86, and port of Linux 2.4.22 as a guest OS.
Xen and the Art of Virtualization (PDF)
This paper presents Xen, an x86 virtual machine monitor which allows multiple commodity operating systems to share conventional hardware in a safe and resource managed fashion, but without sac- rificing either performance or functionality.
Xen は、CPU 自体に仮想化命令のない x86 アーキテクチャで、改変した Linux を動かすことを可能にした。
AMD, x86-64 命令セットを実装した最初の CPU, Opteron をリリース
After nearly a year of hype and development, Advanced Micro Devices Inc. today set loose its new 64-bit Opteron processors, which the company hopes will attract buyers who seek the power advantages of 64-bit computing but are leery of the costs involved in adopting other 64-bit architectures.
前述のとおり、最終的には、Intel の IA-64 ではなく AMD の x86-64 が広く普及することとなる。2004年には Intel も "Intel 64" として互換性のある命令セットを実装し追従する。
インターネット
「デルより安い」：サンの新エントリーレベルサーバが日本に上陸
同氏は、サンのOSであるSolarisと、同社チップのSPARCはいずれも100スレッド以上を処理できるという実績があり、「これだけ多くのスレッドを処理できるのは、SolarisとSPARCの組み合わせだけだ」とアピール、本日発表の製品がいずれもこの組み合わせで、スループットコンピューティングの第一歩であることを示した。
2004
Igor Sysoev, Nginx 0.1.0 をリリース
Interview with Igor Sysoev, author of Apache's competitor NGINX (2012)
I started the initial work in 2002, and in 2004 I opened NGINX to the public. Back then, I was trying to overcome certain barriers of scaling the web infrastructure of a large online media company I worked for. In particular, the difficulties of handling many concurrent connections, reducing latency and offloading static content, SSL and persistent connections were my main interest. There weren't any reliable production quality web server software to crack so-called C10K problem (handling of at least 10,000 of concurrent connections, outlined by Dan Kegel).
2012年のインタビューでは、当初から C10K 問題を視野にいれていたことが語られている。
なお、リリース日はソビエト連邦の人工衛星、スプートニクの打ち上げ日と同じである。
Interview with the creator of Nginx
On October 4th, 2004, on the anniversary of the first space satellite, I released the first public version: 0.1.0.
JSR 166 ファイナルリリース
JSR 166: Concurrency Utilities
The JSR proposes a set of medium-level utilities that provide functionality commonly needed in concurrent programs.
スレッドプールなどの現代的な並列プログラミングのための足場を提供する、java.util.concurrent が策定される。
2005
Intel, VT-x 命令をサポートした最初の CPU をリリース
Intel speeds up rollout of PC virtualization technology
Vanderpool Technology, or VT, is part of Intel's new strategy to provide users with benefits other than performance increases. VT will allow users to create virtual environments on their PCs in order to run separate operating systems on the same PC. It could also permit IT managers to upload patches or upgrades to one portion of the PC while the user runs his work applications in another environment, said Bill Kirby, Intel's director of desktop platform marketing.
Jesse James Garrett, Ajax を命名
Ajax: A New Approach to Web Applications
Google Suggest and Google Maps are two examples of a new approach to web applications that we at Adaptive Path have been calling Ajax. The name is shorthand for Asynchronous JavaScript + XML, and it represents a fundamental shift in what’s possible on the Web.
Herb Sutter, Dr. Dobb's Journal にて "The Free Lunch Is Over" を公開
The major processor manufacturers and architectures, from Intel and AMD to Sparc and PowerPC, have run out of room with most of their traditional approaches to boosting CPU performance. Instead of driving clock speeds and straight-line instruction throughput ever higher, they are instead turning en masse to hyperthreading and multicore architectures.
(...)
Arguably, the free lunch has already been over for a year or two, only we’re just now noticing.
C++ 標準化委員会などで活躍していた Herb Sutter が、雑誌 Dr. Dobb's Journal にて "The Free Lunch Is Over" を公開。CPU のクロック数の伸び悩みを指摘し、マルチコア時代がすでに到来していることを宣言する。
インターネット
lighttpd で FastCGI / CGI-Application-FastCGI-0.01
はてなでも画像サーバーなどの static なコンテンツを返すサーバーに lighttpd を使えないもんかと、ベンチを取ったりしてます。ベンチ結果では、画像ファイルとかだと Apache2 とそこまで差は出ない感じなんですが、単に画像の転送時間が支配的になってるだけかもしれないし、ちょっとトラフィックの多いところに挟んで試してみようかなと思っています。
2006
AMD, 仮想化のための命令をサポートした最初の CPU をリリース
AMD and Intel bake virtualization into chips
Hardware-assisted virtualization, now available from both AMD and Intel, is not a breakthrough but the beginning of one. AMD’s SVM (Secure Virtual Machine) and Intel’s VT (Virtualization Technology) signal a sea change in CPU design assumptions and the architectures that result.
Amazon EC2 ベータ開始
Amazon EC2 gives you access to a virtual computing environment. Your applications run on a “virtual CPU”, the equivalent of a 1.7 GHz Xeon processor, 1.75 GB of RAM, 160 GB of local disk and 250 Mb/second of network bandwidth.
SQS (Simple Queue Service), S3 (Simple Storage Service) に続いて、EC2 (Elastic Compute Cloud) のベータが開始。各種サーバーをクラウドで実行することが可能になる。なお、当時は Xen ベースであったことが、後に明かされている。
Xen-on-Nitro: AWS Nitro for Legacy Instances (2021)
On August 25, 2006, we started the public beta of our first ever EC2 instance. Back then, it didn’t even have a name yet, but we latter dubbed it “m1.small.”. Our first customers were able to use the equivalent of 1.7 GHz Xeon processor, 1.75 GB of RAM, 160 GB of local disk and 250 Mb/second of network bandwidth for just 10 cents an hour whenever they needed it and for as long as they needed it. Under the hood, we used the Xen hypervisor to provide these virtual machines or instances as we call them.
ただし、当時はそもそも東京リージョンがないこと、価格あたりの性能などの問題から、国内ではすぐには使われなかった。
Alex Russell, Comet を命名
Comet: Low Latency Data for the Browser
So what makes these apps special? What makes them different from other things that might at first glance appear similar? Fundamentally, they all use long-lived HTTP connections to reduce the latency with which messages are passed to the server.
Comet が流行って HTTP の接続を維持するようになったら、人気のないサイトでも同時接続数を気にする必要があるのでは、と思われるも、実際にはそこまで流行らなかった。
インターネット
Lingrは「Comet」と呼ばれる技術を試しに使ってみようということで始めたものです。もっとも、そのころにはCometという名前もついていませんでした。この技術は、ブラウザとサーバのコネクションを維持しておくことで、サーバ側からのプッシュを実現するものです。
仮想化も流行しました。オープンソースの仮想化環境、Xenが実用的に広まり始めたのではないでしょうか。
DSASのロードバランサは高価なアプライアンス製品ではなく、LinuxのLVS (Linux Virtual Server)を利用しています。
MochiAds - Flash Game Ad Network
The secret sauce is a combination of Python and Erlang code, and we've got Nginx as the gatekeeper. I've got nothing but good things to say about this whole stack. Erlang's module reloading, concurrency oriented programming model, and pattern matching has really been a dream.
初期の Erlang 事例のひとつ。
2007
KVM がマージされた、Linux 2.6.20 がリリースされる
The KVM patch set was covered here briefly last October. In short, KVM allows for (relatively) simple support of virtualized clients on recent processors. On a CPU with Intel's or AMD's hardware virtualization support, a hypervisor can open /dev/kvm and, through a series of ioctl() calls, create virtualized processors and launch guest systems on them. Compared to a full paravirtualization system like Xen, KVM is relatively small and straightforward; that is one of the reasons why KVM went in to 2.6.20, while Xen remains on the outside.
KVM は、Intel, AMD ともに実装された仮想化命令をつかった仮想化を実現した。
Marc Lehmann, libev を公開
[Libevent-users] announcing libev, towards a faster and more featureful libevent
After analyzing libevent I decided that it wasn't fixable except by rewriting the core parts of it (the inability to have multiple watchers for the same file descriptor event turned out to be blocking for my applications, otherwise I wouldn't have started the effort in the first place...).
インターネット
ところで、今回の移転にあたっては Xen を活用しています。
Xen はいわゆる仮想化プログラムで、これを使うことで一つの物理的なハードウェア上に複数の OS を稼動させることができます。
データセンターのラックや電力を無駄なく有効活用するには、サーバーの性能あたりに必要な物理的な面積と消費電力をいかに少なくするかが鍵になってきます。はてなのように数百台もサーバーがある環境ではクリティカルな問題です。
Xen を使うことで、データベースのような I/O バウンドな用途のサーバーとアプリケーションサーバーのような CPU バウンドなサーバーを同一ホストで動かして、リソースを無駄なく使うことができます。
地図を軸としたコミュニティサービス『alis』（β）[アリス ベータ]の提供を開始
なお、『alis』には、RubyForgeにおいてオープンソースプロジェクトとして開発が行われているCometサーバ『ShootingStar』を利用しています。『ShootingStar』は、ドリコム研究室長の瀧内元気が中心メンバーとして開発を行っています。
Lingr に続く、数少ない Comet 導入事例のひとつ。
すでにカーネルにマージ済みのKVMについては、ほぼ実用に耐え得るレベルに近づいてきたという言及があった。また、よりシンプルな仮想化方式として「Lguest」が紹介された。Lguestは特別なハードウェアを必要としない点が特徴で、Xenとともにカーネル2.6.23でメインラインに統合される見通しが示された。
さらに、サーバ仮想化を補完するテクノロジとして「コンテナ」という仕組みも紹介されている。
なお、Lguest は一度はマージされるも、2017年には削除されている。
The lguest virtualization system (which some of us still call the "rustyvisor") has been removed due to lack of interest and maintenance.
2008
インターネット
ロングテールな画像配信 その2 - 3,000万の画像を配信するシステム
今度はもっとも外側のサーバです。プロフィール画像へのリクエストはまずこのサーバで受ける事になります。これはmod_proxy(mod_proxy_balancer)とmod_rewriteなどを組み込んだApacheです。
ミクシィはもともと広く Apache を使っていたのもあり、当時もリバースプロキシとして Apache を使っている。ただ、著者の kazeburo さんによると、
この当時のApacheの使い方としては、アプリケーションを動かすのはprefork mpn、reverse proxyにはworker mpmを使っていた。worker であれば一台で数千コネクション以上は扱えた
リバースプロキシでは worker を使い、多数のコネクションをさばけていたとのこと。
2009
Ryan Dahl, Node.js を公開
node.js (PDF)
This is the node.js project: To provide a purely evented, non-blocking infrastructure to script highly concurrent programs.
リリース当初の Node.js は libevent ではなく、libev を使っていた。後に Windows サポートを理由に libuv に移行する。
As node.js grew in popularity, it was important to make it work on Windows, but libev ran only on Unix. The Windows equivalent of kernel event notification mechanisms like kqueue or (e)poll is IOCP. libuv was an abstraction around libev or IOCP depending on the platform, providing users an API based on libev. In the node-v0.9.0 version of libuv libev was removed.
Google, Go を公開
Want to write a server with thousands of communicating threads? Want to spend less time reading blogs while waiting for builds? Feel like whipping up a prototype of your latest idea? Go is the way to go! Check out the video for more information or visit golang.org.
スレッドの代わりに、より軽量な goroutine をもつ。リクエストごとに goroutine を作るというごく単純なモデルを使っても、性能が悪化しないのが特長。
インターネット
pixivのインフラを支える技術 (PDF)
Webサーバ apache 2.2.9 (prefork, event)
前掲のミクシィ同様に、2種類の Apache を組み合わせる構成。なお、著者の kamipo さんもいうとおり、Apache 2.2.x での event は "experimental" の扱いである。
2009年当時まだexperimentalだったApache event mpmを使ってますってイキってたときのわいの資料にリンク貼ってある！
2010
インターネット
秒間3,000PVを超えるアクセスを安定して捌く背後に技術者あり～DSAS技術統括責任者が考える技術へのこだわり～
例えば、仮想サーバーが最近流行っていて、「仮想サーバーを使って〇〇しました」っていう人はいるけど、「仮想サーバーを使うと何が嬉しいの？」という質問には答えられなかったりする人がいます。なぜ仮想サーバーが必要になったかということを考えたことがあれば、そうはならないと思うんです。
現在はデータセンター側にフロントサーバとして20台のNginxを設置して、これにURL文字列のハッシュ値をベースとする負荷分散の仕組み「carp」のモジュールを入れて使っているという。
最近シェアを伸ばしている高速 Web サーバ nginx。 組み込み Perl 機能や PSGI standalone server と組み合わせての使い方などを紹介します。
YAPC::Asia2010で「nginx & Perl」の発表をしてきました
YAPC::Asia2010 で、「nginx & Perl」という題名で20分の発表をさせていただきました。
2011
AWS, 東京リージョンを開設
Announcing the AWS Asia Pacific (Tokyo) Region
AWS is excited to announce the immediate availability of its new Asia Pacific (Tokyo) Region. Starting today, Japan-based businesses and global companies with customers in Japan can run their applications and workloads in the Tokyo Region to reduce latency to end-users, keep their data entirely in Japan, and avoid the undifferentiated heavy lifting associated with maintaining and operating their own infrastructure.
東京リージョン開設移行、国内の企業でも、クックパッドなどを皮切りに、インフラをクラウド上につくることが現実的になりはじめる。
そこで、シンガポールリージョンにあった時期からAWSを導入し、動的にサーバーを増やせるAWSのオートスケールを活用。「バレンタインにチョコ作る人の気持ちを考えたら、アクセス過多でレシピにアクセスできないなんてありえない。その女子の人生がかかっているかもしれない」と胸アツなコメントをした成田氏は、ピーク時でも快適にアクセスできるインフラをAWSで構築。コスト面に関しては、決してデータセンターの時と比べて安価になったわけではないが、余剰なサーバーを持たないで済むようになったという。
その後、2011年11月には、社内システムまで含めて、すべてのサービスをAWS化し、EC2とS3を組み合わせたVPC（Virtual Private Cloud）環境で運用している。「社内にはもはやほとんどサーバーはないです。社内wikiや人事評価システムも、AWS上に構築しています」（成田氏）。
クックパッドのAWS活用術 1日10回デプロイする大規模サイトの裏側 （前編）
クックパッドは昔はデータセンターを持っていましたが、2011年にAWSの東京リージョンができたのをきっかけに、AWSに全部サーバを移行しました。