1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2013 Inktank <info@inktank.com>
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
15 #ifndef CEPH_OSD_HITSET_H
16 #define CEPH_OSD_HITSET_H
18 #include <boost/scoped_ptr.hpp>
20 #include "include/encoding.h"
21 #include "include/unordered_set.h"
22 #include "common/bloom_filter.hpp"
23 #include "common/hobject.h"
26 * generic container for a HitSet
28 * Encapsulate a HitSetImpl of any type. Expose a generic interface
29 * to users and wrap the encoded object with a type so that it can be
30 * safely decoded later.
37 TYPE_EXPLICIT_HASH = 1,
38 TYPE_EXPLICIT_OBJECT = 2,
42 static const char *get_type_name(impl_type_t t) {
44 case TYPE_NONE: return "none";
45 case TYPE_EXPLICIT_HASH: return "explicit_hash";
46 case TYPE_EXPLICIT_OBJECT: return "explicit_object";
47 case TYPE_BLOOM: return "bloom";
48 default: return "???";
51 const char *get_type_name() const {
53 return get_type_name(impl->get_type());
54 return get_type_name(TYPE_NONE);
57 /// abstract interface for a HitSet implementation
60 virtual impl_type_t get_type() const = 0;
61 virtual bool is_full() const = 0;
62 virtual void insert(const hobject_t& o) = 0;
63 virtual bool contains(const hobject_t& o) const = 0;
64 virtual unsigned insert_count() const = 0;
65 virtual unsigned approx_unique_insert_count() const = 0;
66 virtual void encode(bufferlist &bl) const = 0;
67 virtual void decode(bufferlist::iterator& p) = 0;
68 virtual void dump(Formatter *f) const = 0;
69 virtual Impl* clone() const = 0;
70 virtual void seal() {}
74 boost::scoped_ptr<Impl> impl;
78 /// create an Impl* of the given type
79 bool create_impl(impl_type_t t);
84 virtual impl_type_t get_type() const = 0;
85 virtual HitSet::Impl *get_new_impl() const = 0;
86 virtual void encode(bufferlist &bl) const {}
87 virtual void decode(bufferlist::iterator& p) {}
88 virtual void dump(Formatter *f) const {}
89 virtual void dump_stream(ostream& o) const {}
94 explicit Params(Impl *i) : impl(i) {}
97 boost::scoped_ptr<Params::Impl> impl;
99 impl_type_t get_type() const {
101 return impl->get_type();
105 Params(const Params& o);
106 const Params& operator=(const Params& o);
108 void encode(bufferlist &bl) const;
109 void decode(bufferlist::iterator &bl);
110 void dump(Formatter *f) const;
111 static void generate_test_instances(list<HitSet::Params*>& o);
113 friend ostream& operator<<(ostream& out, const HitSet::Params& p);
116 HitSet() : impl(NULL), sealed(false) {}
117 explicit HitSet(Impl *i) : impl(i), sealed(false) {}
118 explicit HitSet(const HitSet::Params& params);
120 HitSet(const HitSet& o) {
123 impl.reset(o.impl->clone());
127 const HitSet& operator=(const HitSet& o) {
130 impl.reset(o.impl->clone());
137 bool is_full() const {
138 return impl->is_full();
140 /// insert a hash into the set
141 void insert(const hobject_t& o) {
144 /// query whether a hash is in the set
145 bool contains(const hobject_t& o) const {
146 return impl->contains(o);
149 unsigned insert_count() const {
150 return impl->insert_count();
152 unsigned approx_unique_insert_count() const {
153 return impl->approx_unique_insert_count();
161 void encode(bufferlist &bl) const;
162 void decode(bufferlist::iterator &bl);
163 void dump(Formatter *f) const;
164 static void generate_test_instances(list<HitSet*>& o);
167 void reset_to_type(impl_type_t type);
169 WRITE_CLASS_ENCODER(HitSet)
170 WRITE_CLASS_ENCODER(HitSet::Params)
172 typedef boost::shared_ptr<HitSet> HitSetRef;
174 ostream& operator<<(ostream& out, const HitSet::Params& p);
177 * explicitly enumerate hash hits in the set
179 class ExplicitHashHitSet : public HitSet::Impl {
181 ceph::unordered_set<uint32_t> hits;
183 class Params : public HitSet::Params::Impl {
185 HitSet::impl_type_t get_type() const override {
186 return HitSet::TYPE_EXPLICIT_HASH;
188 HitSet::Impl *get_new_impl() const override {
189 return new ExplicitHashHitSet;
191 static void generate_test_instances(list<Params*>& o) {
192 o.push_back(new Params);
196 ExplicitHashHitSet() : count(0) {}
197 explicit ExplicitHashHitSet(const ExplicitHashHitSet::Params *p) : count(0) {}
198 ExplicitHashHitSet(const ExplicitHashHitSet &o) : count(o.count),
201 HitSet::Impl *clone() const override {
202 return new ExplicitHashHitSet(*this);
205 HitSet::impl_type_t get_type() const override {
206 return HitSet::TYPE_EXPLICIT_HASH;
208 bool is_full() const override {
211 void insert(const hobject_t& o) override {
212 hits.insert(o.get_hash());
215 bool contains(const hobject_t& o) const override {
216 return hits.count(o.get_hash());
218 unsigned insert_count() const override {
221 unsigned approx_unique_insert_count() const override {
224 void encode(bufferlist &bl) const override {
225 ENCODE_START(1, 1, bl);
230 void decode(bufferlist::iterator &bl) override {
236 void dump(Formatter *f) const override;
237 static void generate_test_instances(list<ExplicitHashHitSet*>& o) {
238 o.push_back(new ExplicitHashHitSet);
239 o.push_back(new ExplicitHashHitSet);
240 o.back()->insert(hobject_t());
241 o.back()->insert(hobject_t("asdf", "", CEPH_NOSNAP, 123, 1, ""));
242 o.back()->insert(hobject_t("qwer", "", CEPH_NOSNAP, 456, 1, ""));
245 WRITE_CLASS_ENCODER(ExplicitHashHitSet)
248 * explicitly enumerate objects in the set
250 class ExplicitObjectHitSet : public HitSet::Impl {
252 ceph::unordered_set<hobject_t> hits;
254 class Params : public HitSet::Params::Impl {
256 HitSet::impl_type_t get_type() const override {
257 return HitSet::TYPE_EXPLICIT_OBJECT;
259 HitSet::Impl *get_new_impl() const override {
260 return new ExplicitObjectHitSet;
262 static void generate_test_instances(list<Params*>& o) {
263 o.push_back(new Params);
267 ExplicitObjectHitSet() : count(0) {}
268 explicit ExplicitObjectHitSet(const ExplicitObjectHitSet::Params *p) : count(0) {}
269 ExplicitObjectHitSet(const ExplicitObjectHitSet &o) : count(o.count),
272 HitSet::Impl *clone() const override {
273 return new ExplicitObjectHitSet(*this);
276 HitSet::impl_type_t get_type() const override {
277 return HitSet::TYPE_EXPLICIT_OBJECT;
279 bool is_full() const override {
282 void insert(const hobject_t& o) override {
286 bool contains(const hobject_t& o) const override {
287 return hits.count(o);
289 unsigned insert_count() const override {
292 unsigned approx_unique_insert_count() const override {
295 void encode(bufferlist &bl) const override {
296 ENCODE_START(1, 1, bl);
301 void decode(bufferlist::iterator &bl) override {
307 void dump(Formatter *f) const override;
308 static void generate_test_instances(list<ExplicitObjectHitSet*>& o) {
309 o.push_back(new ExplicitObjectHitSet);
310 o.push_back(new ExplicitObjectHitSet);
311 o.back()->insert(hobject_t());
312 o.back()->insert(hobject_t("asdf", "", CEPH_NOSNAP, 123, 1, ""));
313 o.back()->insert(hobject_t("qwer", "", CEPH_NOSNAP, 456, 1, ""));
316 WRITE_CLASS_ENCODER(ExplicitObjectHitSet)
319 * use a bloom_filter to track hits to the set
321 class BloomHitSet : public HitSet::Impl {
322 compressible_bloom_filter bloom;
325 HitSet::impl_type_t get_type() const override {
326 return HitSet::TYPE_BLOOM;
329 class Params : public HitSet::Params::Impl {
331 HitSet::impl_type_t get_type() const override {
332 return HitSet::TYPE_BLOOM;
334 HitSet::Impl *get_new_impl() const override {
335 return new BloomHitSet;
338 uint32_t fpp_micro; ///< false positive probability / 1M
339 uint64_t target_size; ///< number of unique insertions we expect to this HitSet
340 uint64_t seed; ///< seed to use when initializing the bloom filter
343 : fpp_micro(0), target_size(0), seed(0) {}
344 Params(double fpp, uint64_t t, uint64_t s)
345 : fpp_micro(fpp * 1000000.0), target_size(t), seed(s) {}
346 Params(const Params &o)
347 : fpp_micro(o.fpp_micro),
348 target_size(o.target_size),
350 ~Params() override {}
352 double get_fpp() const {
353 return (double)fpp_micro / 1000000.0;
355 void set_fpp(double f) {
356 fpp_micro = (unsigned)(llrintl(f * (double)1000000.0));
359 void encode(bufferlist& bl) const override {
360 ENCODE_START(1, 1, bl);
361 ::encode(fpp_micro, bl);
362 ::encode(target_size, bl);
366 void decode(bufferlist::iterator& bl) override {
368 ::decode(fpp_micro, bl);
369 ::decode(target_size, bl);
373 void dump(Formatter *f) const override;
374 void dump_stream(ostream& o) const override {
375 o << "false_positive_probability: "
376 << get_fpp() << ", target_size: " << target_size
377 << ", seed: " << seed;
379 static void generate_test_instances(list<Params*>& o) {
380 o.push_back(new Params);
381 o.push_back(new Params);
382 (*o.rbegin())->fpp_micro = 123456;
383 (*o.rbegin())->target_size = 300;
384 (*o.rbegin())->seed = 99;
389 BloomHitSet(unsigned inserts, double fpp, int seed)
390 : bloom(inserts, fpp, seed)
392 explicit BloomHitSet(const BloomHitSet::Params *p) : bloom(p->target_size,
397 BloomHitSet(const BloomHitSet &o) {
401 bufferlist::iterator bli = bl.begin();
405 HitSet::Impl *clone() const override {
406 return new BloomHitSet(*this);
409 bool is_full() const override {
410 return bloom.is_full();
413 void insert(const hobject_t& o) override {
414 bloom.insert(o.get_hash());
416 bool contains(const hobject_t& o) const override {
417 return bloom.contains(o.get_hash());
419 unsigned insert_count() const override {
420 return bloom.element_count();
422 unsigned approx_unique_insert_count() const override {
423 return bloom.approx_unique_element_count();
425 void seal() override {
426 // aim for a density of .5 (50% of bit set)
427 double pc = (double)bloom.density() * 2.0;
432 void encode(bufferlist &bl) const override {
433 ENCODE_START(1, 1, bl);
437 void decode(bufferlist::iterator &bl) override {
442 void dump(Formatter *f) const override;
443 static void generate_test_instances(list<BloomHitSet*>& o) {
444 o.push_back(new BloomHitSet);
445 o.push_back(new BloomHitSet(10, .1, 1));
446 o.back()->insert(hobject_t());
447 o.back()->insert(hobject_t("asdf", "", CEPH_NOSNAP, 123, 1, ""));
448 o.back()->insert(hobject_t("qwer", "", CEPH_NOSNAP, 456, 1, ""));
451 WRITE_CLASS_ENCODER(BloomHitSet)