{"id":2144,"date":"2023-04-02T11:04:23","date_gmt":"2023-04-02T03:04:23","guid":{"rendered":"https:\/\/www.appblog.cn\/?p=2144"},"modified":"2023-04-05T19:54:38","modified_gmt":"2023-04-05T11:54:38","slug":"solving-cache-penetration-issues-through-blossom-filter","status":"publish","type":"post","link":"https:\/\/www.appblog.cn\/index.php\/2023\/04\/02\/solving-cache-penetration-issues-through-blossom-filter\/","title":{"rendered":"\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u65b9\u5f0f\u89e3\u51b3\u7f13\u5b58\u7a7f\u900f\u95ee\u9898"},"content":{"rendered":"<h2>\u539f\u7406<\/h2>\n<p>\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u5de8\u5927\u7528\u5904\u5c31\u662f\uff0c\u80fd\u591f\u8fc5\u901f\u5224\u65ad\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\u3002\u56e0\u6b64\u4ed6\u6709\u5982\u4e0b\u4e09\u4e2a\u4f7f\u7528\u573a\u666f:<\/p>\n<ul>\n<li>\u7f51\u9875\u722c\u866b\u5bf9URL\u7684\u53bb\u91cd\uff0c\u907f\u514d\u722c\u53d6\u76f8\u540c\u7684URL\u5730\u5740<\/li>\n<li>\u53cd\u5783\u573e\u90ae\u4ef6\uff0c\u4ece\u6570\u5341\u4ebf\u4e2a\u5783\u573e\u90ae\u4ef6\u5217\u8868\u4e2d\u5224\u65ad\u67d0\u90ae\u7bb1\u662f\u5426\u5783\u573e\u90ae\u7bb1\uff08\u540c\u7406\uff0c\u5783\u573e\u77ed\u4fe1\uff09<\/li>\n<li>\u7f13\u5b58\u7a7f\u900f\uff0c\u5c06\u6240\u6709\u53ef\u80fd\u5b58\u5728\u7684\u6570\u636e\u7f13\u5b58\u653e\u5230\u5e03\u9686\u8fc7\u6ee4\u5668\u4e2d\uff0c\u5f53\u9ed1\u5ba2\u8bbf\u95ee\u4e0d\u5b58\u5728\u7684\u7f13\u5b58\u65f6\u8fc5\u901f\u8fd4\u56de\u907f\u514d\u7f13\u5b58\u53caDB\u6302\u6389<\/li>\n<\/ul>\n<p><!-- more --><\/p>\n<p>OK\uff0c\u63a5\u4e0b\u6765\u6211\u4eec\u6765\u8c08\u8c08\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u539f\u7406<\/p>\n<p>\u5176\u5185\u90e8\u7ef4\u62a4\u4e00\u4e2a\u5168\u4e3a0\u7684bit\u6570\u7ec4\uff0c\u9700\u8981\u8bf4\u660e\u7684\u662f\uff0c\u5e03\u9686\u8fc7\u6ee4\u5668\u6709\u4e00\u4e2a\u8bef\u5224\u7387\u7684\u6982\u5ff5\uff0c\u8bef\u5224\u7387\u8d8a\u4f4e\uff0c\u5219\u6570\u7ec4\u8d8a\u957f\uff0c\u6240\u5360\u7a7a\u95f4\u8d8a\u5927\u3002\u8bef\u5224\u7387\u8d8a\u9ad8\u5219\u6570\u7ec4\u8d8a\u5c0f\uff0c\u6240\u5360\u7684\u7a7a\u95f4\u8d8a\u5c0f\u3002<\/p>\n<p>\u5047\u8bbe\uff0c\u6839\u636e\u8bef\u5224\u7387\uff0c\u6211\u4eec\u751f\u6210\u4e00\u4e2a10\u4f4d\u7684bit\u6570\u7ec4\uff0c\u4ee5\u53ca2\u4e2ahash\u51fd\u6570<code>(f_1,f_2)<\/code>\uff0c\u5982\u4e0b\u56fe\u6240\u793a(\u751f\u6210\u7684\u6570\u7ec4\u7684\u4f4d\u6570\u548chash\u51fd\u6570\u7684\u6570\u91cf\uff0c\u6211\u4eec\u4e0d\u7528\u53bb\u5173\u5fc3\u662f\u5982\u4f55\u751f\u6210\u7684\uff0c\u6709\u6570\u5b66\u8bba\u6587\u8fdb\u884c\u8fc7\u4e13\u4e1a\u7684\u8bc1\u660e)\u3002<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/Java\/BloomFilter%20bit\u6570\u7ec4\u521d\u59cb\u5316.png\" alt=\"BloomFilter bit\u6570\u7ec4\u521d\u59cb\u5316\" \/><\/p>\n<p>\u5047\u8bbe\u8f93\u5165\u96c6\u5408\u4e3a<code>((N_1,N_2))<\/code>\uff0c\u7ecf\u8fc7\u8ba1\u7b97<code>(f_1(N_1))<\/code>\u5f97\u5230\u7684\u6570\u503c\u5f97\u4e3a2\uff0c<code>(f_2(N_1))<\/code>\u5f97\u5230\u7684\u6570\u503c\u4e3a5\uff0c\u5219\u5c06\u6570\u7ec4\u4e0b\u6807\u4e3a2\u548c\u4e0b\u8868\u4e3a5\u7684\u4f4d\u7f6e\u7f6e\u4e3a1\uff0c\u5982\u4e0b\u56fe\u6240\u793a<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/Java\/BloomFilter\u7b2c\u4e00\u4e2a\u70b9bit\u6570\u7ec4hash\u586b\u5145.png\" alt=\"BloomFilter\u7b2c\u4e00\u4e2a\u70b9bit\u6570\u7ec4hash\u586b\u5145\" \/><\/p>\n<p>\u540c\u7406\uff0c\u7ecf\u8fc7\u8ba1\u7b97<code>(f_1(N_2))<\/code>\u5f97\u5230\u7684\u6570\u503c\u5f97\u4e3a3\uff0c<code>(f_2(N_2))<\/code>\u5f97\u5230\u7684\u6570\u503c\u4e3a6\uff0c\u5219\u5c06\u6570\u7ec4\u4e0b\u6807\u4e3a3\u548c\u4e0b\u8868\u4e3a6\u7684\u4f4d\u7f6e\u7f6e\u4e3a1\uff0c\u5982\u4e0b\u56fe\u6240\u793a<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/Java\/BloomFilter\u7b2c\u4e8c\u4e2a\u70b9bit\u6570\u7ec4hash\u586b\u5145.png\" alt=\"BloomFilter\u7b2c\u4e8c\u4e2a\u70b9bit\u6570\u7ec4hash\u586b\u5145\" \/><\/p>\n<p>\u8fd9\u4e2a\u65f6\u5019\uff0c\u6211\u4eec\u6709\u7b2c\u4e09\u4e2a\u6570<code>(N_3)<\/code>\uff0c\u6211\u4eec\u5224\u65ad<code>(N_3)<\/code>\u5728\u4e0d\u5728\u96c6\u5408<code>((N_1,N_2))<\/code>\u4e2d\uff0c\u5c31\u8fdb\u884c<code>(f_1(N_3),f_2(N_3))<\/code>\u7684\u8ba1\u7b97<\/p>\n<ul>\n<li>\u82e5\u503c\u6070\u5de7\u90fd\u4f4d\u4e8e\u4e0a\u56fe\u7684\u7ea2\u8272\u4f4d\u7f6e\u4e2d\uff0c\u6211\u4eec\u5219\u8ba4\u4e3a\uff0c<code>(N_3)<\/code>\u5728\u96c6\u5408<code>((N_1,N_2))<\/code>\u4e2d<\/li>\n<li>\u82e5\u503c\u6709\u4e00\u4e2a\u4e0d\u4f4d\u4e8e\u4e0a\u56fe\u7684\u7ea2\u8272\u4f4d\u7f6e\u4e2d\uff0c\u6211\u4eec\u5219\u8ba4\u4e3a\uff0c<code>(N_3)<\/code>\u4e0d\u5728\u96c6\u5408<code>((N_1,N_2))<\/code>\u4e2d<\/li>\n<\/ul>\n<p>\u4ee5\u4e0a\u5c31\u662f\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u8ba1\u7b97\u539f\u7406\uff0c\u4e0b\u9762\u6211\u4eec\u8fdb\u884c\u6027\u80fd\u6d4b\u8bd5\uff0c<\/p>\n<h2>\u6027\u80fd\u6d4b\u8bd5<\/h2>\n<p>(1) \u65b0\u5efa\u4e00\u4e2amaven\u5de5\u7a0b\uff0c\u5f15\u5165guava\u5305<\/p>\n<pre><code class=\"language-xml\">&lt;dependencies&gt;\n    &lt;dependency&gt;\n        &lt;groupId&gt;com.google.guava&lt;\/groupId&gt;     \n        &lt;artifactId&gt;guava&lt;\/artifactId&gt;      \n    &lt;\/dependency&gt;\n&lt;\/dependencies&gt;<\/code><\/pre>\n<p>(2) \u6d4b\u8bd5\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5c5e\u4e8e\u4e00\u4e2a\u767e\u4e07\u5143\u7d20\u96c6\u5408\u6240\u9700\u8017\u65f6<\/p>\n<pre><code class=\"language-java\">import java.util.ArrayList;import java.util.List;\nimport com.google.common.hash.BloomFilter;\nimport com.google.common.hash.Funnels;\n\npublic class Test {\n\n    private static int size = 1000000;\n\n        private static BloomFilter&lt;Integer&gt; bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);\n            public static void main(String[] args) {\n            for (int i = 0; i &lt; size; i++) {\n            bloomFilter.put(i);\n        }\n\n        List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;(1000);\n        \/\/\u6545\u610f\u53d610000\u4e2a\u4e0d\u5728\u8fc7\u6ee4\u5668\u91cc\u7684\u503c\uff0c\u770b\u770b\u6709\u591a\u5c11\u4e2a\u4f1a\u88ab\u8ba4\u4e3a\u5728\u8fc7\u6ee4\u5668\u91cc\n        for (int i = size + 10000; i &lt; size + 20000; i++) {\n            if (bloomFilter.mightContain(i)) {\n                list.add(i);\n            }\n        }\n        System.out.println(&quot;\u8bef\u5224\u7684\u6570\u91cf\uff1a&quot; + list.size());\n    }\n}<\/code><\/pre>\n<p>\u8f93\u51fa\u7ed3\u679c\u5982\u4e0b<\/p>\n<pre><code>\u8bef\u5224\u5bf9\u6570\u91cf\uff1a330<\/code><\/pre>\n<p>\u5982\u679c\u4e0a\u8ff0\u4ee3\u7801\u6240\u793a\uff0c\u6211\u4eec\u6545\u610f\u53d610000\u4e2a\u4e0d\u5728\u8fc7\u6ee4\u5668\u91cc\u7684\u503c\uff0c\u5374\u8fd8\u6709330\u4e2a\u88ab\u8ba4\u4e3a\u5728\u8fc7\u6ee4\u5668\u91cc\uff0c\u8fd9\u8bf4\u660e\u4e86\u8bef\u5224\u7387\u4e3a0.03.\u5373\uff0c\u5728\u4e0d\u505a\u4efb\u4f55\u8bbe\u7f6e\u7684\u60c5\u51b5\u4e0b\uff0c\u9ed8\u8ba4\u7684\u8bef\u5224\u7387\u4e3a0.03\u3002<\/p>\n<p>\u4e0b\u9762\u4e0a\u6e90\u7801\u6765\u8bc1\u660e\uff1a<\/p>\n<pre><code class=\"language-java\">\/**\n * Creates a {@link BloomFilter BloomFilter&lt;T&gt;} with the expected number of\n * insertions and a default expected false positive probability of 3%.\n *\n * &lt;p&gt;Note that overflowing a {@code BloomFilter} with significantly more elements\n * than specified, will result in its saturation, and a sharp deterioration of its\n * false positive probability.\n *\n * &lt;p&gt;The constructed {@code BloomFilter&lt;T&gt;} will be serializable if the provided\n * {@code Funnel&lt;T&gt;} is.\n *\n * &lt;p&gt;It is recommended that the funnel be implemented as a Java enum. This has the\n * benefit of ensuring proper serialization and deserialization, which is important\n * since {@link #equals} also relies on object identity of funnels.\n *\n * @param funnel the funnel of T&#039;s that the constructed {@code BloomFilter&lt;T&gt;} will use\n * @param expectedInsertions the number of expected insertions to the constructed\n *     {@code BloomFilter&lt;T&gt;}; must be positive\n * @return a {@code BloomFilter}\n * @since 19.0\n *\/\n@CheckReturnValue\npublic static &lt;T&gt; BloomFilter&lt;T&gt; create(Funnel&lt;? super T&gt; funnel, long expectedInsertions) {\n    return create(funnel, expectedInsertions, 0.03); \/\/ FYI, for 3%, we always get 5 hash functions\n}<\/code><\/pre>\n<p>\u63a5\u4e0b\u6765\u6211\u4eec\u901a\u8fc7\u8c03\u8bd5\u67e5\u770b<code>numBits<\/code>\u548c<code>numHashFunctions<\/code>\uff1a<\/p>\n<pre><code class=\"language-java\">@VisibleForTesting\nstatic &lt;T&gt; BloomFilter&lt;T&gt; create(\n    Funnel&lt;? super T&gt; funnel, long expectedInsertions, double fpp, Strategy strategy) {\n  checkNotNull(funnel);\n  checkArgument(\n      expectedInsertions &gt;= 0, &quot;Expected insertions (%s) must be &gt;= 0&quot;, expectedInsertions);\n  checkArgument(fpp &gt; 0.0, &quot;False positive probability (%s) must be &gt; 0.0&quot;, fpp);\n  checkArgument(fpp &lt; 1.0, &quot;False positive probability (%s) must be &lt; 1.0&quot;, fpp);\n  checkNotNull(strategy);\n\n  if (expectedInsertions == 0) {\n    expectedInsertions = 1;\n  }\n  \/*\n   * TODO(user): Put a warning in the javadoc about tiny fpp values,\n   * since the resulting size is proportional to -log(p), but there is not\n   * much of a point after all, e.g. optimalM(1000, 0.0000000000000001) = 76680\n   * which is less than 10kb. Who cares!\n   *\/\n  long numBits = optimalNumOfBits(expectedInsertions, fpp);\n  int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);\n  try {\n    return new BloomFilter&lt;T&gt;(new BitArray(numBits), numHashFunctions, funnel, strategy);\n  } catch (IllegalArgumentException e) {\n    throw new IllegalArgumentException(&quot;Could not create BloomFilter of &quot; + numBits + &quot; bits&quot;, e);\n  }\n}<\/code><\/pre>\n<p>\u6765\u770b\u4e00\u4e0b\uff0c\u8bef\u5224\u7387\u4e3a0.03\u65f6\uff0c\u5e95\u5c42\u7ef4\u62a4\u7684bit\u6570\u7ec4\u7684\u957f\u5ea6\u548chash\u51fd\u6570\u6570\u91cf\uff1a<\/p>\n<pre><code>numBits = 7298000\nnumHashFunctions = 5<\/code><\/pre>\n<p>\u5c06bloomfilter\u7684\u6784\u9020\u65b9\u6cd5\u6539\u4e3a<\/p>\n<pre><code class=\"language-java\">private static BloomFilter&lt;Integer&gt; bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01);<\/code><\/pre>\n<p>\u5373\uff0c\u6b64\u65f6\u8bef\u5224\u7387\u4e3a0.01\u3002\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u5e95\u5c42\u7ef4\u62a4\u7684bit\u6570\u7ec4\u7684\u957f\u5ea6\u548chash\u51fd\u6570\u6570\u91cf\uff1a<\/p>\n<pre><code>numBits = 9585000\nnumHashFunctions = 7<\/code><\/pre>\n<p>\u7531\u6b64\u53ef\u89c1\uff0c\u8bef\u5224\u7387\u8d8a\u4f4e\uff0c\u5219\u5e95\u5c42\u7ef4\u62a4\u7684\u6570\u7ec4\u8d8a\u957f\uff0c\u5360\u7528\u7a7a\u95f4\u8d8a\u5927\u3002\u56e0\u6b64\uff0c\u8bef\u5224\u7387\u5b9e\u9645\u53d6\u503c\uff0c\u6839\u636e\u670d\u52a1\u5668\u6240\u80fd\u591f\u627f\u53d7\u7684\u8d1f\u8f7d\u6765\u51b3\u5b9a\uff0c\u4e0d\u662f\u62cd\u8111\u888b\u778e\u60f3\u7684\u3002<\/p>\n<h2>\u5b9e\u9645\u4f7f\u7528<\/h2>\n<p>Redis\u4f2a\u4ee3\u7801\u5982\u4e0b\u6240\u793a<\/p>\n<pre><code class=\"language-java\">String get(String key) {\n    String value = redis.get(key);     \n    if (value  == null) {\n        if (!bloomfilter.mightContain(key)) {\n            return null; \n        } else {\n            bloomFilter.put(key);\n            value = db.get(key); \n            redis.set(key, value); \n        }    \n    }\n    return value\uff1b\n}<\/code><\/pre>\n<p>\uff081\uff09\u4f18\u70b9<\/p>\n<ul>\n<li>\u601d\u8def\u7b80\u5355<\/li>\n<li>\u4fdd\u8bc1\u4e00\u81f4\u6027<\/li>\n<li>\u6027\u80fd\u5f3a<\/li>\n<\/ul>\n<p>\uff082\uff09\u7f3a\u70b9<\/p>\n<ul>\n<li>\u4ee3\u7801\u590d\u6742\u5ea6\u589e\u5927<\/li>\n<li>\u9700\u8981\u53e6\u5916\u7ef4\u62a4\u4e00\u4e2a\u96c6\u5408\u6765\u5b58\u653e\u7f13\u5b58\u7684Key<\/li>\n<li>\u5e03\u9686\u8fc7\u6ee4\u5668\u4e0d\u652f\u6301\u5220\u503c\u64cd\u4f5c<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u7406 \u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u5de8\u5927\u7528\u5904\u5c31\u662f\uff0c\u80fd\u591f\u8fc5\u901f\u5224\u65ad\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\u3002\u56e0\u6b64\u4ed6\u6709\u5982\u4e0b\u4e09\u4e2a\u4f7f\u7528\u573a\u666f: \u7f51\u9875\u722c\u866b\u5bf9U [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[544,543,545],"class_list":["post-2144","post","type-post","status-publish","format-standard","hentry","category-redis","tag-bloomfilter","tag-543","tag-545"],"_links":{"self":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/posts\/2144","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2144"}],"version-history":[{"count":0,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/posts\/2144\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2144"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2144"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}