Module: SolidCacheMongoid::Entry::Size

Extended by:

ActiveSupport::Concern

Included in:

SolidCacheMongoid::Entry

Defined in:

app/models/solid_cache_mongoid/entry/size/estimate.rb,
app/models/solid_cache_mongoid/entry/size.rb,
app/models/solid_cache_mongoid/entry/size/moving_average_estimate.rb

Overview

Cache size estimation

We store the size of each cache row in the byte_size field. This allows us to estimate the size of the cache by sampling those rows.

To reduce the effect of outliers though we'll grab the N largest rows, and add their size to a sampled based estimate of the size of the remaining rows.

Outliers

There is an index on the byte_size column, so we can efficiently grab the N largest rows. We also grab the minimum byte_size of those rows, which we'll use as a cutoff for the non outlier sampling.

Sampling

To efficiently sample the data we use the key_hash column, which is a random 64 bit integer. There's an index on key_hash and byte_size so we can grab a sum of the byte_sizes in a range of key_hash directly from that index.

To decide how big the range should be, we need the number of documents in the collection. Upstream Solid Cache subtracts the smallest primary key from the largest, which is cheap and accurate with an autoincrementing integer. ObjectIds cannot be subtracted that way, so here Entry.id_range counts the documents instead.

We then calculate the fraction of the rows we want to sample by dividing the sample size by the estimated number of rows.

Then we grab the byte_size sum of the rows in the range of key_hash values excluding any rows that are larger than our minimum outlier cutoff. We then divide this by the sampling fraction to get an estimate of the size of the non outlier rows

Equations

Given N samples and a key_hash range of Kmin..Kmax

outliers_cutoff              OC = min(byte_size of N largest rows)
outliers_size                OS = sum(byte_size of N largest rows)

estimated number of rows     R = number of documents in the collection
sample_fraction              F = N / R
sample_range_size            S = (Kmax - Kmin) * F
sample range is              K1..K2 where K1 = Kmin + rand(Kmax - S) and K2 = K1 + S

non_outlier_sample_size      NSS = sum(byte_size of rows in key_hash range K1..K2 where byte_size <= OC)
non_outlier_estimated_size   NES = NSS / F
estimated_size               ES = OS + NES

Defined Under Namespace

Classes: Estimate, MovingAverageEstimate