多加 DeepTech深科技

今年夏天，“華為天才少年” 張霽以 201 萬元年薪入職華為，他的老師華中科技大學計算機系統結構專業博士生導師周可，也逐漸為人所知。

近日，周可告訴 DeepTech，他的另一位學生張煜，已於今年攻克了一個 儲存問題 —— 快取命中率計算難題。

相關研究論文以《OSCA：雲塊儲存系統中基於線上模型的快取分配方案》為題，發表於國際系統領域頂會 USENIX ATC 2020 上。周可表示，雖然張霽和張煜的研究方向都是儲存系統，但目前張煜的成果比張霽的更具基礎性。

本次研究中，張煜解決了雲塊儲存系統（CBS，Cloud Block Storage）中多個例項共享的快取資源管理問題。他提出了一種具有缺失率曲線（MRC，Miss-Ratio Curve）的動態快取分配線上模型 OSCA（Online-Model based Scheme for Cache Allocation）。他表示， OSCA 能在超低複雜度下，找到一個接近最優的配置方案，從而提高快取伺服器的整體效率。

張煜告訴 DeepTech，該研究的痛點主要在於：隨著雲計算的廣泛部署，雲租戶的數量正在顯著增加。為滿足不同租戶要求，雲塊儲存系統因其高可靠性、通用性、可彈性等特點，已被雲計算廠商如 AWS、Google cloud、騰訊等廣泛部署。

但是，部署雲塊儲存系統後，動輒就得服務數百萬虛擬儲存卷，要麼還得支撐百萬雲虛擬機器的穩定執行。龐大的儲存體量，讓雲塊儲存系統壓力甚大。

想要最佳化雲塊儲存系統性能，就必須得最佳化快取，而快取效能建模是最佳化快取的重要手段。不足的是，現有命中率計算方法用起來太複雜，自 1970 年 IBM 提出 Stack Processing 方法，到 2015 年 MIT 計算機博士 Carl A. Waldspurger 研發的 SHARDS 資料庫分割槽分片技術誕生以來，業界從未停止追求更好的快取命中率，然而即便目前的最優方法，也無法滿足系統的部署需求。

你可能會問，雲計算近年才興起，為何會有長達幾十年的儲存問題呢？這是因為，快取在儲存系統裡是通用部件，因此不僅雲端儲存系統存在該問題，以前的儲存系統也被此困擾。

現有方法都採用樹結構來統計資料塊歷史訪問資訊，而樹結構的搜尋複雜度已達到 O (logN)，因此當前方法的可最佳化空間比較有限。

圖 | 常見的樹結構二叉樹示意圖

在雲端儲存場景下，在一小時內，僅僅一個儲存域就會產生數十億讀寫請求。這樣的超大請求量，會給分析程式帶來巨大計算壓力。經張煜測試，用現有最佳命中率計算方法 SHARDS，去分析一天的讀寫日誌需要長達數小時。

而超大請求量在雲環境下非常常見，極端情況下更是如此，例如雙十一，很多電商後端資料請求率遠高於平常。巨大的請求量，使得已有分析方法難以實現線上分析，而這會增加使用者訪問資料延遲，進而影響使用者體驗，因此需要探索出一種新型快取命中率計算方法。

而張煜提出的動態快取分配線上模型（OSCA，Online-Model based Scheme for Cache Allocation），正是為上述痛點而生。

動態快取分配線上模型誕生

據他介紹，該模型只需透過雜湊表（Hash table，也叫散列表，是根據健值來直接進行訪問的資料結構）來統計資料塊的歷史訪問資訊，經轉化後可獲得最終命中率資訊，由於雜湊表的搜尋複雜度為 O (1)，這使得 OSCA 在計算複雜度上，擁有較大優勢。

OSCA 的核心思想有三個方面：第一，OSCA 部署了一個基於重訪問率的新型線上快取計算模型 RAR-CM（Re-Access Ratio based Cache Model），RAR-CM 可以在低複雜度下獲得不同儲存節點的快取需求；第二，在最佳化目標方面，OSCA 使用總命中流量來作為衡量快取效率的指標；第三，OSCA 採用動態規劃方法搜尋最優配置。

研究中，本著從實際中來、到實際中去的原則，張煜和團隊先研究了快取理論和資料區域性性的原理，研究後發現快取命中率與資料重用距離之間存在緊密聯絡。但是，獲取資料重用距離時，計算複雜度非常高，而當前最優方法仍具有 O (logN) 的時間複雜度，且需要對日誌資料進行離線採集和分析，這使得已有方案難以線上部署，為此他又研發出 RAR-CM 模型。

RAR-CM 模型是一種開銷極低的快取建模方法，它能透過使用重用率來獲得資料重用距離，進而轉化為命中率曲線，最後基於重用距離分佈，得出快取效能與快取空間之間的的對應函式。

相比此前模型，RAR-CM 無需離線採集和分析 IO 日誌資料，就能實現複雜度為 O (1) 的線上快取模型的建立。它還能在保證計算準確性的前提下，有效降低計算複雜度，進而達到線上計算的目的。

在研究過程中，張煜花費數月時間，對 RAR-CM 進行模型最佳化和引數調整，最終使其精度可以達到現網需求。除錯期間，他還基於真實商用雲資料中心的讀寫日誌資料，驗證了計算模型的有效性。從雲塊儲存系統工作負載的實驗分析結果來看，RAR-CM 除具有較高的計算複雜度之外，其平均絕對誤差也比現有最優計算模型更低。

如下圖所示，基於 RAR-CM 的 OSCA 在快取命中率方面勝過原始分配策略，而且無需額外快取空間。

在張煜的實驗中，當使用 RAR-CM 時，每天在儲存節點中引用大約 5580 萬個唯一塊，僅佔用 0.87 GB 的儲存空間。除具備較低的記憶體資源使用率之外，RAR-CM 也無需引起額外網路流量，去進行日誌資訊傳輸，因為所有計算都在儲存伺服器節點上完成，這樣就可實現線上構建命中率曲線。

可覆蓋多行業的基礎資料儲存服務

據張煜介紹，OSCA 適用於所有涉及多個例項的共享快取場景，例如共享記憶體的多核場景、共享客戶端快取資源的多應用場景等。具體而言，尤其適用於大型雲資料中心的共享快取最佳化問題，服務物件可覆蓋電商、遊戲、金融、社交、教育、政務等諸多行業的基礎資料儲存服務。

他從真實工作負載的測試中觀察到，基於該快取計算模型。對快取分配進行最佳化，可有效提高共享快取的整體命中率，雲供應商的儲存效能可藉此得到提升，C 端使用者體驗也能有所提高。

以遊戲為例，一方面很多遊戲公司的遊戲版本都是釋出和託管在雲端儲存系統上的，更高的雲端儲存效能可以讓玩家更快的進行遊戲下載、更新等操作；另一方面，很多遊戲資料都是儲存雲資料庫中的，更高的雲端儲存效能也能縮短訪問延遲、提高遊戲體驗。

生於 1994 年的張煜，成長於湖北省宜昌當陽市，他認為自己的高考成績不算理想，正因此考入東北林業大學後，他比高中時更加努力，期間曾獲得國家獎學金和黑龍江省級三好學生等榮譽，此外還積極參與各種比賽。

2014 年，張煜讀大二時，參加了 ACM-ICPC 中國・黑龍江省第九屆大學生程式設計競賽，並獲得二等獎。2015 年大三時，其參加 Oracle 杯全國 Java 程式設計競賽並獲得一等獎。同年 11 月，獲國家勵志獎學金。

除積極參加比賽外，他還和就讀東北林大時的導師李丹，發表了數篇論文，最終他以年級第一的成績，保送至華中科技大學武漢光電國家研究中心攻讀直博。

今年 11 月，鑑於張煜的學術表現，華中科技大學武漢國家光電實驗室給予其兩萬元的國光學子獎學金。

而對於周可認為他的成績比 “華為天才少年” 張霽更具基礎性，他表示：“感謝周老師的讚許，我和張霽針對的是不同的問題，在儲存領域都具有很廣泛的應用價值，應該說各具特色。但我相信我們都是想在儲存這個領域做一些事情的。”