Scalable memory allocation using jemallocの備忘録的和訳
Scalable memory allocation using jemalloc
jemallocは今使ったりしてるし，今後ソース読む可能性もあるので，適当に(精度とかは期待しないように！)．気になる人は元記事を読みましょう．
Scalable memory allocation using jemalloc
Facebookは，8コア+CPUと8GiB RAMな専用マシンの上で走っている，様々な種類のサーバアプリケーションの集合で構成されています．これらのアプリケーションは，CPUとRAMと最大限使う事によって最高のスループットを目標に，並行処理のため大体POSIXスレッドを使っています．この環境は，メモリアロケーションのための重大なチャレンジをもたらします．具体的に言えば，
- 確保と解放は速くなければいけません．理想的に，メモリアロケーションはアプリケーションの定常状態においてはほとんど必要になりませんが，これは動的な入力を基本とするデータ構造においては現実からはほど遠くなります．まぁまぁなアロケータの改善でさえ，スループットに多大な影響を及ぼすことが出来ます．
- 実際のメモリとRAMの使用量の関係は一貫していなければなりません．言い換えれば，アロケータによって引き起こされたフラグメンテーションによる実質的な限界はクリティカルなものとなります．もしフラグメンテーションが一日毎に1GiBのRAM使用量の増加を引き起こすのであれば，少しだけ余地を残すように設計されたアプリケーションは，数日の内に失敗するでしょう．
- メモリヒーププロファイリングはクリティカルな操作の補助となります．もし全てがプラン通りに行くのであれば，リークの検出と削除は開発のタスクとなります．しかしその場合でも動的な入力は，生産負荷の下での動作の解析によって特徴付けることが可能な，思いがけないメモリ使用のスパイクを引き起こすことが出来ます．
2009年，存在しているメモリアロケータはこれら3つの要件のうちたいてい2つは満たしていました，なので私たちはjemallocにヒーププロファイリングと多くの最適化を加えました，その結果jemallocは今3つ全てを満たしています．このポストの残りは，多数のFacebookのための改善を扱う前のjemallocのコアアルゴリズムとデータ構造のサーベイで，続いてWebサーバの負荷の下で6つのメモリアロケータを比較した実世界でのベンチマークがあります．
NOTE:Tech Talkの宣伝なので省く
コアアルゴリズムとデータ構造
CとC++は，malloc()，posix_memalign()，calloc()，realloc()，そしてfree()の5つの関数をメインに構成されるとても基本的な型付けのないアロケータAPIに依存しています．多くのmalloc実装もまた，malloc_usable_size()のような基本的な機能を提供しています．APIがシンプルな一方，高い並行でのスループットとフラグメンテーションの回避は無視出来ない内部の複雑さを要求します．jemallocはいくつかのオリジナルなアイディアと他のアロケータで最も有効なアイディアを組み合わせます．以下のアイディアとアロケーションの指針が絡見合い結合することで，jemallocとなっています．
- サイズクラスによって小さいオブジェクトを隔離し，再利用の間はlowアドレスを好んで選びます．このレイアウトポリシーはphkmallocから来ていて，jemallocの予測可能な少ないフラグメンテーション動作のキーとなっています．
- 注意深くサイズクラスを選びます(これはVamにインスパイアされています)．もしサイズクラスがとても広く間隔を開けて置かれたら，オブジェクトは過度な使えないスペースを持つ傾向にあります(内部のフラグメンテーション)．サイズクラスの数が増加するにつれて，現在活用されていないオブジェクトサイズのための未使用メモリも対応して増加する傾向にあります(外部のフラグメンテーション)．
- アロケータのメタデータのオーバーヘッドに厳しい制限を課します．フラグメンテーションを無視し全てのサイズクラスのため，jemallocはトータルのメモリ使用量の2%未満にメタデータを制限します．
- アクティブなページ集合を最小にします
OSのカーネルはページ(大抵一ページ4KiB)を単位として仮想メモリを管理します，なので全てのデータを可能であればいくつかのページへと集めることは重要なことです．phkmallocは，アプリケーションが定期的にHDへとアクティブなページをスワップアウトする問題に取り組む時に，このテネットを有効にしました(全体でスワップするのを回避するという問題が現在でも重要なものとして残っていますが)．
- ロック競合を最小にします
jemallocの独立したアリーナはlkmallocにインスパイアされていますが，時間が経つと，tcmallocは完全な同期を避けることがよりよいことだととてもクリアーにしました，なのでjemallocはまたスレッド特有のキャッシングを実装しています．
- もし汎用な目的でないなら，十分ではない
jemallocが最初FreeBSDへと併合したとき，それはいくつかのアプリケーションでの深刻なフラグメンテーションを持っていました．そして提案はOS内に複数のアロケータを含ませるために出されました．この考えは，開発者がアプリケーションの特性に基づいた知識のある選択をする公的な権限を与えるというものでした．正しいソリューションはパフォーマンスと予測を改善するため，劇的にシンプルなjemallocのレイアウトアルゴリズムでした．この1年で，この哲学はjemallocにおいて多数の大きなパフォーマンスの改善のモチベーションになりました，そしてこれは欠点が発見され続ける限り開発のガイドとなるでしょう．
jemallocは以下のような3つの大きなサイズクラスカテゴリを持っています(64bitシステムを想定しています)．
- Small: [8], [16, 32, 48, ..., 128], [192, 256, 320, ..., 512], [768, 1024, 1280, ..., 3840]
- Large: [4 KiB, 8 KiB, 12 KiB, ..., 4072 KiB]
- Huge: [4 MiB, 8 MiB, 12 MiB, ...]
仮想メモリは論理的に2^k(デフォルトで4MiB)サイズのチャンクへとパーティショニングされています．その結果，ポインタ操作経由で定数時間でsmall / largeオブジェクト(内部ポインタ)のためのアロケータのメタデータを見つけることが可能です，そしてグローバルな赤黒木を経由して対数時間でhugeオブジェクト(チャンクでアラインメントされた)のためのメタデータを探索します．
アプリケーションスレッドは最初にsmall / largeオブジェクトをアロケートした上にラウンドロビンなやり方でアリーナへと割り当てられます．アリーナは完全にそれぞれに独立しています．これらは自身のチャンクを管理し，small / largeオブジェクトのためにページを切り分けます．どのスレッドが解放を実行するかに関わらず，フリーなメモリはいつも自分が確保されたアリーナへと返されます．
各アリーナのチャンクはメタデータ(主にページマップ)を含んでいます，続いて一つ以上のページがあります．smallオブジェクトは，各ページの先頭に追加されたメタデータと共に一緒にグルーピングされ，largeオブジェクトは互いに独立していて，これらのメタデータは全てアリーナのチャンクヘッダに存在しています．各アリーナは赤黒木(各サイズクラス毎に一つ)を経由することでsmallオブジェクトのページを追跡します，そしていつもそのサイズクラスのためのlowestなアドレスとページを用いてアロケーション要求に対して情報を提供します．各アリーナは二つの赤黒木を使って利用可能なページを追跡します(一つは綺麗で未使用なページ，もう一つは既に使われたことのあるダーティなページ)．ページは優先的に，ダーティツリーからlowestでベストフィットするところからアロケートされます．
各スレッドはsmallオブジェクトのキャッシュを管理するのと同様に，largeオブジェクトを制限サイズ(デフォルトで32KiB)までキャッシュを管理します．それゆえに，アロケーション要求の大部分はアリーナにアクセスする前に，キャッシュされた利用可能なオブジェクトがあるかをまずチェックします．スレッドキャッシュ経由のアロケーションはアリーナの貯蔵庫(smallサイズクラスのための一つ)をロックする必要があります，そして/またはアリーナ全体として．
スレッドキャッシュのメインの目的は同期イベントの削減です．しかしながら，各サイズクラスのためにキャッシュされたオブジェクトの最大数は，実際には同期の減少を考慮すると10-100xレベルとなっています．高めのキャッシュ制限はいくつかのアプリケーションではアロケーションのスピードアップをもたらしますが，大抵のケースで受け入れ難いフラグメンテーションコストもあります．更なるフラグメンテーションの制限のため，スレッドキャッシュは，アロケーションリクエストを単位として時間を計測する，インクリメンタルGCを行います．一つ以上のGCが過ぎた未使用なキャッシュオブジェクトは指数的に低下するアプローチを用いて，各自のアリーナへと徐々にフラッシュされます．
Facebookベースのイノベーション
2009年，Facebookのエンジニアが"jemallocの一貫性と信頼性は素晴らしいがまだ速く出来るし，加えてそれが実際に行っていることをモニターするよりよい方法が必要だ"とjemallocの有効性を要約しました．
スピード
私たちは多くの改善点を作ることでスピードアップに取り組みました．以下はそのハイライトです．
- スレッドキャッシングの書き換え
改善された速度のほとんどは一定要因となるオーバーヘッドの削減から来ていますが(これらはクリティカルなパスで大切です)，私たちもまたキャッシュサイズの厳しい制御が，キャッシュを埋める/フラッシュするコスト増加を和らげる傾向にある，データの局所性をしばしば改善することに気付きました．しかしながら，私たちはサイズ制御(各サイズクラスのための制限と，他のスレッドから完全に独立したインクリメンタルGC)とデータ構造(各サイズクラスのためにシングルリンクLIFO)を単位とするとてもシンプルなデザインを選択しました．
jemallocは以前はとてもシンプルなロック戦略を取っていましたが(エリア毎に一つのmutex)，私たちは特にLinux Kernel 2.6.27以前のために，劇的な直列化の効力を持つmmap()，munmap()，madvise()のシステムコールの間はアリーナmutexを持つ事に決めました．しかしながら，私たちはアリーナのチャンクとページにまつわる全ての操作を保護するためアリーナのmutex群を降格させました，そして各アリーナのため，小さなallocation / deallocationで通常アクセスされるデータ構造を保護するため，smallサイズクラス毎に一つのmutexを追加しました．これは不十分な対処ですが，私たちはmadvise()を呼ぶ前に全てのmutex群をdropするためのダーティページのパージング機能を再設計しました．この変更は，Linux 2.6.27以降のmutexの直列化問題を完全に解決しています．
- ダーティページパージングの書き換え
ダーティページの最大数は，定数よりはむしろトータルのメモリ使用量に比例しています，私たちはまた，一体化したものではなく，クリーンなものとダーティで未使用なページを分離させました．優先的にダーティページを再利用するために，トータルのダーティページのパージングを行うボリュームが減少します．この変更は少々仮想メモリ使用量を増加させますが，これはスループットにおいて肯定的な影響と思うことが出来ます．
- 新しい赤黒木実装の開発
これは同じlowメモリオーバーヘッド(一つのノードに二つのポインタ)ですが，挿入/削除においておおよそ30%速くなっています．この改善は私たちのアプリケーションの一つにとってとても大切なものでした．以前の実装は2-3-4木ベースのLL(Left-Leaning)赤黒木で，全ての操作は降下パスだけで行うことが出来ました．この反復アプローチは再起や親ポインタの必要性を回避しますが，木の一貫性が連続する上昇パスの間ゆっくりと保存されるならば回避できる，外部の木の操作を必要とします．実験は，最適な赤黒木実装はゆっくりとfix-up(木のバランスを整える)すべきだと示しました．さらに，fix-upはしばしば上昇パスが完成する前に終了し，そして再起の巻き戻しはこのようなケースでは受け入れ難いコストです．私たちは，下降パスの間は親ポインタの配列を初期化する非再帰な2-3木ベースのLL赤黒木実装に定め，可能であれば早期に終了させるため，上昇パスでは遅延fix-upのため配列を使います．
振り返り(Introspection)
jemallocはいつもアプリケーション終了時に，human-readableな形式で詳細な内部統計を表示することが可能ですが，これは長期間走るサーバアプリケーションでは制限された使用になります．なので，私たちはアプリケーションによって何度も呼ばれることが可能なmalloc_stats_print()を晒しました．不幸にもこれはまだコンシューマにパージングする負担を課しますが，私たちは個々の統計へのアクセスを提供するBSDのsysctl()システムコールのような，mallctl*()APIを追加しました．私たちは完全なカバレッジを確実にするために，malloc*()を単位としてmalloc_stats_print()を再実装して，そしてゆっくり時間をかけてまた，たくさんの制御(スレッドキャッシュのフラッシュやダーティページパージングの強制など)を提供するためこの機能を拡張しました．
メモリリークの診断は，プロダクションがまだ動いている状態でリークを暴く必要がある時は特に，大きなチャレンジを引き起こします．Googleのtcmallocはプロダクションユースに合った素晴らしいヒーププロファイリング機能を提供しており，私たちはそれがとても有益なものだと気付きました．しかしながら，jemallocだけが適切にメモリ使用量を制御でき，tcmallocだけが適切にメモリ使用量を解析するツールを提供していたので，いくつかのアプリケーションではますますジレンマに直面していました．そのため，私たちはjemallocに互換性のあるヒーププロファイリング機能を追加しました．これによってtcmallocを搭載している後処理ツールを活用できるようになりました．
Experimental
必要であれば．
Future work
jemallocは現在とても成熟していますが，アリーナがどうスレッドに割り当てられるかなどの既知の欠点が残っています．大きな静的なデータ構造を置くためスレッドプールを立ち上げるアプリケーションを考慮するとき，残りを実行するためシングルスレッドな操作へと戻ります．アプリケーションがアリーナの割り当て(もしくは単純にアリーナの数を制限する)の制御に特別なアクションを取らない場合には，初期化フェーズは具合の悪いよく利用されるアリーナの荒れた領域(高いフラグメンテーションなどがある)を置き去りにしがちです．workaroundsは存在していますが，これらが予期しないアプリケーションの動作で起こる時のため，私たちはこれと他の問題に取り組むつもりです．
Acknowledgments
Andrei先生がいて驚き！
