HeavyKeeper

This gem implements HeavyKeeper algorithm, based on the paper with the same name: https://www.usenix.org/conference/atc18/presentation/gong

The interface is designed to be similar with ReBloom TopK datastructure (DS) (https://oss.redis.com/redisbloom/TopK_Commands/).

This is a naive implementation of HeavyKeeper, probably not very optimized. We use multiple Redis DSs:

• A hash with maximum depth * width items to act as a bucket to store main counter
• A sorted set with maximum K elements to act as a MinHeap
• A hash with maximum K elements to store more correct counter of the element in MinHeap

Add this line to your application's Gemfile:

gem 'heavy_keeper'

You will need to add an initializer to provide some configuration:

HeavyKeeper.configure do |config|
  config.cache_prefix = 'cache_prefix'.freeze # currently used as prefix for the redis data structures.
  config.storage = Redis.new # a Redis store, at least version 4.0
end

In general, you will only interact with an instance of the HeavyKeeper::TopK class.

These are the most relevant instance methods (see code comments for more detail):

reserve(name, top_k: size, width:, depth:, decay:) - sets up a Top K list with specified options

increase_by(name, *items) - add an array of items to a list

list(name) - returns full list of items in Top K list

clear(name) - deletes list

remove(name, item) - reset the counter of the targeted item in the list

After checking out the repo, run bin/setup to install dependencies. Then, run bundle exec rspec to run the tests.

To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and the created tag, and push the .gem file to rubygems.org.

Bug reports and pull requests are welcome on GitHub at https://github.com/Kaligo/heavy_keeper.