Cuckoo tree with duplicate key support
An aspect of implementing a Cuckoo tree includes providing a Cuckoo filter table for performing lookups in a Cuckoo tree. The table tracks fingerprints of keys and tablets in which the keys reside. An aspect also includes providing a stash configured to manage duplicate keys in the tree. The stash includes: a key hash table that stores full keys corresponding bucket index references that point to a reverse time ordered list of values corresponding to the full keys; and a value store having buckets with slots for storing the list. An aspect further includes setting a duplicate threshold value in the tree that provides a limit on a number of fingerprints that can exist in a bucket. During a store operation on a key, upon determining the number of existing entries with same fingerprint in target bucket would exceed the threshold, another bucket is selected for the key.
1. A method of implementing a Cuckoo tree with duplicate key support in a storage system, the method comprising:
providing a Cuckoo filter table configured to perform lookups in a Cuckoo tree, the Cuckoo filter table tracking fingerprints of keys and corresponding tablets in which the keys reside;
providing a Cuckoo stash (Stash) configured to manage duplicate keys in the Cuckoo tree, the Stash comprising:
a value store; and
a key hash table storing full keys and corresponding bucket index references that point to a reverse time ordered list of values corresponding to the full keys, wherein all of the values that correspond to a given key are stored on a fixed number of cache lines in the value store, the value store including stash buckets with slots for storing the reverse time ordered list of values;
setting a duplicate threshold value in the Cuckoo tree, the duplicate threshold value providing a limit on a number of fingerprints that can exist in a Cuckoo filter bucket;
wherein during a store operation on a key, upon determining the number of existing entries with same fingerprint in a target stash bucket would exceed the duplicate threshold another stash bucket is selected for the key.
2. The method of claim 1 , further comprising:
adding a link reference to the target stash bucket that identifies the other stash bucket.
3. The method of claim 2 , where each cache line in the value store has 8 64-bit quadwords, each cache line is divided into two stash buckets, and each of the stash buckets has a unique bucket index.
4. The method of claim 3 , wherein each bucket has four quadwords, three of the four quadwords store values and a fourth quadword stores the link reference.
5. The method of claim 1 , further comprising:
attempting to add a key/value pair to a tablet;
upon determining slots for a fingerprint corresponding to the key are full in the Cuckoo filter table:
selecting an empty stash bucket from the value store;
entering the key and stash bucket identifier to the key hash table; and
adding the value of the key/value pair to an available slot of the stash bucket in the value store.
6. The method of claim 1 , further comprising:
receiving a request to find a key in the Cuckoo tree;
searching the Stash for the key;
returning, by the Stash, a first bitmap for the key;
searching the Cuckoo filter table for the key;
returning, by the Cuckoo filter table, a second bitmap for the key;
merging data in the first and second bitmaps to produce a third bitmap; and
searching tablets for the key using the third bitmap.
7. A system for implementing a Cuckoo tree with duplicate key support in a storage system, the system includes:
a memory comprising computer-executable instructions; and
a processor executing the computer-executable instructions, the computer-executable instructions when executed by the processor cause the processor to perform operations comprising:
providing a Cuckoo filter table configured to perform lookups in a Cuckoo tree, the Cuckoo filter table tracking fingerprints of keys and corresponding tablets in which the keys reside;
providing a Stash configured to manage duplicate keys in the Cuckoo tree, the Stash comprising:
a value store; and
a key hash table storing full keys and corresponding bucket index references that point to a reverse time ordered list of values corresponding to the full keys, wherein all of the values that correspond to a given key are stored on a single cache line in a value store, the value store including stash buckets with slots for storing the reverse time ordered list of values;
setting a duplicate threshold value in the Cuckoo tree, the duplicate threshold value providing a limit on a number of fingerprints that can exist in a bucket;
wherein during a store operation on a key, upon determining the number of existing entries with same fingerprint in a target stash bucket would exceed the duplicate threshold another stash bucket is selected for the key.
8. The system of claim 7 , wherein the operations further comprise:
adding a link reference to the target stash bucket that identifies the other bucket.
9. The system of claim 8 , where each cache line in the value store has 8 64-bit quadwords, each cache line is divided into two stash buckets, and each of the stash buckets has a unique bucket index.
10. The system of claim 9 , wherein each bucket has four quadwords, three of the four quadwords store values and a fourth quadword stores the link reference.
11. The system of claim 7 , wherein the operations further comprise:
attempting to add a key/value pair to a tablet;
upon determining filter buckets for a fingerprint corresponding to the key are full in the Cuckoo filter table:
selecting an empty stash bucket from the value store;
entering the key and stash bucket identifier to the key hash table; and
adding the value of the key/value pair to an available slot in the bucket in the value store.
12. The system of claim 7 , wherein the operations further comprise:
receiving a request to find a key in the Cuckoo tree;
searching the Stash for the key;
returning, by the Stash, a first bitmap for the key;
searching the Cuckoo filter table for the key;
returning, by the Cuckoo filter table, a second bitmap for the key;
merging data in the first and second bitmaps to produce a third bitmap; and
searching tablets for the key using the third bitmap.
13. A computer program product for implementing a Cuckoo tree with duplicate key support in a storage system, the computer program product embodied on a non-transitory computer readable medium, the computer program product including instructions that, when executed by a computer, causes the computer to perform operations comprising:
providing a Cuckoo filter table configured to perform lookups in a Cuckoo tree, the Cuckoo filter table tracking fingerprints of keys and corresponding tablets in which the keys reside;
providing a Stash configured to manage duplicate keys in the Cuckoo tree, the Stash comprising:
a value store; and
a key hash table storing full keys and corresponding bucket index references that point to a reverse time ordered list of values corresponding to the full keys, wherein all of the values that correspond to a given key are stored on a single cache line in a value store, the value store including stash buckets with slots for storing the reverse time ordered list of values;
setting a duplicate threshold value in the Cuckoo tree, the duplicate threshold value providing a limit on a number of fingerprints that can exist in a bucket;
wherein during a store operation on a key, upon determining the number of existing entries with same fingerprint in a target stash bucket would exceed the duplicate threshold another stash bucket is selected for the key.
14. The computer program product of claim 13 , wherein the operations further comprise:
adding a link reference to the target stash bucket that identifies the other bucket.
15. The computer program product of claim 14 , where each cache line in the value store has 8 64-bit quadwords, each cache line is divided into two stash buckets, and each of the stash buckets has a unique bucket index.
16. The computer program product of claim 15 , wherein each bucket has four quadwords, three of the four quadwords store values and a fourth quadword stores the link reference.
17. The computer program product of claim 13 , wherein the operations further comprise:
attempting to add a key/value pair to a tablet;
upon determining filter buckets for a fingerprint corresponding to the key are full in the Cuckoo filter table:
selecting an empty stash bucket from the value store;
entering the key and stash bucket identifier to the key hash table; and
adding the value of the key/value pair to a slot in the stash bucket in the value store.
18. The computer program product of claim 13 , wherein the operations further comprise:
receiving a request to find a key in the Cuckoo tree;
searching the Stash for the key;
returning, by the Stash, a first bitmap for the key;
searching the Cuckoo filter table for the key;
returning, by the Cuckoo filter table, a second bitmap for the key;
merging data in the first and second bitmaps to produce a third bitmap; and
searching tablets for the key using the third bitmap.