1 業(yè)務(wù)背景

2 技術(shù)選型

• 2.1 MySQL
• 2.2 Redis
• 2.3 ElasticSearch

3 Coding

3.1 GEOADD

3.2 GEOPOS

3.3 GEODIST

3.4 GEORADIUS

4 原理解析

4.1 存儲(chǔ)結(jié)構(gòu)

4.2 GeoHash編碼

4.3 編碼原理

4.4 總結(jié)

5 參考資料

1.業(yè)務(wù)背景

某天在工位上的我，正在敲著代碼，聽著歌，突然就被打斷了：

小G：快來看看！我們的訂單都被詐騙了?。。?/p>

我：What？什么情況？

小G：有些黑中介引導(dǎo)我們用戶下單租賃，把訂單機(jī)器寄到他們那里，拿到機(jī)器后再補(bǔ)貼給用戶一筆錢，然后這批機(jī)器我們就拿不回來啦！

我：emmmm...那這些訂單有沒有什么特征呢？

小G：噢也有，他們的下單的地址都是黑中介那邊指定的某地址，我們也是通過這部分集中下單的地址數(shù)據(jù)進(jìn)行分析得知的。

我：噢那我有個(gè)想法，如果用戶的下單地址與黑中介指定下單地址相同，或者在其附近，是否就可以認(rèn)為這個(gè)訂單有詐騙風(fēng)險(xiǎn)？

小G：可以！

于是，新的需求又開始了。

2.技術(shù)選型

要判斷用戶地址與中介地址是否相同，或者相近。那落到實(shí)際功能開發(fā)，其實(shí)就是計(jì)算兩個(gè)地址之間的距離，由距離長(zhǎng)短決定是否相同，或相近。

那地址之間距離計(jì)算又如何實(shí)現(xiàn)呢？那當(dāng)然是站在巨人的肩膀上開發(fā)啦，下面就來介紹下開發(fā)中常用的GEO（Geolocation）工具，以及他們之間的區(qū)別。

2.1 MySQL

2.1.1 優(yōu)

• 兼容性：最常用的關(guān)系型數(shù)據(jù)之一。其與項(xiàng)目兼容度高，與其他業(yè)務(wù)數(shù)據(jù)（如用戶表、訂單表）天然集成，無需跨數(shù)據(jù)源查詢，通用性強(qiáng)。
• 持久性：數(shù)據(jù)持久化存儲(chǔ)，適合長(zhǎng)期保存地址數(shù)據(jù)。

2.1.2 劣

• 性能：大數(shù)據(jù)量下（如百萬級(jí)以上的地址經(jīng)緯度）的復(fù)雜查詢（地址空間計(jì)算）性能較低。

2.2 Redis

2.2.1 優(yōu)

性能：基于內(nèi)存存儲(chǔ)，查詢/數(shù)據(jù)操作延時(shí)極低，適合實(shí)時(shí)查詢/計(jì)算操作。GEO內(nèi)部數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)為Sorted Set，支持高效的范圍查詢和排序。

擴(kuò)展性：支持集群模式，適合分布式場(chǎng)景。

2.2.2 劣

• 存儲(chǔ)：內(nèi)存容量有限，不適合長(zhǎng)期存儲(chǔ)海量數(shù)據(jù)。
• 功能：不支持高級(jí)地理計(jì)算（如面積計(jì)算、地理圍欄計(jì)算）。

2.3 ElasticSearch

2.3.1 優(yōu)

• 性能：分布式架構(gòu)，適合海量數(shù)據(jù)和高并發(fā)場(chǎng)景。內(nèi)部倒排索引和分片機(jī)制，優(yōu)化查詢性能和保證容錯(cuò)。
• 內(nèi)置地址空間數(shù)據(jù)類型，支持復(fù)雜地址查詢（地理圍欄、距離排序、多邊形查詢等）

2.3.2 劣

• 復(fù)雜度：需要維護(hù)ES集群，開發(fā)學(xué)習(xí)成本較高
• 存儲(chǔ)：內(nèi)存和磁盤占用較高，不適合小規(guī)模場(chǎng)景

3.Coding

經(jīng)過上面的分析，結(jié)合需求的場(chǎng)景，首先保證性能，次要無須重量級(jí)的框架，開發(fā)成本低，同時(shí)還要能夠滿足地理計(jì)算的基本要求。于是，果斷選擇 Redis！

3.1 GEOADD

用于添加一個(gè)或多個(gè)地理位置信息（經(jīng)緯度）

例子：添加一個(gè)key為gk，包含 天安門，故宮 的經(jīng)緯度

圖片

3.2 GEOPOS

用于查詢某一個(gè)key中的指定地址經(jīng)緯度

例子：查詢gk中 天安門 和 故宮 的經(jīng)緯度

圖片

3.3 GEODIST

用于查詢同一個(gè)key兩個(gè)地址之間的距離

例子：查看gk中 天安門 和 故宮的距離（m)

圖片

3.4 GEORADIUS

用于查詢同一個(gè)key中指定地址范圍半徑內(nèi)的地址

例子：查詢gk中以 天安門 為中心，半徑1000km的地址

圖片

Java代碼如下

@Resource
    private Jodis jodis;

    @Test
    public void testGeo() {
        String key = "gk";
        String member1 = "TianAnMen";
        String member2 = "GuGong";
        
        // GEOADD
        jodis.geoadd(key, 116.3974723219871521, 39.90882345602657466, member1);
        jodis.geoadd(key, 116.39738649129867554, 39.91357605820034138, member2);
        
        // GEOPOS
        List<GeoCoordinate> geopos = jodis.geopos(key, member1, member2);
        for (GeoCoordinate geopo : geopos) {
            System.out.println(JSONUtil.toJsonStr(geopo));
        }
        
        // GEODIST
        Double geodist = jodis.geodist(key, member1, member2);
        System.out.println(geodist);
        
        // GEORADIUS
        List<GeoRadiusResponse> georadius = jodis.georadius(key, 116.39738649129867554, 39.91357605820034138, 1000, GeoUnit.KM);
        for (GeoRadiusResponse georadiu : georadius) {
            System.out.println(JSONUtil.toJsonStr(georadiu));
        }
    }

4.原理解析

從上面的示例來看，在使用的角度來說還是簡(jiǎn)潔易懂的。所謂知其然，知其所以然，所以接下來我們?cè)偕罹肯拢琑edis的GEO是如何實(shí)現(xiàn)兩個(gè)地址的經(jīng)緯度之間的距離計(jì)算的呢？

4.1 存儲(chǔ)結(jié)構(gòu)

Redis的GEO底層實(shí)現(xiàn)采用的是Sorted Set有序集合結(jié)構(gòu)，其中key存儲(chǔ)元素信息，value存儲(chǔ)經(jīng)緯度（即權(quán)重）。而經(jīng)緯度包含經(jīng)度和緯度兩個(gè)信息，因此需要使用GeoHash編碼的方式將經(jīng)緯度轉(zhuǎn)化成float類型進(jìn)行存儲(chǔ)。

4.2 GeoHash編碼

上面提到了GeoHash編碼，其實(shí)是分別對(duì)經(jīng)度和緯度進(jìn)行編碼，然后再組合成一個(gè)新的編碼。這個(gè)方法叫：二分區(qū)間編碼

4.3 編碼原理

對(duì)于一個(gè)經(jīng)緯度來說，經(jīng)度的范圍是[-180, 180]，緯度的的范圍是[-90, 90]。而GeoHash編碼針對(duì)兩個(gè)范圍進(jìn)行N次（N可自定義）的二分區(qū)編碼，將其轉(zhuǎn)化成一個(gè)N位的二進(jìn)制值。

以經(jīng)度為例，在進(jìn)行第一次二分區(qū)時(shí)，將經(jīng)度范圍[-180, 180]進(jìn)行二分，得到兩個(gè)區(qū)間 [-180, 0) 和 [0, 180]。然后判斷當(dāng)前經(jīng)度落在哪個(gè)區(qū)間，若落在左區(qū)間，則記錄為0；若落在右區(qū)間，則記錄為1。如此反復(fù)，每次都會(huì)得到一個(gè)二進(jìn)制值。

例子：將經(jīng)度（116.37）進(jìn)行5次二分區(qū)后得到編碼值：11010（如圖下）

圖片

再將緯度（39.86）進(jìn)行5次二分區(qū)后得到編碼值：10111（如圖下）

圖片

現(xiàn)在得到經(jīng)緯度編碼之后的值，需要再將其組合成一個(gè)編碼。同時(shí)遵循組合規(guī)則（如圖下）

1. 從左到右按順序，將經(jīng)度編碼值逐個(gè)放入偶數(shù)位
2. 從左到右按順序，將緯度編碼值逐個(gè)放入奇數(shù)位

圖片

最終兩個(gè)編碼值，轉(zhuǎn)化成了一個(gè)編碼值（1110011101），同時(shí)保存到Sorted Set的value中。至此，編碼完成。

4.4 總結(jié)

了解了GeoHash的編碼原理，那這樣編碼有什么用呢？下面來解答這個(gè)問題。

例子：我們把 經(jīng)度區(qū)間[-180, 180]，緯度區(qū)間[-90, 90] 都做一次二分區(qū)編碼，那么就會(huì)得到4個(gè)分區(qū)（如下圖）

經(jīng)過一次二分區(qū)編碼后，本來是二維信息的經(jīng)緯度，就簡(jiǎn)化成了一維信息的編碼。換句話說，對(duì)于整個(gè)地理空間來說，所有的位置都能經(jīng)過編碼變成平面上的一個(gè)點(diǎn)，多個(gè)點(diǎn)便能組成一條線，由此計(jì)算距離便有跡可循了。

而一次二分區(qū)的結(jié)果，便是圖中的4個(gè)方格，同時(shí)也對(duì)應(yīng)了4個(gè)分區(qū)，每個(gè)分區(qū)都包含指定范圍的經(jīng)緯度。那對(duì)于N次二分區(qū)來說，N越大，分區(qū)也越多，每個(gè)分區(qū)所包含的經(jīng)緯度范圍就越?。ㄋ芨采w的地理空間越小），對(duì)應(yīng)映射在一維空間上的點(diǎn)越小，點(diǎn)越小則越精準(zhǔn)。

需要注意的是，雖然分區(qū)越多，經(jīng)緯度在地理空間上代表的位置則越精準(zhǔn)，但對(duì)于距離統(tǒng)計(jì)來說，并不是分區(qū)越多越好。

例子：還是延續(xù)上面一次二分區(qū)的例子進(jìn)行舉例。這次我們把N+1，做二次二分區(qū)（如下圖）

圖片

上圖可以看到，經(jīng)過二次二分區(qū)后，分區(qū)變成了16個(gè)。理論上對(duì)應(yīng)地理空間上的位置更加精確了，那么將對(duì)應(yīng)的編碼轉(zhuǎn)化為一維空間上的點(diǎn)后，連接成線。發(fā)現(xiàn)對(duì)于大部分的編碼值來說，在線上相鄰的編碼在空間上也是相鄰（如：0001,0010），但是對(duì)于某些編碼來說（如：0111,1000）在線上相鄰，但是在空間上卻相差較遠(yuǎn)。因此，對(duì)于這兩個(gè)分區(qū)來說，如果只單純考慮計(jì)算一維空間上的距離，將會(huì)造成較大誤差。

所以基于以上情況，一般不會(huì)只計(jì)算編碼值的距離，還需要結(jié)合分區(qū)作為輔助計(jì)算。通常在計(jì)算過程中，會(huì)在經(jīng)緯度指定的分區(qū)周圍同時(shí)再查詢附近的幾個(gè)分區(qū)，作為距離遠(yuǎn)近的參考，提高距離計(jì)算的精度。

5.參考資料

[1]  https://cloud.tencent.com/developer/article/1949540

關(guān)于作者

馮超，一名轉(zhuǎn)轉(zhuǎn)金融技術(shù)部后端開發(fā)程序猿