How does FoundationDB store keys with duplicate prefixes?


#1

According to the documentation:

keys starting with 'mytable\' are sorted together (e.g. 'mytable\row1' , 'mytable\row2' , …)

Does this mean that a prefix such as mytable will only be stored once?

For example, if I had 500 keys that all started with mytable, would mytable be stored for all 500 keys, or would it be stored for the first key beginning with mytable, and have subsequent keys just reference the first mytable?

Thanks in advance!


(Alex Miller) #2

No, the mytable\ prefix will be stored 500 times. The directory layer offers a way to reduce mytable\ down to a smaller prefix, at the cost of an extra read.

The feature you’re looking for is called “prefix compression”. It’s being actively worked on as part of a new storage engine called Redwood. Eventually, it will come to replace the ssd storage engine, so you’ll get prefix compression by default, but it will still take some time for the development to reach that point.


#3

@alexmiller Thanks for the help! I have a few questions:

  1. I’ve looked into directories and couldn’t find any mention of them in the C API. Is there a directory layer for C, and if not, is the implementation relatively simple?

  2. Any guesses as to when Redwood will be ready?

Appreciate the help, thanks!


(Anantha Kumaran) #4

directory implementation is not part of the C API. It is implemented as an independent layer on each language bindings. AFAIK, there is no formal spec for the directory layer, so one would have to port the current implementation. But there is a tool called bindings tester to verify the implementation, more information can be found at Creating New Bindings thread