Receive-Side Scalingについての調査メモ

Kernel/VM Advent Calendar 4日目: Linuxのネットワークスタックのスケーラビリティについて - かーねる・う゛いえむにっきで書いたReceive-Side Scalingの記述が未だ理解が足りず不正確だと思ったので、調べ直してみてる所。

Multi-queueなNICってなに

RPS提案のメールにこんな事が書いてある:
This effectively emulates in software what a multi-queue NIC can provide, but is generic requiring no device support.
要約すると「multi-queue NICが提供している機能をソフトウェアエミュレートするのがRPS」
→じゃあmulti-queueなNICってどれで、どんな機能を提供してるんだろう?

それらしいNICを探してみる

Intel® PRO/1000 PT Server Adapter

Broadcom BCM5709C

Realtek RTL8111C
Supports Receive-Side Scaling (RSS)

どうも、Receive-Side Scalingと呼ばれているようだ。
Intelの書き方ではMicrosoftに関係がありそう。

Receive-Side Scalingって言葉はどこから出てきたの

Microsoft用語っぽい。
Microsoft Scalable Networking initiativeの一環で提案されたものらしい。

Scalable Networking Partners
BroadcomとかIntelとかサーバベンダとか

Microsoft Windows Scalable Networking Initiativeのpaper (2004/04)

冒頭の要約

ネットワークインタフェースのスピードが急激に上がってきていて、Windowsのネットワークスタックがボトルネックになっている。
Scalable Networking InitiativeはWindowsのネットワークスタックのスケーラビリティを向上させる為の取り組み。
10GbEのような高速なイーサネットを用いる環境では、3つの大きな問題が発生する。

  • ホストCPUがパケットを一つづつ処理する必要があって、これが大きなオーバヘッドとなる(CPUがボトルネックになる)。

もし、アプリケーションバッファがコピー完了している時にだけホストCPUが処理を行えば良いのであれば、このオーバヘッドを大きく削減出来る。

  • マルチコア環境においても、一つのNICの受信処理は一つのCPUでしか行えていない
  • CPUはネットワークバッファをアプリケーションバッファへコピーする責任があって、これが重い

この問題を以下の方法で解決する:

  • Receive Side Scaling: 複数のCPUで受信処理を行う為のパスを提供
  • Chimney Offload with no wire protocol changes: 既存プロトコルTCPIPSec)をハードウェアにオフロードする。ネットワークバッファ→アプリケーションバッファのコピーのオフロード、プロトコルスタックのフルオフロードからなると思われる。
  • Chimney Offload with wire protocol changes: フルオフロードに適した新しいAPIプロトコルを提供する。RemoteDMA。
Microsoft Windows Server 2003 Scalable Networking Pack

実際にInitiativeの成果が製品としてリリースされたのはこのWindows Server 2003 Scalable Network Packからで、以降のWindowsには統合されているらしい。

Scalable Networking Pack whitepaper (2006/05)
日本語なのでこっちの方がさくっと読めそう。書いてある事はInitiativeのpaperと大差ない?

他の資料

Scalable Networkingに関する資料へのリンク集:
Scalable Networking Pack Update is Available

Receive-Side Scalingに関する資料へのリンク集:
Networking Deployment Guide: Deploying High-speed Networking Features
この中の資料からRecive-Side Scalingの詳細について見ていく。

Receive-Side Scaling Enhancements in Windows Server 2008

これを読んでみる:
Windows Hardware Dev Center Archive - Windows 10 hardware dev

Introduction

Windows Server 2003 SP1以前は、一つのNICに対して同時に一つのDPCしか実行出来なかった(※WindowsのDPC≒Linuxのsoftirq)。
新しいWindows ServerでRSSを有効にすれば、ストリーム毎にインオーダな配信を維持しつつminiport driverのインスタンス毎に別々のCPUで複数のDPCを実行できる。
RSSは動的ロードバランス、セキュアハッシングメカニズム、パラレルな割り込み、パラレルなDPS実行もサポートする。

Packet Receive-Processing Limitations without RSS

割り込みがかかるとDPCがシステムプロセッサにキューされ、DPCが完了するまで追加のネットワーク割り込みは無効化される→LinuxのNAPIと同じっぽい
DPCの並列性の不足によってスケールしない
ひとつのCPUが全てのデバイス割り込みをハンドルしてるのが問題

Packet Receive-Processing with RSS

単一のCPUで処理される問題はRSSを実装する事で解決できた。
これは、受信処理を複数のプロセッサにインオーダなデータ配信を保ったままバランスさせる。
RSSは並列DPCを可能にする。
もしコンピュータとNICがサポートしていれば、RSSは並列割り込みをサポートする。

RSSが提供するベネフィット:

  • 並列な受信処理 単一のNICから受信したパケットが割り込みによって示された複数のCPUでDPCを並列に行える
  • インオーダなデータ配信の維持 受信したパケットの配信順序が保たれる
  • 動的ロードバランス システムへの負荷が偏っている場合、RSSはネットワーク処理の負荷バランスをプロセッサ間で調整出来る
  • キャッシュローカリティ あるコネクションに対するパケットは常に同じプロセッサにマップされるので、キャッシュローカリティを上げられる
  • Send-side scaling TCP/IP protocolがRSSハッシュ値NICに渡す事により、送信完了処理を同じCPUで行える。これで送信処理もスケール出来る
  • Toeplitz hashing デフォルトで生成されるRSSシグニチャはセキュアである
RSS Algorithm

従来の受信処理のシーケンスは以下の通り:

  1. パケットがNICに到着したら、パケットのデータはホストメモリにDMAで転送され、receive descriptorがreceive descriptor queueに転送される(これもDMA)。ホストに新しいデータが届いている事を伝えるために割り込みが生成される。ただし、そのタイミングはinterrupt moderation schemeに依存する。
  2. チップセットやCPUに依るが、割り込みはどれかひとつのCPUに届くか、或いは常に同じCPUに届く。
  3. もし追加のパケットがNICに届いたらデータとdescriptorはDMAされるが、割り込みは生成されない。
  4. ISRがCPUで実行され、NICの割り込みを無効化しminiport adapterのDPCをスケジュールする。DPCは大抵ISRが実行されたCPUで実行される、DPCを他のCPUで実行しろと明示的に指定されない限りは。
  5. DPCが実行され、receive descriptor queueが処理される。DPCはパケットのリストを作成してNDISインタフェースに渡すか各パケットをNDISインタフェースにsignalする(?)。どちらのケースにおいても、割り込みが禁止されている為、他のプロセッサはNICの割り込み処理を行う事が出来ない。
  6. プロトコルスタックがパケットを処理する。TCPなら内部ステートを更新し、TCP windowが許可していれば新しいデータを送り、可能ならばアプリケーションに受信完了したデータを渡す。
  7. 全てのreceive descriptorが処理されるか一定量の処理が終わったらDPCは割り込みを有効化して処理を終える。これによりNICは新しい割り込みを生成出来るようになり、他のCPUに割り込む事が出来るようになる。

RSSはstep 5から7の処理を次のアルゴリズムで並列化する:
複数のISRを特定のプロセッサで走らせ複数のDPCを並列にスケジュールする。
割り込みの禁止は行い、ひとつのDPCが実行されたあとに有効化される(どのDPC?最も最後に実行されたもの?)

説明したシーケンスは受信処理を並列化している。
しかし、もしもインオーダなデータ配信がなければ、パフォーマンスは下がると予想される。
TCPアクノリッジメントがインオーダな処理に強く最適化されている為)

RSSはインオーダなパケット配信をひとつのCPUがひとつのTCPコネクションを処理するようにする事で有効にしている。
これはNICにパケットヘッダを解析し、ハッシュ関数でパケットのシグニチャを計算する機能を要求している。
負荷が全CPUに均等になるように、indirection tableにハッシュ値を用いる。
Indirection tableは割り込みをかけ、DPCを実行するCPUを指しており、ホストのプロトコルスタックはこれをいつでも変更できる。
これを変更する事によってCPUに対する負荷のバランスを調整出来る。

Figure 1はRSSの処理シーケンスを図で表したもの。
右側から入ってきたパケットをハッシュ関数で処理し、32bitのハッシュ結果を得る。
これをハッシュマスクで6bitにマスクしてIndirection tableで使うindex値にする。
Indirection tableはindexからCPU番号を引く事が出来、lookup処理によりどのCPUで受信処理を行えばよいか判別する。

Indirection tableのサイズはCPU数よりも大きくないといけない。

RSS Setup

RSSを使うには、ドライバからRSS capabilitiesがNDISに渡されないといけない。
RSSをサポートするNICMSI-Xをサポートし、全CPUに対して割り込みを分散できる事が強く推奨されている。

ハッシュ関数
デフォルトで使われるハッシュ関数はToeplitz hash

ハッシュの種類

  • 4-tuple: src TCP port, src IPv4 address, dest TCP port, dest IPv4 address
  • 4-tuple: src TCP port, src IPv6 address, dest TCP port, dest IPv6 address
  • 2-tuple: src IPv4 address, dest IPv4 address
  • 2-tuple: src IPv6 address, dest IPv6 address
  • 2-tuple: src IPv6 address, dest IPv6 address, IPv6 extension headers

ハッシュビット
ハッシュビットはindirection tableに入れるindexに何ビット使えるかを表す。全てのNICは7bitをサポートしなくてはならない。ホストのプロトコルスタックは初期化時にビット数を決める事が出来る。ビット数でindirection tableのサイズが決まる。

indirection table
RSSに使うCPUの番号を引くためのテーブル

Secret hash key
ToeplizにはIPv6で40byte, IPv4で16byteのキーが必要

Selection of CPUs Eligible for RSS

HTウザイなの図

Selection of the Default RSS Hash Function

ハッシュのアルゴリズムとか

Mapping Packets to Processors

Figure 4はindirection tableの値を示している。
初期化からしばらくたって、プロセッサの負荷がアンバランスになり、ホストのプロトコルスタックがアンバランスである事を検知してバランスを取ろうと新しいindirection tableを計算しminiport driverのconfiguration OIDを通じて渡している。

更新されてしばらくのあいだはパケットが間違ったCPUで処理される可能性がある(キューに古いindirection tableに基づいたパケットがたまっている間)。

Packet Receive Processing with RSS

実装の話

RSS Implementation

NICがハードでハッシュ計算をサポートしていると様々な実装のオプションが考えられる。

RSS and MSI-X

最適なRSS実装はMSI-Xをサポートし、CPU数と同じ程度の数の受信キューを持つ。
そのようなNICでの受信パスは以下のようになる。

  1. 初期化時にはそれぞれのキューはそれぞれのCPUに関連付けられる
  2. パケットが受信されたらハッシュタイプからハッシュするフィールドを選び、ハッシュ値を計算し、ハッシュマスクを適用する。適用した結果をindex値としてindirect tableを引きどのqueueにパケットを置けばいいか判別
  3. パケットはDMAでホストメモリに転送され、receive descriptorがreceive descriptor queueに転送される(これもDMA)
  4. NICMSI-Xを用いてqueueに関連付けられたCPUに割り込む。割り込みタイミングはinterrupt moderation schemeに依存し、これはRSSに対応したaccoutがなされているべきである
  5. 追加のパケットが届いたら、データとdescriptorはDMAで転送される
  6. ISRが割り込まれたCPUで実行される。ISRは割り込みを禁止しDPCをスケジュールする
  7. DPCが実行され、receive descriptor queueにあるreceive descriptorを処理してパケットをNDIS interfaceに投げる

ハードウェアとドライバの開発者はadditional level of indirectionをハンドルしなければならないー TCP connection <-> Hardware Queue <-> CPU、Hardware QueueからCPUへのマッピングは1:1ではない。

Windows Server 2008では、RSS実装はCPUをRSSの為に割り当てるときにNICが持っているhardware queueの数を考慮しない。
これはNICがパケットの送信をhardware queue数よりも多くのCPUに依頼出来る事を意味する(で、合ってる?)
NICとドライバはこのシチュエーションをハンドル出来なければならない。

Example RSS NIC with MSI-X Capability

Figure 6は4つのhardware queueと16個のMSI-X table entryを持つNICが、4つのCPUがRSS用に割り当てられているシステムに接続されている図である。
ハードウェアは4つ以上のreceive queueを持つことが出来るが、このシステムは4つのCPUしかRSSに割り当てていないので、4つのqueueだけが使われる。
Figure 5はdriverからFigure 6のNICへ渡されるindirection table。
Figure 6の"Hash-To-Queue Table"はdriverから渡されたindirection tableと同じものである。

Figure 8はhardware queue数が2、RSS CPU数が4の場合である。
ここでは、システム管理者はCPU 0をアプリケーションに予約し、RSSに使うCPUをCPU 1以降に指定している。
Figure 8のNICはhardware queueを2つしか持たないにもかかわらず、hardware queueパケットを処理するCPUとして4つのCPUのいずれも使うことが出来る。

miniport driverは2つのhardware queueから4つのCPUへパケットを配送できるよう、MSI-XテーブルエントリのCPU affinityを変更しなければならない。
この実装方式はシステムのパフォーマンスに悪影響を及ぼす可能性がある為推奨されない。
NICが少ないhardware queueとMSI-X tableエントリしか持たず、それ以上の数のCPUをRSSに使う場合、miniport driverはMSI-X table entryのCPU affinityを定期的にアップデートする。
それぞれのMSI-X table entryアップデートはPCIレジスタ書き込みを必要とするが、これはCPU speedに比べて遅い。
結果、パフォーマンスの劣化を引き起こす。

より適切なソリューションは、RSS CPU数を制限することである。
NICドライバはRSS CPUのサブセットを選択する。 Figure 8はこれを実施しているところを示している。"Hash To Queue Table"はRSS indirection tableが用いているCPUのサブセットを用いている。

RSS Load-Balancing Implementation in Windows Server 2008

TCP/IP protocol driverはnetwork load balancingを実装している。
TCP/IP実装はindirection table updateをNDIS経由でNIC driverに送る事によってロードバランスをおこなっている。
TCP/IPは以下のような入力をロードバランスの決定に使っている:

  • 送受信IO per TCPコネクションのグループ
  • 送受信IO per CPU per TCPコネクションのグループ
  • 各CPUの負荷

TCP/IPプロトコルドライバは定期的に入力をチェックしてindirection tableをアップデートする。
TCP/IPプロトコルドライバでは2秒周期で負荷をチェックしている。
さらに、TCPコネクションのestablishmentが必要に応じて負荷のチェックとindirection tableのアップデートを行う。

RSS Configuration Parameters

使い方

RSS Limitations

per-connection basisなbalancingがサポートされるのはTCPのみである。
UDP, IPSec, IGMP, ICMPはsrc/destのIPのみでHashされる。
IP以外のプロトコルRSSが無効なときと同じ処理方法で処理される。