[發明專利]對具有非易失性存儲器的系統的較快樹扁平化

有效

• 申請號: 201210438667.0
• 申請日: 2012-09-14
• 公開（公告）號: CN102999429A
• 公開（公告）日: 2013-03-27
• 發明（設計）人: D·J·波斯特;V·科麥爾尼斯基
• 申請（專利權）人: 蘋果公司
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F3/06
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 宋海寧

技術領域

NAND快閃存儲器，以及其他類型的非易失性存儲器(“NVM”)，通常用于大規模存儲。例如，諸如便攜式媒體播放器的消費電子產品通常包括閃存以存儲音樂、視頻和其他媒體。

背景技術

具有NVM的系統可以包括數據結構，其將文件系統使用的邏輯地址映射到NVM的物理地址(例如，提供邏輯至物理的映射)。該結構經常可以駐留在易失性存儲器中。隨著更新現有文件或添加其他文件，存儲映射需要的存儲量可能相應增加。因此，在某些情況下，為該結構分配的存儲量不足以獲取所有的邏輯至物理映射。

發明內容

公開了對于具有非易失存儲器(“NVM”)的系統的較快樹扁平化(flatten)的系統和方法。樹可以存儲在系統的易失性存儲器中，其中樹可以包含在NVM的邏輯空間和物理地址之間的邏輯至物理的映射。當所述樹可用的存儲量低于預定閾值時，系統可能試圖減少NVM中的數據碎片數量，并因此可以扁平化樹的一部分。所釋放的樹存儲器的量可以添加回樹存儲器池。NVM接口可基于任何合適方法選擇最佳的樹的條目集合以結合，例如經過樹來移動一個或多個滑動窗口，當條件滿足時擴大滑動窗口，掃描樹時使用優先級隊列，和/或當更新樹時維護優先級隊列。

附圖說明

當結合附圖，參考如下詳細描述，本發明的以上和其他的方面和優勢將變得更加明顯，在圖中，同樣的附圖標記指相同的部件，其中：

圖1和2是根據本發明的各種實施例配置的電子設備的框圖；

圖3是根據本發明的各種實施例的非易失性存儲器的功能視圖；

圖4是根據本發明的各種實施例，邏輯塊地址到物理頁的示例性映射的框圖；

圖5是根據本發明的各種實施例，用于提供邏輯至物理映射的示例性樹的一部分的框圖；

圖6是根據本發明的各種實施例，邏輯塊地址至物理頁的另一示例性映射的框圖；

圖7是根據本發明的各種實施例，用于提供邏輯塊地址至物理映射的另一示例性樹的一部分的框圖；

圖8是根據本發明的各種實施例，用于較快樹扁平化的示例性處理的流程圖；

圖9是根據本發明的各種實施例，用于在非易失性存儲器中產生物理連續碎片的示例性處理的流程圖；

圖10A和10B是根據本發明的各種實施例，用于較快樹扁平化的另一示例性處理的流程圖；

圖11是根據本發明的各種實施例，用于較快樹扁平化的再一示例性處理的流程圖；

圖12是根據本發明的各種實施例，優先權隊列的框圖；

圖13是根據本發明的各種實施例，用于較快樹扁平化的另一示例性處理的流程圖；以及

圖14是根據本發明的各種實施例，另一優先級隊列的框圖。

圖15是根據本發明可替換實施例配置的存儲器接口的框圖。

圖16是根據本發明的另一可替換實施例配置的存儲器接口的框圖。

具體實施方式

公開了對于具有非易失存儲器(“NVM”)的系統的較快樹扁平化的系統和方法。樹可以存儲在系統的易失性存儲器中，其中樹可以包含NVM的邏輯空間和物理地址之間的邏輯至物理的映射。當所述樹可用的存儲量低于預定閾值時，系統的NVM接口可能試圖減少NVM中的數據碎片，并因此可以扁平化樹的一部分。所釋放的樹存儲器的量可以添加回樹存儲器池。

NVM接口例如通過將樹的條目的最佳集合結合成單個條目或節點而扁平化樹的一部分。最佳條目集合可以在邏輯空間中是連續的而在物理空間中是不連續的。因此，在選擇最佳條目集合之后，該NVM接口可以重新編碼對應于條目的數據片段，以至于片段可以是物理連續的。具體而言，NVM接口可以通過從NVM讀取對應于多個條目的數據而重新編碼所述片段，然后在易失性存儲器中保存該數據。在保存這些數據之后，NVM接口可將數據連續編入到NVM的新的超級塊。

NVM接口可以使用任何合適的方法選擇最佳條目集合。在某些實施例中，NVM接口可以使用一個或多個滑動窗口以獲得最佳條目集合。在某些情況下，可以為一個或多個滑動窗口中的每個保持最小跨度。然后，基于不同的最小跨度之間的比較，NVM接口可以選擇最佳條目集合。

在其他實施例中，NVM接口可以使用饑渴(greedy)方法以找到最佳的條目集合以扁平化。即，一旦發現最佳條目集合，NVM接口可以繼續在樹中尋找可以添加到最佳條目集合的額外連續條目。