持久性記憶體的易失性優點：第二部分 - Dormando（2019 年 5 月 8 日）
考量到這個對我們來說全新的硬體平台，我們希望找到新的探索方向。我們發現的結果令人著迷：問題比預期的還要無聊許多。
未來：從實驗中觀察
我們對資料結構進行了一項小型調查：DRAM 和 PMEM 非常相似，但 PMEM 具有較高的延遲。Memcached 有一個傳統的 鏈結雜湊表。是否有任何更現代的資料結構可以減少與 PMEM 的往返次數，以產生差異？
我們（目前）尚未找到任何可以大幅改善的方法。本文的其餘部分將探討其中一些想法及其結果。
事實證明，我們的現有資料結構在面對 PMEM 時已獲得最佳化。LRU 演算法 嘗試將對經常存取的項目進行的變更降至最低。從那裡開始，大多數記憶體存取發生在項目中繼資料中，而這些中繼資料符合 DRAM 快取行（64b）。PMEM 本身的快取行為 256 位元組，通常會包含中繼資料和整個金鑰。這表示將金鑰與比對結果進行比對，以及結果中繼資料檢查，會導致對底層 PMEM 進行一次擷取。
經常存取的項目也會受益於處理器快取，因此熱門或非常新的金鑰可以在不進行任何進一步工作的狀況下獲得效能提升。
鏈結雜湊表
理論：當儲存區深度較深時，鏈結雜湊表的效能不佳，這可能會因 PMEM 的延遲而更加惡化。
現實：memcached 會在每個儲存區的平均深度超過 1.5 個項目之前自動調整雜湊表的尺寸。效能差異很小。
一個主要問題是鏈接雜湊表。雜湊表是透過指標的扁平陣列來實作。一個金鑰會雜湊成一個儲存區編號，如果儲存區非 NULL，就會找到一個項目。然後必須將金鑰與要求進行比較，以確保它是要求的確切項目。
如果發生衝突，儲存區會透過單向連結清單「變深」。項目結構中的指標會指向下一個雜湊表項目。這表示找到的每個項目不是所需的項目，都會產生額外的往返 PMEM。
當條目數（「負載」）為原始陣列大小的 150% 時，Memcached 會自動將其雜湊表大小加倍。然後，雜湊表密度會在 50% 到 150% 的負載之間變化。如果雜湊演算法完全公平，平均儲存區深度最差情況會是 1.5。實際上，最差情況會高於 1.5，但不會高出太多。
為了進行快速測試，我們用 201,326,591 個項目填滿了 memcached，足以低於 150% 的雜湊表負載。然後我們強制雜湊表擴充，將其負載降低到 50%。使用這個設定，我們執行了之前「接近實際」的步調負載測試，其中使用了大量的用戶端連線。
這裡我們觀察一個系統呼叫密集測試的平均延遲，只改變雜湊表的大小。所有要求都從持續性記憶體中提供服務。隨著伺服器變得忙碌且時脈穩定，延遲會略微下降，然後隨著伺服器過載而開始上升。由於測試的性質是大量排隊的連線，而且效能接近，因此這些測試的 p99 延遲是隨機的。只有實際平均值在多次測試執行中顯示出一致的差異。
我們看到超大雜湊表確實獲勝。請注意延遲有多接近：最差情況的雜湊表平均而言會損失 5 微秒。如果您需要榨取每一滴效能，超大雜湊表可以提供幫助。否則，這並不是一個巨大的勝利。
參考計數燒毀
理論：每次讀取都會導致對持續性記憶體的寫入：參考計數更新、LRU 變異等。可能會導致一個大問題。
現實：幾乎沒有差別。禁用參考計數和 LRU 洗牌已進行基準測試，僅顯示出 5% 的改進。
大多數記憶體存取都在項目記憶體之外：連線緩衝區、統計計數器，甚至雜湊計算在大多數情況下都是在要求輸入緩衝區而不是項目記憶體中執行。
為了滿足GET要求，幾乎不會觸及項目記憶體
- 項目金鑰會與要求緩衝區進行比較，以完成雜湊表查詢。
- 過期時間已過測試。
- 如果比對成功，則參考計數器會增加。
- 如果最近沒有更新，則可能會更新一些位元標記和「上次存取時間」。
- 金鑰加值會非同步寫入至客戶端插槽。
- 參考計數器會減少。
由於 Intel PMEM 以 256 位元組區塊載入記憶體，因此夠小的項目可能只需進行一次讀取即可完成大部分工作。其餘的小型讀取則由 CPU 快取處理。LRU、上次存取時間和標記並非總是會在讀取時更新。對於忙碌的項目，只會調整兩個位元組的參考計數。即使項目元資料在程式碼中會被參照幾次，但存取 PMEM 的延遲懲罰是固定的。
分層記憶體
理論：最近插入的項目最有可能被存取或取代。在使用率較低時將項目快取至 PMEM 應可提升效能。
現實：速度更慢
LRU 演算法 會將記憶體方便地分成熱 (新)、溫 (頻繁存取) 和冷 (較不頻繁存取)。如果將冷項目放在 PMEM 中，而將熱/溫項目留在 DRAM 中，會如何？
在快取已滿的情況下，每個新的 SET 都會導致
- 熱區塊的尾端必須轉換為冷區塊，並複製至 PMEM。
- 為執行此動作，必須將冷區塊的尾端逐出，以騰出空間給熱區塊的項目。
- 最後，熱區塊會取得其項目資料。
這會讓 SET 的執行時間變為兩倍，而讀取效能的提升並不足以抵銷此影響。頻繁命中的項目會儲存在處理器快取中，因此 PMEM 效能並不重要。
緩衝快取
理論：頻繁存取的項目會使用 RAM 緩衝快取。
現實：可能實際上更好，但變動很大。
與分層方法相反，新項目的 SET 將保持不變。當存取項目時，可以根據機率將其拉入 DRAM 中的緩衝快取。後續的讀取會命中快取項目。利用隨機機會會減少從緩衝池中逐出記憶體以供不頻繁存取的項目時產生的負擔。
原始項目會保留在 PMEM 中，並將一個虛假項目連結到雜湊表。虛假項目會指向真實項目；在刪除、覆寫或從緩衝池中移除時，會還原或釋放原始記憶體。
需要大量的程式碼變更才能達成，而且讀取效能的提升幅度很小；可能只對極度敏感的應用程式有幫助。由於 CPU 快取的關係，變得非常熱門的鍵會與沒有緩衝快取的情況下效能相同。
自適應基數樹
理論：ART 可用於 DRAM 中，以避免在查詢期間檢查 PMEM 來比較鍵，而無需使用大量的記憶體。
現實：可行，但難以擴充，而且鏈結表目前效能良好。
自適應基數樹 是一種非常有趣的相對較新的資料結構。使用 ART 時，您不需要對鍵進行雜湊即可查詢它。在決定比對是否正確之前，也不需要將完整鍵與最終節點進行比較。Memcached 現有的鏈結雜湊表可能必須多次擷取到 PMEM 中才能找到一個項目；ART 可以在 DRAM 中完全保留，只在成功比對時擷取項目資料。此外，由於其排序性質，甚至可能合理地直接在 PMEM 中執行 ART。
An Inefficient Memcached Key
departmentname:appname:subsystem:userdata:picnum:{id}
ART Prefix Compression
[departmentname:][appname:][subsystem:][userdata:][picnum:]{id}
不幸的是，ART 在細節上有所損失：memcached 可以儲存數億個具有類似字首的鍵，但最後會因數字而有所不同。這可能導致在找到一個項目之前，在 DRAM 中多次跳轉。此外，對此類結構的並行性研究很少。現有方法需要在查詢的每個階段進行鎖定。並行寫入可能會導致查詢完全重新開始。相比之下，memcached 的鏈結雜湊表需要一個單一的互斥鎖才能進行查詢，而且我們很樂意避免的雜湊計算是在取得任何鎖定之前完成的。
未來可能會有潛力；我們正在關注這個領域。
外部參考計數器
理論：查詢項目需要兩次寫入 refcount。將其移至 DRAM 可以節省效能和裝置使用壽命。
現實：間接緩慢，效能提升最多 5%。可能值得嘗試。
由於可以同時請求許多項目，因此危害指標和類似的建構對於 memcached 來說擴充性不佳。目前我們只能使用參考計數。與一些學術論文的想法相反；參考計數器不是用於鎖定或並行性，而是安全性和正確性。鍵和值透過分散收集網路複製到客戶端。如果客戶端讀取資料的速度很慢，則在項目的記憶體傳送到客戶端之前，可能會經過很長一段時間。如果沒有寫入時複製和參考計數，則項目的記憶體可能會被「刪除」，然後重新使用。然後錯誤的資料會被傳送到客戶端。一個災難性的錯誤。
一種想法是，如果項目的金鑰和值夠小，則存在大小臨界點，此時將值複製到緩衝區中（同時鎖定項目）比兩次增加參考計數更快。這尤其真實，因為目前需要完整的互斥鎖才能遞減參考計數，儘管這可能會在未來得到修復。
項目不攜帶自己的互斥鎖：會檢查一個較小的獨立互斥鎖表格，而具有類似雜湊位元的項目會共用互斥鎖。此表格可以針對每個鎖擴充一個 [POINTER,refcount] 陣列，並根據需要進行擴充或收縮。如果項目沒有任何參考，則它不會有參考計數記憶體。這可以為每個項目節省兩個位元組。
這是一個複雜的變更，而最大影響小於 5% 的效能和兩個位元組的記憶體。使用外部參考計數，我們也可能對 DRAM 進行更多存取。最後，DRAM 中的外部參考計數可能比透過 PMEM 存取它來得慢，以內嵌方式存取項目元資料。
結論
現有的 memcached 與 Intel® Optane™ DC 持久性記憶體模組配合得非常好。提升效能將具有挑戰性。這可能會不值得進行。這讓我們能夠專注於功能和穩定性，而無需花費大量時間讓服務「與 PMEM 相容」。
儘管如此，我們仍處於現代持久性記憶體的早期階段。目前我們的雜湊表位於 RAM 中，但這也可能移至 PMEM。是否有場景甚至可以讓客戶端連線緩衝區僅使用 PMEM？
為了節省記憶體，我們這段時間以來跳過或遺漏了哪些其他功能？