移動(dòng)實(shí)時(shí)環(huán)境下的數(shù)據(jù)一致性研究

帖 軍，王小榮，金 佳

(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

隨著互聯(lián)網(wǎng)的不斷延伸和無(wú)線接入技術(shù)的快速發(fā)展，人們希望能在任意時(shí)間、地點(diǎn)訪問(wèn)任意數(shù)據(jù)并且對(duì)突發(fā)數(shù)據(jù)做出及時(shí)反應(yīng)的需求已逐漸成為現(xiàn)實(shí)，信息系統(tǒng)正在走出傳統(tǒng)的機(jī)房與桌面，幫助用戶隨時(shí)隨地獲取相關(guān)信息，做出正確決策.因此，一種新的移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)運(yùn)而生并迅速發(fā)展起來(lái).這種新的數(shù)據(jù)庫(kù)技術(shù)主要用于維護(hù)數(shù)據(jù)的一致性，支持多用戶的并發(fā)訪問(wèn)，使用戶可以隨時(shí)隨地查詢和更新數(shù)據(jù)庫(kù).

在移動(dòng)實(shí)時(shí)計(jì)算環(huán)境中，雖然同樣可以滿足事務(wù)的ACID［1］特性，保持系統(tǒng)的嚴(yán)格一致性，但是這樣會(huì)造成許多事務(wù)的回滾操作［2］，使得系統(tǒng)頻繁地處于抖動(dòng)狀態(tài)，嚴(yán)重影響移動(dòng)用戶的使用，所以我們經(jīng)常會(huì)引入一些其他的規(guī)則(如:隔離級(jí)別)，在不同的情況下采用不同的隔離級(jí)別，以犧牲一定的數(shù)據(jù)準(zhǔn)確性來(lái)提高數(shù)據(jù)的處理效率，即提高事務(wù)的并發(fā)性.

由于目前國(guó)內(nèi)外對(duì)基于悲觀并發(fā)控制的事務(wù)處理技術(shù)已經(jīng)很成熟，所以本文基于悲觀并發(fā)控制對(duì)數(shù)據(jù)的不一致性進(jìn)行分析，并找到一種新的隔離級(jí)別劃分的方法來(lái)實(shí)現(xiàn)事務(wù)的并發(fā)執(zhí)行.

1 傳統(tǒng)隔離級(jí)別

1.1 相關(guān)概念

本文在分析數(shù)據(jù)不一致性時(shí)，將事務(wù)劃分為本地事務(wù)和內(nèi)存事務(wù).我們基于鎖控制方案提出保持?jǐn)?shù)據(jù)一致性的相關(guān)策略.首先引入幾個(gè)相關(guān)概念.

定義1本地事務(wù):在單個(gè)數(shù)據(jù)庫(kù)中并且限制在單個(gè)進(jìn)程內(nèi)的操作序列，該序列由讀操作或?qū)懖僮鹘M成并以提交或中止操作結(jié)束.

定義2內(nèi)存事務(wù):對(duì)存放于主存中的數(shù)據(jù)集進(jìn)行操作的序列，該序列由讀操作或?qū)懖僮鹘M成并以提交或中止操作結(jié)束.

定義3讀長(zhǎng)鎖:若事務(wù)T對(duì)數(shù)據(jù)D加讀長(zhǎng)鎖，則其他事務(wù)也只能對(duì)其加讀鎖，不能加寫鎖，而且在整個(gè)事務(wù)范圍內(nèi)，該鎖都有效，直到該事務(wù)以提交或回滾完成，才允許其他事務(wù)對(duì)D進(jìn)行寫操作.

定義4讀短鎖:若事務(wù)T對(duì)數(shù)據(jù)D加讀短鎖，則在T讀取D時(shí)，只允許其他事務(wù)對(duì)D加讀鎖，不能加寫鎖，一旦讀取數(shù)據(jù)結(jié)束，該鎖就立即被釋放，此時(shí)才允許寫鎖發(fā)生.

定義5寫長(zhǎng)鎖:若事務(wù)T對(duì)數(shù)據(jù)D加寫長(zhǎng)鎖，則在T更改D時(shí)，不允許其他事務(wù)對(duì)D做任何操作，而且在整個(gè)事務(wù)范圍內(nèi)，該鎖都有效，直到事務(wù)T以提交或回滾完成，才允許其他事務(wù)操作D.

1.2 傳統(tǒng)隔離級(jí)別

傳統(tǒng)隔離是通過(guò)實(shí)行不同鎖機(jī)制來(lái)實(shí)現(xiàn)的［3］，如:何時(shí)加鎖，加何種類型鎖，加多長(zhǎng)時(shí)間鎖等.傳統(tǒng)的4個(gè)隔離級(jí)別都是通過(guò)對(duì)寫操作加長(zhǎng)鎖，其不同在于，對(duì)于讀鎖，鎖的持有期是不一樣的.

這4個(gè)隔離級(jí)別解釋如下:

(1)read_uncommitted未提交讀，事務(wù)對(duì)讀操作不加任何鎖，對(duì)寫操作加寫長(zhǎng)鎖.

(2)read_committed已提交讀，事務(wù)對(duì)讀操作讀短鎖，對(duì)寫操作加寫長(zhǎng)鎖.

(3)repeatable_read可重復(fù)讀，事務(wù)只對(duì)讀取的數(shù)據(jù)項(xiàng)加讀長(zhǎng)鎖和寫長(zhǎng)鎖.

(4)serializable串行化，事務(wù)對(duì)所有的數(shù)據(jù)表上都加讀長(zhǎng)鎖和寫長(zhǎng)鎖.

這些隔離級(jí)別都是通過(guò)封鎖規(guī)則定義的，我們可以設(shè)計(jì)出并發(fā)控制算法來(lái)實(shí)現(xiàn)這些隔離級(jí)別，以此來(lái)使移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)中的數(shù)據(jù)保持一致.表1為傳統(tǒng)隔離級(jí)別下的數(shù)據(jù)不一致［4］，Y表示3種不一致現(xiàn)象在各隔離級(jí)別中存在，N表示不存在.

表1 傳統(tǒng)隔離級(jí)別下的數(shù)據(jù)不一致Tab.1 Data inconsistency at traditional isolation levels

通過(guò)表1我們發(fā)現(xiàn)只有在嚴(yán)格的鎖控制方案中，即:2級(jí)和3級(jí)隔離級(jí)別，才能保持?jǐn)?shù)據(jù)不發(fā)生寫丟失、臟讀和不可重復(fù)讀這些數(shù)據(jù)不一致［5］，但是這樣做會(huì)使得并發(fā)度嚴(yán)重下降，接下來(lái)我們將具體分析這3種數(shù)據(jù)不一致性.

2 數(shù)據(jù)的不一致性分析

本文討論的數(shù)據(jù)不一致問(wèn)題主要是指在數(shù)據(jù)事務(wù)處理過(guò)程中，由于并發(fā)控制機(jī)制不合理而導(dǎo)致事務(wù)間的并行執(zhí)行結(jié)果有誤的現(xiàn)象.本文將事務(wù)劃分為2種事務(wù)，即內(nèi)存事務(wù)和本地事務(wù)，根據(jù)數(shù)據(jù)不一致對(duì)事務(wù)執(zhí)行的準(zhǔn)確性的影響程度，依次分析寫丟失、臟讀、不可重復(fù)讀這3種不一致性.

2.1 寫丟失

(1)形式化定義.

事務(wù)ti，tj∈T，i≠j，ri(x)，wi(x) ∈ti，rj(x)，wj(x)∈tj.

1)若ti，tj為內(nèi)存事務(wù)，存在s=ri(x)wi(x)·rj(x)wj(x)ai或s=ri(x)rj(x)wj(x)wi(x)ai/ci;

2)若ti，tj為本地事務(wù)，存在s=ri(x)wi(x)·rj(x)wj(x)ci cj或s=ri(x)rj(x)wj(x)wi(x)ai/ci.則稱該并發(fā)執(zhí)行的事務(wù)調(diào)度發(fā)生了寫丟失.

(2)意義.

兩個(gè)事務(wù)接連修改了同一個(gè)數(shù)據(jù)項(xiàng)x的值，使得一個(gè)事務(wù)修改的值將另一個(gè)事務(wù)的值覆蓋掉，或兩個(gè)事務(wù)同時(shí)對(duì)一個(gè)數(shù)據(jù)項(xiàng)進(jìn)行修改，則由于一個(gè)事務(wù)的回滾使得另一事務(wù)修改的值也不得不丟失，這兩種情況都稱為寫丟失(或丟失更新).

(3)典型事例分析及對(duì)策.

1)內(nèi)存事務(wù)序列.

①s=r1(x)w1(x)r2(x)w2(x)a1.

內(nèi)存事務(wù)2讀取內(nèi)存事務(wù)1寫x的值，但由于內(nèi)存事務(wù)1的回滾使得內(nèi)存事務(wù)2發(fā)生寫丟失.

解決方法:寫長(zhǎng)鎖、讀短鎖.使得序列s=rl1(x)r1(x)w1(x)wu1(x)a1rl2(x)r2(x)w2(x)wu2(x).

②s=r1(x)r2(x)w2(x)w1(x)a1.

內(nèi)存事務(wù)2由于內(nèi)存事務(wù)1的寫操作的回滾而造成寫丟失.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2w1(x)wu1(x)a1.

③s=r1(x)r2(x)w2(x)w1(x)c1.

內(nèi)存事務(wù)2由于內(nèi)存事務(wù)1的寫提交操作將自身寫的數(shù)據(jù)給覆蓋掉.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2w1(x)wu1(x)c1.

2)本地事務(wù)序列.

①s=r1(x)w1(x)r2(x)w2(x)c2a1.

事務(wù)2由于事務(wù)1的回滾而造成寫丟失.

解決方法:寫長(zhǎng)鎖、讀短鎖.使得序列s=rl1(x)r1(x)w1(x)wu1(x)a1rl2(x)r2(x)w2(x)wu2(x)c2.

②s=r1(x)w1(x)r2(x)w2(x)c2c1.

事務(wù)2由于事務(wù)1的后提交，其值被事務(wù)1的值覆蓋掉.

解決方法:寫長(zhǎng)鎖、讀短鎖.使得序列s=rl1(x)r1(x)w1(x)wu1(x)c1rl2(x)r2(x)w2(x)wu2(x)c2.

③s=r1(x)r2(x)w2(x)w1(x)c1c2.

事務(wù)1由于事務(wù)2的后提交，其值被覆蓋掉.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2w1(x)wu1(x)c1.

2.2 臟讀

(1)形式化定義.

事務(wù)ti，tj∈T，i≠j，ri(x)，wi(x) ∈ti，rj(x)，wj(x)∈tj，若存在以下情況之一，

1)ti，tj為本地事務(wù)，存在s=wi(x)rj(x)ci;

2)ti，tj為內(nèi)存事務(wù)，存在s=wi(x)rj(x)ai或s=rj(x)wi(x)ci，則稱tj讀臟數(shù)據(jù)x.

(2)意義.

當(dāng)一個(gè)事務(wù)正在訪問(wèn)數(shù)據(jù)，并且對(duì)該數(shù)據(jù)進(jìn)行了修改，而這種修改還沒(méi)有提交到數(shù)據(jù)庫(kù)中，這時(shí)另外一個(gè)事務(wù)也訪問(wèn)這個(gè)數(shù)據(jù)，然后使用了這個(gè)數(shù)據(jù)，進(jìn)而造成的數(shù)據(jù)庫(kù)不一致.

(3)典型事例分析及對(duì)策.

1)內(nèi)存事務(wù)序列.

①s=r1(x)w1(x)r2(x)a1.

內(nèi)存事務(wù)2由于內(nèi)存事務(wù)1的回滾，其讀取的x與數(shù)據(jù)庫(kù)中的x值不一致.

解決方法:寫長(zhǎng)鎖、讀短鎖.使得序列s=rl1(x)r1(x)w1(x)wu1(x)a1rl2(x)r2(x)ru2(x).

②s=r1(x)r2(x)w1(x)c1c2.

內(nèi)存事務(wù)2由于讀取x的值早于內(nèi)存事務(wù)1更改x的值，當(dāng)內(nèi)存事務(wù)1提交時(shí)，內(nèi)存事務(wù)2已讀取x的值與數(shù)據(jù)庫(kù)中x值不一致.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2w1(x)wu1(x)c1.

2)本地事務(wù)序列.

事務(wù)2在事務(wù)1更改x值前讀取x，當(dāng)事務(wù)1提交時(shí)，其已讀取的x與數(shù)據(jù)庫(kù)中被更改的x值不一致.

解決方法:讀長(zhǎng)鎖、寫長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2w1(x)wu1(x)c1.

2.3 不可重復(fù)讀

(1)形式化定義.

事務(wù)ti，tj∈T，i≠j，ri(x)，wi(x) ∈ti，rj(x)，wj(x)∈tj.

1)若ti，tj為本地事務(wù)，存在s=ri(x)rj(x)·wj(x)cj ri(x)，則ti不可重復(fù)讀數(shù)據(jù)項(xiàng)x.

2)若ti，tj為內(nèi)存事務(wù)，存在s=ri(x)rj(x)·wj(x)ri(x)，則ti不可重復(fù)讀數(shù)據(jù)項(xiàng)x.

(2)意義.

在一個(gè)事務(wù)內(nèi)，多次讀同一數(shù)據(jù)，在這個(gè)事務(wù)還沒(méi)有結(jié)束時(shí)，另外一個(gè)事務(wù)也訪問(wèn)該數(shù)據(jù).那么，在第1個(gè)事務(wù)的兩次讀數(shù)據(jù)之間，由于第2個(gè)事務(wù)的修改，那么第1個(gè)事務(wù)兩次讀到的數(shù)據(jù)可能是不一樣的.這樣就發(fā)生了一個(gè)事務(wù)內(nèi)兩次讀到的數(shù)據(jù)是不一樣的，稱為這個(gè)事務(wù)不可重復(fù)讀該數(shù)據(jù)項(xiàng).

(3)典型事例分析及對(duì)策.

1)內(nèi)存事務(wù)序列.

s=r1(x)r2(x)w2(x)r1(x).

內(nèi)存事務(wù)1前后兩次讀取x之間由于內(nèi)存事務(wù)2對(duì)x直接更改使得前后在數(shù)據(jù)庫(kù)中讀取的x值不一致.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2r1(x).

2)本地事務(wù)序列.

s=r1(x)r2(x)w2(x)c2r1(x).

事務(wù)1前后兩次讀取x之間由于事務(wù)2對(duì)x更改并提交數(shù)據(jù)庫(kù)使得前后在數(shù)據(jù)庫(kù)中讀取的x值不一致.

解決方法:寫長(zhǎng)鎖、讀長(zhǎng)鎖.使得序列s=rl1(x)r1(x)rl2(x)r2(x)w2(x)wu2(x)a2r1(x).

表2為將事務(wù)劃分為本地事務(wù)和內(nèi)存事務(wù)時(shí)，在不同隔離級(jí)別下存在的數(shù)據(jù)不一致性的總結(jié)，表2中數(shù)據(jù)含義同表1.

表2 不同隔離級(jí)別下的數(shù)據(jù)不一致性Tab.2 Data inconsistency at different isolation levels

3 新的隔離方法

我們發(fā)現(xiàn)傳統(tǒng)隔離級(jí)別中隔離級(jí)的高低與事務(wù)的并發(fā)度是矛盾的.維護(hù)一個(gè)最高的隔離級(jí)別雖然會(huì)防止數(shù)據(jù)的出錯(cuò)，但是卻導(dǎo)致了并行度的損失，以及增加死鎖出現(xiàn)的可能性，而降低隔離級(jí)別，又會(huì)引起一些難以發(fā)現(xiàn)的問(wèn)題.所以對(duì)數(shù)據(jù)庫(kù)使用何種隔離級(jí)別要慎重.并且在上文對(duì)數(shù)據(jù)不一致性的分析中我們也發(fā)現(xiàn)在1級(jí)隔離級(jí)別的情況下還是會(huì)有臟讀情況發(fā)生，而在0級(jí)隔離情況下也會(huì)有不發(fā)生臟讀的情況，這樣單一的使用隔離級(jí)別的話就會(huì)降低某些事務(wù)的執(zhí)行效率，甚至導(dǎo)致事務(wù)執(zhí)行時(shí)產(chǎn)生沖突，從而導(dǎo)致數(shù)據(jù)的不一致.

對(duì)此，我們可以采用一種新的劃分事務(wù)隔離級(jí)別的方法，當(dāng)事務(wù)的調(diào)度序列中出現(xiàn)形如wi(x)rj(x)這樣的序列，那么我們就采用在寫操作上加寫長(zhǎng)鎖，而對(duì)于讀操作就只需加讀短鎖.當(dāng)事務(wù)的調(diào)度序列中出現(xiàn)形如rj(x)wi(x)這樣的序列，那么我們就要對(duì)其讀操作加讀長(zhǎng)鎖，寫操作加寫長(zhǎng)鎖.這么做既簡(jiǎn)單，還能防止數(shù)據(jù)的不一致(如表3所示，表3中數(shù)據(jù)含義同表1).

表3 解決數(shù)據(jù)不一致性的新方法Tab.3 New solution of data inconsistency

4 結(jié)語(yǔ)

在移動(dòng)實(shí)時(shí)數(shù)據(jù)庫(kù)的并發(fā)控制中，除了要保證數(shù)據(jù)的一致性外，還需要考慮事務(wù)處理的效率問(wèn)題，如:在提高數(shù)據(jù)一致性的基礎(chǔ)上提高事務(wù)的并發(fā)度、有限資源的利用率、系統(tǒng)效率等.本文提出的方法既可以保證事務(wù)的數(shù)據(jù)一致性，又提高了事務(wù)的并發(fā)度，且該方法簡(jiǎn)單、易于實(shí)現(xiàn).但是，對(duì)于某些含有rj(x)wi(x)的調(diào)度序列的事務(wù)的并發(fā)執(zhí)行中，該方法有時(shí)還是會(huì)與傳統(tǒng)隔離級(jí)別一樣，產(chǎn)生鎖過(guò)于嚴(yán)格的缺點(diǎn).而對(duì)于如何解決這個(gè)問(wèn)題，需要做進(jìn)一步的研究.

［1］Ghorbanzadeh P，Shaddeli A，Malekzadeh R，et al.A survey of mobile database security threats and solutions for it［J］.Information Sciences and Interaction Science(ICIS)，2010(6):676-682.

［2］Yadav D S，Agrwal R，Saraswat R C.Analysis of cooperation processing with full and partial aborts in active database［J］.Information，Communications and Signal Processing，2003(12):1670-1674.

［3］Lu Shiyong，Bernstein A，Lewis P.Correct execution of transactions at different isolation levels［J］.Knowledge and Data Engineering，2004(9):1070-1081.

［4］Rahman S，Shrestha GB.Analysis of inconsistent data in power planning［J］.Power Systems，1991(1):225-230.

［5］Zhen Chenggang，Li Kai.Memory management research based on real-time database［J］.International Conference on Test and Measurement，2009(1):416-419.