This is an automated email from the ASF dual-hosted git repository.
jihuayu pushed a commit to branch unstable
in repository https://gitbox.apache.org/repos/asf/kvrocks.git
The following commit(s) were added to refs/heads/unstable by this push:
new 081053769 feat(CuckooFilter): add cf.exists and cf.mexists command
(#3467)
081053769 is described below
commit 081053769d7b70200e21d7f434ed02c579b8033a
Author: hurukawa <[email protected]>
AuthorDate: Mon Sep 28 10:39:59 2026 +0800
feat(CuckooFilter): add cf.exists and cf.mexists command (#3467)
task id: #3359
This pr is This PR was written using codex and GPT-5.5
---------
Co-authored-by: qiang_liu <[email protected]>
Co-authored-by: 纪华裕 <[email protected]>
---
src/commands/cmd_cuckoo_filter.cc | 64 +++++-
src/storage/redis_metadata.h | 3 +-
src/types/cuckoo_filter_sub_filter.cc | 31 +++
src/types/cuckoo_filter_sub_filter.h | 1 +
src/types/redis_cuckoo_chain.cc | 61 ++++-
src/types/redis_cuckoo_chain.h | 9 +
tests/cppunit/types/cuckoo_filter_test.cc | 254 ++++++++++++++++++++-
tests/gocase/unit/type/bloom/cuckoo_filter_test.go | 94 ++++++++
8 files changed, 511 insertions(+), 6 deletions(-)
diff --git a/src/commands/cmd_cuckoo_filter.cc
b/src/commands/cmd_cuckoo_filter.cc
index 2002912f9..3026662c1 100644
--- a/src/commands/cmd_cuckoo_filter.cc
+++ b/src/commands/cmd_cuckoo_filter.cc
@@ -131,8 +131,68 @@ class CommandCFAdd : public Commander {
}
};
-// Register the CF.RESERVE and CF.ADD commands
+class CommandCFExists : public Commander {
+ public:
+ Status Parse(const std::vector<std::string> &args) override {
+ // CF.EXISTS key item
+ if (args.size() != 3) {
+ return {Status::RedisParseErr, errWrongNumOfArguments};
+ }
+ return Commander::Parse(args);
+ }
+
+ Status Execute(engine::Context &ctx, Server *srv, Connection *conn,
std::string *output) override {
+ redis::CuckooChain cuckoo_db(srv->storage, conn->GetNamespace());
+ bool exists = false;
+ auto s = cuckoo_db.Exists(ctx, args_[1], args_[2], &exists);
+
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = conn->Bool(exists);
+ return Status::OK();
+ }
+};
+
+class CommandCFMExists : public Commander {
+ public:
+ Status Parse(const std::vector<std::string> &args) override {
+ // CF.MEXISTS key item [item ...]
+ if (args.size() < 3) {
+ return {Status::RedisParseErr, errWrongNumOfArguments};
+ }
+ items_.reserve(args.size() - 2);
+ for (size_t i = 2; i < args.size(); ++i) {
+ items_.emplace_back(args[i]);
+ }
+ return Commander::Parse(args);
+ }
+
+ Status Execute(engine::Context &ctx, Server *srv, Connection *conn,
std::string *output) override {
+ redis::CuckooChain cuckoo_db(srv->storage, conn->GetNamespace());
+ std::vector<bool> exists(items_.size(), false);
+ auto s = cuckoo_db.MExists(ctx, args_[1], items_, &exists);
+
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::MultiLen(items_.size());
+ for (bool exist : exists) {
+ *output += conn->Bool(exist);
+ }
+ return Status::OK();
+ }
+
+ private:
+ std::vector<std::string> items_;
+};
+
+// Register the CF.RESERVE, CF.ADD, CF.EXISTS, and CF.MEXISTS commands
REDIS_REGISTER_COMMANDS(CuckooFilter,
MakeCmdAttr<CommandCFReserve>("cf.reserve", -3, "write", 1, 1, 1),
- MakeCmdAttr<CommandCFAdd>("cf.add", 3, "write", 1, 1,
1))
+ MakeCmdAttr<CommandCFAdd>("cf.add", 3, "write", 1, 1,
1),
+ MakeCmdAttr<CommandCFExists>("cf.exists", 3,
"read-only", 1, 1, 1),
+ MakeCmdAttr<CommandCFMExists>("cf.mexists", -3,
"read-only", 1, 1, 1))
} // namespace redis
diff --git a/src/storage/redis_metadata.h b/src/storage/redis_metadata.h
index 3f9a793cb..66e847f44 100644
--- a/src/storage/redis_metadata.h
+++ b/src/storage/redis_metadata.h
@@ -347,7 +347,8 @@ class CuckooChainMetadata : public Metadata {
/// When a filter is full, a new one is created with capacity =
base_capacity * expansion^n
uint16_t expansion;
- /// The capacity of the first filter.
+ /// The capacity of the first filter. Auto-created filters use
kCFDefaultCapacity; CF.RESERVE stores the requested
+ /// capacity.
uint64_t base_capacity;
/// Number of fingerprints per bucket
diff --git a/src/types/cuckoo_filter_sub_filter.cc
b/src/types/cuckoo_filter_sub_filter.cc
index 0a0748cc3..0e631bf2c 100644
--- a/src/types/cuckoo_filter_sub_filter.cc
+++ b/src/types/cuckoo_filter_sub_filter.cc
@@ -45,6 +45,37 @@ rocksdb::Status CuckooSubFilter::TryInsert(uint64_t hash,
uint8_t fingerprint, b
return pages_.TryInsertInBucket(filter_index_, num_buckets_, bucket2_idx,
fingerprint, inserted);
}
+rocksdb::Status CuckooSubFilter::Contains(uint64_t hash, uint8_t fingerprint,
bool *exists) {
+ *exists = false;
+ uint32_t bucket1_idx = getPrimaryBucketIndex(hash);
+ uint32_t bucket2_idx = getSecondaryBucketIndex(hash, fingerprint);
+ auto s = pages_.PrefetchBuckets(filter_index_, num_buckets_, bucket1_idx,
bucket2_idx);
+ if (!s.ok()) return s;
+
+ uint8_t slot = 0;
+ for (size_t i = 0; i < bucket_size_; ++i) {
+ s = pages_.GetBucketSlot(filter_index_, num_buckets_, bucket1_idx,
static_cast<uint32_t>(i), &slot);
+ if (!s.ok()) return s;
+ if (slot == fingerprint) {
+ *exists = true;
+ return rocksdb::Status::OK();
+ }
+ }
+
+ if (bucket1_idx == bucket2_idx) return rocksdb::Status::OK();
+
+ for (size_t i = 0; i < bucket_size_; ++i) {
+ s = pages_.GetBucketSlot(filter_index_, num_buckets_, bucket2_idx,
static_cast<uint32_t>(i), &slot);
+ if (!s.ok()) return s;
+ if (slot == fingerprint) {
+ *exists = true;
+ return rocksdb::Status::OK();
+ }
+ }
+
+ return rocksdb::Status::OK();
+}
+
rocksdb::Status CuckooSubFilter::TryKickOutInsert(uint64_t hash, uint8_t
fingerprint, uint16_t max_iterations,
bool *inserted) {
*inserted = false;
diff --git a/src/types/cuckoo_filter_sub_filter.h
b/src/types/cuckoo_filter_sub_filter.h
index 2bd26df85..d3ca1f170 100644
--- a/src/types/cuckoo_filter_sub_filter.h
+++ b/src/types/cuckoo_filter_sub_filter.h
@@ -39,6 +39,7 @@ class CuckooSubFilter {
uint32_t NumBuckets() const { return num_buckets_; }
rocksdb::Status TryInsert(uint64_t hash, uint8_t fingerprint, bool
*inserted);
+ rocksdb::Status Contains(uint64_t hash, uint8_t fingerprint, bool *exists);
// Performs speculative kick-out mutations in the page cache. On success,
dirty pages remain staged for
// WriteToBatch(); on inserted=false or non-OK status, cached pages are
discarded before returning.
rocksdb::Status TryKickOutInsert(uint64_t hash, uint8_t fingerprint,
uint16_t max_iterations, bool *inserted);
diff --git a/src/types/redis_cuckoo_chain.cc b/src/types/redis_cuckoo_chain.cc
index f7074ce94..ef74d17b0 100644
--- a/src/types/redis_cuckoo_chain.cc
+++ b/src/types/redis_cuckoo_chain.cc
@@ -60,7 +60,7 @@ rocksdb::Status CuckooChain::Reserve(engine::Context &ctx,
const Slice &user_key
return rocksdb::Status::InvalidArgument("capacity must be larger than 0");
}
- // RedisBloom requires minimum capacity to ensure at least one bucket can be
created
+ // Require minimum capacity to ensure at least one bucket can be created
// With load factor 0.955, capacity=1 and bucket_size=4 results in 0 buckets
if (capacity < 2) {
return rocksdb::Status::InvalidArgument("capacity must be at least 2");
@@ -291,4 +291,63 @@ rocksdb::Status
CuckooChain::commitSubFilterAndMetadata(engine::Context &ctx, co
return storage_->Write(ctx, storage_->DefaultWriteOptions(),
batch->GetWriteBatch());
}
+rocksdb::Status CuckooChain::Exists(engine::Context &ctx, const Slice
&user_key, const Slice &item, bool *exists) {
+ std::vector<bool> result;
+ auto s = MExists(ctx, user_key, std::vector<std::string>{item.ToString()},
&result);
+ if (!s.ok()) return s;
+ *exists = result[0];
+ return rocksdb::Status::OK();
+}
+
+rocksdb::Status CuckooChain::MExists(engine::Context &ctx, const Slice
&user_key, const std::vector<std::string> &items,
+ std::vector<bool> *exists) {
+ exists->assign(items.size(), false);
+ std::string ns_key = AppendNamespacePrefix(user_key);
+
+ CuckooChainMetadata metadata(false);
+ auto s = getCuckooChainMetadata(ctx, ns_key, &metadata);
+ if (s.IsNotFound()) return rocksdb::Status::OK();
+ if (!s.ok()) return s;
+
+ s = validateMetadata(metadata);
+ if (!s.ok()) return s;
+
+ std::vector<uint64_t> hashes(items.size());
+ std::vector<uint8_t> fingerprints(items.size());
+ for (size_t i = 0; i < items.size(); ++i) {
+ hashes[i] = CuckooFilterHelper::Hash(items[i].data(), items[i].size());
+ fingerprints[i] = CuckooFilterHelper::GenerateFingerprint(hashes[i]);
+ CHECK(fingerprints[i] != 0);
+ }
+
+ size_t found_count = 0;
+ for (int filter_idx = static_cast<int>(metadata.n_filters) - 1; filter_idx
>= 0; --filter_idx) {
+ auto current_filter_idx = static_cast<uint16_t>(filter_idx);
+ uint32_t num_buckets = 0;
+ s = CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion, metadata.bucket_size,
+ current_filter_idx,
&num_buckets);
+ if (!s.ok()) return s;
+
+ CuckooSubFilter sub_filter(storage_, ctx, ns_key,
storage_->IsSlotIdEncoded(), metadata.version,
+ metadata.bucket_size, metadata.page_size,
current_filter_idx, num_buckets);
+ for (size_t i = 0; i < items.size(); ++i) {
+ if ((*exists)[i]) continue;
+
+ bool item_exists = false;
+ s = sub_filter.Contains(hashes[i], fingerprints[i], &item_exists);
+ if (!s.ok()) return s;
+ if (item_exists) {
+ (*exists)[i] = true;
+ ++found_count;
+ }
+ }
+
+ if (found_count == items.size()) {
+ break;
+ }
+ }
+
+ return rocksdb::Status::OK();
+}
+
} // namespace redis
diff --git a/src/types/redis_cuckoo_chain.h b/src/types/redis_cuckoo_chain.h
index ae20b056c..d3a4381e5 100644
--- a/src/types/redis_cuckoo_chain.h
+++ b/src/types/redis_cuckoo_chain.h
@@ -20,6 +20,8 @@
#pragma once
+#include <vector>
+
#include "cuckoo_filter.h"
#include "storage/redis_db.h"
#include "storage/redis_metadata.h"
@@ -47,6 +49,13 @@ class CuckooChain : public Database {
// Duplicate items are allowed, so added is true whenever insertion succeeds.
rocksdb::Status Add(engine::Context &ctx, const Slice &user_key, const Slice
&item, bool *added);
+ // Returns true if the item might exist, and false if it definitely does not.
+ rocksdb::Status Exists(engine::Context &ctx, const Slice &user_key, const
Slice &item, bool *exists);
+
+ // Returns whether each item might exist in the cuckoo filter.
+ rocksdb::Status MExists(engine::Context &ctx, const Slice &user_key, const
std::vector<std::string> &items,
+ std::vector<bool> *exists);
+
private:
// Loads metadata for a cuckoo filter key.
rocksdb::Status getCuckooChainMetadata(engine::Context &ctx, const Slice
&ns_key, CuckooChainMetadata *metadata);
diff --git a/tests/cppunit/types/cuckoo_filter_test.cc
b/tests/cppunit/types/cuckoo_filter_test.cc
index 66a24ad42..8f92263b3 100644
--- a/tests/cppunit/types/cuckoo_filter_test.cc
+++ b/tests/cppunit/types/cuckoo_filter_test.cc
@@ -23,6 +23,7 @@
#include <algorithm>
#include <limits>
#include <memory>
+#include <string>
#include <vector>
#include "common/encoding.h"
@@ -289,7 +290,7 @@ TEST_F(RedisCuckooFilterTest,
CalculateRequiredBucketsCalculation) {
TEST_F(RedisCuckooFilterTest, FingerprintGeneration) {
// Test fingerprint generation ensures non-zero values in range [1, 255]
- // Following RedisBloom: fp = hash % 255 + 1
+ // Standard implementation: fp = hash % 255 + 1
for (uint64_t hash = 0; hash < 1000; ++hash) {
uint8_t fp = redis::CuckooFilterHelper::GenerateFingerprint(hash);
ASSERT_GE(fp, 1) << "Fingerprint should be at least 1";
@@ -306,7 +307,7 @@ TEST_F(RedisCuckooFilterTest, FingerprintGeneration) {
TEST_F(RedisCuckooFilterTest, AlternateBucketCalculation) {
std::vector<uint32_t> num_buckets_cases = {1, 2, 128, 256, 512, 1024, 2048};
- // Test GetAltHash symmetry at hash level (following RedisBloom design)
+ // Test GetAltHash symmetry property
// h2 = GetAltHash(fp, h1)
// h1 = GetAltHash(fp, h2) <- this is the symmetry property
for (auto num_buckets : num_buckets_cases) {
@@ -743,3 +744,252 @@ TEST_F(RedisCuckooFilterTest,
ExpansionWritesNewFilterIndexPage) {
ASSERT_TRUE(s.ok()) << s.ToString();
EXPECT_EQ(page.size(), expected_page_size);
}
+
+TEST_F(RedisCuckooFilterTest, ExistsBasic) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ addAndVerify(key_, "test_item", 1000, 4, 500, 2, 1);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, "test_item", &exists);
+ ASSERT_TRUE(s.ok()) << "Failed to check existence: " << s.ToString();
+ ASSERT_TRUE(exists) << "Item should exist";
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsNonExistentItem) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ addAndVerify(key_, "item1", 1000, 4, 500, 2, 1);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, "item2", &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_FALSE(exists) << "Item should not exist";
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsNonExistentFilter) {
+ bool exists = true;
+ auto s = cuckoo_->Exists(*ctx_, "nonexistent_key", "item", &exists);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_FALSE(exists);
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsMultipleItems) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+
+ std::vector<std::string> items = {"apple", "banana", "cherry", "date",
"elderberry"};
+ for (size_t i = 0; i < items.size(); ++i) {
+ addAndVerify(key_, items[i], 1000, 4, 500, 2, i + 1);
+ }
+
+ for (const auto &item : items) {
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, item, &exists);
+ ASSERT_TRUE(s.ok()) << "Failed to check: " << item;
+ ASSERT_TRUE(exists) << "Item should exist: " << item;
+ }
+
+ std::vector<std::string> non_items = {"fig", "grape", "honeydew"};
+ for (const auto &item : non_items) {
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_FALSE(exists) << "Item should not exist: " << item;
+ }
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsDuplicateItems) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+
+ std::string item = "duplicate_item";
+ for (int i = 0; i < 3; ++i) {
+ addAndVerify(key_, item, 1000, 4, 500, 2, i + 1);
+ }
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Duplicate item should exist";
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsEmptyString) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ addAndVerify(key_, "", 1000, 4, 500, 2, 1);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, "", &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Empty string should exist";
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsBinaryData) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ std::string binary_item = std::string("\x00\x01\x02\xFF\xFE", 5);
+ addAndVerify(key_, binary_item, 1000, 4, 500, 2, 1);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, binary_item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Binary data should exist";
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsAfterExpansion) {
+ reserveAndVerify(key_, 10, 2, 500, 2);
+
+ std::vector<std::string> items;
+ items.reserve(30);
+ for (int i = 0; i < 30; ++i) {
+ items.push_back("item_" + std::to_string(i));
+ }
+
+ for (const auto &item : items) {
+ bool added = false;
+ auto s = cuckoo_->Add(*ctx_, key_, item, &added);
+ if (s.ok() && added) {
+ bool exists = false;
+ s = cuckoo_->Exists(*ctx_, key_, item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Item should exist: " << item;
+ }
+ }
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsWithDifferentBucketSizes) {
+ std::vector<uint8_t> bucket_sizes = {1, 2, 4, 8};
+
+ for (size_t i = 0; i < bucket_sizes.size(); ++i) {
+ std::string test_key = key_ + "_bucket_" + std::to_string(bucket_sizes[i]);
+ reserveAndVerify(test_key, 100, bucket_sizes[i], 500, 2);
+
+ std::vector<std::string> items = {"item1", "item2", "item3"};
+ for (size_t j = 0; j < items.size(); ++j) {
+ addAndVerify(test_key, items[j], 100, bucket_sizes[i], 500, 2, j + 1);
+ }
+
+ for (const auto &item : items) {
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, test_key, item, &exists);
+ ASSERT_TRUE(s.ok()) << "bucket_size=" <<
static_cast<int>(bucket_sizes[i]);
+ ASSERT_TRUE(exists) << "Item should exist with bucket_size=" <<
static_cast<int>(bucket_sizes[i]);
+ }
+ }
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsLongString) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ std::string long_item(10000, 'x');
+ addAndVerify(key_, long_item, 1000, 4, 500, 2, 1);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, long_item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Long string should exist";
+
+ std::string different_long_item(10000, 'y');
+ exists = false;
+ s = cuckoo_->Exists(*ctx_, key_, different_long_item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_FALSE(exists) << "Different long string should not exist";
+}
+
+TEST_F(RedisCuckooFilterTest, MExistsBasic) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ addAndVerify(key_, "alpha", 1000, 4, 500, 2, 1);
+ addAndVerify(key_, "gamma", 1000, 4, 500, 2, 2);
+
+ std::vector<bool> exists;
+ auto s = cuckoo_->MExists(*ctx_, key_, {"alpha", "beta", "gamma"}, &exists);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(exists.size(), 3);
+ EXPECT_TRUE(exists[0]);
+ EXPECT_FALSE(exists[1]);
+ EXPECT_TRUE(exists[2]);
+}
+
+TEST_F(RedisCuckooFilterTest, MExistsNonExistentFilter) {
+ std::vector<bool> exists;
+ auto s = cuckoo_->MExists(*ctx_, "nonexistent_key", {"alpha", "beta"},
&exists);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(exists.size(), 2);
+ EXPECT_FALSE(exists[0]);
+ EXPECT_FALSE(exists[1]);
+}
+
+TEST_F(RedisCuckooFilterTest, MExistsAfterExpansion) {
+ reserveAndVerify(key_, 4, 1, 1, 2);
+
+ std::vector<std::string> inserted_items;
+ for (int i = 0; i < 20; ++i) {
+ std::string item = "expand_item_" + std::to_string(i);
+ bool added = false;
+ auto s = cuckoo_->Add(*ctx_, key_, item, &added);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_TRUE(added);
+ inserted_items.emplace_back(std::move(item));
+ }
+
+ auto metadata = getMetadata(key_);
+ ASSERT_GT(metadata.n_filters, 1);
+ ASSERT_EQ(metadata.size, 20);
+
+ std::vector<bool> exists;
+ auto s = cuckoo_->MExists(*ctx_, key_, {inserted_items.front(),
"definitely_absent", inserted_items.back()}, &exists);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(exists.size(), 3);
+ EXPECT_TRUE(exists[0]);
+ EXPECT_FALSE(exists[1]);
+ EXPECT_TRUE(exists[2]);
+}
+
+TEST_F(RedisCuckooFilterTest, MExistsStopsAfterAllItemsFoundInNewestFilter) {
+ CuckooChainMetadata metadata;
+ metadata.size = 0;
+ metadata.base_capacity = 1000;
+ metadata.bucket_size = 4;
+ metadata.max_iterations = 500;
+ metadata.expansion = 2;
+ metadata.n_filters = 2;
+ metadata.num_deleted_items = 0;
+ metadata.page_size = kCuckooFilterDefaultPageSize;
+ writeMetadata(key_, metadata);
+
+ writePage(makePageKey(key_, metadata, 0, 0), "corrupt");
+
+ addAndVerify(key_, "alpha", metadata.base_capacity, metadata.bucket_size,
metadata.max_iterations, metadata.expansion,
+ 1, metadata.n_filters);
+ addAndVerify(key_, "beta", metadata.base_capacity, metadata.bucket_size,
metadata.max_iterations, metadata.expansion,
+ 2, metadata.n_filters);
+
+ std::vector<bool> exists;
+ auto s = cuckoo_->MExists(*ctx_, key_, {"alpha", "beta"}, &exists);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(exists.size(), 2);
+ EXPECT_TRUE(exists[0]);
+ EXPECT_TRUE(exists[1]);
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsBatchTest) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+
+ for (int x = 0; x < 100; ++x) {
+ addAndVerify(key_, std::to_string(x), 1000, 4, 500, 2, x + 1);
+ }
+
+ for (int x = 0; x < 100; ++x) {
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, std::to_string(x), &exists);
+ ASSERT_TRUE(s.ok()) << "Failed to check item " << x;
+ ASSERT_TRUE(exists) << "Item " << x << " should exist";
+ }
+}
+
+TEST_F(RedisCuckooFilterTest, ExistsWithRepeatedInsertions) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+
+ std::string item = "k1";
+ addAndVerify(key_, item, 1000, 4, 500, 2, 1);
+ addAndVerify(key_, item, 1000, 4, 500, 2, 2);
+
+ bool exists = false;
+ auto s = cuckoo_->Exists(*ctx_, key_, item, &exists);
+ ASSERT_TRUE(s.ok());
+ ASSERT_TRUE(exists) << "Item should exist after duplicate insertions";
+}
diff --git a/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
b/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
index 852dde75e..89048dd80 100644
--- a/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
+++ b/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
@@ -49,6 +49,48 @@ func TestCuckooFilter(t *testing.T) {
require.ErrorContains(t, rdb.Do(ctx, "cf.add", key,
"item").Err(), "WRONGTYPE")
})
+ t.Run("CF.EXISTS missing key returns false", func(t *testing.T) {
+ key := "test_cuckoo_filter_exists_missing_key"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.Equal(t, false, rdb.Do(ctx, "cf.exists", key,
"item").Val())
+ })
+
+ t.Run("CF.EXISTS existing and absent item", func(t *testing.T) {
+ key := "test_cuckoo_filter_exists_items"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"present").Val())
+ require.Equal(t, true, rdb.Do(ctx, "cf.exists", key,
"present").Val())
+ require.Equal(t, false, rdb.Do(ctx, "cf.exists", key,
"absent").Val())
+ })
+
+ t.Run("CF.MEXISTS returns ordered booleans", func(t *testing.T) {
+ key := "test_cuckoo_filter_mexists_ordered"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"alpha").Val())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"gamma").Val())
+ require.Equal(t, []interface{}{true, false, true}, rdb.Do(ctx,
"cf.mexists", key, "alpha", "beta", "gamma").Val())
+ })
+
+ t.Run("CF.EXISTS wrong type returns WRONGTYPE", func(t *testing.T) {
+ key := "test_cuckoo_filter_exists_wrong_type"
+ require.NoError(t, rdb.Set(ctx, key, "value", 0).Err())
+ require.ErrorContains(t, rdb.Do(ctx, "cf.exists", key,
"item").Err(), "WRONGTYPE")
+ })
+
+ t.Run("CF.MEXISTS wrong type returns WRONGTYPE", func(t *testing.T) {
+ key := "test_cuckoo_filter_mexists_wrong_type"
+ require.NoError(t, rdb.Set(ctx, key, "value", 0).Err())
+ require.ErrorContains(t, rdb.Do(ctx, "cf.mexists", key,
"item1", "item2").Err(), "WRONGTYPE")
+ })
+
+ t.Run("CF.EXISTS and CF.MEXISTS wrong number of arguments", func(t
*testing.T) {
+ require.Error(t, rdb.Do(ctx, "cf.exists").Err())
+ require.Error(t, rdb.Do(ctx, "cf.exists", "key_only").Err())
+ require.Error(t, rdb.Do(ctx, "cf.exists", "key", "item1",
"item2").Err())
+ require.Error(t, rdb.Do(ctx, "cf.mexists").Err())
+ require.Error(t, rdb.Do(ctx, "cf.mexists", "key_only").Err())
+ })
+
t.Run("Reserve expansion", func(t *testing.T) {
require.NoError(t, rdb.Do(ctx, "cf.reserve",
"test_cuckoo_filter_expansion_256", "1000", "EXPANSION", "256").Err())
require.NoError(t, rdb.Do(ctx, "cf.reserve",
"test_cuckoo_filter_expansion_max", "1000", "EXPANSION", "32768").Err())
@@ -142,6 +184,20 @@ func TestCuckooFilter(t *testing.T) {
}
})
+ t.Run("CF.EXISTS and CF.MEXISTS after expansion", func(t *testing.T) {
+ key := "test_cuckoo_filter_exists_after_expansion"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.NoError(t, rdb.Do(ctx, "cf.reserve", key, "4",
"BUCKETSIZE", "1", "MAXITERATIONS", "1", "EXPANSION", "2").Err())
+ for i := 0; i < 20; i++ {
+ result := rdb.Do(ctx, "cf.add", key,
fmt.Sprintf("expand_item_%d", i))
+ require.NoError(t, result.Err())
+ require.Equal(t, int64(1), result.Val())
+ }
+ require.Equal(t, true, rdb.Do(ctx, "cf.exists", key,
"expand_item_0").Val())
+ require.Equal(t, true, rdb.Do(ctx, "cf.exists", key,
"expand_item_19").Val())
+ require.Equal(t, []interface{}{true, false, true}, rdb.Do(ctx,
"cf.mexists", key, "expand_item_0", "not_inserted", "expand_item_19").Val())
+ })
+
t.Run("Add to full non-scaling filter returns error", func(t
*testing.T) {
key := "test_cuckoo_filter_full_nonscaling"
require.NoError(t, rdb.Del(ctx, key).Err())
@@ -188,3 +244,41 @@ func TestCuckooFilter(t *testing.T) {
require.Equal(t, int64(1), result.Val())
})
}
+
+func TestCuckooFilterRESP3(t *testing.T) {
+ srv := util.StartServer(t, map[string]string{
+ "resp3-enabled": "yes",
+ })
+ defer srv.Close()
+
+ c := srv.NewTCPClient()
+ defer func() { require.NoError(t, c.Close()) }()
+
+ require.NoError(t, c.WriteArgs("HELLO", "3"))
+ for _, line := range []string{
+ "%6",
+ "$6", "server", "$5", "redis",
+ "$7", "version", "$5", "7.0.0",
+ "$5", "proto", ":3",
+ "$4", "mode", "$10", "standalone",
+ "$4", "role", "$6", "master",
+ "$7", "modules", "_",
+ } {
+ c.MustRead(t, line)
+ }
+
+ key := "test_cuckoo_filter_resp3"
+ require.NoError(t, c.WriteArgs("cf.add", key, "alpha"))
+ c.MustRead(t, ":1")
+
+ require.NoError(t, c.WriteArgs("cf.exists", key, "alpha"))
+ c.MustRead(t, "#t")
+
+ require.NoError(t, c.WriteArgs("cf.exists", key, "beta"))
+ c.MustRead(t, "#f")
+
+ require.NoError(t, c.WriteArgs("cf.mexists", key, "alpha", "beta"))
+ c.MustRead(t, "*2")
+ c.MustRead(t, "#t")
+ c.MustRead(t, "#f")
+}
