線性彈性快取透過將頁面逐出視為「滑雪租賃問題」，並利用輕量級機器學習來最佳化記憶體佔用與快取遺失之間的權衡，從而最大限度地降低總快取成本。

現代高效能資料庫系統和雲端服務仰賴記憶體內快取，將頻繁存取的資料保留在 RAM 中，以繞過緩慢的磁碟操作，並提供使用者期望的閃電般快速回應時間。然而，這種效能是有代價的：高速記憶體價格昂貴，一些無伺服器雲端供應商每天對 1 GiB 記憶體收取高達 3 美元的費用。

過去，快取管理一直被視為固定資源問題。在常規的固定大小快取中，工程師會為快取分配特定量的記憶體，系統則使用「最近最少使用 (LRU)」等逐出策略來決定當空間不足時要保留哪些資料。這導致了經典的「金髮姑娘問題」：快取大小設定太小，效能會急劇下降；設定太大以應對尖峰需求，則會浪費數千美元在閒置記憶體上。

我們在創新資料系統研究會議 (CIDR) 上發表了一篇論文，介紹了線性彈性快取，這是一種旨在透過動態調整快取大小以回應即時工作負載，來最小化快取管理總持有成本 (TCO) 的新方法。我們不再將記憶體視為固定、預先分配的資源，而是將其視為一種公用事業，其成本與快取資料的大小和資料在快取中保留的時間呈線性關係。透過將記憶體佔用視為隨時間整合的變動成本，我們證明可以在不影響系統效能的情況下顯著降低開支。

「滑雪租賃」的記憶體方法

為了解決動態快取大小調整的挑戰，我們採用了經典的滑雪租賃問題。想像您正在進行一次長度未知的滑雪之旅。每天，您都面臨一個選擇：支付少量日租費租用滑雪板，或者支付較高的預付費用購買滑雪板，之後即可免費滑雪。如果您確切知道會滑雪多少天，選擇會很容易。但如果不知道，您就需要一個演算法來最小化總支出。

同樣地，在線性彈性快取中，每筆資料都面臨著類似的困境。當資料被存取時，系統必須在兩種選擇之間做出決定：「租用」空間：將資料保留在 RAM 中，並為其佔用的記憶體支付持續成本。「購買」遺失：逐出資料以節省記憶體成本，但如果資料很快再次被需要，則會面臨「購買」成本（延遲和 I/O 懲罰）的風險。

同時，系統無法獨立最佳化每筆資料，因為快取有最大分配大小（想像一群人在滑雪勝地，而勝地只有有限數量的滑雪板可供租借）。我們的核心理論貢獻證明，我們可以將這兩個因素，逐出策略和「租賃」持續時間，分開最佳化。這種分離非常適合簡潔的實際實作。

我們可以使用滑雪租賃演算法來確定頁面存活時間 (TTL)（類似於租賃持續時間）。如果頁面在 TTL 到期前未再次被存取，它將自動被逐出。但如果快取實體已滿，傳統的逐出策略（如 LRU）就會介入管理空間。傳統線上演算法設計專注於提供最壞情況的效能保證。

對於滑雪租賃問題，經典的「損益兩平」演算法是租賃直到累積成本等於購買價格，然後再購買滑雪板。雖然這種方法（及其隨機對應物）提供了可靠的最壞情況保證，但生產工作負載大多是可預測的。像 Spanner 這種全球分散式資料庫中的資料存取通常遵循可辨識的模式，可以加以利用來做出更好的租賃決策。

測試線性彈性快取

為了確保我們的理論在現實世界中站得住腳，我們利用兩個主要來源進行了廣泛的實驗：生產工作負載：我們將系統整合到 Spanner 中。公開追蹤資料：我們針對各種公開可用的業界基準快取追蹤資料進行了測試，以確保結果並非 Google 基礎設施所特有。

生產工作負載

我們開發了一種實用演算法，根據頁面的存取模式和成本，在每次頁面請求時為快取頁面分配一個存活時間 (TTL)。由於 Spanner 每秒處理數十億次請求，這個 TTL 預測模型必須非常輕量級。我們選擇了一個淺層決策樹，可以轉換成幾行 C++ 程式碼。

生成的程式碼也易於解釋，並提供有關工作負載特性的寶貴見解。該模型考慮了資料大小、快取遺失成本（當資料不在快取中，系統需要從其他較慢的系統（如磁碟）中檢索時的成本）以及正在執行的資料庫操作類型等特徵，以預測每個頁面的最佳 TTL。

我們將彈性快取策略整合到 Spanner 的生產伺服器中數月。與標準的固定大小快取相比，結果顯著：記憶體使用量：減少了 15.5%。快取遺失：僅增加了 5.5%。總持有成本 (TCO)：減少了約 5%。關鍵在於，由於該演算法是「成本感知」的，快取遺失的小幅增加集中在從儲存中獲取成本較低的資料上，這意味著對實際 I/O 成本的影響可忽略不計，僅為 0.5%。

公開追蹤資料

我們還使用多個公開可用的快取追蹤資料評估了我們的彈性快取方法。我們使用貪婪雙尺寸頻率 (GDSF) 逐出演算法的優化實作作為固定快取大小的基準策略，GDSF 是廣為人知的 LRU 策略的推廣，允許不同大小的頁面。我們考慮了四種彈性快取變體，取決於我們使用的滑雪租賃演算法以及是否使用機器學習模型。

由於可用的公開追蹤資料沒有應用層級特徵可供訓練，我們沒有實作決策樹進行預測。相反，我們開發了一種簡單的學習策略，將每個追蹤資料分成兩半，並使用前半部分進行訓練。對於訓練追蹤資料中的每個獨立頁面，我們計算了最小化訓練追蹤資料成本的最佳 TTL。

由於快取的行為會根據快取中最初的內容而變化，一種常見的做法（稱為「暖機」）是使用快取追蹤資料的某些前綴來填充快取，但不實際測量其效能。我們使用追蹤資料後半部分一天的請求來暖機所有快取，並使用其餘部分進行測試和測量。在測試追蹤期間，如果我們遇到在訓練期間見過的頁面，我們將 TTL 設定為該頁面的最佳預先計算 TTL。否則，我們使用損益兩平或隨機策略設定 TTL。

結果

我們發現，彈性方法在各種工作負載中始終優於固定大小快取。隨著記憶體成本相對於快取遺失成本的增加，彈性快取所帶來的節省變得更加顯著。如下圖所示，彈性快取策略透過動態調整快取大小以適應工作負載，顯著降低了總成本。我們還觀察到，在可比較的大小下，彈性策略的快取遺失率遠低於固定大小策略。

結論

線性彈性快取代表了我們對雲端基礎設施思考方式的轉變。透過從靜態尖峰負載配置轉向動態、成本感知模型，我們可以建立既高效能又經濟高效的系統。我們對這些學習型滑雪租賃策略在 Spanner 工作負載上的評估表明，即使是小型、輕量級的機器學習模型，當應用於核心基礎設施時也能產生巨大的影響。隨著雲端環境繼續提供更細緻的隨用隨付資源定價，彈性策略對於任何尋求最佳化其全球足跡的大規模服務都將變得至關重要。

致謝

這項工作是與 Tamas Sarlos (Google) 和 Ravi Kumar (Google) 共同完成的，並已在 2025 年創新資料系統研究會議 (CIDR) 上發表。