評價d-Left Counting Bloom Filter

轉載位址：https://blog.csdn.net/jiaomeng/article/details/1529345

Bloom Filter是一個簡潔精緻的資料結構，要對它進行本質上的提高并不容易。多少年來，針對Bloom Filter的變種很多，但實質性的突破并不多，無非Counting Bloom Filter、Compressed Bloom Filter等幾種。很多變種都針對某一特定的應用領域，或是針對某一個方面的問題，離開特定的領域和問題，将它單獨拿出來算不上有分量的突破。

較之Bloom Filter的其它變種，d-left counting bloom filter有其特殊性。之是以将這種結構稱作counting bloom filter，是因為它的外在功能和counting bloom filter一樣，但就它的内部結構而言，稱它為bloom filter有些牽強。如果将counting bloom filter比作一隻貓，那d-left counting bloom filter就是一隻比貓還擅長抓老鼠的狗。雖然它抓老鼠的效率比貓高了一倍，但它終究是隻狗。它有貓所不具有的一些本領，但是也不具備貓的輕盈和迅捷。

就d-left狗抓老鼠的本領來說，它已經跻身了bloom貓家族的貴族行列。在bloom filter的所有變種中，它大概有資格被稱為前面提到的實質性的突破。Bloom filter的一個先天不足就是不支援删除集合元素，這些年出了這麼多變種，實用的支援删除操作的變種也不過就是counting bloom filter。Counting bloom filter好是好，但畢竟占用的空間是标準bloom filter的4倍。現在d-left counting bloom filter的出現将counting bloom filter的空間占用減少到原來的一半甚至更少，這毫無疑問是巨大的突破。

當然它也不是沒有缺點。前面提到d-left狗不具備貓的輕盈和迅捷，這是由它狗的本質所決定的。Counting bloom貓雖然比它的祖宗bloom貓肥了4倍，但它終究是隻貓，有一些貓的共性。在很多應用領域，比如summary cache，counting bloom filter并不單獨使用，在表示本地動态變化的集合時采用counting bloom filter，而在與其它節點交換資訊時将counting bloom filter轉為标準的bloom filter在網絡上傳送。Counting bloom貓雖然能力強，但是太肥，跑不動，跑路的事兒還是交給它的祖宗bloom貓去幹吧。在這類應用中，d-left狗就傻眼了，它想跟身輕如燕的bloom貓一起配合抓老鼠，但bloom貓不幹啊，貓狗之間完全沒法溝通，除了打架還能幹什麼像樣的工作？

除此之外，d-left counting bloom filter還有其它的問題。雖然論文作者說它是一個很簡單、甚至比counting bloom filter更簡單的結構，但我死活沒有看出這點來。作者本來想直接用d-left hashing的方法将集合的fingerprints一存就了事，沒想到出了一個漏洞，删除時有可能會碰到兩個完全相同的fingerprint。還好作者沒有放棄，趕緊想出了一個亡羊補牢的法子，又引入了d個置換把漏洞抹平。可是漏洞雖然抹平了，但整個hashing操作已經被整了容，不是原汁原味的d-left hashing了。作者沒辦法，隻好說，雖然不是原汁原味了，但也沒關系，将就着用吧，用起來感覺不到差别的。回想bloom filter的簡潔帶來的美感，我實在體會不出d-left counting bloom filter的簡單到底在那裡。

雖然d-left狗不是什麼名門正派，但畢竟走出了一條混血的新路。如果追随者很多，說不定慢慢也就成了名門正派。現在看起來，d-left狗屬于羽翼未豐的小崽兒，需要完善的地方還有很多，這也意味着可以提升的空間還很大。另外，論文中很多需要證明的地方作者都沒有給出，但承諾會在後面雜志上發表時給出完整的理論支援。讓我們拭目以待吧。