Apparatus and method of data sequencing

Patent metadata

Field	Value
Publication number	US-9990146-B2
Application number	US-201615014816-A
Country	US
Kind code	B2
Filing date	Feb 3, 2016
Priority date	Feb 3, 2016
Publication date	Jun 5, 2018
Grant date	Jun 5, 2018

Abstract

An apparatus includes a data sequencing engine configured to receive first data and an identification of a first data container associated with the first data and to allocate the first data to a first data stream of multiple data streams based on the identification. The apparatus further includes at least one memory configured to store the first data container. The data sequencing engine is further configured to cause the at least one memory to send data in the first data stream to a flash memory in response to detecting a data size of the first data stream satisfies a threshold.

First claim

What is claimed is:

1. A method comprising: at a data storage device that includes a non-volatile memory, performing:
receiving data from a device, the data including a first data stream and a second data stream; wherein each of the data stream includes a metadata field and a user data field; the metadata field includes at least a magic number identifying data objects associated with a sequential data container, a container ID identifying the sequential data container, and a sequence number identifying an order of a plurality of containers within a data stream is written to a non-volatile memory; the user data field includes one or more key values pairs; and
writing a first set of key value pairs associated with a first data container identified by the container ID of the first data stream to the non-volatile memory prior to writing a second set of key value pairs associated with a second data container identified by the container ID of the second data stream, wherein the key value pairs are written to the non-volatile memory in a sequence that is based on the metadata field; and if the key value pairs received are associated with non-sequential addresses, the key value pairs are written to the non-volatile memory in sequential address.

2. The method of claim 1 , wherein the received data has a data structure, and wherein the data structure is based on a key value store or a database file format.

3. The method of claim 1 , wherein the non-volatile memory includes a persistent flash memory; wherein the received data is associated with non-sequential addresses, and the data is written to sequential addresses of the persistent flash memory.

4. The method of claim 3 , wherein writing the data to the sequential addresses reduces a fragmentation effect by avoiding one or more copy operations to rearrange the data.

5. The method of claim 1 , wherein the first data stream is received from the device at a first time, and wherein the second data stream is received from the device at a second time that is after the first time.

6. A device comprising:
a controller configured to receive data from a device, the data including a first data stream and a second data stream; wherein each of the data stream includes a metadata field and a user data field; the metadata field includes at least a magic number identifying data objects associated with a sequential data container, a container ID identifying a respective sequential data container, and a sequence number identifying an order of a plurality of containers within a data stream is written to a non-volatile memory; the user data field includes one or more key values pairs;
the non-volatile memory coupled to the controller, the non-volatile memory configured to write a first set of key value pairs associated with a first data container identified by the container ID of the first data stream prior to writing a second set of key value pairs associated with a second data container identified by the container ID of the second data stream, wherein the non-volatile memory includes a persistent flash memory, wherein the controller is configured to write the key value pairs to the persistent flash memory in a sequence that is based on the metadata field; and if the key value pairs received are associated with non-sequential addresses, the key value pairs are written to the persistent flash memory in sequential address.

7. The device of claim 6 wherein the received data has a data structure, and wherein the data structure is based on a key value store or a database file format.

8. An apparatus comprising:
a data sequencing engine configured to receive first data and an identification of a first data container associated with the first data and to allocate the first data to a first data stream of multiple data streams based on the identification;
at least one memory configured to store the first data container,
the data sequencing engine includes a hash generator configured to determine a hash of the identification of the first data container and to assign a first key value pair of the first data to the first data stream based on the hash;
wherein the first data stream comprises a metadata field and a user data field;
the metadata field includes at least a magic number identifying data objects associated with a sequential data container, the first data container identification identifying the sequential data container, and a sequence number identifying an order of a plurality of containers within the first data stream to be written to a persistent non-volatile memory; the user data field includes at least the first key values pair; and
the data sequence engine is further configured to cause the at least one memory to send the first data stream within the first data container to the non-volatile memory in response to detecting a data size of the first data stream satisfies a threshold.

9. The apparatus of claim 8 , wherein the data sequencing engine is further configured to allocate second data to a second data stream of the multiple data streams.

10. The apparatus of claim 9 , wherein the data sequencing engine is further configured to cause the at least one memory to send the second data to the non-volatile memory in response to detecting a data size of a second data container satisfies the threshold.

11. The apparatus of claim 8 , wherein the at least one memory includes a first memory and wherein the non-volatile memory (NVM) is coupled to the first memory.

12. The apparatus of claim 8 , wherein the first data stream includes a metadata field and a user data field, wherein the user data field includes a zero padded portion to enable the data size to satisfy the threshold.

13. The apparatus of claim 12 , wherein the threshold is a positive integer multiple of a logical page size associated with the non-volatile memory.

14. The apparatus of claim 8 , wherein the non-volatile memory comprises a persistent flash memory.

15. The apparatus of claim 8 , wherein the first data has a data structure, and wherein the data structure is based on one or more of a key value store or a database file format.

Assignees

• Sandisk Technologies Llc

Inventors

• Neelakanta Niranjan Patre
• Krishnan Manavalan
• Cheru Tomy Ammuthan
• Chander Ramesh
• O'Krafka Brian Walter

Classifications

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/0688

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/0616 Primary

  in relation to life time, e.g. increasing Mean Time Between Failures [MTBF] · CPC title

• G06F3/0631

  by allocating resources to storage systems · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title