郭 璇， 周 浩， 羅文輝

(武漢理工大學(xué) 自動化學(xué)院， 武漢 430070)

基于OCC-DA-MCP算法的Redis并發(fā)控制

郭 璇*， 周 浩， 羅文輝

(武漢理工大學(xué) 自動化學(xué)院， 武漢 430070)

該文以提高Redis內(nèi)存數(shù)據(jù)庫的并發(fā)性能為目的，通過研究現(xiàn)有的內(nèi)存數(shù)據(jù)庫并發(fā)控制算法，然后結(jié)合Redis架構(gòu)，設(shè)計并實現(xiàn)了基于OCC-DA-MCP算法的Redis并發(fā)控制.仿真結(jié)果表明，該算法在一定程度上改善了現(xiàn)有Redis并發(fā)控制算法存在的浪費的執(zhí)行和不必要的重啟等問題.

并發(fā)控制； Redis； 內(nèi)存數(shù)據(jù)庫

Redis(Remote Dictionary Server)，是一個使用ANSI C語言編寫、基于鍵值對(Key-Value)數(shù)據(jù)存儲的內(nèi)存數(shù)據(jù)庫[1]，并能夠提供多種語言的API.Redis的應(yīng)用非常的廣泛，目前國內(nèi)的大型互聯(lián)網(wǎng)公司如新浪、淘寶，國外的Fickr、Github等均在使用Redis的緩存服務(wù)[2].

并發(fā)控制是指在多線程數(shù)據(jù)請求下，保證數(shù)據(jù)庫一致性和完整性的機制.由于Redis是一種單線程機制的內(nèi)存數(shù)據(jù)庫，理論上來說不存在并發(fā)和鎖的概念，高并發(fā)對同一個鍵的操作會進(jìn)行排隊處理，其命令會一條一條依次執(zhí)行.但是，利用Redis客戶端對Redis進(jìn)行并發(fā)訪問時可能會出現(xiàn)連接超時、數(shù)據(jù)轉(zhuǎn)換錯誤、阻塞、客戶端意外關(guān)閉連接等問題，這些問題的出現(xiàn)都可能會影響Redis的性能.

本文通過分析OCC-DA并發(fā)控制算法，以及結(jié)合Redis內(nèi)存數(shù)據(jù)庫的特點，提出了基于OCC-DA的改良算法，在Redis的高并發(fā)實際應(yīng)用中有很重要的實用意義.

1 內(nèi)存數(shù)據(jù)庫并發(fā)控制研究

1.1 并發(fā)控制算法概述

并發(fā)控制是指在多個用戶同時對服務(wù)器執(zhí)行數(shù)據(jù)操作時，能夠確保并糾正由并發(fā)操作導(dǎo)致的錯誤，用于保護(hù)數(shù)據(jù)庫完整性的各種技術(shù)，其基本單位是事務(wù).并發(fā)機制的不正確可能會導(dǎo)致服務(wù)器數(shù)據(jù)的丟失、不可重復(fù)讀取等問題.

內(nèi)存數(shù)據(jù)庫作為一個共享資源，不同的客戶端可以隨時的對其進(jìn)行數(shù)據(jù)訪問，為了最大限度的利用數(shù)據(jù)庫里的資源，就應(yīng)該允許多個客戶端并行的對數(shù)據(jù)庫的數(shù)據(jù)進(jìn)行訪問.對于實際的系統(tǒng)，可能會出現(xiàn)多個客戶端并發(fā)操作同一個數(shù)據(jù)的情況，如果沒有相應(yīng)的機制來控制并發(fā)操作，很可能會對數(shù)據(jù)造成誤操作，破壞數(shù)據(jù)庫的一致性，因此，并發(fā)控制效果是衡量內(nèi)存數(shù)據(jù)庫性能的重要指標(biāo)之一.

并發(fā)控制主要有悲觀控制和樂觀控制[3]，其技術(shù)手段有時間戳、封鎖、多版本和快照隔離等.基于鎖的并發(fā)控制屬于悲觀并發(fā)控制算法，使用該類算法時，事務(wù)沒有獲取鎖之前無法訪問數(shù)據(jù)對象，悲觀并發(fā)控制算法較為常見的有2PL-HP、2PL-PI、2PL-CPI等；樂觀并發(fā)控制算法的事務(wù)執(zhí)行分為三個階段：讀階段、驗證階段和寫階段，該類算法主要有OCC-BC、OCC-Sacrifice、OCC-Wait、OOC-TI、OCC-DA等.本文針對OCC-DA算法進(jìn)行研究.

1.2 并發(fā)控制算法存在的不足

在對實時事務(wù)進(jìn)行并發(fā)控制時，會考慮到事務(wù)的優(yōu)先級和截止期兩個主要因素，根據(jù)在這兩個因素上的不同側(cè)重點，兩類算法分別存在不同的影響算法性能的問題.

1) 悲觀控制算法的主要問題有：浪費的等待和浪費的重啟.

浪費的重啟：考慮到事務(wù)的優(yōu)先級，悲觀控制算法會在低優(yōu)先級的事務(wù)與高優(yōu)先級的事務(wù)發(fā)生沖突時重啟低優(yōu)先級的事務(wù)，如果在重啟低優(yōu)先級的事務(wù)后，高優(yōu)先級的事務(wù)因為錯過截止期而導(dǎo)致事務(wù)中止，那么低優(yōu)先級事務(wù)的重啟就是浪費的重啟.

浪費的等待：如果低優(yōu)先級的事務(wù)與高優(yōu)先級的事務(wù)發(fā)生沖突時進(jìn)入等待狀態(tài)，而在等待期間高優(yōu)先級的事務(wù)因為錯過截止期而導(dǎo)致事務(wù)中止，那么低優(yōu)先級的事務(wù)的等待就是浪費的等待.

2) 樂觀控制算法的主要問題有：浪費的執(zhí)行和不必要的重啟.

浪費的執(zhí)行：主要有兩種可能導(dǎo)致該問題的原因.一個是如果事務(wù)因為錯過時間截止期而中止了，那么該事務(wù)的所有執(zhí)行時間都是浪費的；另一個是如果事務(wù)因為數(shù)據(jù)訪問沖突而重啟了，那么事務(wù)之前的執(zhí)行都是浪費的.

不必要的重啟：如果一個事務(wù)在驗證階段被重啟了，且該事務(wù)如果不重啟的話仍然能保證事務(wù)調(diào)度的可串行性，那么這種重啟就是不必要的.

2 基于OCC-DA-MCP的Redis并發(fā)控制

2.1 Redis并發(fā)控制

Redis對于并發(fā)控制的處理，主要是基于其相應(yīng)的事務(wù)操作[4].內(nèi)部原理是通過命令將一組數(shù)據(jù)庫操作命令集合起來，一次全部執(zhí)行.使用的命令有：MULTI(開啟事務(wù))；EXEC(執(zhí)行事務(wù))、DISCARD(取消事務(wù))、WATCH(監(jiān)視數(shù)據(jù)).Redis事務(wù)中所有的操作都會被序列化，并且有序的執(zhí)行.

Redis使用的是檢查設(shè)置算法(check-and-set，OCC-CS)處理并發(fā)的問題，這是一種樂觀并發(fā)控制算法.當(dāng)一個請求開啟事務(wù)對某個數(shù)據(jù)進(jìn)行操作時，會首先使用WATCH命令來監(jiān)視這個數(shù)據(jù)，如果事務(wù)執(zhí)行前數(shù)據(jù)值被修改了，那么事務(wù)就會被取消.假設(shè)事務(wù)T1使用WATCH命令監(jiān)控了數(shù)據(jù)D的值，OCC-CS算法的具體描述如下：

if(D.oldvalue!=D.newvalue)

DISCARD T1;

else

EXEC T1;

其中，D.oldvalue是開啟事務(wù)時D的值，D.newvalue是執(zhí)行事務(wù)前D的值.在該算法中，優(yōu)先對數(shù)據(jù)進(jìn)行操作的事務(wù)會成功提交，并未考慮事務(wù)真正的優(yōu)先級，且在實際的使用中會出現(xiàn)大量的事務(wù)重啟，因此并不適用于實際的實時數(shù)據(jù)庫.

2.2 OCC-DA并發(fā)控制

樂觀動態(tài)調(diào)整串行化(Dynamic Adjustment of Serialization Order，OCC-DA)算法[5]，使用動態(tài)的時間戳(SOT)來標(biāo)識事務(wù)，每個數(shù)據(jù)對象有讀和寫兩個時間戳.對于事務(wù)來說，只有在其動態(tài)時間戳的值比數(shù)據(jù)對象的時間戳大時，才能對數(shù)據(jù)對象進(jìn)行操作，否則事務(wù)必須重啟.假定事務(wù)T1和T2，沖突事務(wù)集合T_set，數(shù)據(jù)對象D，大致的驗證階段算法描述如下：

Validate(T1){

if(T1.TS

RESTART T1；

if(T1.Priority

RESTART T1；

else

RESTART T2；

UPDATE D.WTS；

UPDATE D.RTS；

EXEC T1;

}

其中，RESTART表示重啟事務(wù)，UPDATE表示更新時間戳.OCC-DA算法會根據(jù)優(yōu)先級來決定沖突事務(wù)的重啟，同時可以動態(tài)調(diào)整串行化的順序，降低事務(wù)重啟的概率.

2.3 OCC-DA-MCP并發(fā)控制

傳統(tǒng)的OCC-DA算法在進(jìn)行并行控制時，由于沒有對事務(wù)時間截止期的驗證，在事務(wù)發(fā)生沖突導(dǎo)致重啟后可能會造成事務(wù)浪費的執(zhí)行.而且在OCC-DA算法中，雖然有對于實時事務(wù)的優(yōu)先級的描述，但是對于事務(wù)的重要度(即事務(wù)對實時數(shù)據(jù)庫系統(tǒng)的價值)和實時數(shù)據(jù)的一致性這兩點是沒有考慮到的.針對OCC-DA算法的缺點，本文通過加入事務(wù)重要度、時間截止期和數(shù)據(jù)一致性的描述，提出了樂觀多條件優(yōu)先級動態(tài)調(diào)整串行化(OCC-Dynamic Adjustment of Serialization Multi Condition Pririoty，OCC-DA-MCP)并發(fā)控制算法.

OCC-DA-MCP算法中有3個事務(wù)集合：重要事務(wù)(Critic_Set)、活動事務(wù)(Active_Set)和擱置事務(wù)(Idle_Set).重要事務(wù)是執(zhí)行等級最高的事務(wù)，算法總是會優(yōu)先執(zhí)行該集合中的事務(wù)，該事務(wù)的判定方法有兩種，一個是硬實時事務(wù)，另一個是優(yōu)先級達(dá)到重要事務(wù)判定閾值(PThreshold)的軟實時事務(wù)和固實時事務(wù)，這類事務(wù)可以看作是優(yōu)先級處于頂端的活動事務(wù)；活動事務(wù)會與驗證事務(wù)進(jìn)行沖突檢測，算法在產(chǎn)生沖突時會依據(jù)優(yōu)先級和時間截止期等條件對集合中事務(wù)的動態(tài)時間戳進(jìn)行調(diào)整；擱置事務(wù)是截止期比較長，可以暫時等待的事務(wù).設(shè)置活動事務(wù)和擱置事務(wù)兩個集合，可以減少算法進(jìn)行沖突檢測時事務(wù)的數(shù)量，從而減少系統(tǒng)資源上的開銷.

OCC-DA-MCP算法在OCC-DA算法的基礎(chǔ)上加入了對事務(wù)重要度的描述，這樣可以更大程度的保證重要事務(wù)的執(zhí)行.同時在樂觀控制的事務(wù)三階段處理思想上，加入了事務(wù)分類階段，這樣做可以提高并發(fā)控制算法處理重要事務(wù)的能力.各階段的描述如下：

1) 分類階段

該階段首先檢測事務(wù)是否合法，通過合法性檢測的事務(wù)會根據(jù)實時事務(wù)的類型來進(jìn)行分類，如果事務(wù)不是重要事務(wù)，那么會根據(jù)事務(wù)的時間截止期將事務(wù)放入不同的集合中.假定實時事務(wù)T1，該階段的具體算法描述如下：

if(Check(T1)){

if(T1.T==“硬實時事務(wù)” OR T1.P>PT)

Critic_Set.Add(T1);

else{

if(T1.Deadline > PThreshold)

Active_Set.Add(T1);

else

Idle_Set.Add(T1);

}

}

else

DISCARD T1;

其中，Check表示檢測事務(wù)是否合法，Add表示在相應(yīng)的事務(wù)集合中加入該事務(wù).

2) 讀階段

事務(wù)在進(jìn)入重要事務(wù)集合或者活動事務(wù)集合時會開始該階段.在該階段，事務(wù)會將需要操作的各數(shù)據(jù)的值讀入局部變量區(qū)中，并將所有寫操作的結(jié)果都保存在局部變量區(qū)中，同時驗證事務(wù)操作數(shù)據(jù)的內(nèi)部一致性.算法描述如下：

ReadPhase(T);

foreach(D∈T.DATA)

if(!CheckInConsistency(D))

DISCARD T;

其中，ReadPhase表示事務(wù)進(jìn)入讀階段后，將需要操作的數(shù)據(jù)讀到局部變量區(qū)并進(jìn)行相關(guān)的操作，CheckInConsistency的作用是驗證數(shù)據(jù)的內(nèi)部一致性，如果不滿足內(nèi)部一致性，會返回假，此時事務(wù)會直接中止.

3) 驗證階段

驗證階段會對事務(wù)進(jìn)行有效性的檢測，同時會進(jìn)行數(shù)據(jù)的外部一致性檢測，判定是否可以將局部變量區(qū)中的數(shù)據(jù)復(fù)制到實時數(shù)據(jù)庫中，如果判定通過，事務(wù)會進(jìn)入寫階段.

假定事務(wù)T1處于驗證階段，事務(wù)T2是活動事務(wù)集合中的任意事務(wù)，以及數(shù)據(jù)對象D.將所有滿足SOT(T2)SOT(T1)的事務(wù)集合記作BTS(T1)，當(dāng)T1在讀階段讀取D時，令TR(T1，D)=WTS(D).事務(wù)的驗證階段一共分為5步執(zhí)行.

第1步：檢測數(shù)據(jù)的外部一致性.如果D.ST+D.TI>TC，TC表示系統(tǒng)當(dāng)前的時間，數(shù)據(jù)D滿足外部一致性，否則不滿足，當(dāng)數(shù)據(jù)的外部一致性失效時，事務(wù)會中止.

第2步：檢測驗證事務(wù)是否和已提交的事務(wù)發(fā)生了沖突.如果SOT(T1)

第3步：檢測驗證事務(wù)的寫操作是否都有效.如果SOT(T1)

第4步：檢測驗證事務(wù)與活動事務(wù)的數(shù)據(jù)訪問沖突.比較驗證事務(wù)T1的寫數(shù)據(jù)集合與ATS(T1)集合中的活動事務(wù)T2的讀數(shù)據(jù)集合，如果發(fā)生了沖突，則將沖突事務(wù)T2添加到?jīng)_突集合CT(T1)中.

第5步：檢測活動事務(wù)與驗證事務(wù)的數(shù)據(jù)訪問沖突.比較BST(T1)或者CT(T1)中的活動事務(wù)T2的寫數(shù)據(jù)集合與驗證事務(wù)T1的讀寫集合，如果存在交集，則說明T2與T1發(fā)生了沖突.此時必須進(jìn)行沖突解決，根據(jù)優(yōu)先級和時間截止期選擇被重啟的事務(wù).

根據(jù)事務(wù)驗證階段的執(zhí)行內(nèi)容，用WS(T)表示事務(wù)的寫集合，RS(T)表示事務(wù)的讀集合，事務(wù)驗證階段的算法描述如下：

Validate(T1){

if(D.ST+D.TI>TC)

DISCARD T1;

else{

if(T2∈Active_Set)

foreach(D∈RS(T1))

if(SOT(T1)

RESTART T1;

foreach(D∈WS(T1))

if(SOT(T1)

RESTART T1;

CT(T1).Clear;

if(T2∈ATS(T1))

foreach(D∈WS(T1))

if(D∈RS(T2))

CT(T1).Add(T2);

if(T2∈BTS(T1) || T2∈CT(T1)){

foreach(D∈RS(T1))

if(D∈WS(T2))

Conflict_Solve(T1，T2);

foreach(D∈WS(T1))

if(D∈WS(T2))

Conflict_Solve(T1，T2);

}

}

}

其中,Clear表示清空事務(wù)集合，Conflict_Solve表示事務(wù)沖突的解決.OCC-DA算法采用的是優(yōu)先級的方式來解決沖突，低優(yōu)先級的事務(wù)總是會首先重啟，這樣可以簡化算法的執(zhí)行，但是可能會出現(xiàn)浪費的執(zhí)行的情況.例如，驗證事務(wù)T1的優(yōu)先級比活動事務(wù)T2的優(yōu)先級低，且T1和T2出現(xiàn)了讀寫沖突，此時OCC-DA算法會直接重啟T1，但是T2后來執(zhí)行時超過了時間截止期，這樣就導(dǎo)致了浪費的執(zhí)行，同時，如果T2的時間截止期還比較充裕，而T1重啟后離時間截止期也比較近，這樣就導(dǎo)致了T1的執(zhí)行是浪費的.因此在設(shè)計沖突解決策略時，OCC-DA-MCP算法引入了執(zhí)行時間和時間截止期兩個參數(shù)來避免浪費的執(zhí)行.該階段算法描述如下：

Conflict_Solve(T1，T2){

if(T1.P>T2.P)

ASS(T1).Add(T2);

else{

if(T2.AST-TC>Factor×T2.ET)

ASS(T1).Add(T2);

else if(T2.AST-TC

DISCARD T2

else

RESTART T1;

}

}

其中，ASS表示需要調(diào)整動態(tài)時間戳的事務(wù)，在寫階段會對該集合中的事務(wù)進(jìn)行時間戳調(diào)整.Factor是T2剩余時間截止期的比例系數(shù)，實驗表明取1.3～1.5時策略的效果比較好.

4) 寫階段

事務(wù)通過驗證階段后會進(jìn)入寫階段，到達(dá)寫階段的事務(wù)總是會被提交.事務(wù)在該階段會首先更新數(shù)據(jù)的讀寫時間戳和ASS集合中事務(wù)的時間戳，然后將局部變量區(qū)中的數(shù)據(jù)復(fù)制到實時數(shù)據(jù)庫中，即完成提交.該階段的算法描述如下：

foreach(T∈ASS(T1))

T.SOT=TC;

foreach(D∈RS(T1))

D.RTS=TC;

foreach(T∈WS(T1))

D.WTS=TC;

EXEC WS(T1);

3 并發(fā)控制性能分析

通過搭建的測試環(huán)境對相應(yīng)的并發(fā)控制算法進(jìn)行性能測試，取相同參數(shù)下的仿真實驗10次結(jié)果的平均值作為一次實驗的真正結(jié)果.測試中使用的參數(shù)，主要參考了以前的文獻(xiàn)[6]，事務(wù)生成時優(yōu)先級是根據(jù)最早截止期優(yōu)先的策略分配的[7].表1中反映了系統(tǒng)的負(fù)載狀態(tài)和事務(wù)的部分特性設(shè)置.

表1 實驗參數(shù)及對應(yīng)值

1) 截止期計算公式

DeadLine=AT+uniform(MinSlack，

MaxSlack) × ET，

(1)

式中，AT表示的是事務(wù)到達(dá)的時間，ET表示的是事務(wù)執(zhí)行的時間，uniform是均勻分布函數(shù).

2) 事務(wù)錯失率計算公式

M_Ratio=Num_Miss ÷ Num_Total，

(2)

式中，M_Ratio是事務(wù)的截止期錯失率，Num_Miss表示錯失截止期的事務(wù)個數(shù)，Num_Total表示總的事務(wù)個數(shù).

圖1 WP為0.2時事務(wù)錯失率Fig.1 Transaction miss rate when WP=0.2

圖2 WP為0.3時事務(wù)錯失率Fig.2 Transaction miss rate when WP=0.3

將WP值分別設(shè)置為0.2和0.3，并將事務(wù)到達(dá)率設(shè)置為變化量.如圖1所示，此時WP為0.2，當(dāng)系統(tǒng)事務(wù)到達(dá)率小于300，即負(fù)載較低時，OCC-DA算法和OCC-DA-MCP算法都能表現(xiàn)出比較好的性能，事務(wù)錯失率幾乎為零.隨著事務(wù)到達(dá)率的

增加，OCC-CS算法性能降低的比較快，而OCC-DA算法和OCC-DA-MCP算法的錯失率比OCC-CS算法要低很多，即性能要好很多.

如圖2所示，此時WP為0.3，同一種算法的事務(wù)錯失率總體趨勢和WP為0.2時是一致的，即隨著事務(wù)到達(dá)率的增加，事務(wù)錯失率也增加.但是相較于WP為0.2時，OCC-DA-MCP算法能夠比OCC-DA算法表現(xiàn)出更好的性能.由此可見，隨著WP值的增加，OCC-DA-MCP算法能夠更好的提高Redis的并發(fā)性能.

4 結(jié)束語

針對Redis并發(fā)控制性能低的問題，本文在參考OCC-DA算法的基礎(chǔ)上，結(jié)合事務(wù)優(yōu)先權(quán)和實時數(shù)據(jù)一致性，提出了改進(jìn)算法OCC-DA-MCP.試驗結(jié)果表明，OCC-DA-MCP算法能夠提高Redis的并發(fā)性能.

[1] 黃健宏. Redis 設(shè)計與實現(xiàn)[M].北京：機械工業(yè)出版社， 2014．

[2] 曾超宇， 李金香. Redis在高速緩存系統(tǒng)中的應(yīng)用[J].微型機與應(yīng)用， 2013，32(12)：11-13．

[3] 祁 鑫， 王文海. 實時數(shù)據(jù)庫系統(tǒng)并發(fā)控制機制綜述[J].化工自動化及儀表， 2006，33(1)：47-50．

[4] 賴 歆. 基于Redis的分布式鎖的實現(xiàn)方案[J].信息通信， 2016，166(10)：83-84．

[5] 邊 遠(yuǎn)， 楊 靜， 盧大勇. 一種改進(jìn)的動態(tài)調(diào)整串行化順序算法[J].計算機工程， 2008，34(3)：108-110．

[6] 劉云生， 夏家莉， 許貴平. 嵌入式數(shù)據(jù)庫系統(tǒng)的事務(wù)調(diào)度[J].軟件學(xué)報， 2002，13(8)：1692-1697．

[7] INDRAKSHI R.Real-time update of access control policies[J].Data and Knowledge Engineering， 2004，49(3)：287-309．

OCC-DA-MCPalgorithmbasedconcurrencycontrolofRedis

GUO Xuan, ZHOU Hao, LUO Wenhui

(School of Automation, Wuhan University of Technology, Wuhan 430070, China)

In order to improve the concurrency performance of Redis memory database, the existing memory database concurrency control (OCC-DA-MCP) algorithm is studied in the present work. And then Redis concurrency control is desighend and realized in combination of Redis architecture with OCC-DA-MCP algorithm. The simulation results show that the algorithm, to a certain extent, improves the problems of existing Redis concurrency control algorithm such as wasteful execution and unnecessary restart.

concurrency control; Redis; memory database

2017-05-11.

國家高技術(shù)研究發(fā)展計劃項目(863計劃-2015AA015904)．

*E-mail: 498820227@qq.com.

10.19603/j.cnki.1000-1190.2017.06.006

1000-1190(2017)06-0760-05

TP311.133.1

A