平码五不中公式规律
  • / 31
  • 下载费用:30 金币  

主机管理的非易失性存储器.pdf

关 键 ?#21097;?/dt>
主机 管理 非易失性存储器
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201580045881.1

申请日:

2015.09.18

公开号:

CN106662985A

公开日:

2017.05.10

当前法律状态:

实审

有效性:

审中

法?#19978;?#24773;: 实质审查的生效IPC(主分类):G06F 3/06申请日:20150918|||公开
IPC分类号: G06F3/06; G06F12/02 主分类号: G06F3/06
申请人: 英特尔公司
发明人: B.E.维尔; D.J.威廉斯; A.冯
地址: 美国加利福尼亚州
优?#28909;ǎ?/td> 2014.09.26 US 14/498909
专利代理机构: 中国专利代理(香港)有限公司 72001 代理人: 王华强;张涛
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201580045881.1

授权公告号:

|||

法律状态公告日:

2017.06.06|||2017.05.10

法律状态类型:

实质审查的生效|||公开

摘要

一个实施例提供计算装置。计算装置包含:处理器;芯片集;存储器;以及间接逻辑。间接逻辑接收与第一数据扇区关联的主机逻辑块地址(LBA),将主机LBA从主机地址空间映射到装置地址空间中的第一装置LBA,装置地址空间与非易失性存储器(NVM)存储装置物理存储器地址空间相关,并且向NVM存储装置提供第一数据扇区和第一装置LBA。

权利要求书

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.一?#22336;?#27861;,包括:
由间接逻辑接收与第一数据扇区关联的主机逻辑块地址(LBA);
由所述间接逻辑将所述主机LBA从主机地址空间映射到装置地址空间中的第一装置
LBA,所述装置地址空间与非易失性存储器(NVM)存储装置物理存储器地址空间相关;
由所述间接逻辑向所述NVM存储装置提供所述第一数据扇区和所述第一装置LBA。
9.如权利要求8所述的方法,其中所述装置地址空间包括元数据、事务日志和数据部
分。
10.如权利要求9所述的方法,进一步包括:
由所述间接逻辑从自由列表分配叶节点和区间,所述区间对应于所述第一数据扇区,
所述数据部分包括所述自由列表、多个索引节点、多个叶节点和多个区间。
11.如权利要求10所述的方法,进一步包括:
由所述间接逻辑向所述叶节点写所述主机LBA、所述第一装置LBA和对应于所述第一数
据扇区的长度。
12.如权利要求8所述的方法,进一步包括:
由所述间接逻辑接收与所述主机LBA关联的第二数据扇区;
由所述间接逻辑将所述主机LBA映射到第二装置LBA;
由所述间接逻辑向所述NVM存储装置提供所述第二数据扇区和所述第二装置LBA;以及
由所述间接逻辑将叶节点更新成包括所述第二装置LBA。
13.如权利要求8所述的方法,进一步包括:由所述间接逻辑遍历搜索树以并行查找多
个查询主机LBA。
14.如权利要求9所述的方法,其中所述数据部分包括多个自由列表,每个自由列表由
相应处理器、核或线程管理。
15.一种系统,包括一个或多个计算机可读存储介?#21097;?#20854;上单独或组合存储指令,所述
指令当由一个或多个处理器执行时导致如下操作,包括:
接收与第一数据扇区关联的主机逻辑块地址(LBA);
将所述主机LBA从主机地址空间映射到装置地址空间中的第一装置LBA,所述装置地址
空间与非易失性存储器(NVM)存储装置物理存储器地址空间相关;
向所述NVM存储装置提供所述第一数据扇区和所述第一装置LBA。
16.如权利要求15所述的系统,其中所述装置地址空间包括元数据、事务日志和数据部
分。
17.如权利要求16所述的系统,其中所述指令当由一个或多个处理器执行时导致如下
附加操作,包括:
从自由列表分配叶节点和区间,所述区间对应于所述第一数据扇区,所述数据部分包
括所述自由列表、多个索引节点、多个叶节点和多个区间。
18.如权利要求17所述的系统,其中所述指令当由一个或多个处理器执行时导致如下
附加操作,包括:
向所述叶节点写所述主机LBA、所述第一装置LBA和对应于所述第一数据扇区的长度。
19.如权利要求15至18中任一项所述的系统,其中所述指令当由一个或多个处理器执
行时导致如下附加操作,包括:
接收与所述主机LBA关联的第二数据扇区;
将所述主机LBA映射到第二装置LBA;
向所述NVM存储装置提供所述第二数据扇区和所述第二装置LBA;以及
将叶节点更新成包括所述第二装置LBA。
20.如权利要求15至18中任一项所述的系统,其中所述指令当由一个或多个处理器执
行时导致如下附加操作,包括:
遍历搜索树以并行查找多个查询主机LBA。
21.如权利要求16至17中任一项所述的系统,其中所述数据部分包括多个自由列表,每
个自由列表由相应处理器、核或线程管理。
22.一种系统,包括一个或多个计算机可读存储介?#21097;?#20854;上单独或组合存储指令,所述
指令当由一个或多个处理器执行时导致如下操作,包括:如权利要求8至14中任一项所述的
方法。
23.一种系统,包含布置成执行如权利要求8至14中任一项所述的方法的至少一个装
置。
24.一种装置,包括执行如权利要求8至14中任一项所述的方法的部件。

说明书

主机管理的非易失性存储器

技术领域

本公开涉及非易失性存储器,具体地说,涉及固态驱动器中的非易失性存储器。

背景技术

固态驱动器(SSD)是可由计算装置使用的一种类型非易失性存储装置。一些SSD包
含用于存储的基于块的非易失性存储器,例如NAND型闪存。在NAND型闪存中,存储器单元被
编组成页和块。页可包含若干?#32440;冢?#20363;如4096),块可包含若干页(例如128),并且取决于SSD
的存储能力,NAND型闪存SSD可包含若干块(例如1024)。在NAND闪存中,读和写操作是基于
页的。换言之,数据页是可读/写的最小量。从而,为了响应于读或写较小的数据量的应用请
求,读或写整页。另外,NAND型闪存要求,在编程之前擦除存储器单元。此类擦除操作通常在
存储器单元的块上执行。

附图说明

要求权利的主题的特征和优点根据与之符合的实施例的如下详细描述将显而易
见,该描述应该参考附图考虑,附图中:

图1图示了符合本公开各种实施例的计算系统的功能框图;

图2图示了符合本公开各种实施例的装置逻辑块地址(LBA)空间的示例存储布局;

图3图示了符合本公开各种实施例的图2存储布局的示例元数据布局;

图4图示了符合本公开一个实施例的具有分配的索引节点、数据区间(data extent)和
自由空间的示例数据部分;

图5是根据本公开各种实施例的存储器存取操作的流程图;

图6是根据本公开各种实施例的写和丢弃操作的流程图;

图7是根据本公开各种实施例的分配操作的流程图;

图8是根据本公开各种实施例的使自由操作的流程图;

图9是根据本公开各种实施例使用SIMD(单指令多数据)的查?#20063;?#20316;的流程图;以及

图10是根据本公开一个实施例的多个自由列表的操作的流程图。

尽管如下具体实施方式将继续参考说明性实施例,但它们的许多替换、修改和变
形对本领域技术人员将是显而易见的。

具体实施方式

为了补偿基于块(例如NAND型)的固态驱动器(SSD)的特性,写操作可由主机计算
装置和/或SSD控制器管理,以最大化对于每个写操作的存储所写的数据量。例如,要写的数
据可被缓冲,直到累积了最小数据量(例如页)为止,然后,数据页可被写到连续存储器位
置。在另一示例中,响应于包含用于仅一部分页的存储器地址的读请求,数据的整页例如可
被读到SSD中的高速缓冲存储器中。写操作也可配置成促进擦除操作,即,最大化连续页的
数量,因为擦除操作是基于块的。

向具有块可存取的非易失性存储器的SSD的写操作通常利用日志构造的存储技
术。本文所使用的“块可存取”指的是具有用于存储器存取的最小大小(例如一页)的非易失
性存储器。本文所使用的“?#32440;?#21487;存取”指的是可由字和/或?#32440;?#23384;取的非易失性存储器。
“?#32440;?#21487;存取”和“块可存取”指的是对物理存储器地址的存取。换言之,对应用显然的是,已
经请求了如何存取物理存储器的读或写操作。日志构造的存储装置配置成将多个单独的随
机写操作组合成单个顺序写,由此至少提供要写的最小数据量。要写的数据可在主机中的
易失性存储器中缓冲,直到至少已经累积了最小量的数据为止。“段”可包含至少一个数据
页,即,可被写到SSD的最小量的数据。数据段然后可被写到之前擦除的SSD中的存储器位置
的连续块。

写操作进一步配置为写时拷贝。在写时拷贝中,“老”数据不被改写,而是,更新的
(“新?#20445;?#25968;据被写到不同擦除的存储器位置,并且老数据可随后擦除。写时拷贝可导?#28388;?#29255;
化存储,因为每次?#35789;?#21040;不同的存储块,并且每次写可包含仅对应于“老?#20445;?#21363;之前存储的)
数据子集的新数据。

从而,日志构造的存储装置?#19978;?#32791;存储等待要被写的数据并且计算对自由空间碎
片整理的资源的附加主机非易失性存储器容量。对自由空间碎片整理配置?#31245;?#21152;连续页的
数量。日志构造的存储装置可进一步?#26144;?#21521;SSD提交数据,因为准备要写的数据可被?#26144;伲?br />等待附加数据填充页。

一般而言,此公开涉及用于?#32440;?#21487;存取的装置管理的NVM存储装置的主机管理的
NVM(非易失性存储器)方法(和系统)。NVM存储装置例如包含固态驱动器(SSD)。方法和系统
包含主机计算装置中的间接逻辑,其实现NVM基元,同时避免日志构造的存储及其关联的开
销。NVM基元包含但不限于原子多写、原?#26377;礎?#31232;疏编址、丢弃、验证、原子丢弃和原子多丢
弃。

原子操作配置成避免存储器存取操作结果中的不确定性,如果该存储器存取操作
例如由于功率失败而中断的话。换言之,在原?#26377;?#20013;,要被写的所有指定扇区都被写,或者
没有扇区被写。扇区对应于与存储器存取操作关联的若干数据?#32440;凇?#25159;区可包含任何数量
的数据?#32440;凇?#20363;如,扇区可包含512个数据?#32440;凇?#22312;另一示例中,扇区可包含少于512的数据
?#32440;凇?#22312;另一示例中,扇区可包含多于512的数据?#32440;凇?#22914;果写被中断,则之前存储的数据
(“老数据?#20445;?#34987;保持,并且要被存储的数据(“新数据?#20445;?#26410;被写。在原子丢弃中,所有扇区被丢
弃,或者没有扇区被丢弃。写时拷贝促进此类原子性,因为老数据未被立即改写。

间接逻辑配置?#19978;?#24212;于写请求而管理向选择的NVM存储装置写数据扇区,而不等
待附加扇区累积。间接逻辑提供配置成将主机逻辑块地址(LBA)映射到装置LBA的间接层。
逻辑块编址提供物理存储介?#21097;?#21363;物理存储器)与例如操作系统(OS)之间的抽象。例如,由
应用和/或OS使用的主机LBA可被映射到装置LBA,其然后可与存储装置的物理存储器地址
相关。块通常包含多个存储器位置。例如,块可包含扇区,并且LBA然后可对应于一个扇区。
应用可配置成从一系列主机LBA读和/或向一系列主机LBA写。一系列主机LBA可被映射到
(即转换成)对应的一系列装置LBA和/或物理存储器地址。主机地址空间可大于装置地址空
间。之前?#20174;?#23556;的主机LBA?#19978;?#24212;于写请求而动态映射到装置LBA。

装置管理的NVM存储装置例如可在驱动器控制器中包含存储装置上的闪存转换层
(FTL)。FTL配置成将装置LBA映射和/或转换成物理存储器地址。装置控制器然后可执行与
将数据实际存储到NVM存储装置关联的操作。

装置地址空间可包含元数据、事务日志和数据部分。数据部分包含自由空间、自由
列表、例如配置为搜索树的索引节点以及存储的数据。数据被存储在一个或多个数据区间
中。本文所使用的“区间”对应于一个或多个连续的存储单元。例如,存储单元可对应于字
节、扇区(例如512?#32440;冢?#39029;、块?#21462;?#26641;结构可包含B树、B+树和/或它们的一个或多个变量。例
如,B+树包含根节点,可包含一个或多个内部节点和一个或多个叶节点。根节点包含到内部
节点的索引和指针。索引与主机LBA相关。在一些实施例中,一个或多个索引可对应于主机
LBA。内部节点包含到叶节点的索引和指针。每个叶节点包含主机LBA、关联的装置LBA和长
度。在一些实施例中,叶节点可包含多组主机LBA、关联的装置LBA和长度。每个叶节点配置
成将一系列主机LBA映射到对应的一系列装置LBA。长度对应于一系列装置LBA的大小,并且
可对应于开?#21152;?#35013;置LBA的数据区间的大小。大小可以存储单元(例如扇区)为单位。

方法和系统配置成利用相对低等待时间的NVM存储装置(例如SSD)的单扇区原子
写来避免缓冲日志构造的存储装置,而不?#23548;?#24615;能。相对低等待时间的NVM存储装置可以是
?#32440;?#21487;存取的,从而,存取时间可以不包含与日志构造的存储装置关联的等待时间。相对低
等待时间的NVM技术具有相对快的存取时间,例如相对低的随机写或随机读等待时间。例
如,用于写或读扇区的相对低的随机存取等待时间可以在大约10微秒(μs)。在另一示例中,
相对低的存储器存取等待时间可以在大约100μs。写等待时间可根据应用的角度确定。换言
之,等待时间可包含分别开?#21152;?#25552;交对于写的请求并结束于关联的数据被驻留在NVM存储
装置上或者已经被提供给发出请求的应用的时间间隔。例如,此类相对低等待时间的?#32440;?br />可存取的NVM技术可包含但不限于:磁阻存储器(MRAM)、相变存储器(PCM、PRAM)、相变存储
器和开关(PCMS)、阻性存储器、铁电存储器(F-RAM, FeRAM)、自旋转移转矩存储器(STT)、热
辅助的开关存储器(TAS)、千足虫存储器、浮动结栅存储器(FJG RAM)、电池备份RAM?#21462;?#24403;利
用此类?#32440;?#21487;存取的相对低等待时间的NVM技术时,可避免日志构造的存储装置及其关联
的开销。可使用复合本公开的方法和系统与较高等待时间的NVM,但随着等待时间增加,方
法和系统的好处可减少,直到日志构造的存储装置至少一样快。

在一些实施例中,可使用SIMD(单指令多数据)操作,实现查找包含在未分类的B树
叶节点中的地址的方法。例如,在查找地址操作中可利用包含在用于Intel?架构处理器的
SSE4指令集中的PCMPGTQ(对于大于的比较打包数据)SIMD指令,如本文所描述的。换言之,
可实现并行(例如向量)处理,如本文所描述的。

在一些实施例中,可管理共享地址空间内的多个自由列表。共享地址空间内的多
个自由列表中的一个或多个可被指配给相应处理器、核和/或线程。处理器、核和/或线程然
后可配置成从其指配的自由列表中添加和/或移除区间。从而,可避免与自由列表关联的锁
定竞争。

从而,符合本公开的实现可类似于配置成存储单个大稀疏文件的简单文件系统。
分配的空间可包含一个或多个数据区间、提供主机地址空间与装置地址空间之间映射的一
个或多个叶节点以及将索引节点与叶节点相关的树结构。数据区间对应于将主机LBA?#27573;?br />连续映射到装置LBA?#27573;А?#33258;由装置LBA可由堆样式的(heap style)(即,可用的自由存储器
池)自由列表管理。

图1图示了符合本公开几个实施例的计算系统100的系统框图。计算系统100可包
含但不限于:服务器、工作站计算机、台式计算机、膝上型计算机、平板计算机(例如iPad?、
GalaxyTab?等)、超便携式计算机、超移动计算机、上网本计算机和/或亚?#22987;?#26412;计算机;移
动电话,包含但不限于智能电话(例如基于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例如可包:含用户接口装置,包含显
示器、触摸?#26009;?#31034;器、打印机、键区、键盘等;通信逻辑,有线的和/或无线的;其它存储装置,
包含硬盘驱动器、固态驱动器、可移动存储介?#23454;取?#24212;该指出,为了便于图示和描述简化系
统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包含原子多写、原?#26377;礎?#31232;疏编址、丢弃、验证、原子丢弃和原子多丢
弃。原子多写和原?#26377;?#22522;元配置成将一个或多个扇区从主机LBA空间写到装置LBA空间,作
为事务。扇区可以是不连续的。在原?#26377;?#25805;作中,全部所有数据变成被写,或者没有任何数
据变成被写。从而,如果在操作期间中断(例如功率损耗)发生,则现有老数据保持有效。在
整个事务之前或者之后,从一个或多个相同主机LBA其它同时发生的读和/或向其写。在稀
疏编址中,主机LBA空间大于装置LBA空间,并且至少一些主机LBA可保持不映射。当写主机
LBA时,稀疏编址基元配置成将?#20174;?#23556;的主机LBA动态映射到装置LBA。丢弃包含从装置LBA
隐式地不映射主机LBA。验证配置?#31245;?#35768;应用确定是映射还是不映射选择的LBA。原子多丢
弃和原子丢弃基元配置成作为丢弃全部所有数据或者不丢弃任何数据的事务(类似于原子
多写和原?#26377;?#22522;元)执行丢弃。

从而,符合本公开的系统和方法配置成提供间接,将主机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可包含相对低等待时间的?#32440;?#21487;存取非易失性存储器技术,其包含
但不限于:磁阻存储器(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转换成物
理存储器地址,并存储关联的数据。?#19978;?#24212;于存储器存取请求而对于一个或多个数据扇区
执行此类操作,而不等待附加的数据扇区。

图2图示了符合本公开各种实施例的装置LBA空间的示例存储布局200。装置LBA空
间与NVM存储装置104的非易失性物理存储器152相关。换言之,驱动器控制器150可将装置
LBA空间映射到或转换成非易失性物理存储器152 PMA空间,在其中可发生实际存储。装置
LBA空间200包含三个区域:元数据202、事务日志204和数据部分206。元数据202包含与间接
状态相关的固定字段,如本文所描述的。事务日志204配置成包含与分配装置存储器(“分
配?#20445;?#21644;使装置存储器自由(“自由?#20445;?#30456;关的记录。事务日志204配置成存储与暂时配置成支
持原子操作的事务标识符(ID)相关的一个或多个记录。数据部分206可包含与数据区间和
索引节点相关的装置LBA,如本文所描述的。区间是主机LBA?#27573;?#21040;装置LBA?#27573;?#30340;连续映
射。数据区间可由树结构中的主机LBA索引。树结构可包含B树、B+树和/或它们的变量。存储
布局200配置为配置成存储相?#28304;?#30340;稀疏文件的相对简单的文件系统。修改可作为写时拷
贝执行,如本文所描述的。自由装置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?#19978;?#24212;
于分配一个或多个装置LBA的分配和/或使一个或多个装置LBA自由的丢弃而改变。

可利用事务日志204支持当对存储的数据和/或索引节点的改变提交时完成的原
子操作。事务日志204配置成提供最近的事务的检查点。事务日志204配置成包含与事务ID
相关的一个或多个记录。如果存储器存取操作中断,则在存储器存取操作之前,可利用记录
返回到一个状态。间接逻辑140配置成在存储器存取操作期间和/或之后,从事务日志204添
加、更新和/或删除记录。响应于存储器存取请求,间接逻辑140可生成与存储器存取关联的
唯一事务标识符(ID)。事务日志204包含与每个事务ID关联的一个或多个记录。每个记录包
含日志条目类型和一个或多个关联的参数。事务日志204条目类型包含“分配”、“自由意图
(free intent)”、“提交”和“自由”。

分配指示已经从自由列表中移除区间。与分配关联的参数包含开始LBA、分配长
度、新自由列表LBA。开始LBA标识正在分配的区间的开始装置LBA。分配长度对应于分配的
区间中的扇区数。在已经分配了区间之后,新自由列表头LBA对应于新自由列表头装置LBA。
换言之,已经用分配移除现有头。

自由意图指示,区间应该被返回到自由列表。自由意图参数包含自由意图LBA和自
由意图长度。自由意图LBA对应于(即标识)应该被返回到自由列表的区间的装置LBA。自由
意图长度对应于应该使自由的区间中的扇区数。例如,?#19978;?#24212;于丢弃而使区间自由。在另一
示例中,可在写时使区间自由。在此示例中,由于写操作是对应于老数据的写时拷贝装置
LBA,如果可使任何自由的话(如果写成功完成的话)。提交指示事务完成。提交参数包含根
节点LBA。如果根节点已经作为与事务ID关联的存储器存取操作的结果改变,则根节点LBA
配置成提供搜索树的新根的新装置LBA。自由指示,区间应该被返回到自由列表。自由参数
包含自由LBA和自由长度。自由LBA对应于返回到自由列表的区间的装置LBA,并?#26131;?#30001;长度
对应于返回到自由列表的区间的扇区中的长度。

例如,在对装置LBA(或一系列LBA)的写操作期间,一个或多个扇区可被分配用于
存储与写操作关联的数据。唯一事务ID可与写操作关联,并被包含在事务日志204中。事务
日志204中的关联记录然后可包含条目类型分配以及关联的分配参数。在已经分配了与装
置操作关联的区间之后,新自由列表头LBA然后可对应于所得到的装置LBA。分配装置LBA参
数然后可对应于分配的区间的开始装置LBA,并且长度对应于扇区中的区间长度。间接逻辑
140可配置成更新事务日志中的参数。

如果写操作包含之前所写的装置LBA(老数据),则间接逻辑140还可创建和与老数
据关联的装置LBA相关的自由意图记录。如果写操作被中断并且未完成,则间接逻辑140配
置成至少部?#21482;?#20110;事务日志204“滚回”到老数据。如果在完成之后但在自由的区间或节点
已经返回到自由列表之前写操作中断,则间接逻辑140配置成至少部?#21482;?#20110;事务日志204
“前滚?#20445;?#24182;且重新开始将自由的区间和节点返回到自由列表。对应于事务ID的事务204的部
分可在存储器存取操作期间存在,并且可在与事务ID关联的操作已经成功完成之后取消分
配。换言之,事务日志的元素可以是暂时的。

数据部分206包含分配的区间和/或叶节点、索引节点的区域和自由列表。索引节
点包含根节点和内部节点,并且可包含多个叶节点。最初,数据部分206可对应于单个大自
由列表条目。换言之,最初,数据部分206可以不包含索引节点和分配的区间。在操作中,可
分配和/或更?#28388;?#24341;节点,并且可分配一个或多个叶节点和/或数据区间。?#19978;?#24212;于对连续
的一系列“新”主机LBA的写请求而分配叶节点以及关联的数据区间。可用与叶节点的大小
加上数据区间的大小对应的大小,分配自由区间。?#19978;?#24212;于与主机LBA关联的更新请求而更
新叶节点,分配新数据区间,并将老区间标记为“自由意图”。如果存储器存取操作成功完
成,则然后可使老数据区间自由。?#19978;?#24212;于丢弃(即删除)请求而使叶节点和新数据区间自
由。

最初,数据部分206可包含一个自由列表条目。每个自由列表条目包含相应第一扇
区中的长度参数和参数下一装置LBA。长度参数对应于关联的自由列表部分(“项目?#20445;?#20013;的
扇区数。参数下一LBA对应于自由列表中下一项目的装置LBA。从而,初始自由列表条目可包
含邻近(在装置LBA空间中)事务日志204的最后装置LBA的第一装置LBA。

在操作中,当分配叶节点和/或区间时,可至少部?#21482;?#20110;所分配的一系列装置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作为搜索索引来
遍历搜索树。然后可至少部?#21482;?#20110;包含在叶节点中的存储的主机LBA,并且至少部?#21482;?#20110;关
联的长度,选择叶节点。例如,如果查找主机LBA包含在由存储的主机LBA和长度定义的一系
列主机LBA中,则可选择叶节点。然后可标识对应的装置LBA。换言之,叶节点配置成提供从
查找主机LBA到标识的装置LBA的映射。在操作中,可从同一树列表分配索引节点、叶节点和
区间。可从自由列表使叶节点和/或区间自由。

在实施例中,可通过向量处理促进搜索树的遍历。例如,处理器110可配置用于向
量处理,并且间接逻辑140可配置成使用向量处理管理搜索树的遍历。向量处理包含单指令
多数据(SIMD)。换言之,可对多个元素并行执行操作。元素例如可包含在向量中。

搜索树包含B+树,如本文所描述的。搜索树中的索引包含和/或有关主机LBA。查找
操作配置?#25159;?#23450;在叶节点中是否包含查找(即查询)主机LBA。如果查找主机LBA大于或等于
存储的主机LBA并小于存储的主机LBA加上关联的长度,则查找主机LBA被包含在叶节点中。
如果查找主机LBA被包含在叶节点中,则对应装置LBA已经被分配并且未自由。如果查?#20063;?br />作被包含在验证操作中,则验证操作可成功。如果查找主机LBA未包含在叶节点中,则对应
装置LBA未分配和/或已经自由。在此情况下,关联的验证操作可失败,或者?#25159;?#35748;,对应装
置LBA已经自由。

在此实施例中,一个或多个叶节点的内容可配置为用于查?#20063;?#20316;的多个向量。第
一向量可包含多个存储的主机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执行。

这个实施例的操作可开?#21152;?#25509;收存储器存取请求502。例如,可从应用120接收存
储器存取请求。在操作504可接收与数据扇区关联的主机LBA。在操作506可以确定存储器存
取请求是否对应于读、丢弃、验证和/或写请求。如果存储器存取请求对应于读、丢弃和/或
验证请求,则在操作510可使用查询主机LBA作为索引遍历搜索树。在操作512,可以确定是
否存在包含与查询主机LBA对应的存储主机LBA的叶节点。如果此类叶节点不存在,则在操
作514可传递结果。例如,结果可以验证,装置LBA已经被丢弃。在另一示例中,结果可对应于
错误。在操作516,程序流然后可返回。如果此类叶节点确实存在,则操作518可包含利用与
查询主机LBA关联的装置LBA执行存储器存取操作。在操作520,程序流然后可返回。

如果存储器存取操作对应于写请求,则在操作530,主机LBA可被映射?#25509;隢VM物理
存储器地址相关的装置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,可将“自由意图”记录写?#25509;?#20107;务ID关联的事务日志中。例如,更新现有存储的数据
及其关联的丢弃“老”数据的丢弃操作和/或写操作可导致要得到自由的叶节点和/或分配
的数据区间(如果事务成功完成的话)。自由意图条目类型可保持,直到事务完成。操作618
可包含:将“提交”记录写到事务日志。提交日志条目配置成指示写/丢弃事务(操作)成功完
成。

在操作620,可以确定最顶端修改的节点是否是根节点。例如,B+树节点?#19978;?#24212;于
重新平衡通过添加和/或删除叶节点发起的搜索树而修改。如果最顶端修改的节点是跟节
点,则在操作622,元数据根节点可被设置成新根节点。如果最顶端修改的节点不是根节点,
则在操作624,可将改变写到?#38468;?#28857;。换言之,此类节点更新不是写时拷贝操作。在操作626,
可?#22836;?#25152;有节点锁定。在操作628,可使列表自由。自由列表对应于自由区间,并且区间列表
对应于区间标记的自由意图。在事务期间可以锁列表。在操作630,程序流然后可结束。

图7是根据本公开各种实施例的分配操作的流程图700。具体地说,流程图700图示
分配装置存储器中的区间。流程图700是图6的操作608的一个示例。操作例如可由图1的主
机计算装置102执行。流程图700的操作可开?#21152;?#25805;作702,开始分配。在操作704,可使自由
列表锁定。锁定配置成防止其它操作访问并且可能改变自由列表,同时发生流程图700的操
作。

在操作706,可以确定是否存在要分配的任何区间。如果不存在要分配的区间,则
程序流可前进到操作718。如果存在要分配的区间,则在操作708,可以读自由列表中的头自
由区间。在操作710,可以确定头自由区间是否大于需要的。如果?#38750;?#38388;大于需要的,则在操
作712,可以分割区间。例如,自由区间可被分成分配的区间和剩余区间。在714,可以写新头
区间中的剩余区间的下一指针和新大小。操作716包含:将分配记录写到事务日志。程序流
然后可前进到操作706。从而,可重复操作706、708、710、716以及可能的712和714,直到不再
存在区间要分配为止。在操作718,可使自由列表解锁。在操作720,可以返回分配的区间列
表。从而,可从自由列表分配一个或多个区间。区间可包含数据区间和/或节点区间,如本文
所描述的。

图8是根据本公开各种实施例的使自由操作的流程图800。具体地说,流程图800图
示使装置LBA空间中的区间自由。流程图800是响应于图6的操作616而使区间自由的操作的
一个示例。换言之,流程图800配置成使标记为“自由意图”的区间自由。操作例如可由图1的
主机计算装置102执行。在操作802,?#19978;?#24212;于与区间相关的“自由意图”的事务日志条目而
发起流程图800的操作。在操作804,可使自由列表锁定。操作806包含将下一装置LBA和长度
写到自由区间。操作808可包含:将“自由”记录写在事务日志中。在操作810,可使自由列表
解锁。

图9是根据本公开各种实施例使用SIMD(单指令多数据)的查?#20063;?#20316;的流程图900。
具体地说,流程图900图示由配置成执行SIMD指令的处理器(例如向量处理器)执行查?#20063;?br />作。操作例如可由图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的操作可开?#21152;?#24320;头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中图示的更少的或更多的操作。由此,针对一个附图中未明确示出的特征和/或操
作的权利要求被视为在本公开的?#27573;?#21644;内容内。

OS 122可配置成管理系统资源并控制在每个相应装置和/或系统(例如主机计算
装置102和/或NVM存储装置104)上运行的任务。例如,可使用Microsoft Windows、HP-UX、
Linux或UNIX实现OS,尽管可使用其它操作系统。在一些实施例中,OS可由可向在一个或多
个处理单元上运行的各种操作系统(虚拟机)提供底层?#24067;?#30340;抽象层的虚拟机监控器(或监
管程序)替换。

存储器114可包含一个或多个如下类型的存储器:半导体固件存储器、可编程存储
器、非易失性存储器、只读存储器、电可编程存储器、随机存取存储器、闪存、磁盘存储器和/
或光盘存储器。附加地或备选地,系统存储器可包含其它类型和/或以后开发的类型的计算
机可读存储器。

本文描述的操作的实施例可实现在计算机可读存储装置中,其上存储有指令,所
述指令当由一个或多个处理器执行时执行所述方法。处理器例如可包含处理单元和/或可
编程电路。存储装置可包含机器可读存储装置,包含任何类型的有形、非暂时性存储装置,
例如任何类型的盘,包含软盘、光盘、压缩盘只读存储器(CD-ROM)、压缩盘可重写(CD-RW)和
磁光盘、半导体装置,诸如只读存储器(ROM)、随机存取存储器(RAM),诸如动态和静态RAM、
可擦除可编程只读存储器(EPROM)、电可擦除可编程只读存储器(EEPROM)、闪存、磁卡或光
卡、或适合于存储电指令的任何类型存储装置。

如本文任何实施例中所使用的术语“逻辑”可指的是配置成执行上面提到的操作
的软件、固件和/或电路。软件可实施为记录在非暂时性计算机可读存储介质上的软件包、
代码、指令、指令集和/或数据。固件可实施为硬编码在(例如非易失性)存储器装置中的代
码、指令或指令集和/或数据。

如在本文任何实施例中所使用的“电路”例如可包括?#25830;?#32447;电路、可编程电路(诸
如包括一个或多个单独指令处理核心的计算机处理器)、状态机电路和/或存储由可编程电
?#20998;?#34892;的指令的固件(单个或以任何组合)。逻辑可共同或单独实施为形成更大系统(例如
集成电路(IC)、专用集成电路(ASIC)、片上系统(SoC)、台式计算机、膝上型计算机、平板计
算机、服务器、智能电话等)的一部分的电路。

在一些实施例中,?#24067;?#25551;述语言(HDL)可用于规定用于本文描述的各种逻辑和/或
电路的电路和/或逻辑实现。例如,在一个实施例中,?#24067;?#25551;述语言可遵守或兼容超高速集
成电路(VHSIC)?#24067;?#25551;述语言(VHDL),其可实现本文描述的一个或多个电路和/或逻辑的半
导体制造。VHDL可遵守或兼容IEEE标准1076-1987、IEEE标准1076.2、IEEE1076.1、VHDL-
2006的IEEE草稿3.0、VHDL-2008的IEEE草稿4.0和/或IEEE VHDL标准的其它版本和/或其它
?#24067;?#25551;述标准。

从而,与本公开的教导一致,系统和方法包含主机计算装置中的间接逻辑,其实现
NVM基元,同时避免日志构造的存储及其关联的开销。NVM基元包含但不限于原?#26377;礎?#21407;子多
写、原?#26377;礎?#31232;疏编址、丢弃、验证、原子丢弃和原子多丢弃。间接逻辑配置?#19978;?#24212;于写请求
而管理向选择的?#32440;?#21487;存取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中任一示例的元件,其中所述间接逻辑包含与原?#26377;礎?#21407;
子丢弃、原子多写、原子多丢弃、稀疏编址和验证中一个或多个对应的一个或多个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的元件,其中间接逻辑进一步读自由列表中?#38750;?#38388;的长度,如果
?#38750;?#38388;的大小大于分配大小,则将?#38750;?#38388;分成分配的区间和剩余区间,向剩余区间写剩余
区间大小和下一指针,并向与事务ID关联的事务日志写入分配记录。

示例22

这个示例包含示例18的元件,其中间接逻辑进一步至少部?#21482;?#20110;自由意图日志向自由
的区间写下一装置LBA和长度,并向事务日志写入自由记录。

示例23

这个示例包含示例6的元件,其中间接逻辑进一步将存储的主机LBA的向量与包含多个
查找LBA的查找向量相比较,将比较结果存储在第一映射向量中;将存储的主机LBA的向量
和与存储的主机LBA关联的相应长度的向量之和存储在最大LBA向量中;将查找向量与最大
LBA向量的比较结果存储在第二映射向量中;以及至少部?#21482;?#20110;第一映射向量和第二映射
向量确定每个查找主机LBA是否对应于相应存储的主机LBA。

示例24

根据这个示例,提供了一?#22336;?#27861;。该方法包含:由间接逻辑接收与第一数据扇区关联的
主机逻辑块地址(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的元件,其中所述间接逻辑包含与原?#26377;礎?#21407;子丢弃、原子多写、
原子多丢弃、稀疏编址和验证中一个或多个对应的一个或多个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的元件,并且进一步包含:由间接逻辑读自由列表中?#38750;?#38388;的长
度;如果?#38750;?#38388;的大小大于分配大小,则由间接逻辑将?#38750;?#38388;分成分配的区间和剩余区间;
由间接逻辑向剩余区间写剩余区间大小和下一指针;以及由间接逻辑向与事务ID关联的事
务日志写入分配记录。

示例45

这个示例包含示例41的元件,并且进一步包含:由间接逻辑至少部?#21482;?#20110;自由意图日
志向自由的区间写下一装置LBA和长度;以及由间接逻辑向事务日志写入自由记录。

示例46

这个示例包含示例29的元件,并且进一步包含:由间接逻辑将存储的主机LBA的向量与
包含多个查找LBA的查找向量相比较;由间接逻辑将比较结果存储在第一映射向量中;由间
接逻辑将存储的主机LBA的向量和与存储的主机LBA关联的相应长度的向量之和存储在最
大LBA向量中;由间接逻辑将查找向量与最大LBA向量的比较结果存储在第二映射向量中;
以及由间接逻辑至少部?#21482;?#20110;第一映射向量和第二映射向量确定每个查找主机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中任一示例的元件,其中指令包含与原?#26377;礎?#21407;子丢弃、
原子多写、原子多丢弃、稀疏编址和验证中一个或多个对应的一个或多个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的元件,其中所述指令当由一个或多个处理器执行时导致如下附
加操作,包含:读自由列表中?#38750;?#38388;的长度,如果?#38750;?#38388;的大小大于分配大小,则将?#38750;?#38388;
分成分配的区间和剩余区间,向剩余区间写剩余区间大小和下一指针,并向与事务ID关联
的事务日志写入分配记录。

示例68

这个示例包含示例64的元件,其中所述指令当由一个或多个处理器执行时导致如下附
加操作,包含:至少部?#21482;?#20110;自由意图日志向自由的区间写下一装置LBA和长度;以及向事
务日志写入自由记录。

示例69

这个示例包含示例52的元件,其中所述指令当由一个或多个处理器执行时导致如下附
加操作,包含:将存储的主机LBA的向量与包含多个查找LBA的查找向量相比较,将比较结果
存储在第一映射向量中;将存储的主机LBA的向量和与存储的主机LBA关联的相应长度的向
量之和存储在最大LBA向量中;将查找向量与最大LBA向量的比较结果存储在第二映射向量
中;以及至少部?#21482;?#20110;第一映射向量和第二映射向量确定每个查找主机LBA是否对应于相
应存储的主机LBA。

示例70

根据这个示例,存在一种计算机可读存储装置,其上存储了指令,所述指令当由一个或
多个处理器执行时导致如下操作,包含:如示例24至46中任一示例的方法。

示例71

本公开的另一示例是一种系统,包含布置成执行如示例24至46中任一示例的方法的至
少一个装置。

示例72

本公开的另一示例是一种装置,包含执行如示例24至46中任一示例的方法的部件。

本文已经采用的术语和表述被用作描述而非限制的说法,并?#20197;?#20351;用此类术语和
表述时没打算排除所示出和描述的特征的任何等同物(或其部分),并且要认识到,各?#20013;?br />改在权利要求书的?#27573;?#20869;是可能的。因而,权利要求书打算覆盖所有此类等同物。

本文已经描述了各种特点、方面和实施例。特点、方面和实施例易于彼此组合以及
变化和修改,这是本领域技术人员将理解的。本公开因此应该视为包含此类组合、变化和修
改。

关于本文
本文标题:主机管理的非易失性存储器.pdf
链接地址:http://www.pqiex.tw/p-6091824.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 双色球亿元大奖彩票图 开心农场游戏免费下载 内蒙古快三遗漏 幸运快3大小单双技巧 不限ip注册优惠体验金 猛龙传奇网赌 河北快3形态走势图 极速3d计划软件下载 千炮捕鱼达人 篮球吧