ribbon_config.h
// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
// This source code is licensed under both the GPLv2 (found in the
// COPYING file in the root directory) and Apache 2.0 License
// (found in the LICENSE.Apache file in the root directory).
#pragma once
#include <array>
#include <cassert>
#include <cmath>
#include <cstdint>
#include "port/lang.h" // for FALLTHROUGH_INTENDED
#include "rocksdb/rocksdb_namespace.h"
namespace ROCKSDB_NAMESPACE {
namespace ribbon {
// RIBBON PHSF & RIBBON Filter (Rapid Incremental Boolean Banding ON-the-fly)
//
// ribbon_config.h: APIs for relating numbers of slots with numbers of
// additions for tolerable construction failure probabilities. This is
// separate from ribbon_impl.h because it might not be needed for
// some applications.
//
// This API assumes uint32_t for number of slots, as a single Ribbon
// linear system should not normally overflow that without big penalties.
//
// Template parameter kCoeffBits uses uint64_t for convenience in case it
// comes from size_t.
//
// Most of the complexity here is trying to optimize speed and
// compiled code size, using templates to minimize table look-ups and
// the compiled size of all linked look-up tables. Look-up tables are
// required because we don't have good formulas, and the data comes
// from running FindOccupancy in ribbon_test.
// Represents a chosen chance of successful Ribbon construction for a single
// seed. Allowing higher chance of failed construction can reduce space
// overhead but takes extra time in construction.
enum ConstructionFailureChance {
kOneIn2,
kOneIn20,
// When using kHomogeneous==true, construction failure chance should
// not generally exceed target FP rate, so it unlikely useful to
// allow a higher "failure" chance. In some cases, even more overhead
// is appropriate. (TODO)
kOneIn1000,
};
namespace detail {
// It is useful to compile ribbon_test linking to BandingConfigHelper with
// settings for which we do not have configuration data, as long as we don't
// run the code. This template hack supports that.
template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash,
bool kHomogeneous, bool kIsSupported>
struct BandingConfigHelper1MaybeSupported {
public:
static uint32_t GetNumToAdd(uint32_t num_slots) {
// Unsupported
assert(num_slots == 0);
(void)num_slots;
return 0;
}
static uint32_t GetNumSlots(uint32_t num_to_add) {
// Unsupported
assert(num_to_add == 0);
(void)num_to_add;
return 0;
}
};
// Base class for BandingConfigHelper1 and helper for BandingConfigHelper
// with core implementations built on above data
template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash,
bool kHomogeneous>
struct BandingConfigHelper1MaybeSupported<
kCfc, kCoeffBits, kUseSmash, kHomogeneous, true /* kIsSupported */> {
public:
// See BandingConfigHelper1. Implementation in ribbon_config.cc
static uint32_t GetNumToAdd(uint32_t num_slots);
// See BandingConfigHelper1. Implementation in ribbon_config.cc
static uint32_t GetNumSlots(uint32_t num_to_add);
};
} // namespace detail
template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash,
bool kHomogeneous>
struct BandingConfigHelper1
: public detail::BandingConfigHelper1MaybeSupported<
kCfc, kCoeffBits, kUseSmash, kHomogeneous,
/* kIsSupported */ kCoeffBits == 64 || kCoeffBits == 128> {
public:
// Returns a number of entries that can be added to a given number of
// slots, with roughly kCfc chance of construction failure per seed,
// or better. Does NOT do rounding for InterleavedSoln; call
// RoundUpNumSlots for that.
//
// inherited:
// static uint32_t GetNumToAdd(uint32_t num_slots);
// Returns a number of slots for a given number of entries to add
// that should have roughly kCfc chance of construction failure per
// seed, or better. Does NOT do rounding for InterleavedSoln; call
// RoundUpNumSlots for that.
//
// num_to_add should not exceed roughly 2/3rds of the maximum value
// of the uint32_t type to avoid overflow.
//
// inherited:
// static uint32_t GetNumSlots(uint32_t num_to_add);
};
// Configured using TypesAndSettings as in ribbon_impl.h
template <ConstructionFailureChance kCfc, class TypesAndSettings>
struct BandingConfigHelper1TS
: public BandingConfigHelper1<
kCfc,
/* kCoeffBits */ sizeof(typename TypesAndSettings::CoeffRow) * 8U,
TypesAndSettings::kUseSmash, TypesAndSettings::kHomogeneous> {};
// Like BandingConfigHelper1TS except failure chance can be a runtime rather
// than compile time value.
template <class TypesAndSettings>
struct BandingConfigHelper {
public:
static constexpr ConstructionFailureChance kDefaultFailureChance =
TypesAndSettings::kHomogeneous ? kOneIn1000 : kOneIn20;
static uint32_t GetNumToAdd(
uint32_t num_slots,
ConstructionFailureChance max_failure = kDefaultFailureChance) {
switch (max_failure) {
default:
assert(false);
FALLTHROUGH_INTENDED;
case kOneIn20: {
using H1 = BandingConfigHelper1TS<kOneIn20, TypesAndSettings>;
return H1::GetNumToAdd(num_slots);
}
case kOneIn2: {
using H1 = BandingConfigHelper1TS<kOneIn2, TypesAndSettings>;
return H1::GetNumToAdd(num_slots);
}
case kOneIn1000: {
using H1 = BandingConfigHelper1TS<kOneIn1000, TypesAndSettings>;
return H1::GetNumToAdd(num_slots);
}
}
}
static uint32_t GetNumSlots(
uint32_t num_to_add,
ConstructionFailureChance max_failure = kDefaultFailureChance) {
switch (max_failure) {
default:
assert(false);
FALLTHROUGH_INTENDED;
case kOneIn20: {
using H1 = BandingConfigHelper1TS<kOneIn20, TypesAndSettings>;
return H1::GetNumSlots(num_to_add);
}
case kOneIn2: {
using H1 = BandingConfigHelper1TS<kOneIn2, TypesAndSettings>;
return H1::GetNumSlots(num_to_add);
}
case kOneIn1000: {
using H1 = BandingConfigHelper1TS<kOneIn1000, TypesAndSettings>;
return H1::GetNumSlots(num_to_add);
}
}
}
};
} // namespace ribbon
} // namespace ROCKSDB_NAMESPACE