上古面试题：让你实现一个附近的人功能，你有什么方案?
“附近的人” 功能生活中是比较常用的，像外卖app附近的餐厅，共享单车app里附近的车辆。既然常用面试被问的概率就很大，实现方法有很多种，MySQL8之后的空间索引，MongoDB的2d索引，Redis3.2之后的GEO等都可以很高效且完美的满足需求，本文主要讨论如何用Redis GEO实现距离计算和排序，以及分页。
本文仅讨论Redis GEO 的实战应用，不讨论具体算法实现。
世界上标识一个位置，通用的做法就使用经、纬度。经度的范围在 (-180, 180]，纬度的范围 在(-85, 85)左右，纬度正负以赤道为界，北正南负，经度正负以本初子午线 (英国格林尼治天文台) 为界，东正西负。
问：其他八股文都说纬度范围在-90到+90之间啊，为啥你这儿是-85到+85，你丫胡说八道！！！
答：确切的说有效纬度范围为从 -85.05112878 到 85.05112878 度，由于地球的几何形状是椭球体，不同纬度上的地球半径是不同的，这意味着在极端高纬度地区，地球表面的形状开始偏离球形，纬度值的变化不再与地球表面实际的距离变化成正比。因此，通常将纬度的范围限制在85度以内，以保证计算的精度和准确性。
一般咱们到优化的地步了，数据肯定有一定量了，所以，抛开剂量谈毒性，抛开数据量谈优化都是扯淡，那么，我们先来造它个三千万条数据呗。
这里我找了以前一个社交产品的线上用户库的经纬度数据，再结合随机数，写入Redis。
截取部分数据样本：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | "336" "-74.0059413" "40.7127837" "419" "104.039485473283" "30.5069680279405" "427" "104.075410381516" "30.5288014162613" "564" "104.065676435045" "30.6395854135255" "565" "103.988974449557" "30.7551896505727" "607" "-99.5266638603988" "17.6447030436412" "777" "-90.2714753217624" "32.3085690942718" "800" "-94.1788629536463" "30.0809111120459" "878" "-87.6043277" "41.7491088" "890" "-74.580487" "39.9758756" "900" "-83.379117700051" "42.4226956645676" "938" "-73.4646515783357" "45.503437523005" "952" "-73.95600334265893" "40.601518197290275" "956" "0" "0" |
写入Redis的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | func writeGeoData(geoKey string) { startTime := time.Now().UnixMilli() // 读取文件 file, err := os.Open("july_user.txt") if err != nil { log.Fatal(err) } defer file.Close() var totalCount int64 = 0 // 逐行扫描文件 scanner := bufio.NewScanner(file) locationBuffer := []*redis.GeoLocation{} for scanner.Scan() { dataArray := strings.Split(scanner.Text(), " ") if len(dataArray) == 3 { userID := strings.ReplaceAll(dataArray[0], "\"", "") longitude, err := strconv.ParseFloat(strings.ReplaceAll(dataArray[1], "\"", ""), 64) if err != nil { log.Fatalln(err.Error()) } latitude, err := strconv.ParseFloat(strings.ReplaceAll(dataArray[2], "\"", ""), 64) if err != nil { log.Fatalln(err.Error()) } if longitude > 180 || longitude < -180 { longitude = longitude / 2.0 } if latitude > 85 || latitude < -85 { latitude = latitude / 2.0 } locationBuffer = append(locationBuffer, &redis.GeoLocation{ Name: userID, Longitude: longitude, Latitude: latitude, }) if len(locationBuffer) == 500 { count, err := redisClient.GeoAdd(context.Background(), geoKey, locationBuffer...).Result() if err != nil { log.Fatalln(err.Error()) } totalCount += count locationBuffer = []*redis.GeoLocation{} } } } if len(locationBuffer) > 0 { count, err := redisClient.GeoAdd(context.Background(), geoKey, locationBuffer...).Result() if err != nil { log.Fatalln(err.Error()) } totalCount += count locationBuffer = []*redis.GeoLocation{} } if err := scanner.Err(); err != nil { log.Fatal(err) } for i := 0; i < 25_000_000; i++ { // 2500万条随机数据 userID := fmt.Sprintf("%d", 6522446+i) longitude := randFloats(-180.0, 180.0, 1)[0] latitude := randFloats(-85.0, 85.0, 1)[0] locationBuffer = append(locationBuffer, &redis.GeoLocation{ Name: userID, Longitude: longitude, Latitude: latitude, }) if len(locationBuffer) == 500 { count, err := redisClient.GeoAdd(context.Background(), geoKey, locationBuffer...).Result() if err != nil { log.Fatalln(err.Error()) } totalCount += count locationBuffer = []*redis.GeoLocation{} } } fmt.Println("总数据条数：", totalCount, "组装写入耗时：", time.Now().UnixMilli()-startTime, "ms") } |
运行结果：
1 | 总数据条数： 31352891 组装写入耗时： 189617 ms |
Redis为单核4GB内存，写入3100万条数据，占用3.25GB内存，耗时3分钟多一点点，写入数据也不算慢嘛。
那既然咱们都有三千万用户了，那么按照二八法则，每天有个600万的活跃用户不过分吧，均分到每秒才70个不到？
那不行，整活嘛，先来他个一万的并发请求附近的人。
稳一下，别浪，咱们先看看单次请求的情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | func calcDistance(geoKey string) { startTime := time.Now().UnixMilli() longitude := randFloats(-180.0, 180.0, 1)[0] latitude := randFloats(-85.0, 85.0, 1)[0] results, err := redisClient.GeoRadius(context.Background(), geoKey, longitude, latitude, &redis.GeoRadiusQuery{ Radius: 10, Unit: "km", WithCoord: true, WithDist: true, WithGeoHash: false, Count: 0, Sort: "ASC", Store: "", StoreDist: "", }).Result() if err != nil { log.Fatalln(err.Error()) } fmt.Println("条数：", len(results), "耗时：", time.Now().UnixMilli()-startTime, "ms") for _, result := range results { fmt.Println("Distance: ", result.Dist, "Longitude:", result.Longitude, "Latitude:", result.Latitude, "UserID:", result.Name) } } |
输出结果，随机处理5次：
1 2 3 4 5 | 条数： 26 耗时： 1 ms 条数： 32 耗时： 2 ms 条数： 63 耗时： 1 ms 条数： 9 耗时： 1 ms 条数： 116 耗时： 2 ms |
从结果可以看出，每次由于随机位置的不同，得到10公里内数据条数不同，但出结果基本都在3ms内；
作为对比，MySQL在无空间索引的情况下，同等硬件条件，适用st_distance函数计算并排序，基本需要50秒以上才能完成计算，而且数据库CPU满载。
两相对比之下，效率至少5000倍的差距。
1 2 3 4 5 | for i := 0; i < 10000; i++ { go func() { calcDistance(geoKey) }() } |
运行结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | 条数： 10 耗时： 1106 ms 条数： 15 耗时： 1106 ms 条数： 12 耗时： 1106 ms 条数： 17 耗时： 1150 ms 条数： 63 耗时： 1107 ms 条数： 15 耗时： 1106 ms 条数： 73 耗时： 1106 ms 条数： 11 耗时： 1151 ms 条数： 12 耗时： 1106 ms 条数： 15 耗时： 1106 ms 条数： 49 耗时： 1106 ms 条数： 54 耗时： 1106 ms 条数： 13 耗时： 1106 ms 条数： 23 耗时： 1150 ms 条数： 10 耗时： 1150 ms 条数： 10 耗时： 1150 ms 条数： 11 耗时： 1150 ms 条数： 24 耗时： 1106 ms 条数： 11 耗时： 1106 ms 条数： 10 耗时： 1106 ms 条数： 7 耗时： 1106 ms 条数： 23 耗时： 1106 ms 条数： 12 耗时： 1106 ms 条数： 38 耗时： 1106 ms 条数： 17 耗时： 1106 ms 条数： 9 耗时： 1106 ms 条数： 12 耗时： 1106 ms 条数： 10 耗时： 1106 ms 条数： 17 耗时： 1106 ms 条数： 27 耗时： 1106 ms 条数： 89 耗时： 1106 ms 条数： 9 耗时： 1150 ms |
从结果可以看到，在一万个请求同时进行的情况下，最慢1.15秒能处理完，此时CPU峰值占用42%，也就是说完全可以支持随机的万级QPS，是不是很amazing。
注意，此处运行结果显示1150毫秒是因为Redis为单线程执行，所有的请求几乎同一时间发起，但Redis为顺序计算，最后一条实际上是所有请求都执行完成的总时间。
单次执行的时间仍然为毫秒级。
可是问题又来了，附近的人或者店的需求现实情况可能是当前城市，距离我100公里内离我最近的二百个。
那么我们调整一下参数，增大距离到100公里和数量200条，同样同时10000个请求。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | func calcDistance(geoKey string) { startTime := time.Now().UnixMilli() longitude := randFloats(-180.0, 180.0, 1)[0] latitude := randFloats(-85.0, 85.0, 1)[0] results, err := redisClient.GeoRadius(context.Background(), geoKey, longitude, latitude, &redis.GeoRadiusQuery{ Radius: 100, Unit: "km", WithCoord: true, WithDist: true, WithGeoHash: false, Count: 200, Sort: "ASC", Store: "", StoreDist: "", }).Result() if err != nil { log.Fatalln(err.Error()) } fmt.Println("条数：", len(results), "耗时：", time.Now().UnixMilli()-startTime, "ms") // for _, result := range results { // fmt.Println("Distance: ", result.Dist, "Longitude:", result.Longitude, "latitude:", result.Latitude, "UserID:", result.Name) // } } |
输出结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 条数： 200 耗时： 25590 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25589 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25589 ms 条数： 200 耗时： 25589 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25590 ms 条数： 200 耗时： 25589 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25633 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25632 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25588 ms 条数： 200 耗时： 25633 ms |
从结果来看，不是很理想啊，最慢的都快到26秒了，似乎又慢到不能接受了。
此时观察Redis CPU，CPU占用率100%，满载了。
这是为什么呢？答：Redis GEO的距离计算CPU消耗会随着距离范围增大而略微增大，且Redis是单线程的，所以在CPU性能达到瓶颈之后，计算速度会略微下降（实际上每次计算仍然在1-2ms内完成）。
那怎么办呢？答：多开几个一样的实例，分别连接不同的实例进行数据同步然后计算就好了，最简单的解决方案就是开启主从模式，使用多个slave（我就不爱管国外那套政治正确的玩意儿，就爱写master-slave）进行计算。
斥巨资阿里云开1个主节点，5个从节点，直接再来线上试试效果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 条数： 200 耗时： 4261 ms 条数： 200 耗时： 4261 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms 条数： 200 耗时： 4262 ms |
从运行结果看，效果显著，因为每个节点仅原来1/6的运算量，但需要注意：此时要使用直连模式自行分配请求到不同的节点上，代理模式整个过程依然是串行执行，不会有显著提升。
上面解决了顶住并发的问题，但在实际应用场景中很难一次返回200条数据或更多给到前端，需要翻页，而Redis的距离计算又不支持设置距离范围，这个时候怎么办呢？
答：使用Sorted Set把前面查出来的200条数据存起来，如果按照页码翻页，那直接使用zrange进行查询，如果按距离翻页，使用zrangebyscore进行查询即可，接下来上代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | type GeoFlipPageType int const ( GeoFlipPageTypeDistance GeoFlipPageType = iota GeoFlipPageTypePageNumber ) func testGeoFlipPage( geoKey string, longitude, latitude float64, pageMark string, flipType GeoFlipPageType, ) ([]*GeoLocation, error) { resultsKey := fmt.Sprintf("%s_%f_%f_zs", geoKey, longitude, latitude) isExist, err := redisClient.Exists(context.Background(), resultsKey).Result() if err != nil { return nil, err } if isExist != 1 { // 如果没有数据，读取并组装 locations, err := redisClient.GeoRadius( context.Background(), geoKey, longitude, latitude, &redis.GeoRadiusQuery{ Radius: 100, Unit: "km", WithCoord: true, WithDist: true, WithGeoHash: true, Count: 200, Sort: "ASC", Store: "", StoreDist: "", }, ).Result() if err != nil { return nil, err } members := []redis.Z{} for _, result := range locations { members = append(members, redis.Z{ Score: result.Dist, Member: &GeoLocation{result}, }) } // 写入sorted set缓存备用 _, err = redisClient.ZAdd(context.Background(), resultsKey, members...).Result() if err != nil { return nil, err } // 零时数据，设置过期时间30分钟 _, err = redisClient.Expire(context.Background(), resultsKey, time.Minute*30).Result() if err != nil { return nil, err } } results := []*GeoLocation{} switch flipType { case GeoFlipPageTypeDistance: err = redisClient.ZRangeByScore(context.Background(), resultsKey, &redis.ZRangeBy{ Min: pageMark, Max: "100", Offset: 1, // 偏移一个，过滤分界线上的元素 Count: 20, }).ScanSlice(&results) if err != nil { return nil, err } return results, nil case GeoFlipPageTypePageNumber: page, err := strconv.ParseInt(pageMark, 10, 64) if err != nil { log.Fatalln(err.Error()) } if page < 1 { page = 1 } page = page - 1 err = redisClient.ZRange( context.Background(), resultsKey, page*20, (page+1)*20, ).ScanSlice(&results) if err != nil { return nil, err } return results, nil default: return []*GeoLocation{}, nil } } // 实现 encoding.BinaryMarshaler 接口 type GeoLocation struct { redis.GeoLocation } func (m *GeoLocation) UnmarshalBinary(data []byte) error { return json.Unmarshal(data, m) } func (m *GeoLocation) MarshalBinary() (data []byte, err error) { return json.Marshal(m) } |
调用代码：
1 2 3 4 5 6 7 8 9 10 11 12 | func testGeo() { geoKey := "RedisGeoKey" results, err := testGeoFlipPage(geoKey, 104.067561, 30.526257, "1", GeoFlipPageTypePageNumber) if err != nil { log.Fatalln(err.Error()) } for _, result := range results { fmt.Println("Distance: ", result.Dist, "Longitude:", result.Longitude, "Latitude:", result.Latitude, "UserID:", result.Name) } } |
执行结果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | Distance: 0.0393 Longitude: 104.0679207444191 Latitude: 30.52608669604013 UserID: 6052336 Distance: 0.0468 Longitude: 104.06714826822281 Latitude: 30.52648211254099 UserID: 3247975 Distance: 0.0488 Longitude: 104.06705170869827 Latitude: 30.52624384875201 UserID: 2918923 Distance: 0.0534 Longitude: 104.067003428936 Latitude: 30.526248918194334 UserID: 3680103 Distance: 0.0566 Longitude: 104.06699270009995 Latitude: 30.526117112694045 UserID: 4066761 Distance: 0.0592 Longitude: 104.06697124242783 Latitude: 30.526416209790845 UserID: 2807467 Distance: 0.0602 Longitude: 104.06696051359177 Latitude: 30.526416209790845 UserID: 2834183 Distance: 0.061 Longitude: 104.06697124242783 Latitude: 30.52605120994391 UserID: 2981010 Distance: 0.0629 Longitude: 104.06690686941147 Latitude: 30.526302147338676 UserID: 4876728 Distance: 0.063 Longitude: 104.06690686941147 Latitude: 30.526317355665633 UserID: 3429744 Distance: 0.0705 Longitude: 104.0668585896492 Latitude: 30.52644662644476 UserID: 2833174 Distance: 0.1183 Longitude: 104.06660109758377 Latitude: 30.52692568874388 UserID: 2259396 Distance: 0.1506 Longitude: 104.06744867563248 Latitude: 30.527607528735736 UserID: 2239943 Distance: 0.168 Longitude: 104.06755059957504 Latitude: 30.527767216168776 UserID: 4833225 Distance: 0.1741 Longitude: 104.06930476427078 Latitude: 30.526697563839534 UserID: 2529638 Distance: 0.1991 Longitude: 104.06603783369064 Latitude: 30.525039856201325 UserID: 4479366 Distance: 0.2038 Longitude: 104.06939595937729 Latitude: 30.527184230302126 UserID: 5279558 Distance: 0.2103 Longitude: 104.06946033239365 Latitude: 30.5272045080714 UserID: 4413513 Distance: 0.2285 Longitude: 104.06880587339401 Latitude: 30.524505030036707 UserID: 4712364 Distance: 0.2711 Longitude: 104.06835526227951 Latitude: 30.528596069987877 UserID: 460863 Distance: 0.3088 Longitude: 104.06987875699997 Latitude: 30.524327599555555 UserID: 2183474 |
至此，整个Redis实现附近的人功能并翻页的功能全部完成，只需结合对应的业务数据库根据ID查询出对应的详细数据即可。
1. Redis GEO用户经纬度存储和距离计算效率非常高，3100万条数据需要3GB左右的内存，妥妥的超大key。
2. 距离计算在数据量大时受限于单核CPU的瓶颈，在超多并发的情况下，可能需要等待很长时间，但可以通过增加完全相同的实例来分担压力。
3. Redis GEO计算距离原生不支持分页，需要将结果存储到List或Sorted Set来曲线结果，实现翻页功能。
程序猿老龚（龚杰洪）原创，版权所有，转载请注明出处.