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 9ade64a10 feat(CuckooFilter): add cf.del command (#3567)
9ade64a10 is described below
commit 9ade64a10d5e4827d33e880c88aba0c48c0d7a6b
Author: hurukawa <[email protected]>
AuthorDate: Mon Oct 26 11:28:16 2026 +0800
feat(CuckooFilter): add cf.del command (#3567)
part of: #3552
## Summary
Add RedisBloom-compatible `CF.DEL key item` support for Cuckoo Filter.
`CF.DEL` deletes one matching fingerprint occurrence and returns `1`
when a slot is cleared, or `0` when the key/item
is not found. Duplicate inserts require duplicate deletes, matching
RedisBloom behavior.
## Design
The command layer adds `cf.del` as a write command and delegates
deletion to `CuckooChain::Delete`.
Deletion loads the Cuckoo Filter metadata, hashes the item, generates
the fingerprint, then searches sub-filters from
newest to oldest. The first matching slot in either candidate bucket is
cleared, and only one occurrence is removed.
After a successful delete, metadata size is decremented and
`num_deleted_items` is incremented. When the chain has
more than one sub-filter and accumulated deletes exceed 10% of the
remaining item count, an internal compact pass is
triggered. Compact tries to move fingerprints from newer sub-filters
into older ones, removes fully compacted latest
sub-filters, and deletes their persisted page keys to avoid stale data
if the chain expands again later.
Page key construction is shared through small Cuckoo page helpers so
compact cleanup uses the same encoding as normal
page access.
This pr is This PR was written using codex and GPT-5.5
---------
Co-authored-by: 纪华裕 <[email protected]>
---
src/commands/cmd_cuckoo_filter.cc | 26 ++-
src/types/cuckoo_filter.h | 1 +
src/types/cuckoo_filter_page.cc | 13 +-
src/types/cuckoo_filter_page.h | 1 +
src/types/cuckoo_filter_sub_filter.cc | 32 +++
src/types/cuckoo_filter_sub_filter.h | 4 +-
src/types/redis_cuckoo_chain.cc | 51 +++-
src/types/redis_cuckoo_chain.h | 10 +-
tests/cppunit/types/cuckoo_filter_page_test.cc | 37 +++
tests/cppunit/types/cuckoo_filter_test.cc | 259 +++++++++++++++++++++
tests/gocase/unit/type/bloom/cuckoo_filter_test.go | 50 ++++
11 files changed, 474 insertions(+), 10 deletions(-)
diff --git a/src/commands/cmd_cuckoo_filter.cc
b/src/commands/cmd_cuckoo_filter.cc
index 3026662c1..81dd79a6b 100644
--- a/src/commands/cmd_cuckoo_filter.cc
+++ b/src/commands/cmd_cuckoo_filter.cc
@@ -189,9 +189,33 @@ class CommandCFMExists : public Commander {
std::vector<std::string> items_;
};
-// Register the CF.RESERVE, CF.ADD, CF.EXISTS, and CF.MEXISTS commands
+class CommandCFDel : public Commander {
+ public:
+ Status Parse(const std::vector<std::string> &args) override {
+ // CF.DEL 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 deleted = false;
+ auto s = cuckoo_db.Delete(ctx, args_[1], args_[2], &deleted);
+
+ if (!s.ok()) {
+ return {Status::RedisExecErr, s.ToString()};
+ }
+
+ *output = redis::Integer(deleted ? 1 : 0);
+ return Status::OK();
+ }
+};
+
REDIS_REGISTER_COMMANDS(CuckooFilter,
MakeCmdAttr<CommandCFReserve>("cf.reserve", -3, "write", 1, 1, 1),
MakeCmdAttr<CommandCFAdd>("cf.add", 3, "write", 1, 1,
1),
+ MakeCmdAttr<CommandCFDel>("cf.del", 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))
diff --git a/src/types/cuckoo_filter.h b/src/types/cuckoo_filter.h
index 5cd02f0a9..5e7f829d5 100644
--- a/src/types/cuckoo_filter.h
+++ b/src/types/cuckoo_filter.h
@@ -36,6 +36,7 @@ constexpr long double kCuckooFilterLoadFactor = 0.955L;
constexpr uint64_t kCuckooFilterMaxSupportedBuckets =
std::numeric_limits<uint32_t>::max() / 2 + 1ULL;
constexpr uint64_t kCuckooFilterFingerprintModulus = 255;
constexpr uint64_t kCuckooFilterAltHashMultiplier = 0x5bd1e995ULL;
+constexpr uint8_t kEmptyCuckooFingerprint = 0;
// Cuckoo filter implementation from the paper:
// "Cuckoo Filter: Practically Better Than Bloom" by Fan et al.
diff --git a/src/types/cuckoo_filter_page.cc b/src/types/cuckoo_filter_page.cc
index 4264b00f7..e9530a0d9 100644
--- a/src/types/cuckoo_filter_page.cc
+++ b/src/types/cuckoo_filter_page.cc
@@ -160,6 +160,13 @@ rocksdb::Status CuckooPageCache::RestoreBucketSlot(const
SlotMutation &mutation)
rocksdb::Status CuckooPageCache::WriteBackDirtyPages(rocksdb::WriteBatchBase
*batch) {
for (const auto &entry : pages_) {
if (!entry.second.is_dirty) continue;
+ if (std::all_of(entry.second.data.begin(), entry.second.data.end(),
[](char value) { return value == 0; })) {
+ if (entry.second.exists) {
+ auto s = batch->Delete(entry.first);
+ if (!s.ok()) return s;
+ }
+ continue;
+ }
auto s = batch->Put(entry.first, entry.second.data);
if (!s.ok()) return s;
}
@@ -218,6 +225,7 @@ rocksdb::Status CuckooPageCache::loadPage(const
BucketLocation &location, PageEn
PageEntry page_entry;
auto s = storage_->Get(ctx_, ctx_.GetReadOptions(), location.page_key,
&page_entry.data);
if (!s.ok() && !s.IsNotFound()) return s;
+ page_entry.exists = s.ok();
s = normalizePage(s, location.expected_page_size, &page_entry);
if (!s.ok()) return s;
@@ -244,7 +252,10 @@ rocksdb::Status CuckooPageCache::loadPages(const
std::vector<BucketLocation> &lo
for (size_t i = 0; i < locations.size(); ++i) {
PageEntry page_entry;
- if (statuses[i].ok()) page_entry.data.assign(values[i].data(),
values[i].size());
+ if (statuses[i].ok()) {
+ page_entry.data.assign(values[i].data(), values[i].size());
+ page_entry.exists = true;
+ }
auto s = normalizePage(statuses[i], locations[i].expected_page_size,
&page_entry);
if (!s.ok()) return s;
pages_.emplace(locations[i].page_key, std::move(page_entry));
diff --git a/src/types/cuckoo_filter_page.h b/src/types/cuckoo_filter_page.h
index 0012cb82c..b9af7d759 100644
--- a/src/types/cuckoo_filter_page.h
+++ b/src/types/cuckoo_filter_page.h
@@ -69,6 +69,7 @@ class CuckooPageCache {
private:
struct PageEntry {
std::string data;
+ bool exists = false;
bool is_dirty = false;
};
diff --git a/src/types/cuckoo_filter_sub_filter.cc
b/src/types/cuckoo_filter_sub_filter.cc
index e4824b872..00316ee7d 100644
--- a/src/types/cuckoo_filter_sub_filter.cc
+++ b/src/types/cuckoo_filter_sub_filter.cc
@@ -74,6 +74,38 @@ rocksdb::Status CuckooSubFilter::Contains(uint64_t hash,
uint8_t fingerprint, bo
return rocksdb::Status::OK();
}
+rocksdb::Status CuckooSubFilter::Delete(uint64_t hash, uint8_t fingerprint,
bool *deleted) {
+ *deleted = 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;
+
+ for (uint32_t slot_idx = 0; slot_idx < bucket_size_; ++slot_idx) {
+ uint8_t current_fingerprint = kEmptyCuckooFingerprint;
+ s = pages_.GetBucketSlot(filter_index_, num_buckets_, bucket1_idx,
slot_idx, ¤t_fingerprint);
+ if (!s.ok()) return s;
+ if (current_fingerprint != fingerprint) continue;
+
+ *deleted = true;
+ return pages_.SetBucketSlot(filter_index_, num_buckets_, bucket1_idx,
slot_idx, kEmptyCuckooFingerprint);
+ }
+
+ if (bucket1_idx == bucket2_idx) return rocksdb::Status::OK();
+
+ for (uint32_t slot_idx = 0; slot_idx < bucket_size_; ++slot_idx) {
+ uint8_t current_fingerprint = kEmptyCuckooFingerprint;
+ s = pages_.GetBucketSlot(filter_index_, num_buckets_, bucket2_idx,
slot_idx, ¤t_fingerprint);
+ if (!s.ok()) return s;
+ if (current_fingerprint != fingerprint) continue;
+
+ *deleted = true;
+ return pages_.SetBucketSlot(filter_index_, num_buckets_, bucket2_idx,
slot_idx, kEmptyCuckooFingerprint);
+ }
+
+ 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 27d968e3e..4419b03e9 100644
--- a/src/types/cuckoo_filter_sub_filter.h
+++ b/src/types/cuckoo_filter_sub_filter.h
@@ -32,11 +32,9 @@ class CuckooSubFilter {
public:
CuckooSubFilter(CuckooPageCache &pages, uint16_t filter_index, uint32_t
num_buckets);
- uint16_t Index() const { return filter_index_; }
- 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);
+ rocksdb::Status Delete(uint64_t hash, uint8_t fingerprint, bool *deleted);
// Performs speculative kick-out mutations in the page cache. Failed
attempts restore only the slots changed by
// this call, preserving mutations staged by the owning chain operation.
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 cbb724e3f..051342fce 100644
--- a/src/types/redis_cuckoo_chain.cc
+++ b/src/types/redis_cuckoo_chain.cc
@@ -110,7 +110,7 @@ rocksdb::Status CuckooChain::Reserve(engine::Context &ctx,
const Slice &user_key
// Create a write batch for atomic operation
auto batch = storage_->GetWriteBatchBase();
- WriteBatchLogData log_data(kRedisCuckooFilter,
std::vector<std::string>{"reserve", user_key.ToString()});
+ WriteBatchLogData log_data(kRedisCuckooFilter,
std::vector<std::string>{kCFLogDataReserve, user_key.ToString()});
s = batch->PutLogData(log_data.Encode());
if (!s.ok()) return s;
@@ -163,13 +163,56 @@ rocksdb::Status CuckooChain::Add(engine::Context &ctx,
const Slice &user_key, co
return rocksdb::Status::Aborted("filter is full");
}
- s = commitPagesAndMetadata(ctx, user_key, ns_key, &metadata, pages);
+ s = commitPagesAndMetadata(ctx, user_key, ns_key, &metadata, pages,
kCFLogDataAdd);
if (!s.ok()) return s;
*added = true;
return rocksdb::Status::OK();
}
+rocksdb::Status CuckooChain::Delete(engine::Context &ctx, const Slice
&user_key, const Slice &item, bool *deleted) {
+ *deleted = false;
+ std::string ns_key = AppendNamespacePrefix(user_key);
+
+ CuckooChainMetadata metadata(false);
+ auto s = getCuckooChainMetadata(ctx, ns_key, &metadata);
+ if (s.IsNotFound()) return rocksdb::Status::NotFound("Not found");
+ if (!s.ok()) return s;
+
+ s = validateMetadata(metadata);
+ if (!s.ok()) return s;
+
+ uint64_t hash = CuckooFilterHelper::Hash(item.data(), item.size());
+ uint8_t fingerprint = CuckooFilterHelper::GenerateFingerprint(hash);
+
+ CuckooPageCache pages(storage_, ctx, ns_key, storage_->IsSlotIdEncoded(),
metadata.version, metadata.bucket_size,
+ metadata.page_size);
+
+ for (int filter_idx = static_cast<int>(metadata.n_filters) - 1; filter_idx
>= 0; --filter_idx) {
+ uint32_t num_buckets = 0;
+ s = CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion, metadata.bucket_size,
+
static_cast<uint16_t>(filter_idx), &num_buckets);
+ if (!s.ok()) return s;
+
+ CuckooSubFilter sub_filter(pages, static_cast<uint16_t>(filter_idx),
num_buckets);
+ bool found = false;
+ s = sub_filter.Delete(hash, fingerprint, &found);
+ if (!s.ok()) return s;
+ if (!found) {
+ pages.DiscardCleanPages();
+ continue;
+ }
+
+ if (metadata.size == 0) return rocksdb::Status::Corruption("invalid
metadata: size is 0");
+ metadata.size--;
+ metadata.num_deleted_items++;
+ *deleted = true;
+ return commitPagesAndMetadata(ctx, user_key, ns_key, &metadata, pages,
kCFLogDataDel);
+ }
+
+ return rocksdb::Status::OK();
+}
+
rocksdb::Status CuckooChain::tryInsertFingerprint(CuckooChainMetadata
*metadata, CuckooPageCache &pages, uint64_t hash,
uint8_t fingerprint, bool
*inserted) {
auto s = tryCuckooInsert(metadata, pages, hash, fingerprint, inserted);
@@ -271,9 +314,9 @@ rocksdb::Status
CuckooChain::expandAndInsertCuckooChain(CuckooChainMetadata *met
rocksdb::Status CuckooChain::commitPagesAndMetadata(engine::Context &ctx,
const Slice &user_key,
const std::string &ns_key,
const CuckooChainMetadata *metadata,
- CuckooPageCache &pages) {
+ CuckooPageCache &pages,
const std::string &command) {
auto batch = storage_->GetWriteBatchBase();
- WriteBatchLogData log_data(kRedisCuckooFilter,
std::vector<std::string>{"add", user_key.ToString()});
+ WriteBatchLogData log_data(kRedisCuckooFilter,
std::vector<std::string>{command, user_key.ToString()});
auto s = batch->PutLogData(log_data.Encode());
if (!s.ok()) return s;
diff --git a/src/types/redis_cuckoo_chain.h b/src/types/redis_cuckoo_chain.h
index 18eae088e..88baa2b90 100644
--- a/src/types/redis_cuckoo_chain.h
+++ b/src/types/redis_cuckoo_chain.h
@@ -37,6 +37,11 @@ const uint16_t kCFDefaultMaxIterations = 20;
const uint16_t kCFDefaultExpansion = 1;
const uint16_t kCFMaxExpansion = 32768;
+// Command tags recorded in WriteBatchLogData for cuckoo filter mutations.
+constexpr const char *kCFLogDataReserve = "reserve";
+constexpr const char *kCFLogDataAdd = "add";
+constexpr const char *kCFLogDataDel = "del";
+
class CuckooChain : public Database {
public:
CuckooChain(engine::Storage *storage, const std::string &ns) :
Database(storage, ns) {}
@@ -55,6 +60,8 @@ class CuckooChain : public Database {
// 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);
+ // Deletes one matching fingerprint from the cuckoo filter.
+ rocksdb::Status Delete(engine::Context &ctx, const Slice &user_key, const
Slice &item, bool *deleted);
private:
// Loads metadata for a cuckoo filter key.
@@ -71,7 +78,8 @@ class CuckooChain : public Database {
static rocksdb::Status expandAndInsertCuckooChain(CuckooChainMetadata
*metadata, CuckooPageCache &pages,
uint64_t hash, uint8_t
fingerprint, bool *inserted);
rocksdb::Status commitPagesAndMetadata(engine::Context &ctx, const Slice
&user_key, const std::string &ns_key,
- const CuckooChainMetadata *metadata,
CuckooPageCache &pages);
+ const CuckooChainMetadata *metadata,
CuckooPageCache &pages,
+ const std::string &command);
};
} // namespace redis
diff --git a/tests/cppunit/types/cuckoo_filter_page_test.cc
b/tests/cppunit/types/cuckoo_filter_page_test.cc
index 099159220..17e81b635 100644
--- a/tests/cppunit/types/cuckoo_filter_page_test.cc
+++ b/tests/cppunit/types/cuckoo_filter_page_test.cc
@@ -238,6 +238,43 @@ TEST_F(RedisCuckooPageCacheTest,
SetBucketSlotWritesOnlyTargetSlot) {
EXPECT_EQ(page, expected);
}
+TEST_F(RedisCuckooPageCacheTest, SkipsWritingNewPageWhenItBecomesEmpty) {
+ auto metadata = makeMetadata(1);
+ redis::CuckooPageCache pages(storage_.get(), *ctx_, ns_key_,
storage_->IsSlotIdEncoded(), metadata.version,
+ metadata.bucket_size, metadata.page_size);
+
+ auto s = pages.SetBucketSlot(0, 1, 0, 0, 88);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ s = pages.SetBucketSlot(0, 1, 0, 0, 0);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+
+ auto batch = storage_->GetWriteBatchBase();
+ s = pages.WriteBackDirtyPages(batch.Get());
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_EQ(batch->GetWriteBatch()->Count(), 0);
+}
+
+TEST_F(RedisCuckooPageCacheTest, DeletesExistingPageWhenItBecomesEmpty) {
+ auto metadata = makeMetadata(1);
+ auto page_key = makePageKey(metadata, 0, 0);
+ writePage(page_key, std::string{static_cast<char>(88)});
+ redis::CuckooPageCache pages(storage_.get(), *ctx_, ns_key_,
storage_->IsSlotIdEncoded(), metadata.version,
+ metadata.bucket_size, metadata.page_size);
+
+ auto s = pages.SetBucketSlot(0, 1, 0, 0, 0);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+
+ auto batch = storage_->GetWriteBatchBase();
+ s = pages.WriteBackDirtyPages(batch.Get());
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_EQ(batch->GetWriteBatch()->Count(), 1);
+ commitBatch(batch.Get());
+
+ std::string page;
+ s = readPage(page_key, &page);
+ EXPECT_TRUE(s.IsNotFound()) << s.ToString();
+}
+
TEST_F(RedisCuckooPageCacheTest, InvalidBucketAndSlotArguments) {
auto metadata = makeMetadata(4);
redis::CuckooPageCache pages(storage_.get(), *ctx_, ns_key_,
storage_->IsSlotIdEncoded(), metadata.version,
diff --git a/tests/cppunit/types/cuckoo_filter_test.cc
b/tests/cppunit/types/cuckoo_filter_test.cc
index 9fb5fafcd..ae3da1d4c 100644
--- a/tests/cppunit/types/cuckoo_filter_test.cc
+++ b/tests/cppunit/types/cuckoo_filter_test.cc
@@ -108,6 +108,46 @@ class RedisCuckooFilterTest : public TestBase {
.Encode();
}
+ static uint32_t bucketsPerPage(const CuckooChainMetadata &metadata) {
+ return std::max<uint32_t>(1, metadata.page_size / metadata.bucket_size);
+ }
+
+ static uint32_t pageIndexForBucket(const CuckooChainMetadata &metadata,
uint32_t bucket_index) {
+ return bucket_index / bucketsPerPage(metadata);
+ }
+
+ static uint32_t bucketOffsetInPage(const CuckooChainMetadata &metadata,
uint32_t bucket_index) {
+ return (bucket_index % bucketsPerPage(metadata)) * metadata.bucket_size;
+ }
+
+ void placeFingerprint(const std::string &key, const CuckooChainMetadata
&metadata, uint16_t filter_index,
+ uint32_t num_buckets, uint32_t bucket_index, uint32_t
slot_index, uint8_t fingerprint) {
+ ASSERT_LT(bucket_index, num_buckets);
+ ASSERT_LT(slot_index, metadata.bucket_size);
+ auto page_index = pageIndexForBucket(metadata, bucket_index);
+ auto first_bucket = page_index * bucketsPerPage(metadata);
+ auto page_bucket_count = std::min(bucketsPerPage(metadata), num_buckets -
first_bucket);
+ std::string page;
+ auto page_key = makePageKey(key, metadata, filter_index, page_index);
+ auto s = readPage(page_key, &page);
+ if (s.IsNotFound()) {
+ page.assign(page_bucket_count * metadata.bucket_size, 0);
+ } else {
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(page.size(), page_bucket_count * metadata.bucket_size);
+ }
+ page[bucketOffsetInPage(metadata, bucket_index) + slot_index] =
static_cast<char>(fingerprint);
+ writePage(page_key, page);
+ }
+
+ uint8_t readFingerprint(const std::string &key, const CuckooChainMetadata
&metadata, uint16_t filter_index,
+ uint32_t bucket_index, uint32_t slot_index) {
+ std::string page;
+ auto s = readPage(makePageKey(key, metadata, filter_index,
pageIndexForBucket(metadata, bucket_index)), &page);
+ EXPECT_TRUE(s.ok()) << s.ToString();
+ return static_cast<uint8_t>(page[bucketOffsetInPage(metadata,
bucket_index) + slot_index]);
+ }
+
rocksdb::Status readPage(const std::string &page_key, std::string *value) {
return storage_->Get(*ctx_, ctx_->GetReadOptions(),
storage_->GetCFHandle(ColumnFamilyID::PrimarySubkey), page_key,
value);
@@ -665,6 +705,44 @@ TEST_F(RedisCuckooFilterTest,
KickOutSuccessWritesDirtyPages) {
EXPECT_EQ(static_cast<uint8_t>(page[evicted_bucket]), first.fingerprint);
}
+TEST_F(RedisCuckooFilterTest,
DeletePreservesEarlierCachedMutationAcrossSubFilters) {
+ constexpr uint8_t bucket_size = 1;
+ constexpr uint32_t page_size = 2;
+ constexpr uint32_t num_buckets = 2;
+
+ CuckooChainMetadata metadata(false);
+ metadata.version = 1;
+ writePage(makePageKey(key_, metadata, 0, 0), std::string({1, 0}));
+
+ redis::CuckooPageCache page_cache(storage_.get(), *ctx_,
db_->AppendNamespacePrefix(key_),
+ storage_->IsSlotIdEncoded(),
metadata.version, bucket_size, page_size);
+ redis::CuckooSubFilter earlier_sub_filter(page_cache, 1, num_buckets);
+ bool inserted = false;
+ auto s = earlier_sub_filter.TryInsert(0, 9, &inserted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_TRUE(inserted);
+
+ redis::CuckooSubFilter sub_filter(page_cache, 0, num_buckets);
+ bool deleted = false;
+ s = sub_filter.Delete(0, 1, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_TRUE(deleted);
+
+ auto batch = storage_->GetWriteBatchBase();
+ s = page_cache.WriteBackDirtyPages(batch.Get());
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_EQ(batch->GetWriteBatch()->Count(), 2);
+ s = storage_->Write(*ctx_, storage_->DefaultWriteOptions(),
batch->GetWriteBatch());
+ ASSERT_TRUE(s.ok()) << s.ToString();
+
+ std::string page;
+ s = readPage(makePageKey(key_, metadata, 0, 0), &page);
+ EXPECT_TRUE(s.IsNotFound()) << s.ToString();
+ s = readPage(makePageKey(key_, metadata, 1, 0), &page);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_EQ(page, std::string({9, 0}));
+}
+
TEST_F(RedisCuckooFilterTest,
FailedMultiStepKickOutPreservesEarlierCachedMutation) {
constexpr uint8_t bucket_size = 1;
constexpr uint32_t page_size = 2;
@@ -1077,3 +1155,184 @@ TEST_F(RedisCuckooFilterTest,
ExistsWithRepeatedInsertions) {
ASSERT_TRUE(s.ok());
ASSERT_TRUE(exists) << "Item should exist after duplicate insertions";
}
+
+TEST_F(RedisCuckooFilterTest, DeleteMissingItemDoesNotMutateMetadata) {
+ reserveAndVerify(key_, 1000, 4, 500, 2);
+ addAndVerify(key_, "known", 1000, 4, 500, 2, 1);
+
+ auto metadata = getMetadata(key_);
+ uint32_t num_buckets = 0;
+ auto s =
redis::CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion,
+
metadata.bucket_size, 0, &num_buckets);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ auto known_hash = redis::CuckooFilterHelper::Hash("known");
+ auto known_fp = redis::CuckooFilterHelper::GenerateFingerprint(known_hash);
+ auto known_bucket1 = static_cast<uint32_t>(known_hash % num_buckets);
+ auto known_bucket2 =
static_cast<uint32_t>(redis::CuckooFilterHelper::GetAltHash(known_fp,
known_hash) % num_buckets);
+
+ std::string missing_item;
+ for (int i = 0; i < 10000; ++i) {
+ auto candidate = "missing_" + std::to_string(i);
+ auto hash = redis::CuckooFilterHelper::Hash(candidate);
+ auto fp = redis::CuckooFilterHelper::GenerateFingerprint(hash);
+ auto bucket1 = static_cast<uint32_t>(hash % num_buckets);
+ auto bucket2 =
static_cast<uint32_t>(redis::CuckooFilterHelper::GetAltHash(fp, hash) %
num_buckets);
+ if (fp != known_fp || (bucket1 != known_bucket1 && bucket1 !=
known_bucket2 && bucket2 != known_bucket1 &&
+ bucket2 != known_bucket2)) {
+ missing_item = candidate;
+ break;
+ }
+ }
+ ASSERT_FALSE(missing_item.empty());
+
+ bool deleted = true;
+ s = cuckoo_->Delete(*ctx_, key_, missing_item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_FALSE(deleted);
+ verifyMetadata(key_, 1000, 4, 500, 2, 1, 1, 0);
+}
+
+TEST_F(RedisCuckooFilterTest, DeleteSearchesNewestFilterFirst) {
+ CuckooChainMetadata metadata;
+ metadata.size = 100;
+ metadata.base_capacity = 2;
+ metadata.bucket_size = 1;
+ metadata.max_iterations = 1;
+ metadata.expansion = 1;
+ metadata.n_filters = 2;
+ metadata.num_deleted_items = 0;
+ metadata.page_size = 1;
+ writeMetadata(key_, metadata);
+
+ const std::string item = "item";
+ auto hash = redis::CuckooFilterHelper::Hash(item);
+ auto fingerprint = redis::CuckooFilterHelper::GenerateFingerprint(hash);
+ uint32_t num_buckets = 0;
+ auto s =
redis::CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion,
+
metadata.bucket_size, 0, &num_buckets);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ auto bucket = static_cast<uint32_t>(hash % num_buckets);
+ placeFingerprint(key_, metadata, 0, num_buckets, bucket, 0, fingerprint);
+ placeFingerprint(key_, metadata, 1, num_buckets, bucket, 0, fingerprint);
+
+ bool deleted = false;
+ s = cuckoo_->Delete(*ctx_, key_, item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_TRUE(deleted);
+
+ auto stored_metadata = getMetadata(key_);
+ EXPECT_EQ(stored_metadata.n_filters, 2);
+ EXPECT_EQ(readFingerprint(key_, stored_metadata, 0, bucket, 0), fingerprint);
+ std::string page;
+ s = readPage(makePageKey(key_, stored_metadata, 1,
pageIndexForBucket(stored_metadata, bucket)), &page);
+ EXPECT_TRUE(s.IsNotFound()) << s.ToString();
+}
+
+TEST_F(RedisCuckooFilterTest, DeleteSpansMultipleSubFilters) {
+ CuckooChainMetadata metadata;
+ metadata.size = 2;
+ metadata.base_capacity = 2;
+ metadata.bucket_size = 1;
+ metadata.max_iterations = 1;
+ metadata.expansion = 2;
+ metadata.n_filters = 3;
+ metadata.num_deleted_items = 0;
+ metadata.page_size = 1;
+ writeMetadata(key_, metadata);
+
+ const std::string item = "duplicate";
+ auto hash = redis::CuckooFilterHelper::Hash(item);
+ auto fingerprint = redis::CuckooFilterHelper::GenerateFingerprint(hash);
+
+ uint32_t num_buckets = 0;
+ auto s =
redis::CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion,
+
metadata.bucket_size, 0, &num_buckets);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ auto oldest_bucket = static_cast<uint32_t>(hash % num_buckets);
+ placeFingerprint(key_, metadata, 0, num_buckets, oldest_bucket, 0,
fingerprint);
+
+ s = redis::CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion, metadata.bucket_size,
+ 2, &num_buckets);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ auto newest_bucket = static_cast<uint32_t>(hash % num_buckets);
+ placeFingerprint(key_, metadata, 2, num_buckets, newest_bucket, 0,
fingerprint);
+
+ bool deleted = false;
+ s = cuckoo_->Delete(*ctx_, key_, item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_TRUE(deleted);
+
+ auto stored_metadata = getMetadata(key_);
+ EXPECT_EQ(stored_metadata.size, 1);
+ EXPECT_EQ(stored_metadata.n_filters, 3);
+ EXPECT_EQ(stored_metadata.num_deleted_items, 1);
+ EXPECT_EQ(readFingerprint(key_, stored_metadata, 0, oldest_bucket, 0),
fingerprint);
+ std::string page;
+ s = readPage(makePageKey(key_, stored_metadata, 2,
pageIndexForBucket(stored_metadata, newest_bucket)), &page);
+ EXPECT_TRUE(s.IsNotFound()) << s.ToString();
+
+ deleted = false;
+ s = cuckoo_->Delete(*ctx_, key_, item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_TRUE(deleted);
+
+ stored_metadata = getMetadata(key_);
+ EXPECT_EQ(stored_metadata.size, 0);
+ EXPECT_EQ(stored_metadata.n_filters, 3);
+ EXPECT_EQ(stored_metadata.num_deleted_items, 2);
+ s = readPage(makePageKey(key_, stored_metadata, 0,
pageIndexForBucket(stored_metadata, oldest_bucket)), &page);
+ EXPECT_TRUE(s.IsNotFound()) << s.ToString();
+
+ deleted = true;
+ s = cuckoo_->Delete(*ctx_, key_, item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_FALSE(deleted);
+
+ stored_metadata = getMetadata(key_);
+ EXPECT_EQ(stored_metadata.size, 0);
+ EXPECT_EQ(stored_metadata.num_deleted_items, 2);
+}
+
+TEST_F(RedisCuckooFilterTest, DeleteDoesNotCompactFilters) {
+ CuckooChainMetadata metadata;
+ metadata.size = 8;
+ metadata.base_capacity = 2;
+ metadata.bucket_size = 2;
+ metadata.max_iterations = 1;
+ metadata.expansion = 1;
+ metadata.n_filters = 2;
+ metadata.num_deleted_items = 1;
+ metadata.page_size = 4;
+ writeMetadata(key_, metadata);
+
+ uint32_t num_buckets = 0;
+ auto s =
redis::CuckooFilterHelper::GetFilterNumBuckets(metadata.base_capacity,
metadata.expansion,
+
metadata.bucket_size, 0, &num_buckets);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ ASSERT_EQ(num_buckets, 2);
+
+ const std::string item = "delete_me";
+ auto hash = redis::CuckooFilterHelper::Hash(item);
+ auto fingerprint = redis::CuckooFilterHelper::GenerateFingerprint(hash);
+ auto delete_bucket = static_cast<uint32_t>(hash % num_buckets);
+ auto movable_bucket = static_cast<uint32_t>((delete_bucket + 1) %
num_buckets);
+ constexpr uint8_t movable_fingerprint = 77;
+ placeFingerprint(key_, metadata, 1, num_buckets, delete_bucket, 0,
fingerprint);
+ placeFingerprint(key_, metadata, 1, num_buckets, movable_bucket, 0,
movable_fingerprint);
+
+ bool deleted = false;
+ s = cuckoo_->Delete(*ctx_, key_, item, &deleted);
+ ASSERT_TRUE(s.ok()) << s.ToString();
+ EXPECT_TRUE(deleted);
+
+ auto stored_metadata = getMetadata(key_);
+ EXPECT_EQ(stored_metadata.size, 7);
+ EXPECT_EQ(stored_metadata.n_filters, 2);
+ EXPECT_EQ(stored_metadata.num_deleted_items, 2);
+ EXPECT_EQ(readFingerprint(key_, stored_metadata, 1, movable_bucket, 0),
movable_fingerprint);
+ EXPECT_EQ(readFingerprint(key_, stored_metadata, 1, delete_bucket, 0), 0);
+
+ std::string page;
+ s = readPage(makePageKey(key_, metadata, 1, 0), &page);
+ EXPECT_TRUE(s.ok()) << s.ToString();
+}
diff --git a/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
b/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
index 89048dd80..700a4b076 100644
--- a/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
+++ b/tests/gocase/unit/type/bloom/cuckoo_filter_test.go
@@ -149,6 +149,56 @@ func TestCuckooFilter(t *testing.T) {
require.Error(t, rdb.Do(ctx, "cf.add", "key", "item1",
"item2").Err())
})
+ t.Run("Del wrong number of arguments", func(t *testing.T) {
+ require.Error(t, rdb.Do(ctx, "cf.del").Err())
+ require.Error(t, rdb.Do(ctx, "cf.del", "key_only").Err())
+ require.Error(t, rdb.Do(ctx, "cf.del", "key", "item1",
"item2").Err())
+ })
+
+ t.Run("Del missing key", func(t *testing.T) {
+ key := "test_cuckoo_filter_del_missing"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.ErrorContains(t, rdb.Do(ctx, "cf.del", key,
"item").Err(), "Not found")
+ })
+
+ t.Run("Del wrong type", func(t *testing.T) {
+ key := "test_cuckoo_filter_del_wrong_type"
+ require.NoError(t, rdb.Set(ctx, key, "value", 0).Err())
+ require.ErrorContains(t, rdb.Do(ctx, "cf.del", key,
"item").Err(), "WRONGTYPE")
+ })
+
+ t.Run("Del basic", func(t *testing.T) {
+ key := "test_cuckoo_filter_del_basic"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"item").Val())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.del", key,
"item").Val())
+ require.Equal(t, int64(0), rdb.Do(ctx, "cf.del", key,
"item").Val())
+ })
+
+ t.Run("Del duplicate item", func(t *testing.T) {
+ key := "test_cuckoo_filter_del_dup"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"same_item").Val())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"same_item").Val())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.del", key,
"same_item").Val())
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.del", key,
"same_item").Val())
+ require.Equal(t, int64(0), rdb.Do(ctx, "cf.del", key,
"same_item").Val())
+ })
+
+ t.Run("Del duplicates across multiple sub-filters", func(t *testing.T) {
+ key := "test_cuckoo_filter_del_multi_filter"
+ require.NoError(t, rdb.Del(ctx, key).Err())
+ // Small capacity with expansion enabled so duplicates span
several sub-filters
+ require.NoError(t, rdb.Do(ctx, "cf.reserve", key, "2",
"BUCKETSIZE", "1", "MAXITERATIONS", "1", "EXPANSION", "2").Err())
+ for i := 0; i < 20; i++ {
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.add", key,
"same_item").Val())
+ }
+ for i := 0; i < 20; i++ {
+ require.Equal(t, int64(1), rdb.Do(ctx, "cf.del", key,
"same_item").Val())
+ }
+ require.Equal(t, int64(0), rdb.Do(ctx, "cf.del", key,
"same_item").Val())
+ })
+
t.Run("Add many items", func(t *testing.T) {
key := "test_cuckoo_filter_add_many"
require.NoError(t, rdb.Del(ctx, key).Err())
