用於非易失性存儲器存儲系統的雙範圍目錄的製作方法

2023-04-23 14:43:46 2

專利名稱：用於非易失性存儲器存儲系統的雙範圍目錄的製作方法
技術領域：
本發明涉及非易失性存儲器存儲系統。更具體地說，本發明涉及針對非易失性 存儲器存儲系統的使用而維護的目錄結構。
背景技術：
非易失性存儲器(NVM)存儲設備在計算機工業和電子工業中非常普及。計算 機具有長期使用的NVM存儲設備，以用於基本輸入/輸出系統(BIOS)代碼存儲設備和 其它重要的引導例程。但是，近來，NVM存儲設備的使用模型已經從數位相機圖像存儲 設備極大地擴展到了歌曲的數位音樂播放器存儲設備。NVM設備已經在大小上顯著地減 小並且在存儲容量上顯著地增加。現在，計算機工業正開始使用NVM設備為大容量存 儲設備建立固態驅動器(SSD)。未來，SSD能夠部分地由於優秀的性能、更小的外形和 更低的電能需求而顯著地取代傳統的硬碟驅動器。


通過示例的方式來說明本發明，並且本發明不受附圖的限制，其中，相似的標 記指示相似的元件，並且其中圖1說明了包括非易失性存儲器存儲系統的計算機系統的實施例。圖2說明了 NVM子系統的實施例的詳細視圖。圖3說明了通過寫入來添加新的存儲元素的單範圍目錄結構的實施例。圖4-8說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的若干實施例。圖9是使用雙範圍目錄結構將數據寫入NVM存儲陣列中的過程的實施例的流程 圖。圖10是使用雙範圍目錄結構從NVM存儲陣列中讀取數據的過程的實施例的流 程圖。
具體實施例方式描述了用於維護針對非易失性存儲器的雙範圍目錄結構的設備、系統和方法的 實施例。計算機系統可以包括非易失性存儲器(NVM)存儲子系統。在許多實施例中， NVM存儲子系統可以是固態驅動器(SSD)。在其它實施例中，NVM存儲子系統可以用 於不同用途的(而不是通用的)存儲驅動器。NVM存儲子系統包括一個或多個NVM設 備。例如，可以存在數個NAND閃速存儲器設備，其在NVM存儲子系統內創建存儲陣 列。NVM存儲子系統(例如，SSD)存儲了大量的可以是各種大小的存儲元素。當寫 請求到達NVM子系統時，要被寫入到NVM設備的數據隨後被寫入到在子系統內的NVM 存儲陣列的塊中。為了維護針對這些塊所處位置的簡單的訪問結構，通常在非易失性存儲器(例如系統存儲器)中維護目錄結構。目錄結構包括與在NVM存儲陣列中存儲的每一個元 素相對應的條目。在許多實施例中，當寫請求到達時，與NVM子系統相關聯的邏輯至少分析邏輯 塊地址(LBA)開始地址和操作範圍。在存儲元素已經被存儲在新寫入的位置的許多情況 下，較舊的元素被部分重寫。在一些情況下，新元素有效地將舊元素分成兩部分(即， 在新元素的開始之前的前面部分，以及在新元素的結束之後的後面部分)。使用當前的目 錄結構，這使得維護目錄的邏輯除了為新元素添加的條目之外還添加了額外的條目，因 為較舊的元素現在是兩個元素。這是必須的，因為當前的目錄結構針對所有條目維護單 個線性範圍。在許多實施例中，提出了雙範圍目錄結構，其允許將對應於新元素的條目寫入 到目錄結構中的前臺空間，同時較舊的較大元素能夠在目錄結構中的後臺空間中維護單 個條目。這實質上允許當新的存儲元素被不斷地引入時，在目錄結構中創建較少的總的 條目。在以下說明和權利要求中提及的、所公開的技術中的「一個實施例」或「實施 例」意味著結合該實施例而描述的特定特徵、結構或特性被包括在所公開的技術的至少 一個實施例中。因此，整個說明書的各個地方出現的短語「在一個實施例中」的出現並 非必然都是指同一實施例。在以下說明和權利要求中，可以使用術語「包括」和「包含」以及它們的派 生詞，並且旨在被視為彼此的同義詞。此外，在以下說明和權利要求中，可以使用術語
「耦合」和「連接」以及它們的派生詞。應當理解，這些術語不意在作為彼此的同義 詞。而是，在特定的實施例中，「連接」可以用於指示兩個或更多個元件彼此直接物理 或電接觸。「耦合」可以意味著兩個或更多個元件直接物理或電接觸。但是，「耦合」 還可以意味著兩個或更多個元件彼此沒有直接接觸，但仍然彼此合作、交互或通信。圖1說明了包括非易失性存儲器存儲系統的計算機系統的實施例。計算機系統 包括一個或多個中央處理單元(CPU)，例如CPU 100。在許多實施例中，CPU 100是 Intel 公司的CPU。在其它實施例中，CPU 100是其它品牌的CPU。CPUioo包括一 個或多個處理器核心，例如核心102、104、106和108。每一個核心包括一個或多個執行 單元、回退單元(retirementunit)、多個存儲寄存器，可能的一個或多個高速緩存存儲器 以及通常位於CPU核心內的其它電路。CPU 100還可以包括系統存儲器控制器110，以 控制與系統存儲器112的通信。系統存儲器互連114將系統存儲器112與CPU100通信 地耦合。互連可以包括線路以在CPU 100和系統存儲器112之間傳輸地址、數據、控制 和時鐘信息。雖然系統存儲器控制器110位於圖1中的CPU 100內，但是在沒有被示出 的其它實施例中，系統存儲器控制器110可以位於在計算機系統中與CPU 100分離的、獨 立的集成電路中。 在許多實施例中，系統存儲器112可以是動態隨機存取存儲器(DRAM)。例 如，系統存儲器112可以是雙倍數據速率(DDR)同步DRAM的形式。在其它實施例中， 系統存儲器可以是另一種形式的存儲器，例如非易失性存儲器。系統存儲器110可以存 儲由CPU 100執行的指令和數據。例如，系統存儲器110可以在計算機系統的操作期間 存儲作業系統(OS) 116。
在許多實施例中，CPU 100通信地耦合到1/0(輸入/輸出)組件118。I/O組 件118可以包括一個或多個I/O控制器(沒有示出)，其允許計算機系統與一個或多個I/ O設備(例如，設備120和122)進行通信。例如，I/O組件118可以包括通用串行總線 (USB)控制器，並且I/O設備120和122可以是USB設備。在許多實施例中，I/O組件118還耦合到非易失性存儲器(NVM)子系統124。 NVM子系統124包括至少一個或多個非易失性存儲器設備。在不同的實施例中，NVM 設備可以包括某些類型的閃速存儲器，例如基於NAND和NOR的設備、相變存儲器 (PCM),電可擦除可編程只讀存儲器(EEPROM)、或一個或多個其它類型的NVM。 NVM設備可以存儲不取決於被提供到NVM子系統的電能的數據。因此，在計算機系 統的復位序列、斷電和上電序列、以及可以將電能循環到計算機系統的任何其它序列期 間，NVM子系統可以繼續將數據存儲在一個或多個設備中。這與系統存儲器112相反， 其需要電能來存儲數據。如果在復位或電能序列期間沒有在其它地方保存數據，則在系 統存儲器112中存儲的任何數據在該復位或電能序列期間將丟失。NVM子系統124通過互連126通信地耦合到計算機系統。互連126包括用於發 送數據、地址、控制和其它信號的一個或多個線路。在一些實施例中，該線路可以包括 銅線。在其它實施例中，該線路可以包括其它金屬或合金、光學線路，或用於發送信息 的另一種介質。在許多實施例中，互連126將NVM子系統124與I/O組件(在圖1中的部件 118)通信地耦合。但是，在其它實施例中，互連126可以將NVM子系統124與計算機 系統內的另一個集成電路部件通信地耦合。 圖2說明了 NVM子系統的實施例的詳細的視圖。NVM子系統包括NVM存儲 陣列200。在不同的實施例中，存儲設備可以是閃速存儲器或另一種形式的非易失性的存 儲器設備。例如，存儲設備可以包括一個或多個NAND設備。在其它實施例中，非易 失性存儲陣列200可以包括NOR設備、PCM、EEPROM或另一種類型的NVM。在許 多實施例中，非易失性存儲陣列包括一個或多個NVM設備，並且將所述設備中的每一個 細分為多個扇區。NVM子系統124包括主機接口 202。主機接口 202是在NVM子系統124和計 算機系統的其餘部分之間的通信接口。例如，在主機CPU(例如，圖1中的CPU 100)和 NVM子系統124之間的通信可以通過主機接口 202發生。可以將來自CPU 100的讀請求 和寫請求通過主機接口 202路由到NVM子系統124中。在許多實施例中，主機接口 202 包括一個或多個緩衝器，其可以存儲輸入到NVM子系統124的數個讀請求和寫請求。緩 衝器可以是隊列的形式，例如先入先出(FIFO)隊列，其可以存儲輸入到NVM子系統124 的請求。主機接口 202可以接收主機請求，例如讀請求和寫請求，然後將它們轉發到 NVM控制器204。在NVM控制器204內的控制邏輯可以處理這些請求，並寫入非易失 性存儲陣列200或從其讀取。在許多實施例中，NVM子系統124將數據存儲在邏輯塊中。對於每一個寫入， 將數據寫入到NVM存儲陣列200的邏輯塊地址(LBA)開始地址和LBA結束地址之間。 在NVM存儲陣列200中存儲的每條數據可以被稱為存儲元素。因此，在許多實施例中，存儲元素具有指定的LBA開始地址，並且具有LBA結束地址或大小。該信息允許通過 使用LBA開始地址和LBA結束地址來簡單地讀取存儲元素，以捕獲整個數據量。在許多實施例中，使用目錄結構來跟蹤每一個存儲元素。目錄結構可以被存儲 在系統存儲器(例如，圖1中的系統存儲器112中的目錄128)或計算機系統中其它地方 的存儲器中。例如，在另一個實施例中，目錄結構可以位於在NVM子系統124內的存 儲器存儲設備中。一般而言，用於存儲目錄結構的存儲器將位於易失性存儲器中，儘管 這並不是必須的。 目錄結構包括用於每個存儲元素的條目，以便為了將來寫入和讀取NVM存儲陣 列200的目的來跟蹤元素。在目錄結構中存儲的每個條目的組成在不同的實施例中可以 改變。例如，每個元素的安全訪問寫入可能需要額外的信息被存儲在條目內。但是一 般而言，每個條目至少具有LBA的開始地址，以及LBA的結束地址或者在邏輯空間中條 目的跨度。在許多實施例中，條目還可以包括具體的NVM存儲陣列地址單元。例如， 每個條目的大小可以是8個字節，其中，2個字節可以是LBA開始地址，2個字節可以是 LBA結束地址，並且4個字節可以是NVM存儲陣列地址。在其它實施例中，條目可以 包括不同的信息或者可能的額外信息。取決於實現方式，LBA可以由不同數量的比特來 表示，所述比特數量的不同是由於存儲單元的大小不同而引起的(例如，如果存儲設備 的最小單元是1KB，則不需要存儲表示小於1KB粒度的單元的地址比特)。在許多實施例中，目錄結構允許在一定程度上間接讀寫數據。例如，雖然目錄 結構涉及線性的、連續的存儲元素(其每一個可以是任意給定大小)，但是NVM控制器 可以將線性地址翻譯為物理地址，其可能不包括線性的數據塊。事實上，在物理上，可 以將數據在NVM存儲陣列的範圍內隨機地展開，以允許調整NVM設備的磨損。因為 NVM設備通常具有有限的壽命，並且在很多次寫入之後變得不可靠，所以將寫入均勻地 展開到所有設備之間是重要的，以便延長陣列的整體壽命。可以以多種方式來改變條目。例如，如果由較新的存儲元素完全重寫了較舊的 存儲元素，則與較舊的存儲元素相對應(即，相關聯)的條目可以被擦除(即，釋放)， 以釋放存儲器的存儲空間。在單範圍目錄結構中，存在包括整個存儲陣列的、與所有LBA相關聯的線性空 間。對於陣列中的每一個存儲元素，如果由新的存儲元素部分重寫了(而不是完全重寫 了)存儲元素，則必須在目錄結構中為新的存儲元素創建新的條目。除了新的條目之 夕卜，與被部分重寫的較舊的存儲元素相對應的條目將需要被修改。在某些情況下，如果 被部分重寫的較舊的存儲元素被切分為分離的兩塊，並且新的元素在它們之間，則需要 創建第二個額外的新條目。這使得在單範圍目錄結構中產生了額外的空間需求，因為不 是創建了一個額外的條目，而是現在存在第二個額外的條目，需要用其來準確地表示較 舊的存儲元素的剩餘塊。圖3說明了通過寫入來添加新的存儲元素的單範圍目錄結構的實施例。LBA空 間示出了存儲在NVM存儲陣列中的三個獨立的存儲元素存儲元素A、B和C。這些 存儲元素對應於位於目錄結構中的三個條目條目1、2和3。然後，新的寫入發生，其將元素D添加到LBA空間。包括用於描述元素D的 信息的條目4需要被添加到目錄結構。在該特定的情況下，元素D完全地包括在元素B的單元內。換句話說，在線性LBA空間中，元素B在元素D的開始之前開始，並且元素B在元素D的結束之後結束。因此，為了在目錄結構中準確地表示元素D以及元素B的其餘有效部分，第二 個新條目(條目5)被創建。結果顯示元素A和C以及它們對應的條目1和3沒有改變。 現在，條目4表示新寫入的元素D，條目2表示在元素D的開始之前的、元素B的仍然 有效的部分，並且條目5表示在元素D的結束之後的、元素B的仍然有效的部分(現在 是元素E)。在這裡示出了單範圍目錄結構的不利方面，這是因為雖然僅單個存儲元素被 添加到LBA空間，但是單範圍目錄結構的局限需要將兩個條目添加到目錄結構中。圖4-8說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的數個實施例。圖4說明了現在示出為使用目錄結構的雙範圍性質的、與在圖3中所示的相同 的示例存儲元素和大小。目錄結構的雙範圍性質允許該結構一起操作前臺空間和後臺空 間。這兩個獨立的空間僅與目錄結構相關。實際的NVM存儲陣列仍然可以被看作是 LBA的單個線性陣列。在每個圖的長度方向上通過雙箭頭的方式來示出線性度(即，在 X軸線上的每一個點可以被看作是單個LBA)。為了便於解釋，NVM存儲陣列包括以如下方式看到的數據在圖形上從前臺 上的點向下看線性陣列、並然後通過前臺到達後臺所看到的數據。換句話說，在給定的 LBA處，如果在圖4的前臺中沒有示出存儲元素，則在該LBA處存儲的數據是在後臺中 示出的存儲元素中的數據。最後，在給定的LBA處，如果在同一 LBA處存在在前臺中 示出的存儲元素和在後臺中示出的存儲元素，則在前臺中示出的存儲元素優先(即，在 該LBA處，來自後臺的存儲元素的數據被來自前臺的存儲元素的數據重寫)。返回圖4，LBA空間顯示在NVM存儲陣列中存儲的三個獨立的存儲元素存儲 元素A、B和C。這些存儲元素對應於位於目錄結構的後臺中的三個條目條目1、2和 3。然後，新的寫入發生，其將元素D添加到LBA空間。然後，包括用於描述元素 D的信息的條目4被添加到目錄結構的前臺。在該特定的情況下，元素D完全地包括在 元素B的單元內。換句話說，在線性LBA空間中，元素B在元素D的開始之前開始， 並且元素B在元素D的結束之後結束。在雙範圍目錄結構實現中，元素D寫入可以發生，並且重寫在NVM存儲陣列中 的元素B的一部分，並且單個條目(條目4)將被添加到目錄結構。因此，此時，目錄結 構仍然具有在所述目錄結構中的三個原始的條目(條目1、2和3)以及新條目4。原始 條目中的每一個保持原樣並且不需要修改。這包括條目B，其保持條目B的初始的LBA 開始和結束地址。因此，在寫入之後，在目錄結構中的前臺空間包括條目4，並且後臺空 間包括條目1、2和3。當讀取發生在雙範圍的實施例中時，讀取可以在給定的LBA處開始並跨越一個 或多個元素。每個元素由目錄結構的前臺或後臺空間中的條目來表示。在目錄結構的前 臺空間中的條目優先於在後臺空間中的條目。因此，如果在給定LBA處在前臺和後臺空 間中都存在條目，則讀取將使用前臺條目信息來將數據取出。可能位於NVM控制器204內或者在計算機系統中的其它地方的邏輯使用目錄結 構來瀏覽NVM存儲陣列，從而為了讀取數據而將其取出。例如，假設讀請求到達並且其想要讀取從LBA 2到LBA 7的數據，在新的寫入已經發生後，使用在圖4的底部的示例 LBA的線性的行。通過在目錄結構中查找LBA 2並且確定在前臺空間中的該單元處是否 存在條目，邏輯開始操作。因為不存在前臺空間條目，然後邏輯檢查在後臺空間中的條 目並且發現存儲元素B(在目錄結構中由條目2來表示)位於LBA2。然後，邏輯確定條 目2在LBA 2到LBA 4處有效，並且從這些LBA單元讀取數據。在LBA 4處，邏輯意 識到前臺條目存在(條目4)，然後在LBA 4處讀取存儲元素D。然後，發現沒有前臺條 目位於LBA 5，邏輯返回到條目2並且讀取在LBA 5處開始的存儲元素B的其餘部分。 條目2在LBA 6處結束，但是邏輯發現另一個後臺空間條目存在在LBA 6(條目3)。邏 輯從與條目3相對應的存儲元素C讀取從LBA 6到LBA 7的數據，並且結束所述讀取。在許多實施例中，當讀取從開始的LBA進行到結束的LBA的過程中，在NVM 控制器204內或其它地方的邏輯在每一個LBA處保持跟蹤在前臺和後臺中的元素。在一 些實施例中，邏輯可以是IF-THEN例程的形式，其中，對於每個LBA:IF條目位於前臺中，THEN從前臺條目的元素中讀取；ELSE從後臺的條目的元素中讀取；在一些實施例中，讀取處理可以使用遞歸邏輯，從而在完成由前臺空間條目表 示的任何元素的讀取之後，數次返回到後臺空間條目。對於使用雙範圍目錄結構的讀取，許多其它算法也是可用的。圖5說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的另一個實施例。在圖5中的寫入處理的開始處，存在由在目錄結構的後臺空間中的條目表示 的、存儲在NVM存儲陣列中的三個獨立的存儲元素存儲元素A、B和C以及它們各自 的條目1、2和3。還存在由在目錄結構的前臺空間中的條目表示的、存儲在NVM存儲 陣列中的一個存儲元素存儲元素D以及其條目4。然後，新的寫入發生，其將元素E添加到LBA空間。然後，包括用於描述元素 E的信息的條目5被添加到目錄結構的前臺。在該特定的情況下，先前由前臺條目4表 示的元素D被元素E完全重寫。因此，在該情況下，存儲元素D和條目4不再存在，並 且被NVM存儲陣列中的元素E以及在目錄結構的前臺空間中的條目5所取代。圖6說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的另一個實施例。在圖6中的寫入處理的開始處，存在由在目錄結構的後臺空間中的條目表示 的、存儲在NVM存儲陣列中的三個獨立的存儲元素存儲元素A、B和C以及它們各自 的條目1、2和3。然後，新的寫入發生，其將元素D添加到LBA空間。然後，包括用於描述元素D的信息的條目4被添加到LBA空間，但是在不同實施例中，與元素D相對應的條目可 以被添加到目錄結構中的前臺或後臺空間中。對於該示例的特定情況，因為具有與條目 2(其被部分重寫)不同的開始LBA的元素D具有同一結束地址。因此，元素B不必被 分割為新的較小的元素B和額外的元素E(例如，圖4中的情況)。這裡，元素B的僅有 的其餘有效部分是從條目2的原始的開始LBA到元素D的開始LBA(在條目4)。因為不 需要第二條目，所以在目錄結構中不需要如圖4所示的實施例中所需的額外的條目存儲 空間。因此，在一些實施例中，圖6中的條目4可以被添加到前臺空間(類似於圖4)， 但在其它實施例中，圖6中的條目4可以被添加到後臺空間，如同其在單範圍目錄結構中那樣。在一些實施例中，邏輯可以使用簡單的測試來確定是否將新的條目添加到目錄結構的前臺空間或後臺空間，其中，如果所述條目是需要添加到整個目錄結構中的唯一 條目(即，對於添加單個新的存儲元素，總共添加一個條目)，則針對新的存儲元素添加 後臺空間條目。否則，如果通過添加後臺空間條目將需要第二個後臺空間條目(即，如 上所述的單範圍的缺陷對於添加單個新的存儲元素，總共添加兩個條目)，則針對新 的存儲元素添加前臺空間條目。圖7說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的另一個實施例。在圖7中的寫入處理的開始處，存在由在目錄結構的後臺空間中的條目表示 的、存儲在NVM存儲陣列中的三個獨立的存儲元素存儲元素A、B和C以及它們各自 的條目1、2和3。然後，新寫入發生，其將元素D添加到LBA空間。然後，包括用於描述元素D 的信息的條目4被添加到LBA空間，但是在不同實施例中，與元素D相對應的條目可以 被添加到目錄結構中的前臺或後臺空間中。對於該示例的特定情況，因為元素D完全重 寫元素B，使得條目2不再需要。因此，在該情況下，不將表示元素D的條目4放入目 錄結構的前臺空間中是有益的。使用前臺空間將會增加需要存儲的條目(從3個條目變 為4個條目)，而使用後臺空間來存儲條目4將保持在目錄結構中存儲的條目的總數量不 變。換句話說，在新的寫入之前，條目1、2和3被存儲在目錄結構的後臺空間中，在新 的寫入之後，條目1、3和4被存儲在目錄結構的後臺空間中。圖8說明了通過寫入來添加新的存儲元素的雙範圍目錄結構的另一個實施例。在圖8中的寫入處理的開始處，存在由在目錄結構的後臺空間中的條目表示 的、存儲在NVM存儲陣列中的三個獨立的存儲元素存儲元素A、B和C以及它們各自 的條目1、2和3。還存在由在目錄結構的前臺空間中的條目表示的、存儲在NVM存儲 陣列中的一個存儲元素存儲元素D及其條目4。然後，新的寫入發生，其將元素E添加到LBA空間。然後，包括用於描述元素 E的信息的條目5被添加到LBA空間。在許多實施例中，由條目5表示的存儲元素E部 分重寫由條目4表示的元素D。因此，條目5被存儲在目錄結構的前臺空間中，並且條 目4被修改以準確地描述由於元素E對元素D部分重寫而造成的元素D的新(較短)長 度。在該情況下，後臺空間條目1、2和3不需要任何修改。可以存在許多條規定了許多類型的個別案例的具體操作的規則。一般而言，當 前臺空間節省存儲空間(否則所述存儲空間是使用單範圍目錄結構的結果)時，可以使用 目錄結構中的前臺空間。在任何時候，用於對前臺和後臺空間進行控制的邏輯可以決定 用於NVM存儲陣列的碎片整理(desegmentation)處理應當發生，以清理任何級別的數據 碎片。在許多實施例中，當碎片整理發生時，表示在NVM存儲陣列中的所有存儲元素 的所有條目被置入目錄結構的後臺空間。在一些實施例中，可以在具有顯著的碎片量的 區域中進行部分的碎片整理。圖9是使用雙範圍目錄結構將數據寫入到NVM存儲陣列中的過程的實施例的 流程圖。由處理邏輯來執行該過程，該處理邏輯可以包括硬體、軟體或硬體和軟體的組 合。參照圖9，過程以處理邏輯根據新的寫請求分析LBA開始地址和結束地址作為開始(處理框900)。然後，處理邏輯檢查以查看當前在LBA開始地址到LBA結束地址之間 是否存在任何條目位於後臺空間中(處理框902)。
如果在後臺空間中在該單元的條目處不存在包含存儲的數據的存儲元素，則處 理邏輯可以將新的條目添加到目錄結構的後臺空間中(處理框904)。然後，處理邏輯可 以將新的元素寫入到開始於LBA開始位置的NVM存儲陣列中(處理框906)。
返回框902，如果在該單元的後臺空間中存在條目，則處理邏輯將新的條目添加 到目錄結構的前臺空間中(處理框908)。最後，處理邏輯隨後可以將新的存儲元素寫入 到在LBA開始地址到LBA結束地址範圍內的、在NVM存儲陣列中的任意當前元素中的 一部分或所有元素上(處理框910)，並且處理結束。
圖10是使用雙範圍目錄結構從NVM存儲陣列中讀取數據的過程的實施例的流 程圖。由處理邏輯來執行該過程，該處理邏輯可以包括硬體、軟體或硬體和軟體的組 合。參照圖10，過程以處理邏輯根據新的讀請求分析LBA開始地址和LBA結束地址作 為開始(處理框1000)。然後，處理邏輯將LBA開始地址值置入當前LBA參數(處理框 1002)。當前LBA參數僅是由處理邏輯使用的存儲單元，其用於指向從線性LBA地址空 間內讀取數據的當前單元。
在當前LBA，處理邏輯檢查以查看地址是否位於在目錄結構的前臺空間中的條 目的範圍內(處理框1004)。如果當前單元不在前臺空間中，則處理邏輯從與位於後臺空 間中的條目相對應的存儲元素中讀取數據(處理框1006)。否則，如果當前單元處於前臺 空間中，則處理邏輯從與位於前臺空間中的條目相對應的存儲元素中讀取數據(處理框 1008)。
在讀取數據之後，處理邏輯隨後檢查以查看當前LBA是否等於根據讀請求分析 的LBA結束地址(處理框1010)。如果當前LBA參數處在LBA結束地址處，則處理結 束。否則，如果當前LBA參數不在LBA結束地址處，則處理邏輯增加當前LBA到要讀 取的下一單元(處理框1012)，並且處理返回到框1004。
因此，描述了用於維護針對非易失性存儲器的雙範圍目錄結構的設備、系統和 方法的實施例。參照其具體示例性實施例描述了這些實施例。對於受益於該公開的人而 言顯而易見，可以在不脫離本文描述的實施例的較寬的精神和範圍的情況下，對這些實 施例進行各種變型和改變。因此，說明書和附圖被認為是說明性的而不是限制性的。
權利要求
1.一種非易失性存儲器(NVM)間接寫入設備，包括NVM存儲陣列，其用於存儲多個存儲元素；以及雙範圍目錄結構，其具有後臺空間和前臺空間，所述結構用於存儲多個條目，所述 多個條目中的每一個條目對應於在所述NVM存儲陣列中用於存儲所述多個存儲元素中的 一個存儲元素的單元，其中，所述後臺空間包括針對如下存儲元素的條目，該存儲元素在沒有對所述後臺 空間中的先前存儲的存儲元素進行任何部分重寫的情況下被寫入到所述陣列；並且所述 前臺空間包括針對如下存儲元素的條目，該存儲元素在對所述後臺空間中的一個或多個 先前存儲的存儲元素進行至少一次部分重寫的情況下被寫入到所述陣列。
2.根據權利要求1所述的設備，其中，所述多個條目中的每一個條目包括所述存儲元 素的單個邏輯塊地址(LBA)開始地址和單個LBA結束地址。
3.根據權利要求2所述的設備，其中，與已經被在所述前臺空間中的一個或多個元素 部分重寫的、在所述後臺空間中的存儲元素相對應的每一個條目繼續保持所述單個LBA 開始和結束地址。
4.根據權利要求3所述的設備，還包括控制器，其用於控制對所述NVM存儲陣列的訪問。
5.根據權利要求4所述的設備，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前可用於存儲新數據時，針對所述新的存儲元素在所述雙範圍目錄結構中 的所述後臺空間中創建新的條目。
6.根據權利要求4所述的設備，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前存儲了將被所述新的存儲元素完全重寫的、在所述後臺空間中的一個或 多個先前存儲的存儲元素，而沒有存儲將被部分重寫的、在所述後臺空間中的一個或多 個先前存儲的存儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述後臺 空間中創建新的條目。
7.根據權利要求4所述的設備，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前存儲了將被部分重寫的、在所述後臺空間中的一個或多個先前存儲的存 儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述前臺空間中創建新的 條目。
8.根據權利要求4所述的設備，其中，所述控制器用於對於開始於讀請求的LBA開始地址並且持續到讀請求的LBA結束地址的給定的 NVM存儲陣列讀請求，並且其中，對於在所述NVM存儲陣列中從所述LBA開始地址到 所述LBA結束地址的每一個地址單元，當前臺空間條目存在時，從在所述NVM存儲陣 列中的、與前臺空間條目相對應的存儲元素讀取數據；並且當前臺空間條目不存在時， 從在所述NVM存儲陣列中的、與後臺空間條目相對應的存儲元素讀取數據。
9.根據權利要求4所述的設備，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求，當在所述後臺空間中創建新的條目使得表示在所述NVM陣列中存儲的所有存儲元素所需 的所述後臺空間中的條目的總數量增加至多一個條目時，針對所述新的存儲元素在所述 雙範圍目錄結構中的所述後臺空間中創建新的條目。
10.—種系統，包括系統動態隨機存取存儲器(DRAM)；NVM存儲陣列，其用於存儲多個存儲元素；以及存儲在所述系統DRAM中的雙範圍目錄結構，其具有後臺空間和前臺空間，所述結 構用於存儲多個條目，所述多個條目中的每一個條目對應於在所述NVM存儲陣列中用於 存儲所述多個存儲元素中的一個存儲元素的單元，其中，所述後臺空間包括針對如下存儲元素的條目，該存儲元素在沒有對所述後臺 空間中的先前存儲的存儲元素進行任何部分重寫的情況下被寫入到所述陣列；並且所述 前臺空間包括針對如下存儲元素的條目，該存儲元素在對所述後臺空間中的一個或多個 先前存儲的存儲元素進行至少一次部分重寫的情況下被寫入到所述陣列。
11.根據權利要求10所述的系統，其中，每一個條目包括所述存儲元素的單個邏輯塊 地址(LBA)和長度參數。
12.根據權利要求11所述的系統，其中，與已經被在所述前臺空間中的一個或多個 元素部分重寫的、在所述後臺空間中的存儲元素相對應的每一個條目繼續保持所述單個 LBA和長度參數。
13.根據權利要求12所述的系統，還包括控制器，其用於控制對所述NVM存儲陣列的訪問。
14.根據權利要求13所述的系統，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前可用於存儲新數據時，針對所述新的存儲元素在所述雙範圍目錄結構中 的所述後臺空間中創建新的條目。
15.根據權利要求13所述的系統，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前存儲了將被所述新的存儲元素完全重寫的、在所述後臺空間中的一個或 多個先前存儲的存儲元素，而沒有存儲將被部分重寫的、在所述後臺空間中的一個或多 個先前存儲的存儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述後臺 空間中創建新的條目。
16.根據權利要求13所述的系統，其中，所述控制器用於對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求， 當所述單元當前存儲了將被部分重寫的、在所述後臺空間中的一個或多個先前存儲的存 儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述前臺空間中創建新的 條目。
17.根據權利要求13所述的系統，其中，所述控制器用於對於開始於讀請求的LBA開始地址並且持續到讀請求的LBA結束地址的給定的 NVM存儲陣列讀請求，並且其中，對於在所述NVM存儲陣列中從所述LBA開始地址到 所述LBA結束地址的每一個地址單元，當前臺空間條目存在時，從在所述NVM存儲陣列中的、與前臺空間條目相對應的存儲元素讀取數據；並且當前臺空間條目不存在時， 從在所述NVM存儲陣列中的、與後臺空間條目相對應的存儲元素讀取數據。
18.—種方法，包括在包括後臺空間和前臺空間的雙範圍目錄結構中存儲多個條目，所述多個條目中的 每一個條目對應於在非易失性存儲器(NVM)存儲陣列中的存儲元素，其中，所述後臺空間包括針對如下存儲元素的條目，該存儲元素在沒有對所述後臺 空間中的一個或多個先前存儲的元素進行任何部分重寫的情況下被寫入到所述陣列；並 且所述前臺空間包括針對如下存儲元素的條目，該存儲元素在對所述後臺空間中的一個 或多個先前存儲的元素進行至少一次部分重寫的情況下被寫入到所述陣列。
19.根據權利要求18所述的方法，其中，所述多個條目中的每一個條目包括所述存儲 元素的單個邏輯塊地址(LBA)和長度參數。
20.根據權利要求19所述的方法，還包括針對與已經被在所述前臺空間中的一個或多個元素部分重寫的、在所述後臺空間中 的存儲元素相對應的所述多個條目中的每一個條目，保持所述單個LBA和大小參數。
21.根據權利要求20所述的方法，還包括對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求，當所述單元當前可用於存儲新數據時，針對所述新的存儲元素在所述雙範圍目錄結 構中的所述後臺空間中創建新的條目。
22.根據權利要求20所述的方法，還包括對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求，當所述單元當前存儲了將被所述新的存儲元素完全重寫的、在所述後臺空間中的一 個或多個先前存儲的存儲元素，而沒有存儲將被部分重寫的、在所述後臺空間中的一個 或多個先前存儲的存儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述 後臺空間中創建新的條目。
23.根據權利要求20所述的方法，還包括對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求，當所述單元當前存儲了將被部分重寫的、在所述後臺空間中的一個或多個先前存儲 的存儲元素時，針對所述新的存儲元素在所述雙範圍目錄結構中的所述前臺空間中創建 新的條目。
24.根據權利要求20所述的方法，還包括對於開始於讀請求的LBA開始地址並且持續到讀請求的LBA結束地址的給定的 NVM存儲陣列讀請求，並且其中，對於在所述NVM存儲陣列中從所述LBA開始地址到 所述LBA結束地址的每一個地址單元，當前臺空間條目存在時，從在所述NVM存儲陣列中的、與前臺空間條目相對應的存 儲元素讀取數據；以及當前臺空間條目不存在時，從在所述NVM存儲陣列中的、與後臺空間條目相對應的 存儲元素讀取數據。
25.根據權利要求20所述的方法，還包括對於包括要被寫入到所述NVM存儲陣列中的單元的新的存儲元素的給定的寫請求，當在所述後臺空間中創建新的條目使得表示在所述NVM陣列中存儲的所有存儲元素 所需的所述後臺空間中的條目的總數量增加至多一個條目時，針對所述新的存儲元素在 所述雙範圍目錄結構中的所述後臺空間中創建新的條目。
全文摘要
公開了一種設備、系統和方法。在一個實施例中，所述設備包括非易失性存儲器(NVM)存儲陣列以存儲多個存儲元素。所述設備還包括具有後臺空間和前臺空間的雙範圍目錄結構。所述結構能夠存儲若干條目，其每一個對應於在NVM存儲陣列中用於對存儲元素進行存儲的單元。後臺空間包括針對如下存儲元素的條目，該存儲元素在沒有對所述後臺空間中的先前存儲的存儲元素進行任何部分重寫的情況下被寫入到所述陣列。前臺空間包括針對如下存儲元素的條目，該存儲元素在對所述後臺空間中的一個或多個先前存儲的存儲元素進行至少一次部分重寫的情況下被寫入到所述陣列。
文檔編號G06F12/08GK102023930SQ20101024896
公開日2011年4月20日 申請日期2010年8月6日 優先權日2009年8月7日
發明者A·沃根 申請人:英特爾公司