How to deal with a very big hash table?

Question

I'm building an implementation of the dynamo paper, yottastore. Given a key, I need to find which NVMe block stores the data. To do that I hash the key to find the shard where I have an in memory array in which at position [hash] I can find a struct with:

• 32 bit hash (needed for resizing)
• 64 bit pointer to NVMe block
• 32 bit of metadata

The random storage node is: 48 core cpu, 1 tb ram, 24*16 tb SSD

At 128 bit per key-value, it's 64 GB of ram per 16 TB disk, or 1.5 TB of ram in total, way too much.

How could I deal with this?

Options I envisioned:

• Using a btree, but it will make access much slower, and I still have 96 bit of records to deal with

• Pointer compression: I could divide the disks in zones of 256 mb, so for each record I will only need a 16 bit offsets instead of 64 bits. I would also need to store a a 64 bit start for each zone in a separate hash table

• I could mix the approaches, storing a btree to find the zone, and then having an hashmap with offsets

Any other ideas? The array already persists on disk with a LSM tree, I would like to have an in memory copy for fast access.

Answer 1

I am not familiar with yottastore or how NVMEs work. However, let's assume the following (correct me if I am wrong):

You have:

• 64 bit pointer
• 32 bit of metadata

You don't need the hash, I assume, that was only part of your proposed solution?

Instead of a normal btree you could use a critbit tree.

Critbit trees are like btree but the key (= 64bit pointer) is not stored in full. Instead, for all entries whose keys share a common prefix, this prefix is stored only once in memory. E.g. with 8 bit keys, k1=0100010 and k2 = 01000100 there would be one node that stores the common 5 bit prefix 01000 and that has two children k1=010 and k2=100. That way you store only 5 + 2x3 = 11 bits instead of 2x8=16.

As a result you have to store probably only 16-32 bit per pointer + 32bit metadata.

Another big advantage is that you never need rehashing or rebalancing of any sort, that means lookup times and insert/delete times are very predictable. Concurrency can be implemented with a copy-on-write scheme that copyies only one node.

Variant: >2 children per node I think a classic critbit tree has only two children per node. As an optimization (faster & less memory overhead) you can try to split with 2 or more bits per node, i.e. 4 children (or 8 children for 3 bits).

Variant: Prefix sharing btree Just like a normal btree with "n" entries per (leaf) node, but for each leaf node you determine the longest common prefix dynamically and store the for each entry only a 32bit or 16bit value (assuming that all entries in a node typically have a common 32bit or 48bit prefix).

I have an critbit implementation in Java available here.

Answer 2

For each 16 TB ssd, you have 40 GB of RAM. I don't know the prices of server-grade hardware, but with consumer-grade one, 40 GB RAM is about \$100, while 16 TB SSD is about \$1000.

Maybe you just need to make a more balanced system instead of spending money on developers in order to make a small economy on hardware?