Linux カーネル共有メモリーの徹底調査

Linux カーネルでのメモリー重複排除

ハイパーバイザーとしての Linux® には数々の革新技術が盛り込まれていますが、なかでも 2.6.32 カーネルで特に興味深い変更内容の 1 つとなっているのが、カーネル共有メモリー (KSM: Kernel Shared Memory) です。KSM により、ハイパーバイザーは重複するメモリー・ページを 1 つに統合し、同時に稼働する仮想マシンの数を増やすことができます。この記事を読んで、KSM の背後にある概念 (ストレージの重複排除など)、その実装、そして KSM の管理方法を学んでください。

M. Tim Jones, Independent author

M. Tim JonesM. Tim Jones は組み込みソフトウェアのエンジニアであり、『Artificial Intelligence: A Systems Approach』、『GNU/Linux Application Programming』現在、第 2 版です) や『AI Application Programming』(こちらも現在、第 2 版です)、それに『BSD Sockets Programming from a Multilanguage Perspective』などの著者でもあります。技術的な経歴は静止軌道衛星用のカーネル開発から、組み込みシステム・アーキテクチャーやネットワーク・プロトコル開発まで、広範にわたっています。また、コロラド州ロングモン所在のEmulex Corp. の顧問エンジニアでもあります。


developerWorks 貢献著者レベル

2010年 4月 07日

Tim とつながるには

Tim は developerWorks で人気の高いお馴染みの著者の 1 人です。Tim が書いたすべての developerWorks の記事を閲覧してみてください。また、My developerWorks では、Tim のプロフィールを調べることや、彼やその他の著者、そして他の読者とつながることができます。

ソフトウェア・エンジニアリングは、終わりなき進化のプロセスとなりがちです。ソリューションによって問題を解決すると、それがまた新たな問題を作り出し、その問題をさらに新しいソリューションで解決するといった具合です。観念的には、新しい問題が発生するということは、最初のソリューションが正当化されたということになります。ここで説明する技術は、このような派生的ソリューションの 1 つであり、サーバー仮想化によって発生した問題に対処するためのソリューションです。KSM の詳細に入る前に、まずはサーバー仮想化というソリューションの概要と、サーバー仮想化や他の分野で KSM がどのように適用されているかを簡単に説明しておきます。

サーバー仮想化

究極のサーバー統合

エンタープライズ・サーバーは仮想化によって 10 台以上のサーバーを統合することが可能ですが、IBM System z® サーバーであれば 1 台だけでも、1 つの論理区画につき数千の Linux® ゲストをサポートすることができます。

技術としての仮想化は 1960年代から登場しており、IBM® System/360® メインフレームによって実用化されました。それから 50 年経った今、仮想化は急成長を遂げ、1 台のサーバーを複数のオペレーティング・システムやアプリケーションで共有できるようになっています。サーバー仮想化と呼ばれるこの特定の仮想化は、現在データ・センターの形を変えつつあります。サーバー仮想化では、1 台の物理マシンで通常は 10 台以上の仮想マシン (VM) をホストすることができるためです (図 1 を参照)。サーバー仮想化によって、データ・センターのインフラストラクチャーを一段と動的で、電力効率に優れた (その結果として) コスト効果の高いものにすることができます。サーバー仮想化とその利点についての詳細は、「参考文献」を参照してください。

図 1. 仮想化によるサーバー統合
サーバー統合の図。この図では、仮想化によって複数の物理マシンが 1 台の物理サーバーに統合されています。

常時、一般的なサーバーの 10 パーセントから 15 パーセントしか使用されていないとしたら、複数の仮想サーバーを 1 台の物理サーバーに統合するのが妥当なのは明らかです。ではリソースについてはどうなのでしょうか。使用可能なリソースは、主に CPU、メモリー、ネットワーク帯域幅です。CPU とネットワークがフルに使用されることは通常ないため、統合したときに実際に問題となるのは使用可能なメモリー容量にあります。オペレーティング・システムには、使用可能なメモリー・リソースに関してそれぞれに独自の要件がありますが、一体これらの要件はどの程度独自のものなのでしょう。


メモリーの共有

同じオペレーティング・システムとアプリケーションのセットをいくつも仮想化すると、同一のメモリー・ページが多数出てくることになります。オペレーティング・システムとアプリケーションのコードおよび定数データはすべての VM で共通していることを考えると、そうなるのは当然です。また、それぞれのページが固有の場合でも、1 台の物理マシンに統合することで、他のアプリケーションで使用できるようにメモリーを解放することができます。メモリーの共有を表した図 2 を見るとわかるように、同じコンテンツを持つ複数の VM でページを共有すると、使用可能な空きメモリーが増えるという利点があります。

図 2. VM 間でのメモリー共有
メモリーの共有を表す図。同じコンテンツを持つ複数の VM でページを共有することによって、使用可能な空きメモリーが増えます。

機能の名前について

この記事で説明する機能はとても新しいものなので、その名前はまだ確定していません。この Linux カーネル機能は、Kernel Shared Memory とも、Kernel Samepage Merging とも呼ばれています。

この後すぐにわかるように、Linux でのメモリー共有は仮想化された環境でメリットがありますが (KSM は当初、カーネルベースの仮想マシン (KVM) で使用するように設計されました)、仮想化されていない環境でも役に立ちます。実際、組み込み Linux システムでも KSM を使用するメリットがあることが明らかになったことが、この手法の柔軟性を物語っています。ここからは、Linux によるメモリー共有の手法について説明し、この手法を使用してサーバーの「メモリー密度」を増加させることによって、サーバーがさらに多くのアプリケーションや VM をホストできるようになる仕組みを説明します。


他の技術との共通点

重複排除 (de-duplication) と呼ばれる最近のストレージ技術の進歩は、Linux やその他のハイパーバイザーでのメモリー共有の先駆けです。重複排除とは、重複するデータを (ブロック単位、またはブロックよりも大きいファイルなどのデータ・セグメント単位で) 取り除くことによってデータの保存量を減らす技術のことです。共通のセグメントは (コピー・オン・ライト (CoW) 方式で) マージされ、他の用途のためにスペースを解放します。このように重複するデータを削除してストレージの容量を最適化するストレージの重複排除は、重要な技術として進化し続けています。重複するデータがなくなれば、結局はストレージの所要量が少なくなり、それによってストレージにかかるコストも下がります。データの増加速度を考えると、この機能は非常に大きな意味を持ちます。


KSM の動作

KSM はカーネル内でデーモン (ksmd) として、周期的にページをスキャンし、重複するページを特定してマージすることによって、ページを他の用途に使えるように解放します。この動作は、ユーザーにはわからないように行われます。例えば、重複するページがマージされても (マージされた後には、読み取り専用のマークが付けられます)、そのページのユーザーのうちの 1 人が何らかの理由でページを変更した場合には、そのユーザーは独自のコピーを受け取ります (CoW 方式)。カーネル・ソース内での KSM カーネル・モジュールの全実装は、./mm/ksm.c で確認することができます。

KSM では、どのメモリー領域をマージ候補とするかを上位レベルのアプリケーションから指示します。KSM が単純にシステム内のすべての匿名ページをスキャンすることも可能ですが、それでは (ページのマージ・プロセスを管理するためにスペースが必要になることから) CPU とメモリーの無駄になります。したがってアプリケーションが、重複するページが含まれている可能性のある仮想領域を登録できるようになっています。

KSM のアプリケーション・プログラミング・インターフェース (API) は、madvise システム・コール (リスト 1 を参照) と MADV_MERGEABLE という新しいアドバイス・パラメーター (定義された領域がマージ可能であることを示すパラメーター) によって実装されます。領域をマージ不可の状態に変更するには、MADV_UNMERGEABLE パラメーターを使用します (すると、マージされたページがすぐにその領域から分離されます)。madvise を使用してページ領域を削除すると、EAGAIN エラーが発生する場合があることに注意してください。これは、操作がマージ解除のプロセス中にメモリーを使い果たしかねないからです。メモリーを使い果たした場合には、さらに大きな問題 (メモリー不足の状態) になることも考えられます。

リスト 1. madvise システム・コール
#include <sys/mman.h>

int madvise( void *start, size_t length, int advice );

領域がマージ可能として定義されると、KSM はこの領域をワーキング・メモリーのリストに追加します。そして有効になった時点で、同一のページを検索し、そのうちの 1 つを書き込み保護の CoW 方式で保持した上で、そのページと同じ内容のページを他の用途のために解放します。

KSM が使用する手法は、ストレージの重複排除で使用されている手法とは異なります。従来の重複排除では、オブジェクトをハッシュ値に変換し、そのハッシュ値を初期の類似チェックとして使用します。ハッシュ値が同じ場合は、次のステップとして実際のオブジェクトを比較し (この場合はメモリーの比較)、オブジェクトが同一であるかどうかを正式に判別します。KSM の最初の実装でも同じ手法が使用されていましたが、KSM を単純化するために、その後、より直接的な手法が開発されました。

現行の KSM では、ページは 2 つの赤黒木で管理されます。2 つのうちの 1 つは一時的な赤黒木です。不安定ツリー (unstable tree) と呼ばれる最初の赤黒木は、安定しているかどうかがまだわかっていない新しいページを保存するために使用されます。つまり、不安定ツリーにはマージ候補となるページ (一定の期間、変更されないページ) が保存されます。不安定ツリーに保存されるページは、書き込み保護されません。2 番目の赤黒木は安定ツリー (stable tree) と呼ばれ、ここには安定していることが確認されていて、KSM によってマージされたページが保存されます。KSM は、対象のページが頻繁に変更されるページであるか、それともあまり変更されないページであるかを識別するために、単純な 32 ビットのチェックサムを使用します。ページをスキャンする際にチェックサムが計算され、ページと一緒に保存されます。その後のスキャンで、新しく計算されたチェックサムが前に生成されたチェックサムと異なる場合に、そのページは変更されていることになります。したがって、マージする候補としてはふさわしくありません。

KSMのプロセスによる各ページの処理は、まず、安定ツリーにそのページがあるかどうかを調べるところから始まります。安定ツリーの検索プロセスで興味深い点は、各ページを (ページのコンテンツを表す) 非常に大きな数値として扱っていることです。memcmp (メモリー比較) 操作は、基準とするページと、そのページとの比較を行うノードのページで行われます。memcmp 操作が 0 を返した場合、2 つのページは等しく、一致が検出されたことを意味します。ページが一致しなければ、memcmp-1 (マージ候補のページが現行ノードのページより小さい場合) または 1 (マージ候補のページが現行ノードのページより大きい場合) を返し、いずれの場合も赤黒木で検索を続行します (現行ノードのページより小さい場合は赤黒木の左方向を検索し、大きい場合は右方向を検索します)。4KB のページを比較するのはかなり大変な作業に思えますが、ほとんどの場合、memcmp は違いが検出された時点で処理を終了します。したがって、プロセス自体は短時間かつ効率的に行われます。図 3 に、このプロセスを図解します。

図 3. 赤黒木でページを検索するプロセス
赤黒木でページを検索するプロセス。マージ候補のページとの一致が示されています。

マージ候補のページが安定ツリーに見つかった場合には、ページがマージされ、候補ページが解放されます。このコードについては、ksm.c/stable_tree_search() を参照してください (ksm.c/cmp_and_merge_page() が呼び出すコードです)。マージ候補ページが安定ツリーに見つからなければ、不安定ツリーの検索に移ります (ksm.c/unstable_tree_search() を参照)。

不安定ツリーの検索で最初のステップとなるのは、ページでチェックサムを再計算することです。結果が元のチェックサムと異なる場合、このスキャンでは、そのページが以降の検索から除外されます (変更されている場合、追跡しても無駄だからです)。チェックサムが変更されていなければ、不安定ツリーでマージ候補のページが検索されます。不安定ツリーの処理は、安定ツリーとは多少異なります。まず、不安定ツリーを検索してページが見つからない場合には、不安定ツリーに、そのページのための新しいノードを追加します。一方、ページが見つかった場合には、そのページをマージした後、ページのノードを安定ツリーに移します。

スキャン (ksm.c/ksm_do_scan() によって実行) が完了すると、安定ツリーは保持されますが、不安定ツリーは削除されます。不安定ツリーは、次回のスキャンが行われる時点で再作成されます。このプロセスでは、ページの変更に応じて不安定ツリーの編成も変更できることから (不安定ツリーに保存されたページは書き込み保護されないことを思い出してください)、全体的な仕組みが多少単純になります。安定ツリーに保存されるページはすべて書き込み保護されるため、ページに対する書き込みが試行されるとページ・エラーが生成されます。これによって CoW プロセスはページのマージを解除し、ライターがページに書き込めるようにします (ksm.c/break_cow() を参照)。そしてその後、安定ツリーの中で親がなくなったページが削除されます (ただし、ページのユーザーが 2 人以上いる場合には、そのページはまだ共有されていることになるので削除されません)。

以上のように、KSM は赤黒木を使用してページを管理することで、ページを素早く検索できるようにしています。Linux ではこのような赤黒木を再利用可能なデータ構造として組み込み、一般的に使用できるようになっています。赤黒木は、CFS (Completely Fair Scheduler) でも、タスクを時間順に保存するために使用されています。カーネルでの赤黒木の実装については、./lib/rbtree.c を参照してください。


KSM の構成とモニター

KSM の管理およびモニターは sysfs (ルートの /sys/kernel/mm/ksm にあります) によって行われます。この sysfs サブディレクトリーには、制御に使用するファイル、モニターに使用するファイルがまとめて置かれています。

run というファイルは、KSM によるページのマージを有効または無効にするために使用します。デフォルトで KSM によるページのマージは無効 (0) に設定されていますが、run ファイルに 1 を書き込み (例えば、echo 1 > sys/kernel/mm/ksm/run)、KSM デーモンを有効にすることによって、KSM によるページのマージを有効にすることができます。実行中の KSM デーモンを無効にするには、この run ファイルに 0 を書き込みます (ただし、現行の一連のマージ済みページは維持されます)。また、実行 (1) 中に 2 を書き込むと、KSM を停止して、マージされたすべてのページについて、マージを解除するように要求することができます。

KSM を実行中に制御するには、3 つのパラメーター (sysfs 内のファイル) を使用します。まず、sleep_millisecs ファイルは、ページ・スキャンを完了した後に、次のページ・スキャンを実行するまで ksmd をスリープ状態にする期間 (ミリ秒数) を定義するファイルです。max_kernel_pages ファイルには、ksmd が使用できるページの最大数を定義します (デフォルトは使用可能なメモリーの 25 パーセントですが、0 を書き込んで無制限に使用できるように設定することもできます)。そしてもう 1 つのファイル、pages_to_scan では、スキャンするページ数を定義することができます。この 3 つのファイルは、任意のユーザーが表示することができますが、変更する場合にはユーザーに root 権限が必要です。

上記とは別に、sysfs によってエクスポートされた 5 つのファイルがあります。これらのファイルでは、ksmd の動作と効率性をモニターすることができます (読み取り専用ファイルです)。そのうちの 1 つ、full_scans ファイルは、全領域のスキャンが行われた回数を示します。残りの 4 つは、ページ・レベルの KSM 統計値を示すファイルです。

  • pages_shared: KSM が使用しているスワップ不可能なカーネル・ページの数
  • pages_sharing: メモリーの節約状況についての情報
  • pages_unshared: マージ対象として繰り返しチェックされた固有のページの数
  • pages_volatile: 頻繁に変更されているページの数

KSM の作成者たちは、pages_shared に対する pages_sharing の比率が高ければ、ページが効率的に共有されていることを意味すると定義しています (その逆は、ページに無駄があることを示しています)


さらに詳しく調べてください

ページ共有によってメモリーの効率性を改善しているのは Linux だけというわけではありませんが、これをオペレーティング・システムの機能として実装している点では他に類をみません。メモリー共有機能は、VMware の ESX サーバー・ハイパーバイザーでは TPS (Transparent Page Sharing) という名前で提供されており、XEN では Memory CoW という名前で提供されています。けれども名前や実装の違いに関わらず、この機能はメモリーをさらに賢く使用し、それによってオペレーティング・システム (KVM の場合はハイパーバイザー) がメモリーを余分にコミットできるようにして、より多くのアプリケーションや VM をサポートすることを可能にします。KSM (そしてその他多くの興味深い機能) について、最新の 2.6.32 Linux カーネルで調べてください。

参考文献

学ぶために

  • Red Hat の KSM 作成者たちによる優れた記事、「Increasing memory density by using KSM」(PDF 版) を読んでください。この記事で KSM について紹介し、その実装の詳細を掘り下げて説明しています。
  • 仮想化は、統合によって電力節約とコスト節約を実現する方法としてだけでなく、クラウド・コンピューティングの主要な要素としても急激に成長しています。「Growing green with virtualization: Virtualization as a backbone of green IT」(developerWorks、2009年8月) を読んで、仮想化について、そして環境にグリーン IT でのその役割について学んでください。
  • この記事では、Linux をハイパーバイザーとして使用することによってもたらされる利点を説明しました。Linux ハイパーバイザーの利点についての詳細と、その他のトピックについては、「Linux ハイパーバイザーの徹底調査」(developerWorks、2009年5月)、「Linux カーネル仮想マシンを探る」(developerWorks、2007年4月)、「仮想 Linux」(developerWorks、2006年12月) を読んでください。また、「Linux 2.6 Completely Fair Scheduler の内側」(developerWorks、2009年12月) では、赤黒木を使用する別のカーネル・サブシステムについて説明しています。
  • メモリーの重複排除については、2.6.32 カーネルのリリース・ノートで詳しく説明しています。これらのリリース・ノートは、KSM についてだけでなく (カーネルの資料へのリンクも記載)、2.6.32 に至る過程で行われた KSM 以外のさまざまな変更内容についても有益な情報を提供します。KSM のセクションでは、16GB のRAM を搭載した単一のサーバーで 52 の Windows® XP VM を実行するという興味深い方法を説明しています (この場合、VM にはそれぞれ 1GB の RAM セグメントが割り当てられますが、セグメントは KSM によって共有されます)。
  • IT Analysis の記事「De-dupe for big storage savings?」で、ストレージ・システムの重複排除についての詳細と、その手法を学んでください。
  • ウィキペディアで、重複排除についての概要と、さまざまな実装ストラテジー (ソースとターゲットなど) について詳しく説明しています。
  • KSM は仮想サーバーでのメモリー・フットプリントを削減する自動メカニズムですが、アプリケーション開発者はこれまでも同様の手動による機能を使ってきました。Linux の動的 (共有) ライブラリーでは、バイナリー・コードがアプリケーションで静的にコンパイルされたオブジェクトの代わりに共通ライブラリー・オブジェクトを使用することができます。「Linux 動的ライブラリーの徹底調査」(developerWorks、2008年8月) を読んで、共有ライブラリーについて詳しく学んでください。
  • 赤黒木 (symmetric binary B-tree) は、Rudolf Bayer によって発明された平衡木です。これは便利なツリー表現で、挿入・検索・削除などの操作にかかる最大の時間を明確に表します。連想配列を含め、赤黒木はさまざまなアプリケーションで使用されています。
  • developerWorks Linux ゾーンで、Linux 開発者および管理者向けのハウツー記事とチュートリアル、そしてダウンロード、ディスカッション、フォーラムなど、豊富に揃った資料を探してください。
  • さまざまな IBM 製品および IT 業界についての話題に絞った developerWorks の Technical events and webcasts で時代の流れをキャッチしてください。
  • 無料の developerWorks Live! briefing に参加して、IBM 製品およびツール、そして IT 業界の傾向を素早く学んでください。
  • developerWorks の on-demand demos で、初心者向けの製品のインストールおよびセットアップから熟練開発者向けの高度な機能に至るまで、さまざまに揃ったデモを見てください。
  • Twitter で developerWorks をフォローするか、developerWorks で Linux に関するツイートのフィードに登録してください。

製品や技術を入手するために

  • ご自分に最適な方法で IBM 製品を評価してください。評価の方法としては、製品の試用版をダウンロードすることも、オンラインで製品を試してみることも、クラウド環境で製品を使用することもできます。また、SOA Sandbox では、数時間でサービス指向アーキテクチャーの実装方法を効率的に学ぶことができます。

議論するために

  • My developerWorks コミュニティーに加わってください。ここでは他の developerWorks ユーザーとのつながりを持てる他、開発者が主導するブログ、フォーラム、グループ、ウィキを調べることができます。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=487113
ArticleTitle=Linux カーネル共有メモリーの徹底調査
publish-date=04072010