Efficient key collision handling

Patent metadata

Field	Value
Publication number	US-9846642-B2
Application number	US-201514686755-A
Country	US
Kind code	B2
Filing date	Apr 14, 2015
Priority date	Oct 21, 2014
Publication date	Dec 19, 2017
Grant date	Dec 19, 2017

Abstract

Inventive aspects include a key value store engine including non-volatile memory configured to store key-value inode descriptors each including a key and an associated value. The key value store engine can include a volatile memory to store a key hash tree and a collision hash tree. The key hash tree can include nodes each having a hash of one of the keys. The collision hash tree can include nodes each having a collided hash associated with two or more different keys. Each of the nodes of the key hash tree can include a collision flag indicating whether two or more different hashes correspond to a collided hash. The volatile memory can store a collision linked list including linked list nodes each having a key-value inode number indicating a location of a corresponding key-value inode descriptor stored in the non-volatile memory. The key value store engine can include a key value logic section.

First claim

What is claimed is:

1. A key value store engine, comprising:
a non-volatile memory configured to store a plurality of key-value inode descriptors each including a key from among a plurality of keys and an associated value from among a plurality of values;
a volatile memory configured to store a key hash tree and a collision hash tree, the key hash tree including a first plurality of nodes each having a hash of one of the plurality of keys, the collision hash tree including a second plurality of nodes each having a collided hash associated with two different keys from among the plurality of keys; and
a key value logic section configured to:
receive a get-key request associated with a particular key from among the plurality of keys;
hash the particular key to produce a first hashed key;
determine whether the first hashed key collides with a second hashed key in the key hash tree;
in response to said determining that the first hashed key collides with the second hashed key in the key hash tree, reference the collision hash tree to distinguish between the collided first and second hashed keys;
in response to said determining that the first hashed key collides with the second hashed key in the key hash tree, find the first hashed key in the collision hash tree;
access a pointer that is associated with the first hashed key in the collision hash tree and that points to a collision linked list;
walk the collision linked list until a cached key is found that corresponds to the particular key; and
cause a particular cached value associated with the particular key to be read from the collision linked list.

2. The key value store engine of claim 1 , wherein at least one node of the first plurality of nodes includes a collision flag indicating whether two different hashes of the two different keys, respectively, correspond to a collided hash.

3. The key value store engine of claim 1 , wherein:
the volatile memory is configured to store the collision linked list including a plurality of linked list nodes each having a key-value inode number indicating a location of a corresponding key-value inode descriptor from among the plurality of key-value inode descriptors stored in the non-volatile memory.

4. The key value store engine of claim 3 , wherein:
each of the plurality of linked list nodes of the collision linked list includes a cached copy of a key that is digitally equivalent to a corresponding key in the corresponding key-value inode descriptor.

5. The key value store engine of claim 1 , wherein the key value logic section is further configured to:
check a collision flag stored in a node in the key hash tree that is associated with the first hashed key to determine whether the first hashed key collides with the second hashed key.

6. The key value store engine of claim 1 , wherein the key value logic section is further configured to:
walk the collision linked list until a key-value inode number is found that corresponds to a location of a corresponding key-value inode descriptor associated with the particular key and stored in the non-volatile memory; and
cause a particular value associated with the particular key to be read from the non-volatile memory.

7. A computer-implemented method for providing efficient key collision handling, the method comprising:
storing, in a non-volatile memory, a plurality of key-value inode descriptors each including a key from among a plurality of keys and an associated value from among a plurality of values;
storing, in a volatile memory, a key hash tree and a collision hash tree;
storing, in the key hash tree, a first plurality of nodes each having a hash of at least one of the plurality of keys;
storing, in the collision hash tree, a second plurality of nodes each having a collided hash that is associated with two different keys from among the plurality of keys;
receiving, by a key value logic section, a get-key request associated with a particular key from among the plurality of keys;
hashing the particular key to produce a first hashed key;
determining whether the first hashed key collides with a second hashed key in the key hash tree; and
in response to said determining that the first hashed key collides with the second hashed key in the key hash tree, referencing the collision hash tree to distinguish between the collided first and second hashed keys;
wherein referencing includes:
finding the first hashed key in the collision hash tree;
accessing a pointer that is associated with the first hashed key and that points to a collision linked list;
walking the collision linked list until a key-value inode number is found that corresponds to a location of a corresponding key-value inode descriptor associated with the particular key and stored in the non-volatile memory; and
causing a particular value associated with the particular key to be read from the nonvolatile memory.

8. The computer-implemented method for providing efficient key collision handling of claim 7 , the method further comprising:
storing, in the volatile memory, the collision linked list including a plurality of linked list nodes each having a key-value inode number indicating a location of a corresponding key-value inode descriptor from among the plurality of key-value inode descriptors stored in the non-volatile memory.

9. A computer-implemented method for providing efficient key collision handling, the method comprising:
generating a key hash of a key using a hash function;
allocating at least one of a new logical block address (LB A) or a bytes offset within a partially used LBA;
generating a key-value inode descriptor;
storing a key-value pair including the key and a value in the key-value inode descriptor;
writing the key-value inode descriptor to the at least one of the new LBA or the bytes offset within the partially used LBA;
generating a binary tree node including the key hash and a key-value inode number for the key-value inode descriptor;
inserting the binary tree node into a key hash tree in a volatile memory;
determining whether a hash collision of the key hash has occurred; and
in response to determining that the hash collision has occurred, generating a collision tree node including the key hash and a start address for a collision linked list.

10. The computer-implemented method for providing efficient key collision handling of claim 9 , further comprising:
inserting the collision tree node into a collision hash tree.

11. The computer-implemented method for providing efficient key collision handling of claim 10 , further comprising:
updating the collision linked list with a new linked list node.

12. The computer-implemented method for providing efficient key collision handling of claim 9 , further comprising:
determining whether there are more keys for which additional binary tree nodes and key-value inode descriptors need to be generated;
in response to determining that additional binary tree nodes and key-value inode descriptors need to be generated:
generating a second key hash of a second key using the hash function;
allocating at least one of a second new logical block address (LB A) or a second bytes offset within a second partially used LBA;
generating a second key-value inode descriptor;
storing a second key-value pair including the second key and a second value in the second key-value inode descriptor;
writing the second key-value inode descriptor to the at least one of the second new LBA or the second bytes offset within the second partially used LBA;
generating a second binary tree node including the second key hash and a second key-value inode number for the second key-value inode descripto

Assignees

• Samsung Electronics Co Ltd

Inventors

• Choi Changho
• Um Taeil

Classifications

• G06F2212/466

  Metadata, control data · CPC title

• G06F2212/313

  In storage device · CPC title

• G06F2212/214

  Solid state disk · CPC title

• G06F12/0866 Primary

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title