基于增量學(xué)習(xí)的RocksDB鍵值系統(tǒng)主動(dòng)緩存機(jī)制

駱克云，葉保留*，唐 斌，梅 峰，盧文達(dá)

（1.計(jì)算機(jī)軟件新技術(shù)國家重點(diǎn)實(shí)驗(yàn)室（南京大學(xué)），江蘇南京210023；2.國網(wǎng)浙江省電力有限公司，浙江杭州310007）

0 引言

隨著數(shù)據(jù)存儲(chǔ)量的急劇增長，在跨區(qū)域的數(shù)據(jù)中心對海量數(shù)據(jù)的組織管理越來越困難。而隨著分布式存儲(chǔ)技術(shù)的日益完善，其設(shè)計(jì)思想不斷啟發(fā)著傳統(tǒng)關(guān)系型數(shù)據(jù)庫，出現(xiàn)了諸多以RocksDB［1］作為存儲(chǔ)引擎的新型數(shù)據(jù)庫系統(tǒng)。RocksDB是一種基于日志結(jié)構(gòu)合并樹（Log-Structured Merge Tree）［1］的鍵值對存儲(chǔ)系統(tǒng)，它具有將隨機(jī)I/O轉(zhuǎn)化為順序I/O的優(yōu)點(diǎn)，可以大幅度提升數(shù)據(jù)寫入時(shí)的性能，是當(dāng)前絕大部分結(jié)構(gòu)化大數(shù)據(jù)存儲(chǔ)產(chǎn)品的首選存儲(chǔ)引擎。

然而，RocksDB 系統(tǒng)設(shè)計(jì)的場景是面向磁盤介質(zhì)的批量寫優(yōu)化，通過分層結(jié)構(gòu)實(shí)現(xiàn)批量操作，在查詢數(shù)據(jù)時(shí)，讀操作可能會(huì)在日志結(jié)構(gòu)合并樹的多個(gè)層級(jí)中發(fā)生I/O，導(dǎo)致不可避免的性能低下問題［2］。因此，如何高效地降低磁盤I/O 訪問次數(shù)，成為優(yōu)化讀性能研究中的一個(gè)關(guān)鍵問題。為了提升RocksDB 中的查詢效率，現(xiàn)有的系統(tǒng)設(shè)計(jì)大多從過濾器的角度出發(fā)，通過計(jì)算的方式減少不必要的I/O 訪問次數(shù)，如采用布隆過濾器（Bloom Filter）技術(shù)過濾那些數(shù)據(jù)一定不存在于磁盤上的請求［3］，實(shí)現(xiàn)讀取性能的提升。除此之外，現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)中的緩存機(jī)制也在讀取性能優(yōu)化中發(fā)揮著重要作用，通過盡可能地在內(nèi)存或閃存中訪問數(shù)據(jù)，減少磁盤尋道的時(shí)間，獲得更好的查詢性能。RocksDB 中的緩存機(jī)制主要有內(nèi)部精心設(shè)計(jì)的塊緩存和操作系統(tǒng)的通用頁緩存，適當(dāng)提升緩存大小能極大地提升整體的讀取性能。

從上面兩種優(yōu)化機(jī)制來看，提升過濾器和緩存效率的核心在于使用概率計(jì)算或高速設(shè)備的方式避免磁盤I/O訪問，過濾器的位數(shù)越大，緩存的空間越多，效果越好。但這兩方面的優(yōu)化均需要大量的內(nèi)存空間，通常內(nèi)存價(jià)格比磁盤昂貴，所以并不能無限制地通過上述機(jī)制來提升查詢效率。因此，RocksDB 雖然具有顯著的寫優(yōu)勢，但這些存在的問題也制約了其進(jìn)一步應(yīng)用。為了實(shí)現(xiàn)寫操作、空間占用和讀取性能之間開銷權(quán)衡，現(xiàn)有的工作集中于如何在特定的場景中達(dá)到最佳的配置。在理論指導(dǎo)部分，Dayan 等［4］提出的Monkey 系統(tǒng)對查詢、更新和內(nèi)存占用三者中的最優(yōu)平衡點(diǎn)進(jìn)行建模，對每一層的布隆過濾器根據(jù)數(shù)據(jù)的規(guī)模差異分配不同的存儲(chǔ)空間，達(dá)到最小化所有層的布隆過濾器誤報(bào)率，同時(shí)顯著降低內(nèi)存占用的效果。對于空間和性能的折中，Dayan 等［5］的Dostoevsky 系統(tǒng)進(jìn)一步探索了不同的合并策略對不同操作的I/O 和空間占用的影響，并使用了一種惰性合并的方法同時(shí)為不同層的布隆過濾器配置不同大小的內(nèi)存，從而在不顯著增加內(nèi)存占用的情況下提升整體性能。

上述解決方案都是從結(jié)構(gòu)設(shè)計(jì)的角度來解決RocksDB 中的性能問題，此外也有一些工作從數(shù)據(jù)分布和訪問模式的角度來解決這個(gè)問題。例如在Hadoop 分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）［6］中，為了容錯(cuò)，通常使用多個(gè)副本，但多個(gè)副本會(huì)增加系統(tǒng)的存儲(chǔ)開銷，在增加并行度的同時(shí)也增加了空間占用，在熱點(diǎn)讀寫的場景中，很多文件并沒有發(fā)生I/O，因此無法體現(xiàn)多副本的優(yōu)勢。針對這種默認(rèn)配置不靈活的問題，Bui 等［7］提出了根據(jù)HDFS 數(shù)據(jù)塊的訪問頻率動(dòng)態(tài)設(shè)置副本數(shù)加以解決。具體操作是使用高斯過程回歸及其優(yōu)化技術(shù)對文件訪問塊的可能性進(jìn)行預(yù)測：對于熱點(diǎn)塊使用多個(gè)副本，通過數(shù)據(jù)并行加快處理速度；對于冷數(shù)據(jù)塊則只用一個(gè)副本，減少空間占用，提升Hadoop 系統(tǒng)的整體數(shù)據(jù)處理性能。

在數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)分布和訪問模式對數(shù)據(jù)庫性能的影響極大，例如在RocksDB鍵值系統(tǒng)中，順序讀的性能通常比隨機(jī)讀要高出一倍，因此對特定工作負(fù)載進(jìn)行針對性優(yōu)化可以獲得可觀的性能收益。然而，在RocksDB 中進(jìn)行熱點(diǎn)數(shù)據(jù)主動(dòng)緩存會(huì)面臨兩個(gè)挑戰(zhàn)：一是系統(tǒng)在實(shí)際運(yùn)行時(shí)，數(shù)據(jù)分布會(huì)持續(xù)動(dòng)態(tài)變化，導(dǎo)致熱點(diǎn)數(shù)據(jù)難以準(zhǔn)確建模；二是如何將主動(dòng)緩存機(jī)制與RocksDB 存儲(chǔ)結(jié)構(gòu)對接起來，在盡可能不增添內(nèi)存占用的情況下實(shí)現(xiàn)性能的提升［8-9］。

針對上述挑戰(zhàn)，本文以擬合熱點(diǎn)數(shù)據(jù)分布為思路，設(shè)計(jì)并實(shí)現(xiàn)了利用增量學(xué)習(xí)進(jìn)行預(yù)測分析的熱點(diǎn)數(shù)據(jù)主動(dòng)緩存機(jī)制。具體而言，本文設(shè)計(jì)了由數(shù)據(jù)采集、系統(tǒng)交互、系統(tǒng)測試等部分組成的基于熱點(diǎn)數(shù)據(jù)預(yù)測分析的主動(dòng)緩存框架，用于與RocksDB 存儲(chǔ)引擎進(jìn)行交互，使得熱點(diǎn)數(shù)據(jù)大部分存在于日志結(jié)構(gòu)合并樹靠近內(nèi)存等高速設(shè)備的層級(jí)中；并對數(shù)據(jù)訪問模式進(jìn)行建模，設(shè)計(jì)并實(shí)現(xiàn)了基于增量學(xué)習(xí)的熱點(diǎn)數(shù)據(jù)預(yù)測分析方法，能夠有效減少存儲(chǔ)介質(zhì)的I/O訪問次數(shù)。實(shí)驗(yàn)結(jié)果表明該機(jī)制能有效提升不同動(dòng)態(tài)工作負(fù)載下的數(shù)據(jù)讀取性能。

1 RocksDB鍵值系統(tǒng)

1.1 RocksDB基本原理

RocksDB 是日志結(jié)構(gòu)合并樹的一個(gè)經(jīng)典實(shí)現(xiàn)，由Facebook 在參考谷歌的LevelDB［10］和Apache 的HBase［11］基礎(chǔ)上開發(fā)而來，復(fù)用LevelDB 的大部分代碼，在此基礎(chǔ)上進(jìn)行工業(yè)級(jí)的代碼優(yōu)化和功能增強(qiáng)，在實(shí)際生產(chǎn)中已經(jīng)應(yīng)用在了數(shù)據(jù)庫系統(tǒng)、分布式文件系統(tǒng)以及區(qū)塊鏈系統(tǒng)中［9］。

日志結(jié)構(gòu)合并樹是一種按照邏輯分層的有序存儲(chǔ)結(jié)構(gòu)，保存在內(nèi)存中的部件稱為Memtable（C0），其數(shù)目和大小可以分別通過max_write_buffer_number（默認(rèn)為2）、write_buffer_size（默認(rèn)為64 MB）設(shè)置，數(shù)據(jù)先寫入Memtable 中，當(dāng)大小達(dá)到上限后變?yōu)橹蛔x的Immutable Memtable，并使用新的Memtable繼續(xù)寫入，當(dāng)總的Memtable 數(shù)目達(dá)到上限時(shí)則觸發(fā)刷盤操作，將Immutable Memtable 數(shù)據(jù)直接寫入磁盤；保存在磁盤上的部件稱為SSTable，其中SSTable 在邏輯上又分為L0(C1)層、L1(C2)層等。通常下一層的數(shù)據(jù)量是上一層的k（默認(rèn)為10）倍，整體呈現(xiàn)出一個(gè)金字塔結(jié)構(gòu)。具體結(jié)構(gòu)示意圖如圖1所示。

圖1 日志結(jié)構(gòu)合并樹示意圖Fig.1 Schematic diagram of log-structured merge tree

日志結(jié)構(gòu)合并樹在維護(hù)有序結(jié)構(gòu)的過程中主要涉及到刷盤（Flush）和合并（Compaction）兩大操作，其中刷盤操作在內(nèi)存中的Memtable 個(gè)數(shù)超過設(shè)定的閾值時(shí)自動(dòng)觸發(fā)，而當(dāng)層級(jí)內(nèi)的總數(shù)據(jù)量超過閾值時(shí)自動(dòng)觸發(fā)合并操作。其原理如圖1所示，刷盤操作直接將Immutable Memtable 寫入到C1層（以L標(biāo)記為L0層），形成多個(gè)SSTable文件。這些SSTable內(nèi)部是有序的，但SSTable 之間存在一定的范圍重合。合并操作（Compaction）具體實(shí)施的方式與采用的合并策略有關(guān)，以默認(rèn)的Level Style 合并策略為例，選擇C2和C3層中鍵有重疊的SStable 進(jìn)行合并，生成新的SSTable 存放到C3層中，C1層以后的SSTable(L1，L2，…)每層的每個(gè)SSTable 鍵區(qū)間是不重疊的，這與C1層不同。

1.2 RocksDB數(shù)據(jù)讀取流程

RocksDB 中的讀取操作根據(jù)數(shù)據(jù)的版本差異分為當(dāng)前讀和快照讀［12］，默認(rèn)為當(dāng)前讀，整體的讀取步驟如下：

1）在事務(wù)對應(yīng)的writebatch 中查找是否存在請求的數(shù)據(jù)。

2）在Memtable中基于跳躍表快速查找數(shù)據(jù)是否存在。

3）在L0層級(jí)中，依次遍歷每個(gè)SSTable，若SSTable 的索引和布隆過濾器數(shù)據(jù)未被加載到操作系統(tǒng)的頁內(nèi)存中，則首先進(jìn)行SSTable句柄的緩存，然后通過布隆過濾器確定鍵是否存在，若存在則檢查數(shù)據(jù)是否存在于Block Cache，若不存在發(fā)生一次I/O，并緩存至Block Cache。

4）若L0層中未查找到數(shù)據(jù)，則在L1、L2等層中接著查找。由于數(shù)據(jù)在這些層中是嚴(yán)格有序的，因此使用二分查找的技巧，根據(jù)鍵的范圍定位SSTable，然后進(jìn)行步驟3）中的查找流程。

從上面的流程來看，RocksDB 讀取數(shù)據(jù)時(shí)會(huì)在多個(gè)層級(jí)中發(fā)生I/O，極端情況下的I/O 次數(shù)為N(L0)+N(L)-1，即與L0的文件數(shù)目、日志結(jié)構(gòu)合并樹的層級(jí)數(shù)之和相關(guān)。這種分層結(jié)構(gòu)意味著若要提升讀取性能，則必須通過一些機(jī)制避免訪問磁盤I/O?，F(xiàn)有系統(tǒng)中的優(yōu)化機(jī)制主要有布隆過濾器和緩存兩類，其中布隆過濾器方法可以快速判斷鍵是否一定不存在于SSTable 中，當(dāng)訪問不存在于數(shù)據(jù)庫系統(tǒng)中的鍵時(shí)，能有效減少I/O 次數(shù)。布隆過濾器在打開SSTable文件時(shí)通常被載入到操作系統(tǒng)的堆內(nèi)存中，除非通過配置BlockBasedTableOptions：：cache_index_and_filter_blocks=true主動(dòng)進(jìn)行緩存，否則當(dāng)關(guān)閉SSTable 文件時(shí)，系統(tǒng)根據(jù)max_open_files 參數(shù)所定義的文件句柄緩存數(shù)目決定是否對緩存數(shù)據(jù)進(jìn)行垃圾回收。布隆過濾器的緩存位置有兩處：OS Cache［13］（Page Cache，頁緩存，數(shù)據(jù)有壓縮）和Block Cache［14］（塊緩存，數(shù)據(jù)無壓縮），這兩種緩存的詳情如下：

OS Cache：普通的堆內(nèi)存，在Linux 系統(tǒng)中一般是Page Cache，對于每個(gè)文件的第一個(gè)讀請求，系統(tǒng)進(jìn)行預(yù)讀，即會(huì)同步讀取請求的頁面及其后面的幾個(gè)文件，對于第二次讀取，如果所讀頁面不在Cache 中，則繼續(xù)同步讀取，否則請求命中，擴(kuò)大此次預(yù)讀的范圍。最新進(jìn)入的數(shù)據(jù)存儲(chǔ)在鏈表的頭部，當(dāng)內(nèi)存不夠時(shí)進(jìn)行緩存的替換，從尾部掃描回收不活躍的內(nèi)容。在RocksDB 中，處于OS Cache 的數(shù)據(jù)是壓縮過的，因此比Block Cache 節(jié)省空間，但代價(jià)是需要CPU 的參與進(jìn)行數(shù)據(jù)的解壓。

Block Cache：它是RocksDB 緩存數(shù)據(jù)至內(nèi)存中以提高讀取性能的一種方法，用戶通過創(chuàng)建指定存儲(chǔ)大小的Cache 對象供數(shù)據(jù)庫中同一個(gè)進(jìn)程中的多個(gè)實(shí)例使用。Block Cache內(nèi)部存儲(chǔ)的數(shù)據(jù)通常是非壓縮的數(shù)據(jù)塊，也可以存儲(chǔ)壓縮的數(shù)據(jù)塊。如果開啟Direct IO參數(shù)，則沒有OS Cache產(chǎn)生，此時(shí)數(shù)據(jù)以壓縮的形式存在。在系統(tǒng)實(shí)現(xiàn)中根據(jù)緩存的替換算法來分主要有LRU Cache 和Clock Cache 兩大類，這兩種實(shí)現(xiàn)為了方便鎖的控制都將Cache 分片，用戶設(shè)置的容量會(huì)平均分配至每個(gè)分片中，默認(rèn)的Cache 分片數(shù)為64，每塊大小至少512 KB。Block Cache 中存儲(chǔ)的通常是數(shù)據(jù)塊，索引和布隆過濾器緩存在block cache的外部堆內(nèi)存中。這是因?yàn)楫?dāng)數(shù)據(jù)很大時(shí)，索引和布隆過濾器會(huì)占用大量的空間，以10 bit 的布隆過濾器為例，其占用的空間大小是number_of_keys×10 bit，即對于一個(gè)256 MB 的SSTable 文件，索引和布隆過濾器分別需要額外占用0.5 MB 和5 MB 的空間，當(dāng)數(shù)據(jù)規(guī)模較大時(shí)會(huì)占據(jù)Block Cache 的大部分乃至全部空間，由于排擠效應(yīng)導(dǎo)致嚴(yán)重的數(shù)據(jù)命中率缺失問題。

具體體現(xiàn)到RocksDB 鍵值對存儲(chǔ)系統(tǒng)中，在cache_index_and_filter_blocks 設(shè)置為false 的條件下，當(dāng)max_open_files 設(shè)置為-1時(shí)，默認(rèn)會(huì)緩存所有數(shù)據(jù)至OS Cache中，這在一些內(nèi)存空間有限的機(jī)器中特別容易造成內(nèi)存不足（Out Of Memory，OOM）問題，解決的機(jī)制就是根據(jù)內(nèi)存使用情況控制打開的文件數(shù)，及時(shí)清除緩存句柄，保持系統(tǒng)資源的合理占用。當(dāng)cache_index_and_filter_blocks 設(shè)置為true 時(shí)，則布隆過濾器數(shù)據(jù)存儲(chǔ)在block cache中，為了避免性能下降，通常的解決方案是設(shè)置cache_index_and_filter_blocks_with_high_priority 的優(yōu)先級(jí)，此時(shí)布隆過濾器和數(shù)據(jù)緩存分別位于block cache 的兩端，根據(jù)兩者實(shí)際占用內(nèi)存數(shù)動(dòng)態(tài)移動(dòng)。另一個(gè)優(yōu)化點(diǎn)就是設(shè)置pin_l0_filter_and_index_blocks_in_cache來固定第0 層的索引和布隆過濾器數(shù)據(jù)至block cache 中，在內(nèi)存占用和布隆過濾器命中率之間取得一個(gè)較好的平衡。

由上面介紹可知，過濾器機(jī)制和緩存機(jī)制［15］是相輔相成的，過濾器數(shù)據(jù)在SSTale創(chuàng)建的時(shí)候生成，在調(diào)用時(shí)緩存在內(nèi)存中，而熱點(diǎn)數(shù)據(jù)也需要緩存，因而內(nèi)存空間是瓶頸。具體分析，過濾器機(jī)制可以直接減少I/O 次數(shù)，在RocksDB 中是必不可少的，因而優(yōu)化的重點(diǎn)在于緩存機(jī)制。在查詢數(shù)據(jù)時(shí)，通過緩存機(jī)制，一方面可以減少磁盤I/O，提高讀取效率，在另一方面同時(shí)也增加了內(nèi)存占用，這是一種典型的利用空間占用提升讀取性能的折中思想。如果合理地使用緩存機(jī)制，在盡量不增加空間占用的情況下，實(shí)現(xiàn)RocksDB讀取性能的提升，那么將具有優(yōu)良的性價(jià)比。

2 熱點(diǎn)數(shù)據(jù)主動(dòng)緩存問題描述與解決思路

2.1 問題描述

本文將熱點(diǎn)數(shù)據(jù)的主動(dòng)緩存這一概念定義如下：在基于多個(gè)數(shù)據(jù)分布的查詢工作負(fù)載中，通過某種機(jī)制將熱點(diǎn)鍵值對主動(dòng)緩存到內(nèi)存或低層的SSTable中，同時(shí)求解一定時(shí)間內(nèi)的熱點(diǎn)鍵值對，從而提高整個(gè)工作負(fù)載的讀取性能。

在不考慮數(shù)據(jù)分布的情況下，該問題解是一個(gè)典型的緩存控制問題。對于此問題，傳統(tǒng)啟發(fā)式算法的做法為先創(chuàng)建緩存空間，編寫最近訪問的鍵值對，在空間滿時(shí)使用消除算法，如最近最少使用（Least Recently Used，LRU）算法，替換一些已存儲(chǔ)數(shù)據(jù)。如果考慮數(shù)據(jù)分布背景，在概率密度分布為p的情況下，求解目標(biāo)可以理解為對集合進(jìn)行多次采樣操作，求下一個(gè)周期內(nèi)訪問之前采樣得到的數(shù)據(jù)的概率。

本文利用概率分布信息獲取數(shù)據(jù)的訪問特性，預(yù)測這些數(shù)據(jù)被再次訪問的概率，然后篩選出概率較高的密鑰，并進(jìn)行主動(dòng)緩存。這其中主要有兩個(gè)難點(diǎn)：一是預(yù)測模型的選擇，二是活動(dòng)緩存機(jī)制的建立。下面將簡要介紹這兩點(diǎn)：

首先，對于預(yù)測模型選擇問題，由于在通常情況下，數(shù)據(jù)訪問的概率遵循80/20 定律，即20%的數(shù)據(jù)占據(jù)了80%的訪問頻率［8］，所以訪問的這些數(shù)據(jù)具有明顯的相關(guān)性特征。由此我們認(rèn)為，熱點(diǎn)數(shù)據(jù)預(yù)測的主要難點(diǎn)是數(shù)據(jù)范圍會(huì)隨著數(shù)據(jù)的不斷插入和刪除而動(dòng)態(tài)變化，與此同時(shí)數(shù)據(jù)形式也呈現(xiàn)出復(fù)雜多樣性。這種不確定性和不規(guī)則性意味著，在預(yù)測新數(shù)據(jù)時(shí)，很難直接使用預(yù)先訓(xùn)練好的模型進(jìn)行實(shí)時(shí)在線預(yù)測。

第二個(gè)難點(diǎn)是有關(guān)主動(dòng)緩存機(jī)制建立的問題，即活動(dòng)緩存如何適應(yīng)鍵值對存儲(chǔ)結(jié)構(gòu)。在鍵值對存儲(chǔ)場景中，查詢操作涉及到的數(shù)據(jù)量會(huì)非常大，如果使用特定的內(nèi)存緩存結(jié)構(gòu)（如Redis、Memcached），當(dāng)空間設(shè)置得過小時(shí)，就會(huì)導(dǎo)致系統(tǒng)頻繁的更新，從而不可避免地帶來需要較大容量空間的問題，這樣做就失去了優(yōu)化的意義。因此，我們迫切需要一種新的緩存機(jī)制，在不占用大量額外空間的情況下實(shí)現(xiàn)與鍵值對存儲(chǔ)系統(tǒng)的無縫對接。

2.2 解決思路

對于熱點(diǎn)預(yù)測問題，考慮到在短期內(nèi)整個(gè)系統(tǒng)環(huán)境是相對穩(wěn)定的，所以在一個(gè)穩(wěn)定的時(shí)間段里，可使用參數(shù)模型近似擬合這種方法。隨著時(shí)間跨度增長，數(shù)據(jù)分布發(fā)生變化后，模型性能會(huì)不可避免地顯著下降，此時(shí)就需要執(zhí)行在線更新模型的操作，因此整個(gè)過程可以被視為一個(gè)增量學(xué)習(xí)［16］的過程。

與傳統(tǒng)的批量學(xué)習(xí)技術(shù)相比，增量學(xué)習(xí)主要具有現(xiàn)有模型總結(jié)歷史數(shù)據(jù)隱藏規(guī)律的優(yōu)點(diǎn)，這就帶來了無需顯式保存歷史數(shù)據(jù)、減少存儲(chǔ)空間的好處。此外由于新的訓(xùn)練是基于歷史數(shù)據(jù)中的隱含信息，所以能顯著減少新數(shù)據(jù)的訓(xùn)練時(shí)間。就現(xiàn)有的增量學(xué)習(xí)實(shí)現(xiàn)技術(shù)而言，基于參數(shù)的模型（包括感知器和邏輯回歸），通?？梢院芎玫赝瓿蛇@一任務(wù)。該技術(shù)的核心是通過隨機(jī)梯度下降優(yōu)化算法實(shí)現(xiàn)參數(shù)的增量更新。定義整個(gè)模型的輸入是一組特征，輸出為該鍵是熱點(diǎn)的概率，最后，根據(jù)輸出概率對模型進(jìn)行排序，選擇概率較高的密鑰對進(jìn)行主動(dòng)緩存，同時(shí)定期驗(yàn)證模型的準(zhǔn)確性，當(dāng)精度低于閾值時(shí)進(jìn)行增量學(xué)習(xí)。

對于主動(dòng)緩存，涉及到的機(jī)制有數(shù)據(jù)的重放操作（Splaying）和布隆過濾器等，一旦數(shù)據(jù)重放足夠準(zhǔn)確，布隆過濾器的使用就能自然減少，內(nèi)存的使用也會(huì)隨之減少，從而帶來性能的提升。下面將詳細(xì)介紹RocksDB 特有的重放操作機(jī)制［17］：

日志結(jié)構(gòu)合并樹的一個(gè)特性是，頂部的數(shù)據(jù)總是比底部的數(shù)據(jù)更新，因此可以將頻繁訪問的數(shù)據(jù)“調(diào)度”到內(nèi)存中，即重復(fù)寫入，確保熱點(diǎn)優(yōu)先。在實(shí)踐中，有很多方法可以確定一個(gè)鍵是否應(yīng)該重播。在文獻(xiàn)［17］中引入了兩種重放策略，稱之為AlwaysSplay和FlexSplay。

AlwaysSplay：這種策略的一個(gè)結(jié)果是，系統(tǒng)根本無法區(qū)分真實(shí)的頻繁數(shù)據(jù)和熱數(shù)據(jù)。如果鍵在很長一段時(shí)間內(nèi)只有一次讀取，則根本不需要寫入，因此它不是最優(yōu)的。這種方法帶來的另一個(gè)問題是，系統(tǒng)可以創(chuàng)建同一個(gè)鍵的多個(gè)副本，從而造成不必要的空間浪費(fèi)，降低查詢性能。并且，當(dāng)工作負(fù)載中的讀寫比發(fā)生更改時(shí)，這些熱點(diǎn)將不會(huì)帶來任何作用，造成更大的浪費(fèi)。

FlexSplay：為了解決上述策略帶來的問題，本文引入了彈性回放策略。此策略與原始的AlwaysSplay 策略相同：put 操作都是在get操作之后觸發(fā)，但這些冗余的鍵值對被標(biāo)記為重放過（通常將普通鍵分別標(biāo)記為value、delete、merge、write、delete 和modify）。在每次數(shù)據(jù)刪除或合并期間，我們使用某種運(yùn)行時(shí)策略來確定重新傳遞的數(shù)據(jù)是執(zhí)行刪除操作還是執(zhí)行保留操作。所以，現(xiàn)在的問題變成了如何設(shè)計(jì)一種策略，以確保保留或刪除副本的成本最小化、效益最大化和實(shí)現(xiàn)最簡化。當(dāng)頻繁訪問密鑰集的比例超過閾值時(shí)，或者讀操作的比例降低時(shí)，逐步刪除重播數(shù)據(jù)，從而顯示出自適應(yīng)性。但該方法會(huì)涉及存儲(chǔ)結(jié)構(gòu)的修改，因此總體復(fù)雜度較高。

綜合考慮上面兩方面解決思路，本文提出的解決方案是：使用增量學(xué)習(xí)方法預(yù)測熱點(diǎn)鍵，對這些熱點(diǎn)鍵進(jìn)行直接重放操作，同時(shí)依據(jù)熱點(diǎn)鍵的分布區(qū)間動(dòng)態(tài)調(diào)整max_open_files 的大小，實(shí)現(xiàn)對內(nèi)存占用量的精細(xì)控制等目標(biāo)。

3 主動(dòng)緩存框架設(shè)計(jì)

如圖2 所示，整個(gè)框架包括數(shù)據(jù)采集、系統(tǒng)交互和系統(tǒng)測試三大模塊，以客戶機(jī)-服務(wù)器的形式進(jìn)行設(shè)計(jì)，同時(shí)還建立了熱點(diǎn)預(yù)測模型。

下面將分別介紹每個(gè)模塊的功能和設(shè)計(jì)情況。

圖2 基于預(yù)測分析的主動(dòng)緩存框架Fig.2 Prediction and analysis based proactive caching framework

3.1 數(shù)據(jù)采集

在熱點(diǎn)預(yù)測場景中，如果所有的數(shù)據(jù)都是間隔讀取的，那么就會(huì)產(chǎn)生大量對模型沒有影響的冗余鍵，這將極大地增加系統(tǒng)的負(fù)擔(dān)。因此，在此模型中將直接忽略這些數(shù)據(jù)的讀取行為，改為主要考慮以下數(shù)據(jù)：

1）頻率統(tǒng)計(jì)：每個(gè)工作負(fù)載的主要記錄是讀操作下的鍵數(shù)。具體來說，每次執(zhí)行g(shù)et操作時(shí)，在訪問命中時(shí)，都會(huì)記錄操作的key和key的計(jì)數(shù)。具體數(shù)據(jù)格式為＜key，count＞。

2）分布統(tǒng)計(jì)：在每個(gè)工作負(fù)載啟動(dòng)前記錄SSTable元數(shù)據(jù)信息，包括時(shí)間戳、層次結(jié)構(gòu)、SSTable文件名、最小鍵、最大鍵等，數(shù)據(jù)格式為＜timestamp，Level，SSTable，key_min，key_max＞。

3）工作負(fù)載信息：記錄每個(gè)工作負(fù)載數(shù)據(jù)信息，包括工作負(fù)載標(biāo)簽號(hào)、開始時(shí)間、結(jié)束時(shí)間、持續(xù)時(shí)間間隔、讀取次數(shù)、總間隔、每秒查詢、索引和布隆過濾器內(nèi)存占用、Memtable內(nèi)存占用和進(jìn)程內(nèi)存占用量等。

為了避免人為干擾，重放期間的讀和寫操作不被包括在統(tǒng)計(jì)數(shù)據(jù)中。

數(shù)據(jù)采集完畢后，將對數(shù)據(jù)特征進(jìn)行進(jìn)一步的構(gòu)造。在這個(gè)步驟中，輸入數(shù)據(jù)被處理成模型可以讀取的形式。方法是將兩種頻率統(tǒng)計(jì)表和分布統(tǒng)計(jì)表的統(tǒng)計(jì)量進(jìn)行匯總，并對其進(jìn)行標(biāo)記，構(gòu)造正樣本和負(fù)樣本。以key 為主鍵，構(gòu)造特征目前包括：時(shí)間窗內(nèi)的累計(jì)訪問頻率、SSTable 的命中率、SSTable區(qū)間內(nèi)key的訪問比例、key的層次結(jié)構(gòu)等。系統(tǒng)將上述特性拼接到一行記錄中，并在一段時(shí)間后計(jì)算數(shù)據(jù)命中率；同時(shí)還會(huì)執(zhí)行對標(biāo)簽標(biāo)注的工作，例如再次訪問的鍵被標(biāo)記為1，否則被標(biāo)記為0。

3.2 系統(tǒng)交互

該系統(tǒng)的通信體系結(jié)構(gòu)為客戶機(jī)-服務(wù)器模式。RocksDB 數(shù)據(jù)庫實(shí)例充當(dāng)客戶機(jī)，向模型服務(wù)器請求模型服務(wù)。這兩個(gè)角色所提供的功能分別為：

1）RocksDB 數(shù)據(jù)庫實(shí)例：讀寫數(shù)據(jù)，向服務(wù)器發(fā)送任務(wù)請求，獲取服務(wù)器端狀態(tài)，獲取熱點(diǎn)鍵集合，通過max_open_files設(shè)置打開的SSTable文件數(shù)。

2）模型服務(wù)：提供模型服務(wù)，包括加載/培訓(xùn)模型、評估結(jié)果、熱鍵預(yù)測、提供max_open_files設(shè)置等。

該模型被設(shè)計(jì)為一個(gè)帶有Thread 類線程的類ModelServer。它作為守護(hù)線程在后臺(tái)運(yùn)行，同時(shí)整個(gè)系統(tǒng)的設(shè)計(jì)風(fēng)格是Restful 的。flask-Restful 輕量級(jí)框架用于封裝模型服務(wù)器的功能。其中涉及到的路由如表1所示。

RocksDB 數(shù)據(jù)庫實(shí)例與模型服務(wù)器的交互模式如圖3所示。

表1 主動(dòng)緩存服務(wù)器端Rest路由Tab.1 Rest routing on server side with proactive caching

圖3 主動(dòng)緩存系統(tǒng)時(shí)序圖Fig.3 Sequence diagram of proactive caching system

3.3 系統(tǒng)測試

該模塊負(fù)責(zé)模擬數(shù)據(jù)工作負(fù)載的生成和組成操作。由于生成的數(shù)據(jù)需要反映數(shù)據(jù)的分布特征，所以主要考慮在文件訪問模式下幾種典型的分布［18］：

1）正態(tài)分布：此分布由均值和標(biāo)準(zhǔn)差決定。概率密度曲線以均值為中線，形狀由標(biāo)準(zhǔn)差決定。標(biāo)準(zhǔn)差越小，曲線越接近均值。該系統(tǒng)計(jì)算給定數(shù)據(jù)區(qū)間的均值，并根據(jù)三標(biāo)準(zhǔn)差原理確定標(biāo)準(zhǔn)差。

2）均勻分布：該分布由最小值和最大值決定，概率密度是固定的。為了簡化系統(tǒng)測試，將直接選取具有特定后綴的數(shù)據(jù)進(jìn)行采樣分析。

3）Zipf 分布：在Zipf 分布P(r)=C/rα中，將事件發(fā)生概率與其頻率排序優(yōu)先級(jí)之間的關(guān)系視為反比，其中：C 為常數(shù)，r為根據(jù)發(fā)生頻率排序，α 為參數(shù)。在系統(tǒng)測試中，首先生成一個(gè)固定容量的累積概率數(shù)組，然后根據(jù)生成的隨機(jī)數(shù)遍歷數(shù)據(jù)，并取大于或等于隨機(jī)數(shù)的第一個(gè)數(shù)組下標(biāo)采樣。

為了便于比較測試結(jié)果，需要將上述數(shù)據(jù)保存到一個(gè)文件中，以便工作負(fù)載讀取。對于復(fù)合工作負(fù)載，主要從上述三種分布中抽取重復(fù)樣本，形成復(fù)雜的工作流加以測試。

4 算法設(shè)計(jì)和實(shí)驗(yàn)

4.1 算法實(shí)現(xiàn)流程

增量學(xué)習(xí)模型使用sklearn.linear_model.SGDClassifier［19］實(shí)現(xiàn)，利用joblib 庫［20］保存模型的二進(jìn)制文件，這樣做的好處是打開數(shù)據(jù)庫時(shí)若模型存在則會(huì)自動(dòng)導(dǎo)入，節(jié)省模型訓(xùn)練時(shí)間。如果數(shù)據(jù)庫中不存在現(xiàn)有模型，則需要觸發(fā)模型訓(xùn)練操作：數(shù)據(jù)庫端主動(dòng)發(fā)送請求，啟動(dòng)后臺(tái)訓(xùn)練流程。訓(xùn)練之后，數(shù)據(jù)庫客戶機(jī)可以通過輪詢獲得模型的輸出。

增量學(xué)習(xí)的一般過程可以理解為：流數(shù)據(jù)輸入→特征處理→partial_fit擬合→評價(jià)→應(yīng)用。以下將重點(diǎn)介紹模型實(shí)現(xiàn)過程中的幾個(gè)細(xì)節(jié)：

1）評估：很明顯評估模型的學(xué)習(xí)效率是個(gè)二分類問題，所以為了直接篩選出熱點(diǎn)鍵，將使用F1值度量［21］的方式。F1標(biāo)準(zhǔn)會(huì)綜合考慮精確率與召回率兩方面因素。首先，定義TP代表預(yù)測結(jié)果為1，這也代表實(shí)際為1的數(shù)目；TN為預(yù)測為0，實(shí)際也為0 的數(shù)目；FP 為預(yù)測是1，實(shí)際是0 的數(shù)目；FN 為預(yù)測是0，實(shí)際是1的數(shù)目。涉及到的各種計(jì)算公式如下所示：

精確率：

Precision=TP/(TP+FP)

召回率：

Recall=TP/(TP+FN)

F1得分是精確率與召回率的幾何平均：

F1=2*TP*FN/(TP+FN)

2）應(yīng)用：預(yù)測結(jié)果主要應(yīng)用于兩個(gè)方面，一是篩選熱鍵，二是設(shè)置max_open_files 參數(shù)，兩者具體的處理方式如下：對于熱點(diǎn)鍵的篩選，先對預(yù)測概率進(jìn)行排序，然后選取預(yù)測概率大于或等于0.5 的作為熱點(diǎn)鍵。隨后計(jì)算這些熱點(diǎn)鍵所覆蓋的SSTable 熱點(diǎn)數(shù)，選取SSTabel 覆蓋率大于100 的SSTable 熱點(diǎn)數(shù)作為SSTable 熱點(diǎn)數(shù)進(jìn)行記錄。對于max_open_files 設(shè)置，會(huì)根據(jù)經(jīng)驗(yàn)值公式Max（min（SSTable number，2×SSTable hotspot number），SSTable number/2）來設(shè) 置，其中，SSTable number 指SSTable 文件數(shù)，SSTable hotspot number 指SSTable熱點(diǎn)文件數(shù)。除此之外，還可以通過控制max_open_files 來達(dá)到控制內(nèi)存使用的目的。

整個(gè)算法系統(tǒng)的流程如圖4 所示，接下來將對圖中的部分操作細(xì)節(jié)進(jìn)行簡要介紹：

1）訓(xùn)練模型：獲取前一時(shí)間段各鍵的統(tǒng)計(jì)特征，得到當(dāng)前命中的樣本X 和y_true，然后將數(shù)據(jù)放入模型partial_fit（X，y_true）中擬合。

2）模型預(yù)測：獲取當(dāng)前各鍵統(tǒng)計(jì)特征X，調(diào)用函數(shù)predict（X）進(jìn)行預(yù)測，得到預(yù)測結(jié)果y_pred。

3）模型評估：執(zhí)行函數(shù)f1_score（y_true，y_pred），計(jì)算得到F1。

其中，是否重新訓(xùn)練的標(biāo)準(zhǔn)為F1 的下降幅度，本文中將閾值設(shè)為10%，即如果F1 的下降幅度低于此閾值就開始使用新的數(shù)據(jù)訓(xùn)練模型。

圖4 主動(dòng)緩存模型訓(xùn)練和預(yù)測流程Fig.4 Training and prediction process of proactive caching model

4.2 工作負(fù)載設(shè)計(jì)

本文的研究目標(biāo)是面向讀操作的工作負(fù)載優(yōu)化，這其中最重要的部分就是工作負(fù)載設(shè)計(jì)。

我們認(rèn)為的設(shè)計(jì)目標(biāo)具體有兩個(gè)：一個(gè)是模擬特定服務(wù)的讀取性能，在此之上研究數(shù)據(jù)的緩存行為；另一種是通過改變數(shù)據(jù)分布來測試算法在動(dòng)態(tài)環(huán)境中的適應(yīng)性。為了驗(yàn)證本文設(shè)計(jì)是否符合這兩方面的要求，設(shè)計(jì)了以下兩階段工作負(fù)載：

1）數(shù) 據(jù) 準(zhǔn) 備：啟 動(dòng)RocksDB，通 過 調(diào) 用“rocksdb：：NewLRUCache（4×1024*1024*1024LL）”配 置block cache 為4 GB。鍵是長度為8 的十六進(jìn)制字符串，值是長度為20 的十六進(jìn)制字符串。第一階段生成范圍為0x00000000～0x04ffffff的鍵值對，數(shù)量設(shè)為5 000 萬。第二階段生成范圍為0x00000000～0x04ffffff*2 的的鍵值對，數(shù)量也為5 000 萬，并且對于重復(fù)生成的鍵，使用第二階段生成的去覆蓋第一階段生成的，可將此覆蓋視為修改操作。在數(shù)據(jù)生成完畢后，還將構(gòu)造符合以下條件的三個(gè)鍵集合用來執(zhí)行查詢操作：

①數(shù)據(jù)分布a：鍵的區(qū)間在0x00000000～0x04ffffff，執(zhí)行高斯采樣，采樣數(shù)量為500萬；

②數(shù)據(jù)分布b：鍵的區(qū)間在0x00000000～0x04ffffff，所有鍵均以4或8或f結(jié)尾；

③數(shù) 據(jù) 分 布c：構(gòu) 造 近 似Zipf 分 布 模 型（1.005，1 000 000），其中rank 定義為(x+100)/100（減小數(shù)值過大的影響）。把區(qū)間0x00000000～0x04ffffff 劃分為n（n=10）份，在每份區(qū)間內(nèi)選擇一個(gè)數(shù)作為基數(shù)，再按上述類Zipf分布采樣，采樣數(shù)量為100萬。

2）工作負(fù)載組合1：寫入第一階段的鍵值對，按順序依次以不同的數(shù)據(jù)分布a（10 次）→b（10 次）→c（4 組數(shù)據(jù)，每組5次）執(zhí)行，其中，鍵的值以時(shí)間為隨機(jī)數(shù)種子隨機(jī)采樣80%。這種設(shè)計(jì)的目的是多次運(yùn)行，模擬商業(yè)周期和數(shù)據(jù)分布的流動(dòng)。

3）工作負(fù)載組合2：編寫第二階段的鍵值對，將數(shù)據(jù)分布的上限乘以2，其余的操作與工作負(fù)載組合1相同。這是為了在更大的數(shù)據(jù)集中進(jìn)行模擬，并測試模型的遷移能力。

實(shí)驗(yàn)總共測試80 個(gè)工作負(fù)載，前40 個(gè)數(shù)據(jù)范圍大致相同。在隨機(jī)插入或修改了一半數(shù)據(jù)之后，數(shù)據(jù)分布會(huì)發(fā)生顯著變化，實(shí)驗(yàn)中將使用相同的工作負(fù)載繼續(xù)測試這種動(dòng)態(tài)適應(yīng)性。

重復(fù)使用10 次數(shù)據(jù)分布a 是為了測試對于高斯分布數(shù)據(jù)，隨機(jī)采樣其中的一部分，重復(fù)一定次數(shù)后，可以模擬輕度熱點(diǎn)讀取模式。相應(yīng)地，重復(fù)使用10次數(shù)據(jù)分布b（鍵的區(qū)間在0x00000000～0x04ffffff的以4或8或f結(jié)尾的鍵）是為了驗(yàn)證對于均勻分布的數(shù)據(jù)，如果順序采樣其中的一部分，一方面會(huì)破壞前面已有的分布模型，另一方面會(huì)導(dǎo)致模型需要進(jìn)一步的訓(xùn)練。最后，選取4組不同符合數(shù)據(jù)分布c的數(shù)據(jù)每組重復(fù)5 遍，是為了證明：這里每組的數(shù)據(jù)分布長尾特征明顯，每個(gè)讀取為重度熱點(diǎn)模式，但熱點(diǎn)會(huì)經(jīng)常變化。

實(shí)驗(yàn)記錄的數(shù)據(jù)主要有兩種類型：第一種是對系統(tǒng)狀態(tài)執(zhí)行監(jiān)測的數(shù)據(jù)，格式為＜工作負(fù)載類型，開始時(shí)間和結(jié)束時(shí)間，運(yùn)行時(shí)間和數(shù)量的查詢，每秒查詢數(shù)，索引和布隆過濾器，內(nèi)存Memtable 內(nèi)存，進(jìn)程占用內(nèi)存＞；第二種是數(shù)據(jù)估算模型，格式為＜時(shí)間，精確率，召回率，F(xiàn)1＞。第一類數(shù)據(jù)記錄在本地和調(diào)度模型中，使用它們來分析系統(tǒng)性能；第二種數(shù)據(jù)則被用于分析模型性能，它只存在于調(diào)度模型實(shí)驗(yàn)中。

4.3 實(shí)驗(yàn)性能分析

首先分析該模型的預(yù)測性能，該部分的性能由驗(yàn)證集上的測量標(biāo)準(zhǔn)F1（Precision，Recall）來測量。除了前兩個(gè)工作負(fù)載用作訓(xùn)練集和標(biāo)注標(biāo)簽，其余工作負(fù)載皆用于訓(xùn)練和預(yù)測。

接下來使用前三個(gè)工作負(fù)載作為示例進(jìn)行解釋。首先模型以工作負(fù)荷0 和1 為訓(xùn)練集，進(jìn)行模型訓(xùn)練。在0 和1 這兩個(gè)階段中預(yù)測的鍵值將會(huì)被用作熱鍵，與工作負(fù)載2 階段中實(shí)際訪問到的鍵值進(jìn)行比較。其中，工作負(fù)載2 中最上方的折線代表前兩個(gè)工作負(fù)載中被訪問到的鍵在工作負(fù)載2 中再次出現(xiàn)的比例。將召回率定義為預(yù)測的熱鍵數(shù)和訪問的熱鍵數(shù)與所有訪問的鍵數(shù)之比，準(zhǔn)確率定義為預(yù)測的熱鍵數(shù)和訪問的熱鍵數(shù)與總預(yù)測的熱鍵數(shù)之比。

如圖5 所示，這是其中一個(gè)組合的工作負(fù)載，可以看到精確率約為0.83，召回率約為0.62，F(xiàn)1 的值最大0.72。如果在此情況下突然運(yùn)行負(fù)載組合b，因?yàn)閎是均勻采樣數(shù)據(jù)，所以，查全率和查準(zhǔn)率自然會(huì)急劇下降，從而超過閾值觸發(fā)訓(xùn)練，最終F1 可以穩(wěn)定在0.58 左右。隨后將運(yùn)行工作負(fù)載組合c，此時(shí)每個(gè)數(shù)據(jù)包數(shù)據(jù)都是分離的，所以需要一些時(shí)間去改變工作狀態(tài)。如圖5 所示，模型在一段時(shí)間內(nèi)相對穩(wěn)定，這代表了模型處在學(xué)習(xí)訪問模式，并在工作負(fù)載發(fā)生顯著變化時(shí)進(jìn)行重新訓(xùn)練。第二階段的結(jié)果相似，這里不再重復(fù)。

圖5 主動(dòng)緩存模型性能折線圖Fig.5 Line chart of performance of proactive caching model

在系統(tǒng)內(nèi)存性能方面，通過跟蹤進(jìn)程占用的內(nèi)存，可以發(fā)現(xiàn)原始數(shù)據(jù)庫在其峰值時(shí)會(huì)使用7.4 GB 內(nèi)存，平均內(nèi)存消耗則為6.6 GB，活動(dòng)緩存模型在其峰值使用7.1 GB，不存在任何額外的內(nèi)存使用。因此，模型本身帶來的開銷幾乎可以忽略不計(jì)，可以認(rèn)為系統(tǒng)在內(nèi)存效率上有一定程度的提高。

就系統(tǒng)讀取性能而言，查詢測試時(shí)的吞吐量如圖6 所示：橫軸表示運(yùn)行的工作負(fù)載；左側(cè)縱軸表示每秒查詢的數(shù)量（QPS），單位為kop/s；右側(cè)縱軸表示模型QPS 相對于原始QPS改進(jìn)的百分比。

從圖6 可以發(fā)現(xiàn)，除了工作負(fù)載切換階段吞吐量有所損失外，其余階段查詢吞吐量均提高，不同工作負(fù)載的組合帶來的提升效果不盡相同，組合a 查詢性能平均提高了約9.5%，組合b 查詢性能平均提高了約6.3%，組合c 查詢性能平均提高了約6.6%。總的來說，使用該模型能夠?qū)⒖傮w性能提高了7.5%。因此，可以認(rèn)為該模型具有一定的性能優(yōu)勢。

圖6 主動(dòng)緩存模型每秒查詢數(shù)折線圖Fig.6 Line chart of number of queries per second of proactive caching model

5 結(jié)語

本文將機(jī)器學(xué)習(xí)技術(shù)應(yīng)用于RocksDB 鍵值對存儲(chǔ)系統(tǒng)中熱點(diǎn)數(shù)據(jù)的主動(dòng)緩存問題。整個(gè)系統(tǒng)不僅采用增量學(xué)習(xí)方法對熱點(diǎn)數(shù)據(jù)進(jìn)行預(yù)測，還建立了基于預(yù)測分析的主動(dòng)緩存框架。實(shí)驗(yàn)結(jié)果表明，該方法能有效提高動(dòng)態(tài)負(fù)載下的熱點(diǎn)閱讀性能。

以后，我們將針對熱點(diǎn)預(yù)測模型的復(fù)用問題作進(jìn)一步的研究，即如何將訓(xùn)練后的模型應(yīng)用于其他不同鍵值分布的存儲(chǔ)數(shù)據(jù)庫問題。