ssp_bcount.h

Go to the documentation of this file.

/* Copyright 2005 Ben Hyde
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/** \file ssp_bcount.h
 * \brief Silver Spoon's Bloom Counters, a C include file.
 *
 * This API defines an opaque type ssp_bcount_t which is then used to
 * observe a stream of symbols.  It count, aproximately, the
 * number of times each symbol occurs in the stream during the
 * current window.
 *
 * The counts are a lower bound on the number of times the symbol
 * appears.  A typical use for this abstraction is to filter a
 * huge universe of events to find those events that are happening
 * a lot. For example, you could use it to discover the list of
 * high volume visitors to your web site.  You could use it to find
 * the popular phrases in a corpus of text.  You could use it to
 * find files that should be moved to a cache.
 *
 * The user must provide only two operations on symbols, two hashs.
 * Symbols are represented as void * on the interface.
 *
 * That algorithum used here is a direct decendent of the one
 * described in <>.  See also section 8.1 in <> for a overview.
 *
 */

#include "ssp_items.h"
#include <apr_pools.h>

/** \brief The type ssp_bcount_t is the cornerstone of this API.
 *
 * It is the structure that accumlates the counts and manages
 * the current window.  It is allocated in an apr_pool provided
 * by the user and survives until that pool is cleared.  The
 * functions in this API are all operations upon it.
 */
typedef struct ssp_bcount_s ssp_bcount_t;


/** \brief Create a filter for detecting hot symbols.
 *
 * Instantiate a fresh ssp_bcount_t in the pool given.  The user provides
 * two hash functions that will be used on the symbols counted.
 * Two parameters filter_scale and filter_scatter configure how
 * accurate our estimated counts can be.
 *
 * The counters are a varient of bloom filters.  Unlike a traditional
 * bloom filter, which uses a bit map to manage a set, we allocate
 * a set of counters instead of a set of bits.  The scale sets the
 * size of that set.  Scale is a small integer defining the number
 * of bits used to index the set.  So if you pass in 10, you get a
 * counter set of 2^10th.
 *
 * The scatter is how many counters are incremented when ever a
 * symbol is noted.  It is directly analgous to the number of bits
 * set or each member of the set represented in a bloom filter.
 * Scatter must less than 32.
 */
extern ssp_bcount_t *ssp_bcount_create(apr_pool_t *pool,
                                       ssp_hash_function_t *h1,
                                       ssp_hash_function_t *h2,
                                       apr_uint16_t filter_scale,
                                       apr_uint16_t filter_scatter);

/** \brief Advance the current 
 *
 * Counts are maintained for the current window only.  Given a
 * sequence of calls on this routine c7, c8, c9, c10 the current
 * interval runs from moment of c9 thru the current moment.  For
 * example if this is called each hour at the top of the hour and it
 * is currently 10:35 the current interval is 9:00..10:35.  You can
 * clear all counters by making two calls on this.
 **/
extern void ssp_bcount_tick(ssp_bcount_t *h);

/** \brief Count the occurance of a symbol.
 * 
 * Calls on ssp_bcount_insert notify the counters the passed symbol has
 * just occured.  I.e.  it occured during the current window.
 **/
extern apr_uint32_t ssp_bcount_inc(ssp_bcount_t *h, void *symbol);

/** \brief Fetch the estimated count for this symbol.
 *
 * Does not increment the estimated count.
 **/
apr_uint32_t ssp_bcount_lookup(ssp_bcount_t *h, void *symbol);


/** \brief Rarely used counter state.
 *
 * While generally you needn't know what's in a ssp_bcount_t there
 * are a few applications for direct access.  For example to save
 * and restore it.  Or, for example, you want to use it to estimate
 * the maxium over the set of counts.
 */
struct ssp_bcount_s {
  apr_pool_t *object_pool; /**< Subpool created to hold this and it's children */
  ssp_hash_function_t *h1;     /**< 1st hash function on symbols */
  ssp_hash_function_t *h2;     /**< 2nd hash function on symbols */
  apr_uint32_t scale;          /**< 2^scale is how big the counter space is. */
  apr_uint32_t scatter;        /**< How many counters represent a given symbol */
  apr_uint32_t mask;           /**< Used to map hash bits to index value  */
  apr_uint32_t *counters;      /**< Counters of the current interval */
  apr_uint32_t *next_counters; /**< Counters that become live when we tick. */
};

---