採用多個頁替換算法的高速緩存的製作方法

2023-04-28 11:14:41

專利名稱：採用多個頁替換算法的高速緩存的製作方法
技術領域：
本發明涉及高速緩存，尤其涉及採用多個頁替換算法的高速緩存。
背景技術：
計算機系統及相關技術影響社會的許多方面。的確，計算機系統處理信息的能力已轉變了我們生活和工作的方式。現在，計算機系統如今通常執行在計算機系統出現以前手動執行的許多任務(例如，文字處理、日程安排、會計等)。最近，計算機系統彼此耦合併耦合到其他電子設備以形成計算機系統及其他電子設備可在其上傳輸電子數據的有線和無線計算機網絡。因此，許多計算任務的執行分布在多個不同的計算機系統和/或多個不同的計算環境中。計算機系統採用高速緩存來加速對文件的訪問。在一應用請求訪問盤上的文件時，計算機系統(例如，作業系統)可以檢索該文件(或該文件的所請求的部分(頁))並將該文件(或該部分)存儲在高速緩存中(例如，在系統存儲器中)。對該文件的後續訪問隨後可通過訪問高速緩存中(而非來自盤)的文件來執行。因為訪問高速緩存大大快於訪問盤，所以尤其是在頻繁訪問文件時，性能得到改進。可以使用各種不同的頁替換算法來實現高速緩存。一種常見的算法是最久未使用(LRU)算法。在LRU算法中，各頁基於它們被訪問的最後時間而被存儲在高速緩存中。在要對一個頁進行高速緩存(並且高速緩存已經充滿)時，LRU算法將確定高速緩存中哪一頁是最久未使用的並且丟棄該頁來為要進行高速緩存的頁騰出空間。例如，情況可以是:高速緩存存儲了三個頁:10秒之前訪問過的頁1、20秒之前訪問過的頁2、以及30秒之前訪問過的頁3。因而，在要對新頁進行高速緩存時，頁3將被丟棄來為該要被高速緩存的新頁騰出空間，因為頁3是最久未訪問的。另一常見算法是LRU2算法，它是LRU算法的變型。除了對頁的倒數第二次訪問被用來確定要從高速緩存中丟棄哪一頁之外，LRU2算法類似於LRU算法。使用與以上相同的示例，情況是:10秒和2分鐘之前訪問過的頁1、20秒和21秒之前訪問過的頁2、以及30秒和35秒之前訪問過的頁3。如此，在要對新頁進行高速緩存時，使用LRU2算法，頁I將被丟棄，因為頁2的倒數第二次訪問是最久的。LRU算法的另外變型包括LRU3 (它使用倒數第三次訪問)、LRU4 (它使用倒數第四次訪問)，等等。在單次訪問許多文件時，如在執行文件掃描時，LRU算法發生了一個問題。例如，在文件掃描期間(例如，惡意軟體掃描)，每一文件都被訪問。因而，在短期內不太可能被再次訪問的文件的各頁被高速緩存。對這些頁進行的高速緩存使得可能被再次訪問的其他頁被從高速緩存中丟棄。出於這一原因，通常使用LRU2而非LRU，因為LRU2查看倒數第二次訪問而非最後訪問來確定從高速緩存中丟棄哪一頁。對於高速緩存，作業系統提供兩個一般的I/O模式，在本說明書中它們被稱為緩衝I/o和無緩衝I/O。緩衝I/O指的是由作業系統通過使用高速緩存技術(即I/O獲得的數據被高速緩存在存儲器中)來處理的I/o請求。無緩衝I/O指的是由作業系統在不採用高速緩存的情況下(即，所請求的數據總是從盤獲取的)處理的I/o請求。因此，一應用可以請求作業系統通過使用緩衝I/o請求或無緩衝I/O請求來獲得數據。—些類型的文件總是經由無緩衝I/O來訪問的。例如，在主存了虛擬機的系統中，虛擬機經由無緩衝I/O來訪問虛擬盤。在一個環境中，存在著許多虛擬機從中執行的父虛擬盤。父虛擬盤存儲了每一虛擬機所使用的作業系統和應用。另外，可為每一虛擬機創建子虛擬盤。每一虛擬機使用它的子虛擬盤來存儲虛擬機專用數據(如在該虛擬機上創建的文字處理文檔或該虛擬機想要對父虛擬盤作出的任何其他變更)。換言之，父虛擬盤是只讀虛擬盤。相反，每當虛擬機必須修改父虛擬盤的內容(例如，在虛擬盤上存儲新文件)時，對該虛擬機的子虛擬盤作出該修改。子虛擬盤還可被稱為差別(differencing)盤。虛擬機經由無緩衝I/O訪問父虛擬盤以及其子虛擬盤。因此，這些虛擬盤的被訪問的各頁沒有被高速緩存在其中主存這些虛擬機的計算機系統上。因為在同一伺服器上執行的許多虛擬機從父虛擬盤中訪問許多相同的頁，所以I/o性能可能受損。換言之，每一次虛擬機從父虛擬盤訪問特定頁時，該頁必須被從物理盤(而不是從高速緩存)訪問。在虛擬機環境中，物理盤通常在物理上與該計算機系統分開(例如，在通過網絡連接到伺服器的存儲陣列中)，從而造成更大的性能下降。圖1 (現有技術)示出了用於主存虛擬機的典型的計算機環境100。環境100包括各自連接到存儲陣列102的多個伺服器節點(101a-101n)。伺服器節點IOla-1Oln中的每一個主存了通過連接103訪問存儲在存儲陣列102中的父虛擬盤104的多個虛擬機。連接103可以是伺服器節點與存儲陣列102之間的任何類型的連接，包括直接連接或網絡連接。除了父虛擬盤104之外，伺服器節點IOla-1Oln中的每一個上的每一虛擬機的子虛擬盤也被存儲在存儲陣列102上。在虛擬機訪問虛擬盤(父或子虛擬盤)時，經由無緩衝I/O執行該訪問(B卩，通過訪問存儲陣列102，而不是本地存儲器中的高速緩存)。因為許多虛擬機(例如，每伺服器節點1000個虛擬機)訪問存儲在存儲陣列102上的父虛擬盤和它們各自的子虛擬盤，所以通過連接103對存儲陣列102進行了大量的I/O請求。即使同一伺服器節點上的各虛擬機訪問父虛擬盤的相同頁時，情況也是如此，因為這些訪問是經由無緩衝I/O執行的，使得所訪問的頁沒有被高速緩存在對應的伺服器節點的存儲器中。

發明內容
本發明延及用於實現使用多個頁替換算法的高速緩存的方法、系統以及電腦程式產品。通過實現多個算法，可以實現更高效的高速緩存，其中最可能被再次訪問的各頁被保留在高速緩存中。多個頁替換算法可被用於任何高速緩存中，包括用於對經由緩衝I/o訪問的各頁進行高速緩存的作業系統高速緩存以及用於對經由無緩衝I/o訪問的各頁(如虛擬機作出的對虛擬盤的訪問)進行高速緩存的高速緩存。 在一個實施例中，通過使用第一頁替換算法替換高速緩存的第一邏輯部分中的頁來維護該第一邏輯部分，實現了採用多個頁替換算法的高速緩存。使用第二頁替換算法替換高速緩存的第二邏輯部分中的頁，該第二邏輯部分也得到維護。在要替換第一邏輯部分中的第一頁時，如果第一頁至少被訪問了要被認為能高速緩存在第二邏輯部分中所需的最少次數，則將該第一頁從高速緩存的第一邏輯部分移至第二邏輯部分。提供本發明內容以便以簡化的形式介紹將在以下的具體實施例中進一步描述的一些概念。本概述不旨在標識出所要求保護的主題的關鍵特徵或必要特徵，也不旨在用於幫助確定所要求保護的主題的範圍。本發明的附加特徵和優點將在以下描述中敘述，且其一部分根據本說明書將是顯而易見的，或可通過對本發明的實踐來獲知。本發明的特徵和優點可通過在所附權利要求書中特別指出的工具和組合來實現和獲得。本發明的這些和其他特徵將通過以下描述和所附權利要求書變得更加顯而易見，或可通過對下文中所述的本發明的實踐來領會。


為了描述可獲得本發明的上述和其它優點和特徵的方式，將通過引用附圖中示出的本發明的具體實施例來呈現以上簡要描述的本發明的更具體描述。可以理解，這些附圖僅描述本發明的典型實施例，從而不被認為是對其範圍的限制，本發明將通過使用附圖用附加特徵和細節來描述和說明，在附圖中:圖1示出了其中主存了虛擬機的現有技術計算機環境；圖2示出了便於實現使用多個頁替換算法的高速緩存的示例計算機體系結構；圖3A和3B示出了採用多個頁替換算法的高速緩存的示例性邏輯安排；圖4示出了用於實現採用多個頁替換算法的高速緩存的示例性方法的流程圖；以及圖5示出了其中可以使用採用多個頁替換算法的高速緩存的示例性伺服器體系結構。
具體實施例方式本發明延及用於實現使用多個頁替換算法的高速緩存的方法、系統以及電腦程式產品。通過實現多個算法，可以實現更高效的高速緩存，其中最可能被再次訪問的各頁被保留在高速緩存中。多個頁替換算法可被用於任何高速緩存中，包括用於對經由緩衝I/o訪問的各頁進行高速緩存的作業系統高速緩存以及用於對經由無緩衝I/o訪問的各頁(如虛擬機作出的對虛擬盤的訪問)進行高速緩存的高速緩存。在一個實施例中，通過使用第一頁替換算法替換高速緩存的第一邏輯部分中的頁來維護該第一邏輯部分，實現了採用多個頁替換算法的高速緩存。使用第二頁替換算法替換高速緩存的第二邏輯部分中的頁，該第二邏輯部分也得到維護。在要替換第一邏輯部分中的第一頁時，如果第一頁至少被訪問了要被認為能高速緩存在第二邏輯部分中所需的最少次數，則將該第一頁從高速緩存的第一邏輯部分移至第二邏輯部分。本發明的各實施例可包括或利用專用或通用計算機，該專用或通用計算機包括諸如例如一個或多個處理器和系統存儲器等計算機硬體，如以下更詳細討論的。本發明範圍內的各實施例還包括用於承載或存儲計算機可執行指令和/或數據結構的物理和其他計算機可讀介質。這樣的計算機可讀介質可以是可由通用或專用計算機系統訪問的任何可用介質。存儲計算機可執行指令的計算機可讀介質是計算機存儲介質(設備)。承載計算機可執行指令的計算機可讀介質是傳輸介質。由此，作為示例而非限制，本發明的各實施例可包括至少兩種顯著不同的計算機可讀介質:計算機存儲介質(設備)和傳輸介質。計算機存儲介質(設備)包括RAM、ROM、EEPROM、CD-ROM、固態驅動器(SSD)(如基於RAM)、快閃記憶體、相變存儲器(PCM)、其他類型的存儲器、其他光碟存儲、磁碟存儲或其他磁存儲設備、或可用於存儲計算機可執行指令或數據結構形式的所需程序代碼裝置且可由通用或專用計算機訪問的任何其他介質。「網絡」被定義為允許在計算機系統和/或模塊和/或其他電子設備之間傳輸電子數據的一個或多個數據鏈路。當信息通過網絡或另一個通信連接(硬連線、無線、或者硬連線或無線的組合)傳輸或提供給計算機時，該計算機將該連接適當地視為傳輸介質。傳輸介質可包括可用於攜帶計算機可執行指令或數據結構形式的所需程序代碼裝置並可由通用或專用計算機訪問的網絡和/或數據鏈路。上述的組合也應被包括在計算機可讀介質的範圍內。此外，在到達各種計算機系統組件之後，計算機可執行指令或數據結構形式的程序代碼裝置可從傳輸介質自動傳輸到計算機存儲介質(設備)(或反之亦然)。例如，通過網絡或數據連結接收到 的計算機可執行指令或數據結構可被緩存在網絡接口模塊(例如，「NIC」)內的RAM中，然後最終被傳輸到計算機系統RAM和/或計算機系統處的較不易失性的計算機存儲介質(設備)。因而，應當理解，計算機存儲介質(設備)可被包括在還利用(甚至主要利用)傳輸介質的計算機系統組件中。計算機可執行指令例如包括，當在處理器處執行時使通用計算機、專用計算機、或專用處理設備執行某一功能或某組功能的指令和數據。計算機可執行指令可以是例如二進位代碼、諸如彙編語言之類的中間格式指令、或甚至原始碼。儘管用結構特徵和/或方法動作專用的語言描述了本主題，但可以理解，所附權利要求書中定義的主題不必限於上述特徵或動作。相反，上述特徵和動作是作為實現權利要求的示例形式而公開的。本領域的技術人員將理解，本發明可以在具有許多類型的計算機系統配置的網絡計算環境中實踐，這些計算機系統配置包括個人計算機、臺式計算機、膝上型計算機、消息處理器、手持式設備、多處理器系統、基於微處理器的或可編程消費電子設備、網絡PC、小型計算機、大型計算機、行動電話、PDA、平板、尋呼機、路由器、交換機等等。本發明也可在其中通過網絡連結(或者通過硬連線數據鏈路、無線數據鏈路，或者通過硬連線和無線數據鏈路的組合)的本地和遠程計算機系統兩者都執行任務的分布式系統環境中實施。在分布式系統環境中，程序模塊可位於本地和遠程存儲器存儲設備中。圖2示出了便於實現使用多個頁替換算法的高速緩存的示例計算機體系結構200。參考圖2,計算機體系結構200包括計算機系統201。計算機系統201可以通過諸如例如區域網(「LAN」)、廣域網(「WAN」)以及甚至網際網路等網絡被連接到其他計算機系統。因此，計算機系統201以及任何其他連接的計算機系統及其組件都可以創建消息相關數據並通過網絡交換消息相關數據(例如，網際協議(「IP」)數據報和利用IP數據報的其他更高層協議，如傳輸控制協議(「 TCP 」)、超文本傳輸協議(「HTTP 」)、簡單郵件傳輸協議(「 SMTP 」)
O計算機系統201包括存儲202或連接到存儲202。例如，存儲202可以是內部硬碟驅動器或存儲陣列。存儲202可以儲存任何類型的數據，包括作業系統文件、應用文件、虛擬硬碟鏡像，等等。計算機系統201還包括高速緩存203。高速緩存203可以是用任何類型的快速訪問存儲介質來實現的，但通常被實現在存儲器(例如，存儲器204)中。計算機系統201可以表示典型的臺式、膝上型、平板、或其他可攜式計算機，在這些情況下，存儲202可以是內部硬碟驅動器。計算機系統201還可以表示伺服器集群的節點，在這種情況下，存儲202可以是一個或多個其他節點被連接到的存儲陣列(例如，類似於圖1的存儲陣列102)。因而，本發明的高速緩存技術可以應用於採用高速緩存的任何計算機環境內。圖3A示出了根據第一實施例的、高速緩存203如何可在邏輯上被配置成使用多個頁替換算法。雖然圖3描繪了鄰近存儲器的兩個部分，但各頁被高速緩存的實際位置並不重要。換言之，圖3A只描繪了高速緩存的邏輯結構。用於將各頁高速緩存在存儲器中的實際物理放置方案將取決於所使用的硬體的類型以及其他因素而變化。圖3A還示出了第一和第二部分是相同的大小，然而，在一些實施例中，各自的大小可以不同。圖3A中描繪的實施例採用了兩個頁替換算法。在第一邏輯級(301)上，使用LRU，並且在第二邏輯級(302)上，使用LRU2。第一邏輯級實現LRU (即，在一個頁是第一邏輯級中最久未使用的頁時，該頁被從第一邏輯級移除)。然而，在要替換第一邏輯級中的頁時，並非將該頁從高速緩存203中丟棄，而是首先檢查該頁以查看該頁的第二最近訪問何時發生。基於這一第二最近訪問並根據LRU2算法，該頁可被置於高速緩存203的第二邏輯級中。否則，如果第一邏輯級中的該頁在所監視的時間段期間尚未被訪問至少兩次，則該頁將被從高速緩存中丟棄。在圖3A中，頁的最近訪問被縮寫為MRA並且第二最近訪問被縮寫為2MRA。圖3A使用自一個訪問以來的持續時間(以秒為單位)來表示該訪問的發生，然而，同樣可以使用時間戳或標識訪問何時發生的其他方式。同樣，標識頁何時被訪問的信息可結合該頁來儲存(例如，作為元數據)、與該頁分開儲存(例如，在集中式數據結構中)、或以任何其他合適的方式來儲存。此外，另外的較不新近的訪問的發生也可被儲存(例如，在實現更高階的LRU(LRU3、LRU4等)時)。在其他實現中，可以採用鍊表，其中一個邏輯級中的頁在該列表內基於每一頁被最後訪問的時間來排序。在這樣的實現中，鍊表中的最後的頁是最久未使用的頁。因此，在邏輯級內實現每一頁替換算法的方式對本發明而言並非是必需的。如圖3A中所示，頁310被從盤訪問，並且待被高速緩存在高速緩存203中。對盤的訪問可以是讀或寫頁310。注意，頁310還可來自高速緩存203的另一邏輯級，諸如，在請求該頁時它已經被高速緩存在第二邏輯級的情況下。因為高速緩存203的第一邏輯級已充滿，所以必須丟棄來自第一邏輯級的頁來為頁310騰出空間。為了確定丟棄哪一頁，應用LRU算法來丟棄最久未使用的頁。在圖3A中，最久未使用的頁是頁1，因為頁I的MRA是11毫秒，這是第一邏輯級中的所有其他頁的MRA的最久值。並非從高速緩存203中丟棄頁1，而是首先將基於LRU2算法來確定頁I是否應被高速緩存在高速緩存203的第二邏輯級中。這通過比較頁I的第二最近訪問(2MRA)與第二邏輯級中高速緩存的其他頁的2MRA來完成。如果頁I不包括2MRA(例如，如果頁I在所監視的時間期間只被訪問了一次)或者如果它的2MRA是第二邏輯級中的其他頁的2MRA中的最久值，則它將被從高速緩存203中丟棄。否則，具有作為第二邏輯級中的其他頁的2MRA中的最久值的2MRA的頁將被丟棄來在第二邏輯級內為頁I騰出空間。
如圖3A所示，頁16具有作為第二邏輯級中的頁的最久值的2MRA (2秒)。另外，頁I的2MRA比頁16的2MRA更新近(12毫秒)。因此，頁I將被高速緩存在第二邏輯級中並且頁16將被丟棄。圖3B示出了在對頁310進行了高速緩存之後的高速緩存203。如圖所示，頁310出現在第一邏輯級，頁I已被移至第二邏輯級，並且頁16不再被高速緩存。作為另一示例，如果在對頁310進行了高速緩存之後要高速緩存另一頁，則頁2會被從第一邏輯級移除，因為它的MRA (10毫秒)是最久未使用的。因為頁2在所監視的時間期間尚未被訪問兩次，所以它不具有2MRA。因此，頁2會被從高速緩存203丟棄，而非被移至第二邏輯級。如果頁2具有大於I秒的2MRA，則將發生類似結果，因為第二邏輯級中的最久2MRA是I秒(頁11)。因此，在該示例中，LRU2算法會指示頁2將不被高速緩存在第二邏輯級中。注意，圖3A-3B只表示在邏輯上各頁如何被移至高速緩存203、在高速緩存203內轉移、以及從高速緩存203移除。在一些實施例中，在將頁從一個邏輯級移至另一個時，該頁在物理上實際上將不會移動。換言之，該頁在物理上將保留在高速緩存中的相同位置，但將在邏輯上移至另一位置(例如，通過與表示第二邏輯級的數據結構(例如，鍊表)相關聯並從表示第一邏輯級的數據結構(例如，鍊表)中移除)。在這樣的實施例中，圖3A-3B的示例可通過將頁16從高速緩存203中丟棄、將頁310高速緩存在頁16曾被高速緩存過的位置、並相應地更新任何數據結構來實現。在一些實施例中，可使用附加的邏輯級。例如，可在高速緩存203中實現採用LRU3算法(它使用第三最近訪問來確定頁替換)的第三邏輯級。在這樣的實施例中，從第二邏輯級丟棄的各頁可根據LRU3算法(假定這些頁被訪問了足夠次數(即，3次))被高速緩存在第三邏輯級。也可使用分別實現LRU4、LRU5的第四邏輯級、第五邏輯級等。在任何情況下，在將一個頁從一個級移除時，如果它被訪問了所需次數(例如，對於LRU2是兩次，對於LRU3是三次，對於LRU4是四次，等等)，則它可被認為能被高速緩存在下一級。在一些實施例中，在高速緩存203內實現的邏輯級的數量可以是可配置的設置。圖4示出了用於實現採用多個頁替換算法的高速緩存的示例性方法400的流程圖。將參考圖2、3A和3B來描述方法400。方法400包括使用第一頁替換算法來替換高速緩存的第一邏輯部分中的頁以維護該第一邏輯部分的動作401。例如，存儲器204中實現的高速緩存203可包括實現了諸如LRU算法等第一頁替換算法的第一邏輯部分301。方法400包括使用第二頁替換算法來替換高速緩存的第二邏輯部分中的頁以維護該第二邏輯部分的動作402。例如，高速緩存203可包括實現了諸如LRU2算法等第二頁替換算法的第二邏輯部分302。方法400包括確定第一邏輯部分中的第一頁要被替換的動作403。例如，響應於訪問來自盤的未經高速緩存的頁310的請求，可以確定第一邏輯部分301中的頁I要從該第一邏輯部分中被丟棄來為頁310騰出空間。可通過應用LRU算法來確定頁I是第一邏輯部分301中的最久未使用的頁來將頁I標識為要被替換。方法400包括確定第一頁至少已被訪問了要被認為能高速緩存在第二邏輯部分中所需的最小次數的動作404。例如，可以確定頁I已被訪問了至少兩次，如在第二邏輯部分302中實現的LRU2算法所需的。方法400包括將第一頁從高速緩存的第一邏輯部分移至第二邏輯部分的動作405。例如，頁I可從第一邏輯部分301移至第二邏輯部分302。移動頁I可包括在物理上將頁310在高速緩存內重新定位，或可包括在邏輯上移動頁I (如通過改變標識高速緩存的特定部分中的頁的數據結構內的指針或其他數據值)。雖然主要使用LRU和LRU2算法作為第一和第二頁替換算法的示例來描述了方法410，但本發明延及在方法400中使用任何其他兩種(或更多種)頁替換算法。例如，可以使用LRU、LRU2、LRU3、LRU4等的任何組合。此外，可在任何計算機環境內採用方法400以實現任何高速緩存。以下伺服器集群環境的示例只是其中可以採用本發明的高速緩存技術的環境的類型的一個示例。圖5示出了其中可以使用採用多個頁替換算法的高速緩存的示例性伺服器體系結構500。圖5包括伺服器501、502和503以及每一伺服器連接到的存儲陣列504。伺服器501-503中的每一個分別包括其中可實現高速緩存的存儲器501a-503a。在一些實施例中，伺服器501、502和503中的每一個可以是集群的節點。例如，每一伺服器可以主存多個虛擬機，每一虛擬機是從存儲在存儲陣列504上的父虛擬硬碟部署的。因為多個(例如，100個)虛擬機可能在給定伺服器上執行，所以父虛擬硬碟(它儲存每一虛擬機的作業系統鏡像)可能被頻繁訪問。具體而言，虛擬機中的許多可能頻繁訪問虛擬硬碟的相同頁。如上所述，對虛擬硬碟的訪問可作為(並且通常是作為)無緩衝I/o來執行的(意味著所訪問的頁未被進行高速緩存)。在本發明中，對虛擬硬碟的這些訪問是經由無緩衝I/o執行的，然而，可以實現一高速緩存(與用於緩衝I/O的高速緩存分開)(在此稱為塊高速緩存(block cache))來對經由無緩衝I/O訪問的各頁進行高速緩存。在使用Windows作業系統的一個示例中，緩衝I/O被使用LRU算法高速緩存在作業系統高速緩存(即，文件高速緩存)中。本發明可以實現分開的高速緩存(塊高速緩存)，以用於對經由無緩衝I/o訪問的各頁(如虛擬機所訪問的虛擬硬碟(父或子)的各頁)進行高速緩存。這些技術可同樣應用於其他作業系統或高速緩存方案。換言之，根據本發明，對無緩衝I/o的高速緩存可以在任何環境/作業系統中執行。如上所述，可以實現用於對經由無緩衝I/O訪問的各頁進行高速緩存的塊高速緩存以使用多個頁替換算法。在伺服器集群示例中，實現多個頁替換算法提高了塊高速緩存的效率(即，虛擬硬碟的被最頻繁訪問的更大數量的頁被維護在高速緩存中)。以此方式，對存儲陣列504的每秒I/O (IOPS)的數量在集群中得到了減少，因為一旦從存儲陣列504訪問了一個頁，它將被高速緩存在該節點上的塊高速緩存中，使得訪問該頁的後續請求(無論是由同一虛擬機還是該節點上的另一虛擬機)可通過訪問被高速緩存的頁而非訪問存儲陣列504上的頁來得到滿足。存儲陣列504可被通過網絡(或與高速緩存相比其他相對慢的連接)連接到伺服器501-503。這可減少1/0，從而極大地改進集群中虛擬機的性能。圖5示出了虛擬硬碟510被存儲在存儲陣列504上，且虛擬硬碟510的各部分(即，各頁)510a-510c被分別高速緩存在伺服器501-503中的每一個上。例如，部分510a可表示虛擬硬碟510的已被高速緩存以供在伺服器501上執行的虛擬機訪問的各頁。儘管並未示出，但伺服器501-503上的每一虛擬機的子虛擬盤也可被存儲在存儲陣列504上。與父虛擬盤的被高速緩存的各部分一起，這些子虛擬盤的各部分也可被高速緩存在對應虛擬機在其上執行的節點上。在本發明的各實施例中，各高速緩存可被同步。例如，因為存儲在存儲陣列504上的數據的相同頁可被高速緩存在不同節點處，所以對各節點之間的高速緩存進行同步是必要的。例如，如果一個頁被高速緩存在兩個或更多個節點上，並且被高速緩存的頁在這些節點之一上被更新，則其他節點上的高速緩存將需要被同步。高速緩存的同步可通過將對被高速緩存的頁的更新發送到其中對該同一頁進行了高速緩存的節點來執行，以使得這些更新被反映在該頁的每一高速緩存副本中。在其他實施例中，在所高速緩存的頁被更新時，這些更新可被寫到存儲陣列504中的虛擬盤，並且可以向該集群中的其他節點發送通知，以指示經更新的所高速緩存的頁的任何副本應被丟棄，從而使得對該頁的後續請求要通過從存儲陣列504訪問該頁來得到滿足。因此，本發明的技術可被用來實現用於對伺服器集群環境中的無緩衝I/O進行高速緩存的分布式高速緩存。這一同步可以按與在共同擁有的專利申請號12/97132、題為「Volumes And FileSystem In Cluster Shared Volumes (集群共享卷中的卷和文件系統)」中描述的類似方式來實現，該申請描述了用於使用oplock來協調集群的不同節點上的高速緩存的各實施例。在那一申請中描述的技術適用於緩衝I/O內容的高速緩存。類似技術可被應用在本發明中以對無緩衝I/O內容的高速緩存進行同步。本發明可具體化為其他具體形式而不背離其精神或本質特徵。所描述的實施例在所有方面都應被認為僅是說明性而非限制性的。因此，本發明的範圍由所附權利要求書而非前述描述指示。落入權利要求書的等效方案的含義和範圍內的所有改變被權利要求書的範圍所涵蓋。
權利要求
1.一種用於實現採用多個頁替換算法的高速緩存的方法，所述方法包括: 使用第一頁替換算法來替換高速緩存的第一邏輯部分中的頁以維護所述第一邏輯部分； 使用第二頁替換算法來替換所述高速緩存的第二邏輯部分中的頁以維護所述第二邏輯部分； 確定所述第一邏輯部分中的第一頁要被替換； 確定所述第一頁至少已被訪問了要被認為能高速緩存在所述第二邏輯部分中所需的最小次數；以及 將所述第一頁從所述高速緩存的所述第一邏輯部分移至所述第二邏輯部分
2.如權利要求1所述的方法，其特徵在於，所述第一頁替換算法是最久未使用(LRU)算法，並且所述第二頁替換算法是最久未使用2 (LRU2)算法。
3.如權利要求2所述的方法，其特徵在於，確定所述第一邏輯部分中的所述第一頁要被替換包括確定新頁要被添加到所述高速緩存的所述第一邏輯部分並且確定所述第一頁是所述第一邏輯部分中的最久未使用的頁。
4.如權利要求2所述的方法，其特徵在於，所述最小訪問次數是兩次，所述方法還包括: 在將所述第一頁從所述高速緩存的所述第一邏輯部分移至所述第二邏輯部分之前，確定所述第一頁的倒數第二次訪問比所述第二邏輯部分中的至少一個其他頁的倒數第二次訪問更加新近。
5.如權利要求4所述的方法，其特徵在於，將所述第一頁從所述高速緩存的所述第一邏輯部分移至所述第二邏輯部分包括從所述第二邏輯部分中移除另一個頁，其中所述另一個頁的倒數第二次訪問是所述第二邏輯部分中所有其他頁中的最久的。
6.如權利要求1所述的方法，其特徵在於，還包括: 維護所述高速緩存的一個或多個附加邏輯部分，其中所述高速緩存的所述一個或多個附加邏輯部分中的每一個附加邏輯部分使用與該附加邏輯部分之上的每一邏輯部分所不同的頁替換算法。
7.如權利要求6所述的方法，其特徵在於，所述高速緩存的所述一個或多個附加邏輯部分包括使用最久未使用3 (LRU3)頁替換算法的第三邏輯部分。
8.如權利要求1所述的方法，其特徵在於，所述高速緩存包括用於對由多個虛擬機訪問的一個或多個虛擬硬碟的部分進行高速緩存的塊高速緩存。
9.如權利要求1所述的方法，其特徵在於，維護所述高速緩存的第一和第二邏輯部分包括在經由無緩衝I/o訪問頁時，對這些頁進行高速緩存。
10.如權利要求8所述的方法，其特徵在於，所述塊高速緩存是在集群的節點上維護的。
11.一種包括一個或多個存儲有計算機可執行指令的計算機存儲設備的電腦程式產品，所述計算機可執行指令在被一個或多個處理器執行時，執行一種用於實現採用多個頁替換算法的高速緩存的方法，所述方法包括: 在邏輯上將高速緩存劃分成第一和第二邏輯部分； 在儲存在所述第一邏輯部分中的頁上實現最久未使用(LRU)頁替換算法；在儲存在所述第二邏輯部分中的頁上實現最久未使用2 (LRU2)頁替換算法； 其中如果根據所述LRU算法從所述第一邏輯部分移除的頁在所監視的時間跨度期間已被訪問了至少兩次，則這些頁被移至所述第二邏輯部分。
12.如權利要求11所述的電腦程式產品，其特徵在於，所述高速緩存是用於對經由無緩衝I/O訪問的頁進行高速緩存的塊高速緩存。
13.如權利要求12所述的電腦程式產品，其特徵在於，每一個頁是虛擬硬碟的頁。
14.如權利要求13所述的電腦程式產品，其特徵在於，所述虛擬硬碟是只讀父虛擬硬碟或子虛擬硬碟。
15.如權利要求11所述的電腦程式產品，其特徵在於，所述高速緩存是在節點集群的一節點上維護的。
全文摘要
採用多個頁替換算法的高速緩存。本發明延及用於實現使用多個頁替換算法的高速緩存的方法、系統以及電腦程式產品。一示例性高速緩存可包括兩個邏輯部分，其中第一部分實現最久未使用(LRU)算法並且第二部分實現最久未使用2(LRU2)算法以執行相應部分中的頁替換。通過實現多個算法，可以實現更高效的高速緩存，其中最可能被再次訪問的各頁被保留在高速緩存中。多個頁替換算法可被用於任何高速緩存中，包括用於對經由緩衝I/O訪問的各頁進行高速緩存的作業系統高速緩存以及用於對經由無緩衝I/O訪問的各頁(如虛擬機作出的對虛擬盤的訪問)進行高速緩存的高速緩存。
文檔編號G06F12/12GK103218316SQ20131005641
公開日2013年7月24日 申請日期2013年2月21日 優先權日2012年2月21日
發明者N·P·科斯特斯, A·達馬託, V·R·尚卡爾 申請人:微軟公司