1 前言
傳統的緩存解決方案將每一個緩存項都當作一個不可變的數據塊對待，這在重度追加的注入工作負載上會產生很多問題，而這種模式的負載在 Pravega 上卻非常常見。每一個追加到流上的事件因此要麼需要有它自己獨立的緩存項，要麼需要緩存提供昂貴的“讀取 - 修改 - 寫入”操作。
為了能夠做到對大小事件的注入都保持高性能 [1]，同時提供近實時的尾端讀取（Tail Read）和高吞吐量的歷史讀取（Historical Read），Pravega 需要一種特殊的緩存以便能夠原生支持流式存儲系統上常見的工作負載。
流式緩存（Streaming Cache），在 Pravega v0.7 [2] 被首次引入，是一個從頭設計的緩存。它專門針對流式數據並且為追加操作做了優化，同時將數據組織成一種有利於緩存淘汰和磁盤換出的結構。
並非所有的緩存都生來平等。而最重要的原則是選擇適用於所應用系統的那種緩存，而這一原則對流式解決方案來說也不例外。在這篇文章中，我們會詳細描述一種創新的緩存方案，它在流式用例上能夠良好運作。
2 段存儲如何緩存數據
段存儲（Segment Store） [3] 是 Pravega 中所有數據路徑操作的核心。它處理所有注入事件，提供近實時的尾部讀取和高吞吐量的歷史讀取。所有經過段存儲的數據都最終路由經過讀取索引（Read Index），它為一級存儲和二級存儲上的數據提供一種統一的視圖。
在追加路徑上 [1]，事件被持久化到一級存儲，而後被加入讀取索引。尾部讀取的數據完全來自緩存，而歷史讀取的數據則從二級存儲預取並按需暫存在讀取索引中。讀取索引的雙重作用在於服務來自 EventStreamReader [4] 的讀請求和作為數據源將數據移動到二級存儲上。因此，單從操作的數量上說，它必須能夠併發處理大量的更新和查詢，並儘可能減少 CPU 和內存的使用。
每一個活動的段都有它的讀取索引，這是一種定製化的，位於內存中的平衡二叉樹（AVL Tree） [5]，將段偏移映射到緩存項。我們需要一個有序索引幫助定位那些包含但並不以給定偏移起始的項，並且還需要一棵平衡樹來確保插入和查詢時間保持相對恆定。
圖 1 經過讀取索引的數據流。 1）追加數據在持久化到一級存儲後被髮送到讀取索引；讀取索引因此插入或更新緩存項。2）尾部的 Reader 從緩存讀取；讀取索引執行查詢並獲取數據。3）歷史 Reader 可能引發緩存未命中，在這種情況下，一個較大範圍的數據被從二級存儲預取並插入緩存；後續的讀取則有較大概率命中緩存。4）緩存管理器（Cache Manager）定位出 E8 為最近未使用項並將其淘汰；執行緩存移除操作。圖例：在讀取緩衝中，A…B: {C, D}表示偏移 A 到 B 被映射到緩存項 C，並具有代數 D（分代用於緩存淘汰）。
3 為何不使用傳統的緩存
作為最低要求，讀取索引需要一個緩存組件並支持插入，獲取和刪除操作。對這樣一種緩存，感性上可以選擇一種支持傳統鍵 / 值 API 的數據結構。Pravega 直到 v0.7 之前也確實一直是這麼做的。每個讀取索引項都指向一個由一對鍵 / 值組成的緩存項。儘管從功能上說確實能夠正確運行，但這樣一種緩存實現在段存儲工作負載下的性能卻不盡如人意，已經成為整個系統上的一處瓶頸。
在流式處理中一個非常常見的操作就是將數據追加到某一個段上。理想情況下，我們需要更新讀取索引，將事件的內容字節追加到最後一個緩存項上，而不是為每一次追加都創建一個新項。然而，讀取索引項被一一映射到緩存項，如果緩存本身不允許修改已存在的項（不可變的特性簡化了許多場景），那麼這裡幾乎無法做進一步提升了。對追加操作我們僅有兩種選擇，要麼創建一個新項，要麼每次進行昂貴的“讀取 - 修改 - 寫入”操作（讀取最後項的內容，為已有內容和追加內容分配一個新緩衝，然後把新緩衝重新插回緩存中）。這兩種選擇都會產生副作用，導致過量的內存和 CPU 開銷，這都不是高性能系統所期望的。
所有的鍵 / 值緩存都需要實現某種索引以便把鍵映射到值。無論是基於簡單哈希表的內存緩存，還是更復雜的使用 B+ 樹 [6] 或者 LSM 樹 [7] 的磁盤可換出緩存，維護這一索引都有開銷。然而，如果我們後退一步看一下讀取索引，我們就會注意到我們其實並不需要這些額外的數據結構：平衡二叉樹已經把段偏移映射到緩存項了。根本沒有必要再維護一個額外的索引來映射緩存項到緩存的內部。一個簡單的內存指針就足夠了。
當我們最初發布 Pravega 的時候，RocksDB [8] 是我們對緩存的選擇。儘管它是一個優秀的本地鍵 / 值存儲並提供諸多特性，Pravega 並沒有使用這些特性而僅僅將 RocksDB 用作一個堆外緩存，使得過量數據可以在必要時換出到磁盤。然而，在容器化環境中進行 Pravega 的基準測試時，我們發現了一些由於使用 RocksDB 作為緩存而直接導致的問題。其中最嚴重的一個問題就是無法為所使用的內存設定上界，這使得 Kubernetes [9] 由於過量內存使用 [10] 而終止我們的 POD。控制 RocksDB 內存用量的唯一辦法就是配置讀寫緩衝的大小。增大讀寫緩衝使得在需要進行基於磁盤的壓縮之前有更多的數據被緩存在內存中，而減小這個緩衝則更加頻繁地觸發壓縮，因此也導致了更頻繁和更長時間的寫停頓，引起性能下降。
為擺脫物理驅動器的束縛，人們可以選擇將 RocksDB 運行在內存存儲上，但這也使得控制總體內存使用量變得更加困難。即便從一開始就關閉了預寫日誌（Write Ahead Log，WAL），我們嘗試了調優所有已知的 RocksDB 參數，包括關閉布隆過濾器（Bloom Filter）和調整壓縮策略，但都沒有取得顯著的效果。於是我們決定尋找這一核心系統部件的替代實現。
作為 Pravega v0.7 的一部分，我們提升了系統性能，並且花費了很多時間尋找和解決數據注入路徑上的瓶頸。這些提升的核心就是流式緩存：來自流視角的一種創新的緩存方法。
4 設計流式緩存
我們想保持緩存數據位於堆外以避免 Java 的垃圾回收問題。這有助於減少垃圾回收引發的停頓，但它同時也意味著我們無法享受垃圾回收所提供的便利：內存壓縮 [11]。當被調用時，內存分配器需要找到一塊連續的內存（與所請求的大小相同），因此任意存儲和刪除不同大小的數組最終將導致內存不足的錯誤。Java 的垃圾收集器會移動堆上的對象以便減少內存碎片 [12]，但我們卻無法使用。因此，我們需要一種設計能夠以最小代價減少或消除這個問題帶來的影響。
在例如 Kubernetes 這樣的容器化環境中運行 Pravega，需要內存使用量的調優。由於緩存也是內存的一部分，我們必須控制緩存內存使用的上界，包括它的元數據和索引開銷。任何緩存都會有這樣的開銷：即便一個簡單的哈希表也需要同時存儲鍵和值，以及那些未使用的數組單元。我們對 Pravega 在這種環境中進行了大量測試，我們發現用現有的開源解決方案很難解決此類內存使用問題。
為了解決內存碎片和元數據開銷，我們從塊存儲上得到了啟發。我們將緩存劃分為相同大小的緩存塊（Cache Block），其中每一個緩存塊都可以用一個 32 位的指針唯一尋址，選取 4KB 作為塊大小使得每緩存最大理論容量達到了 16TB，這對單節點緩存來說已經足夠了。
緩存塊被組織成鏈表形成了緩存項（Cache Entry）。每個緩存塊都有一個指針指向鏈表中位於它之前的另一個緩存塊。因為每個緩存塊都有一個地址，我們可以選擇鏈表中的最後一個緩存塊的地址來表示整個緩存項的地址。這樣我們就可以從讀取索引中引用這一地址。儘管有一點點反直覺，指向最後一個緩存塊使得我們可以立即定位它並進行追加操作，無論是直接像它寫入（如果它還有空閒空間）還是找到一個新的空緩存塊並將其加入鏈表。
類似緩存項中所使用的緩存塊，空緩存塊同樣也被鏈接在一起，這使得定位一個可用緩存塊成為一個複雜度為 O(1) 的操作。當需要分配一個新緩存塊時，我們所要做的就是在這個鏈表的尾端取一個，這使得它的後繼成為下一個頭指針。刪除一個項將引起它的緩存塊被重新加回這個鏈表以便將來複用。
圖 2 緩存項由鏈狀的緩存塊組成，並且項的地址指向鏈表中的最後一個塊。緩存項不必存儲在連續的緩存塊中。空閒緩存塊同樣被鏈接在一起，這將允許快速分配新項。
分別分配每一個緩存塊並且使用專門的內存池並不能完全避免內存碎片問題，卻讓我們為了管理所有的塊不得不引入大量的元數據（在堆上）。相反地，我們可以分配我們自己的內存池（其實就是一塊連續的內存塊）。仍然，因為內存塊需要是連續的，我們很可能無法一次性分配。因此，我們將這個內存池分割成更小的，等大小的段，稱作緩存緩衝（Cache Buffer）。
當初始化緩存時，我們事先分配所有我們需要的緩存緩衝，這保證我們為後續使用預留了足夠的內存。每個緩存緩衝持有固定數目的緩存塊。例如，每個 2MB 的緩存緩衝可以持有 512 個 4KB 的緩存塊。
對於空緩存塊，為所有緩存緩衝保留一個單一的塊列表將會非常難維護（尤其對於較大的緩存），並且當我們對其進行修改操作的時候會很快遇到併發問題。我們因此選擇對每一個緩存緩衝（更小的併發域）維護一個這樣的空緩存塊列表。對於跨緩衝的情況，我們使用另一種不同的方法。所有緩衝最開始都被加入一個隊列。當我們需要使用一個新的緩存塊時，我們從這個隊列獲取第一個緩衝，並使用來自它的一個緩存塊。如果這會導致緩衝被填滿，那麼我們就將它從隊列移除。因此，當釋放一個緩存塊時，一個滿的緩衝則又會獲得可用空間，我們將其加入隊列的末端。
圖 3 主要的緩存操作如圖所示。尚未填滿的緩存緩衝存儲在一個隊列中；當它們被填滿時會被從隊列移除，而當它們至少獲得一個可用的緩存塊時（緩存項被刪除後）會被重新加回隊列。
這個方法解決了由分配器碎片引起的內存浪費問題，但它又引入了其它問題：緩存項碎片。例如，在一系列涉及不同大小緩存項的插入和刪除操作之後，空閒緩存塊鏈表可能不再指向連續的塊。如圖 2 所示，如果我們想要插入一條需要 5 個塊的項 E3（未在圖中畫出），它將被存儲在塊 1，4，6，7 和 14 上。因為這些塊並不位於一塊連續的內存，這種情況可能導致潛在的性能下降，尤其是對於內存換出系統。然而，我們期望 Pravega 能夠被提供充足的內存，足以容納整個緩存並且避免換出。這一配置通常對於隨機訪問表現良好。未來，我們可以通過提升我們的緩存項分配算法來緩解這一問題。
綜上所述，流式緩存由一組大小相同的緩存緩衝組成，其中每個緩衝又由相同大小的緩存塊組成。每個緩存緩衝的第一個塊被保留用作記錄該緩衝其它塊的元數據。這些元數據包括塊是否被使用，塊內保存了多少內容，鏈表內的前一個塊是什麼（如果這是一個使用中的塊），以及下一個空閒塊是什麼（如果這是一個空閒塊）。
實際的存儲開銷相對較小：存儲在 Java 堆上的唯一信息就是緩存緩衝的指針（本質上就是 ByteBuffer [13]），其它的元數據都存儲在堆外。當有最大尺寸限制時，流式緩衝能確保元數據和實際緩存塊都受限於這個最大值，因此它絕不會超過這個限制。額外開銷同樣很容易計算：使用 4KB 的緩存塊和 2MB 的緩存緩衝允許我們使用每個緩衝 512 個塊中的 511 個，結果就是一個常數 0.2% 的額外開銷（例如，4GB 的緩存有 8MB 的額外開銷）。
讓我們用一個實際的例子看看流式緩存時如何運作的，如下圖（圖 4）所示。
圖 4 一個具有 4 個緩衝的緩存結構。為簡單起見，每個緩衝只顯示 8 個 4KB 的緩存塊。
圖 4 描繪了一個具有 4 個項的緩存。A 小節可視化地展示了緩衝佈局，而 B 小節則用列表格式展示了相同的佈局。項 E1 有 6 個塊，全部在緩衝 0 上分配。因為最後一個塊是 0-6（緩衝 0，塊 6），它也被用作整個項的地址。項 E2 完全佔據了從緩衝 1 到緩衝 2 的 5 個塊。儘管還是空的，E3 是一個合法的緩存項，並且佔用一個完整的塊，但它尚未存儲任何數據。
緩衝 0，1 和 2 的元數據分別如小節 C，D 和 E 所示。“Prev”列可用於重建某個項的完整鏈表結構。例如，項 E4 具有地址 1-4 並且“Prev”值為 0-7，並且再沒有更多的“Prev”值了。因此，E4 的鏈結構為 0-7，1-4。“Next”列可用於定位空閒列表。緩衝 0（C 小節）已經沒有空閒塊了，但我們可以很容易地看出緩衝 1 包含塊 5 作為它的第一個空閒緩衝（元數據塊 0 的“Next”值為 5）。對於其它的緩存項和緩衝都可以做出類似的推斷。對於空閒緩衝，例如緩衝 3，它的每一個塊都指向右邊的塊形成未使用塊的鏈表。
5 基準測試
通常，非常大的改動是不會進入 Pravega 的源碼倉庫的，除非它被證實有明確的性能提升。我們執行了幾種類型的測試，從緩存本身，再到將其集成進段存儲。
在我們繼續之前需要進行一個快速說明。就像所有的性能基準測試那樣，測試結果會隨不同的硬件和操作系統以及 Pravega 版本的變化而變化。所有這些測試都在一臺具有 8 顆因特爾 Core™ i7-6700 CPU，主頻 3.4GHz，64GB 內存的戴爾 Optiplex™ 7040 桌面工作站上進行。操作系統是 Ubuntu 16.04，Pravega 版本是 v0.7。段存儲相關測試使用單一段存儲實例，並使用基於內存的一級和二級存儲（目的是觀測緩存的效果）。每項測試都會反覆進行多次，並選取最好的成績（為了儘可能接近真實的 CPU 時間）。根據所使用的硬件和操作系統的不同，基準測試可能輸出不同的結果。
5.1 原始緩存的基準測試
這項測試的目的是觀測流式緩存在進行各種典型操作時所花費的時間。基準測試執行如下幾類操作：
- 順序測試。1,000,000 個 10KB 的項被插入，查詢，然後從緩存中刪除。
- 隨機測試。執行總數為 1,000,000 個的操作，每個操作有 60% 的概率為插入操作，40% 的概率為移除操作。每次，一個隨機的項被選取並讀取。這項測試在 10KB 和 100KB 大小的項上進行。
我們測試了 Java 的 HashMap 數據結構，之前使用的基於 RocksDB 的緩存實現，以及流式緩存。測試結果總結在下表中，展示了以微秒為單位的每操 / 測試作所花費的時間：
表 1 原始緩存的基準測試結果。結果展示了以微秒的每操作 / 測試所花費的時間。
在所有的測試中，流式緩存都比基於 RocksDB 的緩存表現更好，它甚至還超過了基於 HashMap 的緩存。讓我們分別看一下這些用例：
- HashMap 對 put 和 get 操作的時間複雜度都是 O(1)，但因為它是泛型集合，它並不持有數據，它只保存指向數據的指針。因此，我們必須分配 / 回收 / 複製緩衝區才能進行存儲。例如，如果數據最初來自某個套接字（Socket）的緩衝區，這個緩衝區可能很快會被釋放，這樣我們就只剩下一個指向非法內存的指針了。從另一方面說，如果我們提供了指向內部字節數組的指針，這將會允許外部代碼在我們不知情的情況下對其進行修改。將數據複製移入 / 移出 HashMap 使得它的性能相對不如流式緩存。我們分別以兩種模式運行這項測試：一種，我們進行如上所述的緩衝區複製操作，而另一種，我們不進行復制。後者所花費的時間只有前者的十分之一，額外的時間花費都是由字節數組的分配和數據複製引起的。
- RocksDB 需要維護一些索引和其它數據結構以便提供它的功能。同時，當某些觸發器滿足條件時，也會開始向磁盤換出數據，這使得 IO 操作降速到後端磁盤的速度（這在 100KB 的隨機測試中表現尤為明顯）。HashMap 緩存沒有磁盤 IO 和複雜的數據結構，但這是以 Java 的垃圾回收為代價的。每個插入和讀取緩存的調用都需要分配一個新的字節數組，如果此時需要垃圾收集器介入釋放空間，那麼就將引發停頓。更進一步，大量此類的分配和釋放操作將產生碎片，使得垃圾收集器不得不壓縮內存以解決碎片問題，這也會造成垃圾收集過程的停頓並最終拖慢整個程序。
- 流式緩存在所有這些測試中都表現良好，因為它是專門為了段存儲的特殊需求而剪裁的。插入操作無需分配內存（緩存緩衝是事先分配好的），數據直接從 Netty [14] 緩衝複製進入緩存。讀取操作返回緩存項的只讀視圖，這允許直接將內容複製到所需要的地方（二級存儲的寫緩衝或者 Netty 緩衝 - 客戶端讀取）。為公平起見，在讀取操作之後我們已經模擬了這些複製動作，並且將其所花費的額外時間包含進流式存儲的基準測試中去。HashMap 唯一遠超流式緩存的測試用例就是刪除操作。這是因為流式緩存需要釋放所有被引用的塊，而 HashMap 只需要解引用字節數組，將真正的內存回收動作延後（通過垃圾回收）。
5.2 段存儲的基準測試
接下來，我們將流式存儲集成進段存儲，再運行一些集成測試。幾乎所有對 Pravega 所做的修改都可以在本地進行基準測試，甚至發生在開發者本地工作站推送源碼之前。自測工具 [15] 允許我們運行各種目標測試，只要運用得當，它可以展示某個提交的變更是否可以提升性能。
我們執行了一些測試，分別專注於段存儲的不同方面。每個測試都有 100 個並行的生產者以每次 100 個的大小批量發送事件 / 更新。吞吐量以 MB/s 為單位進行統計，而延遲則以微秒為單位。在以下的測試中，“基線”表示未使用流式緩存的 Pravega v0.7（使用先前的基於 RocksDB 的緩存）。相對的，“流式緩存”表示使用流式緩存的 Pravega v0.7（唯一的區別就是緩存的實現）。
5.2.1 流式處理延遲
這項測試的目的是測量小尺（100 字節）寸追加操作的的延遲。
表 2 小尺寸（100 字節）追加操作的延遲，單位：毫秒。
自測參數：-Dtarget=InProcessStore -Dbkc=0 -Dcc=0 -Dssc=1 -Dc=1 -Ds=1 -Dsc=4 -Dp=100 -Dpp=100 -Dws=1000 -Do=2000000
5.2.2 流式處理吞吐量
這項測試的目的是測量中等尺寸（10KB）追加操作的吞吐量：
表 3 中等尺寸（10KB）追加操作的吞吐量，單位：MB/s。
自測參數：-Dtarget=InProcessStore -Dbkc=0 -Dcc=0 -Dssc=1 -Dc=1 -Ds=1 -Dsc=4 -Dp=100 -Dpp=100 -Dws=10000 -Do=1000000
6 總結
緩存機制在 Pravega 的進站和出站性能中起著關鍵作用。尾部讀取的數據全部來自於緩存，而歷史讀取則用它存儲預取數據：它們在從二級存儲讀出後被暫存在緩存中，直到被某個 Reader 所消費。幾乎所有的用戶操作都會以這樣或那樣的方式涉及到緩存。對緩存的選擇可以成就也可能破壞 Pravega 的吞吐量和延遲。可能就是緩存的選取造成了一個能近實時響應的集群和一個在重負載下緩慢運行的集群之間的差異。通過消除某些典型緩存實現中的額外開銷，流式緩存通過使用基於塊結構的無索引布局，提供了一種快速有效的方法來暫存大量流式數據。採用流式緩存後，我們在數據注入路徑上發現的一些瓶頸都得以解決，這也使得我們能夠在搞吞吐量的重負載下顯著降低尾部延遲。
【雲棲號在線課堂】每天都有產品技術專家分享！
課程地址：https://yqh.aliyun.com/live本文作者：Andrei Paduroiu，蔡超前，滕昱