點選上方“芋道原始碼”，選擇“置頂公眾號”

技術文章第一時間送達！

原始碼精品專欄

 

• 精盡 Dubbo 原理與原始碼專欄( 已經完成 69+ 篇，預計總共 75+ 篇 )

• 中文詳細註釋的開源專案

• Java 併發原始碼合集

• RocketMQ 原始碼合集

• Sharding-JDBC 原始碼解析合集

• Spring MVC 和 Security 原始碼合集

• MyCAT 原始碼解析合集

來源：https://www.jianshu.com/p/87a576d29d4b

平常我們我接觸最多的是5個入門級資料結構：String，Hash，List，Set，Sorted Set。本文介紹3個高階資料結構：Bitmaps，Hyperloglogs，GEO。

Bitmaps

bitmaps不是一個真實的資料結構。而是String型別上的一組面向bit操作的集合。由於strings是二進位制安全的blob，並且它們的最大長度是512m，所以bitmaps能最大設定2^32個不同的bit。

bit操作被分為兩組：

• 恆定時間的單個bit操作，例如把某個bit設定為0或者1。或者獲取某bit的值。

• 對一組bit的操作。例如給定範圍內bit統計（例如人口統計）。

Bitmaps的最大優點就是儲存資訊時可以節省大量的空間。例如在一個系統中，不同的使用者被一個增長的使用者ID表示。40億（2^32=4*1024*1024*1024≈40億）使用者只需要512M記憶體就能記住某種資訊，例如使用者是否登入過。

Bits設定和獲取透過SETBIT 和GETBIT 命令，用法如下：

SETBIT key offset value
GETBIT key offset

使用實體：

127.0.0.1:6380> setbit dupcheck 10 1
(integer) 0
127.0.0.1:6380> getbit dupcheck 10 
(integer) 1

SETBIT命令第一個引數是位編號，第二個引數是這個位的值，只能是0或者1。如果bit地址超過當前string長度，會自動增大string。

Bitmaps示意圖

GETBIT命令指示傳回指定位置bit的值。超過範圍（定址地址在標的key的string長度以外的位）的GETBIT總是傳回0。三個操作bits組的命令如下：

• BITOP 執行兩個不同string的位操作.，包括AND，OR，XOR和NOT.

• BITCOUNT 統計位的值為1的數量。

• BITPOS 定址第一個為0或者1的bit的位置（定址第一個為1的bit的位置：bitpos dupcheck 1； 定址第一個為0的bit的位置：bitpos dupcheck 0）.

bitmaps一般的使用場景：

• 各種實時分析.

• 儲存與物件ID關聯的節省空間並且高效能的布林資訊.

例如，想象一下你想知道訪問你的網站的使用者的最長連續時間。你開始計算從0開始的天數，就是你的網站公開的那天，每次使用者訪問網站時透過SETBIT命令設定bit為1，可以簡單的用當前時間減去初始時間並除以3600*24（結果就是你的網站公開的第幾天）當做這個bit的位置。

這種方法對於每個使用者，都有儲存每天的訪問資訊的一個很小的string字串。透過BITCOUN就能輕易統計某個使用者歷史訪問網站的天數。另外透過呼叫BITPOS命令，或者客戶端獲取並分析這個bitmap，就能計算出最長停留時間。

HyperLogLogs

HyperLogLog是用於計算唯一事物的機率資料結構（從技術上講，這被稱為估計集合的基數）。如果統計唯一項，專案越多，需要的記憶體就越多。因為需要記住過去已經看過的項，從而避免多次統計這些項。

然而，有一組演演算法可以交換記憶體以獲得精確度：在redis的實現中，您使用標準錯誤小於1％的估計度量結束。這個演演算法的神奇在於不再需要與需要統計的項相對應的記憶體，取而代之，使用的記憶體一直恆定不變。最壞的情況下只需要12k，就可以計算接近2^64個不同元素的基數。或者如果您的HyperLogLog（我們從現在開始簡稱它為HLL）已經看到的元素非常少，則需要的記憶體要要少得多。

在redis中HLL是一個不同的資料結構，它被編碼成Redis字串。因此可以透過呼叫GET命令序列化一個HLL，也可以透過呼叫SET命令將其反序列化到redis伺服器。

HLL的API類似使用SETS資料結構做相同的任務，SETS結構中，透過SADD命令把每一個觀察的元素新增到一個SET集合，用SCARD命令檢查SET集合中元素的數量，集合裡的元素都是唯一的，已經存在的元素不會被重覆新增。

而使用HLL時並不是真正新增項到HLL中（這一點和SETS結構差異很大），因為HLL的資料結構只包含一個不包含實際元素的狀態，API是一樣的：

• PFADD命令用於新增一個新元素到統計中。

• PFCOUNT命令用於獲取到目前為止透過PFADD命令新增的唯一元素個數近似值。

• PFMERGE命令執行多個HLL之間的聯合操作。

127.0.0.1:6380> PFADD hll a b c d d c
(integer) 1
127.0.0.1:6380> PFCOUNT hll
(integer) 4
127.0.0.1:6380> PFADD hll e
(integer) 1
127.0.0.1:6380> PFCOUNT hll
(integer) 5

PFMERGE命令說明：bashbash

PFMERGE destkey sourcekey [sourcekey ...]
Merge N different HyperLogLogs into a single one.

用法（把hll1和hll2合併到hlls中）：bashbash

127.0.0.1:6380> PFADD hll1 1 2 3
(integer) 1
127.0.0.1:6380> PFADD hll2 3 4 5
(integer) 1
127.0.0.1:6380> PFMERGE hlls hll1 hll2
OK
127.0.0.1:6380> PFCOUNT hlls

HLL資料結構的一個使用場景就是計算使用者每天在搜尋框中執行的唯一查詢，即搜尋頁面UV統計。而Bitmaps則用於判斷某個使用者是否訪問過搜尋頁面。這是它們用法的不同。

GEO

Redis的GEO特性在 Redis3.2版本中推出，這個功能可以將使用者給定的地理位置（經度和緯度）資訊儲存起來，並對這些資訊進行操作。GEO相關命令只有6個：

• GEOADD：GEOADD key longitude latitude member [longitude latitude member …]，將指定的地理空間位置（緯度、經度、名稱）新增到指定的key中。例如：GEOADD city 113.501389 22.405556 shenzhen；

經緯度具體的限制，由EPSG:900913/EPSG:3785/OSGEO:41001規定如下：
有效的經度從-180度到180度。
有效的緯度從-85.05112878度到85.05112878度。
當坐標位置超出上述指定範圍時，該命令將會傳回一個錯誤。

• GEOHASH：GEOHASH key member [member …]，傳回一個或多個位置元素的標準Geohash值，它可以在http://geohash.org/使用。查詢例子：http://geohash.org/sqdtr74hyu0.（可以透過谷歌瞭解Geohash原理，或者戳Geohash基本原理：https://www.cnblogs.com/tgzhu/p/6204173.html）。

• GEOPOS：GEOPOS key member [member …]，從key裡傳回所有給定位置元素的位置（經度和緯度）。

• GEODIST：GEODIST key member1 member2 [unit]，傳回兩個給定位置之間的距離。GEODIST命令在計算距離時會假設地球為完美的球形。在極限情況下，這一假設最大會造成0.5%的誤差。

指定單位的引數unit必須是以下單位的其中一個：
m 表示單位為米（預設）。
km 表示單位為千米。
mi 表示單位為英里。
ft 表示單位為英尺。

• GEORADIUS：GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD][WITHDIST] [WITHHASH][COUNT count]，以給定的經緯度為中心， 傳回鍵包含的位置元素當中， 與中心的距離不超過給定最大距離的所有位置元素。這個命令可以查詢某城市的周邊城市群。

• GEORADIUSBYMEMBER：GEORADIUSBYMEMBER key member radius m|km|ft|mi [WITHCOORD][WITHDIST] [WITHHASH][COUNT count]，這個命令和GEORADIUS命令一樣，都可以找出位於指定範圍內的元素，但是GEORADIUSBYMEMBER的中心點是由給定的位置元素決定的，而不是像 GEORADIUS那樣，使用輸入的經度和緯度來決定中心點。

指定成員的位置被用作查詢的中心。

GEO的6個命令用法示例如下：

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

redis> GEOHASH Sicily Palermo Catania
1) "sqc8b49rny0"
2) "sqdtr74hyu0"

redis> GEOPOS Sicily Palermo Catania NonExisting
1) 1) "13.361389338970184"
   2) "38.115556395496299"
2) 1) "15.087267458438873"
   2) "37.50266842333162"
3) (nil)

redis> GEODIST Sicily Palermo Catania
"166274.15156960039"

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

redis> GEORADIUSBYMEMBER Sicily Agrigento 100 km
1) "Agrigento"
2) "Palermo"

---

---

如果你對 Dubbo 感興趣，歡迎加入我的知識星球一起交流。

目前在知識星球（https://t.zsxq.com/2VbiaEu）更新瞭如下 Dubbo 原始碼解析如下：

01. 除錯環境搭建
02. 專案結構一覽
03. 配置 Configuration
04. 核心流程一覽

05. 拓展機制 SPI

06. 執行緒池

07. 服務暴露 Export

08. 服務取用 Refer

09. 註冊中心 Registry

10. 動態編譯 Compile

11. 動態代理 Proxy

12. 服務呼叫 Invoke

13. 呼叫特性 

14. 過濾器 Filter

15. NIO 伺服器

16. P2P 伺服器

17. HTTP 伺服器

18. 序列化 Serialization

19. 叢集容錯 Cluster

20. 優雅停機

21. 日誌適配

22. 狀態檢查

23. 監控中心 Monitor

24. 管理中心 Admin

25. 運維命令 QOS

26. 鏈路追蹤 Tracing

…
一共 60 篇++