Key-value store and file system integration

Patent metadata

Field	Value
Publication number	US-12332864-B2
Application number	US-202318491940-A
Country	US
Kind code	B2
Filing date	Oct 23, 2023
Priority date	Apr 20, 2021
Publication date	Jun 17, 2025
Grant date	Jun 17, 2025

Abstract

Techniques are provided for key-value store and file system integration to optimize key value store operations. A key-value store is integrated within a file system of a node. A log structured merge tree of the key-value store may be populated with a key corresponding to a content hash of a value data item stored separate from the key. A random distribution search may be performed upon a sorted log of the log structured merge tree to identify the key for accessing the value data item. A starting location for the random distribution search is derived from key information, a log size of the sorted log, and/or a keyspace size of a keyspace associated with the key.

First claim

What is claimed:

1. A method, implemented by a processor of a node, comprising:
maintaining, within a storage device by the processor, a key-value store integrated within a file system of the node;
creating, by the processor, a set of keyspaces for keys tracked by the key-value store, wherein a set of keys are uniformly distributed within a keyspace;
populating, by the processor, a log structured merge tree, associated with the keyspace of the key-value store, with a key corresponding to a content hash of a value data item stored separate from the key;
performing, by the processor, a random distribution search to identify a location of the key within a sorted log of the log structured merge tree, wherein the random distribution search is performed according to a constant time, wherein a starting location for the random distribution search is derived from key information, a log size of the sorted log, and a keyspace size of the keyspace associated with the key, and wherein the random distribution search is performed by loading a single block into memory based on a determination that the single block is not already in the memory; and
utilizing, by the processor, the key to access the value data item.

2. The method of claim 1 , comprising:
storing a portion of each key of the set of keys within the keyspace based upon the set of keys being equally distributed within the keyspace.

3. The method of claim 1 , wherein the performing the random distribution search comprises:
identifying the location of the key based upon a formula derived from the key, the log size of the sorted log, and the keyspace size of the keyspace.

4. The method of claim 1 , wherein the random distribution search is performed in a timespan shorter than a binary search having an O(log N) cost.

5. The method of claim 1 , comprising:
performing a data management operation upon the keyspace of the set of keyspaces,
wherein the data management operation corresponds to at least one of a snapshot operation, enforcement of a quality of service policy, execution of a selected compression technique, or implementation of a tiering technique.

6. The method of claim 1 , comprising:
defining the keyspace to comprise the set of keys corresponding to a set of value data items that share a characteristic.

7. The method of claim 1 , comprising:
storing keyspaces of the set of keyspaces within separate aggregates and storage groups.

8. A computing device comprising:
a memory comprising machine executable code; and
a processor coupled to the memory, the processor configured to execute the machine executable code to cause the computing device to:
maintain a key-value store integrated within a file system of a node;
create a set of keyspaces for keys tracked by the key-value store, wherein a set of keys are uniformly distributed within a keyspace;
populate a log structured merge tree, associated with the keyspace of the key-value store, with a key corresponding to a content hash of a value data item stored separate from the key;
perform a random distribution search to identify a location of the key within a sorted log of the log structured merge tree, wherein the random distribution search is performed according to a constant time, wherein the random distribution search identifies the location of the key based upon a formula derived from the key, a log size of the sorted log, and a keyspace size of the keyspace, and wherein the random distribution search is performed by loading a single block into memory; and
utilize the key to access the value data item.

9. The computing device of claim 8 , wherein the machine executable code when executed further causes the computing device to:
store a portion of each key of the set of keys within the keyspace based upon the set of keys being equally distributed within the keyspace.

10. The computing device of claim 8 , wherein the random distribution search is performed in O(1) for identifying the key.

11. The computing device of claim 8 , wherein the random distribution search is performed in O(1) for identifying the key faster than a binary searching having an O(log N) cost.

12. The computing device of claim 8 , wherein the machine executable code when executed further causes the computing device to:
perform a data management operation upon the keyspace of the set of keyspaces,
wherein the data management operation corresponds to at least one of a snapshot operation, enforcement of a quality of service policy, execution of a selected compression technique, or implementation of a tiering technique.

13. The computing device of claim 8 , wherein the machine executable code when executed further causes the computing device to:
define the keyspace to comprise the set of keys corresponding to a set of value data items that share a characteristic.

14. The computing device of claim 8 , wherein the machine executable code when executed further causes the computing device to:
store keyspaces of the set of keyspaces within separate aggregates and storage groups.

15. A non-transitory machine readable medium comprising instructions, which when executed by a machine, causes the machine to:
store keys within a sorted log of a log structured merge tree for a key-value store integrated within a file system of a node, wherein a key corresponds to a to a content hash of a value data item stored separate from the key;
maintain a pageable bloom filter for a buftree used to store the key-value store,
wherein the pageable bloom filter is split into multiple bloom filter chunks to reduce write amplification when committing the pageable bloom filter to storage across multiple filesystem consistency point operations;

utilize a bloom filter chunk of the pageable bloom filter to determine whether the key exists within a level of the log structured merge tree; and
in response to determining that the key exists within the level of the log structured merge tree, perform a random distribution search to retrieve the key from a location for accessing the value data item, wherein the random distribution search identifies the location of the key based upon a formula derived from the key, a log size of the sorted log, and a keyspace size of a keyspace, and wherein the random distribution search is performed by loading a single block into memory based on a determination that the single block is if not already in the memory.

16. The non-transitory machine readable medium of claim 15 , wherein the instructions when executed further cause the machine to:
split the pageable bloom filter into a first bloom filter chunk corresponding to a first level of the log structured merge tree and a second bloom filter chunk corresponding to a second level of the log structured merge tree.

17. The non-transitory machine readable medium of claim 15 , wherein the pageable bloom filter is split into the multiple bloom filter chunks for loading a single chunk into memory while performing a randomized lookup as part of the random distribution search to the key-value store.

18. The non-transitory machine readable medium of claim 15 , wherein the instructions when executed further cause the machine to:
store, within the log structured merge tree, a log structured merge info file, an append log hash, an append log, a lookup file comprising a block index, the pageable bloom filter, and a bloom filter chunk index file as an index to the pageable bloom filter.

19. The non-transitory machine readable medium of claim 18 , wherein the sorted log comprising keys corresponding

Assignees

• Netapp Inc

Inventors

• Seshadri Sanjay Subramanian
• Banerjee Arindam
• Patel Manan Dahyabhai
• Go Raymond Jordan
• Thoppil Anil Paul
• Subramanian Ananthan
• Selvaraj Santhosh
• Patel Nikul Y
• Rao Vikhyath
• Odugoudar Meera
• Varghese Kevin Daniel

Classifications

• G06F16/215

  Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors · CPC title

• G06F16/24553

  of query operations · CPC title

• G06F16/24573

  using data annotations, e.g. user-defined metadata · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/217

  Database tuning (G06F16/2282 takes precedence; database performance monitoring G06F11/3409) · CPC title