bloom filter的開源實作程式memcached bloom filter

文章轉自：http://www.heyues.com/mc_bloom_filter/

google code 上的介紹

Introduction Bloom filter 是由 Howard Bloom 在 1970 年提出的二進制向量資料結構，它具有很好的空間和時間效率，被用來檢測一個元素是不是集合中的一個成員，被廣泛使用于各種海量資料排重的場景中。Mc bloom filter是一個全新的排重伺服器，它采用memcached的網絡層封裝了bloom filter的操作，使各種語言php、java、perl、python、go、c等等，都能使用memcached的協定進行bloom filter的操作。 Details 作者 新浪湯曉剛何躍胡鴻 bloom filter 的簡介 bloom_filter的百度百科Google黑闆報算法詳細介紹 mc bloom filter 的特性 完全采用memcached的網絡層協定，建立、删除、添加、檢視狀态等。 mc bloom filter 是一個全記憶體的排重伺服器，所有資料均放在記憶體中。 可以在一個執行個體中建立多個bloom filter，在記憶體允許的情況，可以建立幾十G大小的bloom filter，支援最高上百億的資料排重。 采用google員工寫的的高性能hash算法murmurhash，保證bloom filter的hash的高速 單線程版單機讀寫速度能達到十萬次/s（同網段兩台伺服器多線程壓力測試 伺服器配置：8核 Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 12G記憶體） 多線程版單機讀寫能力均能達到30萬次/s(同網段兩台伺服器多線程壓力測試 伺服器配置：8核 Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 12G記憶體） 32位、64位伺服器相容。 mc bloom filter 的安裝 bloom filter 使用memcached網絡層，依賴于libevent，先登入http://libevent.org/下載下傳最新穩定版本。 wget https://github.com/downloads/libevent/libevent/libevent-2.0.20-stable.tar.gz tar zxvf libevent-2.0.20-stable.tar.gz cd libevent-2.0.20-stable ./configure make && make install 在bloom filter 的google code 上，下載下傳mc bloom filter的最新穩定版本 1.wget bloom filter的最新穩定版本 2.修改Makefile檔案，主要是修改libevent到你的目錄 3.在目錄中執行make,生成mc_bloom_filter【線上版】 mc_bloom_filter_【調試版】 兩個可執行檔案，調試版會打很多日志 4. nohup ./mc_bloom_filter -p12345 -d -uroot -m4000 –p/tmp/mc_bloom_filter.pid –l127.0.0.1 日志檔案就是目前目錄的nohup.out檔案 mc bloom filter的啟動參數 參數 是否必須 值的含義 p(小p) 是 監聽端口，預設12345 P(大P) 是 pid檔案的位址 u(小u) 是 用哪個使用者運作 m(小m) 是 最大記憶體，機關m d(小d) 是 是否用daemon背景運作 l(小l) 是 監聽的ip t 否 表示線程個數，隻多線程版本有此參數，單線程無此參數，t預設為4 v 否 是否将調試的輸出列印出來，如果添加這個參數，會在終端或者nohup.out中列印調試資訊 mc bloom filter 的指令 add add key 0 0 value_lengthexpected_max_amount_of_elements|false_positive_rate 比如add test 0 0 13 1000000|0.001 表示建立一個預計存100萬，誤判率千分之一的bloom filter 成功傳回STORED 失敗傳回NOT_STORED set set key 0 0 subkey_lengthsubkey 成功傳回STORED 失敗傳回NOT_STORED get get key|subkey 存在傳回1，不存在啥都不傳回 stats stats 檢視伺服器的總體狀況 資訊清單 stats blooms 列舉所有過濾器的名稱和占用記憶體位元組大小 資訊清單 stats bloom key 可以檢視名字為key的bloom filter的詳細資訊 資訊清單 try try expected_max_amount_of_elements|false_positive_rate比如 try 100000000|0.0001 表示計算1億個目标存儲數，在誤判率萬分之一的情況下， 需要的記憶體大小用來預估過濾器所需的記憶體大小和hash函數個數 資訊清單 setmem setmem size(Mbytes) 用來設定目前程序可使用的記憶體容量，機關是m,比如要設定記憶體1G，setmem 1024 成功傳回STORED 成功傳回STORED，失敗傳回NOT_STORED PHP 的使用demo <?php $mc = new Memcache(); $mc -> add("my_bloom","10000000|0.0001"); $mc -> set("my_bloom","2222222"); var_dump($mc->get("my_bloom|2222222"); ?>

具體的文檔在這裡https://code.google.com/mc_bloom_filter