]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
1 | // Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved. |
2 | // This source code is licensed under both the GPLv2 (found in the | |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
5 | ||
6 | #pragma once | |
7 | ||
8 | #include <array> | |
9 | #include <cassert> | |
10 | #include <cmath> | |
11 | #include <cstdint> | |
12 | ||
13 | #include "port/lang.h" // for FALLTHROUGH_INTENDED | |
14 | #include "rocksdb/rocksdb_namespace.h" | |
15 | ||
16 | namespace ROCKSDB_NAMESPACE { | |
17 | ||
18 | namespace ribbon { | |
19 | ||
20 | // RIBBON PHSF & RIBBON Filter (Rapid Incremental Boolean Banding ON-the-fly) | |
21 | // | |
22 | // ribbon_config.h: APIs for relating numbers of slots with numbers of | |
23 | // additions for tolerable construction failure probabilities. This is | |
24 | // separate from ribbon_impl.h because it might not be needed for | |
25 | // some applications. | |
26 | // | |
27 | // This API assumes uint32_t for number of slots, as a single Ribbon | |
28 | // linear system should not normally overflow that without big penalties. | |
29 | // | |
30 | // Template parameter kCoeffBits uses uint64_t for convenience in case it | |
31 | // comes from size_t. | |
32 | // | |
33 | // Most of the complexity here is trying to optimize speed and | |
34 | // compiled code size, using templates to minimize table look-ups and | |
35 | // the compiled size of all linked look-up tables. Look-up tables are | |
36 | // required because we don't have good formulas, and the data comes | |
37 | // from running FindOccupancy in ribbon_test. | |
38 | ||
39 | // Represents a chosen chance of successful Ribbon construction for a single | |
40 | // seed. Allowing higher chance of failed construction can reduce space | |
41 | // overhead but takes extra time in construction. | |
42 | enum ConstructionFailureChance { | |
43 | kOneIn2, | |
44 | kOneIn20, | |
45 | // When using kHomogeneous==true, construction failure chance should | |
46 | // not generally exceed target FP rate, so it unlikely useful to | |
47 | // allow a higher "failure" chance. In some cases, even more overhead | |
48 | // is appropriate. (TODO) | |
49 | kOneIn1000, | |
50 | }; | |
51 | ||
52 | namespace detail { | |
53 | ||
54 | // It is useful to compile ribbon_test linking to BandingConfigHelper with | |
55 | // settings for which we do not have configuration data, as long as we don't | |
56 | // run the code. This template hack supports that. | |
57 | template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash, | |
58 | bool kHomogeneous, bool kIsSupported> | |
59 | struct BandingConfigHelper1MaybeSupported { | |
60 | public: | |
61 | static uint32_t GetNumToAdd(uint32_t num_slots) { | |
62 | // Unsupported | |
63 | assert(num_slots == 0); | |
64 | (void)num_slots; | |
65 | return 0; | |
66 | } | |
67 | ||
68 | static uint32_t GetNumSlots(uint32_t num_to_add) { | |
69 | // Unsupported | |
70 | assert(num_to_add == 0); | |
71 | (void)num_to_add; | |
72 | return 0; | |
73 | } | |
74 | }; | |
75 | ||
76 | // Base class for BandingConfigHelper1 and helper for BandingConfigHelper | |
77 | // with core implementations built on above data | |
78 | template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash, | |
79 | bool kHomogeneous> | |
80 | struct BandingConfigHelper1MaybeSupported< | |
81 | kCfc, kCoeffBits, kUseSmash, kHomogeneous, true /* kIsSupported */> { | |
82 | public: | |
83 | // See BandingConfigHelper1. Implementation in ribbon_config.cc | |
84 | static uint32_t GetNumToAdd(uint32_t num_slots); | |
85 | ||
86 | // See BandingConfigHelper1. Implementation in ribbon_config.cc | |
87 | static uint32_t GetNumSlots(uint32_t num_to_add); | |
88 | }; | |
89 | ||
90 | } // namespace detail | |
91 | ||
92 | template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash, | |
93 | bool kHomogeneous> | |
94 | struct BandingConfigHelper1 | |
95 | : public detail::BandingConfigHelper1MaybeSupported< | |
96 | kCfc, kCoeffBits, kUseSmash, kHomogeneous, | |
97 | /* kIsSupported */ kCoeffBits == 64 || kCoeffBits == 128> { | |
98 | public: | |
99 | // Returns a number of entries that can be added to a given number of | |
100 | // slots, with roughly kCfc chance of construction failure per seed, | |
101 | // or better. Does NOT do rounding for InterleavedSoln; call | |
102 | // RoundUpNumSlots for that. | |
103 | // | |
104 | // inherited: | |
105 | // static uint32_t GetNumToAdd(uint32_t num_slots); | |
106 | ||
107 | // Returns a number of slots for a given number of entries to add | |
108 | // that should have roughly kCfc chance of construction failure per | |
109 | // seed, or better. Does NOT do rounding for InterleavedSoln; call | |
110 | // RoundUpNumSlots for that. | |
111 | // | |
112 | // num_to_add should not exceed roughly 2/3rds of the maximum value | |
113 | // of the uint32_t type to avoid overflow. | |
114 | // | |
115 | // inherited: | |
116 | // static uint32_t GetNumSlots(uint32_t num_to_add); | |
117 | }; | |
118 | ||
119 | // Configured using TypesAndSettings as in ribbon_impl.h | |
120 | template <ConstructionFailureChance kCfc, class TypesAndSettings> | |
121 | struct BandingConfigHelper1TS | |
122 | : public BandingConfigHelper1< | |
123 | kCfc, | |
124 | /* kCoeffBits */ sizeof(typename TypesAndSettings::CoeffRow) * 8U, | |
125 | TypesAndSettings::kUseSmash, TypesAndSettings::kHomogeneous> {}; | |
126 | ||
127 | // Like BandingConfigHelper1TS except failure chance can be a runtime rather | |
128 | // than compile time value. | |
129 | template <class TypesAndSettings> | |
130 | struct BandingConfigHelper { | |
131 | public: | |
132 | static constexpr ConstructionFailureChance kDefaultFailureChance = | |
133 | TypesAndSettings::kHomogeneous ? kOneIn1000 : kOneIn20; | |
134 | ||
135 | static uint32_t GetNumToAdd( | |
136 | uint32_t num_slots, | |
137 | ConstructionFailureChance max_failure = kDefaultFailureChance) { | |
138 | switch (max_failure) { | |
139 | default: | |
140 | assert(false); | |
141 | FALLTHROUGH_INTENDED; | |
142 | case kOneIn20: { | |
143 | using H1 = BandingConfigHelper1TS<kOneIn20, TypesAndSettings>; | |
144 | return H1::GetNumToAdd(num_slots); | |
145 | } | |
146 | case kOneIn2: { | |
147 | using H1 = BandingConfigHelper1TS<kOneIn2, TypesAndSettings>; | |
148 | return H1::GetNumToAdd(num_slots); | |
149 | } | |
150 | case kOneIn1000: { | |
151 | using H1 = BandingConfigHelper1TS<kOneIn1000, TypesAndSettings>; | |
152 | return H1::GetNumToAdd(num_slots); | |
153 | } | |
154 | } | |
155 | } | |
156 | ||
157 | static uint32_t GetNumSlots( | |
158 | uint32_t num_to_add, | |
159 | ConstructionFailureChance max_failure = kDefaultFailureChance) { | |
160 | switch (max_failure) { | |
161 | default: | |
162 | assert(false); | |
163 | FALLTHROUGH_INTENDED; | |
164 | case kOneIn20: { | |
165 | using H1 = BandingConfigHelper1TS<kOneIn20, TypesAndSettings>; | |
166 | return H1::GetNumSlots(num_to_add); | |
167 | } | |
168 | case kOneIn2: { | |
169 | using H1 = BandingConfigHelper1TS<kOneIn2, TypesAndSettings>; | |
170 | return H1::GetNumSlots(num_to_add); | |
171 | } | |
172 | case kOneIn1000: { | |
173 | using H1 = BandingConfigHelper1TS<kOneIn1000, TypesAndSettings>; | |
174 | return H1::GetNumSlots(num_to_add); | |
175 | } | |
176 | } | |
177 | } | |
178 | }; | |
179 | ||
180 | } // namespace ribbon | |
181 | ||
182 | } // namespace ROCKSDB_NAMESPACE |