CN107797763B - Solid state drive, drive, and method of controlling a solid state drive - Google Patents

Abstract

A solid state drive, a drive and a method of controlling a solid state drive are disclosed. The SSD may include flash memory for storing data and may support multiple device streams in the SSD. The SSD controller may manage reading and writing of data for the flash memory and may store a commit queue and a memory of the block stream mapper. The flash translation layer may include: a receiver for receiving a write command comprising a logical block address, LBA; an LBA mapper to map LBAs to block Identifiers (IDs); stream selection logic to select a stream ID based on the block ID using a block stream mapper; a stream ID adder for adding a stream ID to the write command; a queueing device for placing the block ID in a commit queue; background logic to update the block stream mapper after removing the block ID from the commit queue.

Description

Translated fromChinese

固态驱动器、驱动器和控制固态驱动器的方法Solid state drive, drive, and method of controlling a solid state drive

本申请要求于2016年9月2日提交的第62/383,302号美国临时专利申请、2016年11月4日提交的第15/344,422号美国专利申请、2017年2月13日提交的第62/458,566号美国临时专利申请、2017年3月14日提交的第62/471,350号美国临时专利申请以及2017年4月27日提交的第15/499,877号美国专利申请的权益，所述申请出于所有目的通过引用而包含于此。This application claims US Provisional Patent Application Ser. U.S. Provisional Patent Application No. 458,566, U.S. Provisional Patent Application No. 62/471,350, filed March 14, 2017, and U.S. Patent Application No. 15/499,877, filed April 27, 2017, for the benefit of all The purpose is incorporated herein by reference.

技术领域technical field

本发明构思总体涉及固态驱动器(SSD)，更具体地涉及管理多流SSD(multi-stream SSD)中的流。The inventive concept relates generally to solid state drives (SSDs), and more particularly to managing streams in multi-stream SSDs.

背景技术Background technique

多流固态驱动器(SSD)允许输入数据(incoming data)的智能布置，以最小化内部垃圾回收(GC)的影响并减小写入放大。可通过将单个标签(流ID)添加到从主机发送到SSD的每个写入命令来实现多流。基于该标签，SSD可将数据分组到公同块。Multi-stream solid-state drives (SSDs) allow intelligent placement of incoming data to minimize the impact of internal garbage collection (GC) and reduce write amplification. Multi-streaming can be achieved by adding a single tag (stream ID) to each write command sent from the host to the SSD. Based on this tag, the SSD can group data into common blocks.

但为了利用多流装置，应用必须知道SSD支持多流，使得软件源可将公同流分配给具有相似属性(诸如，数据寿命)的数据。为了进行软件多流认识(multi-stream-aware)需要修改软件。但是，修改任何的软件承载对软件的操作做出意外改变的风险。并且，假定市场上存在大量的不同软件产品，为了支持多流而期望修改少量这些软件产品似乎未必是最好的对策。But in order to take advantage of multi-streaming devices, applications must know that the SSD supports multi-streaming so that software sources can assign common streams to data with similar properties such as data age. Software modification is required for software multi-stream-aware. However, modifying any software carries the risk of making unexpected changes to the operation of the software. Also, given the large number of different software products on the market, expecting to modify a small number of these software products in order to support multiple streams may not seem to be the best response.

仍然存在对在软件不需要修改的情况下支持多流的方法的需求。There remains a need for a method to support multiple streams without requiring software modification.

发明内容SUMMARY OF THE INVENTION

根据本发明构思的一个实施例，提供一种固态驱动器SSD，所述SSD包括：闪存，用于存储数据并支持SSD中的多个装置流；SSD控制器，用于管理响应于多个写入命令而将数据写入到闪存，所述SSD控制器包括用于存储提交队列和区块流映射器的存储器，其中，所述SSD控制器包括闪存转换层，所述闪存转换层包括：接收器，接收包括逻辑块地址LBA的写入命令；LBA映射器，将LBA映射到区块标识符ID；流选择逻辑，使用区块流映射器来基于区块ID选择流ID；流ID添加器，将流ID添加到所述写入命令；排队器，将区块ID置于提交队列中；后台逻辑，从提交队列去除区块ID来更新区块流映射器。According to one embodiment of the present inventive concept, there is provided a solid state drive SSD, the SSD comprising: flash memory for storing data and supporting multiple device streams in the SSD; and an SSD controller for managing responses to multiple writes command to write data to flash memory, the SSD controller includes memory for storing commit queues and block stream mappers, wherein the SSD controller includes a flash translation layer, the flash translation layer includes a receiver , receives a write command including a logical block address LBA; an LBA mapper, which maps the LBA to a block identifier ID; stream selection logic, uses a block stream mapper to select a stream ID based on the block ID; a stream ID adder, Add a stream ID to the write command; a queuer, place the block ID in the commit queue; background logic, remove the block ID from the commit queue to update the block stream mapper.

区块流映射器可包括顺序性、频度、近因SFR表，所述SFR表包括区块ID和针对区块ID的流ID。The block stream mapper may include a sequential, frequent, recency SFR table including block IDs and stream IDs for the block IDs.

后台逻辑可包括：顺序性逻辑，如果LBA与先前写入命令的第二LBA是顺序的则选择先前流。The background logic may include sequential logic to select the previous stream if the LBA is in sequence with the second LBA of the previous write command.

后台逻辑可包括：近因逻辑，用于基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；访问计数调节器，基于近因权重调节区块ID的访问计数以产生调节的访问计数；流ID调节器，基于针对区块ID的调节的访问计数来调节流ID。Background logic may include: recency logic to calculate recency weights based on current access time for block ID, previous access time for block ID and decay period; access count adjuster to adjust blocks based on recency weight The access count of the ID to generate the adjusted access count; the flow ID adjuster, which adjusts the flow ID based on the adjusted access count for the block ID.

区块流映射器可包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。The block flow mapper may include a node entry that includes a block ID and a flow ID for the block ID.

后台逻辑可包括：升级逻辑，基于区块ID确定何时将流ID升级；第二排队器，响应于针对区块ID的流ID而将区块ID置于与多个流ID分别对应的多个队列中的第一队列；降级逻辑，基于区块ID确定何时将流ID降级。The background logic may include: upgrade logic to determine when to upgrade the stream ID based on the block ID; a second queuer to place the block ID in the multiple corresponding to the plurality of stream IDs in response to the stream ID for the block ID. The first of two queues; demotion logic that determines when to demote a flow ID based on the block ID.

降级逻辑可包括比较器和减量器，其中，比较器确定针对区块ID的失效时间是否已经过去，并且如果区块ID的失效时间已经过去，则减量器减少流ID；第二排队器可进行操作来响应于针对区块ID的减少的流ID而将区块ID置于与所述多个流ID分别对应的所述多个队列中的第二队列。The demotion logic may include a comparator and a decrementer, wherein the comparator determines if the expiration time for the block ID has elapsed, and if the expiration time for the block ID has elapsed, the decrementor decrements the flow ID; the second queuer An operation is operable to place a block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs, respectively, in response to the reduced flow ID for the block ID.

根据本发明构思的另一实施例，提供一种在计算机系统中使用的驱动器，所述驱动器包括：接收器，用于接收针对固态驱动器SSD的写入命令，所述写入命令包括逻辑块地址LBA；LBA映射器，用于将LBA映射到区块标识符ID；流选择逻辑，用于使用存储在主机计算机系统中的存储器中的区块流映射器，来基于区块ID选择流ID；流ID添加器，用于将流ID添加到所述写入命令；排队器，用于将区块ID置于存储在存储器中的提交队列中；后台逻辑，用于从提交队列去除区块ID并更新区块流映射器。According to another embodiment of the inventive concept, there is provided a drive for use in a computer system, the drive comprising: a receiver for receiving a write command for a solid state drive SSD, the write command including a logical block address LBA; LBA mapper for mapping LBA to block identifier ID; stream selection logic for selecting stream ID based on block ID using a block stream mapper stored in memory in the host computer system; a stream ID adder for adding a stream ID to the write command; a queuer for placing the block ID in a commit queue stored in memory; background logic for removing the block ID from the commit queue and update the block stream mapper.

区块流映射器可包括顺序性、频度、近因SFR表，所述SFR表包括区块ID和针对区块ID的流ID。The block stream mapper may include a sequential, frequent, recency SFR table including block IDs and stream IDs for the block IDs.

后台逻辑可包括：顺序性逻辑，如果LBA与先前写入命令的第二LBA是顺序的则选择先前流。The background logic may include sequential logic to select the previous stream if the LBA is in sequence with the second LBA of the previous write command.

后台逻辑可包括：近因逻辑，基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；访问计数调节器，基于近因权重调节针对区块ID的访问计数以产生调节的访问计数；流ID调节器，基于针对区块ID的调节的访问计数来调节流ID。The background logic may include: recency logic to calculate recency weights based on the current access time for the block ID, previous access time for the block ID and the decay period; an access count adjuster to adjust the recency weight for the block ID based on the recency weight to generate an adjusted access count; a flow ID adjuster, which adjusts the flow ID based on the adjusted access count for the block ID.

区块流映射器可包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。The block flow mapper may include a node entry that includes a block ID and a flow ID for the block ID.

后台逻辑可包括：升级逻辑，基于区块ID确定何时将流ID升级；第二排队器，响应于针对区块ID的流ID而将区块ID置于与多个流ID分别对应的多个队列中的第一队列；降级逻辑，基于区块ID确定何时将流ID降级。The background logic may include: upgrade logic to determine when to upgrade the stream ID based on the block ID; a second queuer to place the block ID in the multiple corresponding to the plurality of stream IDs in response to the stream ID for the block ID. The first of two queues; demotion logic that determines when to demote a flow ID based on the block ID.

降级逻辑可包括比较器和减量器，其中，比较器用于确定区块ID的失效时间是否已经过去，如果区块ID的失效时间已经过去，则减量器用于减少流ID；第二排队器可进行操作来响应于区块ID的减少的流ID而将区块ID置于与所述多个流ID分别对应的所述多个队列中的第二队列。The demotion logic may include a comparator and a decrementer, wherein the comparator is used to determine whether the expiration time of the block ID has passed, and the decrementer is used to reduce the flow ID if the expiration time of the block ID has passed; the second queuer An operation is operable to place a block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs, respectively, in response to the reduced flow ID of the block ID.

根据本发明构思的另一实施例，提供一种控制固态驱动器SSD的方法，所述方法包括：从软件源接收写入命令；确定所述写入命令中的逻辑块地址LBA；识别针对包括所述LBA的固态驱动器SSD上的区块的区块标识符ID；访问与区块ID关联的流ID；将流ID分配给写入命令；在SSD上使用分配的流ID处理写入命令；执行与区块ID关联的流ID的后台更新。According to another embodiment of the inventive concept, there is provided a method of controlling a solid state drive SSD, the method comprising: receiving a write command from a software source; determining a logical block address LBA in the write command; The block identifier ID of the block on the solid-state drive SSD of the LBA; access the stream ID associated with the block ID; assign the stream ID to the write command; use the assigned stream ID to process the write command on the SSD; execute Background update of the stream ID associated with the block ID.

所述方法还可包括：确定所述LBA与第二写入命令中的第二LBA是否是顺序的；如果所述LBA与第二写入命令中的第二LBA是顺序的，则：确定分配给第二写入命令的第二流ID；将第二流ID分配给所述写入命令。The method may further include: determining whether the LBA and the second LBA in the second write command are sequential; if the LBA and the second LBA in the second write command are sequential, then: determining allocation a second stream ID to the second write command; assigning a second stream ID to the write command.

执行与区块ID关联的流ID的后台更新的步骤可包括：将区块ID添加到提交队列；当区块ID在提交队列的头部时，从提交队列去除区块ID。The step of performing a background update of the stream ID associated with the chunk ID may include adding the chunk ID to the submission queue; and removing the chunk ID from the submission queue when the chunk ID is at the head of the submission queue.

执行与区块ID关联的流ID的后台更新的步骤可包括：增加针对区块ID的访问计数；响应于针对区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重；响应于近因权重而更新针对区块ID的访问计数；响应于更新的访问计数而确定针对区块ID的流ID。The step of performing a background update of the stream ID associated with the block ID may include: incrementing an access count for the block ID; calculating a recency weight for the block ID in response to the current access time and previous access time for the block ID ; update the access count for the block ID in response to the recency weight; determine the stream ID for the block ID in response to the updated access count.

执行与区块ID关联的流ID的后台更新的步骤可包括：将区块ID置于与流ID对应的队列中，其中，所述与流ID对应的队列是多个队列中的一个；当区块ID到达队列的头部时，确定是否将区块ID降级。The step of performing the background update of the flow ID associated with the block ID may include placing the block ID in a queue corresponding to the flow ID, wherein the queue corresponding to the flow ID is one of a plurality of queues; when When the block ID reaches the head of the queue, determine whether to demote the block ID.

执行与区块ID关联的流ID的后台更新的步骤还包括响应于访问计数和装置寿命而确定针对区块ID的失效时间；当区块ID到达队列的头部时确定是否将区块ID降级的步骤包括：如果区块ID的失效时间已经过去，则：从与流ID对应的队列去除区块ID；减少流ID；将区块ID置于与减少的流ID对应的第二队列中。The step of performing a background update of the stream ID associated with the block ID also includes determining an expiration time for the block ID in response to the access count and device age; determining whether to downgrade the block ID when the block ID reaches the head of the queue The steps include: if the expiration time of the block ID has elapsed, then: removing the block ID from the queue corresponding to the flow ID; reducing the flow ID; placing the block ID in the second queue corresponding to the reduced flow ID.

附图说明Description of drawings

图1示出根据本发明构思的一个实施例的具有固态驱动器(SSD)的机器。FIG. 1 illustrates a machine with a solid state drive (SSD) according to one embodiment of the inventive concept.

图2示出图1的机器的附加细节。FIG. 2 shows additional details of the machine of FIG. 1 .

图3示出图1的SSD的细节。FIG. 3 shows details of the SSD of FIG. 1 .

图4示出图3的闪存转换层的细节。FIG. 4 shows details of the flash translation layer of FIG. 3 .

图5示出被映射到区块标识符(ID)然后映射到图1的SSD所使用的流ID的各种命令的逻辑块地址(LBA)。FIG. 5 shows logical block addresses (LBAs) for various commands that are mapped to block identifiers (IDs) and then to stream IDs used by the SSD of FIG. 1 .

图6示出被修改为包括图5的流ID并被传输到图1的SSD的图5的各种命令。FIG. 6 shows the various commands of FIG. 5 modified to include the stream ID of FIG. 5 and transmitted to the SSD of FIG. 1 .

图7示出将图5的LBA映射到图5的区块ID的算术逻辑单元(ALU)。FIG. 7 shows an arithmetic logic unit (ALU) that maps the LBA of FIG. 5 to the block ID of FIG. 5 .

图8示出根据本发明构思的第一实施例的可用于将区块ID映射到流ID的顺序性、频度和近因(Sequential,Frequency,Recency；SFR)表。8 illustrates a Sequential, Frequency, Recency (SFR) table that may be used to map block IDs to stream IDs according to a first embodiment of the inventive concept.

图9示出根据本发明构思的第一实施例的图3的闪存转换层和图4的后台逻辑的附加细节。9 illustrates additional details of the flash translation layer of FIG. 3 and the background logic of FIG. 4 in accordance with a first embodiment of the inventive concept.

图10示出图9的顺序性逻辑的细节。FIG. 10 shows details of the sequential logic of FIG. 9 .

图11示出使用图9的近因逻辑计算近因权重。FIG. 11 shows the calculation of recency weights using the recency logic of FIG. 9 .

图12示出在图9的访问计数调节器中使用图11的近因权重来调节访问计数。FIG. 12 illustrates the use of the recency weights of FIG. 11 to adjust the access count in the access count adjuster of FIG. 9 .

图13示出使用图9的流ID调节器从图12的调节的访问计数计算流ID。FIG. 13 illustrates the use of the flow ID conditioner of FIG. 9 to calculate the flow ID from the adjusted access count of FIG. 12 .

图14示出根据本发明构思的第二实施例的可用于将区块ID映射到流ID的节点。FIG. 14 illustrates nodes that may be used to map block IDs to stream IDs according to a second embodiment of the inventive concept.

图15示出根据本发明构思的第二实施例的图4的后台逻辑的细节。FIG. 15 illustrates details of the background logic of FIG. 4 according to a second embodiment of the inventive concept.

图16示出图15的队列中的区块ID的升级和降级。FIG. 16 shows promotion and demotion of block IDs in the queue of FIG. 15 .

图17示出图15的升级逻辑的细节。FIG. 17 shows details of the upgrade logic of FIG. 15 .

图18示出根据本发明构思的第二实施例的从调节的访问计数计算流ID。FIG. 18 illustrates calculation of a flow ID from an adjusted access count according to a second embodiment of the inventive concept.

图19示出图17的区块失效逻辑(chunk expiration logic)的细节。FIG. 19 shows details of the chunk expiration logic of FIG. 17 .

图20示出图15的降级逻辑的细节。FIG. 20 shows details of the degradation logic of FIG. 15 .

图21A-图21B示出根据本发明构思的一个实施例的用于确定用于图5的写入命令的流ID的示例过程的流程图。21A-21B illustrate a flowchart of an example process for determining a stream ID for the write command of FIG. 5, according to one embodiment of the inventive concept.

图22示出根据本发明构思的一个实施例的图4的LBA映射器将图5的LBA映射到图5的区块ID的示例过程的流程图。FIG. 22 illustrates a flowchart of an example process for the LBA mapper of FIG. 4 to map the LBA of FIG. 5 to the block ID of FIG. 5 according to one embodiment of the inventive concept.

图23A-图23B示出根据本发明构思的第一实施例的用于使用顺序性逻辑更新用于区块的流ID的示例过程的流程图。23A-23B illustrate a flowchart of an example process for updating a stream ID for a tile using sequential logic according to a first embodiment of the inventive concept.

图24示出根据本发明构思的第一实施例的用于执行图8的SFR表的后台更新的示例过程的流程图。FIG. 24 illustrates a flowchart of an example process for performing background update of the SFR table of FIG. 8 according to the first embodiment of the inventive concept.

图25A-图25C示出根据本发明构思的第二实施例的图14的节点的后台更新的示例过程的流程图。25A-25C illustrate a flowchart of an example process for background update of the node of FIG. 14 according to a second embodiment of the inventive concept.

具体实施方式Detailed ways

现在将对本发明构思的实施例做出详细参照，其中，在附图中示出本发明构思的实施例的示例。在下面的具体实施方式中，大量的具体细节被阐述，以确保对本发明构思的全面理解。然而，应当理解，本领域普通技术人员可在没有这些具体细节的情况下实践本发明构思。在其他实例中，公知的方法、过程、主机、电路和网络没有被详细描述，从而不会不必要地模糊实施例的方面。Reference will now be made in detail to the embodiments of the inventive concept, examples of which are illustrated in the accompanying drawings. In the following detailed description, numerous specific details are set forth to ensure a thorough understanding of the inventive concept. It should be understood, however, that one of ordinary skill in the art may practice the inventive concept without these specific details. In other instances, well-known methods, procedures, hosts, circuits, and networks have not been described in detail so as not to unnecessarily obscure aspects of the embodiments.

将理解，尽管在这里可使用术语第一、第二等描述各种元件，但是这些元件不应该由这些术语限制。这些术语仅用于将一个元件与另一个元件进行区分。例如，在不脱离本发明构思的范围的情况下，第一模块可被称为第二模块，类似地，第二模块可被称为第一模块。It will be understood that, although the terms first, second, etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first module could be termed a second module, and, similarly, a second module could be termed a first module, without departing from the scope of the present inventive concepts.

本发明构思的描述中使用的术语在这里仅是用于描述特定的实施例的目的，而不意图限制本发明构思。除非上下文明确地另有指示，否则如本发明构思的描述和权利要求书所使用的单数形式也意图包括复数形式。还将理解，如这里所使用的术语“和/或”表示并包含一个或多个相关所列项的任意和全部可能的组合。还将理解，当在本说明书中使用术语“包括”和/或“包含”时，表明存在叙述的特征、整体、步骤、操作、元件和/或组件，但不排除存在或添加一个或多个其他特征、整体、步骤、操作、元件、组件和/或它们的组。附图的组件和特征不一定是按比例绘制的。The terms used in the description of the inventive concept are used herein for the purpose of describing particular embodiments only and are not intended to limit the inventive concept. As used in the description and claims of the inventive concept, the singular also is intended to include the plural unless the context clearly dictates otherwise. It will also be understood that the term "and/or" as used herein means and includes any and all possible combinations of one or more of the associated listed items. It will also be understood that when the terms "comprising" and/or "comprising" are used in this specification, it indicates the presence of recited features, integers, steps, operations, elements and/or components, but does not preclude the presence or addition of one or more Other features, integers, steps, operations, elements, components and/or groups thereof. The components and features of the drawings are not necessarily drawn to scale.

提出了一种用于不依赖应用层而执行自动流检测和分配的设备和方法。流分配可基于运行时工作量检测(runtime workload detection)，并可不依赖应用。流分配可被应用到可使用多流的固态驱动器(SSD)。An apparatus and method are presented for performing automatic flow detection and allocation independent of the application layer. Stream allocation can be based on runtime workload detection and can be application independent. Stream distribution can be applied to solid state drives (SSDs) that can use multiple streams.

流分配协议的实现具有一些优点。第一，应用不必被丝毫修改。但是分配应用自己的流优先级的应用可作为因素而计入该方法。例如，流分配协议可彻底推迟应用分配的流优先级。或者，流分配协议可使用任何期望的权重值，来执行组合应用分配的流优先级和计算的流分配的加权和。The implementation of the stream distribution protocol has some advantages. First, the application does not have to be modified in the slightest. But applications that assign their own flow priorities can be factored into this approach. For example, a stream allocation protocol can completely defer application-assigned stream priorities. Alternatively, the flow assignment protocol may use any desired weighting value to perform a weighted sum combining application assigned flow priority and computed flow assignment.

第二，另外使用可使用多流的装置的任何应用能利用自动流检测和分配。第三，应用不需要从硬件知道流相关信息。第四，流分配协议可单独管理每个可使用多流的SSD，使应用能够使用多个SSD，甚至混合使用可使用多流的SSD和不可使用多流的SSD。第五，假如写入命令的起始地址(或者，如果流分配协议被实现在文件系统层中，则文件偏移)可被确定，则流分配可在系统的任何期望的层(诸如，在文件系统中、在块层中，在装置驱动器中，在SSD内(例如，在闪存转换层内)等)被执行。Second, any application that otherwise uses a device that can use multiple streams can take advantage of automatic stream detection and assignment. Third, the application does not need to know stream-related information from the hardware. Fourth, the stream allocation protocol can manage each multi-stream-capable SSD individually, enabling applications to use multiple SSDs, or even mix multi-stream-capable SSDs and non-multi-stream-capable SSDs. Fifth, if the start address of the write command (or, if the stream allocation protocol is implemented in the file system layer, the file offset) can be determined, the stream allocation can be made at any desired layer of the system (such as at In the file system, in the block layer, in the device driver, in the SSD (eg, in the flash translation layer), etc.) are executed.

SSD的整个地址空间可被划分成若干固定大小的区块。这些区块大小可以是任何期望的大小：例如，512位区段的倍数。请求的起始逻辑块地址(LBA)可通过将LBA除以每区块的区段数量或更一般地将LBA除以区块大小，而被转换为区块标识符(ID)。The entire address space of an SSD can be divided into several fixed-size blocks. These block sizes can be any desired size: for example, multiples of 512-bit extents. The requested starting logical block address (LBA) can be converted to a block identifier (ID) by dividing the LBA by the number of extents per block or more generally by dividing the LBA by the block size.

在本发明构思的第一实施例中，顺序性、频度和近因(SFR)方法可用于确定流分配：In a first embodiment of the inventive concept, a sequentiality, frequency, and recency (SFR) method may be used to determine flow allocation:

●顺序性：如果新请求的起始LBA与先前请求的结束LBA邻近(即，写入命令包含顺序写入)，第二写入命令可被分配与较早的写入命令一样的流ID。这个方法假设：如果一组顺序的请求在短时间段内被发出，则他们具有相似的寿命。由于写入命令可由不同的源(应用，文件系统、虚拟机等)发出，并可被混合，所以从SSD的视角看，写入命令可不遵循严格的有序模式。为说明这种可能性，顺序性可以与窗口(其大小可变)内的先前命令的数量有关地被确定。例如，大小为4的窗口可检查输入请求是否与先前四个请求中的任何一个是顺序的。• Sequentiality: If the starting LBA of the new request is adjacent to the ending LBA of the previous request (ie, the write command contains a sequential write), the second write command may be assigned the same stream ID as the earlier write command. This method assumes that if a set of sequential requests are issued within a short period of time, they have similar lifetimes. Since write commands can be issued by different sources (applications, filesystems, virtual machines, etc.) and can be mixed, from an SSD perspective, write commands may not follow a strictly ordered pattern. To account for this possibility, the ordering can be determined in relation to the number of previous commands within a window (which can be of variable size). For example, a window of size 4 can check whether the incoming request is in sequence with any of the previous four requests.

●频度：频度表示起始LBA已被访问的次数。频度可被测量为访问计数。每当区块被访问(写)时，该区块的访问计数增加1。较高访问计数指示该区块的较短寿命。频度因此反映数据区块的温度。● Frequency: The frequency indicates the number of times the starting LBA has been accessed. Frequency can be measured as a visit count. Whenever a block is accessed (written), the block's access count is incremented by 1. A higher access count indicates a shorter lifespan for the block. The frequency thus reflects the temperature of the data block.

●近因：近因指示区块的时间局部性。例如，一个区块可在特定时间段内被更频繁地访问，并累积高访问计数，而在之后不活跃。在这种情形下，不期望将区块长时间保持在热流中。只有当区块在最近的时间段内被频繁访问时，才认为区块是热的。在本发明构思的一个实施例中，可针对全部的区块预定义衰减期。如果区块在最后的N个衰减期内没有被访问，则访问计数将被除以2^N。- Recency: Recency indicates the temporal locality of the block. For example, a block may be accessed more frequently for a certain period of time and accumulate a high access count, and then be inactive. In this situation, it is not desirable to keep the block in the heat flow for a long time. A block is considered hot only if it has been frequently accessed in the recent time period. In one embodiment of the inventive concept, the decay period may be predefined for all blocks. If the block has not been accessed in the last N decay periods, the access count will be divided by 2^N .

针对区块的流ID可通过频度和近因二者(如果可用，还有顺序性)被确定。如果区块被频繁地访问，则频度可将区块升级为较热的流；而如果区块在最后的衰减期期间不活跃，则近因可将该区块降级为较冷的流。在本发明构思的一个实施例中，对数尺度可用于将访问计数转换为流ID，这可反映装置流的数量远小于用于访问计数的值的事实。因此，例如：Stream IDs for blocks can be determined by both frequency and recency (and sequentiality if available). Frequency can promote a block to a hotter stream if it is accessed frequently, while recency can demote a block to a cooler stream if it was inactive during the last decay period. In one embodiment of the inventive concept, a logarithmic scale may be used to convert access counts to flow IDs, which may reflect the fact that the number of device flows is much smaller than the value used for access counts. So for example:

近因权重＝2^{((当前时间–最后访问时间)/衰减期)}recency weight = 2^{((current time – last access time)/decay period)}

流ID＝log(访问计数/近因权重)flow ID=log(access count/recency weight)

针对区块的流ID的更新可作为后台任务而运行，最小化对输入/输出(I/O)性能的影响。Updates of stream IDs for chunks can run as a background task with minimal impact on input/output (I/O) performance.

在本发明构思的第二实施例中，可使用多队列方法。针对每个装置流，队列可被定义：由于存在多个装置流，所以将存在多个队列。多队列算法可被划分成两个不同的功能模块。一个模块负责将每个区块从较低队列升级到较高队列；另一个模区块处理将少活跃或不活跃的区块从较高队列降级到较低队列。区块的访问计数越高，区块就被认为越热，因此，该区块被置于较高队列中。升级和降级二者可作为后台任务而运行，最小化对I/O性能的影响。In the second embodiment of the inventive concept, a multi-queue method may be used. For each device flow, a queue can be defined: since there are multiple device flows, there will be multiple queues. The multi-queue algorithm can be divided into two different functional modules. One module is responsible for promoting each block from a lower queue to a higher queue; another module handles the demotion of less active or inactive blocks from a higher queue to a lower queue. The higher the access count of a block, the hotter the block is considered to be, and therefore, the block is placed in the higher queue. Both upgrades and downgrades can be run as background tasks with minimal impact on I/O performance.

当区块第一次被访问时，它被分配到流0(最低流)并被置于相应的队列中。否则，区块从当前队列被去除，它的访问计数被更新，并且区块被置于(可能地)新队列中。任何方法可被用于基于访问计数确定合适的队列：例如，访问计数的对数可被计算为新的流ID(它识别相应的队列)。升级模块还可(基于访问计数)进行检查来查看区块是否是当前最热的区块。如果是，则装置寿命可基于这个区块的访问之间的间隔而被设置。最终，升级逻辑可基于装置寿命和区块的最后访问时间，来确定区块的失效时间。When a block is accessed for the first time, it is assigned to stream 0 (the lowest stream) and placed in the corresponding queue. Otherwise, the block is removed from the current queue, its access count is updated, and the block is placed in a (possibly) new queue. Any method can be used to determine the appropriate queue based on the access count: for example, the log of the access count can be calculated as the new flow ID (which identifies the corresponding queue). The upgrade module can also check (based on the access count) to see if the block is currently the hottest block. If so, the device lifetime can be set based on the interval between accesses of this block. Ultimately, the upgrade logic can determine the expiration time of the block based on the device age and the last access time of the block.

为使区块降级，降级模块在区块到达他们的队列的头部时检查区块。如果那个区块还没有度过他的失效时间，则该区块可被单独留下。否则，区块可从它的当前队列被去除，被分配新的失效时间，并被降低到较低队列(即，被分配较低流ID)。To demote blocks, demote modules check for blocks when they reach the head of their queue. If that block has not passed its expiration time, the block can be left alone. Otherwise, the block may be removed from its current queue, assigned a new expiration time, and lowered to a lower queue (ie, assigned a lower flow ID).

此外，如果正在被降级的区块是最热的区块，则该区块在一段时间(由失效时间确定)内还没有被访问。因此，该区块不再是热的，来自那个队列的另一区块可被选择为最热的区块(具有装置寿命的合适分支)。这个新选择的最热的区块可以是那个队列中的下一区块，或者它可以是进入那个队列的最后区块。Also, if the block being demoted is the hottest block, that block has not been accessed for a period of time (determined by the expiration time). Therefore, the block is no longer hot and another block from that queue can be selected as the hottest block (appropriate branch with device age). This newly selected hottest block can be the next block in that queue, or it can be the last block to enter that queue.

图1示出根据本发明构思的一个实施例的具有固态驱动器(SSD)的机器。在图1中，示出了机器105。机器105可以是任何期望的机器(包括但不限于台式计算机或膝上型计算机、服务器(独立服务器或机架服务器))或者可从本发明构思的实施例受益的任何其他装置。机器105还可包括专用便携式计算装置、平板计算机、智能电话和其他计算装置。机器105可运行任何期望的应用：数据库应用是好的示例，但本发明构思的实施例可扩展到任何期望的应用。FIG. 1 illustrates a machine with a solid state drive (SSD) according to one embodiment of the inventive concept. In Figure 1, amachine 105 is shown.Machine 105 may be any desired machine (including, but not limited to, desktop or laptop computers, servers (standalone or rack servers)), or any other device that may benefit from embodiments of the inventive concepts.Machine 105 may also include dedicated portable computing devices, tablet computers, smartphones, and other computing devices. Themachine 105 may run any desired application: a database application is a good example, but embodiments of the present inventive concept may be extended to any desired application.

不管机器105的具体形式，它可包括处理器110、存储器115和固态驱动器(SSD)120。处理器110可以是各种处理器：例如，英特尔Xeon、Celeron、Itanium或Atom处理器、AMDOpteron处理器以及ARM处理器等。虽然图1示出单个处理器，但是机器105可包括任何数量的处理器。存储器115可以是任何种类的存储器，诸如，闪存、静态随机存取存储器(SRAM)、持久随机存取存储器、铁电随机存储器(FRAM)或非易失性随机存取存储器(NVRAM)(诸如，磁阻随机存取存储器(MRAM)等，但一般是DRAM。存器115还可以是不同存储器类型的任何期望的组合。存储器115可由也是机器105的部分的存储器控制器125控制。Regardless of the specific form ofmachine 105 , it may includeprocessor 110 ,memory 115 and solid state drive (SSD) 120 . Theprocessor 110 may be a variety of processors: for example, Intel Xeon, Celeron, Itanium or Atom processors, AMD Opteron processors, ARM processors, and the like. Although FIG. 1 shows a single processor,machine 105 may include any number of processors. Thememory 115 may be any kind of memory, such as flash memory, static random access memory (SRAM), persistent random access memory, ferroelectric random access memory (FRAM), or non-volatile random access memory (NVRAM) (such as, Magnetoresistive random access memory (MRAM), etc., but typically DRAM.Memory 115 may also be any desired combination of different memory types.Memory 115 may be controlled bymemory controller 125, which is also part ofmachine 105.

SSD 120可以是任何种类的SSD，并甚至可被扩展为包括(即使当没有使用闪存时)执行垃圾回收的其他类型的存储器。SSD 120可由可在存储器115内的装置驱动器130控制。SSD 120 can be any kind of SSD, and can even be extended to include other types of memory that perform garbage collection even when flash memory is not used.SSD 120 may be controlled bydevice driver 130 , which may be withinmemory 115 .

图2示出图1的机器105的附加细节。参照图2，典型地，机器105包括一个或多个处理器110，其中，处理器110可包括存储器控制器125和时钟205，其可被用于协调机器105的组件的操作。处理器110还可连接到存储器115，其中，作为示例，存储器115可包括随机存取存储器(RAM)、只读存储器(ROM)或其他状态保持介质。处理器110还可连接到SSD 120以及网络连接器210，其中，网络连接器210可以是例如以太网连接器或无线连接器。处理器110还可连接到总线215，其中，总线215可附接其他组件中的用户接口220以及可使用输入/输出引擎225管理的输入/输出接口端口。FIG. 2 shows additional details of themachine 105 of FIG. 1 . Referring to FIG. 2 , themachine 105 typically includes one ormore processors 110 , where theprocessors 110 may include amemory controller 125 and aclock 205 that may be used to coordinate the operation of the components of themachine 105 . Theprocessor 110 may also be connected to amemory 115, which may include, by way of example, random access memory (RAM), read only memory (ROM), or other state-keeping medium. Theprocessor 110 may also be connected to theSSD 120 and to anetwork connector 210, which may be, for example, an Ethernet connector or a wireless connector. Theprocessor 110 may also be connected to abus 215 , which may attachuser interfaces 220 in other components and input/output interface ports that may be managed using an input/output engine 225 .

图3示出图1的SSD 120的细节。在图3中，SSD 120可包括主机接口逻辑305、SSD控制器310和各种闪存芯片315-1至315-8，其中，闪存芯片315-1至闪存芯片315-8可被组织到各种通道320-1至通道320-4中。主机接口逻辑305可管理图1的SSD 120与机器105之间的通信。SSD控制器310可管理对闪存芯片315-1至闪存芯片315-8的读取操作和写入操作以及垃圾回收操作。SSD控制器310可包括用于执行这些管理中的一些的闪存转换层325。在本发明构思的具有负责将写入命令分配给流的SSD 120的实施例中，SSD控制器310可包括用于支持流分配的存储器330。存储器330可包括提交队列335和区块流映射器340。提交队列335可被用于存储关于受各种写入命令影响的区块的信息。当写入命令被接收时，与这些写入命令关联的区块(或不如说，这些区块的标识符(ID))可被置于提交队列335中。然后，作为后台处理的一部分(以最小化对前台操作的影响)，区块可从提交队列335中去除，针对这些区块的流分配可被更新。区块流映射器340可存储关于什么流当前被分配给各种区块的信息：这个信息可被更新为提交队列335中的区块ID的结果(或者提交队列335中的区块ID的缺少—未正被使用的区块可被分配给较低优先级流作为未使用的结果)。各种闪存芯片315-1至闪存芯片315-8可支持SSD 120中的多个装置流。将在下面参照图5和图7进一步讨论区块的概念。FIG. 3 shows details of theSSD 120 of FIG. 1 . In FIG. 3,SSD 120 may includehost interface logic 305,SSD controller 310, and various flash chips 315-1 through 315-8, wherein flash chips 315-1 through 315-8 may be organized into various channel 320-1 into channel 320-4.Host interface logic 305 may manage communications betweenSSD 120 andmachine 105 of FIG. 1 . TheSSD controller 310 may manage read and write operations and garbage collection operations to the flash memory chips 315-1 to 315-8.SSD controller 310 may include aflash translation layer 325 for performing some of these managements. In embodiments of the present inventiveconcept having SSD 120 responsible for distributing write commands to streams,SSD controller 310 may includememory 330 for supporting stream distribution.Memory 330 may include commitqueue 335 andblock stream mapper 340 . The commitqueue 335 may be used to store information about blocks affected by various write commands. When write commands are received, the blocks (or rather, identifiers (IDs) of these blocks) associated with these write commands may be placed in the commitqueue 335 . Then, as part of background processing (to minimize the impact on foreground operations), chunks may be removed from thesubmission queue 335, and the flow assignments for these chunks may be updated. Theblock stream mapper 340 may store information about what streams are currently assigned to various blocks: this information may be updated as a result of the block ID in the commit queue 335 (or the lack of a block ID in the commit queue 335 - Blocks that are not being used can be allocated to lower priority streams as a result of being unused). Various flash chips 315 - 1 through 315 - 8 may support multiple device streams inSSD 120 . The concept of blocks will be discussed further below with reference to FIGS. 5 and 7 .

虽然图3将SSD 120示出为包括被组织到四个通道320-1至通道320-4中的八个闪存芯片315-1至闪存芯片315-8，但是本发明构思的实施例可支持被组织到任何数量的通道中的任何数量的闪存芯片。Although FIG. 3 showsSSD 120 as including eight flash memory chips 315-1 through 315-8 organized into four channels 320-1 through 320-4, embodiments of the present inventive concept may support Any number of flash chips organized into any number of channels.

图4示出图3的闪存转换层325的细节。在图4中，闪存转换层325被示出为包括接收器405、逻辑块地址(LBA)映射器410、流选择逻辑415、流ID添加器420、发送器425、排队器(queuer)430和后台逻辑435。接收器405可从各种软件源(诸如，操作系统、应用、文件系统、远程机器和其他这样的源)接收写入命令。针对给定的写入命令，LBA映射器410可将在写入命令中使用的LBA映射到图1的SSD 120上的特定区块。然后，流选择逻辑415可选择适于该区块的流。流选择逻辑415可使用图3的区块流映射器340来完成这个流选择，并可包括用于搜索图3的区块流映射器340以找到与选择的区块对应的条目(entry)的逻辑。可选地，流选择逻辑425可使用其他方法：例如，通过从区块的访问计数计算流ID(与下面参照图13描述的内容相似)，或通过以循环(round robin)方法分配流(以在全部的装置流上均匀分布写入命令)。然后，流ID添加器420可使用用于将数据写入到写入命令的逻辑来将选择的流ID添加到写入命令。一旦流ID已经被附加到写入命令，则发送器425就可向图1的SSD 120发送写入命令(具有附加的流ID)以便执行。FIG. 4 shows details of theflash translation layer 325 of FIG. 3 . In FIG. 4,flash translation layer 325 is shown to includereceiver 405, logical block address (LBA)mapper 410,stream selection logic 415,stream ID adder 420,transmitter 425,queuer 430, andBackground logic 435.Receiver 405 may receive write commands from various software sources, such as operating systems, applications, file systems, remote machines, and other such sources. For a given write command,LBA mapper 410 may map the LBA used in the write command to a specific block onSSD 120 of FIG. 1 . Thestream selection logic 415 can then select a stream suitable for the tile. Thestream selection logic 415 may use theblock stream mapper 340 of FIG. 3 to accomplish this stream selection, and may include a method for searching theblock stream mapper 340 of FIG. 3 for the entry corresponding to the selected block. logic. Alternatively, thestream selection logic 425 may use other methods: for example, by calculating the stream ID from the access count of the block (similar to that described below with reference to FIG. 13 ), or by allocating streams in a round robin method (to distribute write commands evenly across all device streams). Thestream ID adder 420 may then add the selected stream ID to the write command using logic for writing data to the write command. Once the stream ID has been appended to the write command, thetransmitter 425 may send the write command (with the stream ID attached) to theSSD 120 of FIG. 1 for execution.

排队器430可拿到针对写入命令的识别的区块ID，并可将那个区块ID添加到图3的提交队列335。排队器430可使用用于将区块ID添加到图3的提交队列335的逻辑。例如，排队器430可包括指向图3的提交队列335的尾部的指针，并可在指向图3的提交队列335的尾部的指针可被更新为指向图3的提交队列335的下一位置之后将区块ID写入到图3的提交队列335的尾部中。最终，区块ID将从图3的提交队列335被解排队，此后，后台逻辑435可对解排队(de-queued)的区块ID进行操作。下面将参照图9和图15进一步描述后台逻辑435。Thequeuer 430 can take the identified block ID for the write command and can add that block ID to the commitqueue 335 of FIG. 3 .Queuer 430 may use logic for adding block IDs tosubmission queue 335 of FIG. 3 . For example, thequeuer 430 may include a pointer to the tail of thesubmission queue 335 of FIG. 3, and may place a pointer to the tail of thesubmission queue 335 of FIG. 3 after the pointer to the tail of thesubmission queue 335 of FIG. The block ID is written to the tail of the commitqueue 335 of FIG. 3 . Eventually, the block IDs will be dequeued from thesubmission queue 335 of FIG. 3, after which thebackground logic 435 may operate on the de-queued block IDs.Background logic 435 will be further described below with reference to FIGS. 9 and 15 .

可以以任何期望的方式实现后台逻辑435。例如，后台逻辑435可每当区块被访问时增加区块的访问计数来尽可能简单操作(这将涉及差不多用于在数据结构存储器的区块ID和流ID中执行查找的逻辑以及用于增加以那种方式定位的流ID)。但这样简单的实现将意味着最终每个区块将使用最高编号的流，而较低编号的流不被使用。更相关的实现可考虑区块是否没有被大量使用，并可降低区块的流优先级以进行匹配。下面参照图8-图13和图14-图20描述本发明构思的以不同方式实现后台逻辑435以获得这个结果的两个实施例。Background logic 435 may be implemented in any desired manner. For example, thebackground logic 435 may increase the access count of the block each time the block is accessed to make the operation as simple as possible (this would involve almost logic for performing a lookup in the block ID and stream ID of the data structure memory and for Increment the stream ID that is positioned that way). But such a simple implementation would mean that eventually each block would use the highest numbered stream, and the lower numbered streams would not be used. A more relevant implementation may consider whether the block is not heavily used, and may lower the block's stream priority to match. Two embodiments of the inventive concept that implement thebackground logic 435 in different ways to achieve this result are described below with reference to FIGS. 8-13 and 14-20.

虽然后台逻辑435被描述为按“后台”(因此得名)运行，但是在后台执行流分配更新便于最小化对于图1的SSD 120的读取和写入的影响。假设流分配能够在不影响图1的SSD120的性能的情况下被更新，则没有让后台逻辑435不能够在“前台”操作的理由。例如，如果图1的SSD 120包括处理器(换言之，图1的SSD 120提供存储器中计算(In-StorageComputing，ISC))，则图1的SSD 120中的这个处理器能够潜在地致力于在不影响图1的SSD120的读取和写入性能的情况下实时更新流分配。在这样的情形下，后台逻辑435能够立即操作来执行流分配更新，而无需将区块ID置于图3的提交队列335中或者等待后台逻辑435可不影响前台操作而操作的时间。Whilebackground logic 435 is described as running "in the background" (hence the name), performing stream allocation updates in the background facilitates minimizing the impact on reads and writes toSSD 120 of FIG. 1 . Assuming that stream assignments can be updated without affecting the performance ofSSD 120 of FIG. 1, there is no reason forbackground logic 435 to not be able to operate "in the foreground". For example, if theSSD 120 of FIG. 1 includes a processor (in other words, theSSD 120 of FIG. 1 provides In-Storage Computing (ISC)), then this processor in theSSD 120 of FIG. 1 can potentially be dedicated to Stream allocations are updated in real time without affecting the read and write performance ofSSD 120 of FIG. 1 . In such a situation, thebackground logic 435 can operate immediately to perform stream allocation updates without placing the block ID in the commitqueue 335 of FIG. 3 or waiting for a time when thebackground logic 435 can operate without affecting foreground operations.

在图4中，闪存转换层325被示出为负责执行流分配和流ID更新。但在本发明构思的其他实施例中，图4中示出的一个或多个组件可以以软件被实现，并可被包括作为例如图1的存储器控制器125、图1的装置驱动器130的部分，或者图4中示出的一个或多个组件可被实现为可拦截写入请求并在发出写入命令之前组合流的库程序(library routine)，或可被实现为图1的SSD 120或机器105内的其他地方内的单独的专用硬件。为了这个讨论的目的，即使伴随图4-图12的描述集中在闪存转换层325内的实现，对由图4的组件执行的流分配的任何描述也意图包括在任何特定位置的实现。In Figure 4, theflash translation layer 325 is shown as responsible for performing stream allocation and stream ID updates. However, in other embodiments of the inventive concept, one or more of the components shown in FIG. 4 may be implemented in software and may be included as part of, for example,memory controller 125 of FIG. 1 ,device driver 130 of FIG. 1 , or one or more of the components shown in FIG. 4 can be implemented as a library routine that can intercept write requests and combine streams before issuing write commands, or can be implemented asSSD 120 of FIG. 1 or Separate dedicated hardware elsewhere within themachine 105 . For the purposes of this discussion, even though the accompanying descriptions of FIGS. 4-12 focus on implementations withinflash translation layer 325, any description of stream allocation performed by the components of FIG. 4 is intended to include implementations at any particular location.

虽然图4将LBA映射器410和流选择逻辑415示出为独立组件，但是这些组件的结构可被逻辑地组合成单个组件。更普遍地，本发明构思的实施例可将图4-图6、图9-图13和图15至图20中示出和描述的任何单独组件组合成统一组件。Although FIG. 4 showsLBA mapper 410 andstream selection logic 415 as separate components, the structures of these components may be logically combined into a single component. More generally, embodiments of the present inventive concepts may combine any of the individual components shown and described in FIGS. 4-6, 9-13, and 15-20 into a unified component.

图5示出被映射到区块标识符(ID)然后映射到图1的SSD所使用的流ID的各种命令的逻辑块地址(LBA)。虽然本发明构思的实施例可支持任何数量的写入命令，但是在图5中，示出了写入命令505-1、505-2和505-3。此外，虽然图5仅示出了写入命令，但是本发明构思的实施例还可同样应用到读取命令。写入命令505-1至写入命令505-3可包括指定写入命令505-1至写入命令505-3的起始LBA的LBA 510-1至LBA 510-3。FIG. 5 shows logical block addresses (LBAs) for various commands that are mapped to block identifiers (IDs) and then to stream IDs used by the SSD of FIG. 1 . Although embodiments of the inventive concept may support any number of write commands, in FIG. 5, write commands 505-1, 505-2, and 505-3 are shown. In addition, although FIG. 5 shows only a write command, embodiments of the inventive concept may also be equally applied to a read command. Write commands 505-1 to 505-3 may include LBAs 510-1 to LBAs 510-3 that specify the starting LBAs of write commands 505-1 to 505-3.

LBA映射器410可访问来自写入命令505-1至505-3的LBA 510-1至LBA 510-3。一旦LBA 510-1至LBA 510-3已经从写入命令505-1至505-3被读取，LBA映射器410就可确定相应的区块ID 515-1至515-3。区块可被认为是SSD 120的逻辑细分(但不需要区块与SSD 120的其他逻辑细分(诸如，块和页)对齐)。可以以任何期望的方式确定区块的数量：例如，通过挑选区块的期望的大小并将SSD 120的大小除以那个区块大小，或者通过选择已经被证明在不需要由图4的后台逻辑435执行的太多处理的情况下提供足够的效用的数量(并将SSD120除以那个数量)。区块未必具有相同的大小，但是统一的大小可简化LBA映射器410的操作。因此，例如，一个区块可包括SSD 120中的128KB数据，而另一区块可包括SSD 120中的512KB数据。由于可使用移位操作执行从LBA确定区块，所以大小为2的幂的区块特别有利，但本发明构思的实施例可支持任何期望大小的区块。LBA mapper 410 may access LBA 510-1 through LBA 510-3 from write commands 505-1 through 505-3. Once LBA 510-1 to LBA 510-3 have been read from write commands 505-1 to 505-3,LBA mapper 410 may determine corresponding block IDs 515-1 to 515-3. Blocks may be considered logical subdivisions of SSD 120 (but blocks are not required to be aligned with other logical subdivisions ofSSD 120, such as blocks and pages). The number of blocks can be determined in any desired way: for example, by picking the desired size of the block and dividing the size ofSSD 120 by that block size, or by selecting a block size that has been shown to be unnecessary by the backend logic of Figure 4. 435 is the amount that provides sufficient utility if too much processing is performed (and divide theSSD 120 by that amount). The blocks do not necessarily have the same size, but a uniform size may simplify the operation of theLBA mapper 410 . Thus, for example, one block may include 128KB of data inSSD 120 , while another block may include 512KB of data inSSD 120 . Since the determination of blocks from the LBA can be performed using shift operations, blocks of sizes that are powers of 2 are particularly advantageous, but embodiments of the inventive concept may support blocks of any desired size.

LBA映射器410可以以任何多种方式确定区块ID 515-1至区块ID 515-3。例如，LBA映射器410可包括用于从LBA 510-1至LBA 510-3数学地计算区块ID 515-1至区块ID 515-3的算术逻辑单元(ALU)520。或者，LBA映射器410可包括地址掩码525，其中，地址掩码525可从LBA 510-1至LBA 510-3遮蔽掉各种位，剩下区块ID 515-1至区块ID 515-3。LBA mapper 410 may determine block ID 515-1 through block ID 515-3 in any number of ways. For example,LBA mapper 410 may include an arithmetic logic unit (ALU) 520 for mathematically calculating block ID 515-1 to block ID 515-3 from LBA 510-1 to LBA 510-3. Alternatively,LBA mapper 410 may includeaddress mask 525, whereinaddress mask 525 may mask out various bits from LBA 510-1 to LBA 510-3, leaving block ID 515-1 to block ID 515- 3.

一旦区块ID 515-1至区块ID 515-3已经被确定，流选择逻辑415就可确定将用于那个块的流。流选择逻辑415可使用区块ID 515-1至515-3来从区块映射器340确定相应的流ID 530-1至530-3。Once block ID 515-1 through block ID 515-3 have been determined,stream selection logic 415 can determine the stream to be used for that block. Thestream selection logic 415 may use the block IDs 515-1 to 515-3 to determine the corresponding stream IDs 530-1 to 530-3 from theblock mapper 340.

图6示出被修改为包括图5的流ID 530-1至530-3并被传输到图1的SSD的图5的命令505-1和505-2。(出于空间原因，图6仅示出了来自图5的三个写入命令和三个关联的数据中的两个写入命令和两个关联的数据。但图6以与图5相同的方式进行了概括)。在图6中，流ID添加器420可将流ID 530-1和530-2写入到写入命令505-1和505-2中。以这种方式，图1的SSD 120可知道在处理写入命令505-1和505-2时使用哪个装置流。发送器325可将修改的写入命令505-1和505-2发送到图1的SSD 120。FIG. 6 shows commands 505-1 and 505-2 of FIG. 5 modified to include stream IDs 530-1 to 530-3 of FIG. 5 and transmitted to the SSD of FIG. 1 . (For space reasons, FIG. 6 shows only two write commands and two associated data of the three write commands and three associated data from FIG. 5. However, FIG. 6 uses the same method is summarized). In FIG. 6, thestream ID adder 420 may write the stream IDs 530-1 and 530-2 into the write commands 505-1 and 505-2. In this way,SSD 120 of Figure 1 can know which device stream to use when processing write commands 505-1 and 505-2.Transmitter 325 may transmit modified write commands 505-1 and 505-2 toSSD 120 of FIG. 1 .

图5至图6中没有示出的是图4的排队器430的操作。一旦图5的区块ID 515-1至515-3已经被确定，图4的排队器430就可使图5的区块ID 515-1至515-3在图3的提交队列335中排队，以供图4的后台逻辑435稍后处理。图4的排队器430可在在图5的区块ID 515-1至515-3已经被确定之后的任何时间对区块ID 515-1至515-3进行排队。例如，图4的排队器430可在在图5的区块ID 515-1至515-3已经被图4的LBA映射器410确定之后、在修改的写入命令505-1至写入命令505-3已经被发送到图1的SSD 120之后或者在他们之间的任何时间，对区块ID 515-1至515-3进行排队。Not shown in FIGS. 5-6 is the operation of thequeuer 430 of FIG. 4 . Once the block IDs 515-1 to 515-3 of FIG. 5 have been determined, thequeuer 430 of FIG. 4 may queue the block IDs 515-1 to 515-3 of FIG. 5 in the commitqueue 335 of FIG. 3, For later processing by thebackground logic 435 of FIG. 4 . Thequeuer 430 of FIG. 4 may queue the block IDs 515-1 to 515-3 of FIG. 5 at any time after the block IDs 515-1 to 515-3 of FIG. 5 have been determined. For example, thequeuer 430 of FIG. 4 may execute a modified write command 505-1 to write command 505 after the block IDs 515-1 to 515-3 of FIG. 5 have been determined by theLBA mapper 410 of FIG. 4 Block IDs 515-1 to 515-3 are queued after -3 has been sent toSSD 120 of Figure 1 or at any time between them.

图7示出将图5的LBA 510-1映射到图5的区块ID 515-1的图5的算术逻辑单元(ALU)520。在图7中，ALU 520可接收LBA 510-1和区块大小705。通过将LBA 510-1除以区块大小705(并弃用计算的任何小数部分)，可计算区块ID 515-1。FIG. 7 shows the arithmetic logic unit (ALU) 520 of FIG. 5 mapping the LBA 510-1 of FIG. 5 to the block ID 515-1 of FIG. 5 . In FIG. 7,ALU 520 may receive LBA 510-1 andblock size 705. Block ID 515-1 can be calculated by dividing LBA 510-1 by block size 705 (and discarding any fractional part of the calculation).

如上面参照图4所述，可以以不同的方式来实现图4的后台逻辑435。图8至图13描述本发明构思的一个实施例，图14至图20描述本发明构思的另一个实施例。本发明构思的这些实施例不意图互相排斥：本发明构思的两个实施例的组合是可行的。此外，无论是否在这里明确地描述，本发明构思的其他实施例也是可行的。As described above with reference to FIG. 4, thebackground logic 435 of FIG. 4 may be implemented in different ways. 8 to 13 describe one embodiment of the present inventive concept, and FIGS. 14 to 20 describe another embodiment of the present inventive concept. These embodiments of the inventive concept are not intended to be mutually exclusive: combinations of the two embodiments of the inventive concept are possible. Furthermore, other embodiments of the inventive concept are possible, whether or not explicitly described herein.

在针对图4的后台逻辑435的本发明构思的第一实施例中，图3的区块流映射器340可包括顺序性、频度和近因(SFR)表。“顺序性、频度和近因”表示可确定和更新将被分配给区块的流ID的方式。“顺序性”表示一个写入命令对于另一写入命令是顺序的情形，换言之，第二写入命令在较早的写入命令之后将数据写入到下一LBA。在两个写入命令是顺序的情况下，两个命令应被分配同一流ID是说得通的。In a first embodiment of the present inventive concept for thebackground logic 435 of FIG. 4, theblock stream mapper 340 of FIG. 3 may include a sequentiality, frequency, and recency (SFR) table. "Order, Frequency, and Recency" means the manner in which stream IDs to be assigned to chunks can be determined and updated. "Sequential" means the situation where one write command is sequential to another, in other words, the second write command writes data to the next LBA after the earlier write command. In the case where the two write commands are sequential, it makes sense that both commands should be assigned the same stream ID.

如下面参照图10所述，由于写入命令可从任意数量的不同软件源发出，所以本申请的上下文中的“顺序性”不应该完全从字面上理解。如果来自单个软件源(例如，数据库应用)的两个“顺序的”写入命令碰巧被来自一些其他软件源(例如，文件系统)的写入命令分隔开，则介于中间的写入命令不应该消除来自数据库应用的两个写入命令的顺序性。事实上，这里提供了用于避免介于中间的写入命令打断顺序性的机制。As described below with reference to FIG. 10, since write commands may be issued from any number of different software sources, "sequentiality" in the context of this application should not be taken completely literally. If two "sequential" write commands from a single software source (eg, a database application) happen to be separated by a write command from some other software source (eg, a file system), the intervening write command The sequentiality of the two write commands from the database application should not be eliminated. In fact, a mechanism is provided here to avoid intervening write commands from breaking the sequence.

“频度”表示多频繁地访问区块。区块被访问地越频繁，就认为区块越“热”(使用温度充当对优先级的类比：区块的“温度”越高，它的优先级应该越高)。因此，当区块被越来越多地访问时，它应被分配较高的流优先级。"Frequency" indicates how often the block is accessed. The more frequently a block is accessed, the more "hot" a block is considered to be (using temperature as an analogy for priority: the higher the "temperature" of a block, the higher its priority should be). Therefore, as a block is accessed more and more, it should be assigned a higher stream priority.

“近因”表示自从区块上次被访问已经过了多久。“近因”对“频度”起平衡作用：自从区块上次被访问跨度越长，认为区块越“冷”，并因此，区块被分配较低优先级。因此，“频度”增加区块的关联的流，而“近因”减少块的关联的流。下面参照图10至图13进一步讨论“顺序性”、“频度”和“近因”。"Recency" indicates how long it has been since the block was last accessed. "Recency" balances "frequency": the longer the span since the block was last accessed, the more "cold" the block is considered to be, and as a result, the block is assigned a lower priority. Thus, "frequency" increases the associated flow of a block, while "recency" decreases the associated flow of a block. "Sequence", "Frequency" and "Recency" are discussed further below with reference to Figures 10-13.

现在转向图8中示出的本发明构思的实施例，图8示出根据本发明构思的这个实施例的可用于将图5的区块ID 515-1至515-3映射到图5的流ID 530-1至530-3的示例SFR表。在图8中，SFR表805可存储器各种数据。例如，SFR表805可存储器各种区块ID 515-1至515-4以及针对每个区块ID 515-1至515-4的SFR相应的流ID 530-1至流ID 530-4。Turning now to the embodiment of the inventive concept shown in FIG. 8, FIG. 8 illustrates a stream that may be used to map the block IDs 515-1 to 515-3 of FIG. 5 to FIG. 5 according to this embodiment of the inventive concept Example SFR tables for IDs 530-1 to 530-3. In FIG. 8, SFR table 805 may store various data. For example, the SFR table 805 may store various block IDs 515-1 through 515-4 and corresponding flow IDs 530-1 through 530-4 for the SFR of each block ID 515-1 through 515-4.

除了流ID 530-1至流ID 530-4之外，SFR表805可存储另外的数据。例如，针对每个区块ID 515-1至515-4，SFR表805可存储针对那个区块的当前(即，最近)访问时间810-1至810-4。当前访问时间810-1至810-4可以是任何类型的区块的最后访问的时间(例如，读取或写入)，或者仅是最近写入命令的时间。SFR表805还可存储可表示区块被先前访问的时间的先前访问时间815-1至815-4。最后，SFR表805可存储器可表示区块的访问的次数的访问计数820-1至820-4。如上所述，访问计数820-1至820-4可表示区块的访问(读取和写入二者)的总次数，或仅表示区块的写入访问的总次数。In addition to flow ID 530-1 to flow ID 530-4, SFR table 805 may store additional data. For example, for each block ID 515-1 to 515-4, the SFR table 805 may store the current (ie, most recent) access time 810-1 to 810-4 for that block. The current access times 810-1 to 810-4 may be the time of the last access (eg, read or write) of any type of block, or just the time of the most recent write command. SFR table 805 may also store previous access times 815-1 through 815-4, which may represent times when blocks were previously accessed. Finally, the SFR table 805 may store access counts 820-1 through 820-4 that may represent the number of times the block was accessed. As discussed above, the access counts 820-1 to 820-4 may represent the total number of accesses (both reads and writes) to the block, or only the total number of write accesses to the block.

虽然图8示出本发明构思的一个可行实施例，但是本发明构思的其他实施例可存储多于或少于图8中示出的数据的数据。此外，除了所述表之外的数据结构可被用于存储信息。本发明构思的实施例意图覆盖全部这样的变化。While FIG. 8 illustrates one possible embodiment of the inventive concept, other embodiments of the inventive concept may store more or less data than that shown in FIG. 8 . Furthermore, data structures other than the table may be used to store information. Embodiments of the inventive concept are intended to cover all such variations.

图9示出根据本发明构思的第一实施例的图3的闪存转换层325和图4的后台逻辑435的附加细节。在图9中，闪存转换层325还可包括顺序性逻辑905。出于使用与较早写入命令相同的流分配，顺序性逻辑905可确定图5的写入命令505-1与某个较早写入命令是否是顺序的。下面参照图10进一步讨论顺序性逻辑905。FIG. 9 illustrates additional details of theflash translation layer 325 of FIG. 3 and thebackground logic 435 of FIG. 4 in accordance with a first embodiment of the inventive concept. In FIG. 9 ,flash translation layer 325 may also includesequential logic 905 .Sequential logic 905 may determine whether write command 505-1 of FIG. 5 is sequential with an earlier write command in order to use the same stream allocation as an earlier write command.Sequential logic 905 is discussed further below with reference to FIG. 10 .

后台逻辑435可包括近因逻辑910、访问计数调节器915和流ID调节器920。近因逻辑910可计算区块的近因权重。访问计数调节器915可基于近因权重调节区块的访问计数。流ID调节器可基于调节的访问计数计算用于区块的新的流ID。由于近因逻辑910、访问计数调节器915和流ID调节器920执行算术计算，所以他们可使用一个(或多个)单独或共享的ALU来全部实现。可选择地，近因逻辑910、访问计数调节器915和流ID调节器920可使用被设计为仅计算描述和仅此而已的特定功能的专用硬件来实现。Background logic 435 may includerecency logic 910 ,access count modifier 915 and flowID modifier 920 . Therecency logic 910 may calculate a recency weight for the block. Theaccess count adjuster 915 may adjust the access count of the block based on the recency weight. The stream ID adjuster may calculate a new stream ID for the chunk based on the adjusted access count. Sincerecency logic 910,access count modifier 915, andstream ID modifier 920 perform arithmetic computations, they can all be implemented using one (or more) separate or shared ALUs. Alternatively,recency logic 910,access count modifier 915, and flowID modifier 920 may be implemented using dedicated hardware designed to only compute descriptions and nothing more for specific functions.

图10示出图9的顺序性逻辑905的细节。在图10中，顺序性逻辑905被示出为包括存储器1005和比较器1010。出于实用的目的，存储器1005可以是图3的存储器330的一部分，而不是作为顺序性逻辑905内的独立存储器。存储器1005可存储器作为关于一组最近写入命令的信息的窗口1015，其中，一组最近写入命令中的每个最近写入命令可具有分配给它的流ID。例如，图10示出条目1020-1至条目1020-8，其中，条目1020-1至条目1020-4在窗口1015内。可按队列1025管理条目1020-1至条目1020-8。队列1025可采用任何期望的形式：例如，列出两个示例实施方式为，具有指向队列1025的头部的指针的阵列，或者链表。每个条目1020-1至条目1020-8可包括较早写入命令的结束LBA 1030和流ID 1035。窗口1015可包括可指定窗口1015中包括多少个最近条目的窗口大小1040：在图10中，窗口大小1040被示出为包括四个条目，但本发明构思的实施例可支持窗口1015中的任何数量的条目。窗口大小1040可依赖于多种因素，所述多种因素包括例如图1的处理器110中的核的数量或者在图1的处理器110上运行的可发出写入命令的软件源(操作系统、文件系统、应用等)的数量。本发明构思的实施例可同样支持基于其他因素确定的窗口大小。此外，窗口大小1040可被静态设置，或可随着图1的机器105内的条件变化而被动态改变。FIG. 10 shows details of thesequential logic 905 of FIG. 9 . In FIG. 10 ,sequential logic 905 is shown to includememory 1005 andcomparator 1010 . For practical purposes,memory 1005 may be part ofmemory 330 of FIG. 3 rather than being a separate memory withinsequential logic 905 . Thememory 1005 may store as awindow 1015 of information about a set of recent write commands, wherein each most recent write command in the set of recent write commands may have a stream ID assigned to it. For example, FIG. 10 shows entries 1020-1 through 1020-8, where entries 1020-1 through 1020-4 are withinwindow 1015. Entries 1020-1 to 1020-8 may be managed byqueue 1025. Thequeue 1025 may take any desired form: for example, two example implementations are listed as an array with pointers to the head of thequeue 1025, or a linked list. Each entry 1020-1 through entry 1020-8 may include theend LBA 1030 andstream ID 1035 of the earlier write command.Window 1015 may include a window size 1040 that may specify how many recent entries are included in window 1015: In FIG. 10, window size 1040 is shown as including four entries, but embodiments of the present inventive concepts may support any ofwindows 1015 number of entries. Window size 1040 may depend on a variety of factors including, for example, the number of cores inprocessor 110 of FIG. 1 or a software source (operating system) running onprocessor 110 of FIG. 1 that can issue write commands. , file systems, applications, etc.). Embodiments of the inventive concept may similarly support window sizes determined based on other factors. Furthermore, the window size 1040 may be statically set, or may be dynamically changed as conditions within themachine 105 of FIG. 1 change.

当图5的新的写入命令505-1被接收时，比较器1010可将图5的LBA 510-1与窗口1015中的条目1020-1至条目1020-4的结束LBA 1030进行比较。如果图5的LBA 510-1是在较早写入命令的结束LBA 1030之后的下一地址，则图5的LBA 510-1可被考虑为与较早写入命令的结束LBA 1030是顺序的。可选地，如果不存在可用于较早写入命令的结束LBA 1030与图5的LBA 510-1之间的有效LBA，则图5的LBA 510-1可被认为是与较早写入命令的结束LBA1030是顺序的。(注意的是：假设没有已经能写入数据的可能的介于中间的地址，结束LBA1030不需要是字面上的将由较早写入命令写入的最后地址)。如果图5的LBA 510-1与窗口1015中的任何条目1020-1至条目1020-4的结束LBA 1030是顺序的，则条目1020-1至条目1020-4中的流ID 1035被用于图5的写入命令505-1。When a new write command 505-1 of FIG. 5 is received,comparator 1010 may compare LBA 510-1 of FIG. 5 to endLBA 1030 of entry 1020-1 through entry 1020-4 inwindow 1015. If the LBA 510-1 of FIG. 5 is the next address after theend LBA 1030 of the earlier write command, then the LBA 510-1 of FIG. 5 may be considered sequential to theend LBA 1030 of the earlier write command . Alternatively, if there is no valid LBA available between theend LBA 1030 of the earlier write command and the LBA 510-1 of FIG. 5, the LBA 510-1 of FIG. 5 may be considered to be the same as the earlier write command. The end of the LBA1030 is sequential. (Note: endLBA 1030 need not be literally the last address to be written by an earlier write command, assuming there are no possible intervening addresses to which data can already be written). If theend LBA 1030 of the LBA 510-1 of FIG. 5 and any entry 1020-1 to entry 1020-4 in thewindow 1015 is sequential, theflow ID 1035 in the entry 1020-1 to entry 1020-4 is used in the figure 5 of the write command 505-1.

虽然确定顺序的LBA是一种用于确定顺序性何时已经发生的方式，但是本发明构思的实施例可支持用于检测顺序性的其他实施方式。例如，顺序性逻辑905可使用用于检测特定软件源何时以重复模式访问LBA的模式匹配器。While determining sequential LBA is one way to determine when sequentiality has occurred, embodiments of the present inventive concepts may support other implementations for detecting sequentiality. For example,sequential logic 905 may use a pattern matcher for detecting when a particular software source accesses an LBA in a repeating pattern.

不管图5的LBA 510-1与窗口1015中的任何条目1020-1至条目1020-4的结束LBA1030是否是顺序的，窗口1015中的最旧的条目可被“弹出”，并且图5的写入命令505-1可被添加到窗口1015。例如，假设条目1020-1是窗口1015中的最近写入命令的条目，则条目1020-4是窗口1015中的最旧的条目。条目1020-4可从窗口1015去除，图5的LBA 510-1和流ID 530-1二者可作为新条目而被添加到窗口1015。可以以任何期望的方式实现窗口1015。例如，窗口1015可包括具有指向最旧的条目的指针的循环表(诸如，阵列)。当新的条目将被添加到窗口1015时，指针指向的最旧的条目可被新的条目覆写，并且指针可被调节为指向窗口1015中的下一最旧的条目。本发明构思的实施例可支持用于存储关于窗口1015的信息的任何期望的结构：循环表仅仅是一个这样可行的数据结构。Regardless of whether the LBA 510-1 of FIG. 5 and any entry 1020-1 to theend LBA 1030 of entry 1020-4 inwindow 1015 are sequential, the oldest entry inwindow 1015 may be "popped" and the write of FIG. 5 Input command 505-1 may be added towindow 1015. For example, assuming that entry 1020-1 is the entry for the most recent write command inwindow 1015, entry 1020-4 is the oldest entry inwindow 1015. Entry 1020-4 may be removed fromwindow 1015, and both LBA 510-1 and flow ID 530-1 of FIG. 5 may be added towindow 1015 as new entries.Window 1015 may be implemented in any desired manner. For example,window 1015 may include a circular table (such as an array) with pointers to the oldest entries. When a new entry is to be added towindow 1015, the oldest entry pointed to by the pointer can be overwritten by the new entry, and the pointer can be adjusted to point to the next oldest entry inwindow 1015. Embodiments of the inventive concept may support any desired structure for storing information about the window 1015: a circular table is just one such possible data structure.

图11示出使用图9的近因逻辑910计算近因权重。在图11中，近因逻辑910被示出为计算近因权重1105。图11中示出的公式将近因权重1105计算为二的将针对区块的当前(即，最近)访问时间810-1与先前访问时间815-1之间的差除以衰减期1110次幂。衰减期1110表示可控制区块多快降级到较低优先级流的可调变量。衰减期1110可当图1的机器105启动时被分配初始值，并可如期望地(由系统管理员手动或基于系统工作量自动)被调节。防止区块升级太快(这可导致大多数区块使用同一高优先级流)或太慢(这可导致大多数区块使用同一低优先级流)是可取的。换句话说，具有以相当均匀的方式被分配流的块是可取的：没有单个流应该被过度或轻度使用。衰减期1110表示用于管理流升级和降级以实现这个目标的一种方式。FIG. 11 illustrates calculating recency weights using therecency logic 910 of FIG. 9 . In FIG. 11 ,recency logic 910 is shown calculatingrecency weights 1105 . The formula shown in FIG. 11 divides the difference between the current (ie, most recent) access time 810-1 and the previous access time 815-1 for the block by the decay period to thepower 1110, which calculates theapproximate weight 1105 as two.Decay period 1110 represents a tunable variable that can control how quickly a block is demoted to a lower priority stream. Thedecay period 1110 may be assigned an initial value when themachine 105 of FIG. 1 starts up, and may be adjusted as desired (either manually by a system administrator or automatically based on system workload). It is desirable to prevent blocks from being upgraded too quickly (which can cause most blocks to use the same high-priority stream) or too slow (which can cause most of them to use the same low-priority stream). In other words, it is desirable to have chunks that are allocated streams in a fairly even way: no single stream should be over or lightly used.Decay period 1110 represents one way to manage stream promotion and demotion to achieve this goal.

注意的是：近因权重1015可针对每个区块而变化。另一方面，衰减期1110在针对近因权重1105的全部计算之间应是均匀的(但这不意味着衰减期1110可不随时间变化)。Note that therecency weight 1015 may vary for each block. On the other hand, thedecay period 1110 should be uniform across all calculations for the recency weight 1105 (but this does not mean that thedecay period 1110 may not vary over time).

图12示出在图9的访问计数调节器915中使用图11的近因权重1105来调节访问计数。在图12中，访问计数调节器915被示出为计算调节的访问计数1205。调节的访问计数1205可被计算为一加访问计数820-1然后除以近因权重1105。调节的访问计数1205可然后替换访问计数820-1而被存储在例如图8的SFR表805中。FIG. 12 illustrates the use of therecency weight 1105 of FIG. 11 in theaccess count adjuster 915 of FIG. 9 to adjust the access count. In FIG. 12 , theaccess count adjuster 915 is shown calculating the adjustedaccess count 1205 . Theadjusted access count 1205 may be calculated as one plus the access count 820 - 1 and then divided by therecency weight 1105 . Theadjusted access count 1205 may then be stored, eg, in the SFR table 805 of FIG. 8, in place of the access count 820-1.

图13示出使用图9的流ID调节器920从图12的调节的访问计数1205计算流ID。在图13中，流ID调节器920被示出为计算流ID 530-1。流ID 530-1可被计算为调节的访问计数1205的对数，并且调节的访问计数1205的对数可替换流ID 530-1而被存储在例如图8的SFR表805中。虽然在涉及计算机时使用的数学术语“对数”典型地意味着log₂或log₁₀，但是可选择使用任何期望的底的对数函数。针对对数函数选择的底提供了本发明构思的实施例可避免区块升级太快或太慢(并因而一个或多个装置流的过渡使用和其他装置流的使用不足)的另一种机制。流ID调节器920还可根据调节的访问计数1205变得有多大来使用多于一个的对数函数。例如，如果调节的访问计数1205小于某一阈值，则流ID调节器920可使用log₂来计算流ID 530-1；如果调节的访问计数1205大于阈值，则流ID调节器920可使用log₁₀来计算流ID 530-1。FIG. 13 illustrates the use of theflow ID conditioner 920 of FIG. 9 to calculate the flow ID from the adjustedaccess count 1205 of FIG. 12 . In Figure 13,flow ID conditioner 920 is shown calculating flow ID 530-1. Flow ID 530-1 may be calculated as the log ofadjusted access count 1205, and the log ofadjusted access count 1205 may be stored, eg, in SFR table 805 of FIG. 8, in place of flow ID 530-1. Although the mathematical term "logarithm" as used in reference to computers typically means log₂ or log₁₀ , any desired base logarithmic function may alternatively be used. The base chosen for the logarithmic function provides another mechanism by which embodiments of the inventive concept may avoid block upgrades that are too fast or too slow (and thus over-use of one or more device streams and under-use of other device streams). . Theflow ID conditioner 920 may also use more than one logarithmic function depending on how large theadjusted access count 1205 becomes. For example, if theadjusted access count 1205 is less than a certain threshold, theflow ID conditioner 920 may use log₂ to calculate the flow ID 530-1; if theadjusted access count 1205 is greater than the threshold, theflow ID conditioner 920 may use log₁₀ to calculate the stream ID 530-1.

值得做出几个关于图11至图13的评论。第一，图11至图13示出用于计算图11的近因权重1105、图12的调节的访问计数1205和图13的流ID 530-1的特定计算。但是本发明构思的实施例可支持以任何期望的方式计算这些(或其他值)。由于最终目标是能够将图8的流ID 530-1(向上或向下)调节为适于图8的区块515-1，所以可使用实现这样的结果的任何期望的方法。图11至图13仅示出一个这样的方法。It is worth making several comments about Figures 11 to 13. First, FIGS. 11-13 illustrate specific calculations for calculating therecency weight 1105 of FIG. 11 , the adjustedaccess count 1205 of FIG. 12 , and the flow ID 530 - 1 of FIG. 13 . But embodiments of the inventive concept may support calculating these (or other values) in any desired manner. Since the ultimate goal is to be able to adjust the flow ID 530-1 of Figure 8 (up or down) to fit the block 515-1 of Figure 8, any desired method of achieving such a result may be used. Figures 11-13 illustrate only one such method.

第二，在图11至图13中，访问时间(诸如，图11的当前访问时间810-1和先前访问时间815-1)可基于发出的请求的数量而被确定，而不是基于特定时钟而被确定。例如，假设图5的写入命令505-1至写入命令505-3被连续发出。图5的写入命令505-1可以是第四写入命令，图5的写入命令505-2可以是第五写入命令，图5的写入命令505-3可以是第六写入命令。在这个示例中，针对各种写入命令的“访问时间”将分别是“4”、“5”和“6”。Second, in FIGS. 11-13 , access times (such as current access time 810-1 and previous access time 815-1 of FIG. 11) may be determined based on the number of requests issued, rather than based on a particular clock It is determined. For example, it is assumed that the write command 505-1 to the write command 505-3 of FIG. 5 are continuously issued. The write command 505-1 of FIG. 5 may be the fourth write command, the write command 505-2 of FIG. 5 may be the fifth write command, and the write command 505-3 of FIG. 5 may be the sixth write command . In this example, the "access times" for the various write commands would be "4", "5" and "6" respectively.

确定访问时间的这个选择具有如下影响：如果全部的软件源将在一些时间间隔(诸如，1秒或1分钟或者1小时)内停止发出写入命令，则即使区块在相当长的时间内还没有被技术地访问，区块的“温度”也将不会变化。因此，即使区块可能在相当长的时间内可能还没有被访问，如果在那个时间期间也没有其他区块被访问，则区块的“温度”将不会变化。从实用性的角度看，全部的软件源会同时停止发送写入命令是不太可能的。但如果发生了这种情况，则本发明构思的实施例将能够处理这种情况。此外，本发明构思的实施例可支持使用时钟时间而非命令编号，这可造成：即使没有软件源发出写入命令，区块也会冷却。This choice of determining access time has the effect that if all software sources will stop issuing write commands within some time interval (such as 1 second or 1 minute or 1 hour), even if the block is Without being technically accessed, the "temperature" of the block will not change. Therefore, even though a block may not have been accessed for a considerable period of time, the "temperature" of the block will not change if no other blocks have been accessed during that time. From a practical standpoint, it is unlikely that all software sources will stop sending write commands at the same time. But if such a situation occurs, embodiments of the present inventive concept will be able to handle such a situation. Furthermore, embodiments of the inventive concept may support the use of clock times rather than command numbers, which may result in blocks being cooled even if no software source issues a write command.

与图8-图13不同，图14-图20示出本发明构思的另一实施例。与图8至图13中示出的本发明构思的实施例一样，图14至图20可包括用于将图5的区块ID 515-1至区块ID 515-3映射到图5的流ID 530-1至流ID 530-3的数据结构以及图4的后台逻辑435的实施方式。Unlike FIGS. 8-13 , FIGS. 14-20 illustrate another embodiment of the present inventive concept. Like the embodiments of the inventive concept shown in FIGS. 8-13 , FIGS. 14-20 may include a stream for mapping the block ID 515-1 to block ID 515-3 of FIG. 5 to the flow of FIG. 5 The data structure of ID 530-1 to flow ID 530-3 and the implementation of thebackground logic 435 of FIG. 4 .

图14示出根据本发明构思的第二实施例的可用于将图5的区块ID 515-1至515-3映射到图5的流ID 530-1至530-3的节点。在图14中，示出了节点1405-1至1405-3，并详细示出节点1405-1。可以以任何期望的方式(诸如，阵列、链表或其他数据结构)存储器节点1405-1至节点1405-3。图1的SSD 120中的每个区块可有一个节点。14 illustrates nodes that may be used to map the block IDs 515-1 to 515-3 of FIG. 5 to the flow IDs 530-1 to 530-3 of FIG. 5 according to a second embodiment of the inventive concept. In FIG. 14, nodes 1405-1 to 1405-3 are shown, and node 1405-1 is shown in detail. Nodes 1405-1 through 1405-3 may be stored in any desired manner, such as an array, linked list, or other data structure. Each block inSSD 120 of FIG. 1 may have one node.

节点1405-1可包括各种数据，其中，各种数据包括区块ID 515-1、流ID 530-1、访问计数820-1和失效时间1410。区块ID 515-1、流ID 530-1和访问计数820-1存储器与本发明构思的第一实施例中的那些元素类似的数据。失效时间1410表示由于缺少写入命令的访问而被认为失效的时间。与本发明构思的第一实施例一样，“时间”可根据按全部写入命令的顺序的特定写入命令的数量被测量，而非作为时钟的测量。Node 1405-1 may include various data including block ID 515-1, flow ID 530-1, access count 820-1, andexpiration time 1410. The block ID 515-1, the stream ID 530-1, and the access count 820-1 store data similar to those in the first embodiment of the inventive concept. Theinvalidation time 1410 represents the time that is considered invalid due to lack of access to the write command. As with the first embodiment of the inventive concept, "time" may be measured in terms of the number of specific write commands in the order of all write commands, rather than as a measurement of a clock.

图15示出根据本发明构思的第二实施例的图4的后台逻辑435的细节。在图15中，后台逻辑435可包括升级逻辑1505、第二排队器1510、用于队列1520-1至队列1520-3的存储器1515以及降级逻辑1525。升级逻辑1505可在合适的时候将区块升级为较高优先级流。第二排队器1510(这样命名以区分它与图4的排队器430，但它的操作是类似的)可将区块ID515-1至区块515-3置于队列1520-1至队列1520-3中。第二排队器1510可具有与图4的排队器430类似的结构。与图10的存储器1005类似的存储器1515可有效地作为图3的存储器330的一部分，而不是作为后台逻辑435内的独立存储器。本发明构思的实施例可支持任何数量的队列：三个队列1520-1至1520-3仅是示例。此外，图5的每个流ID 530-1至流ID 530-3可有一个队列：队列1520-1至队列1520-3的数量与图5的区块ID 515-1至区块ID 515-3的数量相同是偶然的。当图5的区块ID 515-1至区块ID 515-3到达队列1520-1至队列1520-3的头部时，降级逻辑1525可确定是否将图5的区块ID 515-1至区块ID 515-3降级。FIG. 15 illustrates details of thebackground logic 435 of FIG. 4 according to a second embodiment of the inventive concept. In FIG. 15 ,background logic 435 may includepromotion logic 1505 ,second queue 1510 ,memory 1515 for queues 1520 - 1 to 1520 - 3 , anddemotion logic 1525 .Promotion logic 1505 may promote blocks to higher priority streams when appropriate. The second queuer 1510 (so named to distinguish it from thequeuer 430 of FIG. 4, but its operation is similar) may place block IDs 515-1 through 515-3 in queues 1520-1 through 1520- 3 in. Thesecond queuer 1510 may have a similar structure to thequeuer 430 of FIG. 4 . Amemory 1515 similar to thememory 1005 of FIG. 10 may effectively be part of thememory 330 of FIG. 3 rather than being a separate memory within thebackground logic 435. Embodiments of the inventive concept may support any number of queues: the three queues 1520-1 to 1520-3 are merely examples. In addition, each flow ID 530-1 to flow ID 530-3 of FIG. 5 may have one queue: the number of queues 1520-1 to 1520-3 is the same as that of block ID 515-1 to block ID 515- of FIG. 5- The same number of 3 is by chance. When block ID 515-1 to block ID 515-3 of FIG. 5 arrive at the head of queue 1520-1 to queue 1520-3,demotion logic 1525 may determine whether to add block ID 515-1 of FIG. 5 to the zone Block ID 515-3 is downgraded.

图16示出图15的队列1520-1至队列1520-3中的区块ID的升级和降级。在图16中，使用字母a至d表示图5的区块ID 515-1至区块ID 515-3。队列1520-1至队列1520-3中的没有标记的条目不在图16中示出的示例中使用，并可存储在本示例中不另外使用的任何区块ID。FIG. 16 shows promotion and demotion of block IDs in queues 1520-1 to 1520-3 of FIG. 15 . In FIG. 16 , the block IDs 515-1 to 515-3 of FIG. 5 are represented by letters a to d. Unmarked entries in queues 1520-1 to 1520-3 are not used in the example shown in FIG. 16 and may store any block IDs not otherwise used in this example.

首先，在图16中，提交队列335被示出为具有在提交队列335的头部1605的区块IDa。区块ID a可识别以前还没有先前访问的区块。相应地，在区块ID a可从提交队列335被去除之后，如虚箭头1610所示，区块ID a可被添加到队列1520-1(针对“最冷”流的队列)的尾部。First, in FIG. 16 , the commitqueue 335 is shown with the block IDa at thehead 1605 of the commitqueue 335 . Block ID a identifies a block that has not been previously accessed before. Accordingly, after chunk ID a may be removed fromsubmission queue 335, chunk ID a may be added to the tail of queue 1520-1 (the queue for the "coolest" flow), as indicated by dashedarrow 1610.

其次，在图16中，提交队列335可包括区块ID b(区块ID b可在区块ID a被处理之后移动到提交队列335的头部1605中)。作为增加针对区块ID b的图14的访问计数820-1的结果，区块ID b可被升级到“较热”流。在区块ID b从提交队列335被去除之后，如虚箭头1615所示，区块ID b可从队列1520-1的条目1620被移动到队列1520-2的尾部。Second, in Figure 16, thesubmission queue 335 may include block ID b (the block ID b may be moved into thehead 1605 of thesubmission queue 335 after the block ID a is processed). As a result of increasing the access count 820-1 of Figure 14 for block ID b, block ID b may be upgraded to a "hotter" stream. After block ID b is removed from commitqueue 335, block ID b may be moved fromentry 1620 of queue 1520-1 to the tail of queue 1520-2, as indicated by dashedarrow 1615.

再次，图15的降级逻辑1525可依次检查队列1520-1至队列1520-3的头部1625-1至头部1625-3。例如，图15的降级逻辑1525可检查在队列1520-3的头部1625-3的区块ID c。如果区块ID c应该得到降级，则区块ID c可从队列1520-3的头部1625-3被移动到队列1520-2(针对下一“最热流”的队列)的尾部。如下面参照图17所述，作为区块ID c被降级的结果，队列1520-3中的区块ID d可变成最热的区块。Again, thedemotion logic 1525 of FIG. 15 may check queue 1520-1 through head 1625-1 through head 1625-3 of queue 1520-3 in sequence. For example, thedemotion logic 1525 of Figure 15 may check for block ID c at the head 1625-3 of the queue 1520-3. If block ID c should be demoted, block ID c may be moved from the head 1625-3 of queue 1520-3 to the tail of queue 1520-2 (the queue for the next "hottest flow"). As described below with reference to FIG. 17, block ID d in queue 1520-3 may become the hottest block as a result of block ID c being demoted.

图17示出图15的升级逻辑1505的细节。在图17中，升级逻辑1505可包括增量器1705、流ID调节器1710、区块失效逻辑1715和最热区块逻辑1720。增量器1705可增加图14的访问计数820-1，产生调节的访问计数。如图18所示，流ID调节器1710可从调节的访问计数计算图5的流ID 530-1。流ID调节器1710可与图9的流ID调节器920结构上类似。FIG. 17 shows details of theupgrade logic 1505 of FIG. 15 . In FIG. 17 , upgradelogic 1505 may includeincrementer 1705 ,stream ID conditioner 1710 , blockinvalidation logic 1715 , andhottest block logic 1720 . Theincrementer 1705 may increment the access count 820-1 of FIG. 14, resulting in an adjusted access count. As shown in FIG. 18, theflow ID conditioner 1710 may calculate the flow ID 530-1 of FIG. 5 from the adjusted access count.Flow ID modifier 1710 may be similar in structure to flowID modifier 920 of FIG. 9 .

回到图17，区块失效逻辑1715可确定区块的失效时间。区块的失效时间可被确定为区块ID的当前访问时间加上装置寿命。装置寿命是根据哪个区块是最热的区块的时间间隔，这将在下面进行讨论。图19将这示出为等式：失效时间1410是访问计数820-1(如上面所述地可以是图5的区块ID 515-1的当前访问时间)与装置寿命1905的和。Returning to FIG. 17,block invalidation logic 1715 may determine when the block will expire. The expiration time of the block can be determined as the current access time of the block ID plus the device age. Device lifetime is the time interval based on which block is the hottest block, as discussed below. Figure 19 shows this as an equation:Expiration time 1410 is the sum of access count 820-1 (which could be the current access time of block ID 515-1 of Figure 5 as described above) anddevice age 1905.

最后，再次回到图17，最热区块逻辑1720可确定图5的区块ID 515-1现在是否表示最热的区块。最热的区块可被定义为具有最高流优先级的区块ID。如果存在具有最高流优先级的多个区块ID，则任何选择算法可被用于将具有最高流优先级的特定区块ID选择作为最热的区块。例如，在队列的头部的表示最高流优先级的区块ID可被选择作为最热的区块。或者，具有最近访问(即，最高读取访问时间)的区块ID可被选择作为最热的区块。或者，在队列的尾部的表示最高流优先级的区块ID可被选择作为最热的区块。如果图5的区块ID515-1现在是最热的区块，则图19的装置寿命1905可被计算为图5的区块ID 515-1的当前访问时间与图5的区块ID 515-1的先前访问时间之间的差。图19的装置寿命1905可表示特定区块上的两个写入命令之间期望的最大间隔，并可基于针对最热的区块的最近的两个写入命令之间的间隔而被定义。图19的装置寿命1905可然后被用于确定图14的失效时间1410，其中，失效时间1410可影响何时将图14的区块ID 515-1降级。Finally, returning again to FIG. 17, thehottest block logic 1720 may determine whether the block ID 515-1 of FIG. 5 now represents the hottest block. The hottest block can be defined as the block ID with the highest stream priority. If there are multiple block IDs with the highest flow priority, any selection algorithm can be used to select the particular block ID with the highest flow priority as the hottest block. For example, the block ID representing the highest flow priority at the head of the queue may be selected as the hottest block. Alternatively, the block ID with the most recent access (ie, the highest read access time) may be selected as the hottest block. Alternatively, the block ID representing the highest flow priority at the tail of the queue may be selected as the hottest block. If block ID 515-1 of FIG. 5 is now the hottest block,device lifetime 1905 of FIG. 19 can be calculated as the current access time of block ID 515-1 of FIG. 5 and block ID 515-1 of FIG. 5- The difference between the previous access times of 1. Thedevice lifetime 1905 of Figure 19 may represent the maximum expected interval between two write commands on a particular block, and may be defined based on the interval between the most recent two write commands for the hottest blocks. Thedevice lifetime 1905 of FIG. 19 may then be used to determine thefailure time 1410 of FIG. 14 , where thefailure time 1410 may affect when the block ID 515-1 of FIG. 14 is degraded.

图20示出图15的降级逻辑1525的细节。在图20中，降级逻辑1525被示出为包括比较器2005和减量器2010。比较器2005可将当前时间(又可以是最近写入请求的数量，而非时钟时间)与图14的失效时间1410进行比较。如果当前时间过了图14的失效时间1410，则因为区块在没有任何写入命令的情况下经过了一段时间间隔(该时间间隔可被测量为图19的装置寿命1905)，所以区块可被认为比之前冷。换句话说，如果图19的装置寿命1905表示针对任何给定区块的写入之间的写入命令的期望的数量，则图14的失效时间1410可表示图14的区块ID 515-1可被写入并不被认为已经冷却的最近时间，其中，图14的失效时间1410可被计算为图14的区块ID 515-1的最近访问时间加上图19的装置寿命1905。如果图14的失效时间1410已经过去，则图14的区块ID 515-1已经有所冷却，并可被降级。在那种情况下，减量器2010可减少图5的流ID 530-1，以将图5的区块ID 515-1的优先级降低为对应于图5的区块ID 515-1的降低的“温度”。FIG. 20 shows details of thedestaging logic 1525 of FIG. 15 . In FIG. 20 , thedegradation logic 1525 is shown to include acomparator 2005 and adecrementor 2010 .Comparator 2005 may compare the current time (which again may be the number of recent write requests, rather than clock time) to theexpiration time 1410 of FIG. 14 . If the current time has passed theexpiration time 1410 of FIG. 14, then the block may have passed an interval of time without any write commands (this time interval may be measured as thedevice lifetime 1905 of FIG. 19) considered colder than before. In other words, if thedevice lifetime 1905 of FIG. 19 represents the expected number of write commands between writes for any given block, then theexpiration time 1410 of FIG. 14 may represent the block ID 515-1 of FIG. 14 The most recent time that can be written and not considered to have cooled, where theexpiration time 1410 of FIG. 14 can be calculated as the last access time of block ID 515-1 of FIG. 14 plus thedevice age 1905 of FIG. 19 . If theexpiration time 1410 of FIG. 14 has elapsed, the block ID 515-1 of FIG. 14 has cooled down and can be downgraded. In that case, thedecrementor 2010 may decrement the flow ID 530-1 of FIG. 5 to reduce the priority of the block ID 515-1 of FIG. 5 to a reduction corresponding to the block ID 515-1 of FIG. 5 temperature".

如果图14的失效时间1410还没有过去，则图14的区块ID 515-1还没有冷却，并且图14的区块ID 515-1可被留在它的队列的头部。注意的是：这不意味着那个队列中的其他区块ID将不会被降级。因为区块ID按区块被访问的顺序被置于队列中，所以图14的区块ID515-1是最长时间以前访问的(那个队列中的那些区块ID中的)区块ID，并因此将是失效的第一个区块ID。如果图14的区块ID 515-1被再次访问(并因此保持“热”)，则图14的区块ID515-1将被移动到队列的尾部，将另一区块ID留在队列的头部，并因此可能服从降级。If theexpiration time 1410 of FIG. 14 has not elapsed, the block ID 515-1 of FIG. 14 has not cooled down, and the block ID 515-1 of FIG. 14 may be left at the head of its queue. Note: this does not mean that other block IDs in that queue will not be demoted. Because chunk IDs are placed in the queue in the order in which chunks are accessed, chunk ID 515-1 of Figure 14 is the chunk ID (of those chunk IDs in that queue) that was accessed the longest time ago, and So will be the first block ID to expire. If block ID 515-1 of Figure 14 is accessed again (and thus remains "hot"), then block ID 515-1 of Figure 14 will be moved to the tail of the queue, leaving the other block ID at the head of the queue Ministry, and therefore may be subject to demotion.

图21A-图21B示出根据本发明构思的一个实施例的用于确定针对图5的写入命令505-1的流ID 530-1的示例过程的流程图。在图21A中，在块2105，图4的接收器405可从软件源接收写入命令505-1。在块2110，图5的LBA 510-1可从图5的写入命令505-1被读取。在块2115，图4的LBA映射器410可将图5的LBA 510-1映射到图5的区块ID 515-1。如上所述，图5的LBA映射器410可以以任何期望的方式来确定图5的区块ID 515-1：例如，通过从图5的LBA510-1遮蔽掉某些位，或者通过将图5的LBA 510-1除以图7的区块大小705。在块2120，图5的流选择逻辑415可将图5的流ID 530-1选择为用于图5的区块ID 515-1。如上所述，图5的流选择逻辑415可以以任何期望的方式进行操作：例如，通过从图3的区块流映射器340查找图5的流ID 530-1，通过从图8的访问计数810-1计算图5的流ID 530-1，通过以循环的方式分配装置流，或者任何其他期望的方法。在块2125，图4的流ID添加器420可将图5的流ID 530-1添加到图5的写入命令505-1。最后，在块2130，图5的写入命令505-1可由图1的SSD 120处理以执行指示的写入操作，其中，指示的写入操作可包括图4的发送器将图5的写入命令505-1发送到图1的SSD 120。21A-21B illustrate a flowchart of an example process for determining the stream ID 530-1 for the write command 505-1 of FIG. 5, according to one embodiment of the inventive concepts. In Figure 21A, atblock 2105, thereceiver 405 of Figure 4 may receive a write command 505-1 from a software source. Atblock 2110, the LBA 510-1 of FIG. 5 may be read from the write command 505-1 of FIG. 5 . Atblock 2115, theLBA mapper 410 of FIG. 4 may map the LBA 510-1 of FIG. 5 to the block ID 515-1 of FIG. 5 . As described above, theLBA mapper 410 of FIG. 5 may determine the block ID 515-1 of FIG. 5 in any desired manner: for example, by masking out certain bits from the LBA 510-1 of FIG. The LBA 510-1 is divided by theblock size 705 of Figure 7. Atblock 2120, thestream selection logic 415 of FIG. 5 may select the stream ID 530-1 of FIG. 5 as the block ID 515-1 of FIG. 5 . As described above, thestream selection logic 415 of FIG. 5 may operate in any desired manner: for example, by looking up the stream ID 530-1 of FIG. 5 from theblock stream mapper 340 of FIG. 3, by accessing counts from FIG. 810-1 computes the flow ID 530-1 of Figure 5, by allocating device flows in a round-robin fashion, or any other desired method. Atblock 2125, thestream ID adder 420 of FIG. 4 may add the stream ID 530-1 of FIG. 5 to the write command 505-1 of FIG. 5 . Finally, atblock 2130, the write command 505-1 of FIG. 5 may be processed by theSSD 120 of FIG. 1 to perform the indicated write operation, wherein the indicated write operation may include the transmitter of FIG. Command 505-1 is sent toSSD 120 of FIG. 1 .

此时，图5的写入命令505-1已经完全被处理。但仍可执行诸如更新分配给图5的区块ID 515-1的图5的流ID 530-1的其他处理。在块2135(图21B)，图4的排队器430可将图5的区块ID 515-1添加到图3的提交队列335以作进一步处理。在块2140，当图5的区块ID 515-1到达图3的提交队列335的头部时，可从图3的提交队列335去除图5的区块ID 515-1。最后，在块2145，图4的后台逻辑435可更新用于图5的区块ID 515-1的图5的流ID 530-1。下面参照图24和图25A-图25C对图4的后台逻辑435更新用于图5的区块ID 515-1的图5的流ID530-1的各种方法进行描述。At this point, the write command 505-1 of FIG. 5 has been completely processed. However, other processing such as updating the stream ID 530-1 of FIG. 5 assigned to the block ID 515-1 of FIG. 5 may still be performed. At block 2135 (FIG. 21B), thequeuer 430 of FIG. 4 may add the block ID 515-1 of FIG. 5 to thesubmission queue 335 of FIG. 3 for further processing. Atblock 2140, when the block ID 515-1 of FIG. 5 reaches the head of the commitqueue 335 of FIG. 3, the block ID 515-1 of FIG. 5 may be removed from the commitqueue 335 of FIG. Finally, atblock 2145, thebackground logic 435 of FIG. 4 may update the stream ID 530-1 of FIG. 5 for the block ID 515-1 of FIG. 5 . Various methods by which thebackground logic 435 of FIG. 4 updates the stream ID 530-1 of FIG. 5 for the block ID 515-1 of FIG. 5 are described below with reference to FIGS. 24 and 25A-25C.

图22示出根据本发明构思的一个实施例的图4的LBA映射器410将图5的LBA 510-1映射到图5的区块ID 515-1的示例过程的流程图。在图22中，在块2205，图4的LBA映射器410可使用图5的地址掩码525来从图5的LBA 510-1遮蔽掉位，留下图5的区块ID 515-1。可选地，在块2210，图4的LBA映射器410可通过将图5的LBA 510-1除以图7的区块大小705，来确定图5的区块ID 515-1。22 illustrates a flowchart of an example process for theLBA mapper 410 of FIG. 4 to map the LBA 510-1 of FIG. 5 to the block ID 515-1 of FIG. 5 according to one embodiment of the inventive concept. In FIG. 22, atblock 2205, theLBA mapper 410 of FIG. 4 may use theaddress mask 525 of FIG. 5 to mask out bits from the LBA 510-1 of FIG. 5, leaving the block ID 515-1 of FIG. Optionally, atblock 2210, theLBA mapper 410 of FIG. 4 may determine the block ID 515-1 of FIG. 5 by dividing the LBA 510-1 of FIG. 5 by theblock size 705 of FIG. 7 .

图23A-图23B示出根据本发明构思的第一实施例的用于使用顺序性逻辑确定针对图5的区块ID 515-1的图5的流ID 530-1的示例过程的流程图。在图23A中，在块2305，图4的流选择逻辑415可决定它是否正在对写入命令505-1至505-3中的顺序的LBA进行测试。例如，在使用多队列方法的本发明构思的实施例中，图4的流选择逻辑415可不考虑图5的写入命令505-1与较早写入命令是否是顺序的。如果图4的流选择逻辑415不是正在对顺序的写入命令进行测试，则在块2310，图4的流选择逻辑415可确定与图5的区块ID 515-1当前关联的图5的流ID 530-1：例如，通过从图3的区块-流映射器340访问图5的流ID 530-1。图4的流选择逻辑415如何确定图5的流ID 530-1的细节可依赖于图3的区块流映射器340如何被实现：如果区块流映射器340包括图8的SFR表805，则图4的流选择逻辑415可执行表查找；如果区块流映射器340包括图14的节点1405-1至节点1405-3，则图4的流选择逻辑415将不得不在确定图5的流ID 530-1之前搜索节点以找到图5的区块ID 515-1。23A-23B illustrate a flowchart of an example process for determining the stream ID 530-1 of FIG. 5 for the block ID 515-1 of FIG. 5 using sequential logic, according to a first embodiment of the inventive concept. In FIG. 23A, atblock 2305, thestream selection logic 415 of FIG. 4 may determine whether it is testing the sequential LBAs in write commands 505-1 through 505-3. For example, in an embodiment of the present inventive concept using a multi-queue approach, thestream selection logic 415 of FIG. 4 may not consider whether the write command 505-1 of FIG. 5 is sequential with the earlier write command. If thestream selection logic 415 of FIG. 4 is not testing the sequential write command, then atblock 2310 thestream selection logic 415 of FIG. 4 may determine the stream of FIG. 5 currently associated with the block ID 515-1 of FIG. 5 ID 530-1: For example, by accessing stream ID 530-1 of FIG. 5 from block-stream mapper 340 of FIG. 3 . The details of how thestream selection logic 415 of FIG. 4 determines the stream ID 530-1 of FIG. 5 may depend on how theblock stream mapper 340 of FIG. 3 is implemented: if theblock stream mapper 340 includes the SFR table 805 of FIG. 8, Thestream selection logic 415 of FIG. 4 may then perform a table lookup; if theblock stream mapper 340 includes nodes 1405-1 through 1405-3 of FIG. 14, then thestream selection logic 415 of FIG. The node is searched before ID 530-1 to find block ID 515-1 of FIG. 5 .

另一方面，如果图4的流选择逻辑415可正在对顺序的写入命令进行测试，则在块2315，图4的流选择逻辑415可识别具有图10的条目1020-1至条目1020-4的图10的窗口1015。在块2320，图4的流选择逻辑415可确定图5的LBA 510-1与针对图10的窗口1015中的图10的任何条目1020-1至条目1020-4的图10的结束LBA 1030是否是顺序的。如果图5的LBA510-1与针对图10的窗口1015中的图10的任何条目1020-1至条目1020-4的图10的结束LBA1030不是顺序的，则如上所述，在块2310，图4的流选择逻辑415可确定与图5的区块ID 515-1当前关联的图5的流ID 530-1。On the other hand, if thestream selection logic 415 of FIG. 4 may be testing sequential write commands, then atblock 2315 thestream selection logic 415 of FIG. 4 may identify entries having entries 1020-1 through 1020-4 of FIG. 10window 1015 of Figure 10. Atblock 2320, thestream selection logic 415 of FIG. 4 may determine whether the LBA 510-1 of FIG. 5 and theend LBA 1030 of FIG. 10 for any of the entries 1020-1 through 1020-4 of FIG. 10 in thewindow 1015 of FIG. is sequential. If the LBA 510-1 of FIG. 5 is not sequential with theend LBA 1030 of FIG. 10 for any of the entries 1020-1 to 1020-4 of FIG. 10 in thewindow 1015 of FIG. 10, then as described above, atblock 2310, FIG. 4 Thestream selection logic 415 of FIG. 5 may determine the stream ID 530-1 of FIG. 5 that is currently associated with the block ID 515-1 of FIG. 5 .

如果图4的流选择逻辑415可正在对顺序的写入命令进行测试，并且图5的LBA510-1与图10的窗口1015中的图10的任何条目1020-1至条目1020-4的图10的结束LBA 1030是顺序的，则在块2325(图23B)，图4的流选择逻辑415可确定分配给先前写入命令的图5的流ID 530-1。在块2125(图21A至图21B的一部分，并因此为了示出的目的而在图23B中以虚线示出)，分配给先前写入命令的图5的流ID 530-1可被分配给图5的写入命令505-1。在块2330，图4的流选择逻辑415可确定图10的条目1020-1至条目1020-8中是图10的窗口1015中的最旧的条目的条目。最后，在块2335，图4的流选择逻辑415可去除图10的窗口1015中的最旧的条目，并添加与图5的写入命令505-1对应的新的条目。图4的流选择逻辑415如何执行这个删除和添加的机制依赖于图10的窗口1015所使用的结构。如果图10的窗口1015存储具有图10的条目1020-1至条目1020的阵列或链表，则删除和添加可仅仅包含使用新的值来对最旧的条目进行覆写并更新指向阵列或链表的头部的指针。另一方面，使用图10的窗口1015的不同结构，删除和添加可包含删除和解分配针对最旧的条目的存储器对象以及为图5的写入命令505-1分配新的存储器对象。If thestream selection logic 415 of FIG. 4 may be testing sequential write commands, and the LBA 510-1 of FIG. 5 and any entry 1020-1 to entry 1020-4 of FIG. The end of theLBA 1030 is sequential, then at block 2325 (FIG. 23B), thestream selection logic 415 of FIG. 4 may determine the stream ID 530-1 of FIG. 5 assigned to the previous write command. At block 2125 (portion of FIGS. 21A-21B and therefore shown in dashed lines in FIG. 23B for illustration purposes), the stream ID 530-1 of FIG. 5 assigned to the previous write command may be assigned to the diagram 5 of the write command 505-1. Atblock 2330 , thestream selection logic 415 of FIG. 4 may determine the entry of the entries 1020 - 1 through 1020 - 8 of FIG. 10 that is the oldest entry in thewindow 1015 of FIG. 10 . Finally, atblock 2335,stream selection logic 415 of FIG. 4 may remove the oldest entry inwindow 1015 of FIG. 10 and add a new entry corresponding to write command 505-1 of FIG. The mechanism by whichstream selection logic 415 of FIG. 4 performs this deletion and addition depends on the structure used bywindow 1015 of FIG. 10 . Ifwindow 1015 of FIG. 10 stores an array or linked list with entries 1020-1 through 1020 of FIG. 10, deletion and addition may simply consist of overwriting the oldest entry with a new value and updating the pointer to the array or linked list. Head pointer. On the other hand, using a different structure ofwindow 1015 of FIG. 10, deletions and additions may include deleting and deallocating memory objects for the oldest entries and allocating new memory objects for write command 505-1 of FIG.

图24示出根据本发明构思的第一实施例的用于执行图8的SFR表805的后台更新的示例过程的流程图。在图24中，在块2405，图9的访问计数调节器905可(例如，使用增量器或ALU)增加图8的访问计数820-1。在块2410，图9的近因逻辑910可(例如，使用ALU)计算图11的近因权重1105。在块2415，图9的访问计数调节器905可(例如，使用ALU)将(在块2405中增加的)图8的访问计数820-1除以图11的近因权重1105。最后，在块2420，图9的流ID调节器920可确定与图5的区块ID 515-1关联的新的流ID。例如，图9的流ID调节器920使用ALU计算图12的调节的访问计数1205的对数。FIG. 24 illustrates a flowchart of an example process for performing background update of the SFR table 805 of FIG. 8 according to the first embodiment of the inventive concept. In FIG. 24, atblock 2405, theaccess count adjuster 905 of FIG. 9 may increment the access count 820-1 of FIG. 8 (eg, using an incrementer or ALU). Atblock 2410, therecency logic 910 of FIG. 9 may calculate therecency weights 1105 of FIG. 11 (eg, using the ALU). Atblock 2415, theaccess count adjuster 905 of FIG. 9 may divide the access count 820-1 of FIG. 8 (increased in block 2405) by therecency weight 1105 of FIG. 11 (eg, using the ALU). Finally, atblock 2420, theflow ID conditioner 920 of FIG. 9 may determine a new flow ID associated with the block ID 515-1 of FIG. 5 . For example, theflow ID conditioner 920 of FIG. 9 uses the ALU to calculate the logarithm of the adjustedaccess count 1205 of FIG. 12 .

图25A-图25C示出根据本发明构思的第二实施例的图14的节点1405-1的后台更新的示例过程的流程图。在图25A中，在块2505，图17的增量器1705可增加图14的访问计数820-1。在块2510，图17的区块失效逻辑1715可确定针对图14的区块ID 515-1的图14的失效时间1410。在块2515，图17的流ID调节器1710可确定针对图14的区块ID 515-1的图14的流ID 530-1。图17的流ID调节器1710可通过例如对来自图14的节点1405-1的图14的流ID530-1进行访问来确定图14的流ID 530-1。在块2520，图15的第二排队器1510可将图14的区块ID 515-1置于图15的队列1520-1至1520-3中的与图14的流ID 530-1对应的一个队列。25A-25C illustrate a flowchart of an example process for background update of the node 1405-1 of FIG. 14 according to the second embodiment of the inventive concept. In Figure 25A, atblock 2505, theincrementer 1705 of Figure 17 may increment the access count 820-1 of Figure 14. Atblock 2510 , theblock invalidation logic 1715 of FIG. 17 may determine theinvalidation time 1410 of FIG. 14 for block ID 515-1 of FIG. 14 . Atblock 2515, theflow ID conditioner 1710 of FIG. 17 may determine the flow ID 530-1 of FIG. 14 for the block ID 515-1 of FIG. 14 . Theflow ID conditioner 1710 of FIG. 17 may determine the flow ID 530-1 of FIG. 14 by, for example, accessing the flow ID 530-1 of FIG. 14 from the node 1405-1 of FIG. 14 . Atblock 2520, thesecond queuer 1510 of FIG. 15 may place the block ID 515-1 of FIG. 14 into one of the queues 1520-1 to 1520-3 of FIG. 15 corresponding to the flow ID 530-1 of FIG. 14 queue.

在块2525(图25B)，图17的最热区块逻辑1720可将针对图14的区块ID 515-1的图14的访问计数820-1与最热的区块的访问计数进行比较。如果针对图14的区块ID 515-1的图14的访问计数820-1大于最热的区块的访问计数，则图14的区块ID 515-1现在是最热的区块。所以，在块2530，图17的最热区块逻辑1720可将图14的区块ID 515-1识别为新的最热的区块；在块2535，图17的最热区块逻辑1720可将图19的装置寿命1905确定为图14的区块ID 515-1的两个最近访问之间的时间差。At block 2525 (FIG. 25B), thehottest block logic 1720 of FIG. 17 may compare the access count 820-1 of FIG. 14 for block ID 515-1 of FIG. 14 to the access count of the hottest block. If the access count 820-1 of FIG. 14 for block ID 515-1 of FIG. 14 is greater than the access count of the hottest block, then block ID 515-1 of FIG. 14 is now the hottest block. Therefore, atblock 2530, thehottest block logic 1720 of FIG. 17 may identify the block ID 515-1 of FIG. 14 as the new hottest block; atblock 2535, thehottest block logic 1720 of FIG. 17 may Thedevice lifetime 1905 of FIG. 19 is determined as the time difference between the two most recent accesses of the block ID 515-1 of FIG. 14 .

不管图14的区块ID 515-1是否是最热的区块，在块2540，图20的比较器2005可确定：当图14的区块ID 515-1在图15的队列1520-1至队列1520-3中的一个队列的头部时，图14的失效时间1410是否已经过去。如果没有，则图4的后台逻辑435可等待(在这期间做其他事情)，并在块2540再次检查，直到图14的区块ID 515-1的图14的失效时间1410已经过去为止。在那时，在块2545，图15的降级逻辑1525可从图15的队列1520-1至1520-3去除图14的区块ID 515-1。然后，在块2550，图20的减量器2010可减少图14的流ID 530-1。Regardless of whether the block ID 515-1 of FIG. 14 is the hottest block, atblock 2540, thecomparator 2005 of FIG. 20 may determine that when the block ID 515-1 of FIG. 14 is in the queue 1520-1 of FIG. 15 to Whether theexpiration time 1410 of FIG. 14 has elapsed when the head of one of the queues 1520-3 has passed. If not, thebackground logic 435 of FIG. 4 may wait (do other things in the meantime) and check again atblock 2540 until theexpiration time 1410 of FIG. 14 for block ID 515-1 of FIG. 14 has elapsed. At that time, atblock 2545, thedemotion logic 1525 of FIG. 15 may remove the block ID 515-1 of FIG. 14 from the queues 1520-1 through 1520-3 of FIG. 15. Then, atblock 2550, thedecrementer 2010 of FIG. 20 may decrement the flow ID 530-1 of FIG. 14 .

在块2555(图25C)，图15的第二排队器1510可将图14的区块ID 515-1置于图15的队列1520-1至1520-3中的与新的流ID对应的另一队列。在块2560，图15的降级逻辑1525可确定图14的区块ID 515-1是否是最热的区块。如果是这样，则在块2565，图15的降级逻辑1525可将另一区块ID选择作为新的最热的区块。例如，(在在块2560中减少之前)分配给图14的流ID 530-1的另一区块(诸如，在队列的头部或尾部的区块)可被选择。与之前一样，图15的降级逻辑1525还可基于选择的新的最热的区块来计算图19的装置寿命1905。At block 2555 (FIG. 25C), thesecond queuer 1510 of FIG. 15 may place the block ID 515-1 of FIG. 14 in another queue corresponding to the new flow ID in the queues 1520-1 through 1520-3 of FIG. 15 a queue. Atblock 2560, thedemotion logic 1525 of FIG. 15 may determine whether the block ID 515-1 of FIG. 14 is the hottest block. If so, atblock 2565, thedemotion logic 1525 of Figure 15 may select another block ID as the new hottest block. For example, another block assigned to flow ID 530-1 of Figure 14 (prior to reduction in block 2560), such as the block at the head or tail of the queue, may be selected. As before, thedegradation logic 1525 of FIG. 15 may also calculate thedevice lifetime 1905 of FIG. 19 based on the selected new hottest block.

在图21A至25C中，示出了本发明构思的一些实施例。但是本领域技术人员将认识到，通过改变块的顺序、通过省略块或通过包括附图中未示出的链接，本发明构思的其他实施例也是可行的。无论是否清楚地描述，流程图的全部这样的改变被认为是本发明构思的实施例。In Figures 21A to 25C, some embodiments of the inventive concept are shown. However, those skilled in the art will recognize that other embodiments of the inventive concept are possible by changing the order of the blocks, by omitting blocks, or by including links not shown in the figures. All such variations of the flowchart, whether explicitly described or not, are considered to be embodiments of the inventive concept.

下面的讨论意图提供对可实现本发明构思的特定方面的合适机器的简洁和总体描述。可通过来自传统输入装置(诸如，键盘、鼠标等)的输入以及从另一机器接收的指令、与虚拟现实(VR)环境的交互、生物反馈或其他输入信号，来至少部分地控制机器。如这里所使用的，术语“机器”意图宽泛地包含单个机器、虚拟机、或通信连接的机器、虚拟机或一起操作的装置的系统。示例性机器包括计算装置(诸如，个人计算机、工作站、服务器、便携式计算机、手持设备、电话、平板等)以及运输装置(诸如，私人或公共交通工具，例如，汽车、火车、出租车等)。The following discussion is intended to provide a brief and general description of a suitable machine in which certain aspects of the present inventive concept may be implemented. A machine may be controlled, at least in part, through input from conventional input devices such as a keyboard, mouse, etc., as well as instructions received from another machine, interaction with a virtual reality (VR) environment, biofeedback, or other input signals. As used herein, the term "machine" is intended to broadly encompass a single machine, a virtual machine, or a system of communicatively connected machines, virtual machines, or devices operating together. Exemplary machines include computing devices (such as personal computers, workstations, servers, portable computers, handheld devices, phones, tablets, etc.) and transportation devices (such as private or public transportation, eg, cars, trains, taxis, etc.).

机器可包括嵌入式控制器，诸如，可编程或非可编程逻辑器件或阵列、专用集成电路(ASIC)、嵌入式计算机、智能卡等。机器可诸如通过网络接口、调制解调器或其他通信连接来将一个或多个连接用于一个或多个远程装置。机器可通过物理和/或逻辑网络(诸如，内部网、因特网、局域网、广域网等)的方式互连。本领域技术人员将理解，网络通信可利用包括射频(RF)、卫星、微波、电气和电子工程师协会(IEEE)802.11、蓝牙、光学、红外、电缆、激光等的各种有线和/或无线短程或长程载波和协议。Machines may include embedded controllers, such as programmable or non-programmable logic devices or arrays, application specific integrated circuits (ASICs), embedded computers, smart cards, and the like. The machine may use one or more connections to one or more remote devices, such as through a network interface, modem, or other communication connection. Machines may be interconnected by means of physical and/or logical networks, such as intranets, the Internet, local area networks, wide area networks, and the like. Those skilled in the art will appreciate that network communications may utilize a variety of wired and/or wireless short-range, including radio frequency (RF), satellite, microwave, Institute of Electrical and Electronics Engineers (IEEE) 802.11, Bluetooth, optical, infrared, cable, laser, etc. or long-range carriers and protocols.

可通过参照或结合包括功能、过程、数据结构和应用程序等的相关联的数据来描述本发明构思的实施例，其中，相关联的数据在被机器访问时使得机器执行任务或限定抽象数据类型或低层硬件上下文。相关联的数据可存储在，例如，易失性和/或非易失性存储器(例如，RAM、ROM等)或者存储在其他存储装置和他们的相关联的存储介质中，其中，相关联的存储介质包括硬盘驱动器、软盘、光存储、磁带、闪存、存储棒、数字视频磁盘、生物存储等。相关联的数据可以以包、串行数据、并行数据、传播信号等的形式在包括物理和/或逻辑网络的传输环境上被传递，并可以以压缩或加密的格式来使用相关联的数据。相关联的数据可被用于分布式环境，并且被本地和/或远程地存储，以供机器访问。Embodiments of the inventive concepts may be described with reference to or in conjunction with associated data, including functions, procedures, data structures, applications, etc., that, when accessed by a machine, cause the machine to perform tasks or define abstract data types or low-level hardware context. The associated data may be stored, for example, in volatile and/or non-volatile memory (eg, RAM, ROM, etc.) or in other storage devices and their associated storage media, wherein the associated data Storage media include hard drives, floppy disks, optical storage, magnetic tapes, flash memory, memory sticks, digital video disks, biological storage, and the like. The associated data may be communicated over transmission environments including physical and/or logical networks in the form of packets, serial data, parallel data, propagated signals, etc., and may be used in a compressed or encrypted format. The associated data can be used in a distributed environment and stored locally and/or remotely for machine access.

本发明构思的实施例可包括有形的非暂时性机器可读介质，其中，有形的非暂时性机器可读介质包括一个或多个处理器可执行的指令，指令包括用于执行如这里描述的本发明构思的元素的指令。Embodiments of the present inventive concepts may include tangible, non-transitory machine-readable media including one or more processor-executable instructions including instructions for performing operations as described herein Instructions for elements of the inventive concept.

已经参照示出的实施例描述和示出了本发明构思的原理，将认识到：可在不脱离这样的原理的情况下在布置和细节上修改示出的实施例，并可以以任何期望的方式组合示出的实施例。此外，虽然前述讨论已经集中于特定实施例，但是其他配置被考虑。尤其，即使在这里使用诸如“根据本发明构思的实施例”等的表述，但是这些短语通常意味着参考实施例可能性，而不意图将本发明构思限制为特定实施例配置。如这里所使用，这些术语可参考可组合到其他实施例中的相同或不同的实施例。Having described and illustrated the principles of the inventive concept with reference to the illustrated embodiments, it will be recognized that the illustrated embodiments may be modified in arrangement and detail without departing from such principles, and may be arranged in any desired manner way to combine the illustrated embodiments. Additionally, while the foregoing discussion has focused on specific embodiments, other configurations are contemplated. In particular, even though expressions such as "embodiments according to the inventive concept" and the like are used herein, these phrases are generally meant to refer to embodiment possibilities and are not intended to limit the inventive concept to a particular embodiment configuration. As used herein, these terms may refer to the same or different embodiments that may be combined into other embodiments.

前述说明性的实施例不被解释为限制它们的发明构思。虽然已经描述了一些实施例，本领域技术人员将容易理解，在不实质地脱离本公开的新的教导和优点的情况下，可对那些实施例做出很多修改。因此，全部这样的修改意图包括在权利要求所限定的本发明构思的范围内。The foregoing illustrative embodiments are not to be construed as limiting their inventive concepts. Although a few embodiments have been described, those skilled in the art will readily appreciate that many modifications are possible in those embodiments without materially departing from the novel teachings and advantages of this disclosure. Accordingly, all such modifications are intended to be included within the scope of the inventive concept as defined by the appended claims.

在没有限制的情况下，本发明构思的实施例可延伸到下面的声明：Without limitation, embodiments of the inventive concept may extend to the following statement:

声明1：本发明构思的一个实施例包括一种固态驱动器(SSD)，所述SSD包括：Statement 1: One embodiment of the inventive concept includes a solid state drive (SSD) comprising:

闪存，用于存储数据；Flash memory, for storing data;

支持SSD中的多个装置流；Support multiple device streams in SSD;

SSD控制器，用于管理响应于多个写入命令而将数据写入到闪存，所述SSD控制器包括用于提交队列和区块流映射器的存储器；An SSD controller for managing writing of data to the flash memory in response to a plurality of write commands, the SSD controller including memory for a commit queue and a block stream mapper;

闪存转换层，包括：接收器，用于接收包括逻辑块地址(LBA)的写入命令；LBA映射器，用于将LBA映射到区块标识符(ID)；流选择逻辑，用于使用区块流映射器来基于区块ID选择流ID；流ID添加器，用于将流ID添加到所述写入命令；排队器，用于将区块ID置于提交队列中；后台逻辑，用于从提交队列去除区块ID并更新区块流映射器。Flash translation layer, including: receiver for receiving write commands including logical block address (LBA); LBA mapper for mapping LBA to block identifier (ID); stream selection logic for using area A block stream mapper to select a stream ID based on the block ID; a stream ID adder to add the stream ID to the write command; a queuer to place the block ID in the commit queue; background logic to use To remove the block ID from the commit queue and update the block stream mapper.

声明2：本发明构思的一个实施例包括根据声明1的SSD，所述SSD还包括：发送器，用于将具有流ID的所述写入命令发送到SSD。Statement 2: An embodiment of the inventive concept includes the SSD according to Statement 1, the SSD further comprising: a transmitter for transmitting the write command with a stream ID to the SSD.

声明3、本发明构思的一个实施例包括根据声明1的SSD，其中，LBA映射器包括：地址掩码，用于遮蔽LBA的部分以确定区块ID。Statement 3. One embodiment of the inventive concept includes the SSD of statement 1, wherein the LBA mapper includes an address mask to mask a portion of the LBA to determine the block ID.

声明4、本发明构思的一个实施例包括根据声明1的SSD，其中，LBA映射器包括：算术逻辑单元(ALU)，用于将LBA除以区块大小以识别区块ID。Statement 4. One embodiment of the inventive concept includes the SSD of statement 1, wherein the LBA mapper includes an arithmetic logic unit (ALU) for dividing the LBA by the block size to identify the block ID.

声明5、本发明构思的一个实施例包括根据声明1的SSD，其中，区块流映射器包括顺序性、频度、近因(SFR)表，所述SFR表包括区块ID和针对区块ID的流ID。Statement 5. One embodiment of the inventive concept includes the SSD according to statement 1, wherein the block stream mapper includes a sequentiality, frequency, recency (SFR) table, the SFR table including a block ID and a ID's stream ID.

声明6、本发明构思的一个实施例包括根据声明5的SSD，其中，后台逻辑包括：顺序性逻辑，用于如果LBA与先前写入命令的第二LBA是顺序的则选择先前流。Statement 6. One embodiment of the inventive concept includes the SSD of statement 5, wherein the background logic includes sequential logic to select a previous stream if the LBA is in sequence with a second LBA of the previous write command.

声明7、本发明构思的一个实施例包括根据声明6的SSD，其中，所述先前写入命令是在所述写入命令之前的窗口中，所述窗口包括窗口大小。Statement 7. One embodiment of the inventive concept includes the SSD of statement 6, wherein the previous write command is in a window preceding the write command, the window including a window size.

声明8、本发明构思的一个实施例包括根据声明7的SSD，其中，窗口大小响应于主机计算机系统中的处理器中的核的数量和运行在主机计算机系统中的处理器上的软件源的数量中的至少一个而被确定。Statement 8. One embodiment of the inventive concept includes the SSD of statement 7, wherein the window size is responsive to a number of cores in a processor in the host computer system and a source of software running on the processor in the host computer system at least one of the numbers is determined.

声明9、本发明构思的一个实施例包括根据声明7的SSD，其中，SSD控制器还包括用于具有包括所述先前写入命令的多个先前写入命令的队列的存储器，所述队列针对所述多个写入命令中的每个写入命令而包括结束LBA和相应的流ID。Statement 9. One embodiment of the inventive concept includes the SSD of statement 7, wherein the SSD controller further includes a memory for having a queue of a plurality of previous write commands including the previous write command, the queue for Each write command in the plurality of write commands includes an end LBA and a corresponding stream ID.

声明10、本发明构思的一个实施例包括根据声明5的SSD，其中，后台逻辑包括：Statement 10. One embodiment of the inventive concept includes the SSD of statement 5, wherein the background logic includes:

近因逻辑，用于基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；Recency logic for calculating recency weights based on the current access time for the block ID, the previous access time for the block ID, and the decay period;

访问计数调节器，用于基于近因权重调节针对区块ID的访问计数以产生调节的访问计数；an access count adjuster for adjusting the access count for the block ID based on the recency weight to produce an adjusted access count;

流ID调节器，用于基于针对区块ID的调节的访问计数来调节流ID。A flow ID adjuster to adjust the flow ID based on the adjusted access count for the block ID.

声明11、本发明构思的一个实施例包括根据声明10的SSD，其中，SFR表还包括针对区块ID的当前访问时间、针对区块ID的先前访问时间和针对区块ID的访问计数。Statement 11. One embodiment of the inventive concept includes the SSD of statement 10, wherein the SFR table further includes a current access time for the block ID, a previous access time for the block ID, and an access count for the block ID.

声明12、本发明构思的一个实施例包括根据声明10的SSD，其中，近因逻辑将近因权重计算为二的(将针对区块ID的当前访问时间与针对区块ID的先前访问时间之间的差除以衰减期)次幂。Statement 12. An embodiment of the present inventive concept includes the SSD according to statement 10, wherein the recency logic calculates the recency weight as a two-fold (between the current access time for the block ID and the previous access time for the block ID The difference is divided by the decay period) power.

声明13、本发明构思的一个实施例包括根据声明10的SSD，其中，访问时间调节器将针对区块ID的调节的访问计数计算为将(区块ID的访问计数加上1)除以近因权重。Statement 13. One embodiment of the present inventive concept includes the SSD of statement 10, wherein the access time adjuster calculates the adjusted access count for the block ID by dividing (the access count of the block ID plus 1) by the recency Weights.

声明14、本发明构思的一个实施例包括根据声明10的SSD，其中，流ID调节器将流ID计算为区块ID的调节的访问计数的对数。Statement 14. One embodiment of the inventive concept includes the SSD of statement 10, wherein the flow ID conditioner calculates the flow ID as the logarithm of the adjusted access count of the block ID.

声明15、本发明构思的一个实施例包括根据声明1的SSD，其中，区块流映射器包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。Statement 15. An embodiment of the inventive concept includes the SSD of statement 1, wherein the block flow mapper includes a node entry including a block ID and a flow ID for the block ID.

声明16、本发明构思的一个实施例包括根据声明15的SSD，其中，后台逻辑包括：Statement 16. One embodiment of the inventive concept includes the SSD of statement 15, wherein the background logic includes:

升级逻辑，用于基于区块ID确定何时将流ID升级；Upgrade logic to determine when to upgrade the stream ID based on the block ID;

第二排队器，用于响应于针对区块ID的流ID而将区块ID置于与多个流ID对应的多个队列中的第一队列；a second queuer for placing the block ID in a first queue of a plurality of queues corresponding to the plurality of flow IDs in response to the flow ID for the block ID;

降级逻辑，用于基于区块ID确定何时将流ID降级。Downgrade logic to determine when to downgrade the stream ID based on the block ID.

声明17、本发明构思的一个实施例包括根据声明16的SSD，其中，升级逻辑包括：Statement 17. One embodiment of the inventive concept includes the SSD of statement 16, wherein the upgrade logic includes:

增量器，用于增加针对区块ID的访问计数；Incrementer, used to increase the access count for the block ID;

流ID调节器，用于响应于针对区块ID的访问计数而确定流ID。A flow ID modifier for determining a flow ID in response to an access count for the block ID.

声明18、本发明构思的一个实施例包括根据声明17的SSD，其中，流ID调节器进行操作来将流ID确定为针对区块ID的访问计数的对数。Statement 18. One embodiment of the inventive concept includes the SSD of statement 17, wherein the stream ID conditioner operates to determine the stream ID as the logarithm of the access count for the block ID.

声明19、本发明构思的一个实施例包括根据声明17的SSD，其中，升级逻辑还包括：区块失效逻辑，用于计算针对区块ID的失效时间。Statement 19. An embodiment of the present inventive concept includes the SSD of statement 17, wherein the upgrade logic further includes block invalidation logic to calculate the invalidation time for the block ID.

声明20、本发明构思的一个实施例包括根据声明19的SSD，其中，区块失效逻辑进行操作来将针对区块ID的失效时间计算为针对区块ID的访问计数和装置寿命之和。Statement 20. One embodiment of the inventive concept includes the SSD of statement 19, wherein the block invalidation logic operates to calculate the invalidation time for the block ID as the sum of the access count and the device lifetime for the block ID.

声明21、本发明构思的一个实施例包括根据声明20的SSD，其中，装置寿命是最热的区块的最后访问时间和最热的块的先前访问时间之差。Statement 21. An embodiment of the inventive concept includes the SSD of statement 20, wherein the device lifetime is the difference between the last access time of the hottest block and the previous access time of the hottest block.

声明22、本发明构思的一个实施例包括根据声明21的SSD，其中，升级逻辑还包括：最热区块逻辑，如果区块ID的访问计数大于最热的区块的最后访问时间，则将区块ID确定为最热的区块。Statement 22. An embodiment of the inventive concept includes the SSD according to statement 21, wherein the upgrade logic further includes: hottest block logic, if the access count of the block ID is greater than the last access time of the hottest block, then The block ID is determined as the hottest block.

声明23、本发明构思的一个实施例包括根据声明21的SSD，其中，节点条目还包括针对区块ID的访问时间和针对区块ID的失效时间。Statement 23. One embodiment of the inventive concept includes the SSD of statement 21, wherein the node entry further includes an access time for the block ID and an expiration time for the block ID.

声明24、本发明构思的一个实施例包括根据声明16的SSD，其中：Statement 24. An embodiment of the inventive concept includes the SSD of statement 16, wherein:

降级逻辑包括比较器和减量器，其中，比较器用于确定针对区块ID的失效时间是否已经过去，如果针对区块ID的失效时间已经过去，则减量器用于减少流ID；The de-escalation logic includes a comparator and a decrementer, wherein the comparator is used to determine whether the expiration time for the block ID has passed, and the decrementer is used to reduce the flow ID if the expiration time for the block ID has passed;

第二排队器进行操作来响应于针对区块ID的减少的流ID而将区块ID置于与所述多个流ID对应的所述多个队列中的第二队列。The second queuer operates to place the block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs in response to the reduced flow ID for the block ID.

声明25、本发明构思的一个实施例包括根据声明24的SSD，其中，降级逻辑进行操作来：当区块ID在所述多个队列中的第一队列的头部时，基于区块ID确定何时将流ID降级。Statement 25. One embodiment of the inventive concept includes the SSD of statement 24, wherein the demotion logic operates to: determine based on the block ID when the block ID is at the head of a first queue of the plurality of queues When to downgrade the stream ID.

声明26、本发明构思的一个实施例包括根据声明24的SSD，其中，降级逻辑进行操作来：如果区块ID在所述多个队列中的第一队列的头部，则基于区块ID确定何时将流ID降级。Statement 26. One embodiment of the inventive concept includes the SSD of statement 24, wherein the demotion logic operates to: determine based on the block ID if the block ID is at the head of a first queue of the plurality of queues When to downgrade the stream ID.

声明27、本发明构思的一个实施例包括用在计算机系统中的驱动器，所述驱动器包括：Statement 27. One embodiment of the inventive concept includes a driver for use in a computer system, the driver comprising:

接收器，用于接收针对固态驱动器(SSD)的写入命令，所述写入命令包括逻辑块地址(LBA)；a receiver for receiving a write command for a solid state drive (SSD), the write command including a logical block address (LBA);

LBA映射器，用于将LBA映射到区块标识符(ID)；LBA mapper for mapping LBAs to block identifiers (IDs);

流选择逻辑，用于使用存储在主机计算机系统中的存储器中的区块流映射器，来基于区块ID选择流ID；stream selection logic for selecting stream IDs based on the block IDs using a block stream mapper stored in memory in the host computer system;

流ID添加器，用于将流ID添加到所述写入命令；a stream ID adder for adding a stream ID to the write command;

排队器，用于将区块ID置于存储在存储器中的提交队列中；a queuer for placing block IDs in a commit queue stored in memory;

后台逻辑，用于从提交队列去除区块ID并更新区块流映射器。Background logic to remove block IDs from the commit queue and update the block stream mapper.

声明28、本发明构思的一个实施例包括根据声明27的驱动器，还包括：发送器，用于将具有流ID的所述写入命令发送到SSD。Statement 28. An embodiment of the inventive concept includes the drive according to statement 27, further comprising a transmitter for transmitting the write command with the stream ID to the SSD.

声明29、本发明构思的一个实施例包括根据声明27的驱动器，其中，LBA映射器包括：地址掩码，用于遮蔽LBA的部分以识别区块ID。Statement 29. An embodiment of the inventive concept includes the driver of statement 27, wherein the LBA mapper includes an address mask for masking portions of the LBA to identify the block ID.

声明30、本发明构思的一个实施例包括根据声明27的驱动器，其中，LBA映射器包括：算术逻辑单元(ALU)，用于将LBA除以区块大小以识别区块。Statement 30. One embodiment of the inventive concept includes the drive of statement 27, wherein the LBA mapper includes an arithmetic logic unit (ALU) for dividing the LBA by the block size to identify the block.

声明31、本发明构思的一个实施例包括根据声明27的驱动器，其中，区块流映射器包括顺序性、频度、近因(SFR)表，所述SFR表包括区块ID和针对区块ID的流ID。Statement 31. One embodiment of the present inventive concept includes the driver of statement 27, wherein the block stream mapper includes a sequential, frequent, recency (SFR) table, the SFR table including a block ID and a ID's stream ID.

声明32、本发明构思的一个实施例包括根据声明31的驱动器，其中，后台逻辑包括：顺序性逻辑，如果LBA与先前写入命令的第二LBA是顺序的则选择先前流。Statement 32. One embodiment of the inventive concept includes the driver of statement 31, wherein the background logic includes sequential logic to select the previous stream if the LBA is in sequence with the second LBA of the previous write command.

声明33、本发明构思的一个实施例包括根据声明32的驱动器，其中，所述先前写入命令是在所述写入命令之前的窗口中，所述窗口包括窗口大小。Statement 33. One embodiment of the inventive concept includes the drive of statement 32, wherein the previous write command is in a window prior to the write command, the window including a window size.

声明34、本发明构思的一个实施例包括根据声明33的驱动器，其中，窗口大小响应于主机计算机系统中的处理器中的核的数量和运行在主机计算机系统中的处理器上的软件源的数量中的至少一个而被确定。Statement 34. One embodiment of the inventive concept includes the driver of statement 33, wherein the window size is responsive to a number of cores in a processor in the host computer system and a source of software running on the processor in the host computer system at least one of the numbers is determined.

声明35、本发明构思的一个实施例包括根据声明31的驱动器，其中，后台逻辑包括：Statement 35. One embodiment of the inventive concept includes the driver of statement 31, wherein the background logic includes:

近因逻辑，用于基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；Recency logic for calculating recency weights based on the current access time for the block ID, the previous access time for the block ID, and the decay period;

访问计数调节器，用于基于近因权重调节针对区块ID的访问计数以产生调节的访问计数；an access count adjuster for adjusting the access count for the block ID based on the recency weight to produce an adjusted access count;

流ID调节器，用于基于针对区块ID的调节的访问计数来调节流ID。A flow ID adjuster to adjust the flow ID based on the adjusted access count for the block ID.

声明36、本发明构思的一个实施例包括根据声明35的驱动器，其中，SFR表还包括针对区块ID的当前访问时间、针对区块ID的先前访问时间和针对区块ID的访问计数。Statement 36. One embodiment of the inventive concept includes the drive of statement 35, wherein the SFR table further includes a current access time for the block ID, a previous access time for the block ID, and an access count for the block ID.

声明37、本发明构思的一个实施例包括根据声明35的驱动器，其中，近因逻辑将近因权重计算为二的(将针对区块ID的当前访问时间与针对区块ID的先前访问时间之差除以衰减期)次幂。Statement 37. An embodiment of the present inventive concept includes the driver according to statement 35, wherein the recency logic calculates the recency weight as two (the difference between the current access time for the block ID and the previous access time for the block ID divided by the decay period) power.

声明38、本发明构思的一个实施例包括根据声明35的驱动器，其中，访问时间调节器将针对区块ID的调节的访问计数计算为(区块ID的访问计数加上1)除以近因权重。Statement 38. An embodiment of the inventive concept includes the drive of statement 35, wherein the access time adjuster calculates the adjusted access count for the block ID as (the access count of the block ID plus 1) divided by the recency weight .

声明39、本发明构思的一个实施例包括根据声明35的驱动器，其中，流ID调节器将流ID计算为针对区块ID的调节的访问计数的对数。Statement 39. One embodiment of the inventive concept includes the driver of statement 35, wherein the flow ID conditioner calculates the flow ID as the logarithm of the adjusted access count for the block ID.

声明40、本发明构思的一个实施例包括根据声明27的驱动器，其中，区块流映射器包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。Statement 40. One embodiment of the inventive concept includes the driver of statement 27, wherein the block flow mapper includes a node entry including a block ID and a flow ID for the block ID.

声明41、本发明构思的一个实施例包括根据声明40的驱动器，其中，后台逻辑包括：Statement 41. One embodiment of the inventive concept includes the driver of statement 40, wherein the background logic includes:

升级逻辑，用于基于区块ID确定何时将流ID升级；Upgrade logic to determine when to upgrade the stream ID based on the block ID;

第二排队器，用于响应于针对区块ID的流ID而将区块ID置于与多个流ID对应的多个队列中的第一队列；a second queuer for placing the block ID in a first queue of a plurality of queues corresponding to the plurality of flow IDs in response to the flow ID for the block ID;

降级逻辑，用于基于区块ID确定何时将流ID降级。Downgrade logic to determine when to downgrade the stream ID based on the block ID.

声明42、本发明构思的一个实施例包括根据声明41的驱动器，其中，升级逻辑包括：Statement 42. One embodiment of the inventive concept includes the driver of statement 41, wherein the upgrade logic includes:

增量器，用于增加针对区块ID的访问计数；Incrementer, used to increase the access count for the block ID;

流ID调节器，用于响应于针对区块ID的访问计数而确定流ID。A flow ID modifier for determining a flow ID in response to an access count for the block ID.

声明43、本发明构思的一个实施例包括根据声明42的驱动器，其中，流ID调节器进行操作来将流ID确定为针对区块ID的访问计数的对数。Statement 43. One embodiment of the inventive concept includes the driver of statement 42, wherein the flow ID conditioner operates to determine the flow ID as the logarithm of the access count for the block ID.

声明44、本发明构思的一个实施例包括根据声明42的驱动器，其中，升级逻辑还包括：区块失效逻辑，用于计算针对区块ID的失效时间。Statement 44. An embodiment of the present inventive concept includes the driver of statement 42, wherein the upgrade logic further includes block invalidation logic to calculate the invalidation time for the block ID.

声明45、本发明构思的一个实施例包括根据声明44的驱动器，其中，区块失效逻辑进行操作来将针对区块ID的失效时间计算为针对区块ID的访问计数和装置寿命之和。Statement 45. One embodiment of the inventive concept includes the driver of statement 44, wherein the block invalidation logic is operative to calculate the invalidation time for the block ID as the sum of the access count and the device lifetime for the block ID.

声明46、本发明构思的一个实施例包括根据声明45的驱动器，其中，装置寿命是最热的区块的最后访问时间和最热的块的先前访问时间之差。Statement 46. An embodiment of the inventive concept includes the drive of statement 45, wherein the device lifetime is the difference between the last access time of the hottest block and the previous access time of the hottest block.

声明47、本发明构思的一个实施例包括根据声明46的驱动器，其中，升级逻辑还包括：最热区块逻辑，如果针对区块ID的访问计数大于最热的区块的最后访问时间，则将区块ID确定为最热的区块。Statement 47. An embodiment of the present inventive concept includes the drive of statement 46, wherein the upgrade logic further comprises: hottest block logic, if the access count for the block ID is greater than the last access time of the hottest block, then Identify the block ID as the hottest block.

声明48、本发明构思的一个实施例包括根据声明46的驱动器，其中，节点条目还包括针对区块ID的访问时间和针对区块ID的失效时间。Statement 48. One embodiment of the inventive concept includes the driver of statement 46, wherein the node entry further includes an access time for the block ID and an expiration time for the block ID.

声明49、本发明构思的一个实施例包括根据声明41的驱动器，其中，Statement 49. An embodiment of the inventive concept includes the drive of statement 41, wherein,

降级逻辑包括比较器和减量器，其中，比较器用于确定针对区块ID的失效时间是否已经过去，如果区块ID的失效时间已经过去，则减量器减少流ID；The de-escalation logic includes a comparator and a decrementer, wherein the comparator is used to determine whether the expiration time for the block ID has elapsed, and the decrementor decrements the flow ID if the expiration time for the block ID has elapsed;

第二排队器进行操作来响应于针对区块ID的减少的流ID而将区块ID置于与所述多个流ID对应的所述多个队列中的第二队列。The second queuer operates to place the block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs in response to the reduced flow ID for the block ID.

声明50、本发明构思的一个实施例包括根据声明49的驱动器，其中，降级逻辑进行操作来：当区块ID在所述多个队列中的第一队列的头部时，基于区块ID确定何时将流ID降级。Statement 50. One embodiment of the inventive concept includes the driver of statement 49, wherein the demotion logic operates to: determine based on the block ID when the block ID is at the head of a first queue of the plurality of queues When to downgrade the stream ID.

声明51、本发明构思的一个实施例包括根据声明49的驱动器，其中，降级逻辑进行操作来：如果区块ID在所述多个队列中的第一队列的头部，则基于区块ID确定何时将流ID降级。Statement 51. One embodiment of the inventive concept includes the driver of statement 49, wherein the demotion logic operates to: determine based on the block ID if the block ID is at the head of a first queue of the plurality of queues When to downgrade the stream ID.

声明52、本发明构思的一个实施例包括一种方法，所述方法包括：Statement 52. One embodiment of the inventive concept includes a method comprising:

从软件源接收写入命令；receive a write command from a software source;

确定所述写入命令中的逻辑块地址(LBA)；determining the logical block address (LBA) in the write command;

识别包括LBA的固态驱动器(SSD)上的针对区块的区块标识符(ID)；Identifying a block identifier (ID) for a block on a solid state drive (SSD) that includes an LBA;

访问与区块ID关联的流ID；access the stream ID associated with the block ID;

将流ID分配给写入命令；assign a stream ID to the write command;

在SSD上使用分配的流ID处理写入命令；Process write commands on the SSD with the assigned stream ID;

执行与区块ID关联的流ID的后台更新。Perform a background update of the stream ID associated with the block ID.

声明53、本发明构思的一个实施例包括根据声明52的方法，其中，所述方法被实现在在主机计算机系统上的文件系统层、块层或装置驱动器层中的一个层中。Statement 53. One embodiment of the inventive concept includes the method of statement 52, wherein the method is implemented in one of a file system layer, a block layer, or a device driver layer on a host computer system.

声明54、本发明构思的一个实施例包括根据声明52的方法，其中，所述方法被实现在SSD的闪存转换层中。Statement 54. An embodiment of the inventive concept includes the method of statement 52, wherein the method is implemented in a flash translation layer of an SSD.

声明55、本发明构思的一个实施例包括根据声明52的方法，其中，识别包括LBA的固态驱动器(SSD)上的针对区块的区块标识符(ID)的步骤包括：使用LBA上的地址掩码来识别区块ID。Statement 55. One embodiment of the inventive concept includes the method of statement 52, wherein the step of identifying a block identifier (ID) for a block on a solid state drive (SSD) that includes the LBA includes using the address on the LBA mask to identify the block ID.

声明56、本发明构思的一个实施例包括根据声明52的方法，其中，识别包括LBA的固态驱动器(SSD)上的针对区块的区块标识符ID的步骤包括：通过将LBA除以为区块中的区段的数量。Statement 56. One embodiment of the inventive concept includes the method of statement 52, wherein the step of identifying a block identifier ID for a block on a solid state drive (SSD) that includes an LBA comprises: by dividing the LBA into the block The number of segments in .

声明57、本发明构思的一个实施例包括根据声明52的方法，其中，将流ID分配给写入命令的步骤包括将流ID作为标签添加到所述写入命令。Statement 57. One embodiment of the inventive concept includes the method of statement 52, wherein the step of assigning a stream ID to a write command includes adding the stream ID as a tag to the write command.

声明58、本发明构思的一个实施例包括根据声明52的方法，还包括：Statement 58. One embodiment of the inventive concept includes the method according to statement 52, further comprising:

确定逻辑块地址与第二写入命令中的第二LBA是否是顺序的；determining whether the logical block address is sequential with the second LBA in the second write command;

如果逻辑块地址与第二写入命令中的第二LBA是顺序的，则：If the logical block address is sequential with the second LBA in the second write command, then:

确定分配给第二写入命令的第二流ID；determining a second stream ID assigned to the second write command;

将第二流ID分配给所述写入命令。A second stream ID is assigned to the write command.

声明59、本发明构思的一个实施例包括根据声明58的方法，其中，第二写入命令是在所述写入命令之前的窗口中。Statement 59. An embodiment of the inventive concept includes the method of statement 58, wherein the second write command is in a window preceding the write command.

声明60、本发明构思的一个实施例包括根据声明59的方法，还包括：识别窗口。Statement 60. An embodiment of the inventive concept includes the method of statement 59, further comprising: identifying a window.

声明61、本发明构思的一个实施例包括根据声明60的方法，其中，识别窗口的步骤包括：响应于包括SSD的主机计算机系统中的处理器中的核的数量和运行在包括SSD的主机计算机系统中的处理器上的软件源的数量中的至少一个而确定窗口的窗口大小。Statement 61. One embodiment of the present inventive concept includes the method of statement 60, wherein the step of identifying a window comprises: responsive to a number of cores in a processor in a host computer system including an SSD and a host computer running on the host computer including the SSD The window size of the window is determined by at least one of the number of software sources on the processors in the system.

声明62、本发明构思的一个实施例包括根据声明59的方法，还包括：Statement 62. An embodiment of the inventive concept includes the method according to statement 59, further comprising:

识别窗口中的最旧的写入命令；Identify the oldest write command in the window;

使用所述写入命令替换窗口中的最旧的写入命令。Replace the oldest write command in the window with the write command.

声明63、本发明构思的一个实施例包括根据声明52的方法，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 63. An embodiment of the present inventive concept includes the method according to statement 52, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

将区块ID添加到提交队列；Add the block ID to the commit queue;

当区块ID在提交队列的头部时，从提交队列去除区块ID。When the block ID is at the head of the commit queue, remove the block ID from the commit queue.

声明64、本发明构思的一个实施例包括根据声明52的方法，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 64. One embodiment of the present inventive concept includes the method according to statement 52, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

增加针对区块ID的访问计数；Increase the access count for the block ID;

响应于针对区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重；calculating a recency weight for the block ID in response to the current access time and the previous access time for the block ID;

响应于近因权重而更新针对区块ID的访问计数；update the access count for the block ID in response to the recency weight;

响应于更新的访问计数而确定针对区块ID的流ID。The stream ID for the block ID is determined in response to the updated access count.

声明65、本发明构思的一个实施例包括根据声明64的方法，其中，响应于针对区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重的步骤包括：将近因权重计算为二的(将针对区块ID的当前访问时间与区块ID的先前访问时间之差除以衰减期)次幂。Statement 65. One embodiment of the inventive concept includes the method of statement 64, wherein the step of calculating a recency weight for a block ID in response to a current access time and a previous access time for the block ID comprises: a recency weight Calculated as a power of two (the difference between the current access time for the block ID and the previous access time for the block ID divided by the decay period) power.

声明66、本发明构思的一个实施例包括根据声明65的方法，其中，响应于近因权重而更新针对区块ID的访问计数的步骤包括：将访问计数除以近因权重。Statement 66. One embodiment of the inventive concept includes the method of statement 65, wherein updating the access count for the block ID in response to the recency weight includes dividing the access count by the recency weight.

声明67、本发明构思的一个实施例包括根据声明64的方法，其中，响应于更新的访问计数而确定区块ID的流ID的步骤包括：将针对区块ID的流ID计算为更新的访问计数的对数。Statement 67. One embodiment of the inventive concept includes the method of statement 64, wherein the step of determining the flow ID for the block ID in response to the updated access count comprises: calculating the flow ID for the block ID as the updated access The logarithm of the count.

声明68、本发明构思的一个实施例包括根据声明52的方法，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 68. One embodiment of the inventive concept includes the method according to statement 52, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

将区块ID置于与流ID对应的队列中，其中，与流ID对应的队列是多个队列中的一个；Place the block ID in the queue corresponding to the flow ID, wherein the queue corresponding to the flow ID is one of multiple queues;

当区块ID到达队列的头部时，确定是否将区块ID降级。When the block ID reaches the head of the queue, determine whether to demote the block ID.

声明69、本发明构思的一个实施例包括根据声明68的方法，其中，将区块ID置于与流ID对应的队列中的步骤包括：Statement 69. One embodiment of the inventive concept includes the method according to statement 68, wherein the step of placing the block ID in the queue corresponding to the stream ID comprises:

增加针对区块ID的访问计数；Increase the access count for the block ID;

响应于针对区块ID的访问计数而确定针对区块ID的流ID。The stream ID for the tile ID is determined in response to the access count for the tile ID.

声明70、本发明构思的一个实施例包括根据声明69的方法，其中，响应于针对区块ID的访问计数而确定针对区块ID的流ID的步骤包括：将针对区块ID的流ID计算为针对区块ID的访问计数的对数。Statement 70. One embodiment of the inventive concept includes the method of statement 69, wherein the step of determining the flow ID for the tile ID in response to the access count for the tile ID comprises: computing the flow ID for the tile ID is the logarithm of the access count for the block ID.

声明71、本发明构思的一个实施例包括根据声明69的方法，其中，将区块ID置于与流ID对应的队列中的步骤还包括：如果区块ID的访问计数超过最热的区块的第二访问计数，则将区块ID确定为新的最热的区块。Statement 71. An embodiment of the inventive concept includes the method according to statement 69, wherein the step of placing the block ID in the queue corresponding to the stream ID further comprises: if the access count of the block ID exceeds the hottest block , the block ID is determined as the new hottest block.

声明72、本发明构思的一个实施例包括根据声明71的方法，其中，将区块ID识别为新的最热的区块的步骤包括：将装置寿命确定为针对区块ID的当前访问时间与针对区块ID的先前访问时间之差。Statement 72. One embodiment of the present inventive concept includes the method of statement 71, wherein the step of identifying the block ID as the new hottest block comprises: determining the device age as the current access time for the block ID and the Difference between previous access times for the block ID.

声明73、本发明构思的一个实施例包括根据声明68的方法，其中：Statement 73. An embodiment of the inventive concept includes the method according to statement 68, wherein:

执行与区块ID关联的流ID的后台更新的步骤还包括：响应于访问计数和装置寿命而确定针对区块ID的失效时间；The step of performing a background update of the stream ID associated with the block ID further comprises: determining an expiration time for the block ID in response to the access count and device age;

当区块ID到达队列的头部时确定是否将区块ID降级的步骤包括：如果区块ID的失效时间已经过去，则：从与流ID对应的队列去除区块ID；减少流ID；将区块ID置于与减少的流ID对应的第二队列中。The step of determining whether to downgrade the block ID when the block ID reaches the head of the queue includes: if the expiration time of the block ID has elapsed, then: remove the block ID from the queue corresponding to the flow ID; reduce the flow ID; The block ID is placed in the second queue corresponding to the reduced stream ID.

声明74、本发明构思的一个实施例包括根据声明73的方法，其中，响应于访问计数和装置寿命而确定针对区块ID的失效时间的步骤包括：将装置寿命确定为最热的区块的最后访问时间与最热的区块的先前访问时间之差。Statement 74. An embodiment of the inventive concept includes the method of statement 73, wherein the step of determining the expiration time for the block ID in response to the access count and the device age comprises: determining the device age as the hottest block's The difference between the last access time and the previous access time of the hottest block.

声明75、本发明构思的一个实施例包括根据声明73的方法，其中，当区块ID到达队列的头部时确定是否将区块ID降级的步骤还包括：如果区块ID的失效时间已经过去，并且如果区块ID是最热的区块，则将与流ID对应的队列中的第二区块ID选择作为新的最热的区块。Statement 75. An embodiment of the present inventive concept includes the method according to statement 73, wherein the step of determining whether to downgrade the block ID when the block ID reaches the head of the queue further comprises: if the block ID's expiration time has elapsed , and if the block ID is the hottest block, the second block ID in the queue corresponding to the stream ID is selected as the new hottest block.

声明76、本发明构思的一个实施例包括一种包含非暂时性存储介质的物品，所述非暂时性存储介质具有存储在其上的指令，所述指令当被机器执行时使得：Statement 76. One embodiment of the present inventive concept includes an article comprising a non-transitory storage medium having instructions stored thereon that, when executed by a machine, cause:

从软件源接收写入命令；receive a write command from a software source;

确定所述写入命令中的逻辑块地址(LBA)；determining the logical block address (LBA) in the write command;

确定包括LBA的固态驱动器(SSD)上的针对区块的区块标识符(ID)；determining the block identifier (ID) for the block on the solid state drive (SSD) that includes the LBA;

访问与区块ID关联的流ID；access the stream ID associated with the block ID;

将流ID分配给写入命令；assign a stream ID to the write command;

在SSD上使用分配的流ID处理写入命令；Process write commands on the SSD with the assigned stream ID;

执行与区块ID关联的流ID的后台更新。Perform a background update of the stream ID associated with the block ID.

声明77、本发明构思的一个实施例包括根据声明76的物品，其中，所述方法被实现在在主机计算机系统上的文件系统层、块层或装置驱动器层中的一个中。Statement 77. An embodiment of the present inventive concept includes the article of statement 76, wherein the method is implemented in one of a file system layer, a block layer, or a device driver layer on a host computer system.

声明78、本发明构思的一个实施例包括根据声明76的物品，其中，所述方法被实现在SSD的闪存转换层中。Statement 78. An embodiment of the present inventive concept includes the article of statement 76, wherein the method is implemented in a flash translation layer of an SSD.

声明79、本发明构思的一个实施例包括根据声明76的物品，其中，识别包括LBA的固态驱动器(SSD)上的针对区块的区块标识符ID的步骤包括：使用LBA上的地址掩码来识别区块ID。Statement 79. An embodiment of the present inventive concept includes the article of statement 76, wherein the step of identifying a block identifier ID for a block on a solid state drive (SSD) that includes an LBA includes using an address mask on the LBA to identify the block ID.

声明80、本发明构思的一个实施例包括根据声明76的物品，其中，识别包括LBA的固态驱动器(SSD)上的用于区块的区块标识符ID的步骤包括：通过将LBA除以区块中的区段的数量。Statement 80. One embodiment of the present inventive concept includes the article of statement 76, wherein the step of identifying a block identifier ID for a block on a solid state drive (SSD) that includes an LBA comprises: by dividing the LBA by the area The number of extents in the block.

声明81、本发明构思的一个实施例包括根据声明76的物品，其中，将流ID分配给写入命令的步骤包括将流ID作为标签添加到所述写入命令。Statement 81. An embodiment of the present inventive concept includes the article of statement 76, wherein the step of assigning a stream ID to a write command includes adding the stream ID as a tag to the write command.

声明82、本发明构思的一个实施例包括根据声明76的物品，所述非暂时性存储介质具有存储在其上的另外指令，所述另外指令当被机器执行时使得：Statement 82. An embodiment of the present inventive concept includes the article according to statement 76, the non-transitory storage medium having stored thereon further instructions that, when executed by a machine, cause:

确定逻辑块地址与第二写入命令中的第二LBA是否是顺序的；determining whether the logical block address is sequential with the second LBA in the second write command;

如果逻辑块地址与第二写入命令中的第二LBA是顺序的，则：确定分配给第二写入命令的第二流ID；将第二流ID分配给所述写入命令。If the logical block address is sequential with the second LBA in the second write command, then: determine the second stream ID assigned to the second write command; assign the second stream ID to the write command.

声明83、本发明构思的一个实施例包括根据声明82的物品，其中，第二写入命令是在所述写入命令之前的窗口中。Statement 83. An embodiment of the present inventive concept includes the article of statement 82, wherein the second write command is in a window preceding the write command.

声明84、本发明构思的一个实施例包括根据声明83的物品，所述非暂时性存储介质具有存储在其上的另外指令，所述另外指令当被机器执行时使得：确定窗口。Statement 84. An embodiment of the present inventive concept includes the article according to statement 83, the non-transitory storage medium having stored thereon further instructions that, when executed by a machine, cause: a window to be determined.

声明85、本发明构思的一个实施例包括根据声明84的物品，其中，确定窗口的步骤包括：响应于包括SSD的主机计算机系统中的处理器中的核的数量和运行在包括SSD的主机计算机系统中的处理器上的软件源的数量中的至少一个而确定窗口的窗口大小。Statement 85. An embodiment of the present inventive concept includes the article of statement 84, wherein the step of determining the window comprises: responsive to a number of cores in a processor in a host computer system including an SSD and running on a host computer including an SSD The window size of the window is determined by at least one of the number of software sources on the processors in the system.

声明86、本发明构思的一个实施例包括根据声明83的物品，所述非暂时性存储介质具有存储在其上的另外指令，所述另外指令当被机器执行时使得：Statement 86. An embodiment of the present inventive concept includes the article according to statement 83, the non-transitory storage medium having stored thereon further instructions that, when executed by a machine, cause:

识别窗口中的最旧的写入命令；Identify the oldest write command in the window;

使用所述写入命令替换窗口中的最旧的写入命令。Replace the oldest write command in the window with the write command.

声明87、本发明构思的一个实施例包括根据声明76的物品，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 87. An embodiment of the present inventive concept includes the article according to statement 76, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

将区块ID添加到提交队列；Add the block ID to the commit queue;

当区块ID在提交队列的头部时，从提交队列去除区块ID。When the block ID is at the head of the commit queue, remove the block ID from the commit queue.

声明88、本发明构思的一个实施例包括根据声明76的物品，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 88. An embodiment of the present inventive concept includes the article according to statement 76, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

增加针对区块ID的访问计数；Increase the access count for the block ID;

响应于区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重；calculating a recency weight for the block ID in response to the current access time and the previous access time of the block ID;

响应于近因权重而更新针对区块ID的访问计数；update the access count for the block ID in response to the recency weight;

响应于更新的访问计数而确定针对区块ID的流ID。The stream ID for the block ID is determined in response to the updated access count.

声明89、本发明构思的一个实施例包括根据声明88的物品，其中，响应于针对区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重的步骤包括：将近因权重计算为二的(将针对区块ID的当前访问时间与区块ID的先前访问时间之差除以衰减期)次幂。Statement 89. An embodiment of the present inventive concept includes the article according to statement 88, wherein the step of calculating a recency weight for a block ID in response to a current access time and a previous access time for the block ID comprises: a recency weight Calculated as a power of two (the difference between the current access time for the block ID and the previous access time for the block ID divided by the decay period) power.

声明90、本发明构思的一个实施例包括根据声明89的物品，其中，响应于近因权重而更新针对区块ID的访问计数的步骤包括：将访问计数除以近因权重。Statement 90. One embodiment of the present inventive concept includes the article of statement 89, wherein the step of updating the access count for the block ID in response to the recency weight comprises dividing the access count by the recency weight.

声明91、本发明构思的一个实施例包括根据声明88的物品，其中，响应于更新的访问计数而确定针对区块ID的流ID的步骤包括：将区块ID的流ID计算为更新的访问计数的对数。Statement 91. An embodiment of the present inventive concept includes the article of statement 88, wherein the step of determining the flow ID for the block ID in response to the updated access count comprises: calculating the flow ID of the block ID as the updated access The logarithm of the count.

声明92、本发明构思的一个实施例包括根据声明76的物品，其中，执行与区块ID关联的流ID的后台更新的步骤包括：Statement 92. An embodiment of the present inventive concept includes the article according to statement 76, wherein the step of performing a background update of the stream ID associated with the block ID comprises:

将区块ID置于与流ID对应的队列中，其中，与流ID对应的队列是多个队列中的一个；Place the block ID in the queue corresponding to the flow ID, wherein the queue corresponding to the flow ID is one of multiple queues;

当区块ID到达队列的头部时，确定是否将区块ID降级。When the block ID reaches the head of the queue, determine whether to demote the block ID.

声明93、本发明构思的一个实施例包括根据声明92的物品，其中，将区块ID置于与流ID对应的队列中的步骤包括：Statement 93. An embodiment of the present inventive concept includes the article according to statement 92, wherein the step of placing the block ID in the queue corresponding to the flow ID comprises:

增加针对区块ID的访问计数；Increase the access count for the block ID;

响应于针对区块ID的访问计数而确定针对区块ID的流ID。The stream ID for the tile ID is determined in response to the access count for the tile ID.

声明94、本发明构思的一个实施例包括根据声明93的物品，其中，响应于针对区块ID的访问计数而确定针对区块ID的流ID的步骤包括：将针对区块ID的流ID计算为针对区块ID的访问计数的对数。Statement 94. An embodiment of the present inventive concept includes the article of statement 93, wherein the step of determining the flow ID for the block ID in response to the access count for the block ID comprises: calculating the flow ID for the block ID is the logarithm of the access count for the block ID.

声明95、本发明构思的一个实施例包括根据声明93的物品，其中，将区块ID置于与流ID对应的队列中的步骤还包括：如果针对区块ID的访问计数超过最热的区块的第二访问计数，则将区块ID确定为新的最热的区块。Statement 95. An embodiment of the present inventive concept includes the article according to statement 93, wherein the step of placing the block ID in the queue corresponding to the flow ID further comprises: if the access count for the block ID exceeds the hottest block The second access count of the block, then the block ID is determined as the new hottest block.

声明96、本发明构思的一个实施例包括根据声明95的物品，其中，将区块ID确定为新的最热的区块的步骤包括：将装置寿命确定为区块ID的当前访问时间与区块ID的先前访问时间之差。Statement 96. An embodiment of the present inventive concept includes the article according to statement 95, wherein the step of determining the block ID as the new hottest block comprises: determining the device age as the current access time of the block ID and the zone The difference between the previous access times of the block ID.

声明97、本发明构思的一个实施例包括根据声明91的物品，其中：Statement 97. An embodiment of the present inventive concept includes an article according to statement 91, wherein:

执行与区块ID关联的流ID的后台更新的步骤还包括响应于访问计数和装置寿命而确定区块ID的失效时间；The step of performing a background update of the stream ID associated with the block ID also includes determining an expiration time for the block ID in response to the access count and device age;

当区块ID到达队列的头部时确定是否将区块ID降级的步骤包括：如果区块ID的失效时间已经过去，则：从与流ID对应的队列去除区块ID；减少流ID；将区块ID置于与减少的流ID对应的第二队列中。The step of determining whether to downgrade the block ID when the block ID reaches the head of the queue includes: if the expiration time of the block ID has elapsed, then: remove the block ID from the queue corresponding to the flow ID; reduce the flow ID; The block ID is placed in the second queue corresponding to the reduced stream ID.

声明98、本发明构思的一个实施例包括根据声明97的物品，其中，响应于访问计数和装置寿命而确定区块ID的失效时间的步骤包括：将装置寿命确定为最热的区块的最后访问时间与最热的区块的先前访问时间之差。Statement 98. An embodiment of the present inventive concept includes the article of statement 97, wherein the step of determining the expiration time of the block ID in response to the access count and the device age comprises: determining the device age as the last of the hottest block The difference between the access time and the previous access time of the hottest block.

声明99、本发明构思的一个实施例包括根据声明97的物品，其中，当区块ID到达队列的头部时确定是否将区块ID降级的步骤还包括：如果区块ID的失效时间已经过去，并且如果区块ID是最热的区块，则将与流ID对应的队列中的第二区块ID选择作为新的最热的区块。Statement 99. An embodiment of the present inventive concept includes the article according to statement 97, wherein the step of determining whether to downgrade the block ID when the block ID reaches the head of the queue further comprises: if the block ID's expiration time has elapsed , and if the block ID is the hottest block, the second block ID in the queue corresponding to the stream ID is selected as the new hottest block.

因此，考虑到这里描述的实施例的各种各样的置换，本具体实施方式和附件意图仅为示意性的，并不应被认为限制本发明构思的范围。因此，要求保护的发明构思是可在权利要求书和其等同物的精神和范围内的所有这样的修改。Accordingly, given the various permutations of the embodiments described herein, the present detailed description and appendix are intended to be illustrative only and should not be construed as limiting the scope of the inventive concept. Accordingly, the claimed inventive concept is intended for all such modifications within the spirit and scope of the claims and their equivalents.

Claims (17)

Translated fromChinese

1.一种固态驱动器SSD，所述SSD包括：1. A solid state drive SSD, the SSD comprising:闪存，存储数据并支持SSD中的多个装置流；Flash memory, which stores data and supports multiple device streams in SSD;SSD控制器，管理响应于多个写入命令而将数据写入到闪存，所述SSD控制器包括用于提交队列和区块流映射器的存储器，An SSD controller that manages writing data to the flash memory in response to a plurality of write commands, the SSD controller including memory for a commit queue and a block stream mapper,其中，所述SSD控制器包括闪存转换层，所述闪存转换层包括：Wherein, the SSD controller includes a flash memory translation layer, and the flash memory translation layer includes:接收器，接收包括逻辑块地址LBA的写入命令；a receiver, receiving a write command including the logical block address LBA;LBA映射器，将LBA映射到区块标识符ID；LBA mapper, which maps LBA to block identifier ID;流选择逻辑，使用区块流映射器来基于区块ID选择流ID；Stream selection logic, using a block stream mapper to select stream IDs based on block IDs;流ID添加器，将流ID添加到所述写入命令；a stream ID adder that adds a stream ID to the write command;排队器，将区块ID置于提交队列中；Queuer, which puts the block ID in the submission queue;后台逻辑，从提交队列去除区块ID来更新区块流映射器，其中，区块流映射器存储关于什么流当前被分配给区块的信息，所述信息能够被更新为提交队列中的区块ID的结果或者提交队列中的区块ID的缺少。Background logic to remove the block ID from the commit queue to update the block stream mapper, where the block stream mapper stores information about what stream is currently assigned to the block, which information can be updated to the block in the commit queue The result of the block ID or the lack of a block ID in the commit queue.2.如权利要求1所述的SSD，其中，区块流映射器包括顺序性、频度、近因SFR表，所述SFR表包括区块ID和针对区块ID的流ID。2. The SSD of claim 1, wherein the block stream mapper includes a sequential, frequent, recency SFR table including a block ID and a stream ID for the block ID.3.如权利要求2所述的SSD，其中，后台逻辑包括：顺序性逻辑，如果LBA与先前写入命令的第二LBA是顺序的则选择与先前写入命令对应的先前流。3. The SSD of claim 2, wherein the background logic includes sequential logic to select the previous stream corresponding to the previous write command if the LBA is in sequence with a second LBA of the previous write command.4.如权利要求2所述的SSD，其中，后台逻辑包括：4. The SSD of claim 2, wherein the background logic comprises:近因逻辑，基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；Recency logic, calculating recency weights based on the current access time for the block ID, the previous access time for the block ID, and the decay period;访问计数调节器，基于近因权重调节区块ID的访问计数以产生调节的访问计数；an access count adjuster that adjusts the access count of the block ID based on the recency weight to generate the adjusted access count;流ID调节器，基于针对区块ID的调节的访问计数来调节流ID。A flow ID adjuster that adjusts the flow ID based on the adjusted access count for the block ID.5.如权利要求1所述的SSD，其中，区块流映射器包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。5. The SSD of claim 1, wherein the block flow mapper includes a node entry including a block ID and a flow ID for the block ID.6.如权利要求5所述的SSD，其中，后台逻辑包括：6. The SSD of claim 5, wherein the background logic comprises:升级逻辑，基于区块ID确定何时将流ID升级；The upgrade logic determines when to upgrade the stream ID based on the block ID;第二排队器，响应于针对区块ID的流ID而将区块ID置于与多个流ID分别对应的多个队列中的第一队列中；a second queuer, responsive to the flow ID for the block ID, placing the block ID in a first queue of the plurality of queues corresponding to the plurality of flow IDs respectively;降级逻辑，基于区块ID确定何时将流ID降级。Downgrade logic to determine when to downgrade the stream ID based on the block ID.7.如权利要求6所述的SSD，其中：7. The SSD of claim 6, wherein:降级逻辑包括比较器和减量器，其中，比较器确定针对区块ID的失效时间是否已经过去，并且如果针对区块ID的失效时间已经过去，则减量器减少流ID；The demotion logic includes a comparator and a decrementer, wherein the comparator determines whether the expiration time for the block ID has elapsed, and if the expiration time for the block ID has elapsed, the decrementor decrements the flow ID;第二排队器进行操作来响应于针对区块ID的减少的流ID而将区块ID置于与所述多个流ID分别对应的所述多个队列中的第二队列中。The second queuer operates to place the block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs, respectively, in response to the reduced flow ID for the block ID.8.一种在计算机系统中使用的驱动器，所述驱动器包括：8. A drive for use in a computer system, the drive comprising:接收器，接收针对固态驱动器SSD的写入命令，所述写入命令包括逻辑块地址LBA；a receiver, receiving a write command for the solid state drive SSD, the write command including the logical block address LBA;LBA映射器，将LBA映射到区块标识符ID；LBA mapper, which maps LBA to block identifier ID;流选择逻辑，使用存储在主机计算机系统中的存储器中的区块流映射器，来基于区块ID选择流ID；stream selection logic, using a block stream mapper stored in memory in the host computer system, to select a stream ID based on the block ID;流ID添加器，将流ID添加到所述写入命令；a stream ID adder that adds a stream ID to the write command;排队器，将区块ID置于存储在存储器中的提交队列中；A queuer that places the block ID in a commit queue stored in memory;后台逻辑，从提交队列去除区块ID来更新区块流映射器，其中，区块流映射器存储关于什么流当前被分配给区块的信息，所述信息能够被更新为提交队列中的区块ID的结果或者提交队列中的区块ID的缺少。Background logic to remove the block ID from the commit queue to update the block stream mapper, where the block stream mapper stores information about what stream is currently assigned to the block, which information can be updated to the block in the commit queue The result of the block ID or the lack of a block ID in the commit queue.9.如权利要求8所述的驱动器，其中，区块流映射器包括顺序性、频度、近因SFR表，所述SFR表包括区块ID和针对区块ID的流ID。9. The driver of claim 8, wherein the block stream mapper includes a sequential, frequent, recency SFR table including a block ID and a stream ID for the block ID.10.如权利要求9所述的驱动器，其中，后台逻辑包括：顺序性逻辑，如果LBA与先前写入命令的第二LBA是顺序的则选择与先前写入命令对应的先前流。10. The drive of claim 9, wherein the background logic includes sequential logic to select the previous stream corresponding to the previous write command if the LBA is in sequence with a second LBA of the previous write command.11.如权利要求9所述的驱动器，其中，后台逻辑包括：11. The driver of claim 9, wherein the background logic comprises:近因逻辑，基于针对区块ID的当前访问时间、针对区块ID的先前访问时间和衰减期来计算近因权重；Recency logic, calculating recency weights based on the current access time for the block ID, the previous access time for the block ID, and the decay period;访问计数调节器，基于近因权重调节针对区块ID的访问计数以产生调节的访问计数；an access count adjuster that adjusts the access count for the block ID based on the recency weight to generate an adjusted access count;流ID调节器，基于针对区块ID的调节的访问计数来调节流ID。A flow ID adjuster that adjusts the flow ID based on the adjusted access count for the block ID.12.如权利要求8所述的驱动器，其中，区块流映射器包括节点条目，所述节点条目包括区块ID和针对区块ID的流ID。12. The driver of claim 8, wherein the block flow mapper includes a node entry including a block ID and a flow ID for the block ID.13.如权利要求12所述的驱动器，其中，后台逻辑包括：13. The driver of claim 12, wherein the background logic comprises:升级逻辑，基于区块ID确定何时将流ID升级；The upgrade logic determines when to upgrade the stream ID based on the block ID;第二排队器，响应于针对区块ID的流ID而将区块ID置于与多个流ID分别对应的多个队列中的第一队列中；a second queuer that places the block ID in a first queue in a plurality of queues corresponding to the plurality of flow IDs in response to the flow ID for the block ID;降级逻辑，基于区块ID确定何时将流ID降级。Downgrade logic to determine when to downgrade the stream ID based on the block ID.14.如权利要求13所述的驱动器，其中：14. The drive of claim 13, wherein:降级逻辑包括比较器和减量器，其中，比较器确定针对区块ID的失效时间是否已经过去，如果针对区块ID的失效时间已经过去，则减量器减少流ID；The downgrade logic includes a comparator and a decrementer, wherein the comparator determines whether the expiration time for the block ID has elapsed, and the decrementor decrements the flow ID if the expiration time for the block ID has elapsed;第二排队器进行操作来响应于针对区块ID的减少的流ID而将区块ID置于与所述多个流ID分别对应的所述多个队列中的第二队列中。The second queuer operates to place the block ID in a second queue of the plurality of queues corresponding to the plurality of flow IDs, respectively, in response to the reduced flow ID for the block ID.15.一种控制固态驱动器SSD的方法，所述方法包括：15. A method of controlling a solid state drive SSD, the method comprising:从软件源接收写入命令；receive a write command from a software source;确定所述写入命令中的逻辑块地址LBA；determining the logical block address LBA in the write command;识别针对包括所述LBA的固态驱动器SSD上的区块的区块标识符ID；identifying a block identifier ID for the block on the solid state drive SSD that includes the LBA;访问与区块ID关联的流ID；access the stream ID associated with the block ID;将流ID分配给所述写入命令；assigning a stream ID to the write command;在SSD上使用分配的流ID处理所述写入命令；processing the write command on the SSD using the assigned stream ID;执行与区块ID关联的流ID的后台更新，perform a background update of the stream ID associated with the block ID,其中，执行与区块ID关联的流ID的后台更新的步骤包括：Wherein, the step of performing the background update of the stream ID associated with the block ID includes:将区块ID添加到提交队列；Add the block ID to the commit queue;当区块ID在提交队列的头部时，从提交队列去除区块ID，When the block ID is at the head of the commit queue, remove the block ID from the commit queue,或者，or,增加针对区块ID的访问计数；Increase the access count for the block ID;响应于针对区块ID的当前访问时间和先前访问时间而计算针对区块ID的近因权重；calculating a recency weight for the block ID in response to the current access time and the previous access time for the block ID;响应于近因权重而更新针对区块ID的访问计数；update the access count for the block ID in response to the recency weight;响应于更新的访问计数而确定针对区块ID的流ID，determining the stream ID for the block ID in response to the updated access count,或者，or,将区块ID置于与流ID对应的队列中，其中，与流ID对应的队列是多个队列中的一个；Place the block ID in the queue corresponding to the flow ID, wherein the queue corresponding to the flow ID is one of multiple queues;当区块ID到达队列的头部时，确定是否将区块ID降级。When the block ID reaches the head of the queue, determine whether to demote the block ID.16.如权利要求15所述的方法，还包括：16. The method of claim 15, further comprising:确定所述LBA与第二写入命令中的第二LBA是否是顺序的；determining whether the LBA is sequential with the second LBA in the second write command;如果所述LBA与第二写入命令中的第二LBA是顺序的，则：确定分配给第二写入命令的第二流ID；将第二流ID分配给所述写入命令。If the LBA is sequential with the second LBA in the second write command, then: determine the second stream ID assigned to the second write command; assign the second stream ID to the write command.17.如权利要求15所述的方法，其中，执行与区块ID关联的流ID的后台更新的步骤包括：17. The method of claim 15, wherein the step of performing a background update of the stream ID associated with the block ID comprises:将区块ID置于与流ID对应的队列中，其中，与流ID对应的队列是多个队列中的一个；Place the block ID in the queue corresponding to the flow ID, wherein the queue corresponding to the flow ID is one of multiple queues;当区块ID到达队列的头部时，确定是否将区块ID降级，When the block ID reaches the head of the queue, determine whether to downgrade the block ID,其中：in:执行与区块ID关联的流ID的后台更新的步骤还包括响应于访问计数和装置寿命而确定针对区块ID的失效时间；The step of performing a background update of the stream ID associated with the block ID also includes determining an expiration time for the block ID in response to the access count and device age;当区块ID到达队列的头部时确定是否将区块ID降级的步骤包括：如果针对区块ID的失效时间已经过去，则：从与流ID对应的队列去除区块ID；减少流ID；将区块ID置于与减少的流ID对应的第二队列中。When the block ID reaches the head of the queue, the step of determining whether to downgrade the block ID includes: if the expiration time for the block ID has passed, then: remove the block ID from the queue corresponding to the flow ID; reduce the flow ID; The block ID is placed in the second queue corresponding to the reduced stream ID.

Images