Page History

...

From the microbenchmarking, it is shown that for an HFile containing 1M entries, random seeks performs better until 300 to 400k look ups. Beyond that, full file scan (i.e. read entire HFile into in memory hash table and do a look up in the hash table) performs better. So, we could leverage that during our look up. We could store information about total number of entries in each Hfile. During look up, if no of entries to be looked up is < 30%, we could do random look up, if not, we could resort to full table scan. This needs to be flushed out with more finer details though. But something to keep in mind.  

Scaling further

This section is still getting flushed out. Listing the possible options for now. 

Option1: Adding file groups to existing buckets

Lets say with initial estimates, 1000 buckets were pre-allocated. And at some point, if we are reaching the tipping point i.e 1M entires per bucket, we can cap that file group and start a new file group. Remember with compaction in place, all HFiles per file group will be compacted to one HFile. So, if we don't expand to another file group, at some point we could have 2M entries or greater in one HFile which might give us bad performance. So, we ought to cap one file group to say 1M entries and start another file group. So, what this essentially means is that, this bucket of interest is equivalent to two virtual buckets. So, the hashing and number of buckets still remains the same, but our index is capable to scaling with more number of entries. 

Option2: Multiple hash look ups.

First hash can result in bucket 1 to 1000. Once we hit 80% load on these indexes, we could come up with a new hash that would result in buckets 1001 to 2000. So, during index look up, all records will go through two lookups and only one among them should return a value if exists. New writes will go into bucket 1001 to 2000. 

Implementation specifics

...