fizz::server::SlidingBloomReplayCache Class Reference

#include <SlidingBloomReplayCache.h>

Inheritance diagram for fizz::server::SlidingBloomReplayCache:

Public Types
using	CellType = uint64_t
using	HashFunction = std::function< CellType(const unsigned char *, size_t)>

Public Member Functions
	SlidingBloomReplayCache (int64_t ttlInSeconds, size_t requestsPerSecond, double acceptableFPR, folly::EventBase *evb)
	~SlidingBloomReplayCache () override=default
void	set (folly::ByteRange query)
bool	test (folly::ByteRange query) const
bool	testAndSet (folly::ByteRange query)
folly::Future< ReplayCacheResult >	check (folly::ByteRange) override
Public Member Functions inherited from fizz::server::ReplayCache
virtual	~ReplayCache ()=default

Private Member Functions
void	clearBucket (size_t bucket)
void	clear ()
void	timeoutExpired () noexceptoverride
Private Member Functions inherited from folly::AsyncTimeout
	AsyncTimeout (TimeoutManager *timeoutManager)
	AsyncTimeout (EventBase *eventBase)
	AsyncTimeout (TimeoutManager *timeoutManager, InternalEnum internal)
	AsyncTimeout (EventBase *eventBase, InternalEnum internal)
	AsyncTimeout ()
virtual	~AsyncTimeout ()
bool	scheduleTimeout (uint32_t milliseconds)
bool	scheduleTimeout (TimeoutManager::timeout_type timeout)
void	cancelTimeout ()
bool	isScheduled () const
void	attachTimeoutManager (TimeoutManager *timeoutManager, InternalEnum internal=InternalEnum::NORMAL)
void	attachEventBase (EventBase *eventBase, InternalEnum internal=InternalEnum::NORMAL)
void	detachTimeoutManager ()
void	detachEventBase ()
const TimeoutManager *	getTimeoutManager ()
struct event *	getEvent ()

Private Attributes
std::chrono::milliseconds	bucketWidthInMs_
size_t	bitSize_
size_t	currentBucket_
std::unique_ptr< CellType[]>	bitBuf_
std::vector< HashFunction >	hashers_

Additional Inherited Members
Private Types inherited from folly::AsyncTimeout
typedef TimeoutManager::InternalEnum	InternalEnum
Static Private Member Functions inherited from folly::AsyncTimeout
template<typename TCallback >
static std::unique_ptr< AsyncTimeout >	make (TimeoutManager &manager, TCallback &&callback)
template<typename TCallback >
static std::unique_ptr< AsyncTimeout >	schedule (TimeoutManager::timeout_type timeout, TimeoutManager &manager, TCallback &&callback)

Detailed Description

Definition at line 23 of file SlidingBloomReplayCache.h.

Member Typedef Documentation

using fizz::server::SlidingBloomReplayCache::CellType = uint64_t

Definition at line 29 of file SlidingBloomReplayCache.h.

using fizz::server::SlidingBloomReplayCache::HashFunction = std::function<CellType(const unsigned char*, size_t)>

Definition at line 30 of file SlidingBloomReplayCache.h.

Constructor & Destructor Documentation

fizz::server::SlidingBloomReplayCache::SlidingBloomReplayCache	(	int64_t	ttlInSeconds,
		size_t	requestsPerSecond,
		double	acceptableFPR,
		folly::EventBase *	evb
	)

Definition at line 56 of file SlidingBloomReplayCache.cpp.

References bitBuf_, bitSize_, bucketWidthInMs_, currentBucket_, hashers_, i, fizz::server::kBucketCount, fizz::server::kHashCount, folly::AsyncTimeout::scheduleTimeout(), seed, and uint64_t.

    : folly::AsyncTimeout(evb) {
  if (acceptableFPR <= 0.0 || acceptableFPR >= 1.0) {
    throw std::runtime_error("false positive rate must lie between 0 and 1");
  }

  // Do all calculations with doubles.
  double ttlDouble = ttlInSecs;
  double rpsDouble = requestsPerSecond;
  double hashCountDouble = kHashCount;
  double bucketCountDouble = kBucketCount;
  double dividend = -hashCountDouble * rpsDouble * ttlDouble;
  double root = pow(acceptableFPR, 1.0 / hashCountDouble);
  double divisor = bucketCountDouble * log(1.0 - root);
  bitSize_ = dividend / divisor;
  VLOG(8) << "Initializing with bitSize = " << bitSize_;

  bucketWidthInMs_ =
      std::chrono::milliseconds(((ttlInSecs * 1000) / kBucketCount) + 1);

  // Reset bit buffer
  bitBuf_.reset(new CellType[bitSize_]());

  // Initialize current bucket
  currentBucket_ = 0;

  // Set up hashers
  for (unsigned int i = 0; i < kHashCount; i++) {
    hashers_.push_back(
        [seed = RandomNumGenerator<uint64_t>().generateRandom()](
            const unsigned char* buf, size_t len) -> uint64_t {
          return SpookyHashV2::Hash64((const void*)buf, len, seed);
        });
  }

  // Schedule reaping function (if evb given)
  if (evb) {
    scheduleTimeout(bucketWidthInMs_.count());
  } else {
    VLOG(8) << "Started replay cache without reaping";
  }
}

fizz::server::SlidingBloomReplayCache::~SlidingBloomReplayCache ( )

overridedefault

Member Function Documentation

folly::Future< ReplayCacheResult > fizz::server::SlidingBloomReplayCache::check ( folly::ByteRange  query )

overridevirtual

Implements fizz::server::ReplayCache.

Definition at line 139 of file SlidingBloomReplayCache.cpp.

References fizz::server::MaybeReplay, folly::gen::move, fizz::server::NotReplay, and testAndSet().

                          {
  return testAndSet(std::move(query)) ? ReplayCacheResult::MaybeReplay
                                      : ReplayCacheResult::NotReplay;
}

void fizz::server::SlidingBloomReplayCache::clear ( )

private

Definition at line 155 of file SlidingBloomReplayCache.cpp.

References clearBucket(), and currentBucket_.

Referenced by timeoutExpired().

                                    {
  // Clear the soon to be occupied bucket
  clearBucket((currentBucket_ + 1) % kBucketCount);

  // Increment current bucket
  currentBucket_ = (currentBucket_ + 1) % kBucketCount;
}

void fizz::server::SlidingBloomReplayCache::clearBucket ( size_t  bucket )

private

Definition at line 145 of file SlidingBloomReplayCache.cpp.

References bitBuf_, bitSize_, currentBucket_, and i.

Referenced by clear().

                                                       {
  VLOG(8) << "Clearing bit " << bucket << ", current bucket is "
          << currentBucket_;

  CellType mask = ~((static_cast<CellType>(1)) << bucket);
  for (size_t i = 0; i < bitSize_; ++i) {
    bitBuf_[i] &= mask;
  }
}

void fizz::server::SlidingBloomReplayCache::set

(

folly::ByteRange

query

)

Definition at line 103 of file SlidingBloomReplayCache.cpp.

References bitBuf_, bitSize_, currentBucket_, folly::Range< Iter >::data(), hashers_, and folly::Range< Iter >::size().

Referenced by fizz::server::test::TEST().

                                                      {
  CellType mask = (static_cast<CellType>(1)) << currentBucket_;

  for (auto& hasher : hashers_) {
    size_t idx = hasher(query.data(), query.size()) % bitSize_;

    bitBuf_[idx] |= mask;
  }
}

bool fizz::server::SlidingBloomReplayCache::test

(

folly::ByteRange

query

)

const

Definition at line 113 of file SlidingBloomReplayCache.cpp.

References bitBuf_, bitSize_, folly::Range< Iter >::data(), hashers_, max, and folly::Range< Iter >::size().

Referenced by fizz::server::test::TEST().

                                                             {
  CellType ret(std::numeric_limits<CellType>::max());

  for (auto& hasher : hashers_) {
    size_t idx = hasher(query.data(), query.size()) % bitSize_;

    ret &= bitBuf_[idx];
  }

  return (ret != 0);
}

bool fizz::server::SlidingBloomReplayCache::testAndSet

(

folly::ByteRange

query

)

Definition at line 125 of file SlidingBloomReplayCache.cpp.

References bitBuf_, bitSize_, currentBucket_, folly::Range< Iter >::data(), hashers_, max, and folly::Range< Iter >::size().

Referenced by check(), and fizz::server::test::TEST().

                                                             {
  CellType ret(std::numeric_limits<CellType>::max());
  CellType mask = (static_cast<CellType>(1)) << currentBucket_;

  for (auto& hasher : hashers_) {
    size_t idx = hasher(query.data(), query.size()) % bitSize_;

    ret &= bitBuf_[idx];
    bitBuf_[idx] |= mask;
  }

  return (ret != 0);
}

void fizz::server::SlidingBloomReplayCache::timeoutExpired ( )

overrideprivatevirtualnoexcept

timeoutExpired() is invoked when the timeout period has expired.

Implements folly::AsyncTimeout.

Definition at line 163 of file SlidingBloomReplayCache.cpp.

References bucketWidthInMs_, clear(), and folly::AsyncTimeout::scheduleTimeout().

                                                      {
  clear();
  scheduleTimeout(bucketWidthInMs_.count());
}

Member Data Documentation

std::unique_ptr<CellType[]> fizz::server::SlidingBloomReplayCache::bitBuf_

private

Definition at line 65 of file SlidingBloomReplayCache.h.

Referenced by clearBucket(), set(), SlidingBloomReplayCache(), test(), and testAndSet().

size_t fizz::server::SlidingBloomReplayCache::bitSize_

private

Definition at line 60 of file SlidingBloomReplayCache.h.

Referenced by clearBucket(), set(), SlidingBloomReplayCache(), test(), and testAndSet().

std::chrono::milliseconds fizz::server::SlidingBloomReplayCache::bucketWidthInMs_

private

Definition at line 59 of file SlidingBloomReplayCache.h.

Referenced by SlidingBloomReplayCache(), and timeoutExpired().

size_t fizz::server::SlidingBloomReplayCache::currentBucket_

private

Definition at line 62 of file SlidingBloomReplayCache.h.

Referenced by clear(), clearBucket(), set(), SlidingBloomReplayCache(), and testAndSet().

std::vector<HashFunction> fizz::server::SlidingBloomReplayCache::hashers_

private

Definition at line 67 of file SlidingBloomReplayCache.h.

Referenced by set(), SlidingBloomReplayCache(), test(), and testAndSet().

---

The documentation for this class was generated from the following files:

• proxygen/fizz/fizz/server/SlidingBloomReplayCache.h
• proxygen/fizz/fizz/server/SlidingBloomReplayCache.cpp