AUTOMATIC STREAM DETECTION & ASSIGNMENT ALGORITHM

• US 20170228157A1
• Filed: 04/27/2017
• Published: 08/10/2017
• Est. Priority Date: 07/13/2015
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: YANG, Jingpei, CHOI, Changho, PANDURANGAN, Rajinikanth, BALAKRISHNAN, Vijay, PANDIAN, Ramaraj
• Granted Patent: US 10,656,838 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A Solid State Drive (SSD) is disclosed. The SSD may include flash memory to store data and may support a plurality of device streams. A SSD controller may manage reading and writing data to the flash memory, and may store a submission queue and a chunk-to-stream mapper. A flash translation layer may include a receiver to receive a write command, an LBA mapper to map an LBA to a chunk identifier (ID), stream selection logic to select a stream ID based on the chunk ID, a stream ID adder to add the stream ID to the write command, a queuer to place the chunk ID in the submission queue, and background logic to update the chunk-to-stream mapper after the chunk ID is removed from the submission queue.

Claims

1. A Solid State Drive (SSD), comprising:

flash memory to store data;

support for a plurality of device streams in the SSD;

a SSD controller to manage writing data to the flash memory responsive to a plurality of write commands, the SSD controller including storage for a submission queue and a chunk-to-stream mapper; and

a flash translation layer, including;

a receiver to receive a write command including a logical block address (LBA);

an LBA mapper to map the LBA to a chunk identifier (ID);

stream selection logic to select a stream ID based on the chunk ID using the chunk-to-stream mapper;

a stream ID adder to add the stream ID to the write command;

a queuer to place the chunk ID in the submission queue; and

background logic to remove the chunk ID from the submission queue and update the chunk-to-stream mapper.

2. A SSD according to claim 1, wherein the chunk-to-stream mapper includes a Sequential, Frequency, Recency (SFR) table, the SFR table including the chunk ID and the stream ID for the chunk ID.

3. A SSD according to claim 2, wherein the background logic includes sequentiality logic to select a previous stream if the LBA is sequential to a second LBA of a previous write command.

4. A SSD according to claim 2, wherein the background logic includes:

recency logic to calculate a recency weight based on a current access time for the chunk ID, a previous access time for the chunk ID, and a decay period;

an access count adjuster to adjust an access count for the chunk ID based on the recency weight producing an adjusted access count; and

a stream ID adjuster to adjust the stream ID based on the adjusted access count for the chunk ID.

5. A SSD according to claim 1, wherein the chunk-to-stream mapper includes a node entry, the node entry including the chunk ID and the stream ID for the chunk ID.

6. A SSD according to claim 5, wherein the background logic includes:

promotion logic to determine when to promote the stream ID based on the chunk ID;

a second queuer to place the chunk ID in a first of a plurality of queues corresponding to a plurality of stream IDs, responsive to the stream ID for the chunk ID; and

demotion logic to determine when to demote the stream ID based on the chunk ID.

7. A SSD according to claim 6, wherein:

the demotion logic includes;

a comparator to determine if an expiration time for the chunk ID has passed; and

if the expiration time for the chunk ID has passed, a decrementor to decrement the stream ID; and

the second queuer is operative to place the chunk ID in a second of the plurality of queues corresponding to the plurality of stream IDs, responsive to the decremented stream ID for the chunk ID.

8. A driver for use in a computer system, comprising:

a receiver to receive a write command for a Solid State Drive (SSD), the write command including a logical block address (LBA);

an LBA mapper to map the LBA to a chunk identifier (ID);

stream selection logic to select a stream ID based on the chunk ID using a chunk-to-stream mapper stored in a memory in a host computer system;

a stream ID adder to add the stream ID to the write command;

a queuer to place the chunk ID in a submission queue stored in the memory; and

background logic to remove the chunk ID from the submission queue and update the chunk-to-stream mapper.

9. A driver according to claim 8, wherein the chunk-to-stream mapper includes a Sequential, Frequency, Recency (SFR) table, the SFR table including the chunk ID and the stream ID for the chunk ID.

10. A driver according to claim 9, wherein the background logic includes sequentiality logic to select a previous stream if the LBA is sequential to a second LBA of a previous write command.

11. A driver according to claim 9, wherein the background logic includes:

recency logic to calculate a recency weight based on a current access time for the chunk ID, a previous access time for the chunk ID, and a decay period;

an access count adjuster to adjust an access count for the chunk ID based on the recency weight producing an adjusted access count; and

a stream ID adjuster to adjust the stream ID based on the adjusted access count for the chunk ID.

12. A driver according to claim 8, wherein the chunk-to-stream mapper includes a node entry, the node entry including the chunk ID and the stream ID for the chunk ID. Patent Application Page 49 of 53 Attorney Docket No. 1535-327

13. A driver according to claim 12, wherein the background logic includes:

promotion logic to determine when to promote the stream ID based on the chunk ID;

a second queuer to place the chunk ID in a first of a plurality of queues corresponding to a plurality of stream IDs responsive to the stream ID for the chunk ID; and

demotion logic to determine when to demote the stream ID based on the chunk ID.

14. A driver according to claim 13, wherein:

the demotion logic includes;

a comparator to determine if an expiration time for the chunk ID has passed; and

if the expiration time for the chunk ID has passed, a decrementor to decrement the stream ID; and

the second queuer is operative to place the chunk ID in a second of the plurality of queues corresponding to the plurality of stream IDs responsive to the decremented stream ID for the chunk ID.

15. A method, comprising:

receiving a write command from a software source;

determining a logical block address (LBA) in the write command;

identifying a chunk identifier (ID) for a chunk on a Solid State Drive (SSD) including the LBA;

accessing a stream ID associated with the chunk ID;

assigning the stream ID to the write command;

processing the write command using the assigned stream ID on the SSD; and

performing a background update of the stream ID associated with the chunk ID.

16. A method according to claim 15, further comprising:

determining whether the logical block address is sequential to a second LBA in a second write command; and

if the logical block address is sequential to the second LBA in the second write command;

determining the second stream ID assigned to the second write command; and

assigning the second stream ID to the write command.

17. A method according to claim 15, wherein performing a background update of the stream ID associated with the chunk ID includes:

adding the chunk ID to a submission queue; and

removing the chunk ID from the submission queue when the chunk ID is at a head of the submission queue.

18. A method according to claim 15, wherein performing a background update of the stream ID associated with the chunk ID includes:

increasing an access count for the chunk ID;

calculating a recency weight for the chunk ID responsive to a current access time and a previous access time for the chunk ID;

updating the access count for the chunk ID responsive to the recency weight; and

determining the stream ID for the chunk ID responsive to the updated access count.

19. A method according to claim 15, wherein performing a background update of the stream ID associated with the chunk ID includes:

placing the chunk ID in a queue corresponding to the stream ID, where the queue corresponding to the stream ID is one a plurality of queues; and

determining whether to demote the chunk ID when the chunk ID reaches the head of the queue.

20. A method according to claim 19, wherein:

performing a background update of the stream ID associated with the chunk ID further includes determining an expiration time for the chunk ID responsive to the access count and a device lifetime; and

determining whether to demote the chunk ID when the chunk ID reaches the head of the queue includes, if the expiration time for the chunk ID has passed;

removing the chunk ID from the queue corresponding to the stream ID;

decrementing the stream ID; and

placing the chunk ID in a second queue corresponding to the decremented stream ID.