https://sado0823.github.io/assets/js/d8d6c8c8.c08f5c45.js

1"use strict";(self.webpackChunkgo_kitx_webside=self.webpackChunkgo_kitx_webside||[]).push([[9344],{3905:function(e,t,n){n.d(t,{Zo:function(){return s},kt:function(){return d}});var r=n(7294);function a(e,t,n){return t in e?Object.defineProperty(e,t,{value:n,enumerable:!0,configurable:!0,writable:!0}):e[t]=n,e}function o(e,t){var n=Object.keys(e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(e);t&&(r=r.filter((function(t){return Object.getOwnPropertyDescriptor(e,t).enumerable}))),n.push.apply(n,r)}return n}function l(e){for(var t=1;t<arguments.length;t++){var n=null!=arguments[t]?arguments[t]:{};t%2?o(Object(n),!0).forEach((function(t){a(e,t,n[t])})):Object.getOwnPropertyDescriptors?Object.defineProperties(e,Object.getOwnPropertyDescriptors(n)):o(Object(n)).forEach((function(t){Object.defineProperty(e,t,Object.getOwnPropertyDescriptor(n,t))}))}return e}function i(e,t){if(null==e)return{};var n,r,a=function(e,t){if(null==e)return{};var n,r,a={},o=Object.keys(e);for(r=0;r<o.length;r++)n=o[r],t.indexOf(n)>=0||(a[n]=e[n]);return a}(e,t);if(Object.getOwnPropertySymbols){var o=Object.getOwnPropertySymbols(e);for(r=0;r<o.length;r++)n=o[r],t.indexOf(n)>=0||Object.prototype.propertyIsEnumerable.call(e,n)&&(a[n]=e[n])}return a}var p=r.createContext({}),c=function(e){var t=r.useContext(p),n=t;return e&&(n="function"==typeof e?e(t):l(l({},t),e)),n},s=function(e){var t=c(e.components);return r.createElement(p.Provider,{value:t},e.children)},u={inlineCode:"code",wrapper:function(e){var t=e.children;return r.createElement(r.Fragment,{},t)}},m=r.forwardRef((function(e,t){var n=e.components,a=e.mdxType,o=e.originalType,p=e.parentName,s=i(e,["components","mdxType","originalType","parentName"]),m=c(n),d=a,f=m["".concat(p,".").concat(d)]||m[d]||u[d]||o;return n?r.createElement(f,l(l({ref:t},s),{},{components:n})):r.createElement(f,l({ref:t},s))}));function d(e,t){var n=arguments,a=t&&t.mdxType;if("string"==typeof e||a){var o=n.length,l=new Array(o);l[0]=m;var i={};for(var p in t)hasOwnProperty.call(t,p)&&(i[p]=t[p]);i.originalType=e,i.mdxType="string"==typeof e?e:a,l[1]=i;for(var c=2;c<o;c++)l[c]=n[c];return r.createElement.apply(null,l)}return r.createElement.apply(null,n)}m.displayName="MDXCreateElement"},4770:function(e,t,n){n.r(t),n.d(t,{assets:function(){return s},contentTitle:function(){return p},default:function(){return d},frontMatter:function(){return i},metadata:function(){return c},toc:function(){return u}});var r=n(7462),a=n(3366),o=(n(7294),n(3905)),l=["components"],i={slug:"bloom-filter",title:"Go Bloom Filter",authors:["sado"],tags:["golang","bloom","redis"],date:"2022-05-25T00:22"},p="Go Bloom Filter",c={permalink:"/blog/bloom-filter",source:"@site/blog/bloom-filter/2022-05-25-bloom-filter.md",title:"Go Bloom Filter",description:"A go bloom filter , base on different implement like redis ...",date:"2022-05-25T00:22:00.000Z",formattedDate:"May 25, 2022",tags:[{label:"golang",permalink:"/blog/tags/golang"},{label:"bloom",permalink:"/blog/tags/bloom"},{label:"redis",permalink:"/blog/tags/redis"}],readingTime:3.14,truncated:!0,authors:[{name:"sado",title:"Developer",url:"https://github.com/sado0823",imageURL:"/img/avatar.jpeg",key:"sado"}],frontMatter:{slug:"bloom-filter",title:"Go Bloom Filter",authors:["sado"],tags:["golang","bloom","redis"],date:"2022-05-25T00:22"},prevItem:{title:"bbr\u81ea\u9002\u5e94\u9650\u6d41\u7b97\u6cd5",permalink:"/blog/bbr-limit"},nextItem:{title:"Clean Architecture",permalink:"/blog/clean-architecture"}},s={authorsImageUrls:[void 0]},u=[{value:"what?",id:"what",level:2},{value:"why?",id:"why",level:2},{value:"how?",id:"how",level:2},{value:"\u57fa\u672c\u601d\u60f3",id:"\u57fa\u672c\u601d\u60f3",level:3},{value:"\u6e90\u7801\u5206\u6790",id:"\u6e90\u7801\u5206\u6790",level:3},{value:"example",id:"example",level:3},{value:"\u9879\u76ee\u5730\u5740",id:"\u9879\u76ee\u5730\u5740",level:2},{value:"references",id:"references",level:2}],m={toc:u};function d(e){var t=e.components,i=(0,a.Z)(e,l);return(0,o.kt)("wrapper",(0,r.Z)({},m,i,{components:t,mdxType:"MDXLayout"}),(0,o.kt)("br",null),"A go bloom filter , base on different implement like `redis` ...",(0,o.kt)("h2",{id:"what"},"what?"),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-js"},"\u4e0a\u4e00\u7bc7\u5728\u63d0\u5230\u7f13\u5b58\u51fb\u7a7f\u7684\u65f6\u5019, \u6709\u4e00\u79cd\u89e3\u51b3\u529e\u6cd5\u5c31\u662f\u5e03\u9686\u8fc7\u6ee4\u5668\n\n\n\u5e03\u9686\u8fc7\u6ee4\u5668\uff08\u82f1\u8a9e\uff1aBloom Filter\uff09\u662f1970\u5e74\u7531\u5e03\u9686\u63d0\u51fa\u7684\u3002 \u5b83\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a\u5f88\u957f\u7684\u4e8c\u8fdb\u5236\u5411\u91cf\u548c\u4e00\u7cfb\u5217\u968f\u673a\u6620\u5c04\u51fd\u6570\u3002 \u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u7528\u4e8e\u68c0\u7d22\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\u3002 \u5b83\u7684\u4f18\u70b9\u662f\u7a7a\u95f4\u6548\u7387\u548c\u67e5\u8be2\u65f6\u95f4\u90fd\u8fdc\u8fdc\u8d85\u8fc7\u4e00\u822c\u7684\u7b97\u6cd5\uff0c\u7f3a\u70b9\u662f\u6709\u4e00\u5b9a\u7684\u8bef\u8bc6\u522b\u7387\u548c\u5220\u9664\u56f0\u96be\n\n")),(0,o.kt)("h2",{id:"why"},"why?"),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-js"},"\u5e03\u9686\u8fc7\u6ee4\u5668: \u53ef\u4ee5\u5224\u65ad\u67d0\u5143\u7d20\u5728\u4e0d\u5728\u96c6\u5408\u91cc\u9762, \u56e0\u4e3a\u5b58\u5728\u4e00\u5b9a\u7684\u8bef\u5224\u548c\u5220\u9664\u590d\u6742\u95ee\u9898;\n")),(0,o.kt)("p",null,"\u4e00\u822c\u7684\u4f7f\u7528\u573a\u666f\u662f:"),(0,o.kt)("ul",null,(0,o.kt)("li",{parentName:"ul"},"\u9632\u6b62\u7f13\u5b58\u51fb\u7a7f(\u9632\u6b62\u6076\u610f\u653b\u51fb)"),(0,o.kt)("li",{parentName:"ul"},"\u5783\u573e\u90ae\u7bb1\u8fc7\u6ee4"),(0,o.kt)("li",{parentName:"ul"},"cache digests (\u7f13\u5b58\u7d22\u5f15)"),(0,o.kt)("li",{parentName:"ul"},"\u6a21\u578b\u68c0\u6d4b\u5668"),(0,o.kt)("li",{parentName:"ul"},"\u5224\u65ad\u662f\u5426\u5b58\u5728\u67d0\u884c\u6570\u636e,\u7528\u4ee5\u51cf\u5c11\u5bf9\u78c1\u76d8\u8bbf\u95ee\uff0c\u63d0\u9ad8\u670d\u52a1\u7684\u8bbf\u95ee\u6027\u80fd")),(0,o.kt)("h2",{id:"how"},"how?"),(0,o.kt)("h3",{id:"\u57fa\u672c\u601d\u60f3"},"\u57fa\u672c\u601d\u60f3"),(0,o.kt)("p",null,"\u901a\u8fc7\u591a\u4e2a",(0,o.kt)("inlineCode",{parentName:"p"},"hash"),"\u65b9\u6cd5, \u8fdb\u884c\u591a\u6b21 hash \u64cd\u4f5c, \u4f7f\u5176\u503c\u4f4d\u4e8e",(0,o.kt)("inlineCode",{parentName:"p"},"bit"),"\u4e0d\u540c\u4f4d\u4e0a, \u68c0\u6d4b\u8be5",(0,o.kt)("inlineCode",{parentName:"p"},"bit"),"\u4e0a\u7684\u6570\u636e\u662f\u5426\u4e3a",(0,o.kt)("inlineCode",{parentName:"p"}

1,"1"),", \u4ece\u800c\u5224\u65ad\u662f\u5426\u5b58\u5728"),(0,o.kt)("p",null,(0,o.kt)("img",{alt:"image-20210912175241849",src:n(7877).Z,width:"922",height:"558"})),(0,o.kt)("h3",{id:"\u6e90\u7801\u5206\u6790"},"\u6e90\u7801\u5206\u6790"),(0,o.kt)("p",null,(0,o.kt)("inlineCode",{parentName:"p"},"interface: bloom.go")),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-go"},"// \u8fc7\u6ee4\u5668\u7684\u6838\u5fc3\u5b9e\u73b0, \u901a\u8fc7interface\u7684\u65b9\u5f0f, \u53ef\u4ee5\u652f\u6301\u591a\u79cd\u5b9e\u73b0\n// \u76ee\u524d\u5b9e\u73b0\u4e86\u57fa\u4e8eredis bit\u6570\u636e\u7c7b\u578b\u7684\u8fc7\u6ee4\u5668\nProvider interface {\n        Add(data []byte) error\n        Exists(data []byte) (bool, error)\n}\n\n// Filter is a bloom filter\nFilter struct {\n\n        // todo counter\n        total int64\n        hit   int64\n        miss  int64\n\n        provider Provider\n}\n")),(0,o.kt)("p",null,(0,o.kt)("inlineCode",{parentName:"p"},"redis\u5b9e\u73b0: internal/redis/redis_bit.go")),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-js"},"// \u5b9e\u73b0Provider\u63a5\u53e3\u7684\u4e24\u4e2a\u65b9\u6cd5\n\n// Add implement Provider interface\nfunc (r *Provider) Add(data []byte) error {\n    location := r.getBitLocation(data)\n    return r.set(location)\n}\n\n// Exists implement Provider interface\nfunc (r *Provider) Exists(data []byte) (bool, error) {\n    location := r.getBitLocation(data)\n    return r.check(location)\n}\n\n// \u6838\u5fc3\u65b9\u6cd5\n// \u901a\u8fc714\u6b21hash, \u6bcf\u6b21hash\u90fd\u5728\u6570\u636e\u6700\u540e\u8ffd\u52a0\u4e00\u4e2abyte(index), \u6700\u540e\u8fdb\u884c\u53d6\u6a21, \u5206\u5e03\u5728map\u91cc\u9762\u7684\u6bcf\u4e2a\u533a\u95f4\n// \u68c0\u67e5\u662f\u5426\u5b58\u5728\u65f6, \u5bf9\u6bcf\u4e2abit\u4f4d\u8fdb\u884c\u5224\u65ad, \u5982\u679c\u6709\u4e00\u4e2a\u7b49\u4e8e0, \u5219\u6570\u636e\u4e0d\u5b58\u5728\n// getBitLocation return data hash to bit location\nfunc (r *Provider) getBitLocation(data []byte) []uint {\n    l := make([]uint, maps)\n    for i := 0; i < maps; i++ {\n        hashV := r.hash(append(data, byte(i)))\n        l[i] = uint(hashV % uint64(maps))\n    }\n    return l\n}\n")),(0,o.kt)("p",null,(0,o.kt)("inlineCode",{parentName:"p"},"todo")),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-js"},"1) \u53ef\u4ee5\u5b9e\u73b0\u7edf\u8ba1\u6570\u636e, \u6bd4\u5982\u603b\u91cf, \u547d\u4e2d\u7387, \u4e22\u5931\u7387\u7b49\n\n2) \u5b9e\u73b0\u5176\u5b83bloom\u8fc7\u6ee4\u5668provider(\u76ee\u524d\u53ea\u6709\u57fa\u4e8eredis bit)\n")),(0,o.kt)("h3",{id:"example"},"example"),(0,o.kt)("pre",null,(0,o.kt)("code",{parentName:"pre",className:"language-go"},'func test() {\n    filter := NewRedis("127.0.0.1:6379", "test-bloom", 1024)\n\n    _ = filter.Add([]byte("a"))\n    _ = filter.Add([]byte("b))\n\n    _, _ = filter.Exists([]byte("a))\n    _, _ = filter.Exists([]byte("p))\n}\n\n')),(0,o.kt)("h2",{id:"\u9879\u76ee\u5730\u5740"},"\u9879\u76ee\u5730\u5740"),(0,o.kt)("p",null,(0,o.kt)("a",{parentName:"p",href:"https://github.com/sado0823/go-bloom"},"https://github.com/sado0823/go-bloom")),(0,o.kt)("h2",{id:"references"},"references"),(0,o.kt)("p",null,"1.",(0,o.kt)("a",{parentName:"p",href:"https://github.com/tal-tech/go-zero"},"https://github.com/tal-tech/go-zero")),(0,o.kt)("p",null,"2.",(0,o.kt)("a",{parentName:"p",href:"http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html"},"http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html")))}d.isMDXComponent=!0},7877:function(e,t,n){t.Z=n.p+"assets/images/image-bloom-25cf9272ab459f129a866230a7b5bdc3.png"}}]);