華為云PB級數(shù)據(jù)庫GaussDB(for Redis)揭秘第八期：計(jì)數(shù)器的應(yīng)用

1.背景

當(dāng)我們打開手機(jī)刷微博時(shí)，就要開始和各種各樣的計(jì)數(shù)器打交道了。我們注冊一個(gè)帳號(hào)后，微博就會(huì)給我們記錄一組數(shù)據(jù)：關(guān)注數(shù)、粉絲數(shù)、動(dòng)態(tài)數(shù)…；我們刷帖時(shí)，關(guān)注每天的熱搜情況，微博需要為每個(gè)熱搜記錄一組搜索量。在這一串?dāng)?shù)據(jù)后面，是一個(gè)個(gè)計(jì)數(shù)器在工作。

計(jì)數(shù)器可以分為常規(guī)計(jì)數(shù)器和基數(shù)計(jì)數(shù)器，對于常規(guī)計(jì)數(shù)器，只需要對計(jì)數(shù)器進(jìn)行簡單的增減即可；對于基數(shù)計(jì)數(shù)器，需要對元素進(jìn)行去重，比如統(tǒng)計(jì)搜索量時(shí)，需要保證每個(gè)用戶的多次搜索只統(tǒng)計(jì)一次。對于這兩種需求，Redis 都有對應(yīng)的數(shù)據(jù)類型進(jìn)行統(tǒng)計(jì)。然而開源 Redis 是一個(gè)弱一致性的數(shù)據(jù)庫，在特定的場景下，弱一致的計(jì)數(shù)不能滿足業(yè)務(wù)需求，為此，我們需要一個(gè)強(qiáng)一致的數(shù)據(jù)庫進(jìn)行計(jì)數(shù)。

GaussDB(for Redis)（下文簡稱高斯Redis），是華為自研的強(qiáng)一致、持久化 NoSQL 數(shù)據(jù)庫，兼容 Redis5.0 協(xié)議。本文將介紹常規(guī)計(jì)數(shù)器與基數(shù)計(jì)數(shù)器的應(yīng)用場景及使用高斯 Redis 實(shí)現(xiàn)計(jì)數(shù)。

2.常規(guī)計(jì)數(shù)器

2.1如何使用 Redis 進(jìn)行常規(guī)計(jì)數(shù)

Redis 實(shí)現(xiàn)常規(guī)計(jì)數(shù)器有兩種數(shù)據(jù)類型適合：String 和 Hash。

2.1.1使用string 計(jì)數(shù)

當(dāng)我們需要維護(hù)的計(jì)數(shù)器數(shù)目較少，比如統(tǒng)計(jì)網(wǎng)站的注冊用戶數(shù)時(shí)，適合使用 String 類型的計(jì)數(shù)器。Redis 提供的 Incr 和 Decr 命令分別對 String 類型的 key 值進(jìn)行增一與減一操作：

127.0.0.1:6379>SETcounter 100OK127.0.0.1:6379> INCRcounter(integer) 101127.0.0.1:6379>DECRcounter(integer) 100

除Incr與Decr命令外，Redis String 類型還提供 Incrby 與 Decrby 命令，語法格式為：

incrby： INCRBY key count

將 key 增加 count，count 可正可負(fù)，返回 key 的結(jié)果：

127.0.0.1:6379>INCRBYcounter10(integer) 10127.0.0.1:6379>INCRBYcounter-20(integer) -10

decrby： DECRBY key count

將 key 減少 count，count 可正可負(fù)，返回 key 的結(jié)果：

127.0.0.1:6379>DECRBYcounter10(integer) -10127.0.0.1:6379>DECRBYcounter-20(integer) 10

2.1.2使用Hash計(jì)數(shù)

需要維護(hù)多個(gè)密切關(guān)聯(lián)的計(jì)數(shù)器時(shí)，可以使用Hash結(jié)構(gòu)進(jìn)行計(jì)數(shù)。比如，當(dāng)我們注冊一個(gè)微博賬號(hào)時(shí)，微博會(huì)給每個(gè)用戶記錄一些用戶數(shù)據(jù)，比如粉絲數(shù)、關(guān)注數(shù)等，這些數(shù)據(jù)都綁定到對應(yīng)用戶上，因此可以將這組計(jì)數(shù)器記錄在同一個(gè)Hash key中，使用 hincrby 命令，語法格式為：

hincrby： HINCRBY key filed count

將 Hash key 的 filed 增加 count，count 可正可負(fù)，返回對應(yīng) field 的結(jié)果：

127.0.0.1:6379>HGETuseridfield(nil)127.0.0.1:6379>HINCRBYuseridfield1(integer) 1127.0.0.1:6379>HINCRBYuseridfield-1(integer) 127.0.0.1:6379>HGETuseridfield"0"

2.2常規(guī)計(jì)數(shù)器使用場景

常規(guī)計(jì)數(shù)器的使用場景很廣泛，對于社交產(chǎn)品，用戶的粉絲數(shù)、關(guān)注數(shù)，帖子的點(diǎn)贊數(shù)、收藏?cái)?shù)…；對于視頻網(wǎng)站，需要統(tǒng)計(jì)視頻的播放次數(shù)（PV統(tǒng)計(jì)，Page View）；對于電商秒殺，需要統(tǒng)計(jì)商品數(shù)量并進(jìn)行流量控制。在并發(fā)量高的情況下，Redis 的性能優(yōu)勢明顯，非常適合以上場景。

以電商秒殺業(yè)務(wù)為例，為了處理高并發(fā)讀寫，通常在MySQL上層部署Redis作為緩存。為了抗住大流量，使用計(jì)數(shù)器作限流。比如，當(dāng)我們想控制每秒1萬次請求時(shí)，可以初始化一個(gè)counter=10000，隨后每次請求過來，都對counter減一，當(dāng)counter 歸零后，阻塞后續(xù)的請求。每隔一段時(shí)間，重置counter=10000，以此保證大流量不會(huì)沖擊底層的MySQL。

3.基數(shù)統(tǒng)計(jì)：HyperLogLog 的原理及使用

基數(shù)計(jì)數(shù)（cardinality counting）是指在一個(gè)數(shù)據(jù)集合中，統(tǒng)計(jì)不重復(fù)元素的個(gè)數(shù)，是實(shí)際應(yīng)用中一種常見的場景。比如統(tǒng)計(jì)一段時(shí)間內(nèi)訪問某個(gè)網(wǎng)站的用戶數(shù)，網(wǎng)絡(luò)游戲的日活用戶數(shù)量等。

在數(shù)據(jù)量較小情況下，我們可以把所有數(shù)據(jù)保存下來進(jìn)行去重統(tǒng)計(jì)。Redis 中，可以使用 Set 與 Zset 將數(shù)據(jù)保存下來，然后統(tǒng)計(jì)集合中的元素?cái)?shù)量。而當(dāng)數(shù)據(jù)量較大時(shí)，該方法會(huì)消耗較大的存儲(chǔ)空間，需要考慮其它的算法。

考慮一種情況，當(dāng)我們登錄微博時(shí)，微博會(huì)記錄我們的登錄情況，并統(tǒng)計(jì)每天有多少活躍用戶。很顯然，我們不需要也不應(yīng)該記錄活躍用戶的ID，并且，少量誤差對活躍用戶數(shù)量的統(tǒng)計(jì)使用影響不大，這種場景下，我們可以使用 HyperLogLog 進(jìn)行計(jì)數(shù)。HyperLogLog 是一種使用極少內(nèi)存實(shí)現(xiàn)巨量統(tǒng)計(jì)的計(jì)數(shù)算法，非常適合大數(shù)據(jù)場景的基數(shù)估計(jì)，在 Redis 中被實(shí)現(xiàn)為一種數(shù)據(jù)類型。

3.1HyperLogLog 原理介紹

從伯努利試驗(yàn)到基數(shù)計(jì)數(shù)

HyperLogLog 是一種基數(shù)估計(jì)算法，其思想來自于伯努利過程。

簡單來說，伯努利過程就是一個(gè)拋硬幣的過程。拋一次硬幣，結(jié)果為正面或者反面的概率都是1/2。記正面為1，反面為0，如果拋硬幣多次，直到出現(xiàn)第一次正面時(shí)停止，記為一次投擲試驗(yàn)，并且得到一個(gè)投擲結(jié)果的序列，比如“001”，我們可以知道，這個(gè)序列出現(xiàn)的概率是 。

反過來，如果我們持續(xù)進(jìn)行投擲試驗(yàn)，當(dāng)出現(xiàn)第一次“001”序列時(shí)，我們可以簡單估算出，我們投擲試驗(yàn)次數(shù)為8（事實(shí)上，這是一個(gè)極大似然估計(jì)）。

HyperLogLog 的原理就是將每個(gè)元素視為一次投擲試驗(yàn)，通過記錄試驗(yàn)的最大投擲次數(shù)對元素的數(shù)量進(jìn)行估計(jì)。當(dāng)我們向集合中每插入一個(gè)元素，視為做了一次投擲試驗(yàn)，相同的元素對應(yīng)一個(gè)投擲結(jié)果的序列。為了將每一個(gè)元素轉(zhuǎn)化成一個(gè)“01”序列，我們可以使用一個(gè)哈希函數(shù)進(jìn)行轉(zhuǎn)換：

這里，我們有了一個(gè)簡單的估計(jì)算法。我們只需要記錄哈希結(jié)果中第一個(gè)“1”出現(xiàn)的位置的最大值即可，但很明顯，當(dāng)數(shù)據(jù)量較小時(shí)，這樣一個(gè)估計(jì)值誤差會(huì)很大，而且單個(gè)元素的對估計(jì)值的影響不平滑。

分桶平均減小誤差

為了減小單一估計(jì)量的影響，HyperLogLog 使用分桶多次試驗(yàn)的方法減小誤差。方法是將哈希后的bitmap中前若干位當(dāng)成桶的編號(hào)，剩余位當(dāng)成試驗(yàn)結(jié)果。

對于每個(gè)桶中的結(jié)果，計(jì)算其調(diào)和平均值獲取基數(shù)估計(jì)值（相比算術(shù)平均，調(diào)和平均數(shù)能夠有效改善基數(shù)較小情況下極值影響過大的問題）：

3.2Redis 中的 HyperLogLog

Redis 將HyperLogLog 實(shí)現(xiàn)成一種數(shù)據(jù)類型，對于每個(gè)元素，Redis將其Hash成64位的二進(jìn)制串，用低14位用來表示bucket的下標(biāo)（所以桶的個(gè)數(shù)為1<<14=16384），剩余的位用來模擬伯努利分布，每個(gè)桶需要6個(gè)bit；最多能夠?qū)?個(gè)元素進(jìn)行統(tǒng)計(jì)，內(nèi)存占用約12 k；其標(biāo)準(zhǔn)誤差為 0.81%。

Redis 支持的 HyperLogLog 命令只有3個(gè)，pfadd，pfcoun，pfmerge, 其語法如下：

pfadd：將所有元素參數(shù)添加到 HyperLogLog 數(shù)據(jù)結(jié)構(gòu)中

語法：PFADD key element1 [element2…]

如果至少有一個(gè)元素被添加返回1，否則返回0

如果沒有指定 element，則創(chuàng)建 hyperloglog key

127.0.0.1:6379>pfaddkey1ele1ele2(integer) 1127.0.0.1:6379>pfaddkey1(integer) 127.0.0.1:6379>pfaddkey2(integer)

pfcount：返回給定的HyperLogLog的基數(shù)估計(jì)值

語法：PFCOUNT key1 [key2 … ]

返回對應(yīng) HyperLogLog 的基數(shù)值，多個(gè)key時(shí)，返回多個(gè)key的合并后的基數(shù)值。

127.0.0.1:6379>pfcountkey1(integer) 127.0.0.1:6379>pfaddkey1ele1ele2(integer) 1127.0.0.1:6379>pfaddkey2ele1ele3(integer) 1127.0.0.1:6379>pfcountkey1(integer) 2127.0.0.1:6379>pfcountkey1key2(integer) 3

pfmerge：將多個(gè) HyperLogLog 合并為一個(gè)

語法：PFMERGE destkey sourcekey1 [sourcekey2 …]

將 sourcekey 與 destkey 合并，當(dāng) destkey 不存在時(shí)，會(huì)創(chuàng)建 destkey

返回OK

127.0.0.1:6379>pfaddkey1ele1ele2(integer) 1127.0.0.1:6379>pfaddkey2ele1ele3(integer) 1127.0.0.1:6379>pfcountkey3(integer) 127.0.0.1:6379>pfmergekey3key1key2OK127.0.0.1:6379>pfcountkey3(integer) 3

3.3HyperLogLog 的適用場景

HyperLogLog 作為一種計(jì)算大數(shù)據(jù)量的基數(shù)統(tǒng)計(jì)算法，在統(tǒng)計(jì)注冊用戶數(shù)，每日訪問IP數(shù)，實(shí)時(shí)統(tǒng)計(jì)在線用戶數(shù)等場景可以大顯神威。

統(tǒng)計(jì)網(wǎng)站的UV(unique visitor)

對于一個(gè)網(wǎng)頁，我們想要知道這個(gè)網(wǎng)頁的受關(guān)注程度，可以統(tǒng)計(jì)一下有多少用戶（IP）點(diǎn)擊了這個(gè)網(wǎng)頁。為此，我們給每個(gè)時(shí)間段設(shè)置一條記錄，比如，127.0.0.1這個(gè)IP在2021年1月1日1點(diǎn)的時(shí)候訪問了網(wǎng)頁：

pfadd key_prefix_2021010101 "127.0.0.1"

當(dāng)需要統(tǒng)計(jì)這一天0-1點(diǎn)這一個(gè)小時(shí)一共有多少IP訪問了這個(gè)網(wǎng)頁時(shí)：

pfcount key_prefix_2021010101

需要統(tǒng)計(jì)上午8到12點(diǎn)的網(wǎng)頁訪問情況：

pfcount key_prefix_2021010109 …… key_prefix_2021010112

一天結(jié)束了，需要統(tǒng)計(jì)并保存這一天訪問情況：

pfmerge key_prefix_2021010101 ...... key_prefix_2021010124

對于一個(gè)熱門的網(wǎng)頁，這樣一個(gè)計(jì)數(shù)的方式顯然能夠極大的節(jié)約存儲(chǔ)空間。

用戶畫像

用戶畫像是根據(jù)用戶在互聯(lián)網(wǎng)上留下的各種數(shù)據(jù)，給用戶貼上一系列的標(biāo)簽，比如用戶的性別，年齡，愛好等。在進(jìn)行數(shù)據(jù)分析時(shí)，可以使用 HyperLogLog 進(jìn)行數(shù)據(jù)的保存與分析。

1. 對于每個(gè)標(biāo)簽，創(chuàng)建hyperloglog key值保存數(shù)據(jù)，如：man, woman， basketball…等，對于每個(gè)需要記錄的值，都需要?jiǎng)?chuàng)建一個(gè)key進(jìn)行記錄。

2. 每多一個(gè)用戶時(shí)，向所有記錄的key里使用pfadd 添加元素。

3. 進(jìn)行數(shù)據(jù)分析時(shí)，使用 pfcount 將需要分析的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)。

4.高斯Redis在計(jì)數(shù)上的優(yōu)勢

4.1開源 Redis 的問題

生產(chǎn)環(huán)境中，為避免單點(diǎn)故障，增強(qiáng)數(shù)據(jù)庫可用性，Redis 通常將數(shù)據(jù)復(fù)制多個(gè)副本，保存在不同的服務(wù)器上；在大量并發(fā)請求過來時(shí)，為了盡可能利用主從節(jié)點(diǎn)的服務(wù)器資源，可以采用主寫從讀的方式。由于 Redis 的主從同步是異步的，當(dāng)主節(jié)點(diǎn)寫入數(shù)據(jù)后，從節(jié)點(diǎn)不保證立刻更新數(shù)據(jù)，如果此時(shí)讀取數(shù)據(jù)，讀到的就是過期的舊數(shù)據(jù)，產(chǎn)生數(shù)據(jù)不一致問題。

當(dāng)主節(jié)點(diǎn)故障宕機(jī)后，數(shù)據(jù)不一致的問題會(huì)更嚴(yán)重。主節(jié)點(diǎn)故障后，哨兵節(jié)點(diǎn)會(huì)將從節(jié)點(diǎn)提升為主，原主節(jié)點(diǎn)上堆積的數(shù)據(jù) buffer 就徹底丟失了。在電商秒殺業(yè)務(wù)中，如果發(fā)生主節(jié)點(diǎn)復(fù)制buffer堆積，導(dǎo)致從節(jié)點(diǎn)與主節(jié)點(diǎn)的 counter 偏大很多，一旦此時(shí)主節(jié)點(diǎn)宕機(jī)，發(fā)生主備倒換后，容易導(dǎo)致流量壓力超出閾值，大量數(shù)據(jù)可能會(huì)將 MySQL 壓垮，導(dǎo)致系統(tǒng)不可用。

4.2高斯 Redis 如何解決

高斯 Redis 借助高斯品牌的“存算分離”架構(gòu)，將全量數(shù)據(jù)下沉到強(qiáng)一致存儲(chǔ)層（DFV Pool），徹底摒棄了開源 Redis 的異步復(fù)制機(jī)制；計(jì)算層將海量數(shù)據(jù)進(jìn)行分片，在故障場景下，自動(dòng)進(jìn)行接管，實(shí)現(xiàn)了服務(wù)的高可用。

存儲(chǔ)層 DFV Pool 是華為內(nèi)部自研的公司級Data Lake，是分布式、強(qiáng)一致、高性能的先進(jìn)架構(gòu)。底層實(shí)現(xiàn)3副本強(qiáng)一致的存儲(chǔ)，保證了在任何時(shí)間點(diǎn)的數(shù)據(jù)強(qiáng)一致，故障情況下數(shù)據(jù)不丟失，對于秒殺等業(yè)務(wù)滿足計(jì)數(shù)的絕對精確。此外，借助存算分離架構(gòu)，高斯Redis 還擁有低成本、大容量、秒擴(kuò)容等優(yōu)勢：

5.結(jié)語

高斯 Redis 在社區(qū)版 Redis 的基礎(chǔ)上，結(jié)合華為自研強(qiáng)一致存儲(chǔ)DFV Pool，具有強(qiáng)一致、秒擴(kuò)容、超可用、低成本等優(yōu)勢，保證了計(jì)數(shù)的準(zhǔn)確性、可靠性。