Where can I find the code for the BlockCache B+ Tree?

[dannycho7]

I am trying to learn more about CacheLib Navy and have been reading parts of the code. One part I am stuck on is finding where the B+ Tree code is. I am interested to see how this tiered mapping of the key hash to save bytes for metadata is implemented.

When I look at navy::Index, the third and fourth byte of the 8-byte key hash appears to identify a bucket in a fixed size array and the last 4 bytes are used as the key for a hash map. Has the implementation changed since the paper and docs were written or maybe I'm misunderstanding the code?

For further context, I am referring to the B tree referenced in both the docs in cachelib.org and the OSDI '20 paper:

• From docs: "Each item is stored in a B tree index in memory. When a read is performed, the region that item is in is promoted in the FIFO queue in memory."
• From the paper: "Keys are hashed to 8B. The first 4B identify the B+-
  tree segment, and the second 4B are used as a key within in a tree segment to lookup a flash location".

[haowu14]

Yes we switched from B-tree to sparse_map after the paper was written. Benchmarking result at that time showed both latency and memory win by this switch.

[haowu14]

Just updated the doc. Thanks for bringing this up!

[dannycho7]

Thank you for the clarification and fix!

[pbhandar2]

Closing this discussion as it has been inactive. If this is still relevant, then please create a new discussion post and we will get back to you as soon as we can. Thank you!