All Projects → erikdubbelboer → Redis Lua Scaling Bloom Filter

erikdubbelboer / Redis Lua Scaling Bloom Filter

Licence: mit
LUA Redis scripts for a scaling bloom filter

Programming Languages

javascript
184084 projects - #8 most used programming language
lua
6591 projects

Projects that are alternatives of or similar to Redis Lua Scaling Bloom Filter

Jredisbloom
Java Client for RedisBloom probabilistic module
Stars: ✭ 108 (-59.7%)
Mutual labels:  bloom-filter, redis
Springmvc Project
开箱即用的SpringMVC项目,包含常规业务所需的框架功能整合,更多功能请关注 https://github.com/MartinDai/SpringBoot-Project
Stars: ✭ 33 (-87.69%)
Mutual labels:  bloom-filter, redis
Redisbloom
Probabilistic Datatypes Module for Redis
Stars: ✭ 858 (+220.15%)
Mutual labels:  bloom-filter, redis
Redis Cuckoofilter
Hashing-function agnostic Cuckoo filters for Redis
Stars: ✭ 158 (-41.04%)
Mutual labels:  bloom-filter, redis
algorithm-structure
2021年最新总结 500个常用数据结构,算法,算法导论,面试常用,大厂高级工程师整理总结
Stars: ✭ 590 (+120.15%)
Mutual labels:  bloom-filter
json-bloomfilter
🗜 A bloom filter implementation in Ruby and Javascript that is serialisable to JSON and compatible between both languages.
Stars: ✭ 15 (-94.4%)
Mutual labels:  bloom-filter
bloomfilter
Simplistic (but fast) java implementation of a bloom filter.
Stars: ✭ 35 (-86.94%)
Mutual labels:  bloom-filter
leaked-password
Leaked password check library with bloom filter
Stars: ✭ 41 (-84.7%)
Mutual labels:  bloom-filter
Goatee
A Redis-backed notification server written in Go
Stars: ✭ 265 (-1.12%)
Mutual labels:  redis
Jetcache
JetCache is a Java cache framework.
Stars: ✭ 3,167 (+1081.72%)
Mutual labels:  redis
fastbloom
A simple but fast bloomfilter written in Python
Stars: ✭ 21 (-92.16%)
Mutual labels:  bloom-filter
golomb-set
A Golomb Coded Set implementation in Rust
Stars: ✭ 33 (-87.69%)
Mutual labels:  bloom-filter
Spring Boot Demo
Spring Boot & Spring Cloud & Spring Security Demo Case(Spring学习示例实战项目)
Stars: ✭ 255 (-4.85%)
Mutual labels:  redis
komihash
Very fast, high-quality hash function (non-cryptographic, C) + PRNG
Stars: ✭ 68 (-74.63%)
Mutual labels:  bloom-filter
Lock
高性能分布式并发锁, 行为限流
Stars: ✭ 260 (-2.99%)
Mutual labels:  redis
xorf
Xor filters - efficient probabilistic hashsets. Faster and smaller than bloom and cuckoo filters.
Stars: ✭ 64 (-76.12%)
Mutual labels:  bloom-filter
bloomfilter
Bloomfilter written in Golang, includes rotation and RPC
Stars: ✭ 61 (-77.24%)
Mutual labels:  bloom-filter
Poseidon
poseidon项目是基于Java的商城项目,包括前台商城(),后台管理系统。系统采用SpringCloud+SpringBoot+Mybatis+React等框架进行开发。包括首页展示,商品搜索,商品推荐,购物车,订单等模块。
Stars: ✭ 261 (-2.61%)
Mutual labels:  redis
hashlookup-forensic-analyser
Analyse a forensic target (such as a directory) to find and report files found and not found from CIRCL hashlookup public service - https://circl.lu/services/hashlookup/
Stars: ✭ 43 (-83.96%)
Mutual labels:  bloom-filter
ntHash
Fast hash function for DNA sequences
Stars: ✭ 66 (-75.37%)
Mutual labels:  bloom-filter

redis-lua-scaling-bloom-filter

add.lua, cas.lua and check.lua are three lua scripts for a scaling bloom filter for Redis

layer-add.lua and later-check.lua are two lua scripts for a scaling layered bloom filter for Redis

The scripts are to be executed using the EVAL command in Redis.

These scripts will probably not work on Redis cluster since the keys used inside the script aren't all passed as arguments!

The layered filter has a maximum number of 32 layers. You can modify this in the source.

add.lua, cas.lua and layer-add.lua

The add.lua script adds a new element to the filter. It will create the filter when it doesn't exist yet.

cas.lua does a Check And Set, this will not add the element if it already exist. cas.lua will return 0 if the element is added, or 1 if the element was already in the filter. Since we use a scaling filter adding an element using add.lua might cause the element to exist in multiple parts of the filter at the same time. cas.lua prevents this. Using only cas.lua the :count key of the filter will accurately count the number of elements added to the filter. Only using cas.lua will also lower the number of false positives by a small amount (less duplicates in the filter means less bits set).

layer-add.lua does a similar thing to cas.lua since this is necessary for the layer part to work (need to check all the filters in a layer to see if it already exists in the layer). layer-add.lua will return the layer number the element was added to.

These scripts expects 4 arguments.

  1. The base name of the keys to use.
  2. The initial size of the bloom filter (in number of elements).
  3. The probability of false positives.
  4. The element to add to the filter.

For example the following call would add "something" to a filter named test which will initially be able to hold 10000 elements with a probability of false positives of 1%.

eval "add.lua source here" 0 test 10000 0.01 something

check.lua and layer-check.lua

The check.lua and layer-check.lua scripts check if an element is contained in the bloom filter.

layer-check.lua returns the layer the element was found in.

These scripts expects 4 arguments.

  1. The base name of the keys to use.
  2. The initial size of the bloom filter (in number of elements).
  3. The probability of false positives.
  4. The element to check for.

For example the following call would check if "something" is part of the filter named test which will initially be able to hold 10000 elements with a probability of false positives of 1%.

eval "check.lua source here" 0 test 10000 0.01 something

Tests

$ npm install redis srand
$ node add.js
$ node cas.js
$ node check.js
$ # or/and
$ node layer-add.js
$ node layer-check.js

add.js and layer-add.js will add elements to a filter named test and then check if the elements are part of the filter.

check.js and layer-check.js will test random elements against the filter build by add.js or layer-add.js to find the probability of false positives.

Both script assume Redis is running on the default port.

Benchmark

You can run ./benchmark.sh and ./layer-benchmark.sh to see how fast the scripts are.

This script assumes Redis is running on the default port and redis-cli and redis-benchmark are installed.

This is the outputs on my 2.3GHz 2012 MacBook Pro Retina:

add.lua
====== evalsha ab31647b3931a68b3b93a7354a297ed273349d39 0 HSwVBmHECt 1000000 0.01 :rand:000000000000 ======
  200000 requests completed in 8.27 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

94.57% <= 1 milliseconds
100.00% <= 2 milliseconds
24175.03 requests per second


check.lua
====== evalsha 437a3b0c6a452b5f7a1f10487974c002d41f4a04 0 HSwVBmHECt 1000000 0.01 :rand:000000000000 ======
  200000 requests completed in 8.54 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

92.52% <= 1 milliseconds
100.00% <= 8 milliseconds
23419.20 requests per second


layer-add.lua
====== evalsha 7ae29948e3096dd064c22fcd8b628a5c77394b0c 0 ooPb5enskU 1000000 0.01 :rand:000000000000 ======
  20000 requests completed in 12.61 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

55.53% <= 12 milliseconds
75.42% <= 13 milliseconds
83.71% <= 14 milliseconds
91.48% <= 15 milliseconds
97.76% <= 16 milliseconds
99.90% <= 24 milliseconds
100.00% <= 24 milliseconds
1586.04 requests per second


layer-check.lua
====== evalsha c1386438944daedfc4b5c06f79eadb6a83d4b4ea 0 ooPb5enskU 1000000 0.01 :rand:000000000000 ======
  20000 requests completed in 11.13 seconds
  20 parallel clients
  3 bytes payload
  keep alive: 1

0.00% <= 9 milliseconds
74.12% <= 11 milliseconds
80.43% <= 12 milliseconds
83.93% <= 13 milliseconds
97.43% <= 14 milliseconds
99.89% <= 15 milliseconds
100.00% <= 15 milliseconds
1797.59 requests per second
Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].