歡迎光臨
每天分享高質量文章

Redis 的 3 個高級資料結構

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

技術文章第一時間送達!

原始碼精品專欄

 

來源: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:6380setbit dupcheck 10 1
(integer) 0
127.0.0.1:6380getbit dupcheck 10 
(integer) 1

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

img

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:6380PFADD hll a b c d d c
(integer) 1
127.0.0.1:6380PFCOUNT hll
(integer) 4
127.0.0.1:6380PFADD hll e
(integer) 1
127.0.0.1:6380PFCOUNT 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:6380PFADD hll1 1 2 3
(integer) 1
127.0.0.1:6380PFADD hll2 3 4 5
(integer) 1
127.0.0.1:6380PFMERGE hlls hll1 hll2
OK
127.0.0.1:6380PFCOUNT 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 篇++

赞(0)

分享創造快樂