diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
commit | e6918187568dbd01842d8d1d2c808ce16a894239 (patch) | |
tree | 64f88b554b444a49f656b6c656111a145cbbaa28 /src/rocksdb/util/ribbon_config.h | |
parent | Initial commit. (diff) | |
download | ceph-upstream/18.2.2.tar.xz ceph-upstream/18.2.2.zip |
Adding upstream version 18.2.2.upstream/18.2.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/rocksdb/util/ribbon_config.h | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/src/rocksdb/util/ribbon_config.h b/src/rocksdb/util/ribbon_config.h new file mode 100644 index 000000000..0e3edf073 --- /dev/null +++ b/src/rocksdb/util/ribbon_config.h @@ -0,0 +1,182 @@ +// 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 |