前提
未來一段時間開發的項目或者需求會大量使用到Redis，趁着這段時間業務並不太繁忙，抽點時間預習和複習Redis的相關內容。剛好看到博客下面的UV和PV統計，想到了最近看書裏面提到的HyperLogLog數據類型，於是花點時間分析一下它的使用方式和使用場景（暫時不探究HyperLogLog的實現原理）。Redis中HyperLogLog數據類型是Redid 2.8.9引入的，使用的時候確保Redis版本>= 2.8.9。
HyperLogLog簡介
基數計數(cardinality counting)，通常用來統計一個集合中不重複的元素個數。一個很常見的例子就是統計某個文章的UV（Unique Visitor，獨立訪客，一般可以理解為客戶端IP）。大數據量背景下，要實現基數計數，多數情況下不會選擇存儲全量的基數集合的元素，因為可以計算出存儲的內存成本，假設一個每個被統計的元素的平均大小為32bit，那麼如果統計一億個數據，佔用的內存大小為：
32 * 100000000 / 8 / 1024 / 1024 ≈ 381M。
如果有多個集合，並且允許計算多個集合的合併計數結果，那麼這個操作帶來的複雜度可能是毀滅性的。因此，不會使用Bitmap、Tree或者HashSet等數據結構直接存儲計數元素集合的方式進行計數，而是在不追求絕對準確計數結果的前提之下，使用基數計數的概率算法進行計數，目前常見的有概率算法以下三種：
Linear Counting(LC)。LogLog Counting(LLC)。HyperLogLog Counting(HLL)。
所以，HyperLogLog其實是一種基數計數概率算法，並不是Redis特有的，Redis基於C語言實現了HyperLogLog並且提供了相關命令API入口。
Redis的作者Antirez為了紀念Philippe Flajolet對組合數學和基數計算算法分析的研究，所以在設計HyperLogLog命令的時候使用了Philippe Flajolet姓名的英文首字母PF作為前綴。也就是說，Philippe Flajolet博士是HLL算法的重大貢獻者，但是他其實並不是Redis中HyperLogLog數據類型的開發者。遺憾的是Philippe Flajolet博士於2011年3月22日因病在巴黎辭世。這個是Philippe Flajolet博士的維基百科照片：
Redis提供的HyperLogLog數據類型的特徵：
- 基本特徵：使用
HyperLogLog Counting(HLL)實現，只做基數計算，不會保存元數據。 - 內存佔用：
HyperLogLog每個KEY最多佔用12K的內存空間，可以計算接近2^64個不同元素的基數，它的存儲空間採用稀疏矩陣存儲，空間佔用很小，僅僅在計數基數個數慢慢變大，稀疏矩陣佔用空間漸漸超過了閾值時才會一次性轉變成稠密矩陣，轉變成稠密矩陣之後才會佔用12K的內存空間。 - 計數誤差範圍：基數計數的結果是一個標準誤差（
Standard Error）為0.81%的近似值，當數據量不大的時候，得到的結果也可能是一個準確值。
內存佔用小（每個KEY最高佔用12K）是HyperLogLog的最大優勢，而它存在兩個相對明顯的限制：
- 計算結果並不是準確值，存在標準誤差，這是由於它本質上是用概率算法導致的。
- 不保存基數的元數據，這一點對需要使用元數據進行數據分析的場景並不友好。
HyperLogLog命令使用
Redis提供的HyperLogLog數據類型一共有三個命令API：PFADD、PFCOUNT和PFMERGE。
PFADD
PFADD命令參數如下：
PFADD key element [element …]
支持此命令的Redis版本是：>= 2.8.9
時間複雜度：每添加一個元素的複雜度為O(1)
- 功能：將所有元素參數
element添加到鍵為key的HyperLogLog數據結構中。
PFADD命令的執行流程如下：
PFADD命令的使用方式如下：
127.0.0.1:6379> PFADD food apple fish
(integer) 1
127.0.0.1:6379> PFADD food apple
(integer) 0
127.0.0.1:6379> PFADD throwable
(integer) 1
127.0.0.1:6379> SET name doge
OK
127.0.0.1:6379> PFADD name throwable
(error) WRONGTYPE Key is not a valid HyperLogLog string value.
雖然HyperLogLog數據結構本質是一個字符串，但是不能在String類型的KEY使用HyperLogLog的相關命令。
PFCOUNT
PFCOUNT命令參數如下：
PFCOUNT key [key …]
支持此命令的Redis版本是：>= 2.8.9
時間複雜度：返回單個HyperLogLog的基數計數值的複雜度為O(1)，平均常數時間比較低。當參數為多個key的時候，複雜度為O(N)，N為key的個數。
- 當
PFCOUNT命令使用單個key的時候，返回儲存在給定鍵的HyperLogLog數據結構的近似基數，如果鍵不存在， 則返回0。 - 當
PFCOUNT命令使用多個key的時候，返回儲存在給定的所有HyperLogLog數據結構的並集的近似基數，也就是會把所有的HyperLogLog數據結構合併到一個臨時的HyperLogLog數據結構，然後計算出近似基數。
PFCOUNT命令的使用方式如下：
127.0.0.1:6379> PFADD POST:1 ip-1 ip-2
(integer) 1
127.0.0.1:6379> PFADD POST:2 ip-2 ip-3 ip-4
(integer) 1
127.0.0.1:6379> PFCOUNT POST:1
(integer) 2
127.0.0.1:6379> PFCOUNT POST:1 POST:2
(integer) 4
127.0.0.1:6379> PFCOUNT NOT_EXIST_KEY
(integer) 0
PFMERGE
PFMERGE命令參數如下：
PFMERGE destkey sourcekey [sourcekey ...]
支持此命令的Redis版本是：>= 2.8.9
時間複雜度：O(N)，其中N為被合併的HyperLogLog數據結構的數量，此命令的常數時間比較高
- 功能：把多個
HyperLogLog數據結構合併為一個新的鍵為destkey的HyperLogLog數據結構，合併后的HyperLogLog的基數接近於所有輸入HyperLogLog的可見集合（Observed Set）的並集的基數。 - 命令返回值：只會返回字符串
OK。
PFMERGE命令的使用方式如下
127.0.0.1:6379> PFADD POST:1 ip-1 ip-2
(integer) 1
127.0.0.1:6379> PFADD POST:2 ip-2 ip-3 ip-4
(integer) 1
127.0.0.1:6379> PFMERGE POST:1-2 POST:1 POST:2
OK
127.0.0.1:6379> PFCOUNT POST:1-2
(integer) 4
使用HyperLogLog統計UV的案例
假設現在有個簡單的場景，就是統計博客文章的UV，要求UV的計數不需要準確，也不需要保存客戶端的IP數據。下面就這個場景，使用HyperLogLog做一個簡單的方案和編碼實施。
這個流程可能步驟的先後順序可能會有所調整，但是要做的操作是基本不變的。先簡單假設，文章的內容和統計數據都是後台服務返回的，兩個接口是分開設計。引入Redis的高級客戶端Lettuce依賴：
<dependency>
<groupId>io.lettuce</groupId>
<artifactId>lettuce-core</artifactId>
<version>5.2.1.RELEASE</version>
</dependency>
編碼如下：
public class UvTest {
private static RedisCommands<String, String> COMMANDS;
@BeforeClass
public static void beforeClass() throws Exception {
// 初始化Redis客戶端
RedisURI uri = RedisURI.builder().withHost("localhost").withPort(6379).build();
RedisClient redisClient = RedisClient.create(uri);
StatefulRedisConnection<String, String> connect = redisClient.connect();
COMMANDS = connect.sync();
}
@Data
public static class PostDetail {
private Long id;
private String content;
}
private PostDetail selectPostDetail(Long id) {
PostDetail detail = new PostDetail();
detail.setContent("content");
detail.setId(id);
return detail;
}
private PostDetail getPostDetail(String clientIp, Long postId) {
PostDetail detail = selectPostDetail(postId);
String key = "puv:" + postId;
COMMANDS.pfadd(key, clientIp);
return detail;
}
private Long getPostUv(Long postId) {
String key = "puv:" + postId;
return COMMANDS.pfcount(key);
}
@Test
public void testViewPost() throws Exception {
Long postId = 1L;
getPostDetail("111.111.111.111", postId);
getPostDetail("111.111.111.222", postId);
getPostDetail("111.111.111.333", postId);
getPostDetail("111.111.111.444", postId);
System.out.println(String.format("The uv count of post [%d] is %d", postId, getPostUv(postId)));
}
}
輸出結果：
The uv count of post [1] is 4
可以適當使用更多數量的不同客戶端IP調用getPostDetail()，然後統計一下誤差。
題外話-如何準確地統計UV
如果想要準確統計UV，則需要注意幾個點：
- 內存或者磁盤容量需要準備充足，因為就目前的基數計數算法來看，沒有任何算法可以在不保存元數據的前提下進行準確計數。
- 如果需要做用戶行為分析，那麼元數據最終需要持久化，這一點應該依託於大數據體系，在這一方面筆者沒有經驗，所以暫時不多說。
假設在不考慮內存成本的前提下，我們依然可以使用Redis做準確和實時的UV統計，簡單就可以使用Set數據類型，增加UV只需要使用SADD命令，統計UV只需要使用SCARD命令（時間複雜度為O(1)，可以放心使用）。舉例：
127.0.0.1:6379> SADD puv:1 ip-1 ip-2
(integer) 2
127.0.0.1:6379> SADD puv:1 ip-3 ip-4
(integer) 2
127.0.0.1:6379> SCARD puv:1
(integer) 4
如果這些統計數據僅僅是用戶端展示，那麼可以採用異步設計：
在體量小的時候，上面的所有應用的功能可以在同一個服務中完成，消息隊列可以用線程池的異步方案替代。
小結
這篇文章只是簡單介紹了HyperLogLog的使用和統計UV的使用場景。總的來說就是：在（1）原始數據量巨大，（2）內存佔用要求盡可能小，（3）允許計數存在一定誤差並且（4）不要求存放元數據的場景下，可以優先考慮使用HyperLogLog進行計數。
參考資料：
- antirez-Redis new data structure: the HyperLogLog
- Redis Commands
- 維基百科
（本文完 c-3-d e-a-20191117）
技術公眾號（《Throwable文摘》），不定期推送筆者原創技術文章（絕不抄襲或者轉載）：
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※帶您來了解什麼是 USB CONNECTOR ?
※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面
※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!
※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
※教你寫出一流的銷售文案?