one bloom filter for all of cachememorylayerde/bloom-filter-experiment

4 files changed, 54 insertions, 21 deletions

diff --git a/src/zencore/bloomfilter.cpp b/src/zencore/bloomfilter.cpp
index 90dd3b031..3a396026f 100644
--- a/src/zencore/bloomfilter.cpp
+++ b/src/zencore/bloomfilter.cpp
@@ -16,7 +16,7 @@ bloomfilter_forcelink()
 
 TEST_CASE("bloomfilter.basics")
 {
-	BloomFilter65536<Oid, Oid::Hasher> Bloom;
+	BloomFilter<Oid, Oid::Hasher, 256> Bloom;
 	Oid								   Key1 = Oid::NewOid();
 	CHECK(Bloom.Test(Key1) == false);
 	Bloom.Set(Key1);
diff --git a/src/zencore/include/zencore/bloomfilter.h b/src/zencore/include/zencore/bloomfilter.h
index 5f17b0031..1cb99e526 100644
--- a/src/zencore/include/zencore/bloomfilter.h
+++ b/src/zencore/include/zencore/bloomfilter.h
@@ -9,10 +9,11 @@
 
 namespace zen {
 
-template<typename T, typename Hasher>
-class BloomFilter65536
+template<typename T, typename Hasher, size_t BitCount>
+class BloomFilter
 {
 public:
+	static_assert((BitCount & 0x1f) == 0);
 	bool Test(const T& Key) const
 	{
 		uint64_t Hash = Hasher{}(Key);
@@ -36,9 +37,9 @@ public:
 
 	void Reset()
 	{
-		for (size_t I = 0; I < 0x800; I++)
+		for (size_t I = 0; I < BitCount / 32; I++)
 		{
-			m_Bits[I].store(0);
+			m_Bits[I].store(0, std::memory_order_relaxed);
 		}
 	}
 
@@ -61,18 +62,18 @@ private:
 
 	inline bool TestHashBit(uint64_t Hash) const
 	{
-		uint32_t Uint32A = (Hash >> 0x20) & 0x7ff;
+		uint32_t Uint32A = (Hash >> 0x20) & (BitCount / 32 - 1);
 		uint32_t BitA	 = 1u << (Hash & 0x1f);
-		return (m_Bits[Uint32A].load() & BitA) != 0;
+		return (m_Bits[Uint32A].load(std::memory_order_relaxed) & BitA) != 0;
 	}
 
 	inline void SetHashBit(uint64_t Hash)
 	{
-		uint32_t Uint32A = (Hash >> 0x20) & 0x7ff;
+		uint32_t Uint32A = (Hash >> 0x20) & (BitCount / 32 - 1);
 		uint32_t BitA	 = 1u << (Hash & 0x1f);
 		while (true)
 		{
-			uint32_t Bits = m_Bits[Uint32A].load();
+			uint32_t Bits = m_Bits[Uint32A].load(std::memory_order_relaxed);
 			if ((Bits & BitA) != 0)
 			{
 				break;
@@ -83,7 +84,7 @@ private:
 			}
 		}
 	}
-	std::atomic_uint32_t m_Bits[0x800] = {0};
+	std::atomic_uint32_t m_Bits[BitCount / 32] = {0};
 };
 
 void bloomfilter_forcelink();  // internal
diff --git a/src/zenserver/cache/cachememorylayer.cpp b/src/zenserver/cache/cachememorylayer.cpp
index 0588ff8c3..125d2a586 100644
--- a/src/zenserver/cache/cachememorylayer.cpp
+++ b/src/zenserver/cache/cachememorylayer.cpp
@@ -18,11 +18,32 @@ ZenCacheMemoryLayer::~ZenCacheMemoryLayer()
 {
 }
 
+#define BLOOM_FILTER
+//#define BLOOM_FILTER_STATS
+
 bool
 ZenCacheMemoryLayer::Get(std::string_view InBucket, const IoHash& HashKey, ZenCacheValue& OutValue)
 {
 	ZEN_TRACE_CPU("Z$::Mem::Get");
-
+#ifdef BLOOM_FILTER
+#	ifdef BLOOM_FILTER_STATS
+	static std::atomic_uint64_t Gets		   = 0;
+	static std::atomic_uint64_t EarlyReject	   = 0;
+	static std::atomic_uint64_t Accept		   = 0;
+	static std::atomic_uint64_t FalsePositives = 0;
+	Gets++;
+#	endif
+	if (!m_Presence.Test(HashKey))
+	{
+#	ifdef BLOOM_FILTER_STATS
+		EarlyReject++;
+#	endif
+		return false;
+	}
+#	ifdef BLOOM_FILTER_STATS
+	Accept++;
+#	endif
+#endif
 	RwLock::SharedLockScope _(m_Lock);
 
 	auto It = m_Buckets.find(std::string(InBucket));
@@ -40,7 +61,16 @@ ZenCacheMemoryLayer::Get(std::string_view InBucket, const IoHash& HashKey, ZenCa
 	// inserts, the bucket delete path could end up deleting the
 	// underlying data structure
 
+#if defined(BLOOM_FILTER) && defined(BLOOM_FILTER_STATS)
+	if (!Bucket->Get(HashKey, OutValue))
+	{
+		FalsePositives++;
+		return false;
+	}
+	return true;
+#else
 	return Bucket->Get(HashKey, OutValue);
+#endif
 }
 
 void
@@ -78,8 +108,10 @@ ZenCacheMemoryLayer::Put(std::string_view InBucket, const IoHash& HashKey, const
 	}
 
 	// Note that since the underlying IoBuffer is retained, the content type is also
-
 	Bucket->Put(HashKey, Value);
+#ifdef BLOOM_FILTER
+	m_Presence.Set(HashKey);
+#endif
 }
 
 bool
@@ -95,6 +127,8 @@ ZenCacheMemoryLayer::DropBucket(std::string_view InBucket)
 		m_DroppedBuckets.push_back(std::move(It->second));
 		m_Buckets.erase(It);
 		Bucket.Drop();
+
+		m_Presence.Reset();	 // Be sure to reset bloom filter
 		return true;
 	}
 	return false;
@@ -114,11 +148,15 @@ ZenCacheMemoryLayer::Drop()
 		m_Buckets.erase(It->first);
 		Bucket.Drop();
 	}
+
+	m_Presence.Reset();
 }
 
 void
 ZenCacheMemoryLayer::ScrubStorage(ScrubContext& Ctx)
 {
+	m_Presence.Reset();
+
 	RwLock::SharedLockScope _(m_Lock);
 
 	for (auto& Kv : m_Buckets)
@@ -144,6 +182,8 @@ ZenCacheMemoryLayer::GatherAccessTimes(zen::access_tracking::AccessTimes& Access
 void
 ZenCacheMemoryLayer::Reset()
 {
+	m_Presence.Reset();
+
 	RwLock::ExclusiveLockScope _(m_Lock);
 	m_Buckets.clear();
 }
@@ -245,10 +285,6 @@ ZenCacheMemoryLayer::CacheBucket::GatherAccessTimes(std::vector<zen::access_trac
 bool
 ZenCacheMemoryLayer::CacheBucket::Get(const IoHash& HashKey, ZenCacheValue& OutValue)
 {
-	if (!m_Presence.Test(HashKey))
-	{
-		return false;
-	}
 	ZEN_TRACE_CPU("Z$::Mem::Bucket::Get");
 
 	RwLock::SharedLockScope _(m_BucketLock);
@@ -306,7 +342,6 @@ ZenCacheMemoryLayer::CacheBucket::Put(const IoHash& HashKey, const ZenCacheValue
 		ZEN_ASSERT_SLOW(m_Payloads.size() == m_CacheMap.size());
 		ZEN_ASSERT_SLOW(m_AccessTimes.size() == m_Payloads.size());
 	}
-	m_Presence.Set(HashKey);
 
 	m_TotalSize.fetch_add(PayloadSize, std::memory_order::relaxed);
 }
@@ -314,8 +349,6 @@ ZenCacheMemoryLayer::CacheBucket::Put(const IoHash& HashKey, const ZenCacheValue
 void
 ZenCacheMemoryLayer::CacheBucket::Drop()
 {
-	m_Presence.Reset();
-
 	RwLock::ExclusiveLockScope _(m_BucketLock);
 	m_CacheMap.clear();
 	m_AccessTimes.clear();
diff --git a/src/zenserver/cache/cachememorylayer.h b/src/zenserver/cache/cachememorylayer.h
index b0e6a8cd0..01c421500 100644
--- a/src/zenserver/cache/cachememorylayer.h
+++ b/src/zenserver/cache/cachememorylayer.h
@@ -82,8 +82,6 @@ private:
 		static_assert(sizeof(BucketPayload) == 32u);
 		static_assert(sizeof(AccessTime) == 4u);
 
-		BloomFilter65536<IoHash, IoHash::Hasher> m_Presence;
-
 		mutable RwLock					 m_BucketLock;
 		std::vector<AccessTime>			 m_AccessTimes;
 		std::vector<BucketPayload>		 m_Payloads;
@@ -100,6 +98,7 @@ private:
 		uint64_t		EntryCount() const;
 	};
 
+	BloomFilter<IoHash, IoHash::Hasher, 24576>					  m_Presence;
 	mutable RwLock												  m_Lock;
 	std::unordered_map<std::string, std::unique_ptr<CacheBucket>> m_Buckets;
 	std::vector<std::unique_ptr<CacheBucket>>					  m_DroppedBuckets;