背景

之前，我們學(xué)習(xí)了 Redis 的 5 大基本數(shù)據(jù)類型：String、List、Hash、Set 和 Sorted Set，它們可以滿足大多數(shù)的數(shù)據(jù)存儲(chǔ)需求，但是在面對(duì)海量數(shù)據(jù)統(tǒng)計(jì)時(shí)，它們的內(nèi)存開銷很大，而且對(duì)于一些特殊的場(chǎng)景，它們是無(wú)法支持的。所以，Redis 還提供了 3 種擴(kuò)展數(shù)據(jù)類型，分別是 Bitmap、HyperLogLog 和 GEO。前兩種我們已經(jīng)重點(diǎn)介紹過(guò)了，今天，再具體講一講 GEO。

面向 LBS 應(yīng)用的 GEO 數(shù)據(jù)類型

在日常生活中，我們?cè)絹?lái)越依賴搜索“附近的餐館”、在打車軟件上叫車，這些都離不開基于位置信息服務(wù)（Location-Based Service，LBS）的應(yīng)用。LBS 應(yīng)用訪問(wèn)的數(shù)據(jù)是和人或物關(guān)聯(lián)的一組經(jīng)緯度信息，而且要能查詢相鄰的經(jīng)緯度范圍，GEO 就非常適合應(yīng)用在 LBS 服務(wù)的場(chǎng)景中，我們來(lái)看一下它的底層結(jié)構(gòu)。

GEO 的底層結(jié)構(gòu)

**一般來(lái)說(shuō)，在設(shè)計(jì)一個(gè)數(shù)據(jù)類型的底層結(jié)構(gòu)時(shí)，我們首先需要知道，要處理的數(shù)據(jù)有什么訪問(wèn)特點(diǎn)。**所以，我們需要先搞清楚位置信息到底是怎么被存取的。

以叫車服務(wù)為例，來(lái)分析下 LBS 應(yīng)用中經(jīng)緯度的存取特點(diǎn)：

1. 每一輛網(wǎng)約車都有一個(gè)編號(hào)（例如 33），網(wǎng)約車需要將自己的經(jīng)度信息（例如 116.034579）和緯度信息（例如 39.000452 ）發(fā)給叫車應(yīng)用。
2. 用戶在叫車的時(shí)候，叫車應(yīng)用會(huì)根據(jù)用戶的經(jīng)緯度位置（例如經(jīng)度 116.054579，緯度 39.030452），查找用戶的附近車輛，并進(jìn)行匹配。
3. 等把位置相近的用戶和車輛匹配上以后，叫車應(yīng)用就會(huì)根據(jù)車輛的編號(hào)，獲取車輛的信息，并返回給用戶。

可以看到，一輛車（或一個(gè)用戶）對(duì)應(yīng)一組經(jīng)緯度，并且隨著車（或用戶）的位置移動(dòng)，相應(yīng)的經(jīng)緯度也會(huì)變化。

Hash

這種數(shù)據(jù)記錄模式屬于一個(gè) key（例如車 ID）對(duì)應(yīng)一個(gè) value（一組經(jīng)緯度）。當(dāng)有很多車輛信息要保存時(shí)，就需要有一個(gè)集合來(lái)保存一系列的 key 和 value。Hash 集合類型可以快速存取一系列的 key 和 value，正好可以用來(lái)記錄一系列車輛 ID 和經(jīng)緯度的對(duì)應(yīng)關(guān)系，所以，我們可以把不同車輛的 ID 和它們對(duì)應(yīng)的經(jīng)緯度信息存在 Hash 集合中，如下圖所示：

同時(shí)，Hash 類型的 HSET 操作命令，會(huì)根據(jù) key 來(lái)設(shè)置相應(yīng)的 value 值，所以，我們可以用它來(lái)快速地更新車輛變化的經(jīng)緯度信息。

到這里，Hash 類型看起來(lái)是一個(gè)不錯(cuò)的選擇。但問(wèn)題是，對(duì)于一個(gè) LBS 應(yīng)用來(lái)說(shuō)，除了記錄經(jīng)緯度信息，還需要根據(jù)用戶的經(jīng)緯度信息在車輛的 Hash 集合中進(jìn)行范圍查詢。一旦涉及到范圍查詢，就意味著集合中的元素需要有序，但 Hash 類型的元素是無(wú)序的，顯然不能滿足我們的要求。

Sortted Set

Sorted Set 類型也支持一個(gè) key 對(duì)應(yīng)一個(gè) value 的記錄模式，其中，key 就是 Sorted Set 中的元素，而 value 則是元素的權(quán)重分?jǐn)?shù)。更重要的是，Sorted Set 可以根據(jù)元素的權(quán)重分?jǐn)?shù)排序，支持范圍查詢。這就能滿足 LBS 服務(wù)中查找相鄰位置的需求了。

實(shí)際上，GEO 類型的底層數(shù)據(jù)結(jié)構(gòu)就是用 Sorted Set 來(lái)實(shí)現(xiàn)的。咱們還是借著叫車應(yīng)用的例子來(lái)加深下理解。

用 Sorted Set 來(lái)保存車輛的經(jīng)緯度信息時(shí)，Sorted Set 的元素是車輛 ID，元素的權(quán)重分?jǐn)?shù)是經(jīng)緯度信息，如下圖所示：
這時(shí)問(wèn)題來(lái)了，Sorted Set 元素的權(quán)重分?jǐn)?shù)是一個(gè)浮點(diǎn)數(shù)（float 類型），而一組經(jīng)緯度包含的是經(jīng)度和緯度兩個(gè)值，是沒法直接保存為一個(gè)浮點(diǎn)數(shù)的，那具體該怎么進(jìn)行保存呢？

這就要用到 GEO 類型中的 GeoHash 編碼了。

GeoHash 的編碼方法

為了能高效地對(duì)經(jīng)緯度進(jìn)行比較，Redis 采用了業(yè)界廣泛使用的 GeoHash 編碼方法，這個(gè)方法的基本原理就是“二分區(qū)間，區(qū)間編碼”。

當(dāng)我們要對(duì)一組經(jīng)緯度進(jìn)行 GeoHash 編碼時(shí)，我們要先對(duì)經(jīng)度和緯度分別編碼，然后再把經(jīng)緯度各自的編碼組合成一個(gè)最終編碼。

對(duì)于一個(gè)地理位置信息來(lái)說(shuō)，它的經(jīng)度范圍是[-180,180]。GeoHash 編碼會(huì)把一個(gè)經(jīng)度值編碼成一個(gè) N 位的二進(jìn)制值，我們來(lái)對(duì)經(jīng)度范圍[-180,180]做 N 次的二分區(qū)操作，其中 N 可以自定義。

在進(jìn)行第一次二分區(qū)時(shí)，經(jīng)度范圍[-180,180]會(huì)被分成兩個(gè)子區(qū)間：[-180,0) 和[0,180]（我稱之為左、右分區(qū)）。此時(shí)，我們可以查看一下要編碼的經(jīng)度值落在了左分區(qū)還是右分區(qū)。如果是落在左分區(qū)，我們就用 0 表示；如果落在右分區(qū)，就用 1 表示。這樣一來(lái)，每做完一次二分區(qū)，我們就可以得到 1 位編碼值。

然后，我們?cè)賹?duì)經(jīng)度值所屬的分區(qū)再做一次二分區(qū)，同時(shí)再次查看經(jīng)度值落在了二分區(qū)后的左分區(qū)還是右分區(qū)，按照剛才的規(guī)則再做 1 位編碼。當(dāng)做完 N 次的二分區(qū)后，經(jīng)度值就可以用一個(gè) N bit 的數(shù)來(lái)表示了。


當(dāng)一組經(jīng)緯度值都編完碼后，我們?cè)侔阉鼈兊母髯跃幋a值組合在一起，組合的規(guī)則是：最終編碼值的偶數(shù)位上依次是經(jīng)度的編碼值，奇數(shù)位上依次是緯度的編碼值，其中，偶數(shù)位從 0 開始，奇數(shù)位從 1 開始。

我們剛剛計(jì)算的經(jīng)緯度（116.37，39.86）的各自編碼值是 11010 和 10111，組合之后，第 0 位是經(jīng)度的第 0 位 1，第 1 位是緯度的第 0 位 1，第 2 位是經(jīng)度的第 1 位 1，第 3 位是緯度的第 1 位 0，以此類推，就能得到最終編碼值 1110011101，如下圖所示：

用了 GeoHash 編碼后，原來(lái)無(wú)法用一個(gè)權(quán)重分?jǐn)?shù)表示的一組經(jīng)緯度（116.37，39.86）就可以用 1110011101 這一個(gè)值來(lái)表示，就可以保存為 Sorted Set 的權(quán)重分?jǐn)?shù)了。

當(dāng)然，使用 GeoHash 編碼后，我們相當(dāng)于把整個(gè)地理空間劃分成了一個(gè)個(gè)方格，每個(gè)方格對(duì)應(yīng)了 GeoHash 中的一個(gè)分區(qū)。

舉個(gè)例子。我們把經(jīng)度區(qū)間[-180,180]做一次二分區(qū)，把緯度區(qū)間[-90,90]做一次二分區(qū)，就會(huì)得到 4 個(gè)分區(qū)。我們來(lái)看下它們的經(jīng)度和緯度范圍以及對(duì)應(yīng)的 GeoHash 組合編碼。

• 分區(qū)一：[-180,0) 和[-90,0)，編碼 00；
• 分區(qū)二：[-180,0) 和[0,90]，編碼 01；
• 分區(qū)三：[0,180]和[-90,0)，編碼 10；
• 分區(qū)四：[0,180]和[0,90]，編碼 11。

這 4 個(gè)分區(qū)對(duì)應(yīng)了 4 個(gè)方格，每個(gè)方格覆蓋了一定范圍內(nèi)的經(jīng)緯度值，分區(qū)越多，每個(gè)方格能覆蓋到的地理空間就越小，也就越精準(zhǔn)。我們把所有方格的編碼值映射到一維空間時(shí)，相鄰方格的 GeoHash 編碼值基本也是接近的，如下圖所示：

所以，我們使用 Sorted Set 范圍查詢得到的相近編碼值，在實(shí)際的地理空間上，也是相鄰的方格，這就可以實(shí)現(xiàn) LBS 應(yīng)用“搜索附近的人或物”的功能了。

不過(guò)，我要提醒你一句，有的編碼值雖然在大小上接近，但實(shí)際對(duì)應(yīng)的方格卻距離比較遠(yuǎn)。例如，我們用 4 位來(lái)做 GeoHash 編碼，把經(jīng)度區(qū)間[-180,180]和緯度區(qū)間[-90,90]各分成了 4 個(gè)分區(qū)，一共 16 個(gè)分區(qū)，對(duì)應(yīng)了 16 個(gè)方格。編碼值為 0111 和 1000 的兩個(gè)方格就離得比較遠(yuǎn)，如下圖所示：

所以，為了避免查詢不準(zhǔn)確問(wèn)題，我們可以同時(shí)查詢給定經(jīng)緯度所在的方格周圍的 4 個(gè)或 8 個(gè)方格。

好了，到這里，我們就知道了，GEO 類型是把經(jīng)緯度所在的區(qū)間編碼作為 Sorted Set 中元素的權(quán)重分?jǐn)?shù)，把和經(jīng)緯度相關(guān)的車輛 ID 作為 Sorted Set 中元素本身的值保存下來(lái)，這樣相鄰經(jīng)緯度的查詢就可以通過(guò)編碼值的大小范圍查詢來(lái)實(shí)現(xiàn)了。接下來(lái)，我們?cè)賮?lái)聊聊具體如何操作 GEO 類型。

如何操作 GEO 類型？

在使用 GEO 類型時(shí)，我們經(jīng)常會(huì)用到兩個(gè)命令，分別是 GEOADD 和 GEORADIUS。

• GEOADD 命令：用于把一組經(jīng)緯度信息和相對(duì)應(yīng)的一個(gè) ID 記錄到 GEO 類型集合中；
• GEORADIUS 命令：會(huì)根據(jù)輸入的經(jīng)緯度位置，查找以這個(gè)經(jīng)緯度為中心的一定范圍內(nèi)的其他元素。當(dāng)然，我們可以自己定義這個(gè)范圍。

假設(shè)車輛 ID 是 33，經(jīng)緯度位置是（116.034579，39.030452），我們可以用一個(gè) GEO 集合保存所有車輛的經(jīng)緯度，集合 key 是 cars:locations。執(zhí)行下面的這個(gè)命令，就可以把 ID 號(hào)為 33 的車輛的當(dāng)前經(jīng)緯度位置存入 GEO 集合中：

GEOADD cars:locations 116.034579 39.030452 33

當(dāng)用戶想要尋找自己附近的網(wǎng)約車時(shí)，LBS 應(yīng)用就可以使用 GEORADIUS 命令。例如，LBS 應(yīng)用執(zhí)行下面的命令時(shí)，Redis 會(huì)根據(jù)輸入的用戶的經(jīng)緯度信息（116.054579，39.030452 ），查找以這個(gè)經(jīng)緯度為中心的 5 公里內(nèi)的車輛信息，并返回給 LBS 應(yīng)用。當(dāng)然， 你可以修改“5”這個(gè)參數(shù)，來(lái)返回更大或更小范圍內(nèi)的車輛信息。

GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

另外，我們還可以進(jìn)一步限定返回的車輛信息。

比如，我們可以使用 ASC 選項(xiàng)，讓返回的車輛信息按照距離這個(gè)中心位置從近到遠(yuǎn)的方式來(lái)排序，以方便選擇最近的車輛；還可以使用 COUNT 選項(xiàng)，指定返回的車輛信息的數(shù)量。畢竟，5 公里范圍內(nèi)的車輛可能有很多，如果返回全部信息，會(huì)占用比較多的數(shù)據(jù)帶寬，這個(gè)選項(xiàng)可以幫助控制返回的數(shù)據(jù)量，節(jié)省帶寬。

如何自定義數(shù)據(jù)類型？

為了實(shí)現(xiàn)自定義數(shù)據(jù)類型，首先，我們需要了解 Redis 的基本對(duì)象結(jié)構(gòu) RedisObject，因?yàn)?Redis 鍵值對(duì)中的每一個(gè)值都是用 RedisObject 保存的。

RedisObject 包括元數(shù)據(jù)和指針。其中，元數(shù)據(jù)的一個(gè)功能就是用來(lái)區(qū)分不同的數(shù)據(jù)類型，指針用來(lái)指向具體的數(shù)據(jù)類型的值。所以，要想開發(fā)新數(shù)據(jù)類型，我們就先來(lái)了解下 RedisObject 的元數(shù)據(jù)和指針。

Redis 的基本對(duì)象結(jié)構(gòu)

RedisObject 的內(nèi)部組成包括了 type、encoding、lru 和 refcount 4 個(gè)元數(shù)據(jù)，以及 1 個(gè)*ptr指針。

• type：表示值的類型，涵蓋了我們前面學(xué)習(xí)的五大基本類型；
• encoding：是值的編碼方式，用來(lái)表示 Redis 中實(shí)現(xiàn)各個(gè)基本類型的底層數(shù)據(jù)結(jié)構(gòu)，例如 SDS、壓縮列表、哈希表、跳表等；
• lru：記錄了這個(gè)對(duì)象最后一次被訪問(wèn)的時(shí)間，用于淘汰過(guò)期的鍵值對(duì)；
• refcount：記錄了對(duì)象的引用計(jì)數(shù)；
• ptr：是指向數(shù)據(jù)的指針。
  
  RedisObject 結(jié)構(gòu)借助ptr指針，就可以指向不同的數(shù)據(jù)類型，例如，ptr指向一個(gè) SDS 或一個(gè)跳表，就表示鍵值對(duì)中的值是 String 類型或 Sorted Set 類型。所以，我們?cè)诙x了新的數(shù)據(jù)類型后，也只要在 RedisObject 中設(shè)置好新類型的 type 和 encoding，再用ptr指向新類型的實(shí)現(xiàn)，就行了。

開發(fā)一個(gè)新的數(shù)據(jù)類型

了解了 RedisObject 結(jié)構(gòu)后，定義一個(gè)新的數(shù)據(jù)類型也就不難了。首先，我們需要為新數(shù)據(jù)類型定義好它的底層結(jié)構(gòu)、type 和 encoding 屬性值，然后再實(shí)現(xiàn)新數(shù)據(jù)類型的創(chuàng)建、釋放函數(shù)和基本命令。

這里不再綴訴，有興趣的可以自己去研究一下。

小結(jié)

這篇文章，我們學(xué)習(xí)了 Redis 的擴(kuò)展數(shù)據(jù)類型 GEO。GEO 可以記錄經(jīng)緯度形式的地理位置信息，被廣泛地應(yīng)用在 LBS 服務(wù)中。GEO 本身并沒有設(shè)計(jì)新的底層數(shù)據(jù)結(jié)構(gòu)，而是直接使用了 Sorted Set 集合類型。

GEO 類型使用 GeoHash 編碼方法實(shí)現(xiàn)了經(jīng)緯度到 Sorted Set 中元素權(quán)重分?jǐn)?shù)的轉(zhuǎn)換，這其中的兩個(gè)關(guān)鍵機(jī)制就是對(duì)二維地圖做區(qū)間劃分，以及對(duì)區(qū)間進(jìn)行編碼。一組經(jīng)緯度落在某個(gè)區(qū)間后，就用區(qū)間的編碼值來(lái)表示，并把編碼值作為 Sorted Set 元素的權(quán)重分?jǐn)?shù)。這樣一來(lái)，我們就可以把經(jīng)緯度保存到 Sorted Set 中，利用 Sorted Set 提供的“按權(quán)重進(jìn)行有序范圍查找”的特性，實(shí)現(xiàn) LBS 服務(wù)中頻繁使用的“搜索附近”的需求。

GEO 屬于 Redis 提供的擴(kuò)展數(shù)據(jù)類型。擴(kuò)展數(shù)據(jù)類型有兩種實(shí)現(xiàn)途徑：一種是基于現(xiàn)有的數(shù)據(jù)類型，通過(guò)數(shù)據(jù)編碼或是實(shí)現(xiàn)新的操作的方式，來(lái)實(shí)現(xiàn)擴(kuò)展數(shù)據(jù)類型，例如基于 Sorted Set 和 GeoHash 編碼實(shí)現(xiàn) GEO，以及基于 String 和位操作實(shí)現(xiàn) Bitmap；另一種就是開發(fā)自定義的數(shù)據(jù)類型，具體的操作是增加新數(shù)據(jù)類型的定義，實(shí)現(xiàn)創(chuàng)建和釋放函數(shù)，實(shí)現(xiàn)新數(shù)據(jù)類型支持的命令操作。