分散式之redis的三大衍生數據結構

2019 年 12 月 2 日
筆記

引言

說起redis的數據結構，大家可能對五大基礎數據類型比較熟悉:String，Hash，List，Set，Sorted Set。那麼除此之外，還有三大衍生數據結構，大家平時是很少接觸的，即：bitmaps、hyperloglog、geo 另外，我覺得，這三個數據結構，只能說是錦上添花。真正在項目中，我還真沒用過。下面大家來看看這三大數據結構的定義和用途

bitmaps

定義

說到這個bitmaps，其實它就是String，但它可以對String的位進行操作。然後呢，這個位操作，有自己的命令，所以和操作String的redis命令又不大一樣！可以這麼理解

bitmaps為一個以位為單位的數組，數組的每個單元只能存儲0和1

下面舉個例子，比如我們要做一個set操作，key為w，value為h，那麼執行如下命令

127.0.0.1:6379> set w h  OK  127.0.0.1:6379> get w  "h"

那麼h的ASCII為0110 1000 接下來，你可以用位命令getbit命令取出，取出每一位的內容。

127.0.0.1:6379> getbit w 0 #用getbit獲取w第0位的值  (integer) 0  127.0.0.1:6379> getbit w 1 #用getbit獲取w第1位的值  (integer) 1  127.0.0.1:6379> getbit w 2 #用getbit獲取w第2位的值  (integer) 1  127.0.0.1:6379> getbit w 3 #用getbit獲取w第3位的值  (integer) 0

用途

網上傳言，此結構用來統計一定時間內的，活躍的用戶數，使用bitmap的結構比傳統的set結構省空間。然而，這種用途有很大的局限性，我後文會說到。先說一下，網上的說法。假設有30個用戶，其中有5個用戶，在2018-10-04這天登陸了。假設這5個用戶的userid=2，4，8，11，12。那麼，我們假設key為users:2018-10-04，將其value值用於記錄用戶登陸資訊。那麼為了記錄上述5個用戶登陸過，我們將該value值的第2位，第4位，第8位，第11位，第12位設為1，即執行下述命令

127.0.0.1:6379> setbit users:2018-10-04 2 1  (integer) 0  127.0.0.1:6379> setbit users:2018-10-04 4 1  (integer) 0  127.0.0.1:6379> setbit users:2018-10-04 8 1  (integer) 0  127.0.0.1:6379> setbit users:2018-10-04 11 1  (integer) 0  127.0.0.1:6379> setbit users:2018-10-04 12 1  (integer) 0

這個時候，比如你要判斷userid=11的用戶，在2018-10-04這天，有沒有登陸過，就執行下述命令

127.0.0.1:6379> getbit users:2018-10-04 11  (integer) 1

結果為1，就代表用戶登陸過。如果返回結果為0，則代表用戶沒登陸過。如果要統計，2018-10-04，這一天登陸的用戶數，可以執行下面的命令

127.0.0.1:6379> bitcount users:2018-10-04  (integer) 5

上面的命令就可以統計出，2018-10-04，這一天5個用戶登陸過。 ok，到這裡大家就查不多能明白了。先說一下，這裡的userid=2，4，8，11，12，可以理解為偏移量。比如實際項目中的userid位1000002,那麼偏移量就是2。大家在項目中，可以靈活變通。然而這種方式有一個局限性。我們在實際項目中，如果userid是使用uuid生成的，那麼，你要如何根據這些userid生成偏移量？莫非你還要去找一個hash函數，生成偏移量？就算找到了相應的hash函數，你能確保一定不發生hash碰撞，導致偏移量一致？所以，大家了解即可。

HyperLogLog

定義

HyperLogLog並不是一種數據結構，而是一種演算法，可以利用極小的記憶體空間完成獨立總數的統計。其實，大家可能對該演算法比較陌生。我們java中有一個庫叫stream-lib，其中也實現了HyperLogLog演算法。我大概說一下該演算法的原理，我不想去長篇大論的搬出數學論文來，大家看著也無聊，這裡Hyper指的是超級的意思，它的前世是LogLog演算法。這裡我蜻蜓點水的裝13一下，大家能領悟到精髓即可。假設有如下對話

我:"小曲啊，假設啊，我一輪丟5次硬幣，丟了很多輪之後，發現這幾輪中，最多出現連續的2次反面1次正面，你能猜出來我丟了多少輪么！" 小曲:"應該沒幾輪吧，頂多就七八輪。" 我:"卧槽，這麼機智，怎麼算的?" 小曲:"很簡單啊，正反面概率都是1/2,連著二次反面，一次正面。不就是1/21/21/2么！" 我:"那要是最多出現連續的4次反面1次正面呢？" 小曲:"那應該是很多很多輪吧！" 我:"果然機智！"

上述聊天，出自我和同事曲之間的，日常互吹！如有雷同，純屬巧合！

好了，原理講完了！只是他的估算演算法比較複雜！沒這麼簡單而已！而且這麼估，誤差還比較大！下面給出演算法的偽程式碼。

輸入：一個集合  輸出：集合的獨立總數  演算法：       max = 0       對於集合中的每個元素：                 hashCode = hash(元素)                 num = hashCode二進位表示中最前面連續的0的數量                 if num > max:                     max = num       最後的結果是2的(max + 1)次冪

需要說明的是

hashCode = hash(元素)

就是把你的輸入元素，映射成二進位長串。映射成二進位長串後，就可以類比到我最先說的拋硬幣的結果了。至於最後的結果為什麼用(max+1)，大家可以去查文獻。畢竟這文章是在講redis，不是在講這個演算法。而且這個演算法，後面還經過了一系列演進，比如將入參集合分為m個部分，然後將m個部分的結果求一個平均數(avg)，最後以2的(avg + 1)次冪，來估計獨立總數！這些讀者有興趣可以自行查詢！

用途

這個結構可以非常省記憶體的去統計各種計數，比如註冊IP數、每日訪問IP數。當然，存在誤差！Redis官方給出的數字是0.81%的失誤率。用法也很簡單如下所示

127.0.0.1:6379> pfadd ips:2018-10-04 "127.0.0.1" "127.0.0.2" "127.0.0.3" "127.0.0.4"  (integer) 1  127.0.0.1:6379> pfcount ips:2018-10-04  (integer) 4

上面就是演示了，2018-10-04這天，約4個ip登陸了系統！網上有一張和傳統集合結構的佔用空間對比圖，貼出來，給大家看看

注意了，再強調一次，使用此結構是存在誤差的！比如你pfadd了一百萬條數據進去，結果pfcount的結果可能就999756條！

Geo

定義

Geo可以用於存儲經緯度、計算兩地之間的距離、範圍計算等。其底層實現是zset。

用途

主要有以下六組命令

geoadd：增加某個地理位置的坐標。
geopos：獲取某個地理位置的坐標。
geodist：獲取兩個地理位置的距離。
georadius：根據給定地理位置坐標獲取指定範圍內的地理位置集合。
georadiusbymember：根據給定地理位置獲取指定範圍內的地理位置集合
geohash：獲取某個地理位置的geohash值。

我這裡直接貼官網文檔的例子，大家有興趣可以自行查詢. 首先，先給key增加兩個坐標

redis> GEOADD Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catania"  (integer) 2

其次，計算兩個坐標之間的舉例

redis> GEODIST Sicily Palermo Catania  "166274.15156960039"

最後，計算距離經緯度(15,37)距離100km和200km範圍內的坐標有哪些

redis> GEORADIUS Sicily 15 37 100 km  1) "Catania"    redis> GEORADIUS Sicily 15 37 200 km  1) "Palermo"  2) "Catania"