Enhanced multi-streaming though statistical analysis

• US 9,898,202 B2
• Filed: 05/04/2016
• Issued: 02/20/2018
• Est. Priority Date: 11/30/2015
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Martineau, Jason, Schwaderer, William David, Choi, Changho
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US15/146,708
• Publication Number:
  US 20170235486A1
• Time in Patent Office: 657 Days
• Field of Search: 711103, 711170
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• 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 system and method for using a Solid State Drive (SSD) (505) are described. Reception circuitry (510) may receive write requests (1610, 1615, 1620, 1625) and invalidate requests (1630, 1635, 1640) from a first stream (305, 320, 335, 350). The write requests (1610, 1615, 1620, 1625) may request that data be written to storage (520) on the SSD (505); invalidate requests (1630, 1635, 1640) may invalidate data written to the storage (520). A statistics calculation logic (1705) may calculate statistics (1410, 1415, 1510) for the stream based on the write requests (1610, 1615, 1620, 1625) and the invalidate requests (1630, 1635, 1640). A performance logic (1710) may use the calculated statistics (1410, 1415, 1510) to improve the performance of the SSD (505).

Claims

1. A method, comprising:

receiving a plurality of write requests at a Solid State Drive (SSD), each of the plurality of write requests associated with a stream;

determining a plurality of write times, each of the plurality of write times associated with one of the plurality of write requests;

receiving a plurality of invalidate requests at the SSD, each of the plurality of invalidate requests deleting data written by one of the plurality of write requests;

determining a plurality of invalidate times, each of the plurality of invalidate times associated with one of the plurality of invalidate requests;

calculating statistics for the stream, the calculated statistics responsive to the plurality of write times and the plurality of invalidate times; and

using the calculated statistics to increase a likelihood that all data written to a block on the SSD will be invalidated around the same time, including;

receiving a new write request, the new write request including new data; and

selecting a destination to store the new data using the calculated statistics, the destination being one of a block on the SSD and a second-order stream.

2. A method according to claim 1, wherein calculating statistics for the stream includes:

determining a plurality of pairs of times, each pair of times in the plurality of pairs of times including one write time from the plurality of write times and one invalidate time from the plurality of invalidate times, the one write time and the one invalidate time associated with a particular write request in the plurality of write requests;

calculating a plurality of data life spans, each data life span in the plurality of data life spans including a difference between the one write time and the one invalidate time in one of the plurality of pairs of times; and

calculating the statistics for the stream, the calculated statistics responsive to the plurality of data life spans.

3. A method according to claim 2, wherein determining a plurality of pairs of times includes determining the plurality of pairs of times, the plurality of pairs of times being fewer in number than the plurality of write requests.

4. A method according to claim 2, wherein calculating statistics for the stream includes generating a statistical function that fits the plurality of data life spans.

5. A method according to claim 2, wherein calculating statistics for the stream includes generating a histogram for the plurality of data life spans.

6. A method according to claim 1, wherein using the calculated statistics to improve performance of the SSD includes using the calculated statistics to select a target block to program valid data from an erase block subject to garbage collection.

7. A method according to claim 6, wherein using the calculated statistics to select a target block to program valid data from an erase block subject to garbage collection includes:

identifying the valid data in the erase block;

determining an estimated remaining life span for the valid data using the calculated statistics;

selecting the target block having a block TTL minimally greater than the estimated remaining life span for the valid data; and

programming the valid data to the target block.

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

storage for data;

reception circuitry to receive a plurality of write requests, a plurality of invalidate requests from a stream, and a new write request, the plurality of write requests and the plurality of invalidate requests affecting the data in the storage, the new write request including new data;

statistics calculation logic to calculate statistics for the stream from the plurality of write requests and the plurality of invalidate requests; and

performance logic including a storage selector to select a destination to store the new data responsive to the calculated statistics, the destination being one of a block on the SSD and a second-order stream, thereby increasing a likelihood that all data written to the destination will be invalidated around the same time.

9. An SSD according to claim 8, wherein the statistics calculation logic includes:

a timing logic to determine a plurality of write times for the plurality of write requests and a plurality of invalidate times for the plurality of invalidate requests, and to pair individual write times for individual write requests with individual invalidate times for corresponding individual invalidate requests; and

a data life span logic to calculate data life spans from the corresponding write times from the plurality of write times and invalidate times from the plurality of invalidate times.

10. An SSD according to claim 9, wherein the statistics calculation logic further includes a statistics logic to generate a statistical function that fits the calculated data life spans.

11. An SSD according to claim 9, wherein the statistics calculation logic is operative to generate a histogram from the calculated data life spans.

12. An SSD according to claim 9, wherein the plurality of write times and the plurality of invalidate times includes a most recent number of write times and invalidate times.

13. An SSD according to claim 8, wherein the performance logic includes:

an estimated remaining life span logic to calculate an estimated remaining life span for a valid data using the calculated statistics, the valid data in an erase block subject to garbage collection; and

a storage selector to select a destination to program the valid data, the destination being one of a second block and a second-order stream, the destination having a TTL minimally greater than the estimated remaining life span for the valid data.

14. A logic for a Solid State Drive (SSD), comprising:

a timing logic to determine a plurality of write times for a plurality of write requests and a plurality of invalidate times for a plurality of invalidate requests, and to pair individual write times for individual write requests with individual invalidate times for corresponding individual invalidate requests;

a data life span logic to calculate data life spans from the corresponding write times from the plurality of write times and invalidate times from the plurality of invalidate times;

statistics calculation logic to calculate statistics for a first stream from the calculated data life spans; and

performance logic to select a destination to store a new data responsive to the calculated statistics, the destination being one of a block on the SSD and a second-order stream, thereby increasing a likelihood that all data written to the destination will be invalidated around the same time.

15. A logic according to claim 14, wherein the statistics calculation logic further includes a statistics logic to generate a statistical function that fits the calculated data life spans.

16. A logic according to claim 14, wherein the statistics calculation logic is operative to generate a histogram from the calculated data life spans.

17. A logic according to claim 14, wherein the plurality of write times and the plurality of invalidate times includes a most recent number of write times and invalidate times.

18. A logic according to claim 14, wherein the performance logic is operative to select the block to store the new data and data from a second stream, the second stream including a second stream TTL for a second confidence level, the second stream TTL close to a block TTL.