2011-01-10
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
必要であれば．
Successes at Facebook
図を見れば分かる．前提がFacebookなので，使うなら自分の環境で確認すべし．
Future work
jemallocは現在とても成熟していますが，アリーナがどうスレッドに割り当てられるかなどの既知の欠点が残っています．大きな静的なデータ構造を置くためスレッドプールを立ち上げるアプリケーションを考慮するとき，残りを実行するためシングルスレッドな操作へと戻ります．アプリケーションがアリーナの割り当て(もしくは単純にアリーナの数を制限する)の制御に特別なアクションを取らない場合には，初期化フェーズは具合の悪いよく利用されるアリーナの荒れた領域(高いフラグメンテーションなどがある)を置き去りにしがちです．workaroundsは存在していますが，これらが予期しないアプリケーションの動作で起こる時のため，私たちはこれと他の問題に取り組むつもりです．
Acknowledgments
Andrei先生がいて驚き！
Permalink | コメント(0) | トラックバック(1) | 13:41 
2011-01-01
2010年を振り返る
乗るしかない，このビッグウェーブに！
人生的なもの
博士課程まで行ったわけですが前年を持って退学し，今年から働きます．朝生でも色々話にあがりましたが，動けばチャンスはやってくる．夢の東京生活！
D言語
ここから今年が始まった気がします．
- std.base64 (リプレース)
- std.utf (エンハンスメント)
- std.socket (リプレース中)
- std.event (誰も書かないなら俺がやるしかない？)
- std.msgpack (RPCとか途中)
その他パッチとかちょくちょく
勉強会関係
- 第1回関西Emacs勉強会参加してました
- オープンセミナー2010@岡山
- x86勉強会 & カーネル/VM勉強会
- 日本Ruby会議2010
- MessagePackハッカソン 第2回
- Boost.勉強会 #2
- Boost勉強会@関西
- 全文検索エンジンgroongaを囲む夕べ #1
- 非公式名古屋Scala
他なんか出てたかな？発表増やしたい…
本
レビュアとして参加してました．俺のコメントが載ってたりします！
広告出させてもらいました．次は記事を(ｹﾞﾌﾝｹﾞﾌﾝ
その他
- MacBook Air, Kindleのおかげでかなり移動が楽になった
- Dvorack, Homebrewなどちょっと環境を見直したりした
多分今までで一番充実した1年だった気がする．ただD言語以外へのコミットが減ってるので，この辺もう少し手広くしたい．
Permalink | コメント(0) | トラックバック(0) | 08:34
2010-12-05
Dvorak-erへの道
一般的なQWERTY配列からDvorak配列へと変更．この一ヶ月で慣れる！
http://d.hatena.ne.jp/Yuzuemon/20101205/1291476984
Permalink | コメント(0) | トラックバック(0) | 17:03
2010-10-11
PFIインターンのまとめ - 大野編 -
このまとめは俺の感想ではなく，同じくインターンに参加した大野君によって書かれました．「なんでこいつ2回書いてんだ？」と誤解なきようお願いします．
インターン採用まで
そもそもPFIインターンを知ったのは過去にPFIでインターンで参加していた大倉さんのブログがきっかけでした。就職するならプログラミング関係が良いなと思い，その訓練も兼ねて応募しました。
ほとんどお遊びでしかプログラミングはした事がなかったですが，中学高校時代で関連する部分をありったけアピールして奇跡的に採用されることに。
後から聞いた話では社長の西川さんは数学を専攻していた自分が来る事を相当楽しみにしていたようです。
インターン開始〜前半
2日目でとんでもない所に来てしまった自覚しました。
ホームページのメンバー紹介を見てある程度覚悟していましたが予想を超えていましたし，
他のインターン3人も尖ってました
（言語を使う立場じゃなくて作る立場って・・・，Haskellなんて言語初めて聞いたよ・・・後ろで黙々とタイプする音が聞こえる・・・）。
場違いかと思いましたが，基本的な所から丁寧に教えていただきました。
分からない所があれば社内チャットで聞けばすぐに返答が返って来て，
書いたコードをすぐにレビューしてもらえる環境が整っていたのはありがたかったです。
テーマ決定
今回「既存のサービスに導入できそう」などの理由で
twitterがテーマとなり，その中でも特に何か事件等で議論で盛り上がる事があるのでそれを検出しようとなりました。
PFIセミナー
インターンが中頃に，セミナーを行いました。
（このセミナーはインターン期間以外でも週に1回持ち回りで持ち回りで行うそうですが，
インターンの楽しみの一つでした）
他の3人の個性の中で自分が埋もれていたので，これはチャンスと思い100%数学の話をする事に，以下はその時用いたスライドです。
インターン後半
何をすべきかわからず手が動かなくなる状態になったり，ピントのはずれた作業に時間をかけたりする事が目立ちました。メンターの岡野原さんに助言を頂いて，残り日数と自分のプログラム能力の落としどころを見つけられた用に思います。研究のやり方や仕事の仕方など学べる部分が多かったです。
以下が最終発表のスライドです。
また，当日Ustreamで配信されました。以下のアドレスからその時の配信を見る事が出来ます
まとめ
ひょんな事からソフトウェアのベンチャー企業にプログラム初心者が紛れ込んだのですが，
非常に刺激的な経験をさせてもらいました。高慢に飛び込んで正解だったと思います。
来年もインターンを行うのではないかと思うので，プログラミング能力を鍛えたい方，チームでプロジェクトに取り組んでみたい方，自然言語処理のエキスパートに会いたい方には是非おすすめします。
Permalink | コメント(0) | トラックバック(3) | 11:26
2010-10-03
ピーFIという会社で行ったRed Bullを2ヶ月間飲み続けるだけの簡単なお仕事を振り返る
タイトル通り2ヶ月間ほど東京でインターンに参加してました．真面目な俺は他の濃過ぎるインターンメンバに比べて影が薄かったため，某バスケ選手のようにすぐ忘れ去られてしまう可能性があるので，ここで記事にしておきます．
申し込み
多分俺が一番最後に申し込みをしたはず．というのも〆切最終日に金曜ロードショーの「踊る大捜査線」を見ながらこんなことを呟いたら@frsyukiからこんなreplyが来た．じゃあ書くかとWebで履歴書のテンプレをダウンロードし自分の過去の業績を探し(そんなのないけど！)，必要書類を23:59分に送信した．
履歴書の写真欄が空白なのが寂しかったのでD言語の可愛いくて有名な某マスコットキャラを整形して貼付けたにも関わらず，何事もなかったかのように面接に進んだので，ピーFIはとても懐が広い会社だなと思いました．
面接
俺がT島という海外にいるということで，Skypeでやって頂いた．いくつか面接っぽいことをした後はコーティング．問題はこれで，面接に備えてdmdのtrunkをビルドしてたら標準ライブラリが上手くビルド出来なくて再DLするのも面倒だったので，Rubyでやった．D言語は素晴らしい言語です．
で，何故か通ったのでインターンに参加することとなりました．
やったこと
テーマに関しては「グループ開発の経験などをしてみたい」というようなことを面接でやり取りをしていたので，Sedueの開発に組み込まれました．メンターも開発チームのちくわkzkさんとGodBullnobu_kさんの二人になりました．主にやったのは以下の3つで，非常にやりがいのある仕事でした．
- Red Bullを最低1日1本は飲む (RedBull Driven Developmentの実践)
- 毎日地獄のミサワを確認する (最新情報を仕入れることで世の流れに送れないようにする)
- CTOを弄る (社員さんとの円滑なコミュニケーション)
その他にやったことに関しては9/30に行われた最終発表で述べました．スライドは以下で，動画はUstで録画されているはずです．
最初からSedueを弄るということは無理なので，少しずつタスクの粒度を上げて行くという感じでやりました．実際の所，最終目標の1億件周りをやることが決まったのは中間発表の前くらいでした．途中こんなハプニングもあったので，もう少し自分の力をセーブすべきだったかもしれません(ｵ
一億件検証が上手く行かなかったのは残念ですが，自分の書いたものが今でもどこかで動いていると思うと，ちょっと感動ものです．
全体の感想
ピーFIは自分にとって非常にやりやすい環境でした．開発環境も勿論のこと，どの社員さんも近くチャットなどを通じていつでも下ネタ様々な話が出来ました．かといってずっとそんな雰囲気な訳でもなく，技術的な話や製品の議論になるとｶﾞﾗｯと空気が変わるので，非常にメリハリがあったと思います．自分と現状直接関わりがないことでも，チャットの流れを見ていたり話を聞いてたりすると「ふむふむ」と思うことが多々ありました．技術的に話が出来ることの楽しさは今の研究室では得ることが出来ないので，この辺は本当日々充実してました．
後，かなり就業スタイルが個人に任せられているので，勿論MTGなどは時間は決めて行われるけど，それ以外は結構バラバラだったりして非常に助かりました(朝起きれない訳ではなく，昼からの方が調子いいんです！！)．
社内セミナーの自然言語処理などの話で分からない所が結構あったのが悔しいので，この辺はいくつか教えて貰った本で学習しておきたい．
2ヶ月って長いなぁと最初思ってたけど，始まったらあっという間だった(1週間や2週間のインターンはどういうことをやっているのだろうか…)．今回インターンに参加して刺激を受けたことで色々考えも変わったので，とりあえず行動を起こす．
最後に
来年もD言語枠があるはずなので(本当？)，興味のある人はピーFIのサマーインターンに申し込んだらいいんじゃないかな！
こんな長文書くの久しぶりで非常に疲れたので，けいおん！4巻を読み直して泣きたいと思います．
P.S.
けいおん！勉強会@PFIはいつやるんですかね？
他の人の感想
Permalink | コメント(0) | トラックバック(2) | 01:26
