1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ seems like if your hashtable doesn't fit in memory then it doesn't. What is the hash table for? $\endgroup$ Aug 26, 2022 at 22:12
  • $\begingroup$ I use the hash table to find the position on disk of a key. E.g.: given tableName/recordName I get the 64 bit pointer representing the sector number on disk $\endgroup$
    – Mascarpone
    Aug 29, 2022 at 8:32
  • $\begingroup$ Sounds like you have to figure out a way to put the hash table on disk, because the hash table is bigger than your RAM. $\endgroup$ Aug 29, 2022 at 13:48

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you very much, looks like a very good candidate. Let me play with it a couple of days. $\endgroup$
    – Mascarpone
    Aug 29, 2022 at 8:35
1
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Apple and Dell will sell you computers with 1.5TB RAM for about $30,000. $\endgroup$
    – gnasher729
    Aug 28, 2022 at 16:57
  • $\begingroup$ I assure you I'm not trying to save some money, the limits are dictated by the physical layout of the server. To get more ram, I need to wait for next generation DDR5 servers. $\endgroup$
    – Mascarpone
    Aug 29, 2022 at 8:30
  • $\begingroup$ @Bulat Can you show me where you can buy a 16tb SSD for 1000$? Looks like an unreasonably low price. $\endgroup$
    – Mascarpone
    Aug 29, 2022 at 8:41
  • $\begingroup$ @Mascarpone EPYC supports 4 TB RAM: en.wikipedia.org/wiki/Epyc#Second_generation_Epyc_(Rome) $\endgroup$
    – Bulat
    Aug 29, 2022 at 18:51
  • $\begingroup$ @Mascarpone cheapest consumer-grade SSD I've seen was \$130 per 2 TB, so \$1000 per 16 TB. My uneducated guess is that both RAM and SSD with the largest capacity has a disproportionately larger price. Overall, I give an obvious suggestion to use a bit less SSDs or a bit more RAM, but of course, you may have other considerations, and anyway it's interesting problem on its own $\endgroup$
    – Bulat
    Aug 29, 2022 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.