Redis HyperLogLog 適用於什麼場景 相比於Set和Sorted Set的優劣與決擇

時間 2021-05-12 05:13:38

1樓:

簡單來說,UV統計一定要做,實時UV也是很好的需求,然後redis很貴相對(ECS,相對Mysql),hyperloglog因為占用記憶體較少,結果就是比較省錢。

如果你對redis有多貴沒有概念,可以上阿里雲去看一下資料結算而言,多維查詢是常見問題,這個也可以了解一下UV意義本身就是計數,夠了

2樓:懸衡

HyperLogLog 就是專門用來估算基數(Distinct Value)的資料結構,而不是用來存具體內容。特點是非常的省記憶體,只占用固定幾位元,就可以進行接近天文數字的基數估算。而 Set 和 SortedSet 進行資料儲存時,占用的記憶體會隨著儲存元素的數量線性增長,當然,它儲存的內容也更加詳細。

HyperLogLog 的基本原理其實也不難理解,假設你拋了很多次硬幣,你告訴在這次拋硬幣的過程中最多只有兩次扔出連續的反面,讓我猜你總共拋了多少次硬幣,我敢打賭你拋硬幣的總次數不會太多,相反,如果你和我說最多出現了100次連續的反面,那麼我敢肯定扔硬碟的總次數非常的多,甚至我還可以給出乙個估計,這個估計要怎麼給呢?其實是乙個很簡單的概率問題,假設1代表丟擲正面,0代表反面:

1110100110

上圖的拋硬幣序列為例,其中最長的反面序列是"00",我們順手把後面那個1也給帶上,也就是"001",因為它包括了序列中最長的一串0,所以在序列中肯定只出現過一次,而它在任意序列出現出現且僅出現一次的概率顯然是上圖所示的三個二分之一相乘,也就是八分之一,所以我可以給出乙個估計值,你大概總共拋了8次硬幣。

這個拋硬幣的序列和計數有什麼關係呢?比如在資料庫中,我只要在每次插入一條新的記錄時,計算這條記錄的hash,並且轉換成二進位制,就可以將其看成乙個硬幣序列了,比如:

hash(record) = 1110100110

這樣我在記憶體中就只需要儲存迄今為止所有記錄 hash 的最長連續 0 的長度就可以了,達成了用固定位元長度進行任意大小的基數計算的小目標。

為了提公升準確性,HyperLogLog 還會取 hash 的前幾位作為桶標識進行分桶,在每個桶分別進行計數,取個平均作為最終結果。

HyperLogLog 結構的另乙個特點,就是非常容易合併,只需要去對應桶中的最大值就可以了,比如 [1,2,1] merge [2,1,2] -> [2,2,2]。

現在我們再來理解一下 Redis HyperLogLog 結構的三個操作究竟是什麼意思:

PFADD hll ele:對 ele 算個 hash,找到它所屬的桶,如果 ele 最長連續 0 的長度超過桶中所記錄的最大值,則替換桶中原有值,否則直接忽略

PFCOUNT hll:計算基數,每個桶的估計加起來取個平均

PFMERGE hll3 hll1 hll2:將幾個 HyperLogLog 結構合併,其實就是對應桶取最大值

Redis的所有HyperLogLog結構都是固定的16384個桶(2的14次方),並且有兩種儲存格式:

稀疏格式:HyperLogLog演算法在剛開始的時候,大多數桶其實都是0,稀疏格式通過儲存連續的0的數目,而不是每個0存一遍,大大減小了HyperLogLog剛開始時需要占用的記憶體

緊湊格式:用6個bit表示乙個桶,需要占用12KB記憶體

可見在 Redis 中, HyperLogLog 結構最大記憶體占用不會超過 12KB。

懸衡:十分鐘快速理解 HyperLogLog 演算法

3樓:

假設你有N個女朋友

那這個Set可以存放女朋友的身份證號 set=

# 新交了乙個女朋友

sadd gfs_selfid gf_id

# 總共交了幾個女朋友

scard gfs_selfid

SortedSet可以存放和每個女朋友一起吃飯的次數/一起逛街的次數/一起看電影的次數/呵呵

zset=

# 吃飯了一次,記錄一次

zadd gfs_eat_selfid 1 gf_id

# 總共和某個女朋友吃了幾次飯

zscore gfs_eat_selfid gf_id

Redis的資料都是放在記憶體裡面的,如果你這個女朋友太多太多,比如說你有1億個女朋友,呵呵,記憶體可能就放不下了,所有我們要節約記憶體

怎麼辦?

用HyperLogLog,HLL犧牲了資料的精確性換取記憶體的稀缺性

# 吃飯了一次,記錄一下

pfadd gfs_eat_selfid gf_id

# 總共和某個女朋友吃了幾次飯

pfcount gfs_eat_selfid gf_id

如果有一天你被抽查了,比如被某個女朋友問「我們兩在一起總共吃過幾次飯」?

你摸摸你的腦袋,只能這樣回答:「大概是300次」,吃了這麼多次飯,估計你女朋友也記不住,所以你給乙個大概的數字,差的也不多,因為你還是能根據認識的時間大致估算出來的。

你可能會想,如果資料不準確了,那統計還有什麼意義?

那得看不準確到什麼程度,就好比說乙個人是靠譜的,不是說他從來不犯錯誤,而是很少犯錯誤

HyperLogLog就是這樣,雖然不準確,但是不準確度很低,官方給的數字是0.81%。

當老闆問你今天的UV是多少的時候,你回答105w和106w對老闆來說是沒什麼區別的。

Node js 發展前景如何?適用於哪些場景?

以前的言論顯然已經不適合當今的node,希望有大拿能重新關注這個問題 後端的前台nodejs已經是王了 我大PHP可是世界上最好的語言什麼Node.js不行 node.js上手很快,但是不敢用它來寫大的系統,高負載下慘不忍睹啊,只用來建立聊天之類的需要推送的部份,算是小應用吧 給我的感覺就像是mon...

HPLC適用於什麼物質

DemondeLaplace 高沸點 極性較強的有機化合物 否則,應選擇氣相色譜 如果待測化合物在紫外光下可發射螢光,色譜可以連線螢光檢測器 如果待測化合物有紫外吸收,可以連線二極體陣列檢測器 可同時檢測多波長,並可檢測可見光吸收 或普通紫外檢測器 單波長,不可檢測可見吸收 如果待測化合物沒有紫外吸...

無鎖佇列是否不適用於大容量應用場景?

holidays 題主可以看下dpdk的rte ring實現的無鎖佇列,支援多生產者多消費者 實現上使用了cas原子操作,結構是環形佇列,思路是使用預約生產 消費 來避免多個生產者 消費者 操作同一塊區間。 題主你好。針對大容量高效能場景,你所說的問題的確存在。陣列模式的問題在於它是有界的。鍊錶模式...