memcached 互換サーバーの自作

実装の再利用性

以前から手軽に memcached プロトコルに則った挙動ができるサーバーを簡単に実装できたらいいなと思うことが何度かあったため、特に memcached プロトコルのパーサーと応答生成部分がなるべく再利用しやすいように配慮しました。

主な配慮の一つは、CPU、OS、固有のライブラリやコンパイラ機能等に極力依存しないようにすることです。また、なるべく多くのコンパイラでコンパイルが可能なように C89 と C++98 という C 言語の標準に準拠させます。

もう一点は、再利用性の高い memcached プロトコルパーサーとキー・バリュー操作の間のインターフェースを定義することですが、こちらはインターフェースが複雑にならず、かつ様々なキー・バリュー操作の実装に対応できるようにすることが中々難しく、特に、当初はキー・バリュー操作機能が memcached 固有のキー・バリューペアのフラグや有効期限についての情報を持つ必要がないようにしたかったのですが、ロックを取らない楽観的な排他制御を適用したい場合に、どのタイミングでバージョンを判断する変数を読み取るか、どのタイミングで読み取ったバージョンと最新のバージョンの値を比較するか、それらが異なった場合にどこからリトライするのか、というような点について、キーバリュー操作の実装に依存しない一般的なプロトコルパーサー側からのキー・バリュー操作に関連した機能の呼び出しタイミングとループの操作を見出すことが難しく、結局は、キー・バリュー操作側にも memcached 固有の情報を持たせることにしました。

この妥協のおかげで、ある程度色々なキー・バリュー操作機能の実装と組み合わせることができるようになっていると思います。

一方で、この妥協の欠点は、仮に新しくハッシュテーブルを開発した人がこのプロトコルパーサー実装を使って memcached 互換サーバーを実装しようとすると、その人は統合作業の中で memcached 固有の情報を操作する実装をする必要があるということです。特に、ms (meta set) や mg (meta get) のようなメタプロトコルのコマンドは挙動が若干複雑なので、統合作業に際してこれらの挙動を認識する必要があるというのは面倒な点です。

応答の挙動をなるべく公式の memcached 実装に近づける

プロトコルパーサーは memcached のテキストプロトコル、メタプロトコル、バイナリプロトコルに対応する、また、なるべく公式の実装と同じエラーメッセージが返されるようにするようにします。

このために、エラーを含むリクエストを公式の memcached と自作 memcached 互換サーバーの両方に送って、同じ結果が返されるかを確認するテストプログラムを用意しました。

利用する CPU コアの増加とともに性能が向上するようにする

利用する CPU コアの増加にあわせて性能を向上できるように、キー・バリューペアを保持するハッシュテーブルへのアクセスの排他制御方法を工夫します。

具体的には、あるスレッドがロックを獲得した後で、そのロックが解放される前に、別のスレッドが同じロックを獲得しようとすると、そのスレッドはロックが解放されるまで待機する必要があり、この待機時間の蓄積が単位時間あたりに処理可能なリクエスト数の低下につながります。

このため、ハッシュテーブル実装において、キー・バリューペアの追加また更新は CPU の compare and swap 機能を元に実装し、読み書き共にロックの獲得が不要になるようにしました。

また、キャッシュの追い出しポリシーも CPU 間の同期が少なくて済むように配慮します。Least Recently Used (LRU) のようなポリシーの実装は CPU コア間での同期が多くなりやすいため採用を見送りました。少し調べてみて、ランダムな追い出しはキャッシュヒット率の観点からは最適ではないものの、必ずしも悪いアルゴリズムではないようだったので、こちらを採用しました。

実験環境

二台の同じ以下の設定のマシンを利用します。

• CPU: 2 x 16-core Intel Xeon Gold 6326 CPU @ 2.90GHz (合計 32 コア) Hyper-Threading は無効
• NIC: Mellanox ConnectX-5 100 Gbps NIC （マシン間はこの NIC へケーブルを直繋ぎして接続）
• DRAM: DDR4-3200 128 GB
• OS: Linux 6.8

memcached 用ワークロード

自作 TCP/IP スタックを利用する memcached サーバー向けクライアントを使用して以下のワークロードを実行します。

• キー・バリューペア総数：1000 件
• キーのサイズ：８バイト
• バリューのサイズ：８バイト
• リクエストの分布：一様にランダム
• set と get の割合：get 100%（1000 件のキー・バリューペアは計測開始時にサーバー側に全てロードされている）
• プロトコル：テキストプロトコル

キー・バリュー操作の負荷が特に小さい場合の性能を見るためにキー・バリューペアの総数を 1000 件という少ない件数に設定しています。

サーバーは自作 TCP/IP スタックを利用する自作 memcached 互換サーバーと、Linux カーネルの TCP/IP スタックを利用する公式の memcached バージョン 1.6.39 の２通りです。

TCP メッセージ往復ワークロード

また、memcached の応答についての処理のうち「memcached プロトコルに則ったメッセージのパースと応答の生成」「キー・バリュー操作」を含まない「メッセージの送受信」だけの場合の性能の目安を得るために、サーバーとクライアント間で 16 バイトのメッセージを往復させた場合のスループットも計測します。

この場合のベンチマークプログラムはサーバーとクライアント共にこちらの実装を利用します。また、Linux カーネルの TCP/IP スタックを利用する場合のサーバーはこのリンクの please click here to show the code of the program タブを開いた先のものを利用します。クライアントは常に自作 TCP/IP スタックを利用します。

memcached と TCP メッセージ往復の両方の計測に共通する設定

以下は memcached についての計測と、TCP でメッセージを往復させる場合の両方に共通する設定です。

• ベンチマーククライアントは常に 32 CPU コアを利用
• サーバー側は CPU コア数を１から 32 まで増加させる
• 並列 TCP 接続数は、サーバー側１CPU コアが 32 並列 TCP 接続を処理するようベンチマーククライアント側で調整

計測結果

以下のテーブルに１秒間に往復できたメッセージの数を記載しています。注意点として、Linux カーネルの TCP/IP スタックと自作 TCP/IP スタックの性能、公式の memcached サーバーと自作 memcached 互換サーバーの性能を比較することは公平ではないため、目安としてご覧ください。

自作の memcached 互換サーバーの性能は自作 TCP/IP スタック実装の性能を反映したものになっているように見えます。また、ある程度 CPU コアの増加にあわせて性能が上がる様子を見ることができました。

他のワークロード

今度はキー・バリューペア数を増やして、リクエストの分布も zipf 分布の近似に変更、また、リクエスト全体のうち 10% は set で上書きをするようにしてみました。

• キー・バリューペア総数：1,000,000 件
• キーのサイズ：８バイト
• バリューのサイズ：８バイト
• リクエストの分布：zipf 分布の近似
• set と get の割合：set 10% get 90%（1000000 件のキー・バリューペアは計測開始時にサーバー側に全てロードされている）
• プロトコル：テキストプロトコル

１秒間にサーバーとクライアントの間で往復できたメッセージ数は以下の通りです。

先ほどの計測結果と比べて、数値の低下が見られます。これは、キー・バリューペアの総数が増えてアクセスが発生し得るメモリ領域の範囲が拡大したことによる CPU キャッシュ効率の低下と、一部 set を行うことによる負荷の増加が要因と予想しています。