一種空間資料庫中基於距離的自適應頁面替換方法
2023-08-04 17:52:46
專利名稱：一種空間資料庫中基於距離的自適應頁面替換方法
技術領域：
本發明屬於空間資料庫技術領域，具體涉及一種空間資料庫中自適應頁面替換方法。
背景技術：
空間資料庫是當今的研究熱點之一，也是一個具有廣闊發展前景的技術領域，緩存頁面替換策略也是當前的研究熱點，空間資料庫需要特殊的頁面替換策略提高緩存命中率以減少磁碟的讀寫操作，本發明所涉及的正是以上兩個領域的交叉。磁碟讀寫是影響空間資料庫系統性能的關鍵因素。現有的替換策略均從從數據訪問的時間局部性角度出發來設計。如選擇當前緩存中最久沒有被訪問的頁面進行替換的 LRU策略，選擇重用距離(頁面最後一次訪問與倒數第二次訪問之間的距離差)大的頁面進行替換的LIRS策略，同時考慮頁面訪問時間與頻率的ARC策略。然而在空間資料庫中，採用的數據組織和查詢不同於基於RDBMS的一般商業應用，從數據訪問的角度看，除了具備時間局部性，還具有很強的空間局部性，一段數據被訪問後，那麼和它地理位置鄰近的數據很可能就要被訪問。空間數據組織結構有兩種——R樹和Voronoi圖。Voronoi圖以其良好的空間劃分性質，極快的查詢處理速度贏得了廣泛關注。如圖1，給定一系列目標節點，Voronoi圖根據這些點把地圖劃分成互不相交的區域(Voronoi格)，而且對任意查詢點，其最近鄰一定是該點所屬區域的生成點(generator)。Voronoi圖的這種性質，使其在處理最近鄰(NN) 查詢時比採用R樹等其他方式組織具有顯著性能優勢；同時，它所需要更大的存儲空間。在Voronoi圖組織的空間資料庫中進行各種NN查詢時，數據訪問的空間局部性表現得特別強。例如我們執行一個2NN查詢，查詢點所在Voronoi格被訪問後，其周圍鄰近的那些Voronoi格都一定會被訪問。此外，對於各類kNN查詢，不同的k值對搜索空間大小差異非常大，使得LIRS等需要預設參數的緩存替換策略的命中率受到影響。在Voronoi圖存儲結構中，每個頁面都會記錄該Voronoi格生成點的坐標信息。所以在執行替換策略時可以根據坐標點等信息選擇替換的頁面。
發明內容
本發明針對空間資料庫訪問的時空局部性，提出一種基於距離的自適應的頁面替換方法(策略AELIRS)，以解決LRU、LIRS、ARC等策略對空間局部性工作集不友好的缺點。本發明提出的空間資料庫的頁面替換方法，在頁面命中時，更新頁面在隊列中的位置與等級信息，更新隊列的目標容量大小；在頁面失效時，選擇與上一次訪問頁面所記錄生成點的空間距離最遠的點所在的頁面進行替換，並更新隊列中頁面信息與等級信息，並更新隊列的目標容量大小；最後約束隊列的大小來節省空間。通過動態調整隊列的目標容量，本發明很好地提高了緩存的命中表現。本發明頁的面替換策略AELIRS中，管理隊列中的頁面有兩種等級低級與高級。而管理隊列如圖2所示，主要有兩個隊列隊列一負責管理一定時間內的所有頁面信息，包括這段時間內移出緩存的頁面信息。而隊列二隻管理在緩存中記錄內容的低級頁面信息。首先對策略執行過程中的一些操作進行定義。定義1.操作隊列剪枝移除隊列一中隊列頭部的低級頁面信息並把其中在緩存中有記錄的頁面信息移至隊列二尾部，直到隊列一頭部是高級頁面信息。定義2.動態調整操作當隊列二容量小於隊列二的目標容量時，把隊列一頭部頁面降級為低級頁面，進行隊列剪枝操作，直到隊列二容量等於其目標容量。定義3.隊列約束操作當隊列一容量大於隊列一的控制容量時，刪除隊列一中接近頭部的沒有在緩存中記錄其內容的頁面信息，直到隊列一容量等於其的控制容量。本發明的詳細描述如下
(1)設定策略管理隊列一的控制容量和隊列二的目標容量；
(2)空間資料庫發起頁面請求，把請求頁面號發送至緩存；緩存根據頁面號碼，判斷該頁面內容是否在緩存中有記錄；
(3)若緩存中記錄該頁面，則執行命中頁面管理；若緩存中沒有記錄該頁面，則執行替換頁面選擇和失效頁面管理；
(4)把請求頁面加載到緩存中，記錄下請求頁面記錄的坐標信息；
(5)執行隊列約束操作；
本發明中，所述執行命中管理操作，具體步驟如下
(1)判斷隊列一中是否含有請求頁面信息並返回頁面信息等級。(2)若隊列一含請求頁面，則將隊列一中請求頁面信息移至隊列一尾，此時若該頁面是高級，則進行隊列剪枝，否則就刪除隊列二中該頁面信息，並進行動態調整。(3)若隊列一不含請求頁面，則將隊列二中請求頁面信息移至隊列一與隊列二尾部，並增大隊列二的目標容量。本發明中，所述失效頁面管理操作，具體步驟如下
(1)判斷隊列一中是否含有請求頁面信息；(2)若步驟(1)回答含有請求頁面信息，則執行失效駐隊頁面管理；否則執行失效離隊頁面管理。本發明中，所述替換頁面選擇的步驟如下
(1)選擇管理隊列二中選擇與上一次訪問頁面空間距離最遠的頁面從隊列二中刪除； (2)在緩存移除步驟(1)選擇頁面的內容。所述執行命中管理操作中，所述命中高級頁面管理的步驟如下 (1)把隊列一中請求頁面信息移至隊列一尾；(2)進行隊列剪枝。所述執行命中管理操作中，所述命中低級頁面管理的步驟如下
(1)把隊列一中請求頁面信息移至隊列一尾，並把設置為高級頁面信息；(2)刪除隊列二中的請求頁面信息；(3)進行動態調整。所述執行命中管理操作中，所述命中離隊頁面管理的步驟如下
(1)把隊列二中請求頁面信息移至隊列一與隊列二尾部；(2)增大隊列二的目標容量。本發明中，所述失效頁面管理操作中，所述失效駐隊頁面管理的步驟如下(1)把隊列一中請求頁面信息移至隊列一尾，並把設置為高級頁面信息；(2)減少隊列二的目標容量；(3)進行動態調整。
本發明中，所述失效頁面管理操作中，所述失效離隊頁面管理的步驟如下把請求頁面信息加載至隊列一與隊列二尾，並設置為低級頁面信息。將實驗模擬得到的數據繪製成四幅圖(見說明書附圖3-6)，通過附圖可以很清楚地驗證本發明始終能適應不同大小的查詢空間。相比於其它頁面替換策略而言，無論查詢空間與緩存大小如何變化，本發明命中率始終是最高的。並可以解決LRU、URS、ARC等策略對空間局部性工作集不友好的缺點。
圖1顯示了本發明所針對空間資料庫的組織結構Voronoi圖。圖2顯示了本發明的兩個管理隊列及三種頁面信息類型。圖3顯示了在緩存容量為訪問頁面總數的1%時iNN查詢中本發明(AELIRS)與其它三種常用頁面替換策略A增大在相對命中率的比較。圖4顯示了在緩存容量為訪問頁面總數的5%時jNN查詢中本發明(AELIRS)與其它三種常用頁面替換策略A增大在相對命中率的比較。圖5顯示了在緩存容量為訪問頁面總數的20%時，iNN查詢中本發明(AELIRS)與其它三種常用頁面替換策略A增大在相對命中率的比較。圖6顯示了 iNN查詢中i在廣100間隨機變化時，本發明(AELIRS)與其它三種常用頁面替換策略隨緩存容量增大在相對命中率的比較。圖7顯示了某個請求發出前兩個隊列的狀態。圖8顯示了訪問頁面/73後兩個隊列的狀態。圖9顯示了隊列二目標容量為2時訪問頁面/72後兩個隊列的狀態。圖10顯示了隊列二目標容量為4時訪問頁面/72後兩個隊列的狀態。圖11顯示了訪問頁面A後兩個隊列的狀態。圖12顯示了隊列二目標容量為3時訪問頁面/74後兩個隊列的狀態。圖13顯示了訪問頁面/77後兩個隊列的狀態。圖14顯示了訪問頁面&並約束隊列一大小為5後兩個隊列的狀態。
具體實施例方式下面結合實施例子來詳細介紹本發明所述的空間資料庫中基於距離的自適應頁面替換策略的執行過程。其中空間資料庫存儲的是如圖1所示的Voronoi圖，而緩存能存儲5個頁面的內容。1、設定隊列一的控制容量為5個頁面信息，隊列二的目標容量為3個頁面信息 (目標容量是在不停變化的，所以起始值只影響前面有限的請求)。2、空間資料庫提出具體的頁面請求並把請求的頁面號碼發送至緩存。緩存接收請求，判斷緩存中是否存在請求頁面與隊列一中是否含有該頁面信息。3、根據請求的頁面不同分情況處理。假設當前管理隊列的狀態如圖7所示，表示儲存生成點是的Voronoi格的頁面。3. 1、若請求的是/73頁面，該頁面在緩存和隊列一中。所以把/73移動至隊列一尾部，由於這時隊列一頭部的頁面等級不是高級，所以執行隊列剪枝操作。如圖8所示，隊頭頁面變成了 A；。若請求的是/72，該頁面在緩存和隊列一中，則刪除/72頁面在隊列二中的信息，並把隊列一中P2頁面信息移動至隊列一頭部，並設置/72頁面為高級頁面，下面有兩種情況
假設這時隊列二的目標容量是2。由於隊列二容量等於目標容量，所以不用動態調整操作。最終結果如圖9。假設這時隊列二的目標容量是4。則需要進行動態調整操作。最終結果如圖10所
7J\ ο3. 2、若請求的是&頁面，則在緩存中存有該頁面內容，而隊列一中沒有該頁面信息。只需把隊列二中A頁面的信息移至隊列一與隊列二的尾部，並增大隊列二的目標容量 (假設之前目標容量是2，這步執行完後就是3 了)，結果如圖11所示。3. 3、若請求的是/74頁面並且這時隊列二的目標容量為3，在緩存中沒有該頁面內容，而隊列一中有該頁面信息。首先，在隊列二中選擇與上次訪問的頁面距離最遠的頁面進行替換。上次訪問的頁面是隊列一尾部的頁面/V而在圖2裡/ 、仏、A離A5最遠的是A。， 所以把/ 同時從隊列二與緩存中移除。然後將請求的P4頁面信息放入隊列一中，並將該頁面設置成高級頁面。這時目標容量為3而隊列二容量為2，所以把隊列一頭部的仏頁面降級並移至隊列二的尾部，然後進行隊列剪枝操作，最終結果如圖12所示。3. 4、若請求的是/77頁面，而緩存與隊列二裡面都沒有該頁面信息。首先在隊列二中選擇與上次訪問的A5頁面距離最遠的頁面/71(|進行替換，把/71(|同時從隊列二與緩存中移除。把請求頁面信息放入隊列一尾部，設置其級別為低級。結果如圖13所示。4、若上一步執行的是3. 3,3. 4，則需要把請求的頁面信息加載到緩存中。接著訪問頁面內容，並且把頁面內的生成點坐標記錄到隊列一與隊列二中的相應頁面信息中。5、執行隊列約束操作(隊列一的約束容量為開始時設定的5)。若上面執行是步驟 3.4 (圖13)的例子，則在這一步需要刪除圖13隊列一中的A。最終結果如圖14。以上就是本發明的詳細步驟。下面通過實驗模擬來驗證本發明比常用的LRU、ARC、 LIRS算法都要好。實驗使用道路網絡中的Voronoi圖iNN查詢並使用了兩組真實中的San Joaquin 道路網絡，其中共有18263個路口和23874條道路。隨機選擇其中的0. 4%作為V圖的生成點。而實驗結果都是經過10000次iNN查詢得出的。實驗中緩存大小則是按照佔數據集總頁面大小的百分比設置的。本發明開始時設定隊列一的控制容量為緩存容納頁面個數的兩倍，隊列二的目標容量為緩存容納頁面個數的10%。如圖3、4、5所示，在緩存容量比較小(1%)、一般大小(5%)、比較大(20%)的情況下， 隨著搜索空間α值)的增大，本發明(AELIRS)始終比其他頁面替換策略要好，而且優勢明
Mo如圖6所示，在A值在廣100間隨機選擇時，無論緩存容量如何變化，本發明 (AELIRS)始終優於其他頁面替換策略。
權利要求
1.一種空間資料庫中基於距離的自適應頁面替換方法，其特徵在於具體步驟如下(1)設定策略管理隊列一的控制容量和隊列二的目標容量；(2)空間資料庫發起頁面請求，把請求頁面號發送至緩存；緩存根據頁面號碼，判斷該頁面內容是否在緩存中有記錄；(3)若緩存中記錄該頁面，則執行命中頁面管理；若緩存中沒有記錄該頁面，則執行替換頁面選擇和失效頁面管理；(4)把請求頁面加載到緩存中，記錄下請求頁面記錄的坐標信息；(5)執行隊列約束操作；其中，涉及的一些操作定義如下定義1、隊列剪枝操作移除隊列一中隊列頭部的低級頁面信息，並把其中在緩存中有記錄的頁面信息移至隊列二尾部，直到隊列一頭部是高級頁面信息；定義2、動態調整操作當隊列二容量小於隊列二的目標容量時，把隊列一頭部頁面降級為低級頁面，進行隊列剪枝操作，直到隊列二容量等於其目標容量；定義3、隊列約束操作當隊列一容量大於隊列一的控制容量時，刪除隊列一中接近頭部的沒有在緩存中記錄其內容的頁面信息，直到隊列一容量等於其的控制容量。
2.根據權利要求1所述的方法，其特徵在於步驟(3)中所述命中頁面管理的步驟如下(1)判斷隊列一中是否含有請求頁面信息並返回頁面信息等級；(2)若步驟(1)回答含有請求頁面信息並且頁面為高級頁面信息，則執行命中高級頁面管理；若步驟(1)回答含有請求頁面信息並且頁面為低級頁面信息，則執行命中低級頁面管理；若步驟(1)回答不含請求頁面信息，則執行命中離隊頁面管理。
3.根據權利要求1所述的方法，其特徵在於步驟(3)中所述替換頁面選擇的步驟如下(1)選擇管理隊列二中選擇與上一次訪問頁面空間距離最遠的頁面從隊列二中刪除；(2)在緩存移除步驟(1)選擇頁面的內容。
4.根據權利要求1所述的方法，其特徵在於步驟(3)中所述失效頁面管理的步驟如下(1)判斷隊列一中是否含有請求頁面信息；(2)若步驟(1)回答含有請求頁面信息，則執行失效駐隊頁面管理；否則執行失效離隊頁面管理。
5.根據權利要求2所述的方法，其特徵在於步驟(2)中 所述命中高級頁面管理的步驟如下把隊列一中請求頁面信息移至隊列一尾； 進行隊列剪枝；所述命中低級頁面管理的步驟如下(1)把隊列一中請求頁面信息移至隊列一尾，並把設置為高級頁面信息；(2)刪除隊列二中的請求頁面信息；(3)進行動態調整；所述命中離隊頁面管理的步驟如下(1)把隊列二中請求頁面信息移至隊列一與隊列二尾部；(2)增大隊列二的目標容量。
6.根據權利要求4所述的方法，其特徵在於步驟(2)中所述失效駐隊頁面管理的步驟如下(1)把隊列一中請求頁面信息移至隊列一尾，並把設置為高級頁面信息；(2)減少隊列二的目標容量；(3)進行動態調整。
7.根據權利要求4所述的方法，其特徵在於步驟(2)中所述失效離隊頁面管理的步驟如下把請求頁面信息加載至隊列一與隊列二尾，並設置為低級頁面信息。
全文摘要
本發明屬於空間資料庫技術領域，具體涉及一種空間資料庫中基於距離的自適應頁面替換方法。其步驟為首先設定策略管理隊列的目標容量及約束容量；由空間資料庫提出具體頁面的請求；緩存接收到請求後，檢查緩存中是否存在請求頁面內容，進行不同處理；接著加載請求頁面的內容到緩存中並記錄請求頁面的坐標信息；最後約束管理隊列容納頁面信息的個數。本發明命中率高，並可以解決LRU、LIRS、ARC等策略對空間局部性工作集不友好的缺點。
文檔編號G06F17/30GK102184236SQ201110124989
公開日2011年9月14日 申請日期2011年5月16日 優先權日2011年5月16日
發明者孫未未, 朱良, 陳坤傑, 陳楚南 申請人:復旦大學