memcached - 分散メモリオブジェクトキャッシングシステム

memcachedのシンプルなインメモリのキー/値データ構造は、学術的著作の一般的な対象となっています。何百もの論文がバニラmemcachedを変更または比較しています。

ここでは、memcachedに対して大幅なパフォーマンスとメモリ効率の変更を加えた初期の論文の1つを分析します。その論文が実際の業界にどのように適用されたのか、また最初の公開時にそれによって何をもたらしたのかに焦点を当てます。

論文の背景

MemC3論文は、2013年4月に発表されたと述べています。珍しくも、その論文はテストされたmemcachedの特定のバージョン、1.4.13も引用しています。そのバージョンは2012年2月2日にリリースされました。

Googleの引用検索では、300以上の結果が、特許と論文に分けられて表示されます。2019年と2020年のような最近の出版物がこの論文を引用していますが、ほとんどは類似のシステムや実験の例としてリストされています。これはmemcachedの初期のマルチスレッド最適化論文の1つであったため、多くの作品で頻繁に比較されています。

主な主張

MemC3の要旨では、オリジナルのmemcachedにアルゴリズムとエンジニアリングの改善を加え、小規模オブジェクトのメモリを30％削減し、ネットワークスループットを3倍にしたと主張しています。新しいクックーハッシュテーブルと、memcachedの倍連結LRUを置き換えるCLOCKアルゴリズムのバージョンを使用してこれを達成します。したがって、2つの個別な主要主張があります。

単一の同時書き込みを伴う同時読み取りを許可するコンパクトなハッシュテーブル。チェーンされたハッシュテーブルよりもメモリオーバーヘッドが少なく、スレッドのスケーラビリティを向上させます。
LRUロックと16バイトのLRUポインターを1ビットに置き換えるCLOCKアルゴリズムを使用します。ハッシュテーブルの原子性と組み合わせることで、オブジェクトごとに16ビットのリファレンスカウントも削除されます。

彼らは例として、機能するシステムを提示しています。

コードを利用できますか？

はい！コードはオンラインで入手できます。1.4.13に基づいていますが、gitのクローンではなくtarballから変更されています。ほとんどの論文では、比較対象のソフトウェアのどのバージョンを使用するか、またはどの引数から開始するかを指定せず、ましてや動作するソースコードを提供しません。

ソフトウェアを構築してテストすることができました。スタートアップの問題を修正するために、単一のpthread CPUの親和性ラインにコメントする必要がありました。パフォーマンスのテストをしなかったので、これには問題ありません。

主張の検証

簡単に言うと、クックーハッシュとCLOCKの交換は рекла通りに機能しているようです。一般的にメモリ効率が高く、グローバルロックを回避します。

ここでは、ハッシュアルゴリズムの詳細は説明しません。プロービングタイプのハッシュテーブルとメモリと速度のトレードオフについて掘り下げる多くの投稿があります。

memcachedの1.4.13バージョンでは、オブジェクトがハッシュテーブルからフェッチまたは削除されている間、グローバルロックが保持されます。その後、ミューテックスロックのバケットを使用して、フェッチまたは変更されている個々のオブジェクトをロックします。

MemC3では、ロックが削除されます。代わりに、さまざまな原子操作を使用してオブジェクトのフェッチと変更が行われます。これにより、複数の同時読み取りがハッシュテーブルに対して許可されますが、memcachedでは許可されませんでした。CLOCKアルゴリズムがオブジェクトを追い出すときの整合性を確保するために特に注意が払われています。

引用

Our cache integrates cache eviction with our optimistic
locking scheme for cuckoo hashing. When Evict selects a victim key
x by CLOCK, it first increases key x’s
version counter to inform other threads currently reading
x to retry; it then deletes x from the hash table to make
x unreachable for later readers, including those retries;
and finally it increases key x’s version counter again to
complete the change for x. Note that Evict and the hash
table Insert are both serialized (using locks) so when
updating the counters they can not affect each other.

論文の基本的な前提はチェックアウトされます。残念ながら、コードをさらに詳しく調べると、「どのコストで？」が不適切に利用されたことがわかります。簡単なレビューで、次の機能が欠けていることが示されています。

CAS機能（オブジェクトの更新はバージョン番号が一致する場合）が壊れている/コメントアウトされています。
「削除」コマンドが壊れています。オブジェクトをハッシュテーブルから削除しますが、スラブアロケータに戻すのではなく、メモリをリークします。
INCR/DECRコマンドはコメントアウトされています。
スラブの再バランス機能が完全に削除されました。
決定的なもの: MemC3は間違った、または破損したデータを戻す可能性があります。

学術発表のタイムラインを考慮すると、すべての機能を有効にするには時間的に余裕がなかった可能性があることに注意することが重要です。削除されたこれらの機能がパフォーマンスに影響を与えることについて言及されていないのは誠実ではないと考えています。少なくとも、修復のためのアイデアまたは計画を含めるべきでした。

システム置換におけるメモリ効率の主張に対する最大のハードルは、スラブの再調整の省略と、論文内でのそれに関する言及の欠如です。

Memcachedはオブジェクトデータにスラブアロケーターを使用します。これは、使用可能なメモリが1メガバイトのページに分割され、その後、同様にサイズのオブジェクトにスライスされることを意味します。つまり、スラブクラス1には最大90バイトのオブジェクトが含まれる可能性があり、スラブクラス2には90〜120バイトのオブジェクトが含まれる可能性があります。これにより、malloc/free実装によるメモリフラグメンテーションが緩和され、memcachedは新しいオブジェクトを1つ追加するときに1つのオブジェクトのみを排除する必要があるようになります。これらのトレードオフにより、長い稼働時間を超えた信頼性の高いパフォーマンスが実現します。

スラブ再調整アルゴリズムは、これらの1メガバイトページをスラブクラス間で移動できます。オブジェクトのサイズは時間とともに変化する可能性があります。時間とともに徐々に大きくなったり小さくなったりする場合があります。したがって、重要なスラブクラスにメモリがほとんどないため、キャッシュサイズが実質的に小さくなることが考えられます。

大きな失望は、実際のワークロードではMemC3が間違ったデータを頻繁に返すということです。「delete」コマンドが機能した場合、それは完全に間違ったキーを返すでしょう。

以下のスクリプトはエラーを再現し、その理由を説明します。

#!/usr/bin/perl
use warnings;
use strict;

use IO::Socket::INET;

my $addr = "127.0.0.1:11211";
my $sock = IO::Socket::INET->new(PeerAddr => $addr,
                                 Timeout  => 3);
my $key = 'b';
# 200 kilobyte objects.
my $size = 1024 * 200;
# data is '1' repeated.
my $data = '1' x $size;

# Set the one key.
print $sock "set $key 0 0 $size\r\n$data\r\n";
rescheck($sock, "STORED\r\n");

# Generate a huge multiget request for the same key.
my $numkeys = 5000;
my @keys = ();
for (1 .. $numkeys) {
    push(@keys, 'b');
}
my $keystring = join(' ', @keys);
chop($keystring);
print $sock "get ", $keystring, "\r\n";

# don't look at the response yet, but give the server a second
# to wake up and process the request.
sleep 2;

# start another socket
my $sock2 = IO::Socket::INET->new(PeerAddr => $addr,
                                  Timeout  => 3);

# If we could delete 'b' now, we could replace it with 'a' and return an
# entirely different key. However memc3's delete command leaks memory, so we
# demonstrate by replacing the existing key with new data instead.

my $data2 = '2' x $size;
# Re-set the key a couple times to swap the original object back out of the slab
# allocator. Probably only need to do this twice.
for (1 .. 5) {
    print $sock2 "set $key 0 0 $size\r\n$data2\r\n";
    rescheck($sock2, "STORED\r\n");
}

# finally, fetch responses and parse them from original socket.
# Ensure we're getting the original data back.
for (1 .. $numkeys) {
    get_is($sock, "$data\r\n");
}

print "\nDone setting\n";

sub get_is {
    my $sock = shift;
    my $val = shift;
    my $line = scalar <$sock>;
    if ($line =~ /^VALUE/) {
        my $rval = scalar <$sock>;
        die "invalid response: $rval (expect: $val)" unless $rval eq $val;
    } elsif ($line =~ /^END/) {
        print "REQUEST END\n";
    }
}

sub rescheck {
    my $sock = shift;
    my $val = shift;
    my $res = scalar <$sock>;
    die "invalid response: $res (expect: $val)" unless $res eq $val;
}

ここでは、サーバーが大きな要求を処理する場合に何が起こるかを示しますが、すべてのデータを一度にソケットに収めることはできません。ソケットが書き込み可能になるのを待ちます。このスクリプトでは、キー「b」のデータは、読み取り途中で「1」から「2」に変更されます! これは、一般的なストレージシステムにとって致命的な状態です。

余談: なぜ参照カウントを行うのか

Memcachedオブジェクトは「書き込み時にコピー」です。つまり、同じキーに新しい値を設定した場合、すべてのインフライトクライアントがネットワークへの書き込みを完了するまで、古いメモリは残ります。その後、参照は0になり、オブジェクトメモリは解放されます。

MemC3は、オブジェクトのデータ構造を調べている間のみオブジェクト参照を重要として扱います。この場合、バージョン番号を使用してロックフリーアルゴリズムを使用し、競合が発生した場合は繰り返し再試行します。これは、実際にはデータをソケットに書き込むことには及びません。

これは、memcachedのネットワーク処理がオブジェクトデータに対して「ゼロコピー」であるためです。オブジェクトデータをバッファーにコピーしてからクライアントに書き戻すのではなく、スキャターギャザーシスコールを使用してオブジェクトデータを回避します。オブジェクトのサイズが大きくなるとネットの性能が向上し、多数のクライアント接続に必要なメモリの量が削減されます。オブジェクトが非常に小さい場合、このコピー段階では目立ったオーバーヘッドは発生しません。memcachedの実際の運用展開は、小さなオブジェクトのみで構成されることはほとんどありません。

何らかの理由でクライアントがソケットへのデータ書き込みを完了できない場合、オブジェクトの元のメモリは参照カウントなしでシステムによって再利用され、間違ったデータがクライアントに送信される可能性があります。

MemC3は、すべてのオブジェクトデータを最初にバッファーにコピーすることでこれを回避できますが、それには同じ再試行ルーチンを実行する必要があります。

オブジェクトを取得する
バッファーにコピーする
オブジェクトが常に有効かどうかをアトミックにテストする?
はいの場合、続行
駄目な場合は、オブジェクトを再度取得して再試行

頻繁に更新されるオブジェクトに病的な低速につながる可能性があります。

この問題の根本原因は、オブジェクトが参照カウントされる理由に対するMemC3論文の誤解であると考えられます。論文では、参照が、現在アクセスされているオブジェクトを退去しないようにするために使用されると述べられています。これは全体像ではありません。参照されているオブジェクトのメモリはすぐに再利用できないため、古いコードでは退去を避けています。これは、インフライトリクエストのデータを破損しないために、他の場所でも参照カウントが使用されている理由と同じです。

後バージョンのmemcached（2015年の1.4.23）では、この制限が削除されました。現在、退去プロセスはループして、テールにアクティブなオブジェクトが見つからない場合は再試行します。使用中であってもテールのオブジェクトを退去しますが、参照解除されるまでそのメモリを再利用しません。その後、ループはもう一度試行し、必要に応じて別のオブジェクトを退去します。アクティブなオブジェクトはすぐにLRUの先頭にバンプされるので、退去中にアクティブなオブジェクトをヒットする確率は非常に低く、この機能は安全のためにのみ必要です。

MemC3 対従来のMemcached

この論文は2012年に書かれました。使用されたmemcachedの1.4.13バージョンには、すでにスレッドスケーリングに関する改善が加えられていました。2012年9月にリリースされた1.4.15では、さらに改善されました。その時点で実施した独自テストでは、1.4.15は大量のバッチリクエストを使用して、秒あたり1,360万のキーを取得できました。リクエストレートは、LRUにどの程度ハードにアクセスされているかによって低下します。MemC3は440万ops/秒と主張しています。どの程度のシステムコールバッチングがテストされたかは不明です。

論文では、ベンチマークを実行するためにYCSBを使用しています。リポジトリにはベンチマークコードが含まれています。YCSBを使用して「トレースファイル」を生成し、ファイルをベンチマークメモリに読み込んで、memcachedに対してリプレイする仕組みで動作します。

優れたパフォーマンスが得られていますが、バニラmemcached（1.5M ops/secが得られる）のテストにこの同じベンチマークツールを使用したかどうかは不明です。memcachedのYCSBのデフォルトモジュールは、すべてのリクエストを1つの接続に流し込むため、すべてのリクエストが1つのサーバースレッドによって処理されます。さらに、1.4.18（2014年リリース）までは、memcachedのバグにより、アップタイムの最初の60秒間、すべてのリクエストでLRUが更新されます。通常、アイテムは過去60秒間アクセスされていない場合にのみ再順序付けされます。これにより、最初はベンチマークが非常に低いレートで実行され、最後に速度が上がり、低い平均で終了します。多くの論文では、このバグに気づきませんでした。

執筆時点で、バニラmemcachedのパフォーマンスはMemC3と同じかそれ以上であり、公開時点でさらに近いものであった可能性があります。

LRUロックが軽減されたのは、2015年の1.4.23のリリースが最初でした。ブログ投稿でこれについて書きました

余談：学術的主張はどれほど厳格であるべきでしょうか。

学術論文を気軽に読む人は、傲慢さに気づかないかもしれません。業界は、賛成点を過大に宣伝し、反対点を隠蔽します。学術作品も非常によく似ています。他の人があなたを信じない限り、あなたはがんを治したとは言えません。

学術論文のマーケティングを認識することが重要です。誰かが熱心に自分のアイデアを売り込んでいます。この研究が実用化できるかどうかは読者が識別する必要があります。業界の実務として、コンピュータサイエンスの論文の労働倫理は奇妙なものになります。それらは非常に徹底して議論されていますが、繰り返し可能性に関する基礎を欠き、コードが欠如していることが多く、さらにそのように続いていきます。著者は論文の「ポイント」がアルゴリズムのデモンストレーションであると簡単議論できますが、それでも完全に機能する代替システムであると主張することができます。私たちは、このことが人々を悪いまたは不完全なシステムを設計するように導くため、より高い基準を必要とします。さらに悪いことに、エンジニアが論文の改善を実装するために実用的なシステムを書き直しリファクタリングする際に時間を無駄にします。実際には、実稼働テストで初めて手抜きが明らかになるのです。

MemC3 が新しい種類のキー/バリューストアであること、非常に正確なサイズの小さなオブジェクト (8 バイトのキー、1 ～ 8 バイトの値など) を持つユーザーに役立つことはかまいません。それを memcached の代替として宣伝することは、それが特殊なケースにしか対応できないことから、よい表現ではありません。

結論

私たちは科学論文によってますますターゲットにされています。多くの場合、巨大企業は学校と提携して、内部システムを論文に変換し、より高い信頼を与えるのです。私たちはこれらの主張が検証され、テストが正確であることを保証し、マーケティングがその範囲内にあると理解されることを厳格に行わなければなりません。

MemC3 のケースでは、クックーハッシュの興味深いアプリケーションが、テスト手法の不十分さと手抜きによって影が薄れています。少なくともデータ破損の問題を解決できれば結果は大幅に変わる可能性があり、システム全体に対する改善であるという主張が無効になります。

論文レビュー: MemC3 - Dormando (2020年2月23日)