Key-value store using journaling with selective data storage format

• US 10,852,978 B2
• Filed: 12/14/2018
• Issued: 12/01/2020
• Est. Priority Date: 12/14/2018
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Micron Technology, Inc.
• Inventors: Kurichiyath, Sudheer, Becker, Greg A., Boles, David, Moyer, Steven, Meeramohideen Mohamed, Nabeel, Tomlinson, Alexander
• Primary Examiner(s): Portka, Gary J
• Application Number:
  US16/220,646
• Publication Number:
  US 20200192590A1
• Time in Patent Office: 718 Days
• Field of Search: 707797, 711154, 711170
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• 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/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Aspects of the present disclosure provide for operations of a key-value store (KVS) that uses journaling with storage of data (e.g., key data or value data of a key-value pair) in different types of data storage objects (e.g., data storage formats) selected based on one or more criteria.

Claims

1. A system comprising:

a set of memory components providing a journal data storage space and a long-term data storage space; and

a processing device, operatively coupled to the set of memory components, configured to perform operations comprising;

receiving, from volatile memory, a set of key-value pairs;

storing key data for a particular key, of a particular key-value pair in the set of key-value pairs, in a first journal data storage object on the journal data storage space;

determining whether a particular value, of the particular key-value pair, meets a non-journal data storage object criterion;

based on the determining whether the particular value meets the non-journal data storage object criterion, storing value data for the particular value, in at least one of a non-journal data storage object on the journal data storage space or a second journal data storage object on the journal data storage space;

determining whether a condition, to move the key data and the value data from the journal data storage space, is satisfied; and

in response to determining that the condition is satisfied, moving the key data and the value data from the journal data storage space to a new key-value set added to a node of a key-value store tree data structure, the key-value store tree being stored on the long-term data storage space, and the new key-value set comprising a first set of non-journal data storage objects for storing one or more keys and a second set of non-journal data storage objects for storing one or more values.

2. The system of claim 1, wherein the first journal data storage object comprises a metadata log.

3. The system of claim 1, wherein the non-journal data storage object comprises a value block, and the second set of non-journal data storage objects comprises a set of value blocks.

4. The system of claim 1, wherein the first set of non-journal data storage objects comprises a set of key blocks.

5. The system of claim 1, wherein the operations further comprise:

in response to determining that the particular value meets the non-journal data storage object criterion, storing the value data in the non-journal data storage object on the journal data storage space.

6. The system of claim 5, wherein the moving the key data and the value data from the journal data storage space to the key-value store tree data structure comprises:

moving the key data, from the journal data storage space to the key-value store tree data structure, by writing the key data, from the first journal data storage object on the journal data storage space, to one or more non-journal data storage objects in the first set of non-journal data storage objects; and

moving the value data, from the journal data storage space to the key-value store tree data structure, by changing association of the non-journal data storage object from the journal data storage space to the key-value store tree data structure such that the second set of non-journal data storage objects includes the non-journal data storage object.

7. The system of claim 5, wherein the first journal data storage object and the non-journal data storage object are associated with a second key-value set in a sequence of key-value sets on the journal data storage space.

8. The system of claim 1, wherein the operations further comprise:

in response to determining that the particular value does not meet the non-journal data storage object criterion, storing the value data in the second journal data storage object on the journal data storage space.

9. The system of claim 8, wherein the moving the key data and the value data from the journal data storage space to the key-value store tree data structure comprises:

moving the key data, from the journal data storage space to the key-value store tree data structure, by writing the key data, from the first journal data storage object on the journal data storage space, to one or more non-journal data storage objects in the first set of non-journal data storage objects; and

moving the value data, from the journal data storage space to the key-value store tree data structure, by writing the value data, from the second journal data storage object on the journal data storage space, to one or more non-journal data storage objects in the second set of non-journal data storage objects.

10. The system of claim 8, wherein the first journal data storage object and the second journal data storage object are associated with a second key-value set in a sequence of key-value sets on the journal data storage space.

11. The system of claim 1, wherein the set of key-value pairs is received from a second key-value set in a sequence of key-value sets on the volatile memory.

12. The system of claim 1, wherein the set of key-value pairs is received from a second key-value set on the volatile memory, the second key-value set comprising a binary tree data structure for storing the set of key-value pairs.

13. The system of claim 1, wherein the non-journal data storage object criterion comprises the particular value exceeding a value data size.

14. The system of claim 1, wherein the non-journal data storage object criterion comprises the particular key matching a target key that is associated with a historic write pattern, the historic write pattern indicating that a number of write operations for the target key has exceeded a write threshold.

15. The system of claim 1, wherein the non-journal data storage object criterion comprises the particular value matching a target value that is associated with a historic write pattern, the historic write pattern indicating that a number of write operations for the target value has exceeded a write threshold.

16. The system of claim 1, wherein the condition comprises at least one of receiving of a request to flush data from the volatile memory to the journal data storage space, reaching a predetermined time interval, or satisfying a data size criterion relating to the volatile memory.

17. The system of claim 1, wherein the system is a memory sub-system.

18. A method comprising:

receiving, from volatile memory, a set of key-value pairs;

storing, by a processing device, key data for a particular key, of a particular key-value pair in the set of key-value pairs, in a first journal data storage object on a journal data storage space provided by a set of memory components;

determining, by the processing device, whether a particular value, of the particular key-value pair, meets a non-journal data storage object criterion;

based on the determining whether the particular value meets the non-journal data storage object criterion, storing, by the processing device, value data for the particular value, in at least one of a non-journal data storage object on the journal data storage space or a second journal data storage object on the journal data storage space;

determining, by the processing device, whether a condition, to move the key data and the value data from the journal data storage space, is satisfied; and

in response to determining that the condition is satisfied, moving, by the processing device, the key data and the value data from the journal data storage space to a new key-value set added to a node of a key-value store tree data structure, the key-value store tree being stored on a long-term data storage space provided by the set of memory components, and the new key-value set comprising a first set of non-journal data storage objects for storing one or more keys and a second set of non-journal data storage objects for storing one or more values.

19. The method of claim 18, wherein the journal data storage object comprises a metadata log, the non-journal data storage object comprises a value block, the first set of non-journal data storage objects comprises a set of key blocks, and the second set of non-journal data storage objects comprises a set of value blocks.

20. A non-transitory machine-readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to:

receive, from volatile memory, a set of key-value pairs;

determine whether a particular value, of the particular key-value pair, meets a non-journal data storage object criterion;

based on the determining whether the particular value meets the non-journal data storage object criterion, store value data for the particular value, in at least one of a non-journal data storage object on a journal data storage space or a second journal data storage object on the journal data storage space;

determine whether a condition, to move key data and the value data from the journal data storage space, is satisfied; and

in response to determining that the condition is satisfied, move the value data from the journal data storage space to a new key-value set added to a node of a key-value store tree data structure, the key-value store tree being stored on a long-term data storage space provided by a set of memory components, and the new key-value set comprising a first set of non-journal data storage objects for storing one or more keys and a second set of non-journal data storage objects for storing one or more values.