主機管理的非易失性存儲器的製作方法

2023-06-07 21:57:06

本公開涉及非易失性存儲器，具體地說，涉及固態驅動器中的非易失性存儲器。

背景技術：

固態驅動器（SSD）是可由計算裝置使用的一種類型非易失性存儲裝置。一些SSD包含用於存儲的基於塊的非易失性存儲器，例如NAND型快閃記憶體。在NAND型快閃記憶體中，存儲器單元被編組成頁和塊。頁可包含若干字節（例如4096），塊可包含若干頁（例如128），並且取決於SSD的存儲能力，NAND型快閃記憶體SSD可包含若干塊（例如1024）。在NAND快閃記憶體中，讀和寫操作是基於頁的。換言之，數據頁是可讀/寫的最小量。從而，為了響應於讀或寫較小的數據量的應用請求，讀或寫整頁。另外，NAND型快閃記憶體要求，在編程之前擦除存儲器單元。此類擦除操作通常在存儲器單元的塊上執行。

附圖說明

要求權利的主題的特徵和優點根據與之符合的實施例的如下詳細描述將顯而易見，該描述應該參考附圖考慮，附圖中：

圖1圖示了符合本公開各種實施例的計算系統的功能框圖；

圖2圖示了符合本公開各種實施例的裝置邏輯塊地址（LBA）空間的示例存儲布局；

圖3圖示了符合本公開各種實施例的圖2存儲布局的示例元數據布局；

圖4圖示了符合本公開一個實施例的具有分配的索引節點、數據區間（data extent）和自由空間的示例數據部分；

圖5是根據本公開各種實施例的存儲器存取操作的流程圖；

圖6是根據本公開各種實施例的寫和丟棄操作的流程圖；

圖7是根據本公開各種實施例的分配操作的流程圖；

圖8是根據本公開各種實施例的使自由操作的流程圖；

圖9是根據本公開各種實施例使用SIMD（單指令多數據）的查找操作的流程圖；以及

圖10是根據本公開一個實施例的多個自由列表的操作的流程圖。

儘管如下具體實施方式將繼續參考說明性實施例，但它們的許多替換、修改和變形對本領域技術人員將是顯而易見的。

具體實施方式

為了補償基於塊（例如NAND型）的固態驅動器（SSD）的特性，寫操作可由主機計算裝置和/或SSD控制器管理，以最大化對於每個寫操作的存儲所寫的數據量。例如，要寫的數據可被緩衝，直到累積了最小數據量（例如頁）為止，然後，數據頁可被寫到連續存儲器位置。在另一示例中，響應於包含用於僅一部分頁的存儲器地址的讀請求，數據的整頁例如可被讀到SSD中的高速緩衝存儲器中。寫操作也可配置成促進擦除操作，即，最大化連續頁的數量，因為擦除操作是基於塊的。

向具有塊可存取的非易失性存儲器的SSD的寫操作通常利用日誌構造的存儲技術。本文所使用的「塊可存取」指的是具有用於存儲器存取的最小大小（例如一頁）的非易失性存儲器。本文所使用的「字節可存取」指的是可由字和/或字節存取的非易失性存儲器。「字節可存取」和「塊可存取」指的是對物理存儲器地址的存取。換言之，對應用顯然的是，已經請求了如何存取物理存儲器的讀或寫操作。日誌構造的存儲裝置配置成將多個單獨的隨機寫操作組合成單個順序寫，由此至少提供要寫的最小數據量。要寫的數據可在主機中的易失性存儲器中緩衝，直到至少已經累積了最小量的數據為止。「段」可包含至少一個數據頁，即，可被寫到SSD的最小量的數據。數據段然後可被寫到之前擦除的SSD中的存儲器位置的連續塊。

寫操作進一步配置為寫時拷貝。在寫時拷貝中，「老」數據不被改寫，而是，更新的（「新」）數據被寫到不同擦除的存儲器位置，並且老數據可隨後擦除。寫時拷貝可導致碎片化存儲，因為每次寫是到不同的存儲塊，並且每次寫可包含僅對應於「老」（即之前存儲的）數據子集的新數據。

從而，日誌構造的存儲裝置可消耗存儲等待要被寫的數據並且計算對自由空間碎片整理的資源的附加主機非易失性存儲器容量。對自由空間碎片整理配置成增加連續頁的數量。日誌構造的存儲裝置可進一步延遲向SSD提交數據，因為準備要寫的數據可被延遲，等待附加數據填充頁。

一般而言，此公開涉及用於字節可存取的裝置管理的NVM存儲裝置的主機管理的NVM（非易失性存儲器）方法（和系統）。NVM存儲裝置例如包含固態驅動器（SSD）。方法和系統包含主機計算裝置中的間接邏輯，其實現NVM基元，同時避免日誌構造的存儲及其關聯的開銷。NVM基元包含但不限於原子多寫、原子寫、稀疏編址、丟棄、驗證、原子丟棄和原子多丟棄。

原子操作配置成避免存儲器存取操作結果中的不確定性，如果該存儲器存取操作例如由於功率失敗而中斷的話。換言之，在原子寫中，要被寫的所有指定扇區都被寫，或者沒有扇區被寫。扇區對應於與存儲器存取操作關聯的若干數據字節。扇區可包含任何數量的數據字節。例如，扇區可包含512個數據字節。在另一示例中，扇區可包含少於512的數據字節。在另一示例中，扇區可包含多於512的數據字節。如果寫被中斷，則之前存儲的數據（「老數據」）被保持，並且要被存儲的數據（「新數據」）未被寫。在原子丟棄中，所有扇區被丟棄，或者沒有扇區被丟棄。寫時拷貝促進此類原子性，因為老數據未被立即改寫。

間接邏輯配置成響應於寫請求而管理向選擇的NVM存儲裝置寫數據扇區，而不等待附加扇區累積。間接邏輯提供配置成將主機邏輯塊地址（LBA）映射到裝置LBA的間接層。邏輯塊編址提供物理存儲介質（即物理存儲器）與例如作業系統（OS）之間的抽象。例如，由應用和/或OS使用的主機LBA可被映射到裝置LBA，其然後可與存儲裝置的物理存儲器地址相關。塊通常包含多個存儲器位置。例如，塊可包含扇區，並且LBA然後可對應於一個扇區。應用可配置成從一系列主機LBA讀和/或向一系列主機LBA寫。一系列主機LBA可被映射到（即轉換成）對應的一系列裝置LBA和/或物理存儲器地址。主機地址空間可大於裝置地址空間。之前未映射的主機LBA可響應於寫請求而動態映射到裝置LBA。

裝置管理的NVM存儲裝置例如可在驅動器控制器中包含存儲裝置上的快閃記憶體轉換層（FTL）。FTL配置成將裝置LBA映射和/或轉換成物理存儲器地址。裝置控制器然後可執行與將數據實際存儲到NVM存儲裝置關聯的操作。

裝置地址空間可包含元數據、事務日誌和數據部分。數據部分包含自由空間、自由列表、例如配置為搜索樹的索引節點以及存儲的數據。數據被存儲在一個或多個數據區間中。本文所使用的「區間」對應於一個或多個連續的存儲單元。例如，存儲單元可對應於字節、扇區（例如512位元組）、頁、塊等。樹結構可包含B樹、B+樹和/或它們的一個或多個變量。例如，B+樹包含根節點，可包含一個或多個內部節點和一個或多個葉節點。根節點包含到內部節點的索引和指針。索引與主機LBA相關。在一些實施例中，一個或多個索引可對應於主機LBA。內部節點包含到葉節點的索引和指針。每個葉節點包含主機LBA、關聯的裝置LBA和長度。在一些實施例中，葉節點可包含多組主機LBA、關聯的裝置LBA和長度。每個葉節點配置成將一系列主機LBA映射到對應的一系列裝置LBA。長度對應於一系列裝置LBA的大小，並且可對應於開始於裝置LBA的數據區間的大小。大小可以存儲單元（例如扇區）為單位。

方法和系統配置成利用相對低等待時間的NVM存儲裝置（例如SSD）的單扇區原子寫來避免緩衝日誌構造的存儲裝置，而不降級性能。相對低等待時間的NVM存儲裝置可以是字節可存取的，從而，存取時間可以不包含與日誌構造的存儲裝置關聯的等待時間。相對低等待時間的NVM技術具有相對快的存取時間，例如相對低的隨機寫或隨機讀等待時間。例如，用於寫或讀扇區的相對低的隨機存取等待時間可以在大約10微秒（μs）。在另一示例中，相對低的存儲器存取等待時間可以在大約100μs。寫等待時間可根據應用的角度確定。換言之，等待時間可包含分別開始於提交對於寫的請求並結束於關聯的數據被駐留在NVM存儲裝置上或者已經被提供給發出請求的應用的時間間隔。例如，此類相對低等待時間的字節可存取的NVM技術可包含但不限於：磁阻存儲器（MRAM）、相變存儲器（PCM、PRAM）、相變存儲器和開關（PCMS）、阻性存儲器、鐵電存儲器(F-RAM, FeRAM)、自旋轉移轉矩存儲器（STT）、熱輔助的開關存儲器(TAS)、千足蟲存儲器、浮動結柵存儲器(FJG RAM)、電池備份RAM等。當利用此類字節可存取的相對低等待時間的NVM技術時，可避免日誌構造的存儲裝置及其關聯的開銷。可使用複合本公開的方法和系統與較高等待時間的NVM，但隨著等待時間增加，方法和系統的好處可減少，直到日誌構造的存儲裝置至少一樣快。

在一些實施例中，可使用SIMD（單指令多數據）操作，實現查找包含在未分類的B樹葉節點中的地址的方法。例如，在查找地址操作中可利用包含在用於Intel®架構處理器的SSE4指令集中的PCMPGTQ（對於大於的比較打包數據）SIMD指令，如本文所描述的。換言之，可實現並行（例如向量）處理，如本文所描述的。

在一些實施例中，可管理共享地址空間內的多個自由列表。共享地址空間內的多個自由列表中的一個或多個可被指配給相應處理器、核和/或線程。處理器、核和/或線程然後可配置成從其指配的自由列表中添加和/或移除區間。從而，可避免與自由列表關聯的鎖定競爭。

從而，符合本公開的實現可類似於配置成存儲單個大稀疏文件的簡單文件系統。分配的空間可包含一個或多個數據區間、提供主機地址空間與裝置地址空間之間映射的一個或多個葉節點以及將索引節點與葉節點相關的樹結構。數據區間對應於將主機LBA範圍連續映射到裝置LBA範圍。自由裝置LBA可由堆樣式的（heap style）（即，可用的自由存儲器池）自由列表管理。

圖1圖示了符合本公開幾個實施例的計算系統100的系統框圖。計算系統100可包含但不限於：伺服器、工作站計算機、臺式計算機、膝上型計算機、平板計算機（例如iPad®、GalaxyTab®等）、超可攜式計算機、超移動計算機、上網本計算機和/或亞筆記本計算機；行動電話，包含但不限於智慧型電話（例如基於iPhone®、Android®的電話、基於Blackberry®、Symbian®的電話、基於Palm®的電話等）和/或特色電話。

系統100包含主機計算裝置102和NVM存儲裝置（例如SSD 104），並且可包含一個或多個外圍裝置106。主機102包含處理器110、晶片集112和存儲器114。處理器110可包含一個或多個處理單元（例如處理器和/或核），並且配置成執行與計算裝置100關聯的操作，如本文所描述的。處理器110可配置成執行一個或多個線程。晶片集112可包含SSD接口113。晶片集112和/或SSD接口113配置成將處理器110耦合到NVM存儲裝置104和/或外圍裝置106。SSD接口113可配置成使用一個或多個串行總線通信協議（例如PCIe（外圍組件互連Express）、SAS（串行附連SCSI（小計算機系統接口））、SATA（串行ATA（高級技術附連））等）與NVM存儲裝置104和/或一個或多個外圍裝置106通信。外圍裝置106例如可包：含用戶接口裝置，包含顯示器、觸控螢幕顯示器、印表機、鍵區、鍵盤等；通信邏輯，有線的和/或無線的；其它存儲裝置，包含硬碟驅動器、固態驅動器、可移動存儲介質等。應該指出，為了便於圖示和描述簡化系統100。

存儲器114可包含高速緩存和/或隨機存取存儲器。存儲器114配置成存儲一個或多個應用120、OS 122和應用庫124。存儲器114配置成存儲包含NVM基元142的間接邏輯140。應用120可配置成發起與NVM存儲裝置104相關的存儲器存取操作。例如，應用120可包含資料庫應用。存儲器存取操作包含讀、寫、丟棄和驗證。應用庫124可包含一個或多個應用編程接口（API）和/或其它應用，它們可由應用120用於促進應用120的操作。

OS 122可包含文件系統130和塊裝置驅動132。文件系統130配置成管理主機計算裝置102的文件存儲和/或檢索。塊裝置驅動132配置成管理主機計算裝置102與例如NVM存儲裝置104之間的輸入和輸出（I/O)操作。間接邏輯140和/或NVM基元142可被包含在OS 122、塊裝置驅動132和/或應用庫124中。在應用庫124中包含間接邏輯140和NVM基元142配置成促進應用120的直接I/O。間接邏輯140配置成接收一個或多個主機LBA以及可能的數據，將主機LBA映射到裝置LBA，並向使用一個或多個NVM基元142的NVM存儲裝置104提供裝置LBA，如本文所描述的。NVM存儲裝置104然後可將接收的裝置LBA映射到和/或轉換成物理存儲器地址，並且如果存儲器存取是寫操作，則存儲關聯的數據。

間接邏輯140配置成從一個或多個應用120接收存儲器存取請求。可經由OS 122和/或直接經由應用庫124接收請求。存儲器存取請求可包含讀、寫、刪除和/或驗證與一個或多個主機LBA標識的存儲器位置相關的操作。間接邏輯140配置成分配由裝置LBA標識的一個或多個扇區，並將主機LBA映射到分配的裝置LBA進行寫操作。如果寫操作針對與現有數據關聯的主機LBA，則寫操作可包含在提交新數據之後隨後丟棄現有數據，如本文所描述的。換言之，寫操作是寫時拷貝。 間接邏輯140進一步配置成丟棄（即返回到自由列表）與刪除的數據相關的裝置LBA。間接邏輯140配置成當執行存儲器存取操作時，利用NVM基元142。

NVM基元142包含原子多寫、原子寫、稀疏編址、丟棄、驗證、原子丟棄和原子多丟棄。原子多寫和原子寫基元配置成將一個或多個扇區從主機LBA空間寫到裝置LBA空間，作為事務。扇區可以是不連續的。在原子寫操作中，全部所有數據變成被寫，或者沒有任何數據變成被寫。從而，如果在操作期間中斷（例如功率損耗）發生，則現有老數據保持有效。在整個事務之前或者之後，從一個或多個相同主機LBA其它同時發生的讀和/或向其寫。在稀疏編址中，主機LBA空間大於裝置LBA空間，並且至少一些主機LBA可保持不映射。當寫主機LBA時，稀疏編址基元配置成將未映射的主機LBA動態映射到裝置LBA。丟棄包含從裝置LBA隱式地不映射主機LBA。驗證配置成允許應用確定是映射還是不映射選擇的LBA。原子多丟棄和原子丟棄基元配置成作為丟棄全部所有數據或者不丟棄任何數據的事務（類似於原子多寫和原子寫基元）執行丟棄。

從而，符合本公開的系統和方法配置成提供間接，將主機LBA映射到裝置LBA。與搜索樹相關的葉節點配置成包含主機LBA、裝置LBA和關聯的長度。下面的實現然後可從應用中抽象，同時允許在裝置驅動132、OS 122 I/O層和/或應用庫124中的一個或多個中實現間接邏輯140和NVM基元142（例如對於使用直接I/O的應用）。NVM存儲裝置104然後可將裝置LBA轉換到物理存儲器地址，並將數據存儲到目標物理存儲器地址。

NVM存儲裝置104包含驅動器控制器150、非易失性物理存儲器152、主機接口156，並且可包含高速緩衝存儲器158。驅動器控制器150配置成例如經由晶片集112、SSD接口113和主機接口156，從間接邏輯140接收裝置LBA以及關聯的數據（如果有任何的話）。例如，非易失性物理存儲器152可包含相對低等待時間的字節可存取非易失性存儲器技術，其包含但不限於：磁阻存儲器（MRAM）、相變存儲器（PCM、PRAM）、相變存儲器和開關（PCMS）、阻性存儲器、鐵電存儲器(F-RAM, FeRAM)、自旋轉移轉矩存儲器（STT）、熱輔助的開關存儲器(TAS)、千足蟲存儲器、浮動結柵存儲器(FJG RAM)、電池備份RAM等，如本文所描述的。驅動器控制器150包含配置成將裝置LBA轉換成物理存儲器地址（PMA）的快閃記憶體轉換層(FTL) 154。驅動器控制器150然後可配置成將裝置LBA映射到PMA，並將接收的數據存儲到對應於裝置LBA的非易失性物理存儲器152中的PMA。

從而，間接邏輯140可從包含主機LBA的一個或多個應用120接收存儲器存取請求，並且可包含到扇區關聯的數據的關聯的數據（或指針）的一個或多個扇區。間接邏輯140然後可利用主機LBA作為索引來遍歷B+樹。間接邏輯140可在裝置地址空間中分配對應於數據扇區長度的數據區間，並提供從主機LBA到裝置LBA的映射。該映射可包含在葉節點中。NVM存儲裝置104可從間接邏輯140接收裝置LBA和關聯的數據，並且然後可將裝置LBA轉換成物理存儲器地址，並存儲關聯的數據。可響應於存儲器存取請求而對於一個或多個數據扇區執行此類操作，而不等待附加的數據扇區。

圖2圖示了符合本公開各種實施例的裝置LBA空間的示例存儲布局200。裝置LBA空間與NVM存儲裝置104的非易失性物理存儲器152相關。換言之，驅動器控制器150可將裝置LBA空間映射到或轉換成非易失性物理存儲器152 PMA空間，在其中可發生實際存儲。裝置LBA空間200包含三個區域：元數據202、事務日誌204和數據部分206。元數據202包含與間接狀態相關的固定欄位，如本文所描述的。事務日誌204配置成包含與分配裝置存儲器（「分配」）和使裝置存儲器自由（「自由」）相關的記錄。事務日誌204配置成存儲與暫時配置成支持原子操作的事務標識符（ID）相關的一個或多個記錄。數據部分206可包含與數據區間和索引節點相關的裝置LBA，如本文所描述的。區間是主機LBA範圍到裝置LBA範圍的連續映射。數據區間可由樹結構中的主機LBA索引。樹結構可包含B樹、B+樹和/或它們的變量。存儲布局200配置為配置成存儲相對大的稀疏文件的相對簡單的文件系統。修改可作為寫時拷貝執行，如本文所描述的。自由裝置LBA即自由區間可由堆樣式的自由列表管理。

圖3圖示了符合本公開各種實施例的圖2的裝置LBA空間200的示例元數據布局300。元數據300包含事務日誌LBA（開始）302、事務日誌大小304、事務日誌最後提交LBA 306、事務日誌頭LBA 308、索引根節點LBA 310和自由頭列表LBA 312。事務日誌LBA 302配置成包含事務日誌的開始裝置LBA。事務日誌大小304配置成包含扇區中的事務日誌大小。事務日誌最後提交LBA 306配置成包含最近「提交」記錄的事務日誌204中的位置，如本文所描述的。事務日誌頭LBA 308配置成包含寫到事務日誌204的最後條目的位置。索引根節點LBA 310配置成包含對應於搜索樹根節點的裝置LBA，如本文所描述的。自由頭列表LBA 312配置成包含對應於自由列表頭的裝置LBA。自由列表與裝置LBA空間中的未分配的裝置LBA相關。在搜索時，可從自由頭列表LBA 312到達其它自由列表區間。

間接邏輯140配置成保持和/或更新元數據202和事務日誌204。可關於來自應用120的存儲器存取請求，更新元數據202和/或事務日誌204。存儲器存取請求可包含寫、讀、丟棄和/或驗證對應於一個或多個主機LBA的存儲器單元。當存儲器存取請求導致包含在元數據202、300中的參數的改變時，可更新元數據202、300。例如，自由列表頭LBA 312可響應於分配一個或多個裝置LBA的分配和/或使一個或多個裝置LBA自由的丟棄而改變。

可利用事務日誌204支持當對存儲的數據和/或索引節點的改變提交時完成的原子操作。事務日誌204配置成提供最近的事務的檢查點。事務日誌204配置成包含與事務ID相關的一個或多個記錄。如果存儲器存取操作中斷，則在存儲器存取操作之前，可利用記錄返回到一個狀態。間接邏輯140配置成在存儲器存取操作期間和/或之後，從事務日誌204添加、更新和/或刪除記錄。響應於存儲器存取請求，間接邏輯140可生成與存儲器存取關聯的唯一事務標識符（ID）。事務日誌204包含與每個事務ID關聯的一個或多個記錄。每個記錄包含日誌條目類型和一個或多個關聯的參數。事務日誌204條目類型包含「分配」、「自由意圖（free intent）」、「提交」和「自由」。

分配指示已經從自由列表中移除區間。與分配關聯的參數包含開始LBA、分配長度、新自由列表LBA。開始LBA標識正在分配的區間的開始裝置LBA。分配長度對應於分配的區間中的扇區數。在已經分配了區間之後，新自由列表頭LBA對應於新自由列表頭裝置LBA。換言之，已經用分配移除現有頭。

自由意圖指示，區間應該被返回到自由列表。自由意圖參數包含自由意圖LBA和自由意圖長度。自由意圖LBA對應於（即標識）應該被返回到自由列表的區間的裝置LBA。自由意圖長度對應於應該使自由的區間中的扇區數。例如，可響應於丟棄而使區間自由。在另一示例中，可在寫時使區間自由。在此示例中，由於寫操作是對應於老數據的寫時拷貝裝置LBA，如果可使任何自由的話（如果寫成功完成的話）。提交指示事務完成。提交參數包含根節點LBA。如果根節點已經作為與事務ID關聯的存儲器存取操作的結果改變，則根節點LBA配置成提供搜索樹的新根的新裝置LBA。自由指示，區間應該被返回到自由列表。自由參數包含自由LBA和自由長度。自由LBA對應於返回到自由列表的區間的裝置LBA，並且自由長度對應於返回到自由列表的區間的扇區中的長度。

例如，在對裝置LBA（或一系列LBA）的寫操作期間，一個或多個扇區可被分配用於存儲與寫操作關聯的數據。唯一事務ID可與寫操作關聯，並被包含在事務日誌204中。事務日誌204中的關聯記錄然後可包含條目類型分配以及關聯的分配參數。在已經分配了與裝置操作關聯的區間之後，新自由列表頭LBA然後可對應於所得到的裝置LBA。分配裝置LBA參數然後可對應於分配的區間的開始裝置LBA，並且長度對應於扇區中的區間長度。間接邏輯140可配置成更新事務日誌中的參數。

如果寫操作包含之前所寫的裝置LBA（老數據），則間接邏輯140還可創建和與老數據關聯的裝置LBA相關的自由意圖記錄。如果寫操作被中斷並且未完成，則間接邏輯140配置成至少部分基於事務日誌204「滾回」到老數據。如果在完成之後但在自由的區間或節點已經返回到自由列表之前寫操作中斷，則間接邏輯140配置成至少部分基於事務日誌204「前滾」，並且重新開始將自由的區間和節點返回到自由列表。對應於事務ID的事務204的部分可在存儲器存取操作期間存在，並且可在與事務ID關聯的操作已經成功完成之後取消分配。換言之，事務日誌的元素可以是暫時的。

數據部分206包含分配的區間和/或葉節點、索引節點的區域和自由列表。索引節點包含根節點和內部節點，並且可包含多個葉節點。最初，數據部分206可對應於單個大自由列表條目。換言之，最初，數據部分206可以不包含索引節點和分配的區間。在操作中，可分配和/或更新索引節點，並且可分配一個或多個葉節點和/或數據區間。可響應於對連續的一系列「新」主機LBA的寫請求而分配葉節點以及關聯的數據區間。可用與葉節點的大小加上數據區間的大小對應的大小，分配自由區間。可響應於與主機LBA關聯的更新請求而更新葉節點，分配新數據區間，並將老區間標記為「自由意圖」。如果存儲器存取操作成功完成，則然後可使老數據區間自由。可響應於丟棄（即刪除）請求而使葉節點和新數據區間自由。

最初，數據部分206可包含一個自由列表條目。每個自由列表條目包含相應第一扇區中的長度參數和參數下一裝置LBA。長度參數對應於關聯的自由列表部分（「項目」）中的扇區數。參數下一LBA對應於自由列表中下一項目的裝置LBA。從而，初始自由列表條目可包含鄰近（在裝置LBA空間中）事務日誌204的最後裝置LBA的第一裝置LBA。

在操作中，當分配葉節點和/或區間時，可至少部分基於所分配的一系列裝置LBA和下一自由裝置LBA，更新受影響的自由列表條目。相應自由列表條目可被包含在每個系列連續自由裝置LBA（即自由區間）的第一扇區中。當使葉節點和/或區間自由時，自由列表條目可被寫到數據區間和/或葉節點的第一扇區。例如，當使區間和/或索引節點自由時，區間和/或索引節點變成自由列表中的新條目。自由列表頭LBA 312然後可被寫為條目中的下一裝置LBA參數。新條目的裝置LBA然後被寫到元數據202，作為新自由列表頭LBA 312。

自由列表是「堆樣式的」自由列表，因為它類似於易失性存儲器的堆存儲器管理器的自由列表。在操作期間，可向自由列表添加項目或從中移除項目。自由列表可變得碎片化，並且條目可能太小而不能存儲對應於連續的一系列主機LBA的數據。數據然後可被分成足以將數據放入自由列表條目的多個區間。對應的葉節點然後可包含多個映射，其中每個不連續區間一個映射。

圖4圖示了符合本公開一個實施例的具有分配的索引節點（包含葉節點）、數據區間和自由空間410的示例數據部分400。為了容易圖示，未示出自由列表條目。示例數據部分400包含根節點402、兩個內部節點404a、404b、四個葉節點406a、406b、406c、406d和八個區間408a、...、408h。在此示例中，根節點402指向兩個內部節點404a、404b。在此示例中，每個內部節點404a、404b分別指向兩個葉節點406a和406b以及406c和406d。每個葉節點指向一個或多個相應區間。

索引節點402、404a、404b、406a、406b、406c、406d和數據區間408a、...、408h都可從同一自由列表分配，如本文所描述的。對於相對低等待時間的NVM，可以避免在自由空間的單獨連續部分中保持索引節點和數據。根節點402和內部節點404a、404b可各包含至少對應於搜索樹（例如B+樹）一部分的索引和指針。索引可與主機LBA相關，並且指針可與裝置LBA相關。葉節點配置成包含將數系列主機LBA映射到數系列裝置LBA（例如數據區間）的多個參數。例如，葉節點可包含主機LBA、對應的裝置LBA和扇區中的長度，例如{主機LBA，裝置LBA，長度}

例如，在操作中，與查詢主機LBA相關的查找包含遍歷該樹以找到具有小於或等於查詢主機LBA的最大主機LBA的葉節點。然後可評估葉節點的關聯長度，以確定所分配的一系列主機LBA是否包含查詢主機LBA。如果查詢主機LBA被包含在該系列LBA中，則然後可選擇關聯的裝置LBA。然後可處理存儲器存取操作。可通過將操作編組成事務來實現跨多個主機LBA系列的原子操作。換言之，原子操作不限於連續主機LBA或連續裝置LBA。

從而，數據部分可包含多個索引節點、多個葉節點和多個數據區間。數據部分可進一步包含一個或多個自由區間。存儲器存取操作可包含使用查找主機LBA作為搜索索引來遍歷搜索樹。然後可至少部分基於包含在葉節點中的存儲的主機LBA，並且至少部分基於關聯的長度，選擇葉節點。例如，如果查找主機LBA包含在由存儲的主機LBA和長度定義的一系列主機LBA中，則可選擇葉節點。然後可標識對應的裝置LBA。換言之，葉節點配置成提供從查找主機LBA到標識的裝置LBA的映射。在操作中，可從同一樹列表分配索引節點、葉節點和區間。可從自由列表使葉節點和/或區間自由。

在實施例中，可通過向量處理促進搜索樹的遍歷。例如，處理器110可配置用於向量處理，並且間接邏輯140可配置成使用向量處理管理搜索樹的遍歷。向量處理包含單指令多數據（SIMD）。換言之，可對多個元素並行執行操作。元素例如可包含在向量中。

搜索樹包含B+樹，如本文所描述的。搜索樹中的索引包含和/或有關主機LBA。查找操作配置成確定在葉節點中是否包含查找（即查詢）主機LBA。如果查找主機LBA大於或等於存儲的主機LBA並小於存儲的主機LBA加上關聯的長度，則查找主機LBA被包含在葉節點中。如果查找主機LBA被包含在葉節點中，則對應裝置LBA已經被分配並且未自由。如果查找操作被包含在驗證操作中，則驗證操作可成功。如果查找主機LBA未包含在葉節點中，則對應裝置LBA未分配和/或已經自由。在此情況下，關聯的驗證操作可失敗，或者可確認，對應裝置LBA已經自由。

在此實施例中，一個或多個葉節點的內容可配置為用於查找操作的多個向量。第一向量可包含多個存儲的主機LBA，並且第二向量可包含多個對應長度。查找向量可由多個查找主機LBA形成。查找向量然後可與第一向量比較，並且比較結果可被存儲在第一映射向量中。例如，對於每個查找主機LBA存儲的主機LBA比較，如果存儲的主機LBA小於或等於查找LBA，則第一映射向量可包含第一值（例如集），並且否則可包含第二值（例如清除）。

最大LBA向量然後可通過對第一向量和第二向量的對應元素求和（即，將存儲的主機LBA和對應長度相加以確定與區間關聯的一系列主機LBA）來形成。查找向量然後可與最大LBA向量比較，並且比較結果可被存儲在第二映射向量中。例如，對於每個查找主機LBA最大LBA比較，如果最大LBA大於查找主機LBA，則記錄映射向量可包含第一值，並且否則可包含第二值。

第一映射向量和第二映射向量然後可進行比較。對於第一映射向量中的每個元素和第二映射向量中的對應元素，如果查找主機LBA大於或等於存儲的主機LBA（例如第一映射向量元素對應於第一值）並且查找主機LBA小於最大主機LBA（例如第二映射向量元素對應於第一值），則查找主機LBA對應於由包含存儲的主機LBA的葉節點映射的主機LBA。

從而，可並行執行多個查找（即查詢）主機LBA的查找。此類並行處理可通過減少遍歷搜索樹的時間量來增加吞吐量。

圖5是根據本公開各種實施例的存儲器存取操作的流程圖500。具體地說，流程圖500圖示：例如由間接邏輯140接收存儲器存取請求，確定存儲器存取請求是否是讀、丟棄、驗證或寫操作，並且然後執行操作的主機計算裝置部分。操作例如可由圖1的主機計算裝置102執行。

這個實施例的操作可開始於接收存儲器存取請求502。例如，可從應用120接收存儲器存取請求。在操作504可接收與數據扇區關聯的主機LBA。在操作506可以確定存儲器存取請求是否對應於讀、丟棄、驗證和/或寫請求。如果存儲器存取請求對應於讀、丟棄和/或驗證請求，則在操作510可使用查詢主機LBA作為索引遍歷搜索樹。在操作512，可以確定是否存在包含與查詢主機LBA對應的存儲主機LBA的葉節點。如果此類葉節點不存在，則在操作514可傳遞結果。例如，結果可以驗證，裝置LBA已經被丟棄。在另一示例中，結果可對應於錯誤。在操作516，程序流然後可返回。如果此類葉節點確實存在，則操作518可包含利用與查詢主機LBA關聯的裝置LBA執行存儲器存取操作。在操作520，程序流然後可返回。

如果存儲器存取操作對應於寫請求，則在操作530，主機LBA可被映射到與NVM物理存儲器地址相關的裝置LBA。操作532可包含向NVM存儲裝置提供數據扇區。NVM存儲裝置然後可將裝置LBA轉換成物理存儲器地址，並存儲數據扇區。在操作534，程序流可返回。

從而，存儲器存取請求可包含主機LBA。寫操作可包含將主機LBA映射到裝置LBA。裝置LBA以及關聯的數據扇區然後可被提供給NVM存儲裝置進行存儲。可避免等待包含多個扇區的數據段。

圖6是根據本公開各種實施例的寫和丟棄操作的流程圖600。操作例如可由圖1的主機計算裝置102和/或NVM存儲裝置104執行。

這個實施例的操作可在開頭602開始。操作604包含創建事務ID。事務ID可包含在事務日誌中。在操作606可以確定分配大小。分配大小可包含葉節點和數據區間或者數據區間，如本文所描述的。操作608包含分配列表。操作608配置成分配總分配大小的區間，並更新自由列表，如本文所描述的。在操作610，可將數據寫到分配的數據區間。在操作611，與數據關聯的主機LBA可被映射到裝置LBA。映射可包含關聯的數據區間的長度。在操作612，可將B+樹節點寫到分配的數據區間。在操作614，可將節點寫到分配的空間。節點包含修改的和/或新的葉節點和內部節點，並且可包含根節點。例如裝置控制器可將節點寫到NVM存儲裝置的物理存儲器中的分配的空間。對於返回到自由列表的每個數據區間和/或節點，在操作616，可將「自由意圖」記錄寫到與事務ID關聯的事務日誌中。例如，更新現有存儲的數據及其關聯的丟棄「老」數據的丟棄操作和/或寫操作可導致要得到自由的葉節點和/或分配的數據區間（如果事務成功完成的話）。自由意圖條目類型可保持，直到事務完成。操作618可包含：將「提交」記錄寫到事務日誌。提交日誌條目配置成指示寫/丟棄事務（操作）成功完成。

在操作620，可以確定最頂端修改的節點是否是根節點。例如，B+樹節點可響應於重新平衡通過添加和/或刪除葉節點發起的搜索樹而修改。如果最頂端修改的節點是跟節點，則在操作622，元數據根節點可被設置成新根節點。如果最頂端修改的節點不是根節點，則在操作624，可將改變寫到父節點。換言之，此類節點更新不是寫時拷貝操作。在操作626，可釋放所有節點鎖定。在操作628，可使列表自由。自由列表對應於自由區間，並且區間列表對應於區間標記的自由意圖。在事務期間可以鎖列表。在操作630，程序流然後可結束。

圖7是根據本公開各種實施例的分配操作的流程圖700。具體地說，流程圖700圖示分配裝置存儲器中的區間。流程圖700是圖6的操作608的一個示例。操作例如可由圖1的主機計算裝置102執行。流程圖700的操作可開始於操作702，開始分配。在操作704，可使自由列表鎖定。鎖定配置成防止其它操作訪問並且可能改變自由列表，同時發生流程圖700的操作。

在操作706，可以確定是否存在要分配的任何區間。如果不存在要分配的區間，則程序流可前進到操作718。如果存在要分配的區間，則在操作708，可以讀自由列表中的頭自由區間。在操作710，可以確定頭自由區間是否大於需要的。如果頭區間大於需要的，則在操作712，可以分割區間。例如，自由區間可被分成分配的區間和剩餘區間。在714，可以寫新頭區間中的剩餘區間的下一指針和新大小。操作716包含：將分配記錄寫到事務日誌。程序流然後可前進到操作706。從而，可重複操作706、708、710、716以及可能的712和714，直到不再存在區間要分配為止。在操作718，可使自由列表解鎖。在操作720，可以返回分配的區間列表。從而，可從自由列表分配一個或多個區間。區間可包含數據區間和/或節點區間，如本文所描述的。

圖8是根據本公開各種實施例的使自由操作的流程圖800。具體地說，流程圖800圖示使裝置LBA空間中的區間自由。流程圖800是響應於圖6的操作616而使區間自由的操作的一個示例。換言之，流程圖800配置成使標記為「自由意圖」的區間自由。操作例如可由圖1的主機計算裝置102執行。在操作802，可響應於與區間相關的「自由意圖」的事務日誌條目而發起流程圖800的操作。在操作804，可使自由列表鎖定。操作806包含將下一裝置LBA和長度寫到自由區間。操作808可包含：將「自由」記錄寫在事務日誌中。在操作810，可使自由列表解鎖。

圖9是根據本公開各種實施例使用SIMD（單指令多數據）的查找操作的流程圖900。具體地說，流程圖900圖示由配置成執行SIMD指令的處理器（例如向量處理器）執行查找操作。操作例如可由圖1的主機計算裝置102執行。流程圖900的操作可在開頭902開始。操作904可包含比較存儲的主機LBA的向量與查找LBA的向量（查找向量）。在操作906，比較結果可被存儲在第一映射向量中。例如，如果相應存儲的主機LBA小於相應查找主機LBA（即查詢主機LBA），則第一映射向量中的每個結果可對應於第一值，並且否則對應於第二值。操作908可包含將存儲的主機LBA的向量加上相應長度的向量。在操作910，操作908的結果可被存儲在最大LBA向量中。操作912包含比較最大LBA向量與查找向量。操作914可包含將操作912的比較結果存儲在第二映射向量中。在操作916可以比較第一映射向量與第二映射向量。

在操作918，可以確定相應查找主機LBA是否大於或等於相應存儲的主機LBA，並且相應查找主機LBA是否小於相應最大主機LBA。換言之，可以比較第一映射向量與第二映射向量。如果相應查找主機LBA大於或等於相應存儲的主機LBA，並且相應查找主機LBA小於相應最大主機LBA，則分配相應查找主機LBA，920。換言之，查找主機LBA對應於存儲的主機LBA。如果相應查找主機LBA小於相應存儲的主機LBA，和/或相應查找主機LBA大於相應最大主機LBA，則不分配查找主機LBA，922。

圖10是根據本公開一個實施例的多個自由列表的操作的流程圖1000。具體地說，流程圖1000圖示了多個自由列表的管理，每個自由列表配置成由相應處理器、核和/或線程維護。操作例如可由圖1的主機計算裝置102執行。流程圖1000的操作可開始於開頭1002。操作1004包含用多個自由列表初始化數據部分。在操作1006，可將相應自由列表指配給選擇的處理器、核和/或線程。操作1008包含：從當前處理器、核和/或線程的相應自由列表分配或返回區間。在操作1010，程序流然後可結束。

雖然圖5至10的流程圖圖示了根據各種實施例的操作，但要理解到，對於其它實施例，並不是在圖5、6、7、8、9和/或10中描繪的所有操作都是必要的。此外，在本文完全可以預見，在本公開的其它實施例中，在圖5、6、7、8、9和/或10中描述的操作和/或本文描述的其它操作可以在任何附圖中都未明確顯示的方式組合，並且此類實施例可包含比在圖5、6、7、8、9和/或10中圖示的更少的或更多的操作。由此，針對一個附圖中未明確示出的特徵和/或操作的權利要求被視為在本公開的範圍和內容內。

OS 122可配置成管理系統資源並控制在每個相應裝置和/或系統（例如主機計算裝置102和/或NVM存儲裝置104）上運行的任務。例如，可使用Microsoft Windows、HP-UX、Linux或UNIX實現OS，儘管可使用其它作業系統。在一些實施例中，OS可由可向在一個或多個處理單元上運行的各種作業系統（虛擬機）提供底層硬體的抽象層的虛擬機監控器（或監管程序）替換。

存儲器114可包含一個或多個如下類型的存儲器：半導體固件存儲器、可編程存儲器、非易失性存儲器、只讀存儲器、電可編程存儲器、隨機存取存儲器、快閃記憶體、磁碟存儲器和/或光碟存儲器。附加地或備選地，系統存儲器可包含其它類型和/或以後開發的類型的計算機可讀存儲器。

本文描述的操作的實施例可實現在計算機可讀存儲裝置中，其上存儲有指令，所述指令當由一個或多個處理器執行時執行所述方法。處理器例如可包含處理單元和/或可編程電路。存儲裝置可包含機器可讀存儲裝置，包含任何類型的有形、非暫時性存儲裝置，例如任何類型的盤，包含軟盤、光碟、壓縮盤只讀存儲器（CD-ROM）、壓縮盤可重寫（CD-RW）和磁光碟、半導體裝置，諸如只讀存儲器（ROM）、隨機存取存儲器（RAM），諸如動態和靜態RAM、可擦除可編程只讀存儲器（EPROM）、電可擦除可編程只讀存儲器（EEPROM）、快閃記憶體、磁卡或光卡、或適合於存儲電指令的任何類型存儲裝置。

如本文任何實施例中所使用的術語「邏輯」可指的是配置成執行上面提到的操作的軟體、固件和/或電路。軟體可實施為記錄在非暫時性計算機可讀存儲介質上的軟體包、代碼、指令、指令集和/或數據。固件可實施為硬編碼在（例如非易失性）存儲器裝置中的代碼、指令或指令集和/或數據。

如在本文任何實施例中所使用的「電路」例如可包括硬連線電路、可編程電路（諸如包括一個或多個單獨指令處理核心的計算機處理器）、狀態機電路和/或存儲由可編程電路執行的指令的固件（單個或以任何組合）。邏輯可共同或單獨實施為形成更大系統（例如集成電路（IC）、專用集成電路（ASIC）、片上系統（SoC）、臺式計算機、膝上型計算機、平板計算機、伺服器、智慧型電話等）的一部分的電路。

在一些實施例中，硬體描述語言（HDL）可用於規定用於本文描述的各種邏輯和/或電路的電路和/或邏輯實現。例如，在一個實施例中，硬體描述語言可遵守或兼容超高速集成電路（VHSIC）硬體描述語言（VHDL），其可實現本文描述的一個或多個電路和/或邏輯的半導體製造。VHDL可遵守或兼容IEEE標準1076-1987、IEEE標準1076.2、IEEE1076.1、VHDL-2006的IEEE草稿3.0、VHDL-2008的IEEE草稿4.0和/或IEEE VHDL標準的其它版本和/或其它硬體描述標準。

從而，與本公開的教導一致，系統和方法包含主機計算裝置中的間接邏輯，其實現NVM基元，同時避免日誌構造的存儲及其關聯的開銷。NVM基元包含但不限於原子寫、原子多寫、原子寫、稀疏編址、丟棄、驗證、原子丟棄和原子多丟棄。間接邏輯配置成響應於寫請求而管理向選擇的字節可存取NVM存儲裝置寫數據扇區，而不等待附加扇區累積。間接邏輯提供配置成將LBA映射到裝置LBA的間接層。NVM存儲裝置然後可將裝置LBA映射和/或轉換成PMA。

在一些實施例中，可使用SIMD（單指令多數據）操作，實現查找包含在未分類的B樹葉節點中的地址的方法。換言之，可實現並行（即向量）處理，如本文所描述的。

在一些實施例中，可管理共享地址空間內的多個自由列表。共享地址空間內的多個自由列表中的一個或多個可被指配給相應處理器、核和/或線程。處理器、核和/或線程然後可配置成從其指配的自由列表中添加和/或移除區間。從而，可避免與自由列表關聯的鎖定競爭。

示例

本公開的示例包含諸如與固態驅動器中的主機管理的非易失性存儲器相關的方法、用於執行方法動作的部件、裝置或設備或計算機可讀存儲裝置的主題，如下面所論述的。

示例1

根據這個示例，提供了一種包含處理器、晶片集、存儲器和簡潔邏輯的設備。間接邏輯接收與第一數據扇區關聯的主機邏輯塊地址（LBA），將主機LBA從主機地址空間映射到裝置地址空間中的第一裝置LBA，裝置地址空間與非易失性存儲器（NVM）存儲裝置物理存儲器地址空間相關，並且向NVM存儲裝置提供第一數據扇區和第一裝置LBA。

示例2

這個示例包含示例1的元件，其中所述裝置地址空間包含元數據、事務日誌和數據部分。

示例3

這個示例包含示例2的元件，其中數據部分包含自由列表、多個索引節點、多個葉節點和多個區間，並且所述間接邏輯進一步從所述自由列表分配葉節點和區間，所述區間對應於所述第一數據扇區。

示例4

這個示例包含示例3的元件，其中所述間接邏輯進一步向葉節點寫所述主機LBA、所述第一裝置LBA和對應於所述第一數據扇區的長度。

示例5

這個示例包含根據示例1至4中任一示例的元件，其中所述間接邏輯進一步接收與所述主機LBA關聯的第二數據扇區，將所述主機LBA映射到第二裝置LBA，向所述NVM存儲裝置提供所述第二數據扇區和所述第二裝置LBA，並將葉節點更新成包含所述第二裝置LBA。

示例6

這個示例包含根據示例1至4中任一示例的元件，其中所述處理器是向量處理器，並且所述間接邏輯進一步遍歷搜索樹以並行查找多個查詢主機LBA。

示例7

這個示例包含根據示例2至3中任一示例的元件，其中所述數據部分包含多個自由列表，每個自由列表由相應處理器、核或線程管理。

示例8

這個示例包含根據示例1至4中任一示例的元件，其中間接邏輯進一步存儲與主機地址空間相關的一個或多個索引節點，索引節點促進對於存儲的數據的搜索。

示例9

這個示例包含示例8的元件，其中索引節點布置在搜索樹中。

示例10

這個示例包含示例9的元件，其中搜索樹是B+樹。

示例11

這個示例包含根據示例1至4中任一示例的元件，其中間接邏輯進一步確定第一數據扇區是否被成功存儲在NVM存儲裝置中。

示例12

這個示例包含根據示例1至4中任一示例的元件，其中所述間接邏輯包含與原子寫、原子丟棄、原子多寫、原子多丟棄、稀疏編址和驗證中一個或多個對應的一個或多個NVM基元。

示例13

這個示例包含示例5的元件，其中如果成功存儲了所述第二數據扇區，則所述間接邏輯進一步丟棄所述第一數據扇區。

示例14

這個示例包含根據權利要求1至4中任一項的元件，其中所述主機地址空間大於所述裝置地址空間。

示例15

這個示例包含根據示例2至3中任一示例的元件，其中事務日誌包含與第一裝置LBA相關的至少一個日誌條目和事務標識符（ID），每個日誌條目包含日誌條目類型。

示例16

這個示例包含示例15的元件，其中每個日誌條目選自包含分配、自由意圖、提交和自由的列表。

示例17

這個示例包含根據示例1至4中任一示例的元件，其中間接邏輯進一步創建事務標識符（ID），確定與第一數據扇區相關的分配大小，分配至少一個區間，向至少一個區間的一個數據區間寫第一數據扇區，並向至少一個區間的節點區間寫索引節點。

示例18

這個示例包含示例17的元件，其中間接邏輯進一步向與要返回到自由列表的節點區間和數據區間中的至少一個的事務ID關聯的事務日誌寫入自由意圖記錄。

示例19

這個示例包含示例17的元件，其中如果第一數據扇區被成功存儲到NVM存儲裝置，則間接邏輯進一步向與事務ID關聯的事務日誌寫入提交記錄。

示例20

這個示例包含示例17的元件，其中間接邏輯進一步調整根節點。

示例21

這個示例包含示例17的元件，其中間接邏輯進一步讀自由列表中頭區間的長度，如果頭區間的大小大於分配大小，則將頭區間分成分配的區間和剩餘區間，向剩餘區間寫剩餘區間大小和下一指針，並向與事務ID關聯的事務日誌寫入分配記錄。

示例22

這個示例包含示例18的元件，其中間接邏輯進一步至少部分基於自由意圖日誌向自由的區間寫下一裝置LBA和長度，並向事務日誌寫入自由記錄。

示例23

這個示例包含示例6的元件，其中間接邏輯進一步將存儲的主機LBA的向量與包含多個查找LBA的查找向量相比較，將比較結果存儲在第一映射向量中；將存儲的主機LBA的向量和與存儲的主機LBA關聯的相應長度的向量之和存儲在最大LBA向量中；將查找向量與最大LBA向量的比較結果存儲在第二映射向量中；以及至少部分基於第一映射向量和第二映射向量確定每個查找主機LBA是否對應於相應存儲的主機LBA。

示例24

根據這個示例，提供了一種方法。該方法包含：由間接邏輯接收與第一數據扇區關聯的主機邏輯塊地址（LBA）；由間接邏輯將主機LBA從主機地址空間映射到裝置地址空間中的第一裝置LBA，裝置地址空間與非易失性存儲器（NVM）存儲裝置物理存儲器地址空間相關；由間接邏輯向NVM存儲裝置提供第一數據扇區和第一裝置LBA。

示例25

這個示例包含示例24的元件，其中所述裝置地址空間包含元數據、事務日誌和數據部分。

示例26

這個示例包含示例25的元件，並且進一步包含：由所述間接邏輯從自由列表分配葉節點和區間，所述區間對應於所述第一數據扇區，所述數據部分包含所述自由列表、多個索引節點、多個葉節點和多個區間。

示例27

這個示例包含示例26的元件，並且進一步包含：由所述間接邏輯向所述葉節點寫所述主機LBA、所述第一裝置LBA和對應於所述第一數據扇區的長度。

示例28

這個示例包含示例24的元件，並且進一步包含：由間接邏輯接收與主機LBA關聯的第二數據扇區；由間接邏輯將主機LBA映射到第二裝置LBA；由間接邏輯向所述NVM存儲裝置提供所述第二數據扇區和所述第二裝置LBA；以及由間接邏輯將葉節點更新成包含所述第二裝置LBA。

示例29

這個示例包含示例24的元件，並且進一步包含：由所述間接邏輯遍歷搜索樹以並行查找多個查詢主機LBA。

示例30

這個示例包含示例25的元件，其中所述數據部分包含多個自由列表，每個自由列表由相應處理器、核或線程管理。

示例31

這個示例包含示例24的元件，並且進一步包含：由間接邏輯存儲與主機地址空間相關的一個或多個索引節點，索引節點促進對於存儲的數據的搜索。

示例32

這個示例包含示例31的元件，其中索引節點布置在搜索樹中。

示例33

這個示例包含示例32的元件，其中搜索樹是B+樹。

示例34

這個示例包含示例24的元件，並且進一步包含：由間接邏輯確定第一數據扇區是否被成功存儲在NVM存儲裝置中。

示例35

這個示例包含示例24的元件，其中所述間接邏輯包含與原子寫、原子丟棄、原子多寫、原子多丟棄、稀疏編址和驗證中一個或多個對應的一個或多個NVM基元。

示例36

這個示例包含示例28的元件，並且進一步包含：如果成功存儲了所述第二數據扇區，則所述間接邏輯丟棄所述第一數據扇區。

示例37

這個示例包含示例24的元件，其中所述主機地址空間大於所述裝置地址空間。

示例38

這個示例包含示例25的元件，其中事務日誌包含與第一裝置LBA相關的至少一個日誌條目和事務標識符（ID），每個日誌條目包含日誌條目類型。

示例39

這個示例包含示例38的元件，其中每個日誌條目選自包含分配、自由意圖、提交和自由的列表。

示例40

這個示例包含示例24的元件，並且進一步包含：由間接邏輯創建事務標識符（ID）；由間接邏輯確定與第一數據扇區相關的分配大小；由間接邏輯分配至少一個區間；由間接邏輯向至少一個區間的一個數據區間寫第一數據扇區；以及由間接邏輯向至少一個區間的節點區間寫索引節點。

示例41

這個示例包含示例40的元件，並且進一步包含：由間接邏輯向與要返回到自由列表的節點區間和數據區間中的至少一個的事務ID關聯的事務日誌寫入自由意圖記錄。

示例42

這個示例包含示例40的元件，並且進一步包含：如果第一數據扇區被成功存儲到NVM存儲裝置，則由間接邏輯向與事務ID關聯的事務日誌寫入提交記錄。

示例43

這個示例包含示例40的元件，並且進一步包含：由間接邏輯調整根節點。

示例44

這個示例包含示例40的元件，並且進一步包含：由間接邏輯讀自由列表中頭區間的長度；如果頭區間的大小大於分配大小，則由間接邏輯將頭區間分成分配的區間和剩餘區間；由間接邏輯向剩餘區間寫剩餘區間大小和下一指針；以及由間接邏輯向與事務ID關聯的事務日誌寫入分配記錄。

示例45

這個示例包含示例41的元件，並且進一步包含：由間接邏輯至少部分基於自由意圖日誌向自由的區間寫下一裝置LBA和長度；以及由間接邏輯向事務日誌寫入自由記錄。

示例46

這個示例包含示例29的元件，並且進一步包含：由間接邏輯將存儲的主機LBA的向量與包含多個查找LBA的查找向量相比較；由間接邏輯將比較結果存儲在第一映射向量中；由間接邏輯將存儲的主機LBA的向量和與存儲的主機LBA關聯的相應長度的向量之和存儲在最大LBA向量中；由間接邏輯將查找向量與最大LBA向量的比較結果存儲在第二映射向量中；以及由間接邏輯至少部分基於第一映射向量和第二映射向量確定每個查找主機LBA是否對應於相應存儲的主機LBA。

示例47

根據這個示例，提供了一種計算機可讀存儲裝置，其上存儲了指令，所述指令當由一個或多個處理器執行時導致如下操作，包含：接收與第一數據扇區關聯的主機邏輯塊地址（LBA）；將主機LBA從主機地址空間映射到裝置地址空間中的第一裝置LBA，裝置地址空間與非易失性存儲器（NVM）存儲裝置物理存儲器地址空間相關；向NVM存儲裝置提供第一數據扇區和第一裝置LBA。

示例48

這個示例包含示例47的元件，其中所述裝置地址空間包含元數據、事務日誌和數據部分。

示例49

這個示例包含示例48的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：從自由列表分配葉節點和區間，所述區間對應於所述第一數據扇區，所述數據部分包含所述自由列表、多個索引節點、多個葉節點和多個區間。

示例50

這個示例包含示例49的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：向所述葉節點寫所述主機LBA、所述第一裝置LBA和對應於所述第一數據扇區的長度。

示例51

這個示例包含根據示例47至50中任一示例的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：接收與所述主機LBA關聯的第二數據扇區，將所述主機LBA映射到第二裝置LBA，向所述NVM存儲裝置提供所述第二數據扇區和所述第二裝置LBA，並將葉節點更新成包含所述第二裝置LBA。

示例52

這個示例包含根據示例47至50中任一示例的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：遍歷搜索樹以並行查找多個查詢主機LBA。

示例53

這個示例包含根據示例48和49中任一示例的元件，其中所述數據部分包含多個自由列表，每個自由列表由相應處理器、核或線程管理。

示例54

這個示例包含根據示例47至50中任一示例的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：存儲與主機地址空間相關的一個或多個索引節點，索引節點促進對於存儲的數據的搜索。

示例55

這個示例包含示例54的元件，其中索引節點布置在搜索樹中。

示例56

這個示例包含示例55的元件，其中搜索樹是B+樹。

示例57

這個示例包含根據示例47至50中任一示例的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：確定第一數據扇區是否被成功存儲在NVM存儲裝置中。

示例58

這個示例包含根據示例47至50中任一示例的元件，其中指令包含與原子寫、原子丟棄、原子多寫、原子多丟棄、稀疏編址和驗證中一個或多個對應的一個或多個NVM基元。

示例59

這個示例包含示例51的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：如果成功存儲了所述第二數據扇區，則丟棄所述第一數據扇區。

示例60

這個示例包含根據示例47至50中任一示例的元件，其中所述主機地址空間大於所述裝置地址空間。

示例61

這個示例包含根據示例48和49中任一示例的元件，其中事務日誌包含與第一裝置LBA相關的至少一個日誌條目和事務標識符（ID），每個日誌條目包含日誌條目類型。

示例62

這個示例包含示例61的元件，其中每個日誌條目選自包含分配、自由意圖、提交和自由的列表。

示例63

這個示例包含根據示例47至50中任一示例的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：創建事務標識符（ID），確定與第一數據扇區相關的分配大小，分配至少一個區間，向至少一個區間的一個數據區間寫第一數據扇區，並向至少一個區間的節點區間寫索引節點。

示例64

這個示例包含示例63的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：向與要返回到自由列表的節點區間和數據區間中的至少一個的事務ID關聯的事務日誌寫入自由意圖記錄。

示例65

這個示例包含示例63的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：如果第一數據扇區被成功存儲到NVM存儲裝置，則向與事務ID關聯的事務日誌寫入提交記錄。

示例66

這個示例包含示例63的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：調整根節點。

示例67

這個示例包含示例63的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：讀自由列表中頭區間的長度，如果頭區間的大小大於分配大小，則將頭區間分成分配的區間和剩餘區間，向剩餘區間寫剩餘區間大小和下一指針，並向與事務ID關聯的事務日誌寫入分配記錄。

示例68

這個示例包含示例64的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：至少部分基於自由意圖日誌向自由的區間寫下一裝置LBA和長度；以及向事務日誌寫入自由記錄。

示例69

這個示例包含示例52的元件，其中所述指令當由一個或多個處理器執行時導致如下附加操作，包含：將存儲的主機LBA的向量與包含多個查找LBA的查找向量相比較，將比較結果存儲在第一映射向量中；將存儲的主機LBA的向量和與存儲的主機LBA關聯的相應長度的向量之和存儲在最大LBA向量中；將查找向量與最大LBA向量的比較結果存儲在第二映射向量中；以及至少部分基於第一映射向量和第二映射向量確定每個查找主機LBA是否對應於相應存儲的主機LBA。

示例70

根據這個示例，存在一種計算機可讀存儲裝置，其上存儲了指令，所述指令當由一個或多個處理器執行時導致如下操作，包含：如示例24至46中任一示例的方法。

示例71

本公開的另一示例是一種系統，包含布置成執行如示例24至46中任一示例的方法的至少一個裝置。

示例72

本公開的另一示例是一種裝置，包含執行如示例24至46中任一示例的方法的部件。

本文已經採用的術語和表述被用作描述而非限制的說法，並且在使用此類術語和表述時沒打算排除所示出和描述的特徵的任何等同物（或其部分），並且要認識到，各種修改在權利要求書的範圍內是可能的。因而，權利要求書打算覆蓋所有此類等同物。

本文已經描述了各種特點、方面和實施例。特點、方面和實施例易於彼此組合以及變化和修改，這是本領域技術人員將理解的。本公開因此應該視為包含此類組合、變化和修改。