在这里，我们分析了早期论文之一，该论文对 memcached 进行了重大性能和内存效率改进。我们重点关注论文如何应用于现实世界的行业以及它在最初发表时提供了什么。

论文背景

该 MemC3 论文 指出它是在 2013 年 4 月发表的。不同寻常的是，该论文还引用了测试的 memcached 的特定版本：1.4.13。该版本于 2012 年 2 月 2 日发布。

谷歌引用搜索产生了 300 多个结果，分布在专利和论文中。最近在 2019 年和 2020 年发表的出版物引用了这篇论文，尽管通常是在类似系统或实验的示例列表中。由于这是 memcached 的早期多线程优化论文之一，因此它经常在数十篇作品中进行比较。

主要主张

MemC3 的摘要声称对原始 memcached 进行了算法和工程改进，小对象的内存减少了 30%，网络吞吐量提高了 3 倍。它通过一种新颖的布谷鸟哈希表和 CLOCK 算法的版本来实现这一点，以替换 memcached 中的双向 LRU。因此，我们有两个独立的主要主张

• 一个紧凑的哈希表，它允许并发读取器和单个并发写入器。通过比链式哈希表更少的内存开销来提高线程可扩展性。

• 使用 CLOCK 算法来替换 LRU 锁和 16 字节的 LRU 指针，用一个位代替。结合哈希表原子操作，它们还从每个对象中删除了 16 位引用计数器。

他们提供了一个工作系统作为示例。

代码是否可用？

是的！代码 可在线获取。基于 1.4.13，但从 tarball 修改而来，而不是 git 克隆。大多数论文都没有指定它们比较的软件的版本或启动参数，更不用说提供工作源代码了。

我们能够构建软件并对其进行测试。为了解决启动问题，我们不得不注释掉一行 pthread CPU 亲和力行；这很好，因为我们最终没有测试性能。

验证主张

简而言之，布谷鸟哈希 和 CLOCK 替换 似乎按预期工作；通常内存效率高，同时避免全局锁。

我们不会深入探讨哈希算法的细节。有 许多 文章 深入探讨探测类型哈希表以及内存与速度之间的权衡。

在 1.4.13 版本的 memcached 中，在从哈希表中获取或删除对象时会持有全局锁。然后使用一组互斥锁来锁定正在获取或修改的单个对象。

在 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 功能（如果版本号匹配则更新对象）已损坏/注释掉。
• “删除”命令已损坏。它从哈希表中删除了对象，但随后泄漏了内存，而不是返回到 slab 分配器。
• INCR/DECR 命令已注释掉。
• slab 重新平衡功能已完全移除。
• 最关键的是：MemC3 可能返回错误或损坏的数据。

需要注意的是，学术出版物的发布时间表意味着他们可能没有足够的时间来启用所有功能。我们认为，不提及这些被移除的功能是不诚实的，因为它们会影响性能。至少应该包含修复这些功能的想法或计划。

省略 slab 重新平衡功能，以及论文中没有提及它，是他们声称在系统替换中实现内存效率的最大障碍。

Memcached 使用 slab 分配器来存储其对象数据。这意味着可用内存被切割成 1 兆字节的页面，然后这些页面被切分成大小相似的对象。例如：slab 类 1 可能包含大小为 90 字节或更小的对象，而 slab 类 2 包含大小为 90 到 120 字节之间的对象，等等。这减轻了 malloc/free 实现带来的内存碎片问题，并确保 memcached 只需要在添加一个新对象时驱逐一个对象。这些权衡在长时间运行时创造了可靠的性能。

slab 重新平衡算法允许在 slab 类之间移动这些 1 兆字节的页面。对象的大小可能会随着时间的推移而改变：缓慢增长或缩小。因此，可能在一个重要的 slab 类中内存不足，从而有效地缩小了缓存大小。

最大的失望是，在任何实际工作负载下，MemC3 都会频繁地返回错误数据。如果“删除”命令有效，它会完全返回错误的键。

以下脚本重现了故障并有助于解释原因

#!/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 对象是“写时复制”，这意味着如果我将新值设置为同一个键，旧内存将保留，直到所有正在进行的客户端完成写入网络。然后引用达到零，对象内存被释放。

MemC3 仅在*检查对象的​​数据结构*时才将对象引用视为重要。在这种情况下，它们使用无锁算法，带有版本号和冲突时的循环重试。这并不扩展到实际将数据写入套接字。

这是因为 memcached 的网络处理对于对象数据是“零拷贝”。使用散射-收集系统调用来避免在将对象数据写回客户端之前将其复制到缓冲区中。当对象变大时，这会提高性能，并减少大量客户端连接所需的内存。如果对象严格很小，此复制阶段不会增加明显的开销。memcached 的实际生产部署很少只包含小型对象。

如果客户端因任何原因无法完成将数据写入套接字，则在没有引用计数的情况下，对象的原始内存可能会被系统重新使用，并将错误的数据发送回客户端。

MemC3 可以通过首先将所有对象数据复制到缓冲区来解决此问题，但它必须执行相同的重试例程

• 获取对象
• 复制到缓冲区
• 原子地测试对象是否始终有效？
• 如果是，则继续
• 如果不是，则重新获取对象并重试。

这会导致频繁更新的对象出现病态的性能下降。

我们认为这个问题源于对 MemC3 论文中关于对象引用计数原因的误解。论文中指出，引用计数用于避免驱逐当前正在访问的对象。但这并非全部：被引用的对象内存不能立即被重用，这就是旧代码避免驱逐它们的原因。这与其他地方使用引用计数的原因相同：避免在进行中的请求中破坏数据。

后来的 memcached 版本（2015 年的 1.4.23 版本）消除了此限制。现在，驱逐过程可以在罕见的情况下找到尾部有活动对象时循环并重试。它会驱逐尾部对象，即使它很忙，但不会在它被取消引用之前重用它的内存。然后循环再次尝试，并在必要时驱逐另一个对象。活动对象会立即被提升到 LRU 的顶部，因此在驱逐过程中遇到活动对象的概率非常低，此功能仅用于安全目的。

MemC3 与历史 Memcached

这篇论文写于 2012 年。使用的 1.4.13 版本的 memcached 已经对线程扩展进行了改进。在 2012 年 9 月发布的 1.4.15 版本中又进行了进一步的改进。在我们当时自己的测试中，1.4.15 版本能够使用大批量的请求每秒获取 1360 万个键。请求速率会根据 LRU 被访问的程度而下降。MemC3 声称每秒 440 万次操作。目前尚不清楚测试了多少系统调用批处理。

这篇论文使用 YCSB 来运行基准测试。他们在存储库中包含了一些基准测试代码。它通过使用 YCSB 生成“跟踪文件”，然后将文件读入基准测试内存并重播到 memcached 来工作。

虽然他们获得了良好的性能，但目前尚不清楚他们是否使用相同的基准测试工具来测试普通 memcached（他们从中获得了每秒 150 万次操作）。YCSB 用于 memcached 的默认模块将所有请求都发送到单个连接，这会导致所有请求都被单个服务器线程处理。此外，在 1.4.18 版本（2014 年发布）之前，memcached 中的一个错误会导致每个请求在启动后的前 60 秒内更新 LRU。通常，只有在过去 60 秒内未访问过某个项目时才会重新排序它。这会导致基准测试在开始时以极低的速率运行，在结束时加速，然后以较低的平均值结束。许多论文都没有注意到这个错误。

在撰写本文时，普通 memcached 的性能可能与 MemC3 相同或更高，并且在发表时更加接近。

直到 2015 年，随着 1.4.23 版本的发布，LRU 锁才得到缓解。 我们在博客文章中对此进行了介绍

旁白：学术主张应该有多严格？

非专业读者可能无法识别学术论文中的“自负”。行业工作者通常会大力宣传其产品的优点，而掩盖其缺点。学术作品也是如此：除非你让其他人相信你已经治愈了癌症，否则你并没有真正治愈癌症。

重要的是要认识到学术论文的营销手段。作者会竭力推销他们的想法，而读者需要判断这项工作是否适用于生产工具。作为一名行业从业者，我发现计算机科学论文的工作方式很奇怪。它们论证非常充分，但却缺乏可重复性的基本要素，经常缺少代码等等。作者可以轻松地辩称论文的“重点”是算法的演示，但同时声称这是一个完全可用的替代系统。我们需要更高的标准，因为这会导致人们设计出糟糕或不完整的系统。更糟糕的是，这会浪费时间，因为工程师会重写和重构现有的系统来实现论文中的改进，结果却在生产测试中发现漏洞。

MemC3 作为一种新型的键值存储，对于需要存储非常精确大小的小对象（8 字节键，1-8 字节值等）的用户来说很有用。但将其宣传为 memcached 的替代品，充其量是误导，因为它只适用于一种特殊情况。

结论

我们越来越受到科学论文的营销影响。大型公司经常会与学校合作，将内部系统转化为论文，以提高其可信度。我们必须严格确保这些声明得到验证，测试准确，并且了解营销的本质。

以 MemC3 为例，一个有趣的布谷鸟哈希应用却被糟糕的测试方法和偷工减料所掩盖。至少修复数据损坏问题后，结果可能会发生重大变化，从而使其声称对系统进行全面改进的说法失效。