在這裡，我們分析了較早的論文之一，對 memcached 進行了顯著的效能和記憶體效率修改。我們專注於該論文如何應用於現實世界的產業，以及它在最初發表時提供了什麼。

論文背景

MemC3 論文指出它是在 2013 年 4 月發表的。不同尋常的是，該論文還引用了測試的特定 memcached 版本：1.4.13。該版本於 2012 年 2 月 2 日發布。

Google 引用搜尋產生超過 300 個結果，分為專利和論文。最近於 2019 年和 2020 年發表的論文引用了這篇論文，儘管通常在類似系統或實驗的範例清單中。由於這是 memcached 的早期多執行緒最佳化論文之一，因此經常在許多十幾篇作品中進行比較。

主要主張

MemC3 的摘要聲稱對原始 memcached 進行演算法和工程改進，小型物件的記憶體減少 30%，網路吞吐量增加 3 倍。它使用新穎的布穀鳥雜湊表和 CLOCK 演算法版本來取代 memcached 中的雙向連結 LRU。因此，我們有兩個獨立的主要主張

• 一個緊湊的雜湊表，允許並發讀取器和單一並發寫入器。與鏈式雜湊表相比，以較少的記憶體開銷改善執行緒可擴充性。

• 使用 CLOCK 演算法取代 LRU 鎖定和 16 位元組的 LRU 指標，並使用單一位元。結合雜湊表原子，它們還從每個物件中移除 16 位元參考計數器。

他們提供了一個工作系統作為範例。

是否有可用程式碼？

是的！程式碼可在線上取得。基於 1.4.13，但從 tarball 修改，而不是 git clone。大多數論文未指定他們比較的軟體版本或啟動引數，更不用說提供可用的原始程式碼。

我們能夠建置軟體並測試它。為了修復啟動問題，我們必須註解單一 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 MB 的頁面。物件的大小可能會隨著時間而改變：緩慢地增加或縮小。因此，重要的區塊類別中可能會記憶體不足，從而有效縮小快取大小。

最大的失望是，在任何實際的工作負載下，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;
}

這裡示範當伺服器處理大型要求，但無法一次將所有資料放入 socket 中時會發生什麼事：它會等到 socket 可寫入。使用這個指令碼，鍵「b」的資料會在讀取過程中從「1」變更為「2」！這對任何儲存系統來說都是致命的情況。

補充：我們計算參考的原因

Memcached 物件是「寫入時複製」，表示如果我將新的值設定為相同的鍵，舊的記憶體會保留，直到所有正在運作的用戶端寫入網路完成。然後，參考會變為零，而物件記憶體會釋放。

MemC3 僅在檢查物件的資料結構時將物件參考視為重要。在這種情況下，它們使用帶有版本號碼和衝突迴圈重試的無鎖定演算法。這不會延伸到實際將資料寫入 socket。

這是因為 memcached 的網路處理對物件資料是「零複製」。分散收集系統呼叫用於避免在寫回用戶端之前將物件資料複製到緩衝區中。隨著物件變大，這會帶來更高的效能，並減少大量用戶端連線所需的記憶體。如果物件非常小，這個複製階段不會增加顯著的負擔。實際上，memcached 的生產部署很少只包含小物件。

如果用戶端無法完成將資料寫入 socket（出於任何原因！），在沒有參考計數的情況下，系統可能會重新使用物件的原始記憶體，並將錯誤的資料傳送回用戶端。

MemC3 可以透過先將所有物件資料複製到緩衝區中來解決這個問題，但它必須執行相同的重試常式

• 擷取物件
• 複製到緩衝區
• 原子測試物件是否始終有效？
• 如果是，繼續
• 如果不是，重新擷取物件並重試。

這可能會導致經常更新的物件病態減速。

我們認為這個問題源於 MemC3 論文中對物件參考計數原因的誤解。他們指出，使用參考來避免驅逐目前正在存取的物件。這並非全貌：已參考的物件記憶體無法立即重新使用，這就是舊程式碼會避免驅逐它們的原因。這與在其他地方使用參考計數器的原因相同：避免損毀正在運作的要求的資料。

後續版本的 memcached（2015 年的 1.4.23）移除了這個限制。現在，驅逐程序可以在罕見的情況下在尾端找到活動物件時迴圈並重試。即使尾端物件很忙碌，它也會將其驅逐，但直到它未被參考之前，它不會重新使用其記憶體。然後，迴圈會再次嘗試，並在必要時驅逐另一個物件。活動物件會立即移至 LRU 的頂端，因此在驅逐期間命中一個物件的機率非常低，而且此功能僅是為了安全起見而必需的。

MemC3 與歷史上的 Memcached

這篇論文寫於 2012 年。當時使用的 memcached 1.4.13 版本已經對執行緒縮放進行了改進。1.4.15 版本在 2012 年 9 月發布，進一步改進了執行緒縮放。在我們當時進行的測試中，1.4.15 能夠使用大量的請求批次每秒獲取 1,360 萬個金鑰。請求速率會根據 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 的案例中，一個有趣的 Cuckoo hash 應用程式卻被不良的測試方法論和偷工減料所掩蓋。至少在修正資料毀損問題時，結果可能會大幅改變，使其宣稱對系統整體改善的說法失效。