basho/riak_core — pull request #633 by jtuple (2014-10-07 02:14:10+00:00)
Title: Implement key count estimation via AAE trees

This pull-request adds `hashtree:estimate_keys/1` which can be used to estimate the number of keys in a partition by sampling the segments in the relevant AAE tree.

The estimation is calculated by computing a keys-per-segment estimate and then multiplying that estimate by the total number of segments.

The keys-per-segment estimate is determined by traversing over segments until either 1% of segments have been sampled or 1000 keys have been seen.

This key count estimation is used as part of an improvement to AAE-based fullsync replication.