{"id":1997,"date":"2023-04-01T11:29:59","date_gmt":"2023-04-01T03:29:59","guid":{"rendered":"https:\/\/www.appblog.cn\/?p=1997"},"modified":"2023-04-07T20:06:39","modified_gmt":"2023-04-07T12:06:39","slug":"playing-redis-exploring-the-principles-of-hyperloglog","status":"publish","type":"post","link":"https:\/\/www.appblog.cn\/index.php\/2023\/04\/01\/playing-redis-exploring-the-principles-of-hyperloglog\/","title":{"rendered":"\u73a9\u8f6cRedis-HyperLogLog\u539f\u7406\u63a2\u7d22"},"content":{"rendered":"<p>\u4e0a\u6587\u300a\u73a9\u8f6cRedis-HyperLogLog\u7edf\u8ba1\u5fae\u535a\u65e5\u6d3b\u6708\u6d3b\u300b\u4ecb\u7ecd\u4e86\u725b\u903c\u54c4\u54c4\u7684HyperLogLog\uff0c\u4f20\u5165\u5143\u7d20\u6570\u91cf\u6216\u4f53\u79ef\u975e\u5e38\u5927\u65f6\uff0cHLL\u6240\u9700\u7a7a\u95f4\u56fa\u5b9a\u4e14\u5f88\u5c0f\u300212kb\u5185\u5b58\u53ef\u8ba1\u7b97\u63a5\u8fd1 2^64 \u4e2a\u4e0d\u540c\u5143\u7d20\u7684\u57fa\u6570\u3002\u5982\u6b64\u5389\u5bb3\uff0c\u600e\u80fd\u4e0d\u7ee7\u7eed\u6df1\u5165\u63a2\u7d22\u5462\uff1f<\/p>\n<p>PS\uff1a\u770b\u5b8c\u8fd9\u7bc7\u6587\u7ae0\uff0c\u4f60\u4f1a\u53d1\u73b0HyperLogLog\u80fd\u7edf\u8ba1\u7684\u57fa\u6570\u503c\u5b9e\u9645\u5e76\u4e0d\u662f 2^64<\/p>\n<h2>\u540d\u8bcd\u89e3\u91ca<\/h2>\n<p><!-- more --><\/p>\n<ul>\n<li>\u57fa\u6570\uff1a\u96c6\u5408\u4e2d\u4e0d\u91cd\u590d\u5143\u7d20\u7684\u4e2a\u6570<\/li>\n<li>HLL\uff1aHyperLogLog \u7684\u7b80\u5199<\/li>\n<\/ul>\n<h2>\u4f2f\u52aa\u5229\u8bd5\u9a8c<\/h2>\n<p>\u4ecb\u7ecdHyperLogLog\u5e95\u5c42\u539f\u7406\u524d\uff0c\u6211\u4eec\u5148\u4e86\u89e3\u4e0b\u4f2f\u52aa\u5229\u8bd5\u9a8c\uff08\u63f4\u5f15\u767e\u5ea6\u767e\u79d1\uff09\u3002<\/p>\n<p>\u4f2f\u52aa\u5229\u8bd5\u9a8c\uff08Bernoulli experiment\uff09\u662f\u5728\u540c\u6837\u7684\u6761\u4ef6\u4e0b\u91cd\u590d\u5730\u3001\u76f8\u4e92\u72ec\u7acb\u5730\u8fdb\u884c\u7684\u4e00\u79cd\u968f\u673a\u8bd5\u9a8c\u3002<\/p>\n<p>\u5176\u7279\u70b9\u662f\u8be5\u968f\u673a\u8bd5\u9a8c\u53ea\u6709\u4e24\u79cd\u53ef\u80fd\u7ed3\u679c\uff1a\u53d1\u751f\u6216\u8005\u4e0d\u53d1\u751f\u3002\u6211\u4eec\u5047\u8bbe\u8be5\u9879\u8bd5\u9a8c\u72ec\u7acb\u91cd\u590d\u5730\u8fdb\u884c\u4e86n\u6b21\uff0c\u90a3\u4e48\u5c31\u79f0\u8fd9\u4e00\u7cfb\u5217\u91cd\u590d\u72ec\u7acb\u7684\u968f\u673a\u8bd5\u9a8c\u4e3an\u91cd\u4f2f\u52aa\u5229\u8bd5\u9a8c\uff0c\u6216\u79f0\u4e3a\u4f2f\u52aa\u5229\u6982\u578b\u3002<\/p>\n<p>\u4ee5\u629b\u786c\u5e01\u4e3a\u4f8b\uff0c\u6bcf\u6b21\u629b\u786c\u5e01\u51fa\u73b0\u6b63\u9762\u7684\u6982\u7387\u90fd\u662f50%\u3002\u5047\u8bbe\u4e00\u76f4\u629b\u786c\u5e01\uff0c\u76f4\u5230\u51fa\u73b0\u6b63\u9762\uff0c\u5219\u4e00\u4e2a\u4f2f\u52aa\u5229\u8bd5\u9a8c\u7ed3\u675f\uff1b<\/p>\n<p>\u5047\u8bbe\u7b2c1\u6b21\u4f2f\u52aa\u5229\u8bd5\u9a8c\u629b\u786c\u5e01\u7684\u6b21\u6570\u4e3aK1\uff0c\u7b2cn\u6b21\u4f2f\u52aa\u5229\u8bd5\u9a8c\u629b\u786c\u5e01\u7684\u6b21\u6570\u4e3aKn\u3002\u6211\u4eec\u8bb0\u5f55\u8fd9n\u6b21\u4f2f\u52aa\u5229\u8bd5\u9a8c\u7684\u6700\u5927\u629b\u786c\u5e01\u6b21\u6570\u4e3aK_max\uff1b<\/p>\n<p>\u7ed3\u5408\u6781\u5927\u4f3c\u7136\u4f30\u7b97\u6cd5\uff0c\u6211\u4eec\u80fd\u5f97\u5230\u4f30\u7b97\u5173\u7cfb n = 2^(K_max)\u3002\u5f53\u7136\uff0c\u7528\u8fd9\u79cd\u65b9\u5f0f\u8ba1\u7b97\u7684\u7ed3\u679c\u4f1a\u6709\u8f83\u5927\u7684\u504f\u5dee\uff0cHyperLogLog\u5185\u90e8\u8fd0\u7528\u4e86<strong>\u5206\u6876\u5e73\u5747<\/strong>\u3001<strong>\u8c03\u548c\u5e73\u5747<\/strong>\u3001<strong>\u504f\u5dee\u4fee\u6b63<\/strong>\u7b49\u4e00\u7cfb\u5217\u6570\u5b66\u4f18\u5316\u65b9\u6848\uff0c\u6d89\u53ca\u8f83\u590d\u6742\u7684\u6570\u5b66\u7b97\u6cd5\uff0c\u6b64\u5904\u6682\u4e0d\u6df1\u5165\u7814\u7a76\u3002<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/n\u91cd\u4f2f\u52aa\u5229\u8bd5\u9a8c.png\" alt=\"n\u91cd\u4f2f\u52aa\u5229\u8bd5\u9a8c\" \/><\/p>\n<p>\u4e0b\u56fe\u7684\u8ba1\u7b97\u516c\u5f0f\u5f15\u81ea\u7f51\u7edc\uff1aHLL\u8ba1\u7b97\u516c\u5f0f<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u8ba1\u7b97\u516c\u5f0f.png\" alt=\"HLL\u8ba1\u7b97\u516c\u5f0f\" \/><\/p>\n<h2>HyperLogLog\u7ed3\u6784<\/h2>\n<p>HyperLogLog\u603b\u4f53\u5206\u4e3a2\u5927\u90e8\u5206\uff1a\u5bf9\u8c61\u5934\u3001\u5bc4\u5b58\u5668\uff08\u6876\uff09\u3002<\/p>\n<table>\n<thead>\n<tr>\n<th style=\"text-align: left;\"><strong>HYLL<\/strong><\/th>\n<th style=\"text-align: left;\"><strong>E<\/strong><\/th>\n<th style=\"text-align: left;\"><strong>N\/U<\/strong><\/th>\n<th style=\"text-align: left;\"><strong>Cardin.<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td style=\"text-align: left;\">4 \u5b57\u8282<\/td>\n<td style=\"text-align: left;\">1 \u5b57\u8282<\/td>\n<td style=\"text-align: left;\">3 \u5b57\u8282<\/td>\n<td style=\"text-align: left;\">8 \u5b57\u8282<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>HLL\u6e90\u7801\u4e2d\u7ed3\u6784\u4f53\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n<pre><code class=\"language-c\">struct hllhdr {\n    char magic[4];       \/* &quot;HYLL&quot;\uff0c\u5bf9\u5e94\u6e90\u7801\u6ce8\u91ca\u4e2d\u7684HYLL*\/\n    uint8_t encoding;    \/* HLL_DENSE or HLL_SPARSE.\u7a00\u758f\/\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u6807\u8bb0\uff0c\u5bf9\u5e94\u6e90\u7801\u6ce8\u91ca\u4e2d\u7684E *\/\n    uint8_t notused[3];  \/* \u4fdd\u75593\u5b57\u8282\u5907\u7528\uff0c\u76ee\u524d\u672a\u4f7f\u7528\uff0c\u503c\u4e3a0\uff0c\u5bf9\u5e94\u6e90\u7801\u6ce8\u91ca\u4e2d\u7684N\/U *\/\n    uint8_t card[8];     \/* Cached cardinality\uff08\u57fa\u6570\u7f13\u5b58\uff09, little endian. \u5bf9\u5e94\u6e90\u7801\u6ce8\u91ca\u4e2d\u7684Cardin\uff0ccardinality&lt;\u57fa\u6570&gt; *\/\n    uint8_t registers[]; \/* Data bytes. *\/\n};<\/code><\/pre>\n<p>HyperLogLog\u5e95\u5c42\u7ed3\u6784\u6709 dense\uff08\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\uff09 \u548c sparse\uff08\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\uff09 2\u79cd\uff0c\u65e0\u8bba\u54ea\u79cd\u5b58\u50a8\u7ed3\u6784\uff0c\u90fd\u6709\u4e00\u4e2a 16 byte \u7684\u5bf9\u8c61\u5934\uff08header\uff09<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u5b58\u50a8\u7ed3\u6784.png\" alt=\"HLL\u5b58\u50a8\u7ed3\u6784\" \/><\/p>\n<h2>HyperLogLog\u5bf9\u8c61\u5934\uff08HLL header\uff09<\/h2>\n<h3>magic\u9b54\u672f\u5b57\u7b26\u4e32<\/h3>\n<p>\u4ece\u5b9a\u4e49\u770b\uff0cmagic\u5360\u7528 4 byte \uff0c\u5b58\u50a8\u7684\u662f\u201cHYLL\u201d\u6807\u8bb0\uff0c\u90a3\u4e48\u5b83\u7a76\u7adf\u6709\u4ec0\u4e48\u7528\u5462\uff1f\u4f7f\u7528\u8fc7HyperLogLog\u7684\u540c\u5b66\u80af\u5b9a\u5bf9\u4e0b\u9762\u8fd9\u4e2a\u5f02\u5e38\u4e0d\u964c\u751f\uff1a<\/p>\n<pre><code class=\"language-bash\">127.0.0.1:6379&gt; set key1 e1\nOK\n127.0.0.1:6379&gt; pfadd key1\n(error) WRONGTYPE Key is not a valid HyperLogLog string value.\n\n127.0.0.1:6379&gt; pfadd hll1 a\n(integer) 1\n127.0.0.1:6379&gt; get hll1\n&quot;HYLL\\x01\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x80q\\xa6\\x84NW&quot;<\/code><\/pre>\n<p>\u5f53\u6211\u4eec\u5bf9\u4e00\u4e2a\u666e\u901a\u5b57\u7b26\u4e32\u4f7f\u7528<code>pfadd<\/code>\u6307\u4ee4\u65f6\uff0c\u4f1a\u63d0\u793astring value \u4e0d\u662fHyperLogLog\u7c7b\u578b<\/p>\n<p>\u7531\u4e8eHyperLogLog\u5e95\u5c42\u7ed3\u6784\u4e5f\u662fstring\uff0c\u90a3\u4e48Redis\u5982\u4f55\u533a\u5206\u4e00\u4e2astring\u4ec5\u4ec5\u662f\u57fa\u7840\u7684\u5b57\u7b26\u4e32\u8fd8\u662fHyperLogLog\u5462\uff1f<\/p>\n<p>\u539f\u6765\u5728\u6267\u884cpf\u76f8\u5173\u6307\u4ee4\u524d\uff0c\u4f1a\u8c03\u7528\u65b9\u6cd5<code>isHLLObjectOrReply()<\/code>\u68c0\u67e5 value\u5bf9\u8c61\u662f\u5426\u662f HyperLogLog\u7ed3\u6784\uff0c\u5982\u679c\u4e0d\u662f\u5219\u8bf4\u660e\u4e0d\u662fHyperLogLog\u7ed3\u6784\uff0c\u5c31\u4f1a\u8fd4\u56de\u4e0a\u8ff0WRONGTYPE\u5f02\u5e38<\/p>\n<p><code>isHLLObjectOrReply()<\/code>\u5176\u4e2d\u4e00\u9879\u6821\u9a8c\u5c31\u662f\u68c0\u67e5 value \u7684magic\u9b54\u672f\u5b57\u7b26\u4e32\u662f\u5426\u662f&quot;HYLL&quot;\uff0c\u4e0d\u662f\u5219\u8bf4\u660e\u4e0d\u662fHyperLogLog\u7ed3\u6784<\/p>\n<p>\u7ec6\u5fc3\u7684\u540c\u5b66\u4e00\u5b9a\u53d1\u73b0\u4e86\uff0c\u4f7f\u7528get\u6307\u4ee4\u83b7\u53d6HyperLogLog\u5bf9\u8c61\u7684\u503c\u65f6\uff0c\u5bf9\u8c61\u5934\u662f\u4ee5&quot;HYLL&quot;\u5f00\u5934\u7684<\/p>\n<p>\u6ce8\u610f\uff1a\u5982\u679cpfcount \u4e00\u4e2a \u4e0d\u5b58\u5728\u7684 key\uff0c\u8fd4\u56de\u7ed3\u679c\u662f0<\/p>\n<h3>encoding\u5b58\u50a8\u7ed3\u6784\u6807\u8bb0<\/h3>\n<p>encoding\uff1a\u5355\u5b57\u8282\u7f16\u7801\uff0cHyperLogLog\u6570\u636e\u7c7b\u578b\u65f6\u503c\u4e3a0\u62161\uff1a<\/p>\n<ul>\n<li>1\u8868\u793a DENSE \u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\uff1b<\/li>\n<li>0\u8868\u793a SPARSE \u7a00\u758f\u5b58\u50a8\u7ed3\u6784\uff1b<\/li>\n<\/ul>\n<p>\u5148\u524d\u63d0\u5230\u7684<code>isHLLObjectOrReply()<\/code>\u65b9\u6cd5\u5728\u68c0\u67e5value\u5bf9\u8c61\u662f\u5426\u662f HyperLogLog\u7ed3\u6784\u65f6\uff0c\u4e5f\u4f1a\u68c0\u67e5 encoding\u503c\uff1a<\/p>\n<ul>\n<li>\u68c0\u67e5encoding\u7684\u503c\u662f\u5426\u662f0\u62161\uff0c\u4e0d\u662f\u5219\u8bf4\u660e\u4e0d\u662fHyperLogLog\u7ed3\u6784<\/li>\n<li>\u5982\u679c\u662f\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\uff0c\u8fd8\u9700\u8981\u6821\u9a8c\u5bf9\u8c61\u957f\u5ea6\u662f\u5426\u548c\u5bc6\u96c6\u8ba1\u6570\u5668\u957f\u5ea6\u76f8\u540c<\/li>\n<\/ul>\n<pre><code class=\"language-c\"># HyperLogLog\u6e90\u7801-\u6821\u9a8cencoding\u503c\n# HLL_MAX_ENCODING\u5b9a\u4e49\u503c\u4e3a1\uff0c\u6709\u8da3\u7684\u662f\u6b64\u5904\u4e0d\u662f\u7528\u7684(encoding !=0 || encoding != 1)\uff0c\u800c\u662f\u76f4\u63a5(encoding &gt; 1)\nif (hdr-&gt;encoding &gt; HLL_MAX_ENCODING) goto invalid;<\/code><\/pre>\n<h3>notused\u548cCardin<\/h3>\n<ul>\n<li>notused\uff1a\u672a\u4f7f\u7528\u76843\u4e2a\u5b57\u8282\uff0c\u76ee\u524d\u672a\u4f7f\u7528\uff0c\u503c\u4e3a0<\/li>\n<li>Cardin\uff1aThe &quot;Cardin.&quot; field is a 64 bit integer\u30028\u5b57\u8282\u7684 \u57fa\u6570\u7f13\u5b58\uff0c\u6b63\u56e0\u4e3a\u6709\u4e86\u57fa\u6570\u7f13\u5b58\uff0c\u624d\u8ba9pfcount\u66f4\u52a0\u9ad8\u6548<\/li>\n<\/ul>\n<h2>\u57fa\u6570\u7f13\u5b58<\/h2>\n<p>\u5728\u6267\u884c<code>pfcount<\/code>\u6307\u4ee4\u65f6\uff0c\u4f1a\u8fd4\u56deHLL\u5bf9\u8c61\u7684\u57fa\u6570\uff0c\u90a3\u4e48\u8fd9\u4e2a\u57fa\u6570\u662f\u5982\u4f55\u5b58\u50a8\u53ca\u8fd4\u56de\u7684\u5462\uff1f\u8ba9\u6211\u4eec\u4e00\u63a2\u7a76\u7adf\uff1a<\/p>\n<p>HLL\u7684\u5bf9\u8c61\u5934\u4e2d\u6709\u4e2aCardin\u57fa\u6570\u7f13\u5b58\uff0c\u5b58\u50a8\u7740HLL\u7684\u57fa\u6570\uff0c\u4fbf\u4e8e\u5feb\u901f\u8fd4\u56de\u57fa\u6570\u503c<\/p>\n<p>HyperLogLog \u7684\u57fa\u6570\u503c\u662f\u7531 16384\u4e2a\u5bc4\u5b58\u5668\uff08\u5bc4\u5b58\u5668\u53c8\u53ef\u53eb\u505a\u6876\uff0c\u6bcf\u4e2a\u68766bit\uff09\u7684\u57fa\u6570\u503c\u8fdb\u884c\u8c03\u548c\u5e73\u5747\u5e76\u4fee\u6b63\u800c\u6765\u3002\u5982\u679c\u6709\u6876\u4f4d\u57fa\u6570\u503c\u6539\u53d8\uff0c\u5219\u5c06\u57fa\u6570\u7f13\u5b58\u6807\u8bb0\u7f6e\u4e3a\u8fc7\u671f\uff0c\u9700\u8981\u7279\u522b\u6ce8\u610f\u7684\u662f\uff0c\u6b64\u65f6\u5e76\u4e0d\u4f1a\u91cd\u65b0\u8ba1\u7b97\u57fa\u6570\u503c\uff0c\u9700\u7b49\u6267\u884c<code>pfcount<\/code>\u6307\u4ee4\u65f6\u624d\u91cd\u65b0\u8ba1\u7b97\u5e76\u5237\u65b0\u7f13\u5b58<\/p>\n<pre><code>\/\/ 1\u5de6\u79fb14\u4f4d\uff082^14\uff09\uff0c\u503c\u4e3a 16384\uff1b\n\n#define HLL_P 14 \/* The greater is P, the smaller the error. *\/\n\n#define HLL_REGISTERS (1&lt;&lt;HLL_P) \/* With P=14, 16384 registers. *\/<\/code><\/pre>\n<p>\u6267\u884c<code>pfcount<\/code>\u6307\u4ee4\u65f6\uff0c\u5148\u5224\u65ad\u57fa\u6570\u7f13\u5b58\u662f\u5426\u8fc7\u671f\uff0c\u672a\u8fc7\u671f\u5219\u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\u503c\uff0c\u5df2\u8fc7\u671f\u5219\u91cd\u65b0\u8ba1\u7b97\u5e76\u7f13\u5b58\u540e\u518d\u8fd4\u56de<\/p>\n<p>\u4f46\u662f\u8fd9\u4e2a\u57fa\u6570\u5e76\u4e0d\u4e00\u5b9a\u662f\u6700\u65b0\u7684\uff0c\u5982\u679ccard\u6700\u9ad8\u4f4d\u662f0\uff0c\u5219\u8bf4\u660e\u7f13\u5b58\u6709\u6548\u3002card\u51718\u5b57\u8282\u537364\u4f4d\uff0c1bit\u6807\u8bb0\u7f13\u5b58\u662f\u5426\u6709\u6548\uff0c63bit\u5b58\u50a8\u57fa\u6570\u503c<\/p>\n<pre><code class=\"language-c\">\/\/ pfcount \u6838\u5fc3\u903b\u8f91\n\nvoid pfcountCommand(client *c) {\n\n    if (\u591akey) {\n        \/\/ \u5408\u5e76\u591a\u4e2aHLL\u540e\u8ba1\u7b97\u57fa\u6570\u5e76\u8fd4\u56de\uff08\u6ce8\u610f\uff1a\u4e0d\u662f\u57fa\u6570\u503c\u4e4b\u548c\uff09\uff1b\n    }\n\n    if (\u5355key\u4e14value\u4e0d\u5b58\u5728) {\n        \/\/ \u5355key\u4e14value\u4e0d\u5b58\u5728\u8fd4\u56de0\uff1b\n    } else { \/\/ \u5355key\u4e14value\u5b58\u5728\n\n        if (HLL_VALID_CACHE(hdr)) {\/\/ \u7f13\u5b58\u6709\u6548\n            \/\/ \u76f4\u63a5\u8fd4\u56de\u57fa\u6570\u7f13\u5b58\u503c\uff1b\n        } else {\/\/ \u7f13\u5b58\u65e0\u6548\n            \/\/ \u8ba1\u7b97\u57fa\u6570\u503c\uff1b\n            \/\/ \u66f4\u65b0\u57fa\u6570\u7f13\u5b58\u6807\u8bb0\u53ca\u57fa\u6570\u7f13\u5b58\u503c\uff1b\n        }\n    }\n}<\/code><\/pre>\n<pre><code class=\"language-c\">\/\/ HLL_INVALIDATE_CACHE\uff1a\u5c06\u57fa\u6570\u7f13\u5b58\u7f6e\u4e3a\u5931\u6548\u72b6\u6001\uff08\u6700\u9ad8\u4f4d\u8bbe\u7f6e\u4e3a1\uff09\n#define HLL_INVALIDATE_CACHE(hdr) (hdr)-&gt;card[7] |= (1&lt;&lt;7)\n\n\/\/ HLL_VALID_CACHE\uff1a\u6821\u9a8c\u7f13\u5b58\u662f\u5426\u6709\u6548\n\/\/ \u6700\u9ad8\u4f4d\u5982\u679c\u4e3a0\uff0c\u8868\u793a\u7f13\u5b58\u6709\u6548\uff0cpfcount\u67e5\u8be2\u57fa\u6570\u65f6\u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\u503c\n#define HLL_VALID_CACHE(hdr) (((hdr)-&gt;card[7] &amp; (1&lt;&lt;7)) == 0)<\/code><\/pre>\n<h2>pfadd\u5e95\u5c42\u903b\u8f91<\/h2>\n<pre><code>pfadd key value<\/code><\/pre>\n<p>HLL\u67092^14 = 16384\u4e2a\u6876\uff0c\u6bcf\u4e2a\u6876\u6709 6 bit\uff1b<\/p>\n<p><code>pfadd<\/code>\u65f6\u9700\u8981\u8ba1\u7b972\u4e2a\u503c\uff1a\u6876\u4f4d\uff08\u5bc4\u5b58\u5668\u7f16\u53f7\uff09 <code>regnum<\/code>\u3001\u6876\u503c\uff08\u5bc4\u5b58\u5668\u8ba1\u6570\u503c\uff09<code>count<\/code><\/p>\n<ul>\n<li>\u4f7f\u7528<code>MurmurHash64A<\/code>\u7b97\u6cd5\u5bf9value\u8fdb\u884chash\uff0c\u7ed3\u679c\u4e3a64bit\u7684hash\u503c\uff08\u6bd4\u7279\u4e32\uff09<\/li>\n<li>\u53d6hash\u503c\u7684\u524d14\u4f4d\uff08\u4f4e14\u4f4d\uff0c\u4ece\u53f3\u8fb9\u5f00\u59cb\u8ba1\u7b97\uff09\u7528\u4e8e\u8ba1\u7b97\u6876\u7f16\u53f7\uff0c\u5c0614\u4f4d\u7684\u4e8c\u8fdb\u5236\u503c\u8f6c\u4e3a10\u8fdb\u5236\uff0c\u8fd9\u4e2a\u503c\u5c31\u662f regnum<\/li>\n<li>\u4ecehash\u503c\u7b2c15\u4f4d\u5f00\u59cb\uff0c\u7edf\u8ba1\u7b2c\u4e00\u4e2a1\u51fa\u73b0\u7684\u4f4d\u7f6e\uff08\u4ece1\u5f00\u59cb\u8ba1\u6570\uff09\uff08\u6e90\u7801\u4e2d\u5199\u7684\u662f\u8fde\u7eed0\u7684\u4e2a\u6570+1\uff09\uff0c\u6b64\u503c\u4e3a count\uff0ccount\u6700\u5927\u4e3a50<\/li>\n<li>\u6839\u636e regnum \u67e5\u8be2 \u5bf9\u5e94\u6876\u4f4d\u5148\u524d\u7684\u503c oldcount<\/li>\n<li>\u5982\u679c count \u503c\u5927\u4e8e oldcount\uff0c\u5219\u66f4\u65b0\u503c\u4e3acount<\/li>\n<\/ul>\n<p>\u8ba9\u6211\u4eec\u770b\u4e2a\u5b9e\u9645\u7684\u4f8b\u5b50\uff1a<\/p>\n<p>\u5047\u8bbehash\u503c\u662f \uff1a{\u6b64\u5904\u7701\u756545\u4f4d}01100 00000000000101<\/p>\n<ul>\n<li>\u524d14\u4f4d\u7684\u4e8c\u8fdb\u5236\u8f6c\u4e3a10\u8fdb\u5236\uff0c\u503c\u4e3a5\uff08regnum\uff09\uff0c\u5373\u6211\u4eec\u628a\u6570\u636e\u653e\u5728\u7b2c5\u4e2a\u6876<\/li>\n<li>\u540e50\u4f4d\u7b2c\u4e00\u4e2a1\u7684\u4f4d\u7f6e\u662f3\uff0c\u5373count\u503c\u4e3a3<\/li>\n<li>registers[5]\u53d6\u51fa\u5386\u53f2\u503coldcount<\/li>\n<li>\u5982\u679ccount &gt; oldcount\uff0c\u5219\u66f4\u65b0 registers[5] = count<\/li>\n<li>\u5982\u679ccount &lt;= oldcount\uff0c\u5219\u4e0d\u505a\u4efb\u4f55\u5904\u7406<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL%20pfadd\u5e95\u5c42\u903b\u8f91.png\" alt=\"HLL pfadd\u5e95\u5c42\u903b\u8f91\" \/><\/p>\n<h2>\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u548c\u7a00\u758f\u5b58\u50a8\u7ed3\u6784<\/h2>\n<p>\u524d\u6587\u6211\u4eec\u63d0\u5230\uff0cHLL\u5e95\u5c42\u67092\u79cd\u5b58\u50a8\u7ed3\u6784\uff1a\u7a00\u758f\u548c\u5bc6\u96c6\u3002<\/p>\n<h3>\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784<\/h3>\n<p>\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u76f8\u5bf9\u5f88\u7b80\u5355\uff0c\u7531\u8fde\u7eed\u768416384\u4e2a\u5bc4\u5b58\u5668\uff08\u6876\uff09\u62fc\u63a5\u800c\u6210\uff0c\u6bcf\u4e2a\u68766 bit<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784.png\" alt=\"HLL\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\" \/><\/p>\n<p>\u4f46\u7531\u4e8e\u4e00\u4e2a\u6876\u53ea\u67096 bit\uff0c\u5728\u8ba1\u7b97\u4e00\u4e2a\u6876\u7684\u8ba1\u6570\u503c\u65f6\uff0c\u53ef\u80fd\u9700\u8981 2\u4e2a\u6876\u62fc\u63a5\u8ba1\u7b97\uff0c\u5373\u4f1a\u6d89\u53ca\u52302\u4e2a\u5b57\u8282\u3002<\/p>\n<p>\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0cHHL\u7684\u5b57\u8282\u90fd\u662f\u5de6\u4f4e\u4f4d\u53f3\u9ad8\u4f4d\uff0c\u6211\u4eec\u5e73\u65f6\u8ba1\u7b97\u4f7f\u7528\u7684\u5b57\u8282\u90fd\u662f\u5de6\u9ad8\u4f4d\u53f3\u4f4e\u4f4d\uff08\u5982\u4e8c\u8fdb\u5236 0101 \u8868\u793a \u5341\u8fdb\u5236 5\uff09\uff0c\u6240\u4ee5\u9700\u8981\u5012\u7f6e\u540e\u8fdb\u884c\u8ba1\u7b97\u3002\u6211\u4eec\u6765\u4e2a\u7b80\u5355\u7684\u56fe\u7406\u89e3\u4e0b\uff0c\u5bc4\u5b58\u5668registers\u8868\u793aHLL\u7684\u5b58\u50a8\u5355\u5143\uff0c\u5b57\u8282buffer\u662f\u5e95\u5c42\u5b58\u50a8\u7ed3\u6784\u3002<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u5bc4\u5b58\u5668\u793a\u610f\u56fe.png\" alt=\"HLL\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u5bc4\u5b58\u5668\u793a\u610f\u56fe\" \/><\/p>\n<p>\u4ee5\u4e0a\u56fe\u4f8b\u4ec5\u4e3a\u65b9\u4fbf\u7406\u89e3\uff0cHLL\u5b9e\u9645\u5b58\u50a8\u8ba1\u7b97\u65b9\u5f0f\u66f4\u52a0\u590d\u6742\uff0c\u6709\u5174\u8da3\u7684\u540c\u5b66\u53ef\u4ee5\u770b\u770b\u4ee5\u4e0b\u6e90\u7801\uff1a<\/p>\n<pre><code class=\"language-c\">\/* Store the value of the register at position &#039;regnum&#039; into variable &#039;target&#039;.\n * &#039;p&#039; is an array of unsigned bytes. *\/\n\n\/*\n  \u83b7\u53d6\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u6307\u5b9a\u5bc4\u5b58\u5668\u7684\u503c\n  target\uff1a\u53d8\u91cf\uff0c\u7528\u6237\u5b58\u653e\u6307\u5b9a\u5bc4\u5b58\u5668\u7f16\u53f7regnum\u76ee\u524d\u7684\u8ba1\u6570\u503c\uff1b\n  p\uff1a\u5bc4\u5b58\u5668\uff1b\n  regnum\uff1a\u5bc4\u5b58\u5668\u7f16\u53f7\uff1b\n*\/\n#define HLL_BITS 6 \/* Enough to count up to 63 leading zeroes. *\/\n#define HLL_REGISTER_MAX ((1&lt;&lt;HLL_BITS)-1)\n\n#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \\\n    uint8_t *_p = (uint8_t*) p; \\\n    unsigned long _byte = regnum*HLL_BITS\/8; \\\n    unsigned long _fb = regnum*HLL_BITS&amp;7; \\\n    unsigned long _fb8 = 8 - _fb; \\\n    unsigned long b0 = _p[_byte]; \\\n    unsigned long b1 = _p[_byte+1]; \\\n    target = ((b0 &gt;&gt; _fb) | (b1 &lt;&lt; _fb8)) &amp; HLL_REGISTER_MAX; \\\n} while(0)\n\n\/* Set the value of the register at position &#039;regnum&#039; to &#039;val&#039;.\n * &#039;p&#039; is an array of unsigned bytes. *\/\n\n\/*\n  \u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784 \u8bbe\u7f6e\u5bc4\u5b58\u5668\u6307\u5b9a\u7f16\u53f7\uff08\u6876\u4f4d\uff09\u7684\u503c\n  p\uff1a\u5bc4\u5b58\u5668\uff1b\n  regnum\uff1a\u5bc4\u5b58\u5668\u7f16\u53f7\uff1b\n  val\uff1a\u5f85\u8bbe\u7f6e\u7684\u8ba1\u6570\u503c\uff1b\n*\/\n#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \\\n    uint8_t *_p = (uint8_t*) p; \\\n    unsigned long _byte = regnum*HLL_BITS\/8; \\\n    unsigned long _fb = regnum*HLL_BITS&amp;7; \\\n    unsigned long _fb8 = 8 - _fb; \\\n    unsigned long _v = val; \\\n    _p[_byte] &amp;= ~(HLL_REGISTER_MAX &lt;&lt; _fb); \\\n    _p[_byte] |= _v &lt;&lt; _fb; \\\n    _p[_byte+1] &amp;= ~(HLL_REGISTER_MAX &gt;&gt; _fb8); \\\n    _p[_byte+1] |= _v &gt;&gt; _fb8; \\\n} while(0)<\/code><\/pre>\n<h3>\u7a00\u758f\u5b58\u50a8\u7ed3\u6784<\/h3>\n<p>\u4e3a\u4ec0\u4e48\u4f1a\u6709\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u5462\uff1f\u8bd5\u60f3\u4e00\u4e0b\uff0c\u5728HLL\u521d\u59cb\u5316\u540e\uff0c\u4ec5\u5c11\u91cf\u6570\u636e\u5b58\u5165\uff0c\u6b64\u65f6\u5927\u91cf\u7684\u5bc4\u5b58\u5668register\uff08\u6876\uff09\u7684\u503c\u90fd\u662f0\uff0c\u5927\u91cf\u76846bit\u5bc4\u5b58\u5668\u7a7a\u95f4\u4e5f\u5c31\u5b8c\u5168\u6d6a\u8d39\u4e86\u3002<\/p>\n<p>Redis\u91c7\u7528\u4e86\u5982\u4e0bopcode\uff08\u6307\u4ee4\uff09\u6781\u81f4\u4f18\u5316\u7a7a\u95f4\u5360\u7528\uff1a<\/p>\n<p><strong>ZERO<\/strong>\uff1a\u8868\u793a\u8fde\u7eed\u591a\u5c11\u4e2a\u6876\u8ba1\u6570\u4e3a0\uff08\u6876\u6570\u6700\u592764\uff09<\/p>\n<ul>\n<li>\u524d2\u4f4d\uff1a\u6807\u5fd7\u4f4d00<\/li>\n<li>\u540e6\u4f4d\uff1a\u8868\u793a\u6876\u6570<\/li>\n<li>\u5360\u75281\u5b57\u8282<\/li>\n<\/ul>\n<p><strong>XZERO<\/strong>\uff1a\u8868\u793a\u8fde\u7eed\u591a\u5c11\u4e2a\u6876\u8ba1\u6570\u4e3a0\uff08\u6876\u6570\u6700\u592716384\uff09<\/p>\n<ul>\n<li>\u524d2\u4f4d\uff1a\u6807\u5fd7\u4f4d01<\/li>\n<li>\u540e14\u4f4d\uff1a\u8868\u793a\u6876\u6570<\/li>\n<li>\u5360\u75282\u5b57\u8282<\/li>\n<\/ul>\n<p><strong>VAL<\/strong>\uff1a\u8868\u793a\u8fde\u7eedxx\u4e2a\u8ba1\u6570\u4e3av\u7684\u6876<\/p>\n<ul>\n<li>\u524d1\u4f4d\uff1a\u6807\u5fd7\u4f4d1<\/li>\n<li>\u4e2d\u95f45\u4f4d\uff1a\u8868\u793a\u503c<\/li>\n<li>\u6700\u540e2\u4f4d\uff1a\u8868\u793a\u6876\u6570<\/li>\n<li>\u5360\u75281\u5b57\u8282<\/li>\n<li>\u793a\u4f8b\uff1a1vvvvvxx\uff0cxx\u503c\u6700\u592732\uff0cvvvvv\u6570\u503c+1<\/li>\n<\/ul>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u64cd\u4f5c\u7801.png\" alt=\"HLL\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u64cd\u4f5c\u7801\" \/><\/p>\n<p>\u73b0\u5728\u56de\u8fc7\u5934\u6765\u770b\u770b\u5148\u524d\u7684HLL\u7ed3\u6784\u56fe\u662f\u4e0d\u662f\u5c31\u66f4\u6e05\u6670\u4e86\u5462\u3002<\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HLL\u7a00\u758f\u5b58\u50a8\u7ed3\u6784.png\" alt=\"HLL\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\" \/><\/p>\n<h3>\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u4f55\u65f6\u8f6c\u4e3a\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784<\/h3>\n<p>\u8f6c\u6362\u6761\u4ef6\u67092\u4e2a\uff0c\u6ee1\u8db3\u4efb\u610f\u4e00\u4e2a\u5c31\u4f1a\u7acb\u5373\u8f6c\u6362\uff1a<\/p>\n<ul>\n<li>\u4efb\u610f\u4e00\u4e2a\u5bc4\u5b58\u5668\u7684\u503c\u4ece32\u53d8\u621033\uff08\u524d\u9762\u5df2\u7ecf\u63d0\u5230\uff0c\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u4e0bval\u7684\u6700\u5927\u503c\u662f 32\uff0c\u4ee3\u7801\u4e2d\u5bf9\u5e94\u53d8\u91cf\u662f<code>HLL_SPARSE_VAL_MAX_VALUE = 32<\/code>\uff09<\/li>\n<li>\u7a00\u758f\u5b58\u50a8\u5360\u7528\u7684\u603b\u5b57\u8282\u6570\u8d85\u8fc7 3000 \u5b57\u8282\uff08\u8fd9\u4e2a\u9608\u503c\u53ef\u4ee5\u901a\u8fc7<code>redis.conf<\/code>\u914d\u7f6e\u6587\u4ef6\u7684<code>hll-sparse-max-bytes<\/code>\u8fdb\u884c\u8c03\u6574\uff09<\/li>\n<\/ul>\n<p>\u6ce8\u610f\uff1a<\/p>\n<ul>\n<li>\u7a00\u758f\u8f6c\u4e3a\u5bc6\u96c6\u5b58\u50a8\u7ed3\u6784\u662f\u4e0d\u53ef\u9006\u7684<\/li>\n<li><code>hll-sparse-max-bytes<\/code>\u914d\u7f6e\u8d85\u8fc716000\u5c31\u6ca1\u6709\u610f\u4e49\u4e86\uff0c\u5982\u679cCPU\u8d44\u6e90\u8db3\u591f\uff0c\u4f46\u5185\u5b58\u8d44\u6e90\u7d27\u5f20\u65f6\uff0c\u5efa\u8bae\u8bbe\u7f6e\u621010000<\/li>\n<\/ul>\n<pre><code class=\"language-c\"># this limit, it is converted into the dense representation.\n#\n# A value greater than 16000 is totally useless, since at that point the\n# dense representation is more memory efficient.\n#\n# The suggested value is ~ 3000 in order to have the benefits of\n# the space efficient encoding without slowing down too much PFADD,\n# which is O(N) with the sparse encoding. The value can be raised to\n# ~ 10000 when CPU is not a concern, but space is, and the data set is\n# composed of many HyperLogLogs with cardinality in the 0 - 15000 range.\n\nhll-sparse-max-bytes 3000<\/code><\/pre>\n<h2>HyperLogLog\u5f15\u53d1\u7684\u601d\u8003<\/h2>\n<p>\u9996\u5148\u8865\u5145\u4e00\u4e2a\u975e\u5e38\u5b9e\u7528\u7684\u7f51\u7ad9\uff0c\u53ef\u4ee5\u5728\u7ebf\u52a8\u6001\u89c2\u5bdfHyperLogLog\u7b97\u6cd5\uff1a<a target=\"_blank\" rel=\"noopener\" href=\"http:\/\/content.research.neustar.biz\/blog\/hll.html\">http:\/\/content.research.neustar.biz\/blog\/hll.html<\/a><\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.yezhou.me\/AppBlog\/images\/\u6280\u672f\/HyperLogLog\u7b97\u6cd5\u5728\u7ebf\u52a8\u6001\u89c2\u5bdf.png\" alt=\"HyperLogLog\u7b97\u6cd5\u5728\u7ebf\u52a8\u6001\u89c2\u5bdf\" \/><\/p>\n<p>\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0c\u6b64\u7f51\u7ad9 value hash\u540e\u7684\u503c\u662f24\u4f4d\uff0c\u4e0d\u662f<code>HyperLogLog MurmurHash64A()<\/code>\u540e\u768464\u4f4d\uff0c\u4e0d\u8fc7\u4e5f\u4e0d\u5f71\u54cd\u89c2\u5bdf\u5b66\u4e60\u5176\u539f\u7406\u4e86\u3002<\/p>\n<h3>pf \u7684\u5185\u5b58\u5360\u7528\u4e3a\u4ec0\u4e48\u662f 12k\uff1f<\/h3>\n<p>HyperLogLog\u5b9e\u9645\u4f7f\u7528\u4e86<code>2^14 = 16384<\/code>\u4e2a\u6876\uff0c\u6bcf\u4e2a\u6876<code>6bit<\/code>\uff0c\u6700\u5927\u5360\u7528\u5185\u5b58\u5373<code>2^14 * 6 \/ 8 = 12288 Byte = 12 KB<\/code>\uff08\u4e0d\u591a\u4e0d\u5c11\u521a\u597d12KB\uff09\u3002<\/p>\n<p><strong>\u8865\u51451\uff1aHyperLogLog\u5b9e\u9645\u6700\u5927\u5b58\u50a8\u7a7a\u95f4<\/strong><\/p>\n<p>HyperLogLog\u5b9e\u9645\u5360\u7528\u7684\u7a7a\u95f4\u4e3a<code>\u3010header\u3011 + \u3010\u5bc4\u5b58\u5668\u6240\u5360\u7528\u7684\u7a7a\u95f4\u3011<\/code>\uff0c\u6240\u4ee5HyperLogLog\u5b9e\u9645\u5360\u7528\u7a7a\u95f4\u4f1a\u6bd412KB\u7565\u591a\u4e00\u70b9\u513f\u3002<\/p>\n<p><strong>\u8865\u51452\uff1aHyperLogLog\u5b9e\u9645\u6700\u5c0f\u5b58\u50a8\u7a7a\u95f4<\/strong><\/p>\n<p>HyperLogLog\u6700\u5c0f\u5b58\u50a8\u7a7a\u95f4\u662f\u591a\u5c11\u5462\uff1f\u5f53HHL\u57fa\u6570\u4e3a1\u65f6\uff0c1\u5b57\u8282\u8868\u793a\u57fa\u6570\uff0cXZERO\u5360\u75282\u5b57\u8282\u8868\u793a\u4f59\u4e0b\u6240\u6709\u7684\u96f6\u503c\u8ba1\u6570\u5668\uff0c\u6240\u4ee5 HyperLogLog\u6700\u5c0f\u5b58\u50a8\u7a7a\u95f4\u662f3\u5b57\u8282\u7565\u591a\u4e00\u70b9\u513f\uff08\u7b97\u4e0aheader\u5360\u7528\uff09\u3002<\/p>\n<h3>HyperLogLog\u6700\u5927\u7edf\u8ba1\u7684\u6570\u91cf\u662f 2^64 \u5417\uff1f<\/h3>\n<p>MurmurHash64A\u7b97\u6cd5\u5bf9value\u8fdb\u884chash\uff0c\u7ed3\u679c\u4e3a64bit\u7684hash\u503c\uff0c64\u4f4d\u4e8c\u8fdb\u5236\u6700\u5927\u8868\u793a\u7684\u5341\u8fdb\u5236\u662f 2^64 \uff0c\u6240\u4ee5\u6700\u5927\u53ef\u7edf\u8ba1\u57fa\u6570\u503c\u5c31\u662f 2^64 \u4e86\u5417\uff1f<\/p>\n<p>\u4f46\u8fd8\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0cheader\u4e2d8\u5b57\u8282\u7684<strong>\u57fa\u6570\u7f13\u5b58Cardin<\/strong>\uff0c1\u4f4d\u8868\u793a\u7f13\u5b58\u662f\u5426\u6709\u6548\uff0c63\u4f4d\u8868\u793a\u57fa\u6570\u503c\uff0c\u6240\u4ee5<strong>HyperLogLog\u5b9e\u9645\u80fd\u7edf\u8ba1\u7684\u6700\u5927\u6570\u91cf\u662f 2^63<\/strong>\u3002<\/p>\n<h3>\u7a00\u758f\u5b58\u50a8\u7ed3\u6784\u4e3a\u4ec0\u4e48\u65e2\u6709ZERO\u53c8\u6709XZERO\u5462\uff1f<\/h3>\n<ul>\n<li><code>ZERO<\/code>\uff1a\u8868\u793a\u8fde\u7eed\u591a\u5c11\u4e2a\u6876\u8ba1\u6570\u4e3a0\uff08\u6876\u6570\u6700\u592764\uff09\uff1b<\/li>\n<li><code>XZERO<\/code>\uff1a\u8868\u793a\u8fde\u7eed\u591a\u5c11\u4e2a\u6876\u8ba1\u6570\u4e3a0\uff08\u6876\u6570\u6700\u592716384\uff09\uff1b<\/li>\n<\/ul>\n<p>\u56e0\u4e3a1\u4e2a\u5bc4\u5b58\u56686bit\uff0c\u6700\u591a\u53ef\u8868\u793a<code>2^6 = 64<\/code>\u4e2a \u96f6\u503c\u8ba1\u6570\u5668\uff0c\u6240\u4ee5\u9700\u8981XZERO\u6765\u8868\u793a\u66f4\u591a\u7684\u96f6\u503c\u8ba1\u6570\u5668\u3002<\/p>\n<h3>\u6211\u4eec\u80fd\u4eceHyperLogLog\u4e2d\u5b66\u5230\u4ec0\u4e48\uff1f<\/h3>\n<p><strong>\u9700\u8981\u624d\u8ba1\u7b97<\/strong><\/p>\n<p>\u5728\u8ba1\u7b97\u57fa\u6570\u7f13\u5b58\u65f6\uff0cHLL\u5e76\u6ca1\u6709\u5728\u6bcf\u6b21\u5bc4\u5b58\u5668\u66f4\u65b0\u65f6\u5c31\u8ba1\u7b97\uff0c\u800c\u662f\u6267\u884cpfcount\u6307\u4ee4\u65f6\u624d\u8ba1\u7b97\u57fa\u6570\u503c\u5e76\u7f13\u5b58\u3002<\/p>\n<p>HLL\u4e0d\u7acb\u5373\u8ba1\u7b97\u672c\u8d28\u4e0a\u662f\u56e0\u4e3apfadd\u7684\u6267\u884c\u9891\u7387\u8fdc\u9ad8\u4e8epfcount\uff0c\u6240\u4ee5\u6211\u4eec\u4e5f\u4e0d\u80fd\u4e00\u5473\u7684\u91c7\u7528\u6b64\u79cd\u601d\u60f3\u3002\u9002\u5408\u7684\u624d\u662f\u6700\u597d\u7684\u3002<\/p>\n<p><strong>\u5b58\u50a8\u7ed3\u6784\u8f6c\u6362<\/strong><\/p>\n<p>\u4e3a\u4e86\u6700\u5927\u5316\u8282\u7701\u5185\u5b58\u7a7a\u95f4\uff0c\u4e5f\u7b97\u662f\u715e\u8d39\u82e6\u5fc3\u4e86\u3002<\/p>\n<h3>HyperLogLog\u600e\u4e48\u8bfb\uff1f<\/h3>\n<p>\u5b66\u539f\u6c41\u539f\u5473\u7684\u8bfb\u97f3\uff0c\u53ef\u524d\u5f80YouTube\u7684 Redis University \u9891\u9053\u62dc\u542c\u300a<a target=\"_blank\" rel=\"noopener\" href=\"https:\/\/www.youtube.com\/watch?v=UAL2dxl1fsE\" title=\"Redis HyperLogLog Explained\">Redis HyperLogLog Explained<\/a>\u300b<\/p>\n<p>\u8bfb\u97f3\uff1a<code>[\u02c8ha\u026ap\u0259rl\u0254\u02d0\u0261l\u0254\u02d0\u0261]<\/code><\/p>\n<blockquote>\n<p>\u8f6c\u8f7d\u81f3\uff1a<a target=\"_blank\" rel=\"noopener\" href=\"https:\/\/blog.csdn.net\/u010887744\/article\/details\/108041280\">https:\/\/blog.csdn.net\/u010887744\/article\/details\/108041280<\/a><\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>\u4e0a\u6587\u300a\u73a9\u8f6cRedis-HyperLogLog\u7edf\u8ba1\u5fae\u535a\u65e5\u6d3b\u6708\u6d3b\u300b\u4ecb\u7ecd\u4e86\u725b\u903c\u54c4\u54c4\u7684HyperLogLog\uff0c\u4f20\u5165\u5143\u7d20 [&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":[504],"class_list":["post-1997","post","type-post","status-publish","format-standard","hentry","category-redis","tag-hyperloglog"],"_links":{"self":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/posts\/1997","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=1997"}],"version-history":[{"count":0,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/posts\/1997\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/media?parent=1997"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/categories?post=1997"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.appblog.cn\/index.php\/wp-json\/wp\/v2\/tags?post=1997"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}