valkey-io / valkey-bloom

Rust based Valkey Module which provides a BloomFilter data type / APIs
11 stars 9 forks source link

rdb format optimization: using fixed seed for bloom filters #2

Closed YueTang-Vanessa closed 2 months ago

YueTang-Vanessa commented 2 months ago

Description

Fixed seeds and sip keys can help user create bloom objects using the same seed and to restore (from RDB save and load) the bloom objects with the same hashers(sip keys are generated based on the seed). This will save RDB space (32 bytes per filter and there can be multiple filters per object).

This commit have following changes:

Test

Loading the module with valkey-server, verified that the rdb can load successfully with same bf.info key item and bf.exists key item output

127.0.0.1:6379> info keyspace
# Keyspace
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> info keyspace
# Keyspace
db0:keys=1,expires=0,avg_ttl=0
127.0.0.1:6379> bf.add key item
(integer) 1
127.0.0.1:6379> info keyspace
# Keyspace
db0:keys=2,expires=0,avg_ttl=0
127.0.0.1:6379> keys *
1) "hello"
2) "key"
127.0.0.1:6379> bf.exists key item
(integer) 1
127.0.0.1:6379> bf.info key
 1) Capacity
 2) (integer) 100000
 3) Size
 4) (integer) 179952
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 1
 9) Expansion rate
10) (integer) 2
127.0.0.1:6379> bgsave
Background saving started
127.0.0.1:6379> shutdown
not connected> info keyspace
# Keyspace
db0:keys=2,expires=0,avg_ttl=0
127.0.0.1:6379> keys *
1) "key"
2) "hello"
127.0.0.1:6379> bf.exists key item
(integer) 1
127.0.0.1:6379> bf.info key
 1) Capacity
 2) (integer) 100000
 3) Size
 4) (integer) 179952
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 1
 9) Expansion rate
10) (integer) 2

Also passed python tests and unit tests

running 3 tests
test bloom::utils::tests::test_sip_keys ... ok
test bloom::utils::tests::test_non_scaling_filter ... ok
test bloom::utils::tests::test_scaling_filter ... ok

test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 9.92s

valkey-bloom/tests/test_basic.py::TestBloomBasic::test_basic PASSED           [ 50%]
valkey-bloom/tests/test_save_and_restore.py::TestBloomSaveRestore::test_basic_save_and_restore PASSED [100%]

================================================================ 2 passed in 3.61 seconds ================================================================
Build and Integration Tests succeeded