nagisa-kunhah commented on code in PR #3481: URL: https://github.com/apache/kvrocks/pull/3481#discussion_r3325501841
########## src/types/redis_cuckoo_chain.cc: ########## @@ -0,0 +1,269 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + * + */ + +#include "redis_cuckoo_chain.h" + +#include "cuckoo_filter.h" +#include "cuckoo_filter_sub_filter.h" +#include "logging.h" + +namespace redis { + +rocksdb::Status CuckooChain::getCuckooChainMetadata(engine::Context &ctx, const Slice &ns_key, + CuckooChainMetadata *metadata) { + return Database::GetMetadata(ctx, {kRedisCuckooFilter}, ns_key, metadata); +} + +rocksdb::Status CuckooChain::validateMetadata(const CuckooChainMetadata &metadata) { + if (metadata.n_filters == 0) { + return rocksdb::Status::Corruption("invalid metadata: n_filters is 0"); + } + if (metadata.base_capacity == 0) { + return rocksdb::Status::Corruption("invalid metadata: base_capacity is 0"); + } + if (metadata.bucket_size == 0) { + return rocksdb::Status::Corruption("invalid metadata: bucket_size is 0"); + } + if (metadata.max_iterations == 0) { + return rocksdb::Status::Corruption("invalid metadata: max_iterations is 0"); + } + if (metadata.page_size < metadata.bucket_size) { + return rocksdb::Status::Corruption("invalid metadata: page_size is smaller than bucket_size"); + } + if (!CuckooFilterHelper::IsCapacitySupported(metadata.base_capacity, metadata.bucket_size)) { + return rocksdb::Status::Corruption("invalid metadata: base_capacity is too large"); + } + return rocksdb::Status::OK(); +} + +rocksdb::Status CuckooChain::Reserve(engine::Context &ctx, const Slice &user_key, uint64_t capacity, + uint8_t bucket_size, uint16_t max_iterations, uint16_t expansion, + uint32_t page_size) { + if (capacity == 0) { + return rocksdb::Status::InvalidArgument("capacity must be larger than 0"); + } + + // RedisBloom requires 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"); + } + + if (bucket_size == 0 || bucket_size > 255) { + return rocksdb::Status::InvalidArgument("bucket_size must be between 1 and 255"); + } + + if (max_iterations == 0) { + return rocksdb::Status::InvalidArgument("max_iterations must be larger than 0"); + } + if (page_size == 0) { + return rocksdb::Status::InvalidArgument("page_size must be larger than 0"); + } + if (page_size < bucket_size) { + return rocksdb::Status::InvalidArgument("page_size must be at least bucket_size"); + } + if (expansion > kCFMaxExpansion) { + return rocksdb::Status::InvalidArgument("expansion must be between 0 and 32768"); + } + if (!CuckooFilterHelper::IsCapacitySupported(capacity, bucket_size)) { + return rocksdb::Status::InvalidArgument("capacity is too large"); + } + + std::string ns_key = AppendNamespacePrefix(user_key); + + CuckooChainMetadata existing_metadata; + auto s = getCuckooChainMetadata(ctx, ns_key, &existing_metadata); + if (!s.ok() && !s.IsNotFound()) return s; + if (!s.IsNotFound()) { + return rocksdb::Status::InvalidArgument("the key already exists"); + } + + CuckooChainMetadata metadata; + + metadata.size = 0; + metadata.base_capacity = capacity; + metadata.bucket_size = bucket_size; + metadata.max_iterations = max_iterations; + metadata.expansion = expansion; + metadata.n_filters = 1; + metadata.num_deleted_items = 0; + metadata.page_size = page_size; + + // Create a write batch for atomic operation + auto batch = storage_->GetWriteBatchBase(); + WriteBatchLogData log_data(kRedisCuckooFilter, std::vector<std::string>{"reserve", user_key.ToString()}); + s = batch->PutLogData(log_data.Encode()); + if (!s.ok()) return s; + + std::string metadata_bytes; + metadata.Encode(&metadata_bytes); + s = batch->Put(metadata_cf_handle_, ns_key, metadata_bytes); + if (!s.ok()) return s; + + // Pages are created lazily on first write. Reserve only persists metadata so sparse filters don't preallocate page + // values that may never be used. + + return storage_->Write(ctx, storage_->DefaultWriteOptions(), batch->GetWriteBatch()); +} + +rocksdb::Status CuckooChain::Add(engine::Context &ctx, const Slice &user_key, const Slice &item, bool *added) { Review Comment: Your suggestion makes sense. I’ve refactored the function into three private helpers: tryCuckooInsert, tryCuckooKickOut, and expandAndInsertCuckooChain. Thanks for the tip! -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
