https://gitlab.com/zhangxin1932/java-tools.git (java-tools for redis5.0)
全文代碼及安裝均基于 Redis5.0
1.Redis中的布隆過濾器 (驗證某X是否在某Y中, 防緩存穿透)
2.Redis去重計數(shù) (大批量數(shù)據(jù))
3.Redis實現(xiàn)分布式計數(shù)器 (限流 & 接口請求次數(shù)統(tǒng)計)
4.Redis GEO (附近的人, 商店)
1.Redis中的布隆過濾器 (驗證某X是否在某Y中, 防緩存穿透)
http://www.itdecent.cn/p/28b97568299b (參考此文即可)
2.Redis去重計數(shù) (大批量數(shù)據(jù))
2.1 HyperLogLog (模糊去重計數(shù)版本)
2.1.1 概述
在說明 HyperLogLog 之前，我們需要先了解一個概念：基數(shù)統(tǒng)計。維基百科中的解釋是：
[cardinality of a set is a measure of the “number of elements“ of the set.]
它的意思是：
一個集合（注意：這里集合的含義是 Object 的聚合，可以包含重復(fù)元素）中不重復(fù)元素的個數(shù)。
例如集合 {1,2,3,1,2}，它有5個元素，但它的基數(shù)/Distinct 數(shù)為3。
Redis 最常用的數(shù)據(jù)結(jié)構(gòu)有字符串、列表、字典、集合和有序集合。
后來，由于 Redis 的廣泛應(yīng)用，Redis 自身也做了很多補(bǔ)充，其中就有 HyperLogLog（2.8.9 版本添加）結(jié)構(gòu)。
HyperLogLog 是用來做基數(shù)統(tǒng)計的算法，HyperLogLog 的優(yōu)點(diǎn)是，
在輸入元素的數(shù)量或者體積非常大時，計算基數(shù)所需的空間總是固定的、并且是很小的。
2.1.2 Redis HyperLogLog 結(jié)構(gòu)
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html (關(guān)于HyperLogLog算法)
在 Redis 中每個鍵占用的內(nèi)容都是 12K，理論存儲近似接近 2^64 個值，不管存儲的內(nèi)容是什么。
這是一個基于基數(shù)估計的算法，只能比較準(zhǔn)確的估算出基數(shù)，
可以使用少量固定的內(nèi)存去存儲并識別集合中的唯一元素。
但是這個估算的基數(shù)并不一定準(zhǔn)確，是一個帶有 0.81% 標(biāo)準(zhǔn)誤（standard error）的近似值。
但是，也正是因為只有 12K 的存儲空間，所以，它并不實際存儲數(shù)據(jù)的內(nèi)容。
2.1.3 Redis HyperLogLog 應(yīng)用場景
鑒于 HyperLogLog 不保存數(shù)據(jù)內(nèi)容的特性，所以，它只適用于一些特定的場景。
比如: 計算日活、7日活、月活數(shù)據(jù)。
微信公眾號文章的閱讀數(shù)，網(wǎng)頁的 UV 統(tǒng)計(可利用cookie)。
// 為啥采用這種方式呢?
如果我們通過解析日志，把 ip 信息（或用戶 id）放到集合中，例如：HashSet。
如果數(shù)量不多則還好，但是假如每天訪問的用戶有幾百萬。無疑會占用大量的存儲空間。
且計算月活時，還需要將一個整月的數(shù)據(jù)放到一個 Set 中，這隨時可能導(dǎo)致我們的程序 OOM。
2.1.4 Redis HyperLogLog 命令
Redis 為 HyperLogLog提供了三個命令：PFADD、PFCOUNT、PFMERGE。
1.PFADD
將任意數(shù)量的元素添加到指定的 HyperLogLog 里面。
時間復(fù)雜度： 每添加一個元素的復(fù)雜度為 O(1) 。
>> 如果 HyperLogLog 估計的近似基數(shù)（approximated cardinality）在命令執(zhí)行之后出現(xiàn)了變化，
那么命令返回 1 ， 否則返回 0 。
>> 如果命令執(zhí)行時給定的鍵不存在， 那么程序?qū)⑾葎?chuàng)建一個空的 HyperLogLog 結(jié)構(gòu)， 然后再執(zhí)行命令。
2.PFCOUNT
>> 當(dāng) PFCOUNT key [key …] 命令作用于單個鍵時，返回儲存在給定鍵的 HyperLogLog 的近似基數(shù)，
如果鍵不存在，那么返回 0，復(fù)雜度為 O(1)，并且具有非常低的平均常數(shù)時間；
>> 當(dāng) PFCOUNT key [key …] 命令作用于多個鍵時，返回所有給定 HyperLogLog 的并集的近似基數(shù)，
這個近似基數(shù)是通過將所有給定 HyperLogLog 合并至一個臨時 HyperLogLog 來計算得出的，
復(fù)雜度為 O(N)，常數(shù)時間也比處理單個 HyperLogLog 時要大得多。
3.PFMERGE
>> 將多個 HyperLogLog 合并（merge）為一個 HyperLogLog，
合并后的 HyperLogLog 的基數(shù)接近于所有輸入 HyperLogLog 的可見集合（observed set）的并集。
時間復(fù)雜度是 O(N)，其中 N 為被合并的 HyperLogLog 數(shù)量，不過這個命令的常數(shù)復(fù)雜度比較高。
>> 命令格式：PFMERGE destkey sourcekey [sourcekey …]
合并得出的 HyperLogLog 會被儲存在 destkey 鍵里面，
如果該鍵并不存在，那么命令在執(zhí)行之前，會先為該鍵創(chuàng)建一個空的 HyperLogLog。
[zhangxin@JD install-prefix-redis]$ bin/redis-cli -p 26379
127.0.0.1:26379> pfadd alipay20200205 001 002 003
(integer) 1
127.0.0.1:26379> pfadd alipay20200206 001 004 005
(integer) 1
127.0.0.1:26379> pfmerge alipay202002 alipay20200205 alipay20200206
OK
127.0.0.1:26379> pfcount alipay20200205
(integer) 3 // 這里計數(shù)某一天的數(shù)據(jù)
127.0.0.1:26379> pfcount alipay202002
(integer) 5 // 這里計算2月份數(shù)據(jù)時, 進(jìn)行了去重計數(shù)
127.0.0.1:26379>
2.1.5 java代碼實現(xiàn)
java實現(xiàn)去重計數(shù).png
2.2 位圖 (精確去重計數(shù)版本)
2.2.1 概述
#Bitmap(即Bitset)
Bitmap是一串連續(xù)的2進(jìn)制數(shù)字（0或1），每一位所在的位置為偏移(offset)，
在bitmap上可執(zhí)行AND（與） OR（或） NOT（非） XOR（異或）以及其它位操作。
#位圖計數(shù)（Population Count）
位圖計數(shù)統(tǒng)計的是bitmap中值為1的位的個數(shù)。位圖計數(shù)的效率很高，
例如，一個bitmap包含10億個位，90%的位都置為1，
在一臺MacBook Pro上對其做位圖計數(shù)需要 21.1 ms。
SSE4甚至有對整形(integer)做位圖計數(shù)的硬件指令。
2.2.2 實用命令
setbit命令
>> 語法：SETBIT key offset value
>> 對 key 所儲存的字符串值，設(shè)置或清除指定偏移量上的位(bit)。
>> 位的設(shè)置或清除取決于 value 參數(shù)，必須是 0 或 1 。
>> offset 參數(shù)必須大于或等于 0 ，小于 2^32 (bit 映射被限制在 512 MB 之內(nèi))。
>> offset 較大的操作，內(nèi)存分配可能造成 Redis 服務(wù)器被阻塞。
# 命令示例
[zhangxin@JD install-prefix-redis]$ bin/redis-cli -p 26379
127.0.0.1:26379> setbit k 2 0
(integer) 0
127.0.0.1:26379> setbit k 3 1
(integer) 0
getbit命令
>> 語法：GETBIT key offset
>> 對 key 所儲存的字符串值，獲取指定偏移量上的位(bit)。
>> 當(dāng) offset 比字符串值的長度大，或者 key 不存在時，返回 0 。
# 命令示例
[zhangxin@JD install-prefix-redis]$ bin/redis-cli -p 26379
# 對已存在的 offset 進(jìn)行 GETBIT, 返回 1
127.0.0.1:26379> exists k
(integer) 1
127.0.0.1:26379> getbit k 3
(integer) 1
# 對不存在的 offset 進(jìn)行 GETBIT, 返回 0
127.0.0.1:26379> exists k1
(integer) 0
127.0.0.1:26379> getbit k 99
(integer) 0
bitcount命令
>> BITCOUNT key [start] [end]
>> 計算給定字符串中，被設(shè)置為 1 的比特位的數(shù)量。
>> 一般情況下，給定的整個字符串都會被進(jìn)行計數(shù)，
通過指定額外的 start 或 end 參數(shù)，可以讓計數(shù)只在特定的位上進(jìn)行。
start 和 end 參數(shù)的設(shè)置和 GETRANGE 命令類似，都可以使用負(fù)數(shù)值：
比如 -1 表示最后一個位，而 -2 表示倒數(shù)第二個位，以此類推。
# 命令示例
[zhangxin@JD install-prefix-redis]$ bin/redis-cli -p 26379
127.0.0.1:26379> setbit k1 120 1
(integer) 0
127.0.0.1:26379> setbit k1 122 1
(integer) 0
127.0.0.1:26379> setbit k1 121 0
(integer) 0
127.0.0.1:26379> bitcount k1
(integer) 2
127.0.0.1:26379> bitcount k1 0 1
(integer) 0
127.0.0.1:26379> bitcount k1 15 16
(integer) 2
127.0.0.1:26379> bitcount k1 14 15
(integer) 2
bitpos命令
>> 語法：bittops key bit [start] [end]
>> 返回位圖中第一個值為bit的二進(jìn)制位的位置
>> 在默認(rèn)情況下,命令將檢測到的整個位圖,但用戶也可以通過可選的start參數(shù)和end參數(shù)指定要檢測的范圍
>> start和end指的單位是字節(jié)[byte]
>> 如果我們查找設(shè)置位（位參數(shù)為1）并且字符串為空或僅由零字節(jié)組成，則返回-1。
# 命令示例
[zhangxin@JD install-prefix-redis]$ bin/redis-cli -p 26379
127.0.0.1:26379> setbit k 2 0
(integer) 0
127.0.0.1:26379> setbit k 3 1
(integer) 0
127.0.0.1:26379> setbit k 5 1
(integer) 0
127.0.0.1:26379> bitpos k 0
(integer) 0
#返回位圖中第一個值為 1 的二進(jìn)制位的位置
127.0.0.1:26379> bitpos k 1
(integer) 3
#返回位圖中[0-10字節(jié)中]第一個值為 1 的二進(jìn)制位的位置
127.0.0.1:26379> bitpos k 1 0 10
(integer) 3
#返回位圖中[1-10字節(jié)中]第一個值為 1 的二進(jìn)制位的位置
127.0.0.1:26379> bitpos k 1 1 10
(integer) -1
bitop命令
>> BITOP operation destkey key [key ...]
>> 對一個或多個保存二進(jìn)制位的字符串 key 進(jìn)行位元操作，并將結(jié)果保存到 destkey 上。
>> operation 可以是 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種：
-- BITOP AND destkey key [key ...] ，對一個或多個 key 求邏輯并，并將結(jié)果保存到 destkey 。
-- BITOP OR destkey key [key ...] ，對一個或多個 key 求邏輯或，并將結(jié)果保存到 destkey 。
-- BITOP XOR destkey key [key ...] ，對一個或多個 key 求邏輯異或，并將結(jié)果保存到 destkey 。
-- BITOP NOT destkey key ，對給定 key 求邏輯非，并將結(jié)果保存到 destkey 。
>> 除了 NOT 操作之外，其他操作都可以接受一個或多個 key 作為輸入。
>> 處理不同長度的字符串
>> 當(dāng) BITOP 處理不同長度的字符串時，較短的那個字符串所缺少的部分會被看作 0 。
>> 空的 key 也被看作是包含 0 的字符串序列。
2.2.3 應(yīng)用場景
場景一: 統(tǒng)計活躍用戶數(shù)
Redis支持對String類型的value進(jìn)行基于二進(jìn)制位的置位操作。
通過將一個用戶的id對應(yīng)value上的一位，通過對活躍用戶對應(yīng)的位進(jìn)行置位，
就能夠用一個value記錄所有活躍用戶的信息。
如下圖所未，下圖中的bitmap有9個位被置為1，表示這9個位上對應(yīng)的用戶是今天的活躍用戶。
其中第15位表示uid為15的用戶，第一位表示uid為0的用戶。
如果你的uid不是從1開始的，比如從100000開始，
實際上你也可以相應(yīng)的用uid減去初始值來表示其位數(shù)，
比如1000000用戶對應(yīng)到bitmap的第一位。
圖片.png
具體的代碼類似下面這樣：
[
redis.setbit(play:yyyy-mm-dd, user_id, 1)
]
這樣一次記錄的復(fù)雜度是O(1)，在Redis中速度非?？臁?而我們通過每天換用一個不同的key來將每天的活躍用戶狀態(tài)記錄分開存。
并且可以通過一些與或運(yùn)算計算出N天活躍用戶，和連接N天活躍用戶這樣的統(tǒng)計數(shù)據(jù)。
如下圖，第一行表示星期一的活躍用戶情況，第二行表示周二的，以此類推。
為樣我們通過對N天的活躍用戶記錄取并集操作，就能得出在N天內(nèi)活躍過的用戶列表。
圖片.png
https://www.cnblogs.com/hzjjames/p/redis_bit.html (Redis位圖)
https://blog.csdn.net/weixin_34292959/article/details/93850749 (Redis位圖)
https://blog.csdn.net/sen7747/article/details/84991871 (Redis位圖的一些問題)
2.3 咆哮位圖 (精確去重計數(shù)版本--省內(nèi)存版本)
>> 如果要統(tǒng)計一篇文章的閱讀量，可以直接使用 Redis 的 incr 指令來完成。
>> 如果要求閱讀量必須按用戶去重，那就可以使用 set 來記錄閱讀了這篇文章的所有用戶 id，
獲取 set 集合的長度就是去重閱讀量。
>> 但是如果爆款文章閱讀量太大，set 會浪費(fèi)太多存儲空間。
此時可以使用 Redis 提供的 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)來代替 set，
它只會占用最多 12k 的存儲空間就可以完成海量的去重統(tǒng)計。
但是它犧牲了準(zhǔn)確度，它是模糊計數(shù)，誤差率約為 0.81%。
那么有沒有一種不怎么浪費(fèi)空間的精確計數(shù)方法呢？
我們首先想到的就是位圖，可以使用位圖的一個位來表示一個用戶id。
如果一個用戶id是32字節(jié)，那么使用位圖就只需要占用 1/256 的空間就可以完成精確計數(shù)。
但是如何將用戶id映射到位圖的位置呢？
如果用戶id是連續(xù)的整數(shù)這很好辦，但是通常用戶系統(tǒng)的用戶id并不是整數(shù)，
而是字符串或者是有一定隨機(jī)性的大整數(shù)。
我們可以強(qiáng)行給每個用戶id賦予一個整數(shù)序列，然后將用戶id和整數(shù)的對應(yīng)關(guān)系存在redis中。
[
$next_user_id = incr user_id_seq
set user_id_xxx $next_user_id
$next_user_id = incr user_id_seq
set user_id_yyy $next_user_id
$next_user_id = incr user_id_seq
set user_id_zzz $next_user_id
]
#這里你也許會提出疑問，你說是為了節(jié)省空間，這里存儲用戶id和整數(shù)的映射關(guān)系就不浪費(fèi)空間了么？
{
這個問題提的很好，但是同時我們也要看到這個映射關(guān)系是可以復(fù)用的，
它可以統(tǒng)計所有文章的閱讀量，還可以統(tǒng)計簽到用戶的日活、月活，
還可以用在很多其它的需要用戶去重的統(tǒng)計場合中。
有了這個映射關(guān)系，我們就很容易構(gòu)造出每一篇文章的閱讀打點(diǎn)位圖，
來一個用戶，就將相應(yīng)位圖中相應(yīng)的位置為一。
如果位從0變成1，那么就可以給閱讀數(shù)加1。這樣就可以很方便的獲得文章的閱讀數(shù)。
而且我們還可以動態(tài)計算閱讀了兩篇文章的公共用戶量有多少？
將兩個位圖做一下 AND 計算，然后統(tǒng)計位圖中位 1 的個數(shù)。
同樣，還可以有 OR 計算、XOR 計算等等都是可行的。
}
#問題又來了！Redis 的位圖是密集位圖，什么意思呢？
如果有一個很大的位圖，它只有最后一個位是 1，其它都是零，
這個位圖還是會占用全部的內(nèi)存空間，這就不是一般的浪費(fèi)了。
你可以想象大部分文章的閱讀量都不大，但是它們的占用空間卻是很接近的，
和哪些爆款文章占據(jù)的內(nèi)存差不多。
看來這個方案行不通，我們需要想想其它方案！這時咆哮位圖（RoaringBitmap）來了。
它將整個大位圖進(jìn)行了分塊，如果整個塊都是零，那么這整個塊就不用存了。
但是如果位1比較分散，每個塊里面都有1，雖然單個塊里的1很少，
這樣只進(jìn)行分塊還是不夠的，那該怎么辦呢？
我們再想想，對于單個塊，是不是可以繼續(xù)優(yōu)化？
如果單個塊內(nèi)部位 1 個數(shù)量很少，我們可以只存儲所有位1的塊內(nèi)偏移量（整數(shù)），
也就是存一個整數(shù)列表，那么塊內(nèi)的存儲也可以降下來。
這就是單個塊位圖的稀疏存儲形式 —— 存儲偏移量整數(shù)列表。
只有單塊內(nèi)的位1超過了一個閾值，才會一次性將稀疏存儲轉(zhuǎn)換為密集存儲。
咆哮位圖除了可以大幅節(jié)約空間之外，還會降低 AND、OR 等位運(yùn)算的計算效率。
以前需要計算整個位圖，現(xiàn)在只需要計算部分塊。
如果塊內(nèi)非常稀疏，那么只需要對這些小整數(shù)列表進(jìn)行集合的 AND、OR 運(yùn)算，如是計算量還能繼續(xù)減輕。
這里既不是用空間換時間，也沒有用時間換空間，而是用邏輯的復(fù)雜度同時換取了空間和時間。
咆哮位圖的位長最大為 2^32，對應(yīng)的空間為 512M（普通位圖），
位偏移被分割成高 16 位和低 16 位，高 16 位表示塊偏移，
低16位表示塊內(nèi)位置，單個塊可以表達(dá) 64k 的位長，也就是 8K 字節(jié)。最多會有64k個塊。
現(xiàn)代處理器的 L1 緩存普遍要大于 8K，這樣可以保證單個塊都可以全部放入 L1 Cache，可以顯著提升性能。
如果單個塊所有的位全是零，那么它就不需要存儲。
具體某個塊是否存在也可以是用位圖來表達(dá)，當(dāng)塊很少時，
用整數(shù)列表表示，當(dāng)塊多了就可以轉(zhuǎn)換成普通位圖。
整數(shù)列表占用的空間少，它還有類似于 ArrayList 的動態(tài)擴(kuò)容機(jī)制避免反復(fù)擴(kuò)容復(fù)制數(shù)組內(nèi)容。
當(dāng)列表中的數(shù)字超出4096個時，會立即轉(zhuǎn)變成普通位圖。
用來表達(dá)塊是否存在的數(shù)據(jù)結(jié)構(gòu)和表達(dá)單個塊數(shù)據(jù)的結(jié)構(gòu)可以是同一個，
因為塊是否存在本質(zhì)上也是 0 和 1，就是普通的位標(biāo)志。
#但是 Redis 并沒有原生支持咆哮位圖這個數(shù)據(jù)結(jié)構(gòu)??？
Redis 確實沒有原生的，但是咆哮位圖的 Redis Module 有。
https://github.com/aviggiano/redis-roaring (Redis Module 咆哮位圖)
3.Redis實現(xiàn)分布式計數(shù)器 (限流 & 接口請求次數(shù)統(tǒng)計)
http://www.itdecent.cn/p/f6189078514e (參考此文即可)
譬如一個手機(jī)號一天限制發(fā)送5條短信、一個接口一分鐘限制多少請求、一個接口一天限制調(diào)用多少次等等。
使用Redis的Incr自增命令可以輕松實現(xiàn)以上需求。
4.Redis GEO (附近的人)
4.1 概述
自Redis 3.2開始，Redis基于geohash和有序集合提供了地理位置相關(guān)功能。
Redis Geo模塊包含了以下6個命令：
>> GEOADD: 將給定的位置對象（緯度、經(jīng)度、名字）添加到指定的key;
>> GEOPOS: 從key里面返回所有給定位置對象的位置（經(jīng)度和緯度）;
>> GEODIST: 返回兩個給定位置之間的距離;
>> GEOHASH: 返回一個或多個位置對象的Geohash表示;
>> GEORADIUS:
以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過給定最大距離的所有位置對象;
>> GEORADIUSBYMEMBER:
以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。
4.2 應(yīng)用場景
應(yīng)用場景1
組合使用GEOADD和GEORADIUS可實現(xiàn)“附近的人”中“增”和“查”的基本功能。
要實現(xiàn)微信中“附近的人”功能，也可直接使用GEORADIUSBYMEMBER命令。
其中“給定的位置對象”即為用戶本人，搜索的對象為其他用戶。
不過本質(zhì)上，GEORADIUSBYMEMBER = GEOPOS + GEORADIUS，
即先查找用戶位置再通過該位置搜索附近滿足位置相互距離條件的其他用戶對象。
其他場景
這個功能在做搖一搖或者周邊餐飲、車輛時非常有用。
http://www.gpsspg.com/maps.htm (查看某地點(diǎn)的經(jīng)緯度工具網(wǎng)站)
https://blog.csdn.net/ruanhao1203/article/details/88742179
參考資源
https://mp.weixin.qq.com/s/oMdmM8Lfc5EsswQ5GifEOg
https://zhuanlan.zhihu.com/p/58358264 (Redis-HyperLogLog)
https://juejin.im/post/5cf5c817e51d454fbf5409b0 (Redis精確去重計數(shù))
https://mp.weixin.qq.com/s/2uSr2YOjtLbUdHI01qc4rw (附近的人實現(xiàn)原理)
https://blog.csdn.net/tx542009/article/details/87970254 (核心參考)
