1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
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
|
