AUTOMATIC I/O STREAM SELECTION FOR STORAGE DEVICES

• US 20170228188A1
• Filed: 04/13/2016
• Published: 08/10/2017
• Est. Priority Date: 02/09/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: HASSANI, Sina, SHAYESTEH, Anahita, BALAKRISHNAN, Vijay
• Granted Patent: US 10,296,264 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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 method of selecting among a plurality of I/O streams through which data is to be written to a multi-streaming flash storage device is presented. According to an example embodiment, the method comprises: assigning write sequences of similar length to the same I/O streams; receiving instructions for a write operation, the instructions including a starting logical block address (LBA) and a number of blocks of data to be written; determining whether the write operation is part of an existing write sequence; identifying an I/O stream associated with an existing write sequence; and providing a stream ID of the identified I/O stream to the multi-streaming flash storage device.

Claims

1. A method of selecting among a plurality of I/O streams through which data is to be written to a multi-streaming flash storage device, each I/O stream corresponding to a different logical division of the multi-streaming flash storage device, the method comprising:

assigning write sequences of similar length to the same I/O streams;

receiving instructions for a write operation, the instructions including a starting logical block address (LBA) and a number of blocks of data to be written;

determining whether the write operation is part of an existing write sequence;

identifying an I/O stream associated with an existing write sequence; and

providing a stream ID of the identified I/O stream to the multi-streaming flash storage device.

2. The method of claim 1, wherein assigning write sequences of similar length to the same I/O streams includes:

providing a number of queues, each queue including a plurality of elements, each element configured to store a last LBA of a current write sequence and a count value; and

assigning each queue in hierarchal order to a corresponding one of the I/O streams.

3. The method of claim 2, wherein assigning write sequences of similar length to the same I/O streams further includes:

comparing the count value with an upgrade threshold value;

storing the last LBA of the current write sequence and the count value in an element of a first queue in response to determining that the count value is less than the upgrade threshold value; and

storing the last LBA of the current write sequence and the count value in an element of a second queue in response to determining that the count value is greater than the upgrade threshold value, wherein the second queue is in a next higher hierarchal order than the first queue.

4. The method of claim 3, wherein assigning write sequences of similar length to the same I/O streams further includes moving the element of the first queue to the front of the first queue.

5. The method of claim 2, wherein the count value is calculated as an accumulating function of a number of blocks of data written in the current write sequence.

6. The method of claim 2, wherein determining whether the write operation is part of an existing write sequence includes:

determining whether the starting LBA is within a threshold proximity of a last LBA stored in an element of the queues.

7. The method of claim 6, wherein determining whether the write operation is part of an existing write sequence further includes:

summing the starting LBA and the number of blocks of data to be written;

calculating the count value as a function of the number of blocks of data to be written; and

storing the sum as the last LBA and the count value in the first element of a lowest ordered queue.

8. The method of claim 2, wherein identifying an I/O stream associated with an existing write sequence includes:

identifying a queue in which the last LBA and the count value of the current write sequence is to be stored.

9. The method of claim 8, wherein providing a stream ID of the identified I/O stream to the multi-streaming flash storage device includes:

returning a number associated with the hierarchal order of the identified queue as the stream ID.

19. The non-transitory, tangible computer readable storage medium of claim 1, wherein the instructions are executed in a kernel of an operating system running on the computer.

20. The non-transitory, tangible computer readable storage medium of claim 1, wherein the instructions are executed by a virtual machine software running on the computer.

10. A non-transitory, tangible computer readable storage medium having stored thereon computer executable instructions that, when executed by a computer, cause the computer to select among a plurality of I/O streams through which data is to be written to a multi-streaming flash storage device, each I/O stream corresponding to a different storage area of the multi-streaming flash storage device, by:

assigning write sequences of similar length to the same I/O streams;

receiving instructions for a write operation, the instructions including a starting logical block address (LBA) and a number of blocks of data to be written;

determining whether the write operation is part of an existing write sequence;

identifying an I/O stream associated with an existing write sequence; and

providing a stream ID of the identified I/O stream to the multi-streaming flash storage device.

11. The non-transitory, tangible computer readable storage medium of claim 10, wherein assigning write sequences of similar length to the same I/O streams includes:

providing a number of queues, each queue including a plurality of elements, each element configured to store a last LBA of a current write sequence and a count value; and

assigning each queue in hierarchal order to a corresponding one of the I/O streams.

12. The non-transitory, tangible computer readable storage medium of claim 11, wherein assigning write sequences of similar length to the same I/O streams further includes:

comparing the count value with an upgrade threshold value;

storing the last LBA of the current write sequence and the count value in an element of a first queue in response to determining that the count value is less than the upgrade threshold value; and

storing the last LBA of the current write sequence and the count value in an element of a second queue in response to determining that the count value is greater than the upgrade threshold value, wherein the second queue is in a next higher hierarchal order than the first queue.

13. The non-transitory, tangible computer readable storage medium of claim 12, wherein assigning write sequences of similar length to the same I/O streams further includes moving the element of the first queue to the front of the first queue.

14. The non-transitory, tangible computer readable storage medium of claim 11, wherein the count value is calculated as an accumulating function of a number of blocks of data written in the current write sequence.

15. The non-transitory, tangible computer readable storage medium of claim 11, wherein determining whether the write operation is part of an existing write sequence includes:

determining whether the starting LBA is within a threshold proximity of a last LBA stored in an element of the queues.

16. The non-transitory, tangible computer readable storage medium of claim 15, wherein determining whether the write operation is part of an existing write sequence further includes:

summing the starting LBA and the number of blocks of data to be written;

calculating the count value as a function of the number of blocks of data to be written; and

storing the sum as the last LBA and the count value in the first element of a lowest ordered queue.

17. The non-transitory, tangible computer readable storage medium of claim 11, wherein identifying an I/O stream associated with an existing write sequence includes:

identifying a queue in which the last LBA and the count value of the current write sequence is to be stored.

18. The non-transitory, tangible computer readable storage medium of claim 17, wherein providing a stream ID of the identified I/O stream to the multi-streaming flash storage device includes:

returning a number associated with the hierarchal order of the identified queue as the stream ID.