一口氣說出4種「附近的人」實現方式,面試官笑了

引言

昨天一位公眾號粉絲和我討論了一道面試題，個人覺得比較有意義，這裡整理了一下分享給大家，願小夥伴們面試路上少踩坑。面試題目比較簡單：「讓你實現一個附近的人功能，你有什麼方案?」，這道題其實主要還是考察大家對於技術的廣度，本文介紹幾種方案，給大家一點思路，避免在面試過程中語塞而影響面試結果，如有不嚴謹之處，還望親人們溫柔指正!

「附近的人」 功能生活中是比較常用的，像外賣app附近的餐廳，共享單車app裡附近的車輛。既然常用面試被問的概率就很大，所以下邊依次來分析基於MySQL資料庫、Redis、 MongoDB實現的 「附近的人」 功能。

科普：世界上標識一個位置，通用的做法就使用經、緯度。經度的範圍在 (-180, 180]，緯度的範圍 在(-90, 90]，緯度正負以赤道為界，北正南負，經度正負以本初子午線 (英國格林尼治天文臺) 為界，東正西負。比如：望京摩託羅拉大廈的經、緯度(116.49141，40.01229)全是正數，就是因為我國位於東北半球。

一、「附近的人」原理

「附近的人」 也就是常說的 LBS (Location Based Services，基於位置服務)，它圍繞用戶當前地理位置數據而展開的服務，為用戶提供精準的增值服務。

「附近的人」 核心思想如下：

• 以 「我」 為中心，搜索附近的用戶
• 以 「我」 當前的地理位置為準，計算出別人和 「我」 之間的距離
• 按 「我」 與別人距離的遠近排序，篩選出離我最近的用戶或者商店等

二、什麼是GeoHash算法?

在說 「附近的人」 功能的具體實現之前，先來認識一下GeoHash 算法，因為後邊會一直和它打交道。定位一個位置最好的辦法就是用經、緯度標識，但經、緯度它是二維的，在進行位置計算的時候還是很麻煩，如果能通過某種方法將二維的經、緯度數據轉換成一維的數據，那麼比較起來就要容易的多，因此GeoHash算法應運而生。

GeoHash算法將二維的經、緯度轉換成一個字符串，例如：下圖中9個GeoHash字符串代表了9個區域，每一個字符串代表了一矩形區域。而這個矩形區域內其他的點(經、緯度)都用同一個GeoHash字符串表示。

比如：WX4ER區域內的用戶搜索附近的餐廳數據，由於這區域內用戶的GeoHash字符串都是WX4ER，故可以把WX4ER當作key，餐廳信息作為value進行緩存;而如果不使用GeoHash算法，區域內的用戶請求餐廳數據，用戶傳來的經、緯度都是不同的，這樣緩存不僅麻煩且數據量巨大。

GeoHash字符串越長，表示的位置越精確，字符串長度越長代表在距離上的誤差越小。下圖geohash碼精度表：

geohash碼長度	寬度	高度
1	5,009.4km	4,992.6km
2	1,252.3km	624.1km
3	156.5km	156km
4	39.1km	19.5km
5	4.9km	4.9km
6	1.2km	609.4m
7	152.9m	152.4m
8	38.2m	19m
9	4.8m	4.8m
10	1.2m	59.5cm
11	14.9cm	14.9cm
12	3.7cm	1.9cm

而且字符串越相似表示距離越相近，字符串前綴匹配越多的距離越近。比如：下邊的經、緯度就代表了三家距離相近的餐廳。

商戶	經緯度	Geohash字符串
串串香	116.402843,39.999375	wx4er9v
火鍋	116.3967,39.99932	wx4ertk
烤肉	116.40382,39.918118	wx4erfe

讓大家簡單了解什麼是GeoHash算法，方便後邊內容展開，GeoHash算法內容比較高深，感興趣的小夥伴自行深耕一下，這裡不佔用過多篇幅(其實是我懂得太膚淺，哭唧唧~)。

三、基於MySQL

此種方式是純基於mysql實現的，未使用GeoHash算法。

1、設計思路

以用戶為中心，假設給定一個500米的距離作為半徑畫一個圓，這個圓型區域內的所有用戶就是符合用戶要求的 「附近的人」。但有一個問題是圓形有弧度啊，直接搜索圓形區域難度太大，根本無法用經、緯度直接搜索。

但如果在圓形外套上一個正方形，通過獲取用戶經、緯度的最大最小值(經、緯度 + 距離)，再根據最大最小值作為篩選條件，就很容易將正方形內的用戶信息搜索出來。

那麼問題又來了，多出來一些面積腫麼辦?

我們來分析一下，多出來的這部分區域內的用戶，到圓點的距離一定比圓的半徑要大，那麼我們就計算用戶中心點與正方形內所有用戶的距離，篩選出所有距離小於等於半徑的用戶，圓形區域內的所用戶即符合要求的「附近的人」。

2、利弊分析

純基於 MySQL 實現 「附近的人」，優點顯而易見就是簡單，只要建一張表存下用戶的經、緯度信息即可。缺點也很明顯，需要大量的計算兩個點之間的距離，非常影響性能。

3、實現

創建一個簡單的表用來存放用戶的經、緯度屬性。

1. CREATE TABLE `nearby_user` ( 
2.   `id` int(11) NOT NULL AUTO_INCREMENT, 
3.   `name` varchar(255) DEFAULT NULL COMMENT '名稱', 
4.   `longitude` double DEFAULT NULL COMMENT '經度', 
5.   `latitude` double DEFAULT NULL COMMENT '緯度', 
6.   `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '創建時間', 
7.   PRIMARY KEY (`id`) 
8. ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; 

計算兩個點之間的距離，用了一個三方的類庫，畢竟自己造的輪子不是特別圓，還有可能是方的，啊哈哈哈~

1. <dependency> 
2.      <groupId>com.spatial4j</groupId> 
3.      <artifactId>spatial4j</artifactId> 
4.      <version>0.5</version> 
5. </dependency> 

獲取到外接正方形後，以正方形的最大最小經、緯度值搜索正方形區域內的用戶，再剔除超過指定距離的用戶，就是最終的附近的人。

1. private SpatialContext spatialContext = SpatialContext.GEO;     
2.  
3.     /** 
4.      * 獲取附近 x 米的人 
5.      * 
6.      * @param distance 搜索距離範圍 單位km 
7.      * @param userLng  當前用戶的經度 
8.      * @param userLat  當前用戶的緯度 
9.      */ 
10.     @GetMapping("/nearby") 
11.     public String nearBySearch(@RequestParam("distance") double distance, 
12.                                @RequestParam("userLng") double userLng, 
13.                                @RequestParam("userLat") double userLat) { 
14.         //1.獲取外接正方形 
15.         Rectangle rectangle = getRectangle(distance, userLng, userLat); 
16.         //2.獲取位置在正方形內的所有用戶 
17.         List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY()); 
18.         //3.剔除半徑超過指定距離的多餘用戶 
19.         users = users.stream() 
20.             .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance) 
21.             .collect(Collectors.toList()); 
22.         return JSON.toJSONString(users); 
23.     } 
24.  
25.     private Rectangle getRectangle(double distance, double userLng, double userLat) { 
26.         return spatialContext.getDistCalc() 
27.             .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat),  
28.                                  distance * DistanceUtils.KM_TO_DEG, spatialContext, null); 
29.     } 

由於用戶間距離的排序是在業務代碼中實現的，可以看到SQL語句也非常的簡單。

1. <select id="selectUser" resultMap="BaseResultMap"> 
2.         SELECT * FROM user 
3.         WHERE 1=1 
4.         and (longitude BETWEEN ${minlng} AND ${maxlng}) 
5.         and (latitude BETWEEN ${minlat} AND ${maxlat}) 
6.     </select> 

四、MySQL + GeoHash

1、設計思路

這種方式的設計思路更簡單，在存用戶位置信息時，根據用戶經、緯度屬性計算出相應的GeoHash字符串。注意：在計算GeoHash字符串時，需要指定GeoHash字符串的精度，也就是GeoHash字符串的長度，參考上邊的GeoHash精度表。

當需要獲取附近的人，只需用當前用戶GeoHash字符串，資料庫通過WHERE geohash Like 'geocode%' 來查詢GeoHash字符串相似的用戶，然後計算當前用戶與搜索出的用戶距離，篩選出所有距離小於等於指定距離(附近500米)的，即附近的人。

2、利弊分析

利用GeoHash算法實現「附近的人」有一個問題，由於GeoHash算法將地圖分為一個個矩形，對每個矩形進行編碼，得到GeoHash字符串。可我當前的點與鄰近的點很近，但恰好我們分別在兩個區域，明明就在眼前的點偏偏搜不到，實實在在的燈下黑。

如何解決這一問題?

為了避免類似鄰近兩點在不同區域內，我們就需要同時獲取當前點(WX4G0)所在區域附近 8個區域的GeoHash碼，一併進行篩選比較。

在這裡插入圖片描述

3、實現

同樣要設計一張表存用戶的經、緯度信息，但區別是要多一個geo_code欄位，存放GeoHash字符串，此欄位通過用戶經、緯度屬性計算出。使用頻繁的欄位建議加上索引。

1. CREATE TABLE `nearby_user_geohash` ( 
2.   `id` int(11) NOT NULL AUTO_INCREMENT, 
3.   `name` varchar(255) DEFAULT NULL COMMENT '名稱', 
4.   `longitude` double DEFAULT NULL COMMENT '經度', 
5.   `latitude` double DEFAULT NULL COMMENT '緯度', 
6.   `geo_code` varchar(64) DEFAULT NULL COMMENT '經緯度所計算的geohash碼', 
7.   `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '創建時間', 
8.   PRIMARY KEY (`id`), 
9.   KEY `index_geo_hash` (`geo_code`) 
10. ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; 

首先根據用戶經、緯度信息，在指定精度後計算用戶坐標的GeoHash碼，再獲取到用戶周邊8個方位的GeoHash碼在資料庫中搜索用戶，最後過濾掉超出給定距離(500米內)的用戶。

1. private SpatialContext spatialContext = SpatialContext.GEO; 
2.  
3.     /*** 
4.      * 添加用戶 
5.      * @return 
6.      */ 
7.     @PostMapping("/addUser") 
8.     public boolean add(@RequestBody UserGeohash user) { 
9.         //默認精度12位 
10.         String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude()); 
11.         return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now())); 
12.     } 
13.  
14.  
15. /** 
16.      * 獲取附近指定範圍的人 
17.      * 
18.      * @param distance 距離範圍（附近多遠的用戶） 單位km 
19.      * @param len      geoHash的精度（幾位的字符串） 
20.      * @param userLng  當前用戶的經度 
21.      * @param userLat  當前用戶的緯度 
22.      * @return json 
23.      */ 
24.     @GetMapping("/nearby") 
25.     public String nearBySearch(@RequestParam("distance") double distance, 
26.                                @RequestParam("len") int len, 
27.                                @RequestParam("userLng") double userLng, 
28.                                @RequestParam("userLat") double userLat) { 
29.  
30.  
31.         //1.根據要求的範圍，確定geoHash碼的精度，獲取到當前用戶坐標的geoHash碼 
32.         GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len); 
33.         //2.獲取到用戶周邊8個方位的geoHash碼 
34.         GeoHash[] adjacent = geoHash.getAdjacent(); 
35.  
36.         QueryWrapper<UserGeohash> queryWrapper = new QueryWrapper<UserGeohash>() 
37.             .likeRight("geo_code",geoHash.toBase32()); 
38.         Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32())); 
39.  
40.         //3.匹配指定精度的geoHash碼 
41.         List<UserGeohash> users = userGeohashService.list(queryWrapper); 
42.         //4.過濾超出距離的 
43.         users = users.stream() 
44.                 .filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance) 
45.                 .collect(Collectors.toList()); 
46.         return JSON.toJSONString(users); 
47.     } 
48.  
49.  
50.     /*** 
51.      * 球面中，兩點間的距離 
52.      * @param longitude 經度1 
53.      * @param latitude  緯度1 
54.      * @param userLng   經度2 
55.      * @param userLat   緯度2 
56.      * @return 返回距離，單位km 
57.      */ 
58.     private double getDistance(Double longitude, Double latitude, double userLng, double userLat) { 
59.         return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat), 
60.                 spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM; 
61.     } 

五、Redis + GeoHash

Redis 3.2版本以後，基於GeoHash和數據結構Zset提供了地理位置相關功能。通過上邊兩種MySQL的實現方式發現，附近的人功能是明顯的讀多寫少場景，所以用Redis性能更會有很大的提升。

1、設計思路

Redis 實現附近的人功能主要通過Geo模塊的六個命令。

• GEOADD：將給定的位置對象(緯度、經度、名字)添加到指定的key;
• GEOPOS：從key裡面返回所有給定位置對象的位置(經度和緯度);
• GEODIST：返回兩個給定位置之間的距離;
• GEOHASH：返回一個或多個位置對象的Geohash表示;
• GEORADIUS：以給定的經緯度為中心，返回目標集合中與中心的距離不超過給定最大距離的所有位置對象;
• GEORADIUSBYMEMBER：以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。
• 以GEOADD 命令和GEORADIUS 命令簡單舉例：
• 1GEOADD key longitude latitude member [longitude latitude member ...]
• 其中，key為集合名稱，member為該經緯度所對應的對象。

GEOADD 添加多個商戶「火鍋店」位置信息：

1. GEOADD hotel 119.98866180732716    30.27465803229662 火鍋店 

GEORADIUS 根據給定的經緯度為中心，獲取目標集合中與中心的距離不超過給定最大距離(500米內)的所有位置對象，也就是「附近的人」。

1. GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key] 

範圍單位：m | km | ft | mi --> 米 | 千米 | 英尺 | 英裡。

• WITHDIST：在返回位置對象的同時，將位置對象與中心之間的距離也一併返回。距離的單位和用戶給定的範圍單位保持一致。
• WITHCOORD：將位置對象的經度和維度也一併返回。
• WITHHASH：以 52 位有符號整數的形式，返回位置對象經過原始 geohash 編碼的有序集合分值。這個選項主要用於底層應用或者調試，實際中的作用並不大。
• ASC | DESC：從近到遠返回位置對象元素 | 從遠到近返回位置對象元素。
• COUNT count：選取前N個匹配位置對象元素。(不設置則返回所有元素)
• STORE key：將返回結果的地理位置信息保存到指定key。
• STORedisT key：將返回結果離中心點的距離保存到指定key。

例如下邊命令：獲取當前位置周邊500米內的所有飯店。

1. GEORADIUS hotel 119.98866180732716    30.27465803229662 500 m WITHCOORD 

Redis內部使用有序集合(zset)保存用戶的位置信息，zset中每個元素都是一個帶位置的對象，元素的score值為通過經、緯度計算出的52位geohash值。

2、利弊分析

Redis實現附近的人效率比較高，集成也比較簡單，而且還支持對距離排序。不過，結果存在一定的誤差，要想讓結果更加精確，還需要手動將用戶中心位置與其他用戶位置計算距離後，再一次進行篩選。

3、實現

以下就是Java Redis實現版本，代碼非常的簡潔。

1. @Autowired 
2.     private RedisTemplate<String, Object> redisTemplate; 
3.  
4.     //GEO相關命令用到的KEY 
5.     private final static String KEY = "user_info"; 
6.  
7.     public boolean save(User user) { 
8.         Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation<>( 
9.                 user.getName(),  
10.                 new Point(user.getLongitude(), user.getLatitude())) 
11.         ); 
12.         return flag != null && flag > 0; 
13.     } 
14.  
15.     /** 
16.      * 根據當前位置獲取附近指定範圍內的用戶 
17.      * @param distance 指定範圍 單位km ，可根據{@link org.springframework.data.geo.Metrics} 進行設置 
18.      * @param userLng 用戶經度 
19.      * @param userLat 用戶緯度 
20.      * @return 
21.      */ 
22.     public String nearBySearch(double distance, double userLng, double userLat) { 
23.         List<User> users = new ArrayList<>(); 
24.         // 1.GEORADIUS獲取附近範圍內的信息 
25.         GeoResults<RedisGeoCommands.GeoLocation<Object>> reslut =  
26.             redisTemplate.opsForGeo().radius(KEY,  
27.                         new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)), 
28.                         RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs() 
29.                                 .includeDistance() 
30.                                 .includeCoordinates().sortAscending()); 
31.         //2.收集信息，存入list 
32.         List<GeoResult<RedisGeoCommands.GeoLocation<Object>>> content = reslut.getContent(); 
33.         //3.過濾掉超過距離的數據 
34.         content.forEach(a-> users.add( 
35.                 new User().setDistance(a.getDistance().getValue()) 
36.                 .setLatitude(a.getContent().getPoint().getX()) 
37.                 .setLongitude(a.getContent().getPoint().getY()))); 
38.         return JSON.toJSONString(users); 
39.     } 

六、MongoDB + 2d索引

1、設計思路

MongoDB實現附近的人，主要是通過它的兩種地理空間索引 2dsphere 和 2d。兩種索引的底層依然是基於GeoHash來進行構建的。但與國際通用的GeoHash還有一些不同，具體參考官方文檔。

2dsphere 索引僅支持球形表面的幾何形狀查詢。

2d 索引支持平面幾何形狀和一些球形查詢。雖然2d 索引支持某些球形查詢，但 2d 索引對這些球形查詢時，可能會出錯。所以球形查詢儘量選擇 2dsphere索引。

儘管兩種索引的方式不同，但只要坐標跨度不太大，這兩個索引計算出的距離相差幾乎可以忽略不計。

2、實現

首先插入一批位置數據到MongoDB， collection為起名 hotel，相當於MySQL的表名。兩個欄位name名稱，location 為經、緯度數據對。

1. db.hotel.insertMany([ 
2.  {'name':'hotel1',  location:[115.993121,28.676436]}, 
3.  {'name':'hotel2',  location:[116.000093,28.679402]}, 
4.  {'name':'hotel3',  location:[115.999967,28.679743]}, 
5.  {'name':'hotel4',  location:[115.995593,28.681632]}, 
6.  {'name':'hotel5',  location:[115.975543,28.679509]}, 
7.  {'name':'hotel6',  location:[115.968428,28.669368]}, 
8.  {'name':'hotel7',  location:[116.035262,28.677037]}, 
9.  {'name':'hotel8',  location:[116.024770,28.68667]}, 
10.  {'name':'hotel9',  location:[116.002384,28.683865]}, 
11.  {'name':'hotel10', location:[116.000821,28.68129]}, 
12. ]) 

接下來我們給 location 欄位創建一個2d索引，索引的精度通過bits來指定，bits越大，索引的精度就越高。

1. db.coll.createIndex({'location':"2d"}, {"bits":11111}) 

用geoNear命令測試一下， near 當前坐標(經、緯度)，spherical 是否計算球面距離，distanceMultiplier地球半徑，單位是米，默認6378137， maxDistance 過濾條件(指定距離內的用戶)，開啟弧度需除distanceMultiplier，distanceField 計算出的兩點間距離，欄位別名(隨意取名)。

1. db.hotel.aggregate({ 
2.     $geoNear:{ 
3.         near: [115.999567,28.681813], // 當前坐標 
4.         spherical: true, // 計算球面距離 
5.         distanceMultiplier: 6378137, // 地球半徑,單位是米,那麼的除的記錄也是米 
6.         maxDistance: 2000/6378137, // 過濾條件2000米內，需要弧度 
7.         distanceField: "distance" // 距離欄位別名 
8.     } 
9. }) 

看到結果中有符合條件的數據，還多出一個欄位distance 剛才設置的別名，代表兩點間的距離。

1. { "_id" : ObjectId("5e96a5c91b8d4ce765381e58"), "name" : "hotel10", "location" : [ 116.000821, 28.68129 ], "distance" : 135.60095397487655 } 
2. { "_id" : ObjectId("5e96a5c91b8d4ce765381e51"), "name" : "hotel3", "location" : [ 115.999967, 28.679743 ], "distance" : 233.71915803517447 } 
3. { "_id" : ObjectId("5e96a5c91b8d4ce765381e50"), "name" : "hotel2", "location" : [ 116.000093, 28.679402 ], "distance" : 273.26317035334176 } 
4. { "_id" : ObjectId("5e96a5c91b8d4ce765381e57"), "name" : "hotel9", "location" : [ 116.002384, 28.683865 ], "distance" : 357.5791936927476 } 
5. { "_id" : ObjectId("5e96a5c91b8d4ce765381e52"), "name" : "hotel4", "location" : [ 115.995593, 28.681632 ], "distance" : 388.62555058249967 } 
6. { "_id" : ObjectId("5e96a5c91b8d4ce765381e4f"), "name" : "hotel1", "location" : [ 115.993121, 28.676436 ], "distance" : 868.6740526419927 } 

總結

本文重點並不是在具體實現，旨在給大家提供一些設計思路，面試中可能你對某一項技術了解的並不深入，但如果你的知識面寬，可以從多方面說出多種設計的思路，能夠侃侃而談，那麼會給面試官極大的好感度，拿到offer的概率就會高很多。而且「附近的人」 功能使用的場景比較多，尤其是像電商平臺應用更為廣泛，所以想要進大廠的同學，這類的知識點還是應該有所了解的。

【編輯推薦】

【責任編輯：

武曉燕

TEL：[phone]】

點讚 0