吳 剛，阿卜杜熱西提·熱合曼，李 梁，喬百友，韓東紅

1.東北大學 計算機科學與工程學院，沈陽 110819

2.南京大學 計算機軟件新技術國家重點實驗室，南京 210093

1 引言

近年來，隨著互聯網技術的快速發(fā)展，越來越多的網絡應用需要能夠支持大量用戶的并發(fā)訪問以及高吞吐量和低延時等特性。傳統(tǒng)的磁盤數據庫由于將所有數據放在磁盤上進行管理，慢速的磁盤I/O限制了數據庫的性能。而內存數據庫的數據存儲與管理都在內存中進行，因此綜合性能有了很大的提升，特別適合此類對性能要求極高的場合[1-4]。

為了保證數據庫的完整性，內存數據庫通常使用日志結合檢查點的故障恢復機制[5-6]。日志記錄方面，ARIES類日志[7]和命令日志[8]為兩大日志記錄方式。其中，命令日志是專門為內存數據庫而設計的粗粒度、輕量級的日志記錄方式。它的優(yōu)點是產生的日志小，I/O開銷低。因此這種日志記錄方式非常適合內存數據庫。

但是，由于命令日志記錄的事務之間存在復雜的依賴關系，故障發(fā)生后無法直接進行并行恢復[9]，很難發(fā)揮好多核處理器的并行處理性能，恢復速度較慢。針對該情況，現有的解決辦法是，在開始恢復之前，先分析日志記錄中事務之間的依賴關系，并求出最優(yōu)的并行執(zhí)行計劃，再開始并行恢復[10]。顯然這樣可以加快命令日志的恢復速度。但是，這需要在恢復之前遍歷一遍日志內容。由于內存數據庫的吞吐量很高，短時間內都能產生很大的日志數據。因此，遍歷一遍日志的時間是不可忽視的。

相對于傳統(tǒng)對稱多處理器架構的多個CPU通過單一內存控制器訪問內存的體系架構，在非統(tǒng)一內存訪問（non-uniform memory access，NUMA）體系架構中，內存和多核CPU分布在多個節(jié)點上，CPU通過節(jié)點間的高速鏈路可以訪問系統(tǒng)內所有節(jié)點的內存[11]。因此這種架構具有很好的可擴展性。在這種架構中，相比訪問遠端內存，CPU訪問本地內存的延遲低，帶寬高[12]。在本文的實驗部分所用NUMA體系架構的服務器中，經實驗測得，CPU訪問遠端內存的延時為251.1 ns，是訪問本地內存延時138.2 ns的1.82倍。

最近研究顯示，在NUMA體系架構上優(yōu)化的內存數據庫系統(tǒng)和內存存儲引擎中，面向數據而非面向事務的設計架構是一種主流思想[13]。面向事務的設計架構中，事務處理所需要的數據往往會分布在不同的節(jié)點[14]。在NUMA架構中使用面向數據的設計架構可以避免這種跨節(jié)點訪問數據帶來的延時。在面向數據的設計架構中，通常的做法是將內存數據庫中的每一條數據按鍵的范圍平均劃分到不同節(jié)點的內存區(qū)域中，每個節(jié)點的CPU上創(chuàng)建一個線程負責執(zhí)行本區(qū)域內數據的添加、刪除、修改、查找等操作[15]。這種策略有效地保證了各個節(jié)點所處理數據的均衡性，但忽略了數據訪問的不均衡性，即忽略了數據的熱度。

Fig.1 Framework of command log recovery algorithm based on data popularity圖1 基于數據熱度的命令日志恢復算法框架

通常情況下，數據庫中的數據的訪問符合正態(tài)分布規(guī)律。因此，一定會出現某些數據被頻繁訪問的情形。在故障恢復時這種數據劃分策略顯露出其弊端。即如果某些數據的訪問次數遠高于其他數據，在故障恢復階段負責這些數據的線程的工作負載將會加重。劃分到那些被頻繁訪問的數據的命令子隊列中的命令明顯多于其他命令子隊列。如圖1所示，命令子隊列中命令數目（藍色示意）呈現不均衡狀態(tài)。由于總的恢復時間由最后執(zhí)行完成的線程來決定，因此這種負載不均衡性顯然增加了恢復時間。

因此，從這個角度出發(fā)，為了更好地利用硬件性能，認為在NUMA體系架構上針對命令日志恢復進行優(yōu)化是很有必要的。

在本文中，針對NUMA體系架構的特性設計了NUMA體系架構下的基于熱度記錄的命令日志快速恢復算法。該算法的框架如圖1所示。

在本文算法中，加載線程首先從磁盤加載檢查點和日志數據，并將它們送入命令隊列。然后，分發(fā)命令的線程使用一定策略將命令隊列中的數據分發(fā)到各個命令子隊列中。命令子隊列的數量取決于本服務器上NUMA節(jié)點的數量。最后，執(zhí)行線程不斷地從所屬的命令子隊列中取出命令并執(zhí)行，將數據添加到所在節(jié)點的內存中。本文提出的NUMA架構上基于數據熱度的故障恢復策略在故障恢復時通過使各個執(zhí)行線程的負載比較均衡，以此來加快恢復速度。本文的主要貢獻如下：

（1）提出了基于數據操作熱度的日志和檢查點記錄方案；

（2）設計并實現了NUMA架構上基于熱度記錄的故障恢復算法。實驗表明，本文算法的恢復速度比常規(guī)劃分策略快，恢復速度最高提升了19%。

本文工作安排如下：第2章介紹具有熱度記錄的日志和檢查點記錄方案；第3章介紹故障恢復算法；第4章為實驗部分；第5章為結束語。

2 具有熱度記錄的日志和檢查點

首先提出數據熱度的定義。

定義1設D={d1,d2,…,dn}為數據記錄的集合，C={c1,c2,…,cn}為與D中一一對應的數據記錄的被訪問次數的集合，τ為閾值。如果存在cn＞τ,cn∈C，則與之對應的數據記錄dn∈D為熱數據；反之，則為冷數據。cn越大，數據dn的熱度越高。

在實驗中模擬了Key-Value型數據庫的操作過程。在本文的策略中，數據庫執(zhí)行過程中會記錄每一條數據記錄的訪問次數，并保存在一個Map結構中。在本文的算法中，日志記錄的格式如圖2（a）中所示。在日志內容中除了記錄該數據的鍵和值外，還記錄該數據的熱度。數據記錄的熱度為該數據記錄在最近一次檢查點中所記錄的操作次數。如圖3所示為數據庫執(zhí)行過程的簡易示意圖。t0為完成一次一致性檢查點的時刻。在t0至t1時間內數據庫執(zhí)行過程中，數據記錄每被訪問一次，就將該數據的操作次數自增1。在t1至t2時間內檢查點制作過程中，將該數據的被訪問次數作為該數據的熱度跟數據記錄一并傳輸到磁盤中。從t2開始到下一次檢查點之前，日志中數據熱度即為前一次檢查點時該數據的操作次數。如果某一數據是在此時間段內新增數據，則其熱度置為零，并記錄其操作次數。在t3時刻發(fā)生故障后，數據庫進入恢復階段?；謴碗A段根據熱度來劃分檢查點數據和日志數據。

在傳統(tǒng)的一致性檢查點中，只會記錄包括版本號在內的頭部信息以及該時刻數據庫中數據的內容。由于其沒有對熱數據進行特殊劃分，因此無法保證故障恢復時的工作負載均衡。在本文方案中，在檢查點中還設置兩個全局參數D和C。其中，D記錄該時刻數據庫中的數據記錄的總數，C記錄從前一次檢查點到該時刻數據庫的總的操作次數。在制作檢查點時，這些信息將被放在檢查點頭部傳輸到磁盤中。檢查點格式如圖2（b）所示。

Fig.2 Log and checkpoint with popularity record圖2 帶有熱度記錄的日志和檢查點

在本文的方案中，總的數據量D，總的操作次數C以及每一個數據條目的操作次數均使用64位無符號整數來代替。

Fig.3 Database execution process圖3 數據庫執(zhí)行過程

3 故障恢復算法

3.1 整體介紹

首先介紹命令日志恢復實驗的算法框架，如圖1所示。首先加載線程會從磁盤中加載檢查點數據到命令隊列。檢查點數據加載完畢后，向命令隊列發(fā)送一條結束指令，以表示檢查點數據加載完畢。隨后，加載線程加載命令日志數據，并將其數據追加到命令隊列。日志數據加載完畢后，加載線程同樣會發(fā)送一條結束指令到命令隊列，表示加載日志數據結束。就此，加載過程結束。

然后，分發(fā)命令的線程用熱度記錄分發(fā)策略將數據從命令隊列中取出并送入相應的命令子隊列。命令分發(fā)算法為本程序的核心算法，而且檢查點數據的分發(fā)算法與日志數據的分發(fā)算法有些不同，兩種命令分發(fā)算法以加載時的結束指令為分界。命令分發(fā)過程的流程圖如圖4所示。命令分發(fā)算法單獨做介紹。

在分發(fā)命令結束后，各個NUMA節(jié)點上的執(zhí)行命令的線程不斷地從相應命令子隊列中取出指令并執(zhí)行，將數據恢復到本地內存中，每一個執(zhí)行命令的線程為Redis進程。如此一來，數據庫恢復過程結束，數據庫恢復到了故障發(fā)生前的一致性狀態(tài)。

下面介紹檢查點數據和日志數據的命令分發(fā)算法。

3.2 檢查點數據的分發(fā)算法

由于檢查點數據具有熱度記錄，因此可以根據數據的熱度記錄采用與NUMA常規(guī)方案不同的方式分發(fā)數據。

首先，計算數據熱度的閾值τ。此處可以根據檢查點數據的頭部記錄中檢查點數據記錄的總量D和操作總次數C，以及設定的影響因子α，得到τ=(C/D)×α。則根據數據熱度的定義，操作次數大于τ的數據記錄屬于熱數據。

Fig.4 Command distribution thread flow chart圖4 命令分發(fā)線程流程圖

同時，每一個命令子隊列也會記錄該子隊列中的數據的操作總次數。如果從命令隊列中取出的數據記錄是熱數據，則動態(tài)地將其分發(fā)到當前操作總次數最少的命令子隊列，并將該熱數據的key和分發(fā)到的命令子隊列的序號i保存在為熱數據創(chuàng)建的哈希表Map中。否則，根據其key值計算出哈希值，并分發(fā)到該哈希值相應的命令子隊列中。當從命令隊列中取到結束指令時，檢查點數據分發(fā)結束。該算法如算法1所示。

算法1檢查點數據的命令分發(fā)算法

輸入：Ci，第i個線程所持有的數據在檢查點中記錄的操作次數之和；C，檢查點中存放的所有操作次數之和；D，檢查點中所存放的數據條目數量；α，影響因子；Q，命令隊列；Qi，命令子隊列；Hi，命令子隊列Qi在堆H中的位；Map，哈希表，鍵為熱數據的鍵，值為其分配的命令子隊列的序號。

輸出：命令子隊列Qi。

1.Distribute_data_in_checkpoint():

2.τ=(C/D)×α

3.whileDATA=Q.top_and_pop：

4.ifDATA.N＞τ:

5.i=min(H)

6.Map[DATA.key]=i

7.else:

8.i=hash(DATA.key)%H.size()

9.H[Hi]+=N

10.Qi.push(DATA)

3.3 日志數據的命令分發(fā)算法

加載完檢查點數據后，數據庫恢復到了故障發(fā)生前最近一次一致性檢查點完成時的狀態(tài)。檢查點數據也就是數據庫在該檢查點完成時刻的數據庫中的數據。隨后的日志為對這些數據的各種操作。日志恢復期間將所獲取到的命令日志按序執(zhí)行。此過程中，有可能會重復更新某條數據，且有可能增加新數據或刪除已有數據。

日志恢復期間的命令分發(fā)算法如算法2所示。

首先從命令隊列Q中獲取命令。命令有可能是范圍操作，如果是范圍操作，則向每一個命令子隊列發(fā)送此命令；如果不是，再判斷其是否為熱數據的訪問操作。如果是，則從哈希表Map中取其分配的命令子隊列序號i；如果不是熱數據的操作，則計算其哈希值，得到其分發(fā)的子隊列的序號i。最后將其分發(fā)到命令子隊列i中。

算法2命令日志數據的命令分發(fā)算法

輸入：Q，命令隊列；Qi，命令子隊列；Map，哈希表，鍵為熱數據的鍵，值為被分配的命令子隊列的序號。

輸出：命令子隊列Qi。

1.Distribute_data_in_log():

2.whileCMD=Q.top_and_pop():

3.ifCMDis a range command:

4.Q[every].push(CMD)

5.ifCMD.N>τ:

6.QMap[CMD.KEY].push(CMD)

7.else:

8.Qhash(CMD.KEY).push(CMD)

4 實驗及結果分析

4.1 實驗環(huán)境

實驗在內核版本為4.13.0的Ubuntu 16.04系統(tǒng)中實現NUMA架構下基于熱度的內存數據庫日志恢復算法。所用主機是配有4個NUMA節(jié)點的服務器（結構見圖5）。該服務器的詳細配置如表1所示。

Fig.5 Server structure圖5 服務器結構

Table1 Detailed server configuration information表1 服務器詳細配置信息

4.2 實驗負載參數

實驗中所用命令日志和檢查點數據另由一個程序產生，并保存在磁盤中。其中，數據記錄的鍵為64位無符號整型數組成的字符串，值為大小為512 Byte至1 024 Byte的隨機字符組成的字符串。命令日志中數據的鍵由檢查點數據中數據記錄的鍵按正態(tài)分布規(guī)律訪問而得，符合數據庫的日常訪問規(guī)律。如圖6所示，橫坐標的整數值表示數據記錄的鍵的值，數據記錄的鍵互不重復，而且相鄰兩個鍵相差為1，縱坐標表示該數據的訪問次數，訪問次數超過τ的數據為熱數據。這樣，檢查點中數據記錄的數量可理解為圖6中左右邊界A和B中整數點的數量，日志數量為這些離散點的縱坐標值之和。實驗中通過調整檢查點數據記錄的數量、命令日志數量、影響因子α以及正態(tài)分布函數的參數σ2來產生不同的實驗數據。

Fig.6 Key access rules in checkpoint data圖6 檢查點數據中鍵的訪問規(guī)律

4.3 命令日志恢復實驗

4.3.1 控制檢查點數據記錄數量不變

實驗1中恢復所用數據是通過控制檢查點數據記錄的數量不變，針對不同的σ2產生的。該實驗中的實驗負載參數如表2所示。σ2會影響正態(tài)分布曲線的陡峭程度。

Table2 Experiment 1 load parameters表2 實驗1負載參數

由于控制檢查點數據記錄的數量不變，數據記錄的鍵的分布區(qū)域的邊界已固定，σ2越小時，正態(tài)分布曲線越陡，產生的日志數量也越多，因此恢復所需時間也就越多。圖7為檢查點數據記錄的數量為1.0×105，命令日志恢復實驗。其中橫坐標為與其訪問規(guī)律相關的參數σ2，縱坐標為恢復時間，副縱坐標表示檢查點數據記錄中熱數據記錄所占比例。從圖中可以看出，在本次實驗中，雖然所產生日志數量各不相同，但針對每一數據，基于熱度記錄的內存數據庫恢復策略比NUMA架構的常規(guī)恢復策略要快，而且隨著σ2的增大，熱數據所占比有增長的趨勢。圖8和圖9分別為檢查點數據記錄數量為5.0×105和1.0×106時的內存數據庫日志恢復實驗。這兩個實驗中能發(fā)現同樣的規(guī)律。

Fig.7 Recovery time when checkpoint data number is1.0×105圖7 檢查點數據記錄數量為1.0×105時恢復時間

Fig.8 Recovery time when checkpoint data number is5.0×105圖8 檢查點數據記錄數量為5.0×105時恢復時間

Fig.9 Recovery time when checkpoint data number is1.0×106圖9 檢查點數據記錄數量為1.0×106時恢復時間

為了展示檢查點數據記錄數量不變時，不同的σ2產生的日志大小，實驗中獲取了檢查點數據記錄數量為1.0×106，日志大小隨σ2而變化的情況，如表3所示。從表中可以看出，σ2越小，所產生的日志數據越多，恢復所需時間也將隨之越多，符合圖中所示實驗結果。

Table3 σ2and log size when the number of checkpoint data is1.0×106表3 檢查點數據數量為1.0×106時σ2與日志大小

4.3.2 控制日志大小不變

實驗2中恢復所用數據是控制日志數量不變，調整σ2的大小而產生的。該實驗中，實驗負載參數如表4所示。由于日志數量不變，為了產生數量固定的日志數據，圖6中檢查點數據的鍵的左右邊界會隨著σ2的增大而增大。

Table4 Experiment 2 load parameters表4 實驗2負載參數

圖10和圖11分別為日志數量為1.0×107和5.0×107時的內存數據庫日志恢復時間圖。此實驗中日志數量保持不變，檢查點數據記錄的數量隨σ2的變化而不同。兩張圖的恢復時間的變化趨勢基本類似，即σ2較小時，兩種恢復策略的恢復時間差值較大，熱數據策略相對常規(guī)策略的恢復速度的提升比例較大，最大提升為19%。隨著σ2的增大，兩種策略的恢復時間越來越接近。本實驗中由于日志數量保持不變，在σ2較小時，數據訪問規(guī)律的正態(tài)分布曲線比較陡，訪問的數據比較集中。此時，各個執(zhí)行恢復操作的線程的負載不均衡度越高。基于熱度記錄的恢復策略可以很好地做到負載均衡。此時，恢復性能的提升較高。隨著σ2的增大，數據庫對數據的訪問越來越分散，正態(tài)分布曲線越來越平緩，導致NUMA架構下常規(guī)策略的執(zhí)行恢復操作的線程的負載越來越趨向均衡。因此，常規(guī)策略的恢復時間會越來越少。熱數據策略為負載均衡所做的開銷逐漸成為劣勢。因此，隨著σ2的增大，熱數據策略的恢復性能提升比例越來越小，兩種策略的恢復時間越來越接近。圖中，σ2的值為1.0×106時的兩種恢復策略所用時間都明顯高于前面幾組的恢復時間。這是因為，在實驗2中由于固定日志數量不變，當σ2較小時，所產生的檢查點數據記錄的數量很小，加載檢查點數據的時間對整體恢復時間來說可忽略。但從σ2的值為1.0×105開始，檢查點數據記錄的數量為日志數量的5.2%，σ2的值為1.0×106時為37.3%。此時的檢查點數據的加載時間會導致整體的數據庫恢復時間增大。

Fig.10 Recovery time when the number of logs is1.0×107圖10 日志數量為1.0×107時的恢復時間

Fig.11 Recovery time when the number of logs is5.0×107圖11 日志數量為5.0×107時的恢復時間

5 結束語

針對在面向數據設計的內存數據庫系統(tǒng)中，NUMA體系架構環(huán)境下進行日志恢復時，因恢復線程負載不均衡而導致的恢復速度慢的問題，本文提出了基于數據熱度的命令日志恢復算法。該算法利用數據的訪問頻次將數據分為熱數據和非熱數據，將熱數據分配給相對空閑的恢復線程，有效解決了恢復線程負載不均衡的問題。實驗表明，在數據訪問相對集中時，基于數據熱度的命令劃分方案比NUMA架構的常規(guī)方案快，最高快19%?？梢缘贸?，在NUMA架構下面向數據設計的內存數據庫系統(tǒng)中，對數據的訪問頻率相對集中的數據庫系統(tǒng)中，適合使用本文提出的基于熱度記錄的命令日志恢復策略，相反則適合使用NUMA架構下的常規(guī)的平均劃分策略。在未來的研究中主要解決的問題是在NUMA體系架構環(huán)境下，面向數據設計的內存數據庫中，提高數據的本地性，減少CPU跨節(jié)點訪問遠端內存中的數據的問題。