# FaRM: Fast Remote Memory > [!abstract] 概要(abstract の日本語訳) > 我々は、RDMAを利用してレイテンシとスループットの両方を最新のTCP/IPを使うメインメモリシステムに対して一桁改善する、新しいメインメモリ分散コンピューティングプラットフォームFaRMの設計と実装を述べる。FaRMはクラスタ内のマシンのメモリを共有アドレス空間として公開する。アプリケーションはトランザクションを使って、アドレス空間内のオブジェクトを位置透過的に確保・読み出し・書き込み・解放できる。我々は、この単純なプログラミングモデルがほとんどのアプリケーションコードにとって十分であると期待している。FaRMは必要な場合に性能を改善する2つの機構を提供する。RDMA上でのロックフリー読み出しと、単一マシンでの効率的なトランザクションを可能にするオブジェクトのコロケーションおよびfunction shippingのサポートである。FaRMは共有アドレス空間内のデータへの直接アクセスと高速メッセージングの両方にRDMAを使用し、最良のRDMA性能のために注意深くチューニングされている。我々はFaRMを使ってキーバリューストアとFacebookに似たグラフストアを構築した。両者とも良好な性能を発揮する。例えば、20台構成のクラスタは1秒あたり1億6700万回のキーバリュールックアップをレイテンシ31µsで実行できる。 ## 論文情報 - タイトル: *FaRM: Fast Remote Memory* - 著者: [[Aleksandar Dragojević]]・[[Dushyanth Narayanan]]・[[Orion Hodson]]・[[Miguel Castro]]([[Microsoft Research]]) - 会議: 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI '14)、2014年4月2日〜4日、シアトル - ISBN: 978-1-931971-09-6 - URL: https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-dragojevic.pdf - 会議ページ: https://www.usenix.org/conference/nsdi14/technical-sessions/presentation/dragojević - 原本: `.raw/papers/nsdi14-paper-dragojevic.pdf`(15ページ) ## 概要 FaRMは、クラスタ内の全マシンのメインメモリをRDMAでアクセス可能な単一の共有アドレス空間として公開する分散コンピューティングプラットフォームである。アプリケーションはACIDトランザクションでオブジェクトを確保・読み書き・解放でき、位置透過性を保ったまま分散データ構造を構築できる。RDMAの直接読み出しと高速メッセージングを組み合わせ、ロックフリー読み出しとオブジェクトのコロケーション+単一マシントランザクションという2つの高速化機構を提供する。この基盤の上にキーバリューストア(hopscotch hashingベース)とFacebook Taoに似たグラフストアを実装し、いずれもTCP/IPベースラインに対して一桁の性能改善を示した。 ## 問題設定 DRAM価格の低下により、100台規模のクラスタで数十テラバイトのメインメモリを保持できるようになり、ディスク・フラッシュのオーバーヘッドを回避できる可能性が生まれた。しかしTCP/IPベースのネットワーク通信がボトルネックになる。既存の最先端キーバリューストアは、単一マシン構成に比べてクライアント・サーバ構成でリクエストのバッチ処理を行っても7倍遅くなることが報告されている。 RDMAはカーネルをバイパスし複雑なプロトコルスタックのオーバーヘッドを回避することで低レイテンシ・高スループットのリモートメモリアクセスを実現するが、InfinibandはEthernetと非互換で高価だったため、データセンターでの普及が遅れていた。RoCE(RDMA over Converged Ethernet)がデータセンターブリッジング拡張とともに競争力のある価格でEthernet上のRDMAを可能にしたことが、FaRMの前提となっている。課題は、(1)RDMAの生の性能を実際に引き出すためのシステム・ドライバレベルの最適化、(2)共有アドレス空間上でACID特性を保ちながら実用的な性能を出すトランザクションモデルの設計、の2点に整理できる。 ## 提案手法 ### 通信プリミティブ FaRMはone-sided RDMA読み出しでデータに直接アクセスし、RDMA書き込みで高速メッセージングプリミティブを実装する。メッセージングは受信者側に置かれた循環バッファ(図1)を使う単方向チャネルで、送信者はRDMA書き込みでバッファの末尾(tail)に書き込み、受信者は先頭(head)位置をポーリングして新規メッセージを検知する。RDMA書き込みがアドレス増加順に実行される性質を利用し、メッセージの終端(トレーラ)が非ゼロになった時点で全体の受信を確認する。 ![[fig01-circular-buffer-messaging.png]] *図1(Figure 1): RDMAメッセージング用の循環バッファ。受信者側に置かれたバッファに送信者がRDMA書き込みで末尾(Tail)へ追記し、受信者は先頭(Head)をポーリングして新規メッセージを検知する。* チャネル数を1スレッド対1リモートマシンに絞ることでポーリングオーバーヘッドを抑え、78台規模でも無視できるレベルに留めている。20台のRoCEクラスタでの比較では、FaRMのメッセージングは16〜512バイトの典型的なリクエストサイズでTCP/IPの9〜11倍のリクエストレートを達成し、one-sided RDMA読み出しは256バイトまでのサイズでさらに2倍改善する(図2(Figure 2))。 ![[fig02-request-rate-rdma-vs-tcp.png]] *図2(Figure 2): ランダム読み出しのリクエストレート。RDMA(one-sided読み出し)・RDMAメッセージング・TCPの3方式を、転送バイト数を変えて比較する。* ### RDMA性能を引き出すための低レベル最適化 登録するメモリ量を増やすとRDMAの性能が大きく低下する問題を発見した。NICのページテーブルキャッシュが溢れ、PCIバス越しにページテーブルエントリをフェッチし続けるためである。これに対し、起動時に物理的に連続した2GB境界の大きなメモリ領域を確保するカーネルドライバ**PhyCo**を実装し、NICドライバを2GBページ対応に改修することで、ページテーブルエントリ数を50万超から1へと削減した。 ![[fig04-phyco-impact.png]] *図4(Figure 4): 物理的に連続した領域確保の効果。VirtualAllocでは16MB超の登録でリクエストレートが4分の1に低下するが、PhyCoでは100GB登録時も一定を保つ。* さらにクラスタサイズが大きくなるとキューペア(QP)データのキャッシュ溢れで性能が低下する問題があり、スレッド対リモートマシンで単一コネクションを共有する方式(2×m×t個のQP)へ削減し、加えてNUMAを意識したキューペア共有(q個のスレッドで共有)を導入してクラスタサイズごとに最適なqを選べるようにした。 ![[fig05-connection-multiplexing.png]] *図5(Figure 5): コネクション多重化の影響。小さいqは小規模クラスタで有利だが大規模クラスタではQPデータ量の増加により性能が劣化するため、クラスタサイズごとに最適なqが異なる。* 割り込みとブロッキングを使うとRDMAレイテンシが最大4倍に増加することが分かったため、FaRMはイベント駆動型プログラミングモデルを採用し、各マシンはスレッドをハードウェアスレッドにピン留めしてユーザーレベルでポーリングするイベントループを実行する。 ### アーキテクチャとプログラミングモデル FaRMマシンはメインメモリにデータを格納しアプリケーションスレッドも実行する。全マシンのメモリは共有アドレス空間として公開され、one-sided RDMA読み出しでアクセスできる。ローカルメモリアクセスはRDMAより最大23倍高速であるため、データと計算のコロケーションを可能にする設計を選んでいる。 FaRMのAPI(図6(Figure 6)。`txAlloc`・`txRead`・`txWrite`・`txFree`・`txCommit`などのトランザクション操作、`lockFreeStart`/`lockFreeRead`/`lockFreeEnd`のロックフリー操作、`msgSend`のメッセージ送信)は継続(continuation)ベースのイベント駆動モデルを提供する。トランザクションはstrictly serializableなACID特性を持ち、オブジェクトの確保時にヒント(既存オブジェクトのアドレス)を与えることでコロケーションを促せる。 ```c Tx* txCreate(); void txAlloc(Tx *t, int size, Addr a, Cont *c); void txFree(Tx *t, Addr a, Cont *c); void txRead(Tx *t, Addr a, int size, Cont *c); void txWrite(Tx *t, ObjBuf *old, ObjBuf *new); void txCommit(Tx *t, Cont *c); Lf* lockFreeStart(); void lockFreeRead(Lf* op, Addr a, int size, Cont *c); void lockFreeEnd(Lf *op); Incarnation objGetIncarnation(ObjBuf *o); void objIncrementIncarnation(ObjBuf *o); void msgRegisterHandler(MsgId i, Cont *c); void msgSend(Addr a, MsgId i, Msg *m, Cont *c); ``` *図6(Figure 6): FaRMのAPI。* ### 分散メモリ管理 共有アドレス空間は32ビットのリージョンIDと32ビットのオフセットからなるアドレスで表現される2GBの共有メモリリージョンの集合として構成される。リージョンIDから担当マシンへのマッピングには、one-hop分散ハッシュテーブルによるconsistent hashing(k=100個の仮想リング)を用い、リージョンのプライマリとレプリカはリング上の位置に続くr台のマシンに配置される。 ![[fig07-resolving-address.png]] *図7(Figure 7): アドレスの解決。リージョンID(32ビット)は位置(Position)とリングID(RingID)に分解され、対応するリング上でプライマリ・レプリカ1・レプリカ2に解決される。* メモリアロケータはスラブ・ブロック・リージョンの3階層で構成され、256種類のオブジェクトサイズクラス(64バイト〜1MB)を持ち平均フラグメンテーションは1.8%、最大3.6%である。 ### トランザクション FaRMは楽観的並行性制御と2相コミットでstrict serializabilityを実現する。コーディネータはprepareメッセージを全参加者(書き込み集合のプライマリ・レプリカ)へ送り、プライマリは変更対象オブジェクトをロックし、プライマリ・レプリカともにメッセージをログしてから応答する。全応答を受けた後、読み込み集合の版数を検証するvalidateメッセージをプライマリへ送り、成功すればレプリカ、続いてプライマリへcommitメッセージを送る。ログはSSD上に保持し、不揮発性RAMで循環メッセージバッファとログエントリのバッファリングを高速化する。 2相コミットの高コストに対処するため、FaRMは(1)関連オブジェクトを同一マシンにコロケーションしトランザクションをそのマシンへshipすることで実現する単一マシントランザクション、(2)ロックフリー読み出し、の2つの機構を提供する。単一マシントランザクションでは書き込み集合のロックと読み込み集合の検証がローカルで完結するため、prepare/validateメッセージが不要になる。 ### ロックフリー読み出し オブジェクトヘッダの先頭ワードと各キャッシュライン先頭にバージョン番号を格納し(図8)、キャッシュコヒーレントなDMAを利用して、単一のRDMA読み出しでトランザクションとstrictly serializableな読み出しを実現する。読み出し時にロックフィールドが0でありすべてのキャッシュラインバージョンが一致すれば読み出しは一貫している。一致しなければランダム化バックオフの後にRDMAを再試行する。 ![[fig08-versioning-lockfree-reads.png]] *図8(Figure 8): ロックフリー読み出しのためのバージョニング。ロックフィールドLが0であり、Vc1・Vc2がVobjの下位ビットと一致すれば読み出しは一貫している。インカーネーションIは読み出しと同時にオブジェクトが解放されたかどうかの検知に使う。* オブジェクトの解放によるダングリング参照を防ぐため、type stabilityとインカーネーション検査を用いる。128ビットのfat pointer(アドレス・サイズ・期待インカーネーションを含む)により、読み出したオブジェクトが解放されていないことを検証する。メモリ再利用には分散版epoch-basedアロケータを実装している。 ### ハッシュテーブル hopscotch hashingとchaining・associativityを組み合わせた新しいアルゴリズム**chained associative hopscotch hashing**を設計した。各バケットはH/2スロットを持つFaRMオブジェクトで、キーバリューペアはキーのバケットか次のバケットに格納される。ルックアップは単一のRDMA読み出しでキーのバケットbと次のバケットb+1の両方を読む。隣接バケット間の一貫性を保証するため、joint version(前方・後方の結合バージョン、図9(Figure 9))を各バケットに追加している。 H=8・90%占有率で平均1.04回のRDMA読み出しでルックアップでき、cuckoo hashingベースの手法(75%占有率で3.2回、インライン化時1.6回)より効率的である。値サイズを変えたスループットと空間利用率のトレードオフは図10(Figure 10)・図11(Figure 11)に示されており、H=6またはH=8が128バイトまでのオブジェクトで良いバランスを与える。 ![[fig10-hashtable-throughput-value-size.png]] *図10(Figure 10): ハッシュテーブルのスループット(値サイズ別)。Out of table(値をバケット外に格納)とH=2/4/6/8でのインライン化を比較する。*挿入・更新・削除はshipping transactionsとflat combiningに着想を得た結合により最適化し、スキューしたYCSBワークロードでスループットを4倍以上改善している。 ## 新規性 - one-sided RDMA読み出しとRDMAベースメッセージングの両方を組み合わせ、ワークロードの読み出し支配的な性質(先行研究[9, 11]の知見)を活かして低レイテンシ・高スループットを両立させた点。 - 登録メモリ量の増加によるRDMA性能劣化を、専用カーネルドライバPhyCoによる物理的に連続な2GBページ確保で解決し、100GB規模のメモリ登録でも性能を維持した点。 - hopscotch hashingにchainingとassociativityを組み合わせたchained associative hopscotch hashingにより、90%占有率でも平均1.04回のRDMA読み出しでルックアップを実現し、cuckoo hashingベースの先行研究より効率的にした点。 - コロケーションとfunction shippingにより分散トランザクションを単一マシントランザクションへ置き換え可能にし、2相コミットのコストを局所化した点。 - ロックフリー読み出しをトランザクションとstrictly serializableに保ちながら単一RDMAで実現するバージョニング機構(キャッシュラインごとのバージョン+incarnation)を設計した点。 ## 実験設定 - クラスタ: 隔離された20台構成。各マシンは40Gbps Mellanox ConnectX-3 RoCE NIC、Mellanox SX-1036スイッチに接続。Windows Server 2012 R2、2.4GHz Intel Xeon E5-2665を2ソケット(合計32ハードウェアスレッド)、240GB Intel 520 SSD、128GB DRAM(クラスタ全体で2.5TB)。28GBのプライベートメモリと100GBの共有メモリで構成。 - 比較対象: MemC3[16]のほとんどの最適化を取り込みTCP/IPで通信するベースラインキーバリューストア(chained associative hopscotch hashingを共通利用)。 - キーバリューストア実験: 16バイトキー・32バイト値、90%占有率、均一分布とYCSB(θ=0.99のZipf分布)。1マシンあたり1.2億キーバリューペアを事前ロード(制御実験では20台で13億ペア/マシン、合計1.8TB)。 - グラフストア実験: Facebook TaoをモデルにしたFaRM実装をLinkBenchのfullスケール(10億ノード・43.5億エッジ)、[11]のオペレーションミックスで評価。 ## 実験結果 - **RDMA vs TCP/IP(図2(Figure 2)・図3(Figure 3))**: FaRMのメッセージングはリクエストサイズ16〜512バイトでTCP/IPの9〜11倍のリクエストレート、ピーク負荷時のレイテンシは少なくとも145倍低い。one-sided RDMA読み出しは256バイトまででさらに2倍のレイテンシ改善。 - **PhyCoの効果(図4)**: VirtualAllocは16MB超の登録でリクエストレートが4分の1に低下するが、PhyCoは100GB登録でも一定の性能を維持。 - **コネクション多重化(図5)**: 最適なqはクラスタサイズに依存し、小規模ではq小(並列性重視)、大規模ではq大(QPデータ削減重視)が有利。 - **キーバリューストアのルックアップスケーラビリティ(図12(Figure 12))**: 20台構成でFaRMは1秒あたり1.46億回のルックアップをレイテンシ35µsで達成。TCP/IPベースラインより1桁高いスループット、2桁低いレイテンシ(ベースラインのピークレイテンシは8ms超)。YCSBスキュー分布では8台超でホットキーによるNIC過負荷が生じるが、それでも1億回/秒・レイテンシ51µsを達成。単一マシンではベースライン(専用チューニング済みロックフリー読み出し)が4000万回/秒、FaRM(汎用ロックフリー読み出し、余分なオブジェクトコピーあり)が2600万回/秒。 ![[fig12-kv-lookup-scalability.png]] *図12(Figure 12): キーバリューストアのルックアップスケーラビリティ。上段がスループット、下段がレイテンシ(対数)で、サーバ台数に対するFaRM(均一分布・YCSB)とTCP(通常・レイテンシ1ms設定)を比較する。* - **マルチゲットとの比較(図13(Figure 13))**: マルチゲットバッチはベースラインの性能を改善するが、FaRMはバッチサイズ24比で8倍、100比で3倍のスループット優位を保つ。バッチサイズ100・20台ではベースラインのレイテンシが25msに増加する。 - **更新を含むワークロード(図14(Figure 14)・図15(Figure 15))**: 5%更新(YCSB-B相当)でFaRMは非レプリケーションベースラインより1桁高いスループット、SSDへの2重レプリケーションログでも性能低下は30%程度。5%を超える更新率でレプリケーションのオーバーヘッドが顕在化し、SSDのI/O帯域がボトルネックになる。更新結合(update combining)最適化はスキューしたワークロードで約4倍のスループット改善、dual-mode lockingはロックフリー読み出しの再試行率削減により約25%の全体スループット改善をもたらす。 ![[fig15-kv-update-rate-tradeoff.png]] *図15(Figure 15): 更新率を変えたキーバリューストアの性能。(a)は更新率に対するスループット(YCSBと均一分布)、(b)はルックアップと更新のレイテンシ(均一分布)。NoRepは非レプリケーション、Memはメモリへのレプリケーション、SSDはSSDへのログを表す。* - **グラフストア(Tao)**: 20台クラスタでLinkBenchにより1秒あたり1.26億操作(マシンあたり630万操作)、平均レイテンシ41µsを達成。報告されているTaoの値に対し10倍のスループット、40〜50倍低いレイテンシ。ロックフリー読み出しを使う3つの操作型は平均1.02回のRDMA読み出しで完結する。 ## 考察 - 著者らは、ハードウェアの違い(独自クラスタ vs Facebookの本番環境)とワークロードの違い(LinkBenchによる合成生成 vs 実ワークロード)から、Taoとの直接比較には限界があるとしつつも、桁違いの改善は妥当な結論であるとしている。 - 関連研究との位置づけとして、PGAS抽象化を提供するライブラリ・言語(著者らが挙げる[4, 13, 14, 22, 47, 49, 50])はone-sided操作にRDMAを使うものもあるが、ロックフリーRDMA読み出しを持たずロック・バリア・メッセージで一貫性を保つ点、インタラクティブなオンラインサービス向けの永続性・耐障害性を欠く点が異なるとしている。Pilaf[37]は一方向のRDMA読み出しでルックアップを実装するが、64ビットCRCによる一貫性検出でありFaRMのバージョニング機構より一般性が低く、トランザクションに対するserializabilityも提供しないとしている。Sinfonia[3]はmini-transactionsで2相コミットに処理をピギーバックするが、FaRMはロックフリー読み出しと局所性最適化を組み合わせた一般的な分散トランザクションを提供する点で異なるとしている。 ## 強み / 弱点・課題 - 強み: RDMAの生の性能を引き出すための低レベル最適化(PhyCo、QP共有、イベント駆動モデル)とアプリケーションレベルの抽象化(共有アドレス空間・ACIDトランザクション・ロックフリー読み出し)の両方を一貫した設計として提示し、キーバリューストアとグラフストアという2つの異なるアクセスパターンで性能を実証している点。 - 弱点・課題(本文に明記された限界): 現行NICがRDMAのバッチングをサポートしないためFaRMではマルチゲットインタフェースを未実装(RDMAベースのメッセージングで実装可能だが未着手と明記)。障害からの回復(failure recovery)の詳細な記述・評価は本論文の範囲外。グラフストア評価はFacebook本番のハードウェア・実ワークロードとは異なる環境・LinkBenchによる合成負荷での測定であり、著者ら自身が直接比較の難しさに言及している。コネクション多重化の最適値qがクラスタサイズごとに事前実験で選択する必要があり、動的な解決(Dynamically Connected Transport)は将来課題として述べられている。