[發(fā)明專利]一種范圍鎖的實現(xiàn)方法及裝置

有效

• 申請?zhí)枺?/td>: 201410677262.1
• 申請日: 2014-11-21
• 公開（公告）號: CN104391935B
• 公開（公告）日: 2017-12-12
• 發(fā)明（設(shè)計）人: 楊晗;馮銳
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產(chǎn)權(quán)代理有限公司11291
• 代理人: 馮艷蓮

技術(shù)領(lǐng)域

本發(fā)明涉及電子技術(shù)領(lǐng)域，尤其涉及一種范圍鎖的實現(xiàn)方法及裝置。

背景技術(shù)

分布式鎖是在集群系統(tǒng)中實現(xiàn)跨節(jié)點互斥訪問共享資源的一種方式。在大型應(yīng)用系統(tǒng)中，對單個文件(如數(shù)據(jù)庫文件)以文件為粒度的跨節(jié)點互斥訪問無法滿足系統(tǒng)的高并發(fā)要求，故產(chǎn)生了范圍鎖，實現(xiàn)對大文件/資源的按字節(jié)范圍加鎖，以最大程度滿足應(yīng)用系統(tǒng)的并發(fā)訪問要求。

范圍鎖中的范圍，還可以非“字節(jié)”為單位進行擴展，如描述條帶、塊等。

因加鎖的粒度不再為“是”或“非”，而是眾多隨機的、可能重疊或相鄰的、離散的區(qū)間，每個區(qū)間又可能存在不同的持有者(以下簡稱owner)，故范圍鎖數(shù)據(jù)結(jié)構(gòu)的組織遠比非范圍鎖要復(fù)雜，其加鎖性能也大幅下降。

現(xiàn)有技術(shù)中組織范圍鎖數(shù)據(jù)結(jié)構(gòu)的方案可以通過紅黑樹實現(xiàn)，具體實現(xiàn)可以是：

將所有區(qū)間組織到紅黑樹中，利用平衡二叉樹的特性加速區(qū)間的查找。這樣的紅黑樹也叫區(qū)間樹，典型的區(qū)間樹如圖1所示。在區(qū)間樹中，每個節(jié)點至少要包含三個屬性：

區(qū)間信息：區(qū)間的起始端點(start)和結(jié)束端點(end)，如圖1中的第一個節(jié)點[5,10]，其中起始端點為5、結(jié)束端點為10；

最大端點(MaxEnd)：記錄了本節(jié)點和本節(jié)點所有子節(jié)點中最大的端點值。所以，[start,MaxEnd]描述了本節(jié)點和右子樹所能描述的最大區(qū)間

持有者列表(OwnerList)：記錄了當前持有這個區(qū)間的所有持有者信息，一個持有者即是這個區(qū)間的申請者。

使用紅黑樹，可以獲得O(logn)的查找性能，適用于大規(guī)格的分布式系統(tǒng)中。為了查找沖突，需要找到樹中所有與給定區(qū)間重疊的區(qū)間，因為樹中重疊的區(qū)間可能分布在不同的分支中，故可能需要遍歷多個分支才能完成這個查找，最壞情況下需要遍歷整棵樹(例如申請的區(qū)間很大，與樹中所有區(qū)間都重疊)。綜上：通過紅黑樹組織的數(shù)據(jù)結(jié)構(gòu)記錄范圍鎖后，如果再對一個新的范圍加鎖時，需要遍歷紅黑樹表中的多棵樹和多個分支，所以會造成操作繁復(fù)不便實現(xiàn)的問題。

發(fā)明內(nèi)容

本發(fā)明提供一種范圍鎖的實現(xiàn)方法及裝置，本發(fā)明所提供的方法和裝置解決現(xiàn)有技術(shù)中通過紅黑樹組織的數(shù)據(jù)結(jié)構(gòu)記錄范圍鎖后，如果再對一個新的范圍加鎖時，需要遍歷紅黑樹表中的多棵樹和多個分支，所以會造成操作繁復(fù)不便實現(xiàn)的問題。

第一方面，提供一種范圍鎖的實現(xiàn)方法，該方法包括：

接收第一請求，其中，所述第一請求包含第一區(qū)間的區(qū)間信息和鎖權(quán)限信息；

將所述第一區(qū)間與本地存儲的已授權(quán)區(qū)間進行比對；

若所述第一區(qū)間是所述已授權(quán)區(qū)間中第二區(qū)間的子集，則根據(jù)預(yù)設(shè)的沖突判斷規(guī)則確定所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息是否沖突；

如果所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息不沖突，則返回所述第一區(qū)間的區(qū)間信息和鎖權(quán)限信息。

結(jié)合第一方面，在第一種可能的實現(xiàn)方式中，所述已授權(quán)區(qū)間的區(qū)間信息和鎖權(quán)限信息以紅黑樹的方式記錄；

所述方法還包括：將所述第一區(qū)間的區(qū)間信息和鎖權(quán)限信息加入到紅黑樹中。

結(jié)合第一方面，或者第一方面的第一種可能的實現(xiàn)方式，在第二種可能的實現(xiàn)方式中，當所述已授權(quán)區(qū)間有多個時，其中，任意兩個已授權(quán)區(qū)間存在重疊部分，則所述任意兩個已授權(quán)區(qū)間的鎖權(quán)限信息不沖突。

結(jié)合第一方面，或者第一方面的第一至第二種可能的實現(xiàn)方式，在第三種可能的實現(xiàn)方式中，所述鎖權(quán)限信息包括：對數(shù)據(jù)執(zhí)行讀操作或?qū)懖僮鞯逆i權(quán)限信息。

結(jié)合第一方面，或者第一方面的第一至第三種可能的實現(xiàn)方式，在第四種可能的實現(xiàn)方式中，根據(jù)預(yù)設(shè)的沖突判斷規(guī)則確定所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息是否有沖突包括：

當所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息不相同，則確定所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息沖突；

當所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息相同，則確定第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息是否為讀取操作，如果是，則確定所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息不沖突；否則，所述第一區(qū)間的鎖權(quán)限信息與所述第二區(qū)間的鎖權(quán)限信息沖突。

結(jié)合第一方面，或者第一方面的第一至第四種可能的實現(xiàn)方式，在第五種可能的實現(xiàn)方式中，該方法還包括：

若所述已授權(quán)區(qū)間中不包含所述第一區(qū)間，則返回所述第一區(qū)間的區(qū)間信息和鎖權(quán)限信息；或