基于OCC-DA-MCP算法的Redis并發控制

郭 璇， 周 浩， 羅文輝

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

基于OCC-DA-MCP算法的Redis并發控制

郭 璇*， 周 浩， 羅文輝

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

該文以提高Redis內存數據庫的并發性能為目的，通過研究現有的內存數據庫并發控制算法，然后結合Redis架構，設計并實現了基于OCC-DA-MCP算法的Redis并發控制.仿真結果表明，該算法在一定程度上改善了現有Redis并發控制算法存在的浪費的執行和不必要的重啟等問題.

并發控制； Redis； 內存數據庫

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

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

本文通過分析OCC-DA并發控制算法，以及結合Redis內存數據庫的特點，提出了基于OCC-DA的改良算法，在Redis的高并發實際應用中有很重要的實用意義.

1 內存數據庫并發控制研究

1.1 并發控制算法概述

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

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

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

1.2 并發控制算法存在的不足

在對實時事務進行并發控制時，會考慮到事務的優先級和截止期兩個主要因素，根據在這兩個因素上的不同側重點，兩類算法分別存在不同的影響算法性能的問題.

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

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

浪費的等待：如果低優先級的事務與高優先級的事務發生沖突時進入等待狀態，而在等待期間高優先級的事務因為錯過截止期而導致事務中止，那么低優先級的事務的等待就是浪費的等待.

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

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

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

2 基于OCC-DA-MCP的Redis并發控制

2.1 Redis并發控制

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

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

if(D.oldvalue!=D.newvalue)

DISCARD T1;

else

EXEC T1;

其中，D.oldvalue是開啟事務時D的值，D.newvalue是執行事務前D的值.在該算法中，優先對數據進行操作的事務會成功提交，并未考慮事務真正的優先級，且在實際的使用中會出現大量的事務重啟，因此并不適用于實際的實時數據庫.

2.2 OCC-DA并發控制

樂觀動態調整串行化(Dynamic Adjustment of Serialization Order，OCC-DA)算法[5]，使用動態的時間戳(SOT)來標識事務，每個數據對象有讀和寫兩個時間戳.對于事務來說，只有在其動態時間戳的值比數據對象的時間戳大時，才能對數據對象進行操作，否則事務必須重啟.假定事務T1和T2，沖突事務集合T_set，數據對象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表示重啟事務，UPDATE表示更新時間戳.OCC-DA算法會根據優先級來決定沖突事務的重啟，同時可以動態調整串行化的順序，降低事務重啟的概率.

2.3 OCC-DA-MCP并發控制

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

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

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

1) 分類階段

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

if(Check(T1)){

if(T1.T==“硬實時事務” 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表示檢測事務是否合法，Add表示在相應的事務集合中加入該事務.

2) 讀階段

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

ReadPhase(T);

foreach(D∈T.DATA)

if(!CheckInConsistency(D))

DISCARD T;

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

3) 驗證階段

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

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

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

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

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

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

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

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

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

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表示需要調整動態時間戳的事務，在寫階段會對該集合中的事務進行時間戳調整.Factor是T2剩余時間截止期的比例系數，實驗表明取1.3～1.5時策略的效果比較好.

4) 寫階段

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

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 并發控制性能分析

通過搭建的測試環境對相應的并發控制算法進行性能測試，取相同參數下的仿真實驗10次結果的平均值作為一次實驗的真正結果.測試中使用的參數，主要參考了以前的文獻[6]，事務生成時優先級是根據最早截止期優先的策略分配的[7].表1中反映了系統的負載狀態和事務的部分特性設置.

表1 實驗參數及對應值

1) 截止期計算公式

DeadLine=AT+uniform(MinSlack，

MaxSlack) × ET，

(1)

式中，AT表示的是事務到達的時間，ET表示的是事務執行的時間，uniform是均勻分布函數.

2) 事務錯失率計算公式

M_Ratio=Num_Miss ÷ Num_Total，

(2)

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

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

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

將WP值分別設置為0.2和0.3，并將事務到達率設置為變化量.如圖1所示，此時WP為0.2，當系統事務到達率小于300，即負載較低時，OCC-DA算法和OCC-DA-MCP算法都能表現出比較好的性能，事務錯失率幾乎為零.隨著事務到達率的

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

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

4 結束語

針對Redis并發控制性能低的問題，本文在參考OCC-DA算法的基礎上，結合事務優先權和實時數據一致性，提出了改進算法OCC-DA-MCP.試驗結果表明，OCC-DA-MCP算法能夠提高Redis的并發性能.

[1] 黃健宏. Redis 設計與實現[M].北京：機械工業出版社， 2014．

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

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

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

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

[6] 劉云生， 夏家莉， 許貴平. 嵌入式數據庫系統的事務調度[J].軟件學報， 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.

國家高技術研究發展計劃項目(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