CubeFSの論文を読んだ

背景

現代のコンテナが一般的となったシステムでは、計算が実際に行われるノードとストレージの結合を上手く抽象化してやる必要がある。密結合な状態ではコンテナの動的なスケジューリングは難しい^[1]。ストレージシステムをワークロードごとに複数抱えるのはコスト（金銭的なものに限らず、運用コストも含むと思う）の問題であまりやりたくない。大規模なファイルを扱うならHDFSがあるし、小さなファイルに対してはHaystackがある。ただどちらのワークロードにも対応したファイルシステムというのは少ない。それでもいくつかの先行研究はあるのだが、それらは大抵one-size-fits-allなアプローチをとる（単純に対応出来るファイルサイズの幅を持たせているだけ、という意味だと思う）。それだとレプリケーションの最適化がしづらいので問題である。

加えて、ストレージシステムにはメタデータサービスが必要だがシングルノードのメタデータサーバはハードウェア限界からボトルネックが生まれる^[2]。かと言って単純に分割すればいいというわけでもなく、メタデータのリバランシングが行われると大きなR/W性能の低下が生じる。（単純なConsistent hashingとかがそうだ。ノード数に対するスケーラビリティとノード増減に対するElastic性はまた別に話だということの好例だと思う）

そしてPOSIXの厳格なインターフェースは性能向上を図る上でとても厄介だ。大抵の分散ファイルシステムは一貫性を弱めることで解決しているが、それでもある程度のatomicityは保証する必要があるし、それは性能についての制限を生む。

これらの問題に対処するために作られたCubeFSは以下の特徴を持つ

• 汎用高性能ストレージ
  • Linuxのpunch holeインターフェースの活用がキモである
• シナリオ別のレプリケーション
  • appendとoverwriteの2つのレプリケーション戦略の使い分け
• 使用量を考慮したメタデータの配置
  • メタデータのリバランシングを回避する
  • MooseFSも同様のアプローチを取っている
• POSIXマンティクスの緩和と原子性の保証
  • 厳格なPOSIXせマンティクスは性能を稼げないので、注意深く弱めた
  • （私見）これはみんなやってること

アーキテクチャ

Metadata subsystem、Data subsystem、Resource managerの3つのコンポーネントからなる。Metadata、Dataはそれぞれノード内でPartitionに分割される。CubeFSの重要なコンセプトにVolumeというものがあり、　前述のPartitionは1つのVolumeに属する（1つのVolumeは複数のPartitionから構成されうる）。

Volumeはクライアントから見た場合は1つのファイルシステムと同じように見えて、マウント可能である。

Resource managerはシステム自体の管理を行うノードでNodeの追加や削除などのメタ的な操作を処理し、ノードのリソースを監視する。このリソースマネージャーはRaftで一貫性を保持し、データはローカルのRocksDBで永続化される（ただし基本的にはinmemoryを指向している）。

メタデータサーバ

inodeとdentryを扱うBTree、free listなどをインメモリに持つ構造。レプリケーションはMultiRaftを使い、ローカルディスクにログを書いてFailure recovoeryを行う。メタデータ操作中のエラーはdentryに属さないinodeを作り出すが、これの解決は困難であるのでクライアントがretryを行うことで発生率を下げる。

データサーバ

複数のData partitionを持つ。Data partionはextent storeを持ち、またidとreplicaへのアドレスを持つ。高速化のためにCRCのchecksumのキャッシュをインメモリに持っている。

データサーバはある境界値t(デフォルトだと128 KB)より小さいものをSmall file、大きいものをLarge fileとして別々に扱う。

Large fileは単一または複数のextentを排他的に使う。一つのファイルを構成するextentは複数のデータパーティションに属しうるので、データサーバも当然異なりうる。

Small fileはextentを共有する。extentとオフセットの情報はメタデータサーバに記録され、fallocateで領域を確保することで細かいストレージ管理をLinuxに委任している。

シナリオ別のレプリケーション

Sequential Writeはprimary-backupレプリケーション、ランダムアクセスはMultiRaftベースのoverwriteレプリケーションを行う（メタデータもこのoverwriteレプリケーションを行う）。

primary-backupレプリケーションで上書きを行うとその度に新しいextentが発生し、かつそのextentは元のextentとリンクさせる必要がある。これは容易に断片化を招くしその管理にコストがかかるので適切ではない。

一方でoverwriteレプリケーションはWrite ampiliationを発生させるが、大半がSequentialになるようなHPCやmicroserviceでよくあるシナリオではこれは大きな問題ではない。

Failure recovery

まずはprimary-backupレプリケーションでextentを用意し、次にMultiRaftでそのextentをoverwriteして復元を行う。

またデータパーティションは古いデータが残っていることを許容する。Raftベースでのファイルシステムであるため、クライアントに返されるデータは完全にコミットされたデータだけとなる。データが古いかどうかはoffsetの大小を見ればよく、これはメタデータサーバで管理されている。（Read after Write annormalyとかどうなんでしょうね？）

リソースマネージャ

シングルノードではなくマルチノードでメタデータサービスを構築する場合の手法として、hashingやsubtree partitioningなどがあるが、これらは新規のノード追加などで再分散が必要となる。これは高速な水平スケーリングが行われる現代のコンテナ環境においては頭痛の元となる。

lazyhybridやdynamic partitioningといった手法による対処もあるが、これはエンジニアリングコストがかかりメンテナンス性に悪影響を及ぼす。

使用率ベースの分散は単純な方法でこれを解決する。メタデータ、データの両方のパーティションを最も使用率が低いノードに割り当てるだけである。この方法は新規にノードが追加されてもそのノードが優先的に使用されるだけでデータのrebalancingは走らない。（冗長性確保のためのノード分散があるので、実際はもう少し複雑だと思う）

また、メタデータについてはテーブルの分割が必要になる場合がある（inodeかdentryが上限に達した場合）その場合は現在までに使われているinodeの最大値 + Δを基準に分割を行う。（ここからもわかる通り、CubeFSは二分木的な分割手法ではなく最大値に達した場合に新しくアロケーションを行う戦略を全面的に採用している。これはデータ量に対する柔軟性には欠けるが、永続的なストレージの場合は順次使用量が増すようなワークロードとなるし、現実的にハードウェアの性能には上限があるので十分に妥当だと思う）

また何らかの障害でメタデータパーティションが利用不能となった場合は残りのレプリケはreadonlyに設定され、新しいパーティションへの移行が手動で（手動で？）行われる。（ノード障害への対応がちょっと面倒になりそうだし、停電からの復旧作業とかが大変そうだ。これは要検証）

クライアント

FUSEで提供され、データそれ自体を除く多くの情報をキャッシュする。

最適化

• heatbeatの最小化
  • これは所謂MultiRaftそのもの
• 非永続的なコネクション
  • 大量のコネクションが保持され続けるのはリソースの無駄

メタデータ操作

多くのPOSIXに準拠したファイルシステムは空間的局所性のために同じノードにメタデータとデータを置くが、CubeFSの配置戦略では別々のノードに配置されうるしその場合は分散トランザクションが必要となる。これはパフォーマンスに大きな影響を与える。

そこでトレードオフとして、dentryが 常に 少なくとも1つのinodeに結び付けられている場合に原子性の要件を緩和する。この手法の欠点はdentryに結びつけられないorphanなinodeが発生する可能性があることだ。orphan inodeのGCは困難であるので、なるべく発生しないように注意深く設計を行い、かつfsckのようなツールも提供している。

Create

Resource managerがメタデータパーティションを割り当てるので、そこでinodeをアロケートし、成功した場合にdentryを作成し割り当てる。dentryの作成に失敗した場合はunlinkリクエストを送り、Orphanなinodeのリストへと作成したinodeを追加する。このリストはクライアントからのevictリクエストによってGCされる。

Link

inodeでnlinkをインクリメントしてからdentryを作成する。失敗すればnlinkを巻き戻す

Unlink

dentryを削除し、inodeのnlinkをデクリメントする。デクリメント後のnlinkが0ならOrphan listに追加する。dentryの削除失敗やデクリメント失敗はそのまま失敗として終了する。

Sequential Write

Sequential writeでは逐次的に固定サイズのパケットをリーダーへ送り続ける。リーダーのアドレスは前述の通りキャッシュされているのでいきなり送信することが可能である。リーダーからcommit完了の通知を受けるとローカルのキャッシュを即座に更新し、fsyncが呼ばれるか、または一定の周期でメタデータサービスとの同期を行う。このデータ操作はRaftではなく一般的なLeader-Followerレプリケーションである。Raftを使わない理由は追加でログを書くのを避けてWrite amplificationの回避するため。

Random Write

Sequential Writeとの差分はレプリケーションがRaftで行われること、メタデータの更新が不要なことだ。

削除

メタデータサービスからの削除は既に述べたとおり。データサービスからの削除は非同期で実行される。

読みとり

読み取りは Raftの リーダーノードからのみ行われる（Primary-backupレプリケーションのリーダーはRaftのリーダーとは異なる場合がある）この時のリクエストはクライアント側のキャッシュを元に構築することで高速化を実現している。

Centralization v.s. Decentralization

Centralizationアプローチは単一のサーバーがボトルネックとなりやすい反面、実装を単純にすることが可能である。

CubeFSは全体としてはCentralizationアプローチを採用しているが、メタデータ、データのサービスは分散されている。Resource managerはクラスタリングはされているが単純なRaftなのでスケールしない。しかしキャッシュを十分に活用することにより、ボトルネックとはなり得ないことはCubeFSのチームの実験によって明らかになっている。

メタデータとデータを切り離すかどうか

CubeFSはメタデータとデータを切り離している。これは一貫性保持をより困難にするが、メタデータをinmemoryに保持した上でmemory intensiveなサーバとDisk intensiveなサーバで別々に特化させることでコストとパフォーマンスを向上させることが可能である。また、これに加えてデプロイの柔軟性を確保することも可能となる。

(HPC向けの高パフォーマンスファイルシステムもメタデータとデータを分散させる構成を取るものが多い)

一貫性モデル

低レイヤのストレージ層はprimary-backupとRaftの二種類のレプリケーションプロトコルを用いて強い一貫性を提供する。一方でファイルシステム層それ自体の保証する一貫性は弱いが、多くのワークロードにおいてこれは問題にならない。