btrfs領域管理一代記

Transcript

1. btrfs領域管理一代記 牛酪亭直太
2. Linuxファイルシステム戦国時代 • 台頭する新興FSたち ◦ 平成13(2001)年1月: ReiserFS, Linuxに入る ◦ 同6月: JFS ◦ 平成14(2001)年: XFS • そのころのFS: Ext3, XFS, ReiserFS ◦ Ext3はLinux古来の流れを組む由緒正しき FS ▪ ext1は, 文献上のみで知られ、実 (用的に存)在はしなかったと言われている ▪ ext3を刷新したext4の開発 ◦ XFSはSGIの流れを組む(Linuxでは)比較的新しいFS • ReiserFS ◦ 初めてジャーナリングを Linuxに持ちこんだ ◦ B+treeに様々なmetadataを保管
3. Btrfsの建国 • 平成18(2006)年: Reiser家「お家騒動」により, 開発中のReiser4は凋落 • Btrfs創設者: Chris Mason ◦ もともとSuSEでReiserFSの開発に関わる ◦ その後、OracleにてBtrfsを立ち上げ ◦ Fusion-IOを経て、現在はFacebook所属 • 平成19(2007)年, Btrfsの誕生 ◦ [ANNOUNCE] Btrfs: a copy on write, snapshotting FS ◦ B-trees, Shadowing, and Clones [Rodeh, ToS’07] による, CoW フレンドリーなB-tree
4. Btrfs七勇士と家臣団 • Btrfs七勇士 ◦ checksumによるデータ保護 ◦ snapshot ◦ subvolume ◦ 複数デバイスサポート ◦ 透過的圧縮 ◦ send/recvを使った効率的差分バックアップ ◦ dedupe • Btrfsを支える関数総勢1791個 • 今日のお題 find_free_extent() ◦ 指定されたサイズの空き領域を探索する関数
5. find_free_extent()奇々怪々 • 行数482行の大関数 ◦ その半分近くを占める 259行の大ループ • 8つのgoto label, 22のgoto文 ◦ 右図のような状態遷移 (単純な上下は省略) 大ループ
6. 通常のFSのマッピング 通常のFSはファイルアドレスと ディスク上のアドレスを直接マッピング
7. Btrfsのマッピング: extent空間 • 複数デバイスに対応するため, ディスクに直接マッピングしにくい
8. Btrfsのマッピング: extent空間 • 複数デバイスに対応するため, ディスクに直接マッピングしにくい • extent空間という「仮想領域」を 中間にはさむ • extent上のBlock Groupが, さらにディス クにマップされる
9. find_free_extent()の読解ポイント • free space cache treeを知る ◦ free spaceをメモリ上で管理する tree • クラスタを知る ◦ cacheから条件に合う領域だけを集めた tree • “loop”変数に惑わされない ◦ 4つのstageと考える ◦ stageごとにallocation戦略が変わる • アロケーションの階層をイメージする ◦ クラスタからのalloc ◦ BlockGroupからクラスタへのrefill ◦ extent空間から新しいBlockGroupのalloc ◦ 最後の手段: クラスタなしのalloc
10. free space cache tree: 連続領域(extent)ノード • free space cache tree ◦ 空き領域の位置とサイズを管理する赤黒木 ◦ 各BlockGroupで一つ、メモリ上に構築 ◦ 構築するにはIOが必要 • ノード ◦ キー 空き領域の開始アドレス (BGの先頭からのオフセット ) ◦ bytes 空き領域のサイズ • 一つの連続した空き領域(extent)に対して、一つのノード
11. free space cache tree: bitmap • 断片化した領域を保持するには、多くのノードが必要になる ◦ 一連続領域に一ノードの弊害 • ある程度断片化したところで、extentノードをbitmapノードに変換 • bitmapノードの開始位置は128MBにalignされる ◦ 結果的に、同じアドレスをキーとして "bitmapノード"と"extentノード"とが重複する ▪ (コードがめんどくなるんよ ) ◦ 128MB = 1つのbitmapでカバーする領域 ◦ BGが大きくても1GBなので、断片化しまくっても 8つのbitmapノードで覆うことができる
12. クラスタ • 各BGのcacheの, さらに上位のcache ◦ metadata と dataでそれぞれ1つ • cacheは, offsetをキーとするため, サイズを条件とした探索ができない ◦ 赤黒木なのに線形探索 ◦ 効率化のため, 一定の条件に合う領域を「クラスタ」に集めておく • クラスタは可能なかぎり、extentノードだけで作られる ◦ bitmapノードは断片化しているため , allocが成功しにくい • できる限り, このクラスタからallocを行う
13. クラスタとmount option • BtrfsのSSD最適化 ◦ 2つのmount option: SSD, SSD_SPREAD • mount optionによりクラスタ作成法が変わる ◦ SSD_SPREAD ▪ alloc_size + 2M の領域を見つけだす . それ未満の領域を全て無視 ◦ metadata ▪ alloc_size の領域を1つ確保 ▪ 最低成立量: SSD: 2MB, HDD 64K ◦ data: alloc_size の領域を1つ確保. 最低成立量なし
14. 秘技loop二刀流 • 2つの”loop” ◦ gotoラベルのloop ◦ 変数のloop • 2つの"loop"は独立している • goto loopは"見える"forループを回す ◦ continueのようなもの • loop変数は, "見えない"ループのカウンタ ◦ goto searchで”見える”forループの後から前に戻る時にインクリメント • ここからloop変数のことを”stage”と言いかえる ◦ stageごとに、alloc戦略が変わる
15. アロケーションの階級社会 1. CACHING_NOWAIT ◦ クラスタからalloc ◦ 適宜クラスタを作る ◦ cacheを待たない 2. CACHING_WAIT ◦ NOWAITと同じ ◦ cacheを待つ 3. ALLOC_CHUNK ◦ 新しいBGを作る ◦ あとはNOWAIT 4. NO_EMPTY_SIZE ◦ 最終手段 ◦ クラスタを使わない
16. 関数冒頭, そしてループに飛び越む • last_ptr = fetch_cluster_info(fs_info, space_info, &empty_cluster); ◦ last_ptrに「最後に使ったクラスタ」を読みこむ ◦ empty_clusterには、クラスタを作る時用にほしいクラスタサイズが入る • if (last_ptr->block_group) hint_byte = last_ptr->window_start; ◦ 最後に使っていたクラスタがあれば , 引数のalloc hintは無視! • goto have_block_group; ◦ Block Groupをlockしたら、一気に大ループのどまん中に飛び越む !!!
17. have_block_group: • このラベルの時点で、allocを試みるBlockGroupが決まっている • if (!block_group_cache_done(block_group)) cache_block_group(block_group, 0); ◦ cacheができていなければ、 cacheするスレッドを走らせる • btrfs_alloc_from_cluster(...) ◦ クラスタからのallocを試みる ◦ 必要な領域を取得できれば -> goto checks ◦ 取得できなければ, release_cluster へ
18. release_cluster:/refill_cluster • release_cluster: クラスタを解放するための場所 • btrfs_return_cluster_to_free_space(NULL, last_ptr); ◦ クラスタに確保していた空き領域情報をBlockGroupのcacheに返却 • refill_cluster: BGからクラスタに領域を確保する場所 • btrfs_find_space_cluster() ◦ クラスタを作り直す ◦ クラスタを作ったら ▪ btrfs_alloc_from_cluster()で、できたてのクラスタから alloc ◦ 作れなかった or やっぱりクラスタから allocできなかったら ▪ クラスタを解放(クラスタからallocできない時用) ▪ goto loop して、次のBlockGroupへ
19. checks: / loop: • checks: allocがうまくいった時にgoto ◦ 領域の確認や, メモリ上での空き容量情報を更新する • loop: allocがうまくいかなかった時に goto ◦ いくつか変数をresetし, BlockGroupを解放して, ループをまわり次の BlockGroupへ
20. ループの後 • allocする領域を見つけた / 全てのBGからallocをためし終わった • まだallocできてなければ、ここで次のstageを決める ◦ stage == CACHING_NOWAIT ▪ cacheをkickしたBGがあれば -> 次はCACHING_WAIT ▪ なければ -> ALLOC_CHUNK ◦ stage == ALLOC_CHUNK ▪ BlockGroup (=CHUNK)を新しく1つ作る ▪ 作れたら -> goto serachで、またループ (いま作ったBGからとれるはず) ▪ 作れなかった -> 次はNO_EMPTY_SIZE
21. NO_EMPTY_SIZEでのループ • 最終手段のalloc ◦ クラスタのサイズ下限を撤廃 : クラスタが前より成立しやすい ! ▪ とかなってんだけど、そもそも if (loop >= LOOP_NO_EMPTY_SIZE) goto unclustered_alloc しててクラスタ作んない • btrfs_find_space_for_alloc() ◦ 直接cacheからのalloc ◦ allocできたら -> checks へ ◦ allocできなかった, かつ、 まだcache完成してなかったら -> cacheを待ってもう一度 ◦ allocできなかった -> goto loopでつぎのBG
22. アロケーションの階級社会 (再掲) 1. CACHING_NOWAIT ◦ クラスタからalloc ◦ 適宜クラスタを作る ◦ cacheを待たない 2. CACHING_WAIT ◦ NOWAITと同じ ◦ cacheを待つ 3. ALLOC_CHUNK ◦ 新しいBGを作る ◦ あとはNOWAIT 4. NO_EMPTY_SIZE ◦ 最終手段 ◦ クラスタを使わない
23. 今日のまとめ • Ext*: 平家のようなFS • XFS: SeiwaGenjIのようなFS • ReiserFS: 織田信長のようなFS Linuxファイルシステムを天下統一するのは誰なのか アロケータを把握したいま, みなさんはもはやbtrfsの家臣も同然. btrfsを盛り立てていきましょう
24. 何度も同じループしすぎでは? • ぼくもそう思います • ループしてる間にほかの人が、領域解放した可能性はあるので・・・
25. ラベルとinvariant • search: “見える”ループを使って探索, stageの開始地点 • have_block_group: allocを試みるBlockGroupを決定した • release_cluster: クラスタからallocできなかった. クラスタを解除 • refill_cluster: BGからクラスタに領域を確保 • unclustered_alloc: クラスタを使わずBG全体からallocを試みる ◦ BGはfragmentedしており、クラスタをとれない • checks: 候補となる領域を見つけた. 要求を満たすかを確認 • loop: 次のBGに移行 • out: 関数の終わり